級本數(shù)據(jù)結構實驗教案

數(shù)據(jù)結構與算法實驗教案授課教師：祁文青適用專業(yè)：計算機科學與技術使用班級：11計科2班、11計科（數(shù)媒）授課時間：2012年秋季授課學時：16學時使用教材：《數(shù)據(jù)結構》嚴蔚敏主編實驗指導書：數(shù)據(jù)結構與算法實驗指導書，計算機學院編，2012年版湖北理工學院計算機學院

實驗安排表周次日期實驗課題學時實驗報告次數(shù)9實驗一線性表的實驗2學時10實驗一線性表的實驗2學時111實驗二棧、隊列的實現(xiàn)及應用2學時112實驗三二叉樹的操作及應用2學時13實驗三二叉樹的操作及應用2學時114實驗四圖的操作及應用2學時115實驗五查找與排序2學時16實驗五查找與排序2學時1

實驗一線性表的實驗一、實驗目的及要求1、掌握在TC環(huán)境下調試順序表的基本方法2、掌握順序表的基本操作，插入、刪除、查找、以及有序順序表的合并等算法的實現(xiàn)。3、掌握用在TC環(huán)境下上機調試單鏈表的基本方法4、掌握單鏈表的插入、刪除、查找、求表長以及有序單鏈表的合并算法的實現(xiàn)5、進一步掌握循環(huán)單鏈表的插入、刪除、查找算法的實現(xiàn)二、實驗學時4學時三、實驗任務生成一個順序表并動態(tài)地刪除任意元素和在任意位置插入元素。將兩個有序表合并成一個有序表。3、在帶頭結點的單鏈表h中第i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素。4、將兩個有序單鏈表合并成一個有序單鏈表。四、實驗重點、難點在順序表中移動元素。在順序表中找到正確的插入位置。在單鏈表中尋找到第i-1個結點并用指針p指示。比較兩個單鏈表的節(jié)點數(shù)據(jù)大小。五、操作要點(一)順序表基本操作的實現(xiàn)[問題描述]當我們要在順序表的第i個位置上插入一個元素時，必須先將順序表中第i個元素之后的所有元素依次后移一個位置，以便騰空一個位置，再把新元素插入到該位置。若是欲刪除第i個元素時，也必須把第i個元素之后的所有元素前移一個位置。[基本要求]要求生成順序表時，可以鍵盤上讀取元素，用順序存儲結構實現(xiàn)存儲。[實現(xiàn)提示]要實現(xiàn)基本操作，可用實現(xiàn)的基本操作，也可設計簡單的算法實現(xiàn)。[程序實現(xiàn)]#include<stdio.h>#include<conio.h>typedefintDataType;#definemaxnum20typedefstruct{intdata[maxnum];intlength;}SeqList;/*插入函數(shù)*/intinsert(SeqList*L,inti,DataTypex)/*將新結點x插入到順序表L第i個位置*/{intj;if(i<0||i>(*L).length+1){printf("\ni值不合法!");return0;}if((*L).length>=maxnum-1){printf("\n表滿不能插入!");return0;}for(j=(*L).length;j>=i;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i]=x;(*L).length++;return1;}/*刪除函數(shù)*/intdelete(SeqList*L,inti)/*從順序L中刪除第i個結點*/{intj;if(i<0||i>(*L).length){printf("\n刪除位置錯誤!");return0;}for(j=i+1;j<=(*L).length;j++)(*L).data[j-1]=(*L).data[j];(*L).length--;return1;}/*生成順序表*/voidcreatlist(SeqList*L){intn,i,j;printf("請輸入順序表L的數(shù)據(jù)個數(shù)：\n");scanf("%d",&n);for(i=0;i<n;i++){printf("data[%d]=",i);scanf("%d",&((*L).data[i]));}(*L).length=n-1;printf("\n");}/*creatlist*//*輸出順序表L*/printout(SeqList*L){inti;for(i=0;i<=(*L).length;i++){printf("data[%d]=",i);printf("%d",(*L).data[i]);}/*printout*/printf("\n");}main(){SeqList*L;charcmd;inti,t,x;clrscr();creatlist(L);do{printf("\ni,I-----插入\n");printf("d,D-----刪除\n");printf("q,Q-----退出\n");do{cmd=getchar();}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));switch(cmd){case'i':case'I': printf("\nPleaseinputtheDATA:"); scanf("%d",&x); printf("\nWhere?"); scanf("%d",&i); insert(L,i,x); printout(L); break;case'd':case'D': printf("\nWheretoDelete?"); scanf("%d",&i); delete(L,i);printout(L);break;}}while((cmd!='q')&&(cmd!='Q'));}（二）有序順序表的合并[問題描述]已知順序表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb表中的數(shù)據(jù)元素，合并成為一個新的順序表lc[基本要求]lc中的數(shù)據(jù)元素仍按非遞減有序排列，并且不破壞la和lb表[程序實現(xiàn)]#include<stdio.h>#definemaxnum20typedefintDataType;typedefstruct{DataTypedata[maxnum];intlength;}SeqList;intMergeQL(SeqListla,SeqListlb,SeqList*lc){inti,j,k;if(la.length+1+lb.length+1>maxnum){printf("\narrayoverflow!");return0;}i=j=k=0;while(i<=la.length&&j<=lb.length){if(la.data[i]<=lb.data[j])lc->data[k++]=la.data[i++];elselc->data[k++]=lb.data[j++];}/*處理剩余部分*/while(i<=la.length)lc->data[k++]=la.data[i++];while(j<=lb.length)lc->data[k++]=lb.data[j++];lc->length=k-1;return1;}main(){SeqListla={{3,4,7,12,15},4};SeqListlb={{2,5,7,15,18,19},5};SeqListlc;inti;if(MergeQL(la,lb,&lc)){printf("\n");for(i=0;i<=lc.length;i++)printf("%4d",lc.data[i]);}}（一）單鏈表基本操作的實現(xiàn)[問題描述]要在帶頭結點的單鏈表h中第i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素x，首先需要在單鏈表中尋找到第i-1個結點并用指針p指示，然后申請一個由指針s指示的結點空間，并置x為其數(shù)據(jù)域值，最后修改第i-1個結點，并使x結點的指針指向第i個結點，要在帶頭結點的單鏈表h中刪除第i個結點，首先要計數(shù)尋找到第i個結點并使指針p指向其前驅第i-1個結點，然后刪除第i個結點并釋放被刪除結點空間。[基本要求]用鏈式存儲結構實現(xiàn)存儲[實現(xiàn)提示]鏈式存儲結構不是隨機存儲結構，即不能直接取到單鏈表中某個結點，而要從單鏈表的頭結點開始一個一個地計數(shù)尋找。[程序實現(xiàn)]#include<stdio.h>#include<malloc.h>typedefcharDataType;typedefstructnode{DataTypedata;/*結點的數(shù)據(jù)域*/structnode*next;/*結點的指針域*/}ListNode;voidInit_List(ListNode**L){(*L)=(ListNode*)malloc(sizeof(ListNode));/*產(chǎn)生頭結點*/(*L)->next=NULL;}intList_Length(ListNode*L){intn=0;ListNode*p=L->next;while(p!=NULL){n++;p=p->next;}returnn;}ListNode*GetNode(ListNode*L,inti){intj;ListNode*p;p=L;j=0;/*從頭結點開始掃描*/while(p->next&&j!=i)/*順指針向后掃描,直到p->next為NULL或i=j為止*/{p=p->next;j++;}if(i==j)returnp;/*找到了第i個結點*/elsereturnNULL;/*當i<0或i>0時,找不到第i個結點*/}voidInsertList(ListNode*L,DataTypex,inti){ListNode*p,*s;p=GetNode(L,i-1);/*尋找第i-1個結點*/if(p==NULL)/*i<1或i>n+1時插入位置i有錯*/{printf("positionerror");return;}s=(ListNode*)malloc(sizeof(ListNode));s->data=x;s->next=p->next;p->next=s;}voidDeleteList(ListNode*L,inti){ListNode*p,*r;p=GetNode(L,i-1);/*找到第i-1個結點*/if(p==NULL||p->next==NULL)/*i<1或i>n時,刪除位置錯*/{printf("positionerror");return;}r=p->next;/*使r指向被刪除的結點a*/p->next=r->next;/*將ai從鏈上刪除*/free(r);}/*使用頭插法建立帶頭結點鏈表算法*/ListNode*CreatListF(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*生成頭結點*/ListNode*s;/*工作指針*/head->next=NULL;ch=getchar();/*讀入第1個字符*/while(ch!='\n'){s=(ListNode*)malloc(sizeof(ListNode));/*生成新結點*/s->data=ch;/*將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)域中*/s->next=head->next;head->next=s;ch=getchar();/*讀入下一字符*/}returnhead;}/*使用尾插法建立帶頭結點鏈表算法*/ListNode*CreatListR1(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*生成頭結點*/ListNode*s,*r;/*工作指針*/r=head;/*尾指針初值也指向頭結點*/while((ch=getchar())!='\n'){s=(ListNode*)malloc(sizeof(ListNode));s->data=ch;r->next=s;r=s;}r->next=NULL;/*終端結點的指針域置空,或空表的頭結點指針域置空*/returnhead;}/*復制鏈表A中的內容到表B中*/voidcopy(ListNode*a,ListNode*b){ListNode*pa=a->next;ListNode*u;ListNode*rb=b;while(pa!=NULL){u=(ListNode*)malloc(sizeof(ListNode));u->data=pa->data;rb->next=u;rb=u;pa=pa->next; }rb->next=NULL;}/*輸出帶頭結點的單鏈表*/voidDisplaySL(ListNode*la,char*comment){ListNode*p;p=la->next;if(p)printf("\n%s\n",comment);while(p) { printf("%4c",p->data); p=p->next; }printf("\n");}/*主函數(shù)*/main(){ListNode*la,*lb,*lc,*p;intn,x,i;printf("\n用頭插法建立鏈表la，請輸入節(jié)點內容:");la=CreatListF();DisplaySL(la,"新生成鏈la節(jié)點內容:");printf("\n鏈表la的長度:%2d",List_Length(la));printf("\n請輸入要插入的元素:");scanf("%c",&x);printf("\n請輸入要插入的位置：");scanf("%d",&i);InsertList(la,x,i);DisplaySL(la,"插入后鏈la節(jié)點內容");printf("\n請輸入要刪除元素的位置：");scanf("%d",&i);DeleteList(la,i);DisplaySL(la,"刪除后鏈la節(jié)點內容");printf("\n用尾插法建立鏈表lb，請輸入節(jié)點內容:");fflush(stdin);lb=CreatListR1();DisplaySL(lb,"新生成鏈lb節(jié)點內容:");Init_List(&lc);copy(la,lc);DisplaySL(lc,"復制生成的鏈lc節(jié)點內容:");}（二）有序單鏈表的合并[問題描述]已知單鏈表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb中的數(shù)據(jù)元素,合并為一個新的單鏈表lc,lc中的數(shù)據(jù)元素仍按非遞減有序排列。[基本要求]不破壞la表和lb表的結構。[程序實現(xiàn)]#include<stdio.h>#include<alloc.h>#defineNULL0typedefintDataType;typedefstructSLNode{DataTypedata;structSLNode*next;}slnodetype;intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc);intCreateSL(slnodetype*la,intn);voidDisplaySL(slnodetype*la,char*comment);main(){slnodetype*la,*lb,*lc,*p;intn,m;la=(slnodetype*)malloc(sizeof(slnodetype));la->next=NULL;lb=(slnodetype*)malloc(sizeof(slnodetype));lb->next=NULL;lc=(slnodetype*)malloc(sizeof(slnodetype));lc->next=NULL;printf("\n輸入鏈la節(jié)點數(shù):");scanf("%d",&n);printf("\n輸入鏈la節(jié)點內容:");CreateSL(la,n);DisplaySL(la,"鏈la節(jié)點內容:");printf("\n輸入鏈lb節(jié)點數(shù):");scanf("%d",&m);printf("\n輸入鏈lb節(jié)點內容:");CreateSL(lb,m);DisplaySL(lb,"鏈lb節(jié)點內容:");if(MergeSL(la,lb,&lc))DisplaySL(lc,"合成后的鏈lc:");getchar();}intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc){slnodetype*pa,*pb,*pc;lc=(slnodetype*)malloc(sizeof(slnodetype));pa=la->next;pb=lb->next;pc=*lc;while(pa&&pb){pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;pb=pb->next;}}while(pa)/*插入la鏈的剩余段*/{ pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pa->data;pa=pa->next;}/*插入lb鏈的剩余段*/while(pb){ pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pb->data;pb=pb->next;}/*生成單鏈表*/intCreateSL(slnodetype*la,intn){inti;slnodetype*p,*q;q=la;for(i=1;i<=n;i++){p=(slnodetype*)malloc(sizeof(slnodetype));scanf("%d",&p->data);q->next=p;q=p;}q->next=NULL;return1;}/*輸出單鏈表*/voidDisplaySL(slnodetype*la,char*comment){slnodetype*p;p=la->next;if(p)printf("\n%s\n",comment);while(p){printf("\n%3d",p->data);p=p->next;}printf("\n");}

