數(shù)據(jù)結構實驗報告內容及格式

實驗一線性表順序存儲與操作1實驗目的編寫程序建立順序存儲的線性表L,其數(shù)據(jù)元素按非遞減有序排列，插入一個元素X后，該線性表L仍保持有序。2實驗內容/*2005-03-04 實驗內容：編寫程序建立順序存儲的線性表L，其數(shù)據(jù)元素按非遞減有序排列，插入一個元素X后，該線性表L仍保持有序。實驗要求：L的存儲結構為：#defineLIST_INIT_SIZE100//順序表存儲空間的初分配量#defineLISTINCREMENT10 //順序表存儲空間的分配增量struct 〃線性表的結構{int*elem; //存儲空間的基地址intlength; 〃當前的長度intlistsize;〃當前分配的容量};測試數(shù)據(jù)：建立：1,3,5,7,9插入：x=-1,6,10 */#include<stdio.h>#include<malloc.h>#include<conio.h>#include<string.h>#defineLIST_INIT_SIZE100//順序表存儲空間的初分配量#defineLISTINCREMENT10 //順序表存儲空間的分配增量typedefstruct //線性表的結構{int*elem; 〃存儲空間的基地址intlength; //當前的長度intlistsize;//當前分配的容量}SQLIST;voidCreate(SQLIST&L) 〃建立線性表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)

