第一篇：數(shù)據(jù)結(jié)構(gòu)實驗C語言版
南陽理工學(xué)院
數(shù)據(jù)結(jié)構(gòu)(C語言版)上機實驗指導(dǎo)書
軟件學(xué)院·軟件工程
目錄
實驗1 線性表應(yīng)用
實驗2 棧和隊列的應(yīng)用.......................................................................14 實驗3 線性表應(yīng)用...............................................................................27 實驗4 圖論及其應(yīng)用...........................................................................46
實驗5 查找
實驗6 排序...........................................................................................64
實驗1 線性表應(yīng)用
一、實驗?zāi)康?/p>
3，了解和掌握線性表順序存儲和鏈式存儲在計算機中的表示，基本操做在計算機中的實 2，能夠利用線性表結(jié)構(gòu)對實際問題進行分析建模，利用計算機求解。
1，能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。
二、實驗內(nèi)容及步驟
1、利用程序設(shè)計語言分別實現(xiàn)順序表和鏈表的抽象數(shù)據(jù)類型。
2、掌握程序分文件（頭文件和實現(xiàn)文件）書寫的方式。
3、分別用順序表和鏈表實現(xiàn)課本算法2.2：合并兩個非遞減有序序列，并對其時間性能做出分析。
三、實驗步驟與調(diào)試過程
以線性表來描述一元多項式，儲存結(jié)構(gòu)采用單鏈表，每個結(jié)點儲存的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù)高的結(jié)點列于指數(shù)低的結(jié)點之后，即線性表的元素按指數(shù)遞增有序排列。
四、實驗結(jié)果
五、疑難小結(jié)
當線性表的長度變化較大，難以估計其存儲規(guī)模，另外對線性表頻繁進行插入和刪除操作時，則采用鏈表作為存儲結(jié)構(gòu)可能會更好一些。在實際應(yīng)用中應(yīng)該考慮以下因素：(1)應(yīng)有利于運算的實現(xiàn)；(2)應(yīng)有利于數(shù)據(jù)的特性；(3)應(yīng)有利于軟件環(huán)境。
六、主要算法和程序清單 順序表的非遞減數(shù)列合并 #include
/*包含輸入輸出頭文件*/ #define ListSize 100 typedef int DataType;typedef struct { DataType list[ListSize];int length;}SeqList;
void InitList(SeqList *L)
/*將線性表初始化為空的線性表只需要把線性表的長度length置為0*/ { L->length=0;/*把線性表的長度置為0*/ } int ListEmpty(SeqList L)
/*判斷線性表是否為空，線性表為空返回1，否則返回0*/ {
if(L.length==0)
/*判斷線性表的長度是否為9*/
return 1;
/*當線性表為空時，返回1；否則返回0*/
else
return 0;} int GetElem(SeqList L,int i,DataType *e)
/*查找線性表中第i個元素。查找成功將該值返回給e，并返回1表示成功；否則返回-1表示失敗。*/ { if(i<1||i>L.length)
/*在查找第i個元素之前，判斷該序號是否合法*/
return-1;*e=L.list[i-1];/*將第i個元素的值賦值給e*/
return 1;} int LocateElem(SeqList L,DataType e)
/*查找線性表中元素值為e的元素，查找成功將對應(yīng)元素的序號返回，否則返回0表示失敗。*/ {
int i;for(i=0;i if(L.list[i]==e) return i+1; return 0;} int InsertList(SeqList *L,int i,DataType e) /*在順序表的第i個位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，順序表滿返回0*/ { int j;if(i<1||i>L->length+1) /*在插入元素前，判斷插入位置是否合法*/ { printf(“插入位置i不合法！n”); return-1;} else if(L->length>=ListSize)/*在插入元素前，判斷順序表是否已經(jīng)滿，不能插入元素*/ { printf(“順序表已滿，不能插入元素。n”); return 0;} else { for(j=L->length;j>=i;j--)/*將第i個位置以后的元素依次后移*/ L->list[j]=L->list[j-1]; L->list[i-1]=e;/*插入元素到第i個位置*/ L->length=L->length+1;/*將順序表長增1*/ return 1;} } int DeleteList(SeqList *L,int i,DataType *e){ int j; if(L->length<=0) { printf(“順序表已空不能進行刪除!n”); return 0; } else if(i<1||i>L->length) { printf(“刪除位置不合適!n”); return-1; } else { *e=L->list[i-1]; for(j=i;j<=L->length-1;j++) L->list[j-1]=L->list[j]; L->length=L->length-1; return 1; } } int ListLength(SeqList L){ return L.length;} void ClearList(SeqList *L){ L->length=0;} void MergeList(SeqList A,SeqList B,SeqList *C);*/ void main(){ int i,flag;DataType a[]={6,11,11,23};DataType b[]={2,10,12,12,21};DataType e; /*合并順序表A和B中元素的函數(shù)聲明 SeqList A,B,C; /*聲明順序表A，B和C*/ InitList(&A); /*初始化順序表A*/ InitList(&B); /*初始化順序表B*/ InitList(&C); /*初始化順序表C*/ for(i=1;i<=sizeof(a)/sizeof(a[0]);i++) /*將數(shù)組a中的元素插入到順序表A中*/ { if(InsertList(&A,i,a[i-1])==0) { printf(“位置不合法”); return; } } for(i=1;i<=sizeof(b)/sizeof(b[0]);i++) /*將數(shù)組b中元素插入到順序表B中*/ { if(InsertList(&B,i,b[i-1])==0) { printf(“位置不合法”); return; } } printf(“順序表A中的元素：n”);for(i=1;i<=A.length;i++)/*輸出順序表A中的每個元素*/ { flag=GetElem(A,i,&e);/*返回順序表A中的每個元素到e中*/ if(flag==1) printf(“%4d”,e);} printf(“n”);printf(“順序表B中的元素：n”);for(i=1;i<=B.length;i++)/*輸出順序表B中的每個元素*/ { flag=GetElem(B,i,&e);/*返回順序表B中的每個元素到e中*/ if(flag==1) printf(“%4d”,e); } printf(“n”);printf(“將在A中出現(xiàn)B的元素合并后C中的元素：n”);MergeList(A,B,&C); /*將在順序表A和B中的元素合并*/ for(i=1;i<=C.length;i++) /*顯示輸出合并后C中所有元素*/ { flag=GetElem(C,i,&e); if(flag==1) printf(“%4d”,e); } printf(“n”);getch(); } void MergeList(SeqList A,SeqList B,SeqList *C)/*合并順序表A和B的元素到C中，并保持元素非遞減排序*/ { int i,j,k;DataType e1,e2;i=1;j=1;k=1;while(i<=A.length&&j<=B.length){ GetElem(A,i,&e1); GetElem(B,j,&e2); if(e1<=e2) { InsertList(C,k,e1); i++; k++; } else { InsertList(C,k,e2); j++; k++; } } while(i<=A.length) 素*/ { GetElem(A,i,&e1); InsertList(C,k,e1); i++; k++;} while(j<=B.length) 素*/ { GetElem(B,j,&e2); InsertList(C,k,e2); j++; /*取出順序表A中的元素*/ /*取出順序表B中的元素*/ /*比較順序表A和順序表B中的元素*/ /*將較小的一個插入到C中*/ /*往后移動一個位置，準備比較下一個元素*/ /*將較小的一個插入到C中*/ /*往后移動一個位置，準備比較下一個元素*/ /*如果A中元素還有剩余，這時B中已經(jīng)沒有元/*將A中剩余元素插入到C中*/ /*如果B中元素還有剩余，這時A中已經(jīng)沒有元/*將B中剩余元素插入到C中*/ k++;} C->length=A.length+B.length;/*C的表長等于A和B的表長的和*/ } ? 鏈式表的非遞減數(shù)列合并 /*包含頭文件*/ #include #include DataType data; struct Node *next;}ListNode,*LinkList;void MergeList(LinkList A,LinkList B,LinkList *C);/*將單鏈表A和B的元素合并到C中的函數(shù)聲明*/ void InitList(LinkList *head)/*將單鏈表初始化為空。動態(tài)生成一個頭結(jié)點，并將頭結(jié)點的指 針域置為空。*/ { if((*head=(LinkList)malloc(sizeof(ListNode))) ==NULL)/*為頭結(jié)點分配一個存儲空間*/ exit(-1);(*head)->next=NULL; /*將單鏈表的頭結(jié)點指針域置為空*/ } int ListEmpty(LinkList head) /*判斷單鏈表是否為空，就是通過判斷頭結(jié)點的指針域是否為空 */ { if(head->next==NULL) /*判斷 單鏈表頭結(jié)點的指針域是否為空*/ return 1; /*當單鏈表為空時，返回1；否則返回0*/ else return 0;} ListNode *Get(LinkList head,int i) /*查找單鏈表中第i個結(jié)點。查找成功返回該結(jié)點的指針表示成 功；否則返回NULL表示失敗。*/ { ListNode *p;int j;if(ListEmpty(head))/*在查找第i個元素之前，判斷鏈表是否為空*/ return NULL;if(i<1) /*在查找第i個元 素之前，判斷該序號是否合法*/ return NULL;j=0;p=head;while(p->next!=NULL&&j p=p->next; j++;} if(j==i) return p;/*找到第i個結(jié)點，返回指針p*/ else return NULL;/*如果沒有找到第i個元 素，返回NULL*/ } ListNode *LocateElem(LinkList head,DataType e) /*查找線性表中元素值為e的元素，查找成功將對應(yīng)元素的結(jié)點 指針返回，否則返回NULL表示失敗。*/ { ListNode *p;p=head->next;/*指針p指向第一個結(jié)點*/ while(p){ if(p->data!=e)/*找到與e相等的元素，返 回該序號*/ p=p->next; else break;} return p;} int LocatePos(LinkList head,DataType e) /*查找線性表中元素值為e的元素，查找成功將對應(yīng)元素的序號 返回，否則返回0表示失敗。*/ { ListNode *p;int i; if(ListEmpty(head))/*在查找第i個元 素之前，判斷鏈表是否為空*/ return 0; p=head->next;/*指針p指向第一 個結(jié)點*/ i=1; while(p) { if(p->data==e)/*找到與e相等的 元素，返回該序號*/ return i; else { p=p->next; i++; } } if(!p) /*如果 沒有找到與e相等的元素，返回0，表示失敗*/ return 0;} int InsertList(LinkList head,int i,DataType e)/*在單鏈表中第i個位置插入一個結(jié)點，結(jié)點的元素值為e。插入 成功返回1，失敗返回0*/ { ListNode *p,*pre;/*定義指向第i個元素的前 驅(qū)結(jié)點指針pre，指針p指向新生成的結(jié)點*/ int j;pre=head; /*指針p指向頭結(jié) 點*/ j=0;while(pre->next!=NULL&&j pre=pre->next; j++;} if(!pre) /*如果沒找到，說明插入位置錯誤*/ { printf(“插入位置錯”); return 0;} /*新生成一個結(jié)點，并將e賦值給該結(jié)點的數(shù)據(jù)域*/ if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL) exit(-1);p->data=e;/*插入結(jié)點操作*/ p->next=pre->next;pre->next=p;return 1;} int DeleteList(LinkList head,int i,DataType *e)/*刪除單鏈表中的第i個位置的結(jié)點。刪除成功返回1，失敗返回 0*/ { ListNode *pre,*p;int j; pre=head; j=0; while(pre->next!=NULL&&pre->next->next! =NULL&&j { pre=pre->next; j++; } if(j!=i-1) /*如果沒找到要 刪除的結(jié)點位置，說明刪除位置錯誤*/ { printf(“刪除位置錯誤”); return 0;} /*指針p指向單鏈表中的第i個結(jié)點，并將該結(jié)點的數(shù)據(jù) 域值賦值給e*/ p=pre->next;*e=p->data;/*將前驅(qū)結(jié)點的指針域指向要刪除結(jié)點的下一個結(jié)點，也就是將p指向的結(jié)點與單鏈表斷開*/ pre->next=p->next; free(p); /*釋放p指向的結(jié) 點*/ return 1;} int ListLength(LinkList head){ ListNode *p; int count=0; p=head; while(p->next!=NULL) { p=p->next; count++; } return count;} void DestroyList(LinkList head){ ListNode *p,*q; p=head; while(p!=NULL){ q=p; p=p->next; free(q); } } void main(){ int i;DataType a[]={6,7,9,14,37,45,65,67};DataType b[]={3,7,11,34,45,89}; LinkList A,B,C; /*聲明單鏈表A和B*/ ListNode *p;InitList(&A); /*初始化單鏈表A*/ InitList(&B); /*初始化單鏈表B*/ for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)/*將數(shù)組a中元素插入到單鏈表A中*/ { if(InsertList(A,i,a[i-1])==0) { printf(“位置不合法”); return; } } for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)/*將數(shù)組b中元素插入單鏈表B中*/ { if(InsertList(B,i,b[i-1])==0) { printf(“位置不合法”); return; } } printf(“單鏈表A中的元素有%d個：n”,ListLength(A));for(i=1;i<=ListLength(A);i++)/*輸出單鏈表A中的每個元素*/ { p=Get(A,i); /*返回單鏈表A中的每個結(jié)點的指針*/ if(p) printf(“%4d”,p->data);/*輸出單鏈表A中的每個元素*/ } printf(“n”);printf(“單鏈表B中的元素有%d個：n”,ListLength(B));for(i=1;i<=ListLength(B);i++) { p=Get(B,i); /*返回單鏈表B中的每個每個結(jié)點的指針*/ if(p) printf(“%4d”,p->data);/*輸出單鏈表B中的每個元素*/ } printf(“n”);MergeList(A,B,&C); /*將單鏈表A和B中的元素合并到C中*/ printf(“將單鏈表A和B的元素合并到C中后，C中的元素有%d個：n”,ListLength(C));for(i=1;i<=ListLength(C);i++) { p=Get(C,i); /*返回單鏈表C中每個結(jié)點的指針*/ if(p) printf(“%4d”,p->data);/*顯示輸出C中所有元素*/ } printf(“n”);getch();} void MergeList(LinkList A,LinkList B,LinkList *C)/*單鏈表A和B中的元素非遞減排列，將單鏈表A和B中的元素合并到C中，C中的元素仍按照非遞減排列*/ { ListNode *pa,*pb,*pc;/*定義指向單鏈表A，B,C的指針*/ pa=A->next;pb=B->next;*C=A; /*將單鏈表A的頭結(jié)點作為C的頭結(jié)點*/(*C)->next=NULL;pc=*C;/*依次將鏈表A和B中較小的元素存入鏈表C中*/ while(pa&&pb) { if(pa->data<=pb->data) { pc->next=pa;/*如果A中的元素小于或等于B中的元素，將A中的元素的結(jié)點作為C的結(jié)點*/ pc=pa; pa=pa->next; } else { pc->next=pb;/*如果A中的元素大于B中的元素，將B中的元素的結(jié)點作為C的結(jié)點*/ pc=pb; pb=pb->next; } } pc->next=pa?pa:pb;/*將剩余的結(jié)點插入C中*/ free(B); /*釋放B的頭結(jié)點*/ } 實驗2 棧和隊列的應(yīng)用 一、實驗?zāi)康?/p> 1、掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 2、熟練掌握棧類型的兩種實現(xiàn)方法。 3、熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。 二、實驗內(nèi)容及步驟 1、用程序設(shè)計語言實現(xiàn)棧和隊列的抽象數(shù)據(jù)類型。 2、在第一題的基礎(chǔ)上完成以下選擇： 選擇一： 1)設(shè)計并實現(xiàn)括號匹配算法。 2)用隊列實現(xiàn)在屏幕上打印楊輝三角。選擇二： 分別用棧和隊列實現(xiàn)迷宮問題求解。選擇三： 分別用棧和隊列實現(xiàn)一個列車調(diào)度系統(tǒng)。 三、實驗步驟與調(diào)試過程 首先只只置操作數(shù)棧為空，表達式起始符“#”為運算符棧的棧底元素，依次讀入表達式中每個字符，直至整個表達式求值完畢。 四、實驗結(jié)果 五、疑難小結(jié) 對棧的順序存儲結(jié)構(gòu)用了更深刻的了解，同時也對程序設(shè)計能力有了提高，加深了對棧先進后出性質(zhì)的理解，對數(shù)組的應(yīng)用也十分熟練。 六、主要算法： ? 括號匹配算法。#include DataType data; struct node *next;}LStackNode,*LinkStack;void InitStack(LinkStack *top)/*將鏈棧初始化為空。動態(tài)生成頭結(jié)點，并將頭結(jié)點的指針域置為空。*/ { if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL)/*為頭結(jié)點分配一個存儲 空間*/ exit(-1);(*top)->next=NULL; /*將鏈棧的頭結(jié)點指針域置為空*/ } int StackEmpty(LinkStack top) /*判斷鏈棧是否為空，就是通過判斷頭結(jié)點的指針域是否為空*/ { if(top->next==NULL) /*判斷鏈棧頭結(jié)點的指針域是否為空*/ return 1; /*當鏈棧為空時，返回1；否則返回0*/ else return 0;} int PushStack(LinkStack top, DataType e)/*進棧操作就是要在鏈表的第一個結(jié)點前插入一個新結(jié)點，進棧成功返回1*/ { LStackNode *p;/*定義指向第i個元素的前驅(qū)結(jié)點指針pre，指針p指向新生成的結(jié)點*/ if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL){ printf(“內(nèi)存分配失敗!”); exit(-1);} p->data=e; /*指針p指向頭結(jié)點*/ p->next=top->next;top->next=p;return 1;} int PopStack(LinkStack top,DataType *e)/*刪除單鏈表中的第i個位置的結(jié)點。刪除成功返回1，失敗返回0*/ { LStackNode *p; p=top->next; if(!p) /*判斷鏈棧是否為空*/ { printf(“棧已空”); return 0; } top->next=p->next; /*將棧頂結(jié)點與鏈表斷開，即出棧*/ *e=p->data; /*將出棧元素賦值給e*/ free(p); /*釋放p指向的結(jié)點*/ return 1;} int StackLength(LinkStack top){ LStackNode *p; int count=0; p=top; while(p->next!=NULL) { p=p->next; count++; } return count;} void DestroyStack(LinkStack top){ LStackNode *p,*q; p=top; while(!p){ q=p; p=p->next; free(q); } } int GetTop(LinkStack top,DataType *e){ LStackNode *p; p=top->next; if(!p) /*判斷鏈棧是否為空*/ { printf(“棧已空”); return 0; } *e=p->data; /*將出棧元素賦值給e*/ return 1;} void main(){ LinkStack S;char *p;DataType e;DataType ch[60];InitStack(&S); /*初始化鏈棧*/ printf(“請輸入帶括號的表達式('{}','[]','()').n”);gets(ch);p=ch;while(*p) { switch(*p) { case '(': case '[': case '{': PushStack(S,*p++); break; case ')': case ']': case '}': if(StackEmpty(S)) { printf(“缺少左括號.n”); return; } else { GetTop(S,&e); if(Match(e,*p)) PopStack(S,&e); else { printf(“左右括號不配對.n”); return; } } default: p++; } } if(StackEmpty(S)) printf(“括號匹配.n”);else printf(“缺少右括號.n”);} int Match(DataType e,DataType ch){ if(e=='('&&ch==')') return 1;else if(e=='['&&ch==']') return 1;else if(e=='{'&&ch=='}') return 1;else return 0;} ? 用隊列實現(xiàn)在屏幕上打印楊輝三角 /*包含頭文件*/ #include /*定義鏈式隊列元素的類型為整數(shù)類型*/ #define MaxSize 100 void PrintArray(int a[],int n);void YangHuiTriangle(int N); typedef struct QNode { DataType data;struct QNode* next;}LQNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue; void InitQueue(LinkQueue *LQ) /*將帶頭結(jié)點的鏈式隊列初始化為空隊列需要把頭結(jié)點的指針域置為0*/ { LQ->front=(LQNode*)malloc(sizeof(LQNode));if(LQ->front==NULL)exit(-1); LQ->front->next=NULL;/*把頭結(jié)點的指針域置為為0*/ LQ->rear=LQ->front;} int QueueEmpty(LinkQueue LQ) /*判斷鏈式隊列是否為空，隊列為空返回1，否則返回0*/ { if(LQ.front->next==NULL)/*當鏈式隊列為空時，返回1，否則返回0*/ return 1; else return 0;} int EnterQueue(LinkQueue *LQ,DataType e)/*將元素e插入到鏈式隊列LQ中，插入成功返回1*/ { LQNode *s;s=(LQNode*)malloc(sizeof(LQNode));/*為將要入隊的元素申請一個結(jié)點的空間*/ if(!s)exit(-1); /*如果申請空間失敗，則退出并返回參數(shù)-1*/ s->data=e; /*將元素值賦值給結(jié)點的數(shù)據(jù)域*/ s->next=NULL; /*將結(jié)點的指針域置為空*/ LQ->rear->next=s; /*將原來隊列的隊尾指針指向p*/ LQ->rear=s; /*將隊尾指針指向p*/ return 1;} //int DeleteQueue(LinkQueue *LQ,DataType *e)///*刪除鏈式隊列中的隊頭元素，并將該元素賦值給e，刪除成功返回1，否則返回0*/ //{ // LQNode *s;//if(LQ->front==LQ->rear)/*在刪除元素之前，判斷鏈式隊列是否為空*/ // return 0;// else //{ // s=LQ->front->next; /*使指針p指向隊頭元素的指針*/ // *e=s->data; /*將要刪除的隊頭元素賦值給e*/ // LQ->front->next=s->next; /*使頭結(jié)點的指針指向指針p的下一個結(jié)點*/ // if(LQ->rear==s)LQ->rear=LQ->front;/*如果要刪除的結(jié)點是隊尾，則使隊尾指針指向隊頭指針*/ // free(s); /*釋放指針p指向的結(jié)點*/ // return 1;// } //} int GetHead(LinkQueue LQ,DataType *e)/*取鏈式隊列中的隊頭元素，并將該元素賦值給e，取元素成功返回1，否則返回0*/ { LQNode *s;if(LQ.front==LQ.rear)/*在取隊頭元素之前，判斷鏈式隊列是否為空*/ return 0;else { s=LQ.front->next;/*將指針p指向隊列的第一個元素即隊頭元素*/ *e=s->data; /*將隊頭元素賦值給e，取出隊頭元素*/ return 1;} } /*出隊操作。*/ int DeleteQueue(LinkQueue *Q,DataType *x){ /* 將隊列Q的隊頭元素出隊，并存放到x所指的存儲空間中 */ LQNode * p; if(Q->front==Q->rear) return(0);p=Q->front->next;Q->front->next=p->next;/* 隊頭元素p出隊 */ if(Q->front==NULL)/* 如果隊中只有一個元素p，則p出隊后成為空隊 */ Q->rear=Q->front; *x=p->data;free(p); /* 釋放存儲空間 */ return(1);} void YangHuiTriangle(int N)/*鏈式隊列實現(xiàn)打印楊輝三角*/ { int i,j,k,n;DataType e,t;int temp[MaxSize]; LinkQueue Q;k=0;InitQueue(&Q); EnterQueue(&Q,1); /*產(chǎn)生第中間n-2行的元素*/ for(n=2;n<=N;n++) 在臨時數(shù)組中*/ { k=0; EnterQueue(&Q,1); for(i=1;i<=n-2;i++) 并入隊列*/ { DeleteQueue(&Q,&t); temp[k++]=t; GetHead(Q,&e); t=t+e; EnterQueue(&Q,t); } DeleteQueue(&Q,&t); temp[k++]=t; PrintArray(temp,k,N); EnterQueue(&Q,1); } k=0; while(!QueueEmpty(Q)) { /*定義一個臨時數(shù)組，用于存放每一行的元素*/ /*初始化鏈隊列*/ /*第一行元素入隊*/ /*產(chǎn)生第i行元素并入隊，同時將第i-1行的元素保存/*第i行的第一個元素入隊*/ /*利用隊列中第i-1行元素產(chǎn)生第i行的中間i-2個元素/*將第i-1行的元素存入臨時數(shù)組*/ /*取隊頭元素*/ /*利用隊中第i-1行元素產(chǎn)生第i行元素*/ /*將第i-1行的最后一個元素存入臨時數(shù)組*/ /*第i行的最后一個元素入隊*/ /*將最后一行元素存入數(shù)組之前，要將下標k置為0*/ /*將最后一行元素存入臨時數(shù)組*/ DeleteQueue(&Q,&t); temp[k++]=t; if(QueueEmpty(Q)) PrintArray(temp,k,N);} } void main(){ int n;printf(“請輸入要打印的行數(shù)：n=:”);scanf(“%d”,&n); YangHuiTriangle(n);} void PrintArray(int a[],int n,int N)/*打印數(shù)組中的元素，使能夠呈正確的形式輸出*/ { int i;static count=0; /*記錄輸出的行*/ for(i=0;i /*打印空格*/ printf(“ ”);count++;for(i=0;i /*打印數(shù)組中的元素*/ printf(“%6d”,a[i]);printf(“n”);} ? 用棧實現(xiàn)迷宮問題求解 #include #define OVERFLOW-1 #define MAX 100 typedef struct { int x; int y; int d;}Data; typedef struct { int pos; Data data[MAX];}SNode,*Stack; Stack InitStack() { Stack pStack; pStack=(Stack)malloc(sizeof(SNode)); if(!pStack) exit(OVERFLOW); pStack->pos=-1; return pStack;} int IsEmpty(Stack pstack){ return pstack->pos==-1;} void Push(Stack pStack,Data x){ if(pStack->pos>=MAX-1) exit(OVERFLOW); else { pStack->pos++; pStack->data[pStack->pos]=x; } } void Pop(Stack pStack){ if(pStack->pos==-1) exit(OVERFLOW); else pStack->pos--;} Data GetTop(Stack pStack){ return pStack->data[pStack->pos];} Data SetStackElem(int x,int y,int d){ Data element; element.x=x; element.y=y; element.d=0; return element;} void DisplayPath(Stack pStack){ Data element; printf(“The path is:n”); while(!IsEmpty(pStack)) { element=GetTop(pStack); Pop(pStack); printf(“The node is:(%d,%d)n”,element.x,element.y); } } void MazePath(int maze[8][11],int direction[4][2],int x1,int y1,int x2,int y2){ int i,j,k,g,h; Stack pStack; Data element; pStack=InitStack(); maze[x1][y1]=2; Push(pStack,SetStackElem(x1,y1,0)); while(!IsEmpty(pStack)){ element=GetTop(pStack); Pop(pStack); i=element.x; j=element.y; k = element.d; while(k<=3) { g=i+direction[k][0]; h=j+direction[k][1]; if(g==x2 && h==y2 && maze[g][h]==0) { Push(pStack,SetStackElem(i,j,k)); Push(pStack,SetStackElem(x2,y2,k)); DisplayPath(pStack); return; } if(maze[g][h]==0) { maze[g][h]=2; Push(pStack,SetStackElem(i,j,k+1)); i=g; j=h; k=0; } else k++; } } printf(“The path has not been foundn”);} void main(){ int direction[4][2]={0,1,1,0,0,-1,-1,0}; int maze[8][11]= { 1,1,1,1,1,1,1,1,1,1,1，1,0,1,0,0,1,1,1,0,0,1，1,0,0,0,0,0,1,0,0,1,1，1,0,1,1,1,0,0,0,1,1,1，1,0,0,0,1,0,1,1,0,1,1，1,1,0,0,1,0,1,1,0,0,1，1,1,1,0,1,0,0,0,0,0,1，1,1,1,1,1,1,1,1,1,1,1 }; int i,j; printf(“The maze is:n”); for(i=0;i<8;i++){ for(j=0;j<11;j++) printf(“%2d”,maze[i][j]); printf(“n”);};MazePath(maze,direction,1,1,6,9);} ? 用隊列實現(xiàn)迷宮問題求解 #include //行列坐標 int pre;}sqtype; sqtype sq[r];struct moved { int x, y;//坐標增量，取值-1，0，1 }move[8]; int maze[m2][n2]; int PATH(int maze[][n2])//找迷宮maze的路徑 { int i,j,k,v,front,rear,x,y;int mark[m2][n2];for(i=0;i for(j=0;j mark[i ][j]=0;printf(“Please Input move arrayn”);for(i=0;i<8;i++){ scanf(“%d,%d”,&move[i ].x,&move[i ].y);sq[1].x=1;sq[1].y=1;sq[1].pre=0;front=1;rear=1;mark[1][1]=1; //標記入口以到達過 while(front<=rear){ x=sq[front].x; y=sq[front].y; //(x,y)為出發(fā)點 for(v=0;v<8;v++)//搜索(x,y)的8個相鄰(i,j)是否可以到達 { i=x+move[v].x; j=y+move[v].y; if((maze[i ][j]==0)&&(mark[i ][j]==0))//(i,j)為可以到達點，將起入隊 { rear++; sq[rear].pre=front; mark[i ][j]=1;//標記(i,j)已經(jīng)到達過 } if((i==m)&&(j==n)) //到達出口 { printf(“THE PATH: n”); k=rear; do { printf(“(%d %d)<-”,sq[k].x,sq[k].y); k=sq[k].pre;//找前一點 }while(k!=0);//k=0是已經(jīng)到達 for(i=1;i<19;i++) printf(“%3d”,i); printf(“n”); for(i=1;i<19;i++) printf(“%3d”,sq[i ].x); printf(“n”); for(i=1;i<19;i++) printf(“%3d”,sq[i ].y); printf(“n”); for(i=1;i<19;i++) printf(“%3d”,sq[i ].pre); printf(“n”); return(1); //成功返回 } } front++; //出隊，front 指向新的出發(fā)點 } } //隊空，循環(huán)結(jié)束 printf(“There is no path!n”);return(0); //迷宮沒有路徑返回 } main(){ int i,j;for(i=0;i<10;i++){ maze[0][i ]=1; maze[7][i ]=1;} for(i=0;i<8;i++){ maze[i ][0]=1; maze[i ][9]=1;} /*for(i=1;i<7;i++) for(j=1;j<9;j++) { printf(“%d %d”,i,j); scanf(“%d”,&maze[i ][j]); }*/ maze[1][1]=0;maze[1][2]=1;maze[1][3]=0;maze[1][4]=1;maze[1][5]=1;maze[1][6]=0;maze[1][7]=1;maze[1][8]=1; maze[2][1]=1;maze[2][2]=0;maze[2][3]=0;maze[2][4]=1;maze[2][5]=1;maze[2][6]=0;maze[2][7]=1;maze[2][8]=0;maze[3][1]=0;maze[3][2]=1;maze[3][3]=1;maze[3][4]=0;maze[3][5]=0;maze[3][6]=1;maze[3][7]=1;maze[3][8]=1;maze[4][1]=1;maze[4][2]=0;maze[4][3]=0;maze[4][4]=1;maze[4][5]=1;maze[4][6]=0;maze[3][7]=0;maze[4][8]=1;maze[5][1]=1;maze[5][2]=1;maze[5][3]=0;maze[5][4]=0;maze[5][5]=1;maze[5][6]=1;maze[5][7]=0;maze[5][8]=1;maze[6][1]=0;maze[6][2]=1;maze[6][3]=1;maze[6][4]=1;maze[6][5]=0;maze[6][6]=0;maze[6][7]=0;maze[6][8]=0; printf(“n”);for(i=0;i<8;i++){ for(j=0;j<10;j++) printf(“%d”,maze[i ][j]); printf(“n”);} PATH(maze);} ? 分別用隊列實現(xiàn)一個列車調(diào)度系統(tǒng)。 實驗3 樹的應(yīng)用 一、實驗?zāi)康?/p> 1、領(lǐng)會并理解二叉樹的類型定義。 2、熟練掌握二叉樹的主要特性。 3、熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。 4、熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法。 5、了遞歸算法的實現(xiàn)過程。 二、實驗內(nèi)容及步驟 1、實現(xiàn)二叉樹的抽象數(shù)據(jù)類型。 2、構(gòu)造一棵二叉樹并用遞歸實現(xiàn)其先序、中序、后序遍歷算法并驗證。 3、用非遞歸算法實現(xiàn)二叉樹的中序遍歷。 4、給出一段報文和每個字符出現(xiàn)的概率，對其進行哈夫曼編碼和解碼。 三、實驗步驟與調(diào)試過程 利用棧來實現(xiàn)；根結(jié)點進棧，之后棧非空，彈出，接著根節(jié)點的右結(jié)點進棧，之后，左節(jié)點進棧；接著，彈出棧頂元素,此結(jié)點的右結(jié)點進棧，之后左節(jié)點進棧，彈出棧頂元素，直到棧為空。 從根節(jié)點開始，循環(huán)，只要有左子節(jié)點則進棧，直到左子節(jié)點為空。接著彈出棧頂輸出，判斷該結(jié)點是否有右子節(jié)點，若有則進棧，若沒有繼續(xù)彈棧。有右子節(jié)點的情況，判斷該節(jié)點是否有左子節(jié)點，有則進棧，直到左子節(jié)點為空；若該右子節(jié)點沒有左子節(jié)點，則彈棧；判斷彈出的節(jié)點，是否有右子節(jié)點，若有則進棧，沒有繼續(xù)彈棧；接著又要判斷剛進棧的這個節(jié)點，是否有左子節(jié)點，有則進棧，沒有則繼續(xù)彈棧。 從根結(jié)點開始，只要左子節(jié)點非空，則進棧，直到左子節(jié)點為空為止。取出棧頂元素，判斷取出的棧頂元素是否有右子節(jié)點，或者右子節(jié)點是否被訪問過，若滿足條件，則輸出該結(jié)點，同時彈棧，并且記錄下該訪問的節(jié)點。取出的棧頂元素，若有右子節(jié)點，且未被訪問過，則指針繼續(xù)移動到右子節(jié)點。 四、實驗結(jié)果 五、疑難小結(jié) 用圖形顯示遍歷能夠是人更好的明白二叉樹的遍歷，更好的理解二叉樹的鏈式結(jié)構(gòu)的存儲，理解二叉樹遍歷的過程，能夠針對遞歸結(jié)構(gòu)的二叉樹進行查詢、修改、刪除的操作。 六、主要算法和程序清單 二叉樹遞歸實現(xiàn)其先序、中序、后序遍歷算法并驗證。/*包含頭文件及宏定義*/ #include /*定義棧的最大容量*/ /*函數(shù)的聲明*/ void CreateBitTree2(BiTree *T,char str[]);/*利用括號嵌套的字符串建立二叉樹的函數(shù)聲明*/ void LevelPrint(BiTree T); /*按層次輸出二叉樹的結(jié)點*/ void TreePrint(BiTree T,int nLayer);/*按樹狀打印二叉樹*/ typedef struct Node /*二叉鏈表存儲結(jié)構(gòu)類型定義*/ { DataType data; /*數(shù)據(jù)域*/ struct Node *lchild; /*指向左孩子結(jié)點*/ struct Node *rchild; /*指向右孩子結(jié)點*/ }*BiTree,BitNode; void InitBitTree(BiTree *T)/*二叉樹的初始化操作*/ { *T=NULL;} void DestroyBitTree(BiTree *T)/*銷毀二叉樹操作*/ { if(*T) /*如果是非空二叉樹*/ { if((*T)->lchild) DestroyBitTree(&((*T)->lchild)); if((*T)->rchild) DestroyBitTree(&((*T)->rchild)); free(*T); *T=NULL;} } void CreateBitTree(BiTree *T)/*遞歸創(chuàng)建二叉樹*/ { DataType ch; scanf(“%c”,&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode));/*生成根結(jié)點*/ if(!(*T)) exit(-1); (*T)->data=ch; CreateBitTree(&((*T)->lchild)); /*構(gòu)造左子樹*/ CreateBitTree(&((*T)->rchild)); /*構(gòu)造右子樹*/ } } int InsertLeftChild(BiTree p,BiTree c)/*二叉樹的左插入操作*/ { if(p) /*如果指針p不空*/ { c->rchild=p->lchild; /*p的原來的左子樹成為c的右子樹*/ p->lchild=c; /*子樹c作為p的左子樹*/ return 1; } return 0;} int InsertRightChild(BiTree p,BiTree c)/*二叉樹的右插入操作*/ { if(p) /*如果指針p不空*/ { c->rchild=p->rchild; /*p的原來的右子樹作為c的右子樹*/ p->rchild=c; /*子樹c作為p的右子樹*/ return 1; } return 0;} BiTree Point(BiTree T,DataType e)/*查找元素值為e的結(jié)點的指針*/ { BiTree Q[MaxSize]; /*定義一個隊列，用于存放二叉樹中結(jié)點的指針*/ int front=0,rear=0; /*初始化隊列*/ BitNode *p; if(T) /*如果二叉樹非空*/ { Q[rear]=T; rear++; while(front!=rear)/*如果隊列非空*/ { p=Q[front]; /*取出隊頭指針*/ front++; /*將隊頭指針出隊*/ if(p->data==e) return p; if(p->lchild) /*如果左孩子結(jié)點存在，將左孩子指針入隊*/ { Q[rear]=p->lchild;/*左孩子結(jié)點的指針入隊*/ rear++; } if(p->rchild) /*如果右孩子結(jié)點存在，將右孩子指針入隊*/ { Q[rear]=p->rchild;/*右孩子結(jié)點的指針入隊*/ rear++; } } } return NULL;} DataType LeftChild(BiTree T,DataType e)/*返回二叉樹的左孩子結(jié)點元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->lchild) 在*/ return p->lchild->data; } return;} DataType RightChild(BiTree T,DataType e)/*返回二叉樹的右孩子結(jié)點元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->rchild) 在*/ return p->rchild->data; } return;} int DeleteLeftChild(BiTree p)/*二叉樹的左刪除操作*/ { if(p) { DestroyBitTree(&(p->lchild)); return 1; } return 0;} int DeleteRightChild(BiTree p)/*二叉樹的左刪除操作*/ { if(p) { DestroyBitTree(&(p->rchild)); return 1; } return 0;} void main() /*如果二叉樹不空*/ /*p是元素值e的結(jié)點的指針*/ /*如果p不為空且p的左孩子結(jié)點存 /*返回p的左孩子結(jié)點的元素值*/ /*如果二叉樹不空*/ /*p是元素值e的結(jié)點的指針*/ /*如果p不為空且p的右孩子結(jié)點存/*返回p的右孩子結(jié)點的元素值*/ /*如果p不空*/ /*刪除左子樹*/ /*如果p不空*/ /*刪除右子樹*/ { BiTree T,root;printf(“根據(jù)括號嵌套(a(b(c,d),e(f(,g),h(i)))建立二叉樹:n”);CreateBitTree2(&T,“(a(b(c,d),e(f(,g),h(i)))”);printf(“按層次輸出二叉樹的序列：n”);LevelPrint(T);printf(“n”);printf(“按樹狀打印二叉樹：n”);TreePrint(T,1);printf(“根據(jù)括號嵌套(A(B(D(,H),E(,I)),C(F,G)))建立二叉樹:n”);CreateBitTree2(&root,“(A(B(D(,H),E(,I)),C(F,G)))”);printf(“按層次輸出二叉樹的序列：n”);LevelPrint(root);printf(“n”);printf(“按樹狀打印二叉樹：n”);TreePrint(root,1);DestroyBitTree(&T);DestroyBitTree(&root);} void LevelPrint(BiTree T)/*按層次打印二叉樹中的結(jié)點*/ { BiTree queue[MaxSize]; /*定義一個隊列，用于存放結(jié)點的指針*/ BitNode *p; int front,rear; /*定義隊列的隊頭指針和隊尾指針*/ front=rear=-1; /*隊列初始化為空*/ rear++; /*隊尾指針加1*/ queue[rear]=T; /*將根結(jié)點指針入隊*/ while(front!=rear) /*如果隊列不為空*/ { front=(front+1)%MaxSize; p=queue[front]; /*取出隊頭元素*/ printf(“%c ”,p->data); /*輸出根結(jié)點*/ if(p->lchild!=NULL) /*如果左孩子不為空，將左孩子結(jié)點指針入隊*/ { rear=(rear+1)%MaxSize; queue[rear]=p->lchild; } if(p->rchild!=NULL) /*如果右孩子不為空，將右孩子結(jié)點指針入隊*/ { rear=(rear+1)%MaxSize; queue[rear]=p->rchild; } } } void TreePrint(BiTree T,int level)/*按樹狀打印的二叉樹*/ { int i;if(T==NULL) /*如果指針為空，返回上一層*/ return;TreePrint(T->rchild,level+1); /*打印右子樹，并將層次加1*/ for(i=0;i /*按照遞歸的層次打印空格*/ printf(“ ”);printf(“%cn”,T->data); /*輸出根結(jié)點*/ TreePrint(T->lchild,level+1); /*打印左子樹，并將層次加1*/ } void CreateBitTree2(BiTree *T,char str[])/*利用括號嵌套的字符串建立二叉鏈表*/ { char ch;BiTree stack[MaxSize]; /*定義棧，用于存放指向二叉樹中結(jié)點的指針*/ int top=-1; /*初始化棧頂指針*/ int flag,k;BitNode *p;*T=NULL,k=0;ch=str[k];while(ch!='