（一）約瑟夫環(huán)問題[問題描述]設有N個人圍坐一圈，現(xiàn)從某個人開始報數(shù)，數(shù)到M的人出列，接著從出列的下一個人開始重新報數(shù)，數(shù)到M的人以出列，如此下去，直到所有人都出列為此。試設計確定他們的出列次序序列的程序。[基本要求]選擇單向循環(huán)鏈表作為存儲結構模擬整個過程，并依次輸出列的各人的編號。[實現(xiàn)提示]程序運行之后，首先要求用戶指定初始報數(shù)的下限值，可以n<=30,此題循環(huán)鏈表可不設頭節(jié)點，而且必須注意空表和非空表的界限。如n=8,m=4時，若從第一個人，設每個人的編號依次為1，2，3，…開始報數(shù)，則得到的出列次序為4，8，5，2，1，3，7，6，如下圖所示，內層數(shù)字表示人的編號，每個編號外層的數(shù)字代表人出列的序號。[程序實現(xiàn)]#include<stdio.h>#include<malloc.h>typedefstructnode{intnum;structnode*next;}linklist;linklist*creat(head,n)/*使n個人圍成一圈，并給每個人標識號數(shù)*/linklist*head;intn;{linklist*s,*p;inti;s=(linklist*)malloc(sizeof(linklist));head=s;s->num=1;p=s;for(i=2;i<=n;i++){s=(linklist*)malloc(sizeof(linklist));s->num=i;p->next=s;p=s;}p->next=head; return(head);}/*creat*/linklist*select(linklist*head,intm){linklist*p,*q;inti,t;p=head;t=1;q=p;/*q為p的前趨指針*/p=p->next;do{t=t+1;/*報一次數(shù)*/if(t%m==0) {printf("%4d",p->num);q->next=p->next;free(p); p=q->next; }else{q=p; p=p->next; }}while(q!=p);head=p;printf("%4d",p->num);return(head);}/*select*/main(){intn,m;linklist*head;printf("\ninputthetotalnumber:n=");scanf("%d",&n);printf("\ninputthenumbertocall:m=");scanf("%d",&m);head=creat(head,n);head=select(head,m);printf("\nthelastoneis:%d",head->num);}/*main*/六、注意事項刪除元素或插入元素表的長度要變化。在合并表中當某一個表到表尾了就不用比較了，直接將另一個表的元素復制到總表去即可。3、在第i個節(jié)點前刪除或插入節(jié)點需要用指針來表示第i-1個節(jié)點。4、在合并鏈表時需要設置多個指針變量。5、如果不是要刪除的節(jié)點則指針后移，否則刪除該節(jié)點。七、思考題1、編程實現(xiàn)兩個循環(huán)單鏈表的合并。