printf（”為線性表分配空間失敗!”）;L.length=0;L.listsize=LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx) 〃實現(xiàn)有序的插入操作{if(A.length==A.listsize)printf('線性表錯誤!”)；if(x>A.elem[A.length-1])elseA.elem[A.length]=x; 〃與最大的元素進行判斷，以決定是否插在最后elseinti=0;while(x>=A.elem[i])i++; 〃從第一個元素起，尋找正確的插入位置for(intj=A.length;j>=i;j--)A.elem[j+1]=A.elem[j];〃將所找位置后面的所有數(shù)據(jù)都向右移動一個位A.elem[i]=x;//插入新的數(shù)據(jù)A.length++;//順序表的長度加1}voidmain(){printf("程序說明:\n");printf(- 建立順序存儲的單鏈表，其數(shù)據(jù)元素按元素值非遞減有序排列，插入一個數(shù)據(jù)元素后，該線性表仍保持有序\n\n");SQLISTs;Create(s); 〃為線性表分配空間s.elem[0]=1;//建表s.elem[1]=3;s.elem[2]=5;s.elem[3]=7;s.elem[4]=9;s.length=5;printf("\n\n已建立的順序表為：\n");for(inti=0;i<s.length;i++)printf("%d”,s.elem[i]);printf("\n\n請輸入要插入的數(shù)據(jù):\n");inttmp;scanf("%d”,&tmp);Insert(s,tmp);printf("\n\n插入數(shù)據(jù)后的順序表為：\n");for(i=0;i<s.length;i++)printf("%d”,s.elem[i]);_getch();//如果不加如該句，則執(zhí)行用VisualC++編譯后的exe文件，控制臺窗口會一閃而過，看不請執(zhí)行結果:)}3實驗結果4實驗總結與分析實驗二線性表鏈式存儲與操作1實驗目的掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運算在鏈接存儲結構上的運算。2實驗內容#include<stdio.h>#include<malloc.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineERROR0#defineOK1#defineEQUAL1#defineOVERFLOW-1#defineLIST_INIT_SIZE100#defineLISTINCREMENT10structSTU{\\線性表的結構charname[20];charstuno[10];intage;intscore;}stu[50];typedefstructSTUElemType;structLNODE{ElemTypedata;structLNODE*next;};typedefstructLNODELNode;typedefstructLNODE*LinkList;intinit(LinkList*L)\\建表{*L=(LNode*)malloc(sizeof(LNode));if(!L)exit(ERROR);(*L)->next=NULL;returnOK;}/*init*/intListLength(LinkListL)\\返回數(shù)據(jù)元素個數(shù){intj=0;while(L->next){L=L->next;j++;}returnj;}intGetElem(LinkListL,inti,ElemType*。)\\用e返回L中第i值{LinkListp;intj;p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!pllj>1)returnERROR;*e=p->data;returnOK;intEqualList(ElemType*e1,ElemType*e2)\比匕較{if(strcmp(e1->name,e2->name)==0)return1;elsereturn0;}intLess_EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name)<=0)return1;elsereturn0;}intLocateElem(LinkListLa,ElemTypee,inttype){//inti;LinkListp;p=La;switch(type){caseEQUAL:while(p->next){p=p->next;if(EqualList(&p->data,&e))return1;}return0;break;default:break;}return0;}voidMergeList(LinkListLa,LinkListLb,LinkList*Lc)\\合并表{LinkListpa,pb,pc;pa=La->next;pb=Lb->next;*Lc=pc=La;while(pa&&pb){if(Less_EqualList(&pa->data,&pb->data)){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);\'釋放表Lb}voidprintlist(LinkList1)\\輸出表{//inti;LinkListp;p=L;printf("namestuno agescore\n");while(p->next){p=p->next;printf("%-10s%s\t%d\t%d\n",p->,p->data.stuno,p->data.age,p->data.score);}printf("\n");}intListInsert(LinkListL,inti,ElemTypee)\插入信息{LinkListp,s;intj;p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!pllj>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}/*ListInsertBeforei*/intmain(){structSTUe;LinkListLa,Lb,Lc;system("cls");\\清屏printf("\n\n ListDemoisrunning... \n\n");printf("FirstisInsertListfunction.\n");init(&La);strcpy(,"stu1”);strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(La,1,e);\\插入信息1strcpy(,"stu3”);strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(La,2,e);\\插入信息2printlist(La);\'輸出表Lagetch();strcpy(,"stu5”);strcpy(e.stuno,”100003");e.age=80;e.score=1000;ListInsert(La,3,e);\\插入信息3printlist(La);\'輸出表Lagetch();init(&Lb);\\建立Lb表strcpy(,"stu2”);strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,1,e);\\插入信息1strcpy(,"stu4”);strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(Lb,2,e);\\插入信息2strcpy(,"stu6”);strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,3,e);\\插入信息3printlist(Lb);\'輸出表Lbgetch();MergeList(La,Lb,&Lc);\\歸并La,LB成為Lcprintlist(Lc);\'輸出Lc表getch();}3實驗結果4實驗總結與分析實驗三棧的應用---判斷字符串是否中心對稱1實驗目的掌握棧的順序存儲結構和鏈式存儲結構，以便在實際背景下靈活運用。掌握棧的特點，即先進后出。掌握棧的基本運算，如入棧與出棧等運算在順序存儲結構上的實現(xiàn)。2實驗內容/*2005-03-2 實驗內容：有n個字符的字符串，判斷字符串是否中心對稱。如:xyzzyx和xyzyx都是中心對稱的字符串實驗要求：字符串放在單鏈表中，內容1由棧實現(xiàn)(存儲結構自定)并實現(xiàn)利用棧的入棧和出棧完成判斷。 */#include<stdio.h>#include<stdlib.h>#include<string.h>#definemax100//////////////////定義單鏈表的結點類型////////////////////typedefstructnode{chardata;structnode*next;}LinkList;/////////////////根據(jù)輸入的字符(存儲在字數(shù)組中)建立一個不帶結點的單鏈表////////////LinkList*create(chars[])〃函數(shù)返回的類型為指針{LinkList*head, 〃頭指針*newNode,//newNode始終指向新開的結點*tail; //tail始終指向鏈表中的最后一個結點for(inti=0;s[i]!='\0';i++){newNode=(LinkList*)malloc(sizeof(LinkList));〃新開一個結點newNode->data=s[i];newNode->next=NULL;if(i==0) 〃如果只輸入了一個字符{head=newNode;tail=head;}else{tail->next=newNode;//把新開的結點連接到鏈表的最后一個結點上tail=newNode;}}returnhead;}////////////////////定義棧的存儲類型//////////////////////////typedefstruct{char*base; 〃棧頂指針(始終指向棧頂元素的下一個位置)char*top; 〃棧底指針(始終指向棧底)}stack;voidInitStack(stack&s) 〃棧的初始化{s.base=(char*)malloc(max*sizeof(char));s.top=s.base;}voidpush(stack&s,chare) 〃進棧函數(shù){*s.top++=e;}charpop(stack&s,char&e) 〃出棧函數(shù){e=*--s.top;returne;}///////////////判斷以單鏈表存儲的字符串是否對稱的函數(shù)///////////////intjudge(LinkList*head){stacks;chare;InitStack(s);〃定義一個棧并初始化LinkList*p=head;//把頭指針賦給p,即讓p指向第一個結點while(p!=NULL){push(s,p->data);p=p->next;}p=head;while(p!=NULL) 〃將棧中的元素彈出，逐個與鏈表中的元素比較(可以看成是把鏈表換個方向，然后與原來的鏈表比較){if(p->data==pop(s,e))p=p->next;elsebreak;〃如果不相等，說明不是對稱，調處循環(huán)}if(p==NULL)return1;elsereturn0;}voidmain(){printf("程序說明:\n");printf("目的：判斷字符串是否關于中心對稱.\n");printf(-方法：字符串用單鏈表實現(xiàn)，將字符串全部入棧然后比較\n\n");charstr[max];//定義一個字符數(shù)組，用來存儲輸入的字符//LinkList*h;while(1){printf("\n\n請輸入字符串(輸入cls清屏,exit退出):")；gets(str);if(strcmp(str,"exit")==0)break;if(strcmp(str,"cls")==0)system("cls");switch(judge(create(str)))〃根據(jù)輸入的字符串(存儲在字符數(shù)組中)建立單鏈表然后進行判斷{case1:printf("\n ?％s是中心對稱的的字符串\n",str);break;case0:printf("\n ?％s不是關于中心對稱的\n”,str);break;}}}3實驗結果4實驗總結與分析實驗四順序隊列的實現(xiàn)---約瑟夫環(huán)問題的實現(xiàn)1實驗目的掌握隊列的順序存儲結構和鏈式存儲結構，以便在實際背景下靈活運用。掌握隊列的特點，即先進先出。掌握隊列的基本運算，如入隊與出隊等運算在順序存儲結構的實現(xiàn)。2實驗內容#include<stdio.h>#include<stdlib.h>structLnodeintnumber;intpa