數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目 C語(yǔ)言

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)內(nèi)容和目的：掌握幾種基本的數(shù)據(jù)結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)等在求解實(shí)際問(wèn)題中的應(yīng)用，以及培養(yǎng)書(shū)寫規(guī)范文檔的技巧。學(xué)習(xí)基本的查找和排序技術(shù)。讓我們?cè)趯?shí)際上機(jī)中具有編制相當(dāng)規(guī)模的程序的能力。養(yǎng)成一種良好的程序設(shè)計(jì)風(fēng)格。

實(shí)驗(yàn)教材：數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）清華大學(xué)出版社2007年實(shí)驗(yàn)項(xiàng)目：實(shí)驗(yàn)一、棧和循環(huán)隊(duì)列㈠、實(shí)驗(yàn)內(nèi)容：棧掌握棧的特點(diǎn)(先進(jìn)后出FILO)及基本操作,如入棧、出棧等，棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以便在實(shí)際問(wèn)題背景下靈活應(yīng)用。本程序采用的是鏈棧結(jié)構(gòu)，具有初始化一個(gè)棧、PUSH、POP、顯示所有棧里的元素四個(gè)功能。循環(huán)隊(duì)列掌握隊(duì)列的特點(diǎn)(先進(jìn)先出FIFO)及基本操作,如入隊(duì)、出隊(duì)等，學(xué)會(huì)循環(huán)隊(duì)列的實(shí)現(xiàn)，以便在實(shí)際問(wèn)題背景下靈活運(yùn)用。本程序具有初始化一個(gè)隊(duì)列、入隊(duì)、出隊(duì)、顯示隊(duì)列的所有元素、隊(duì)列長(zhǎng)度五個(gè)功能。㈡、實(shí)驗(yàn)代碼棧程序代碼：#include<stdio.h>#include<malloc.h>#defineStack_Size6#defineERROR0#defineOK1typedefintSElemType;typedefstructSNode{ SElemTypedata; structSNode*next;}SNode,*LinkStack;intCreatTwo(LinkStack&head,intn){ inti; SNode*p; head=(LinkStack)malloc(sizeof(SNode)); head->next=NULL; printf("請(qǐng)輸入數(shù)據(jù)(數(shù)字):\n"); for(i=n;i>0;--i) { p=(SNode*)malloc(sizeof(SNode)); scanf("%d",&p->data); p->next=head->next; head->next=p; } return1;}intmenu_select(){ intsn; for(;;) { scanf("%d",&sn); if(sn<1||sn>6) printf("\n\t輸入錯(cuò)誤，請(qǐng)重新輸入\n"); else break; } returnsn;}intPush(LinkStack&top,SElemTypee){ SNode*q; q=(LinkStack)malloc(sizeof(SNode)); if(!q) { printf("溢出!\n"); return(ERROR); } q->data=e; q->next=top->next; top->next=q; return(OK);}intPop(LinkStack&top,SElemType&e){ SNode*q; if(!top->next) {printf("error!\n"); return(ERROR);} e=top->next->data; q=top->next; top->next=q->next; free(q); return(OK);}voidmain(){inte; LinkStacktop; printf("1.初始化一個(gè)棧;\n2.PUSH;\n3.POP;\n4.顯示所有棧里的元素;\n5.結(jié)束;\n"); while(1) { switch(menu_select()) { case1: if(CreatTwo(top,Stack_Size))printf("Success!\n");break;case2: printf("Push:\n"); scanf("%d",&e); if(Push(top,e))printf("Success!\n"); break; case3: if(Pop(top,e))printf("Success!\n"); printf("%d\n",e); break; case4: LinkStackp; printf("所有棧里的元素:\n"); p=top; while(p->next) {p=p->next; printf("%7d",p->data); } printf("\n"); break; case5: return; } }}運(yùn)行結(jié)果：循環(huán)隊(duì)列程序代碼：#include<stdlib.h>#include<stdio.h>#defineOVERFLOW-1#defineOK1#defineERROR0#defineMAXSIZE100typedefstruct{ int*elem;//隊(duì)列存儲(chǔ)空間 intfront; intrear;}SqQueue;//判斷選擇是否正確intmenu_select(){ intsn; for(;;) { scanf("%d",&sn); if(sn<1||sn>6) printf("\n\t輸入錯(cuò)誤，請(qǐng)重新輸入\n"); else break; } returnsn;}//參數(shù)(傳出)SqQueue&Q,循環(huán)隊(duì)列(空)intInitQueue(SqQueue&Q){ Q.elem=(int*)malloc(MAXSIZE*sizeof(int)); if(!Q.elem)exit(OVERFLOW); Q.front=Q.rear=-1; for(inti=0;i<MAXSIZE;i++) Q.elem[i]=-1; returnOK;}//返回Q的元素個(gè)數(shù)intQueueLength(SqQueueQ){ return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}//顯示隊(duì)列的元素voidDisplay(SqQueueQ){ for(inti=0;i<=QueueLength(Q);i++) if(Q.elem[i]!=-1)printf("%d",Q.elem[i]); printf("\n");}//入隊(duì)intEnQueue(SqQueue&Q,inte){ Q.rear=(Q.rear+1)%MAXSIZE; if(Q.rear==Q.front)returnERROR; Q.elem[Q.rear]=e; returnOK;}//出隊(duì)intDeQueue(SqQueue&Q,int&e){ if(Q.front==Q.rear)returnERROR; e=Q.elem[Q.front+1]; Q.elem[Q.front+1]=-1; Q.front=(Q.front+1)%MAXSIZE; returnOK;}voidmain(){ SqQueueQ; InitQueue(Q); intelem,e; printf("請(qǐng)輸入隊(duì)列元素(以0結(jié)束):\n"); scanf("%d",&elem); while(elem!=0) { EnQueue(Q,elem); scanf("%d",&elem); } printf("隊(duì)列為：\n"); Display(Q); printf("1.初始化一個(gè)隊(duì)列;\n2.入隊(duì);\n3.出隊(duì);\n4.顯示隊(duì)列的所有元素;\n5.隊(duì)列長(zhǎng)度:\n6.結(jié)束;\n"); while(1) { switch(menu_select()) { case1: printf("請(qǐng)輸入隊(duì)列元素(以0結(jié)束):\n"); scanf("%d",&elem); while(elem!=0) {EnQueue(Q,elem); scanf("%d",&elem);} printf("隊(duì)列為：\n"); Display(Q); fflush(stdin); break;case2: scanf("%d",&elem); EnQueue(Q,elem); printf("隊(duì)列為：\n"); Display(Q); fflush(stdin); break; case3: DeQueue(Q,elem); printf("隊(duì)列為：\n"); Display(Q); break; case4: printf("\n隊(duì)列的所有元素:\n"); Display(Q); break; case5: printf("%d\n",QueueLength(Q)); break; case6: return; } }}運(yùn)行結(jié)果：實(shí)驗(yàn)二、數(shù)組㈠、實(shí)驗(yàn)內(nèi)容：數(shù)組一般不做插入或刪除操作，也就是說(shuō)，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。本程序數(shù)組的大小定義為3*3，可以通過(guò)修改“#defineM”來(lái)變動(dòng)。本程序具有矩陣相加、矩陣A轉(zhuǎn)置、矩陣B轉(zhuǎn)置、矩陣相乘四個(gè)功能。㈡、實(shí)驗(yàn)代碼：#include<stdio.h>#defineM3voidMatrixAdd(intm1[M][M],intm2[M][M],intresult[M][M])//兩個(gè)矩陣m1和m2相加,結(jié)果放到result{ inti,j; for(i=0;i<M;i++) { for(j=0;j<M;j++) result[i][j]=m1[i][j]+m2[i][j]; }}voidMatrixTrams(intm1[M][M],intresult[M][M])//矩陣轉(zhuǎn)置{ inti,j; for(i=0;i<M;i++) { for(j=0;j<M;j++) result[i][j]=m1[j][i]; }}voidMatrixMultiply(intm1[M][M],intm2[M][M],intresult[M][M]){ inti,j; for(i=0;i<M;i++) { for(j=0;j<M;j++) { result[i][j]=0; for(intk=0;k<M;k++) result[i][j]+=m1[i][k]*m2[k][j]; } }}voidDisplay(intresult[M][M])//顯示矩陣{ inti,j; for(i=0;i<M;i++) { for(j=0;j<M;j++) printf("%-5d",result[i][j]); printf("\n"); }}voidmain(){ intA[M][M],B[M][M]; inti,j; printf("請(qǐng)輸入第一個(gè)矩陣：\n"); for(i=0;i<M;i++) for(j=0;j<M;j++) scanf("%d",&A[i][j]); printf("請(qǐng)輸入第二個(gè)矩陣：\n"); for(i=0;i<M;i++) for(j=0;j<M;j++) scanf("%d",&B[i][j]); intresult[M][M]; /*printf("\n矩陣A:\n"); Display(A); printf("\n矩陣B:\n"); Display(B);*/ printf("請(qǐng)選擇：\n1.矩陣相加：\n2.矩陣A轉(zhuǎn)置：\n3.矩陣B轉(zhuǎn)置：\n4.矩陣相乘：\n5.退出。\n\n"); while(1) {intl; scanf("%d",&l); switch(l) { case1: printf("矩陣相加的運(yùn)算結(jié)果：\n"); MatrixAdd(A,B,result); Display(result); printf("\n"); break; case2: printf("矩陣A轉(zhuǎn)置的運(yùn)算結(jié)果：\n"); MatrixTrams(A,result); Display(result); printf("\n"); break; case3: printf("矩陣B轉(zhuǎn)置的運(yùn)算結(jié)果：\n"); MatrixTrams(B,result); Display(result); printf("\n"); break; case4: printf("矩陣相乘的運(yùn)算結(jié)果：\n"); MatrixMultiply(A,B,result); Display(result); printf("\n"); break; case5: printf("退出。\n"); return; default: printf("輸入錯(cuò)誤！"); printf("\n"); } }}實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)三、查找、實(shí)驗(yàn)內(nèi)容掌握各種查找（順序、二分法、查找樹(shù)、哈希）方法及適用場(chǎng)合，并能在解決實(shí)際問(wèn)題時(shí)靈活應(yīng)用。本實(shí)驗(yàn)采用二分查找。二分查找又稱折半查找，它是一種效率較高的查找方法。折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好;其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。本程序具有找出數(shù)據(jù)位置和顯示查找次數(shù)兩個(gè)功能。㈡、實(shí)驗(yàn)代碼：#include<stdio.h>#defineMAX100voidmain(){ intr[MAX],i,k,low,high,mid,m,n; printf("\n\n建立遞增有序的查找順序表（以-1結(jié)束）：\n"); for(i=0;i<MAX;i++) { scanf("%d",&r[i]); if(r[i]==-1) { n=i; break; } } printf("\n請(qǐng)輸入要查找的數(shù)據(jù)：\n"); scanf("%d",&k); low=0;high=n-1;m=0; while(low<=high) { mid=(low+high)/2; m++; if(r[mid]>k) high=mid-1; else if(r[mid]<k) low=mid+1; else break; } if(low>high) { printf("沒(méi)有找到\n"); printf("共進(jìn)行%d次比較。\n",m); if(r[mid]<k) mid++; printf("可將這個(gè)數(shù)插入到第%d個(gè)數(shù)的后面。\n",mid); } else {printf("\n要找的數(shù)據(jù)=%d在第%d個(gè)數(shù)的位置上。\n",k,mid+1); printf("\n\n共進(jìn)行了%d次比較。\n",m); }}實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)四、樹(shù)、實(shí)驗(yàn)內(nèi)容：進(jìn)一步掌握樹(shù)的結(jié)構(gòu)及非線性特點(diǎn)，遞歸特點(diǎn)和動(dòng)態(tài)性；進(jìn)一步鞏固對(duì)指針的使用和二叉樹(shù)的三種遍歷方法、建立方法及用廣義表進(jìn)行輸入輸出。本程序?qū)⒌谝粋€(gè)元素作為樹(shù)根，其余元素若小于樹(shù)根則為左子樹(shù)，若大于樹(shù)根則為右子樹(shù)。本程序具有求左子樹(shù)、求右子樹(shù)、求深度、先序遍歷、中序遍歷（遞歸算法）、中序遍歷（非遞歸算法）、后序遍歷六個(gè)功能。㈡、實(shí)驗(yàn)代碼//描述：兩個(gè)指針指向左右孩子，算法見(jiàn)教材#include<stdio.h>#include<stdlib.h>#defineMAX50typedefstructbtnode{ intData; structbtnode*Llink; structbtnode*Rlink;}btnode,*btreetype;btreetypeCreatTree(intn)//傳入數(shù)據(jù)數(shù)量，返回根結(jié)點(diǎn)指針{ inti; btreetyperoot=NULL; for(i=0;i<n;i++) { btreetypenewNode,currentNode,parentNode; newNode=(btreetype)malloc(sizeof(btnode)); scanf("%d",&newNode->Data); newNode->Llink=NULL; newNode->Rlink=NULL; currentNode=root; if(currentNode==NULL)root=newNode; else{ while(currentNode!=NULL) { parentNode=currentNode; if(newNode->Data<currentNode->Data) currentNode=currentNode->Llink; else currentNode=currentNode->Rlink; } if(newNode->Data<parentNode->Data) parentNode->Llink=newNode; else parentNode->Rlink=newNode; } } returnroot;}voidOutputTree(btreetype&root){ btreetypep; p=root->Llink; printf("建立的二叉樹(shù)的左子樹(shù)為：\n"); while(p!=NULL) { printf("%-8d",p->Data); p=p->Llink; } p=root->Rlink; printf("\n建立的二叉樹(shù)的右子樹(shù)為：\n"); while(p!=NULL) { printf("%-8d",p->Data); p=p->Rlink; }}intdepth(btreetyperoot){ btreetypep; p=root; intdep1; intdep2; if(root==NULL)return0; else { dep1=depth(p->Llink); dep2=depth(p->Rlink); if(dep1>dep2)return(dep1+1); elsereturn(dep2+1); }}voidPreOrder(btreetype&root)//先序遍歷（遞歸）{ btreetypep; p=root; if(p!=NULL) { printf("%-5d",p->Data); PreOrder(p->Llink); PreOrder(p->Rlink); }}voidInOrder(btreetype&root)//中序遍歷（遞歸）{ btreetypep; p=root; if(p!=NULL) { InOrder(p->Llink); printf("%-5d",p->Data); InOrder(p->Rlink); }}voidInOrder_Norecuision(btreetype&root){ btreetypestack[MAX]; btreetypep; inttop=0; p=root; do { while(p!=NULL) { top++; stack[top]=p; p=p->Llink; } if(top>0) { p=stack[top]; top--; printf("%-5d",p->Data); p=p->Rlink; } }while(p!=NULL||top!=0);}voidPostOrder(btreetype&root){ btreetypep; p=root; if(p!=NULL) { PostOrder(p->Llink); PostOrder(p->Rlink); printf("%-5d",p->Data); }}voidmain(){ btreetypebtree; intcount; printf("請(qǐng)輸入元素個(gè)數(shù)：\n"); scanf("%d",&count); printf("請(qǐng)輸入數(shù)據(jù)：\n"); btree=CreatTree(count); OutputTree(btree); printf("\n建立的二叉樹(shù)的深度為:%d\n",depth(btree)); printf("\n先序遍歷：\n"); PreOrder(btree); printf("\n中序遍歷（遞歸算法）：\n"); InOrder(btree); printf("\n中序遍歷（非遞歸算法）：\n"); InOrder_Norecuision(btree); printf("\n后序遍歷：\n"); PostOrder(btree); printf("\n");}實(shí)驗(yàn)結(jié)果：#include<stdio.h>#include<string.h>#definemaxspace100#definekeylen7#defineradix_n10#defineradix_c26typedefcharkeytype;typedefstruct{charstart[6];charend[10];charsche[10];chartime1[5];chartime2[5];charmodel[4];intprice;}infotype;typedefstruct{keytypekeys[keylen];infotypeothers;intnext;}slnode;typedefstruct{slnodesl[maxspace];intkeynum;intlength;}sllist;typedefintarrtype_n[radix_n];typedefintarrtype_c[radix_c];voiddistribute(slnode*sl,inti,arrtype_nf,arrtype_ne){intj,p;for(j=0;j<radix_n;j++){f[j]=e[j]=0;}for(p=sl[0].next;p;p=sl[p].next){j=sl[p].keys[i]%48;if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}voidcollect(slnode*sl,inti,arrtype_nf,arrtype_ne){intj,t;for(j=0;!f[j];j++);sl[0].next=f[j];t=e[j];while(j<radix_n-1){for(j=j+1;j<radix_n-1&&!f[j];j++);if(f[j]){sl[t].next=f[j];t=e[j];}}sl[t].next=0;}voiddistribute_c(slnode*sl,inti,arrtype_cf,arrtype_ce){intj,p;for(j=0;j<radix_c;j++){f[j]=e[j]=0;}for(p=sl[0].next;p;p=sl[p].next){j=sl[p].keys[i]%65;if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}voidcollect_c(slnode*sl,inti,arrtype_cf,arrtype_ce){intj,t;for(j=0;!f[j];j++);sl[0].next=f[j];t=e[j];while(j<radix_c-1){for(j=j+1;j<radix_c-1&&!f[j];j++)if(f[j]){sl[t].next=f[j];t=e[j];}}sl[t].next=0;}voidradixsort(sllist&l)//鏈?zhǔn)絳inti;arrtype_nfn,en;arrtype_cfc,ec;for(i=0;i<l.length;i++)l.sl[i].next=i+1;l.sl[l.length].next=0;for(i=l.keynum-1;i>=2;i--){distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);}for(i=1;i>=0;i--){distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);}}voidarrange(sllist&l)//重新整理{intp,q,i;slnodetemp;p=l.sl[0].next;for(i=1;i<l.length;i++){while(p<i)p=l.sl[p].next;q=l.sl[p].next;if(p!=i){temp=l.sl[p];l.sl[p]=l.sl[i];l.sl[i]=temp;l.sl[i].next=p;}p=q;}}intbinsearch(sllistl,keytypekey[]){intlow,high,mid;low=1;high=l.length;while(low<=high){mid=(low+high)/2;if(strcmp(key,l.sl[mid].keys)==0)returnmid;elseif(strcmp(key,l.sl[mid].keys)<0)high=mid-1;elselow=mid+1;}return0;}voidseqsearch(sllistl,keytypekey[],inti){intj,k,m=0;printf("*************************************************************\n");printf("*航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)*\n");for(j=1;j<=l.length;j++){switch(i){case2:k=strcmp(key,l.sl[j].others.start);break;case3:k=strcmp(key,l.sl[j].others.end);break;case4:k=strcmp(key,l.sl[j].others.time1);break;case5:k=strcmp(key,l.sl[j].others.time2);break;}if(k==0){m=1;printf("*%-8s,%-6s,%-6s,%-11s,%-9s,%-7s,%-5s,%4d*\n",l.sl[j].keys,l.sl[j].others.start,l.sl[j].others.end,l.sl[j].others.sche,l.sl[j].others.time1,l.sl[j].others.time2,l.sl[j].others.model,l.sl[j].others.price);}}if(m==0)printf("*無(wú)此航班信息，可能是輸入錯(cuò)誤！*\n");printf("*************************************************************\n");}voidsearchcon(sllistl){keytypekey[keylen];inti=1,k;while(i>=1&&i<=5){printf("\n********************\n");printf("*航班信息查詢系統(tǒng)*\n");printf("********************\n");printf("*1.航班號(hào)*\n");printf("*2.起點(diǎn)站*\n");printf("*3.終點(diǎn)站*\n");printf("*4.起飛時(shí)間*\n");printf("*5.到達(dá)時(shí)間*\n");printf("*0.退出系統(tǒng)*\n");printf("********************\n");printf("請(qǐng)選擇(0-5):");scanf("%d",&i);printf("\n");switch(i){cas