實驗二棧、隊列的實現(xiàn)及應用一、實驗目的及要求1、掌握棧和隊列的順序存儲結構和鏈式存儲結構，以便在實際背景下靈活運用。2、掌握棧和隊列的特點，即先進后出與先進先出的原則。3、掌握棧和隊列的基本操作實現(xiàn)方法。二、實驗學時2學時三、實驗任務實現(xiàn)棧的順序存儲利用棧實現(xiàn)數(shù)制轉換四、實驗重點、難點進棧、出棧棧頂指針都要改變。數(shù)制轉換結束的判斷條件。五、操作要點（一）實現(xiàn)棧的順序存儲#defineMAXSIZE100typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==MAXSIZE-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n"); return0; }else{s->data[s->top]=x;s->top++;}}voidDisplay(SeqStack*s){if(s->top==0)printf("thestackisempty!\n");else{while(s->top!=0){printf("%d->",s->data[s->top]); s->top=s->top-1;}}}ElemTypePop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[--s->top];}ElemTypeStackTop(SeqStack*s){inti;if(StackEmpty(s))return0;else{i=s->top-1;returns->data[i];}/*返回棧頂元素的值，但不改變棧頂指針*/}main(SeqStack*p){intn,i,k,h,x1,x2,select;printf("createaemptystack!\n");InitStack(p);printf("inputastacklength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("inputastackvalue:\n");scanf("%d",&k);Push(p,k);}printf("select1:Display()\n");printf("select2:Push()\n");printf("select3:Pop()\n");printf("select4:StackTop()\n");printf("inputayourselect(1-4):\n");scanf("%d",&select);switch(select){case1:{ display(p); break;}case2:{ printf("inputapushavalue:\n"); scanf("%d",&h); Push(p,h); display(p); break;}case3:{ x1=Pop(p); printf("x1->%d\n",x1); display(p); break; }case4:{ x2=StackTop(p); printf("x2->%d",x2); break;}}}（二）利用棧實現(xiàn)數(shù)制轉換#defineMAXSIZE100typedefintElemType；/*將順序棧的元素定義為整型*/typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==m-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n"); return0; }else{s->data[s->top]=x;s->top++;}}ElemTypePop(SeqStack*s){ElemTypey;if(StackEmpty(s)){printf("thestackisempty!\n"); return0;}else{y=s->data[s->top]; s->top=s->top-1; returny;}}ElemTypeStackTop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[s->top];}voidDec_to_Ocx(intN)/*n是非負的十進制整數(shù)，輸出等值的八進制數(shù)*/{SeqStack*S；/*定義一個順序棧*/ElemTypex；Init_SeqStack(S)；/*初始化棧*/if(N<0){printf("\nError,Thenumbermustbeover0。")；return；}if(!N)Push(S,0)；while(N)/*自右向左產(chǎn)生八進制的各位數(shù)字，并將其進棧*/

