第一篇：數據結構實驗C語言版
南陽理工學院
數據結構(C語言版)上機實驗指導書
軟件學院·軟件工程
目錄
實驗1 線性表應用
實驗2 棧和隊列的應用.......................................................................14 實驗3 線性表應用...............................................................................27 實驗4 圖論及其應用...........................................................................46
實驗5 查找
實驗6 排序...........................................................................................64
實驗1 線性表應用
一、實驗目的
3，了解和掌握線性表順序存儲和鏈式存儲在計算機中的表示，基本操做在計算機中的實 2，能夠利用線性表結構對實際問題進行分析建模，利用計算機求解。
1，能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合。
二、實驗內容及步驟
1、利用程序設計語言分別實現順序表和鏈表的抽象數據類型。
2、掌握程序分文件（頭文件和實現文件）書寫的方式。
3、分別用順序表和鏈表實現課本算法2.2：合并兩個非遞減有序序列，并對其時間性能做出分析。
三、實驗步驟與調試過程
以線性表來描述一元多項式，儲存結構采用單鏈表，每個結點儲存的多項式中某一項的系數和指數，建立單鏈表時指數高的結點列于指數低的結點之后，即線性表的元素按指數遞增有序排列。
四、實驗結果
五、疑難小結
當線性表的長度變化較大，難以估計其存儲規模，另外對線性表頻繁進行插入和刪除操作時，則采用鏈表作為存儲結構可能會更好一些。在實際應用中應該考慮以下因素：(1)應有利于運算的實現；(2)應有利于數據的特性；(3)應有利于軟件環境。
六、主要算法和程序清單 順序表的非遞減數列合并 #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的元素，查找成功將對應元素的序號返回，否則返回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)/*在插入元素前，判斷順序表是否已經滿，不能插入元素*/ { 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中元素的函數聲明 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++) /*將數組a中的元素插入到順序表A中*/ { if(InsertList(&A,i,a[i-1])==0) { printf(“位置不合法”); return; } } for(i=1;i<=sizeof(b)/sizeof(b[0]);i++) /*將數組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中出現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中已經沒有元/*將A中剩余元素插入到C中*/ /*如果B中元素還有剩余，這時A中已經沒有元/*將B中剩余元素插入到C中*/ k++;} C->length=A.length+B.length;/*C的表長等于A和B的表長的和*/ } ? 鏈式表的非遞減數列合并 /*包含頭文件*/ #include #include DataType data; struct Node *next;}ListNode,*LinkList;void MergeList(LinkList A,LinkList B,LinkList *C);/*將單鏈表A和B的元素合并到C中的函數聲明*/ void InitList(LinkList *head)/*將單鏈表初始化為空。動態生成一個頭結點，并將頭結點的指 針域置為空。*/ { if((*head=(LinkList)malloc(sizeof(ListNode))) ==NULL)/*為頭結點分配一個存儲空間*/ exit(-1);(*head)->next=NULL; /*將單鏈表的頭結點指針域置為空*/ } int ListEmpty(LinkList head) /*判斷單鏈表是否為空，就是通過判斷頭結點的指針域是否為空 */ { if(head->next==NULL) /*判斷 單鏈表頭結點的指針域是否為空*/ return 1; /*當單鏈表為空時，返回1；否則返回0*/ else return 0;} ListNode *Get(LinkList head,int i) /*查找單鏈表中第i個結點。查找成功返回該結點的指針表示成 功；否則返回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個結點，返回指針p*/ else return NULL;/*如果沒有找到第i個元 素，返回NULL*/ } ListNode *LocateElem(LinkList head,DataType e) /*查找線性表中元素值為e的元素，查找成功將對應元素的結點 指針返回，否則返回NULL表示失敗。*/ { ListNode *p;p=head->next;/*指針p指向第一個結點*/ while(p){ if(p->data!=e)/*找到與e相等的元素，返 回該序號*/ p=p->next; else break;} return p;} int LocatePos(LinkList head,DataType e) /*查找線性表中元素值為e的元素，查找成功將對應元素的序號 返回，否則返回0表示失敗。*/ { ListNode *p;int i; if(ListEmpty(head))/*在查找第i個元 素之前，判斷鏈表是否為空*/ return 0; p=head->next;/*指針p指向第一 個結點*/ 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個位置插入一個結點，結點的元素值為e。插入 成功返回1，失敗返回0*/ { ListNode *p,*pre;/*定義指向第i個元素的前 驅結點指針pre，指針p指向新生成的結點*/ int j;pre=head; /*指針p指向頭結 點*/ j=0;while(pre->next!=NULL&&j pre=pre->next; j++;} if(!pre) /*如果沒找到，說明插入位置錯誤*/ { printf(“插入位置錯”); return 0;} /*新生成一個結點，并將e賦值給該結點的數據域*/ if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL) exit(-1);p->data=e;/*插入結點操作*/ p->next=pre->next;pre->next=p;return 1;} int DeleteList(LinkList head,int i,DataType *e)/*刪除單鏈表中的第i個位置的結點。刪除成功返回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) /*如果沒找到要 刪除的結點位置，說明刪除位置錯誤*/ { printf(“刪除位置錯誤”); return 0;} /*指針p指向單鏈表中的第i個結點，并將該結點的數據 域值賦值給e*/ p=pre->next;*e=p->data;/*將前驅結點的指針域指向要刪除結點的下一個結點，也就是將p指向的結點與單鏈表斷開*/ pre->next=p->next; free(p); /*釋放p指向的結 點*/ 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++)/*將數組a中元素插入到單鏈表A中*/ { if(InsertList(A,i,a[i-1])==0) { printf(“位置不合法”); return; } } for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)/*將數組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中的每個結點的指針*/ 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中的每個每個結點的指針*/ 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中每個結點的指針*/ 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的頭結點作為C的頭結點*/(*C)->next=NULL;pc=*C;/*依次將鏈表A和B中較小的元素存入鏈表C中*/ while(pa&&pb) { if(pa->data<=pb->data) { pc->next=pa;/*如果A中的元素小于或等于B中的元素，將A中的元素的結點作為C的結點*/ pc=pa; pa=pa->next; } else { pc->next=pb;/*如果A中的元素大于B中的元素，將B中的元素的結點作為C的結點*/ pc=pb; pb=pb->next; } } pc->next=pa?pa:pb;/*將剩余的結點插入C中*/ free(B); /*釋放B的頭結點*/ } 實驗2 棧和隊列的應用 一、實驗目的 1、掌握棧和隊列這兩種抽象數據類型的特點，并能在相應的應用問題中正確選用它們。 2、熟練掌握棧類型的兩種實現方法。 3、熟練掌握循環隊列和鏈隊列的基本操作實現算法。 二、實驗內容及步驟 1、用程序設計語言實現棧和隊列的抽象數據類型。 2、在第一題的基礎上完成以下選擇： 選擇一： 1)設計并實現括號匹配算法。 2)用隊列實現在屏幕上打印楊輝三角。選擇二： 分別用棧和隊列實現迷宮問題求解。選擇三： 分別用棧和隊列實現一個列車調度系統。 三、實驗步驟與調試過程 首先只只置操作數棧為空，表達式起始符“#”為運算符棧的棧底元素，依次讀入表達式中每個字符，直至整個表達式求值完畢。 四、實驗結果 五、疑難小結 對棧的順序存儲結構用了更深刻的了解，同時也對程序設計能力有了提高，加深了對棧先進后出性質的理解，對數組的應用也十分熟練。 六、主要算法： ? 括號匹配算法。#include DataType data; struct node *next;}LStackNode,*LinkStack;void InitStack(LinkStack *top)/*將鏈棧初始化為空。動態生成頭結點，并將頭結點的指針域置為空。*/ { if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL)/*為頭結點分配一個存儲 空間*/ exit(-1);(*top)->next=NULL; /*將鏈棧的頭結點指針域置為空*/ } int StackEmpty(LinkStack top) /*判斷鏈棧是否為空，就是通過判斷頭結點的指針域是否為空*/ { if(top->next==NULL) /*判斷鏈棧頭結點的指針域是否為空*/ return 1; /*當鏈棧為空時，返回1；否則返回0*/ else return 0;} int PushStack(LinkStack top, DataType e)/*進棧操作就是要在鏈表的第一個結點前插入一個新結點，進棧成功返回1*/ { LStackNode *p;/*定義指向第i個元素的前驅結點指針pre，指針p指向新生成的結點*/ if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL){ printf(“內存分配失敗!”); exit(-1);} p->data=e; /*指針p指向頭結點*/ p->next=top->next;top->next=p;return 1;} int PopStack(LinkStack top,DataType *e)/*刪除單鏈表中的第i個位置的結點。刪除成功返回1，失敗返回0*/ { LStackNode *p; p=top->next; if(!p) /*判斷鏈棧是否為空*/ { printf(“棧已空”); return 0; } top->next=p->next; /*將棧頂結點與鏈表斷開，即出棧*/ *e=p->data; /*將出棧元素賦值給e*/ free(p); /*釋放p指向的結點*/ 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;} ? 用隊列實現在屏幕上打印楊輝三角 /*包含頭文件*/ #include /*定義鏈式隊列元素的類型為整數類型*/ #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) /*將帶頭結點的鏈式隊列初始化為空隊列需要把頭結點的指針域置為0*/ { LQ->front=(LQNode*)malloc(sizeof(LQNode));if(LQ->front==NULL)exit(-1); LQ->front->next=NULL;/*把頭結點的指針域置為為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));/*為將要入隊的元素申請一個結點的空間*/ if(!s)exit(-1); /*如果申請空間失敗，則退出并返回參數-1*/ s->data=e; /*將元素值賦值給結點的數據域*/ s->next=NULL; /*將結點的指針域置為空*/ 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; /*使頭結點的指針指向指針p的下一個結點*/ // if(LQ->rear==s)LQ->rear=LQ->front;/*如果要刪除的結點是隊尾，則使隊尾指針指向隊頭指針*/ // free(s); /*釋放指針p指向的結點*/ // 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)/*鏈式隊列實現打印楊輝三角*/ { int i,j,k,n;DataType e,t;int temp[MaxSize]; LinkQueue Q;k=0;InitQueue(&Q); EnterQueue(&Q,1); /*產生第中間n-2行的元素*/ for(n=2;n<=N;n++) 在臨時數組中*/ { 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)) { /*定義一個臨時數組，用于存放每一行的元素*/ /*初始化鏈隊列*/ /*第一行元素入隊*/ /*產生第i行元素并入隊，同時將第i-1行的元素保存/*第i行的第一個元素入隊*/ /*利用隊列中第i-1行元素產生第i行的中間i-2個元素/*將第i-1行的元素存入臨時數組*/ /*取隊頭元素*/ /*利用隊中第i-1行元素產生第i行元素*/ /*將第i-1行的最后一個元素存入臨時數組*/ /*第i行的最后一個元素入隊*/ /*將最后一行元素存入數組之前，要將下標k置為0*/ /*將最后一行元素存入臨時數組*/ DeleteQueue(&Q,&t); temp[k++]=t; if(QueueEmpty(Q)) PrintArray(temp,k,N);} } void main(){ int n;printf(“請輸入要打印的行數：n=:”);scanf(“%d”,&n); YangHuiTriangle(n);} void PrintArray(int a[],int n,int N)/*打印數組中的元素，使能夠呈正確的形式輸出*/ { int i;static count=0; /*記錄輸出的行*/ for(i=0;i /*打印空格*/ printf(“ ”);count++;for(i=0;i /*打印數組中的元素*/ printf(“%6d”,a[i]);printf(“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);} ? 用隊列實現迷宮問題求解 #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)為出發點 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)已經到達過 } 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是已經到達 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 指向新的出發點 } } //隊空，循環結束 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);} ? 分別用隊列實現一個列車調度系統。 實驗3 樹的應用 一、實驗目的 1、領會并理解二叉樹的類型定義。 2、熟練掌握二叉樹的主要特性。 3、熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現二叉樹的其它操作。 4、熟練掌握二叉樹和樹的各種存儲結構及其建立的算法。 5、了遞歸算法的實現過程。 二、實驗內容及步驟 1、實現二叉樹的抽象數據類型。 2、構造一棵二叉樹并用遞歸實現其先序、中序、后序遍歷算法并驗證。 3、用非遞歸算法實現二叉樹的中序遍歷。 4、給出一段報文和每個字符出現的概率，對其進行哈夫曼編碼和解碼。 三、實驗步驟與調試過程 利用棧來實現；根結點進棧，之后棧非空，彈出，接著根節點的右結點進棧，之后，左節點進棧；接著，彈出棧頂元素,此結點的右結點進棧，之后左節點進棧，彈出棧頂元素，直到棧為空。 從根節點開始，循環，只要有左子節點則進棧，直到左子節點為空。接著彈出棧頂輸出，判斷該結點是否有右子節點，若有則進棧，若沒有繼續彈棧。有右子節點的情況，判斷該節點是否有左子節點，有則進棧，直到左子節點為空；若該右子節點沒有左子節點，則彈棧；判斷彈出的節點，是否有右子節點，若有則進棧，沒有繼續彈棧；接著又要判斷剛進棧的這個節點，是否有左子節點，有則進棧，沒有則繼續彈棧。 從根結點開始，只要左子節點非空，則進棧，直到左子節點為空為止。取出棧頂元素，判斷取出的棧頂元素是否有右子節點，或者右子節點是否被訪問過，若滿足條件，則輸出該結點，同時彈棧，并且記錄下該訪問的節點。取出的棧頂元素，若有右子節點，且未被訪問過，則指針繼續移動到右子節點。 四、實驗結果 五、疑難小結 用圖形顯示遍歷能夠是人更好的明白二叉樹的遍歷，更好的理解二叉樹的鏈式結構的存儲，理解二叉樹遍歷的過程，能夠針對遞歸結構的二叉樹進行查詢、修改、刪除的操作。 六、主要算法和程序清單 二叉樹遞歸實現其先序、中序、后序遍歷算法并驗證。/*包含頭文件及宏定義*/ #include /*定義棧的最大容量*/ /*函數的聲明*/ void CreateBitTree2(BiTree *T,char str[]);/*利用括號嵌套的字符串建立二叉樹的函數聲明*/ void LevelPrint(BiTree T); /*按層次輸出二叉樹的結點*/ void TreePrint(BiTree T,int nLayer);/*按樹狀打印二叉樹*/ typedef struct Node /*二叉鏈表存儲結構類型定義*/ { DataType data; /*數據域*/ struct Node *lchild; /*指向左孩子結點*/ struct Node *rchild; /*指向右孩子結點*/ }*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)/*遞歸創建二叉樹*/ { DataType ch; scanf(“%c”,&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode));/*生成根結點*/ if(!(*T)) exit(-1); (*T)->data=ch; CreateBitTree(&((*T)->lchild)); /*構造左子樹*/ CreateBitTree(&((*T)->rchild)); /*構造右子樹*/ } } 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的結點的指針*/ { BiTree Q[MaxSize]; /*定義一個隊列，用于存放二叉樹中結點的指針*/ 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) /*如果左孩子結點存在，將左孩子指針入隊*/ { Q[rear]=p->lchild;/*左孩子結點的指針入隊*/ rear++; } if(p->rchild) /*如果右孩子結點存在，將右孩子指針入隊*/ { Q[rear]=p->rchild;/*右孩子結點的指針入隊*/ rear++; } } } return NULL;} DataType LeftChild(BiTree T,DataType e)/*返回二叉樹的左孩子結點元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->lchild) 在*/ return p->lchild->data; } return;} DataType RightChild(BiTree T,DataType e)/*返回二叉樹的右孩子結點元素值操作*/ { 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的結點的指針*/ /*如果p不為空且p的左孩子結點存 /*返回p的左孩子結點的元素值*/ /*如果二叉樹不空*/ /*p是元素值e的結點的指針*/ /*如果p不為空且p的右孩子結點存/*返回p的右孩子結點的元素值*/ /*如果p不空*/ /*刪除左子樹*/ /*如果p不空*/ /*刪除右子樹*/ { BiTree T,root;printf(“根據括號嵌套(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(“根據括號嵌套(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)/*按層次打印二叉樹中的結點*/ { BiTree queue[MaxSize]; /*定義一個隊列，用于存放結點的指針*/ BitNode *p; int front,rear; /*定義隊列的隊頭指針和隊尾指針*/ front=rear=-1; /*隊列初始化為空*/ rear++; /*隊尾指針加1*/ queue[rear]=T; /*將根結點指針入隊*/ while(front!=rear) /*如果隊列不為空*/ { front=(front+1)%MaxSize; p=queue[front]; /*取出隊頭元素*/ printf(“%c ”,p->data); /*輸出根結點*/ if(p->lchild!=NULL) /*如果左孩子不為空，將左孩子結點指針入隊*/ { rear=(rear+1)%MaxSize; queue[rear]=p->lchild; } if(p->rchild!=NULL) /*如果右孩子不為空，將右孩子結點指針入隊*/ { 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); /*輸出根結點*/ TreePrint(T->lchild,level+1); /*打印左子樹，并將層次加1*/ } void CreateBitTree2(BiTree *T,char str[])/*利用括號嵌套的字符串建立二叉鏈表*/ { char ch;BiTree stack[MaxSize]; /*定義棧，用于存放指向二叉樹中結點的指針*/ int top=-1; /*初始化棧頂指針*/ int flag,k;BitNode *p;*T=NULL,k=0;ch=str[k];while(ch!='
主站蜘蛛池模板：
国产精品对白刺激久久久|
国模无码视频一区二区三区|
精品久久久久久亚洲综合网|
情人伊人久久综合亚洲|
中文字幕久久久久人妻|
亚洲国产精品尤物yw在线|
色综合av综合无码综合网站|
日本高清aⅴ毛片免费|
亚洲精品无码一区二区三区四虎|
久久精品国产99久久久香蕉|
无人区码一码二码w358cc|
国产盗摄xxxx视频xxxx|
成年片色大黄全免费网站久久高潮|
av中文无码乱人伦在线观看|
国产寡妇树林野战在线播放|
亚洲aⅴ无码天堂在线观看|
性中国妓女毛茸茸视频|
日韩不卡手机视频在线观看|
亚洲中文字幕国产综合|
女人被弄到高潮的免费视频|
国产va在线观看免费|
国产成人亚洲综合无码加勒比一|
亚洲成在线aⅴ免费视频|
男男车车的车车网站w98免费|
国产在线视频一区二区三区|
99久久无码国产精品性出奶水|
国产重口老太和小伙乱|
国产真人无遮挡作爱免费视频|
在线精品国精品国产尤物|
亚洲制服有码在线丝袜|
熟女无套内射线观56|
在线综合亚洲中文精品|
最好看2019高清中文字幕视频|
成人片无码免费播放|
中文字幕av在线一二三区|
国产成人av乱码在线观看|
国产精品进线69影院|
国产日产欧产美韩系列麻豆|
亚洲一卡2卡新区国色天香|
色综合av亚洲超碰少妇|
爽爽影院免费观看视频|