{Push(S，N%8)；/*余數(shù)入棧*/N=N/8；/*商作為被除數(shù)*/}printf("Number%dconvertedtoOCT:",N);while(StackEmpty(S))/*棧非空時退棧輸出*/

{x=Pop(S)；printf(“%d”,x)；}printf("\n");}main(){intn;printf("InputanumbertoconverttoOCT:\n");scanf("%d",&n);Dec_to_Ocx(n);}六、注意事項1、進棧、出棧棧頂指針都要改變。2、數(shù)制轉換余數(shù)入棧后商作為被除數(shù)。七、思考題1、實現(xiàn)循環(huán)隊列的順序存儲

實驗三二叉樹的操作及應用一、實驗目的及要求1、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結構特性，以及各種存儲結構的特點和適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。二、實驗學時4學時三、實驗任務以二叉鏈表作存儲結構，編寫前序、中序、后序及層次順序遍歷二叉樹的算法。2、以二叉鏈表作存儲結構，編寫計算二叉樹深度、所有結點總數(shù)、葉子結點數(shù)、雙孩子結點個數(shù)、單孩子結點個數(shù)的算法四、實驗重點、難點1、前序、中序、后序及層次順序遍歷二叉樹的算法。2、計算二叉樹深度、所有結點總數(shù)、葉子結點數(shù)、雙孩子結點個數(shù)、單孩子結點個數(shù)的算法。五、操作要點（一）以二叉鏈表作存儲結構，試編寫前序、中序、后序及層次順序遍歷二叉樹的算法。#defineM10typedefintDataType;/*元素的數(shù)據(jù)類型*/typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BitTNode,*BiTree;intfront=0,rear=0;BitTNode*que[10];BitTNode*creat(){BitTNode*t;DataTypex;scanf("%d",&x);if(x==0)t=NULL;else{t=(BitTNode*)malloc(sizeof(BitTNode));t->data=x;t->lchild=creat();t->rchild=creat();}return(t);}/*creat*//*前序遍歷二叉樹t*/voidpreorder(BiTreet){if(t!=NULL){printf("%4d",t->data);preorder(t->lchild);preorder(t->rchild);}}/*中序遍歷二叉樹t*/voidinorder(BiTreet){if(t!=NULL){inorder(t->lchild);printf("%4d",t->data);inorder(t->rchild);}}/*后序遍歷二叉樹t*/voidpostorder(BiTreet){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%4d",t->data);}}voidenqueue(BitTNode*t){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=t;}}/*enqueue*/BitTNode*delqueue(){if(front==rear)returnNULL;{front=(front+1)%M;return(que[front]);}}/*delqueue*//*按層次遍歷二叉樹t*/voidlevorder(BiTreet){BitTNode*p;if(t!=NULL){enqueue(t);while(front!=rear){p=delqueue();printf("%4d",p->data);if(p->lchild!=NULL)enqueue(p->lchild);if(p->rchild!=NULL)enqueue(p->rchild);}}}/*levorder*/main(){BitTNode*root;root=creat();printf("\n按先序遍歷次序生成的二叉樹");printf("\n前序遍歷二叉樹");preorder(root);printf("\n中序遍歷二叉樹");inorder(root);printf("\n后序遍歷二叉樹");postorder(root);printf("\n層次順序遍歷二叉樹");levorder(root);}（二）以二叉鏈表作存儲結構，試編寫計算二叉樹深度、所有結點總數(shù)、葉子結點數(shù)、雙孩子結點個數(shù)、單孩子結點個數(shù)的算法#include<stdio.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;structnode*left,*right;}BTree;BTree*createbt(){ BTree*q; structnode1*s[30]; intj,i,x; printf("建立二叉樹，輸入結點對應的編號和值,編號和值之間用逗號隔開\n\n"); printf("i,x="); scanf("%d,%c",&i,&x); while(i!=0&&x!='$') {q=(BTree*)malloc(sizeof(BTree));/*建立一個新結點q*/ q->data=x;q->left=NULL;q->right=NULL; s[i]=q;/*q新結點地址存入s指針數(shù)組中*/ if(i!=1)/*i=1，對應的結點是根結點*/ {j=i/2;/*求雙親結點的編號j*/ if(i%2==0)s[j]->left=q;/*q結點編號為偶數(shù)則掛在雙親結點j的左邊*/ elses[j]->right=q;/*q結點編號為奇數(shù)則掛在雙親結點j的右邊*/} printf("i,x="); scanf("%d,%c",&i,&x);} returns[1];/*返回根結點地址*/}voidpreorder(BTree*BT)/*前序遍歷二叉樹t*/{if(BT!=NULL){printf("%4c",BT->data);preorder(BT->left);preorder(BT->right);}}intBTreeDepth(BTree*BT){intleftdep,rightdep;if(BT==NULL) return(0);else{ leftdep=BTreeDepth(BT->left); rightdep=BTreeDepth(BT->right); if(leftdep>rightdep) return(leftdep+1); else return(rightdep+1);}}intnodecount(BTree*BT){if(BT==NULL) return(0);else return(nodecount(BT->left)+nodecount(BT->right)+1);}intleafcount(BTree*BT){if(BT==NULL) return(0);elseif(BT->left==NULL&&BT->right==NULL) return(1);else return(leafcount(BT->left)+leafcount(BT->right));}intnotleafcount(BTree*BT){if(BT==NULL) return(0);elseif(BT->left==NULL&&BT->right==NULL) return(0);else return(notleafcount(BT->left)+notleafcount(BT->right)+1);}intonesoncount(BTree*BT){if(BT==NULL) return(0);elseif((BT->left==NULL&&BT->right!=NULL)||(BT->left!=NULL&&BT->right==NULL)) return(onesoncount(BT->left)+onesoncount(BT->right)+1);else return(onesoncount(BT->left)+onesoncount(BT->right));}inttwosoncount(BTree*BT){if(BT==NULL) return(0);elseif(BT->left==NULL||BT->right==NULL) return(twosoncount(BT->left)+twosoncount(BT->right));elseif(BT->left!=NULL&&BT->right!=NULL) return(twosoncount(BT->left)+twosoncount(BT->right)+1);}main(){BTree*B;B=creatree();printf("\n按先序遍歷次序生成的二叉樹");preorder(B);printf("\n二叉樹深度:%d\n",BTreeDepth(B));printf("總結點個數(shù):%d\n",nodecount(B));printf("葉子結點個數(shù):%d\n",leafcount(B));printf("非葉子結點個數(shù):%d\n",notleafcount(B));printf("具有雙孩子結點個數(shù):%d\n",twosoncount(B));printf("具有單孩子結點個數(shù):%d\n",onesoncount(B));}六、注意事項遍歷的思想。七、思考題1、用非遍歷算法如何實現(xiàn)？

實驗四圖的操作及應用一、實驗目的及要求1、熟練掌握圖的鄰接矩陣和鄰接表的存儲方式；2、實現(xiàn)圖的一些基本運算，特別是深度遍歷和廣度遍歷；3、掌握以圖為基礎的一些常用算法，如最小生成樹、拓撲排序、最短路徑等。二、實驗學時2學時三、實驗任務1、定義鄰接矩陣存儲結構或鄰接表存儲結構。2、按照建立一個帶權有向圖的操作需要，編寫在鄰接矩陣或鄰接表存儲結構下，帶權有向圖基本操作的實現(xiàn)函數(shù)（如初始化圖、在圖中插入一個結點、在圖中插入一條邊、在圖中尋找序號為v的結點的第一個鄰接結點、在圖中尋找序號為v1結點的鄰接結點v2的下一個鄰接結點、圖的深度優(yōu)先遍歷、圖的廣度優(yōu)先遍歷等）。3、設計一個測試主函數(shù)，首先創(chuàng)建一個圖（有n個結點和e條邊），然后打印圖的n個結點信息和e條邊信息，最后分別打印出圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結點信息序列。四、實驗重點、難點1、圖的抽象數(shù)據(jù)結構的創(chuàng)建。2、圖的遍歷算法。五、操作要點1、抽象數(shù)據(jù)結構typedefintstatus;typedefstructArcNode{intadjvex;structArcNode*nextarc;ArctexTypeinfo;}ArcNode;typedefcharVertexType[10];statusVisited[MAC_VERTEX_NUM];typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAC_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}Graph;2、算法基本操作的說明及分析(1)以鄰接表的形式建立圖的算法voidCreateMGraph(Mgraph*G){inti,j,k;printf("Enterthenumberofverticesandedges：：n");scanf("%d%d",&G->n,&G->e);getchar();printf("Enter%dverticesn",G->n);for(i=0;i<G->n;i++)G->vexs[i]=getchar();for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("Enterthe%dinthematrixelements:n",2*(G->e));for(k=0;k<2*(G->e);k++){scanf("%d%d",&i,&j);G->edges[i][j]=1;}}(2)廣度優(yōu)先遍歷算法：voidBFS(MgraphG,inti){intu,j;LinkQueueQ;InitQueue(&Q);printf("%c",G.vexs[i]);visited2[i]=1;EnQueue(&Q,i);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G.n;j++)if(G.edges[i][j]==1&&!visited2[j]){printf("%c",G.vexs[j]);visited2[j]=1;EnQueue(&Q,j);}}}(3)深度優(yōu)先遍歷算法實現(xiàn)。voidDFSM(Mgraph*G,inti){intj;printf("%c",G->vexs[i]);visited1[i]=1;for(j=0;j<G->n;j++){if(G->edges[i][j]==1&&!visited1[j])DFSM(G,j);}}(4)總的算法描述的程序代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>intvisited1[20]={0},visited2[20]={0};typedefstruct{charvexs[20];intedges[20][20];intn,e;}Mgraph;typedefstructQNode{intdata;structQNode*next;intQueusize;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*Q){Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));Q->front->next=NULL;}voidEnQueue(LinkQueue*Q,inte){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}intDeQueue(LinkQueue*Q){inte;QueuePtrp;p=Q->front->next;e=p->data;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);return(e);}intQueueEmpty(LinkQueue*Q){if(Q->front==Q->rear)return1;elsereturn0;}voidCreateMGraph(Mgraph*G){inti,j,k;printf("Enterthenumberofverticesandedges：：n");scanf("%d%d",&G->n,&G->e);getchar();printf("Enter%dverticesn",G->n);for(i=0;i<G->n;i++)G->vexs[i]=getchar();for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("Enterthe%dinthematrixelements:n",2*(G->e));for(k=0;k<2*(G->e);k++){scanf("%d%d",&i,&j);G->edges[i][j]=1;}}voidBFS(MgraphG,inti){intu,j;LinkQueueQ;InitQueue(&Q);printf("%c",G.vexs[i]);visited2[i]=1;EnQueue(&Q,i);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G.n;j++)if(G.edges[i][j]==1&&!visited2[j]){printf("%c",G.vexs[j]);visited2[j]=1;EnQueue(&Q,j);}}}voidDFSM(Mgraph*G,inti){intj;printf("%c",G->vexs[i]);visited1[i]=1;for(j=0;j<G->n;j++){if(G->edges[i][j]==1&&!visited1[j])DFSM(G,j);}}intmain(void){MgraphG;clrscr();CreateMGraph(&G);printf("BFS:n");BFS(G,0);printf("n");printf("DFS:n");DFSM(&G,0);}實驗五查找與排序一、實驗目的及要求1、掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法。2、熟練掌握順序表的查找方法和有序順序表的折半查找算法以及靜態(tài)查找樹的構造方法和查找算法。3、掌握二叉排序樹的生成、插入、刪除、輸出運算。4、掌握常用的排序方法，并能用高級語言實現(xiàn)排序算法。5、深刻理解排序的定義和各種排序方法的特點，并能加以靈活運用。6、了解各種方法的排序過程及依據(jù)的原則，并掌握各種排序方法的時間復雜度的分析方法。二、實驗學時4學時三、實驗任務1、順序表的順序查找有序順序表的二分查找的遞歸算法3、直接插入排序、簡單交換排序、快速排序、簡單選擇排序、堆排序、二路歸并中的"一趟歸并"算法。四、實驗重點、難點1、設置一個監(jiān)視哨。2、mid的變化。3、快速排序4、二路歸并中的"一趟歸并"算法五、操作要點（一）順序表的順序查找#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(KEYTYPEk,SSTABLE*st){/*順序表上查找元素*/intj;j=st->len;/*順序表元素個數(shù)*/st->r[0].key=k;/*st->r[0]單元作為監(jiān)視哨*/while(st->r[j].key!=k)j--;/*順序表從后向前查找*/returnj;/*j=0,找不到；j<>0找到*/}main(){SSTABLEa;inti,j,k;printf("請輸入順序表元素(整型量)，用空格分開，-99為結束標志：");j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;a.r[k].key=i;k++;scanf("%d",&i);}/*輸入順序表元素*/a.len=j;printf("\n順序表元素列表顯示：");for(i=1;i<=a.len;i++)printf("%d",a.r[i].key);printf("\n");printf("\n輸入待查元素關鍵字:");scanf("%d",&i);k=seq_search(i,&a);if(k==0)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,為第%d個元素\n"，k);}（二）有序順序表的二分查找的遞歸算法#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intsearch_bin(KEYTYPEk,intlow,inthigh){/*有序表上二分法查找,遞歸算法*/intmid;mid=-1;if(low<=high)/*low表示當前表中第1個元素所在下標*//*high表示當前表中最后一個元素所在下標*/{mid=(low+high)/2;/*mid表示當前表中中間一個元素所在下標*/if(a.r[mid].key<k)mid=search_bin(k,mid+1,high);/*二分法遞歸查找*/elseif(a.r[mid].key>k)mid=search_bin(k,low,high-1);}returnmid;/*mid=-1查找不成功；mid!=-1查找成功*/}main(){SSTABLEa;inti,j,k;printf("請輸入有序表元素，元素為整型量（從小到大輸入），用空格分開，-99為結束標志：");j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;a.r[k].key=i;k++;scanf("%d",&i);}/*輸入有序表元素*/a.len=j;printf("\n有序表元素列表顯示：");for(i=1;i<=a.len;i++)printf("%d",a.r[i]);printf("\n");printf("\n輸入待查元素關鍵字:");scanf("%d",&i);k=search_bin(i,1,a.len);if(k==-1)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,為第%d個元素\n"，k);}1、排序綜合練習#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100intcreateList(RECNODE*r){intj,k;printf("\n\n輸入待排序數(shù)據(jù)(整數(shù)，以空格隔開，0結束):");k=0;scanf("%d",&j);while(j!=0){k++;r[k].key=j;scanf("%d",&j);}returnk;}frontdisplayList(RECNODE*r,intn){inti;printf("\n排序前:");for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n\n");}reardisplayList(RECNODE*r,intn){inti;printf("\n\n排序后:");for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n\n");}voidinsertsort(RECNODE*r,intn){/*直接插入排序*/ inti,j; for(i=2;i<=n;i++) {r[0]=r[i];j=i-1;/*r[0]是監(jiān)視哨，j表示當前已排好序列的長度*/ while(r[0].key<r[j].key)/*確定插入位置*/ {r[j+1]=r[j];j--;} r[j+1]=r[0];/*元素插入*/ }}voidbublesort(RECNODE*r,intn){/*簡單交換排序:冒泡排序*/ inti,j; RECNODEtemp; for(i=1;i<n;i++) for(j=n-1;j>=i;j--) if(r[j+1].key<r[j].key) {temp=r[j+1];r[j+1]=r[j];r[j]=temp;}}intpartition(RECNODE*r,int*low,int*high){/*一趟快速排序,返回i,產(chǎn)生了兩個獨立的待排子序列*/ inti,j; RECNODE temp; i=*low;j=*high; temp=r[i];/*樞軸記錄保存在temp變量中*/ do{while((r[j].key>=temp.key)&&(i<j))j--;/*j指針記錄和樞軸記錄比較*/ if(i<j){r[i]=r[j];i++;} while((r[i].key<=temp.key)&&(i<j))i++;/*i指針記錄和樞軸記錄比較*/ if(i<j){r[j]=r[i];j--;}}while(i!=j); r[i]=temp;/*樞軸記錄的排序位置確定在i*/ returni;}voidquicksort(RECNODE*r,intstart,intend){/*快速排序*/ inti; if(start<end) {i=partition(r,&start,&end);/*一趟快速排序,返回i,產(chǎn)生了兩個獨立的待排子序列*/ quicksort(r,start,i-1);/*對兩個獨立的待排子序列分別遞歸調用快速排序算法*/ quicksort(r,i+1,end);}}voidselesort(RECNODE*r,intn){/*簡單選擇排序*/ inti,j,k; RECNODEtemp; for(i=1;i<n;i++) {k=i;/*k:最小關鍵字的初始位置*/ for(j=i+1;j<=n;j++) if(r[j].key<r[k].key) k=j;/*k:跟蹤記錄當前最小關鍵字的位置*/ if(k!=i)/*最小關鍵字元素和待排序列的第一個元素交換*/ {temp=r[i];r[i]=r[k];r[k]=temp;} }}voidsift(RECNODE*r,inti,intm){/*i是根結點編號,m是以i結點為根的子樹中最后一個結點的編號*/ intj; RECNODEtemp; temp=r[i]; j=2*i;/*j為i根結點的左孩子*/ while(j<=m) {if(j<m&&(r[j].key<r[j+1].key)) j++;/*當i結點有左右孩子時,j取關鍵字大的孩子結點編號*/ if(temp.key<r[j].key)/*按堆定義調整,并向下一層篩選調整*/ {r[i]=r[j];i=j;j=2*i;} elsebreak;/*篩選調整完成,跳出循環(huán)*/ } r[i]=temp;}voidheapsort(RECNODE*r,intn){/*堆排序:n為r表中記錄數(shù),從r[1]開始放起*/ inti; RECNODEtemp; for(i=n/2;i>=1;i--) sift(r,i,n);/*將無序序列建