數(shù)據(jù)結構實驗系統(tǒng)源代碼(期末作業(yè))

/*樹子系統(tǒng) */#include<stdio.h>#include<malloc.h>#defineMAX100intcount=0; /*定義計算結點個數(shù)的變量 */typedefstructtnode{chardata;structtnode*lchild,*rchild;}BT;BT*CreateBTree(){BT*t;charch;scanf("%c",&ch);getchar();if(ch=='0')t=NULL;else{t=(BT*)malloc(sizeof(BT));t->data=ch;",t->data);",t->data);printf("請輸入％c結點的左孩子結點:",t->data);",t->data);printf("請輸入％c結點的右孩子結點:t->rchild=CreateBTree();}returnt;}/*用廣義表表示法顯示二叉樹 /*用廣義表表示法顯示二叉樹 *//*當二叉樹非空時 *//*輸入該結點數(shù)據(jù)域 *//*若其左子樹非空 *//*輸入左括號 *//*遞歸調用該函數(shù)輸出其左子樹各結點 *//*若其右子樹非空 *//*輸出逗號 *//*遞歸調用該函數(shù)輸出其右子樹各結點 */{if(T!=NULL){printf("%c",T->data);if(T->lchild!=NULL){printf("(");ShowBTree(T->lchild);if(T->rchild!=NULL){printf(",");ShowBTree(T->rchild);}printf(")");}else/*/*二叉樹左子樹為空，右子樹不為空時 */if(T->rchild!=NULL){/*輸入左括號 /*輸入左括號 *//*遞歸調用該函數(shù)輸出其左子樹各結點 *//*若其右子樹非空 *//*輸出逗號 *//*遞歸調用該函數(shù)輸出其右子樹各結點 */ShowBTree(T->lchild);if(T->rchild!=NULL){printf(",");ShowBTree(T->rchild);}printf(")");}}}/*先序遍歷二叉樹 /*先序遍歷二叉樹 T*//* 遞歸調用的結束條件 *//*輸出結點的數(shù)據(jù)域 *//* 先序遞歸遍歷左子樹 *//* 先序遞歸遍歷右子樹 */{if(T==NULL)return;else{printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}/*中序遍歷二叉樹 /*中序遍歷二叉樹 T*//*遞歸調用的結束條件 *//*中序遞歸遍歷左子樹 *//*輸出結點的數(shù)據(jù)域 *//*中序遞歸遍歷右子樹 */{if(T==NULL)return;else{InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}/*后序遍歷二叉樹 /*后序遍歷二叉樹 T*//*遞歸調用的結束條件 *//*后序遞歸遍歷左子樹 *//*后序遞歸遍歷右子樹 *//*輸出結點的數(shù)據(jù)域 */{if(T==NULL)return;else{PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->data);}}/*按層次遍歷二叉樹 /*按層次遍歷二叉樹 T*//*定義隊頭隊尾指針 *//*定義循環(huán)隊列，存放結點指針 */{intf,r;BT*p,*q[MAX];p=T;if(p!=NULL){f=1; q[f]=p;r=2;}while(f!=r){p=q[f];printf("%c",p->data);if(p->lchild!=NULL){q[r]=p->lchild; r=(r+1)%MAX;}if(p->rchild!=NULL){q[r]=p->rchild; r=(r+1)%MAX;}f=(f+1)%MAX;}}TOC\o"1-5"\h\z/*若二叉樹非空，則根結點地址入隊 *//*隊列不空時 *//*訪問隊首結點的數(shù)據(jù)域 *//*將隊首結點的左孩子入隊 *//*將隊首結點的右孩子入隊 */voidLeafnum(BT*T) /*求二叉樹葉子結點數(shù) */{if(T) /*若樹不為空 */{if(T->lchild==NULL&&T->rchild==NULL)count++;Leafnum(T->lchild);Leafnum(T->rchild);}}TOC\o"1-5"\h\z/*全局變量 count為計數(shù)值， 其初值為 0*//*遞歸統(tǒng)計 T的左子樹葉子結點數(shù) *//*遞歸統(tǒng)計 T的右子樹葉子結點數(shù) */voidNodenum(BT*T){if(T){count++;Nodenum(T->lchild);Nodenum(T->rchild);}}intTreeDepth(BT*T){intldep=0,rdep=0;的深度*/if(T==NULL)return0;else{ldep=TreeDepth(T->lchild);rdep=TreeDepth(T->rchild);if(ldep>rdep)returnldep+1;else/*若樹不為空 *//*全局變量 count為計數(shù)值， 其初值為 0*//*遞歸統(tǒng)計 T的左子樹結點數(shù) *//*遞歸統(tǒng)計 T的右子樹結點數(shù) *//*求二叉樹深度 *//*定義兩個整型變量， 用以存放左、 右子樹/*遞歸統(tǒng)計 T的左子樹深度 *//*遞歸統(tǒng)計 T的右子樹深度 */returnrdep+1;void（MenuTree（）/*顯示菜單子函數(shù)*/printf（"\n二叉樹子系統(tǒng)");printf（"\nprintf（"\n================================================="）;TOC\o"1-5"\h\zprintf（"\n| 1——建立一個新二叉樹 |"）;printf（"\n| 2 廣義表表示法顯示 |"）;printf（"\n| 3 先序遍歷 |"）;printf（"\n| 4 中序遍歷 |"）;printf（"\n| 5 后序遍歷 |"）;printf（"\n| 6 層次遍歷 |"）;printf（"\n| 7 求葉子結點數(shù)目 |"）;printf（"\n| 8 求二叉樹總結點數(shù)目 |"）;printf（"\n| 9——求樹深度 |"）;printf（"\n| 0 返回 |"）;printf（"\n================================================"）;printf（"\n請輸入菜單號（0-9）:"）;btree（）（BT*T=NULL;charch1,ch2,a;ch1='y';while（ch1=='y'||ch1=='Y'）{MenuTree（）;scanf（"%c",&ch2）;getchar（）;switch（ch2）{case'1':printf（"請按先序序列輸入二叉樹的結點： \n"）;printf（"說明：輸入結點后按回車（’0'表示后繼結點為空）：\n"）;printf（"請輸入根結點："）；T=CreateBTree（）;printf（"二叉樹成功建立！ "）;break;case'2':printf（"二叉樹廣義表表示法如下： "）;ShowBTree（T）;break;case'3':printf（"二叉樹的先序遍歷序列為： "）;PreOrder（T）;break;case'4':TOC\o"1-5"\h\zprintf("二叉樹的中序遍歷序列為： ");InOrder(T);break;case'5':printf("二叉樹的后序遍歷序列為： ");PostOrder(T);break;case'6':printf("二叉樹的層次遍歷序列為： ");LevelOrder(T);break;case'7':count=0;Leafnum(T);printf("該二叉樹有％~個葉子。",count);break;case'8':count=0;Nodenum(T);printf("該二叉機擋^有％~個結點?！?count);break;case'9':printf("該二叉樹的深度是 %d。",TreeDepth(T));break;case'0':ch1='n';break;default:printf("輸入有誤，請輸入 0-9進行選擇！ ");}if(ch2!='0'){printf("\n按回車鍵繼續(xù)，按任意鍵返回主菜單！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';}}/*用鄰接表存儲的圖子系統(tǒng) *//*/*最大頂點數(shù) *//*全局變量，訪問數(shù)組 *//*鄰接點域 *//*指向下一鄰接點的指針域 *//*定義邊表結點 */#include"stdio.h"#include"malloc.h"#defineMAX100typedefcharVertexType;intvisited[MAX];typedefstructnode{intadjvex;structnode*next;}EdgeNode;typedefstructvexnode{VertexTypedata;EdgeNode*firstedge;}VHeadNode;/*頂點域*//*指向第一條邊結點 *//*定義頂點表結點 */typedefstruct{VHeadNodeadjlist[MAX];intn,e;}AdjList;TOC\o"1-5"\h\z/*鄰接表頭結點數(shù)組 *//*頂點數(shù)，邊數(shù) *//*圖的鄰接表類型 */voidCreateAGraph(AdjList*g,intflag){/*生成無向圖的鄰接表函數(shù) */inti,j,k;EdgeNode*p;if(flag==0)printf("\n=========== 將建立一個無向圖 ===========\n");elseprintf("\n=========== 將建立一個有向圖 ===========\n");TOC\o"1-5"\h\zprintf（"請輸入圖的頂點數(shù)： "）;scanf（"%d",&g->n）;printf（"請輸入圖的邊數(shù)： "）;scanf("%d",&g->e);printf("\n請輸入圖的各頂點信息： \n"/*生成有/*生成有n個頂點的頂點表 *//*接受上次輸入的換行符 *//*讀入頂點信息 *//*點的邊表頭指針設為空 */{//getchar();printf("第％~個頂點信息：",i+1);scanf("\n%c",&(g->adjlist[i].data));g->adjlist[i].firstedge=NULL;}printf("\n請輸入邊的信息，輸入格式為 :序號 1，序號 2(序號依次為 0、1、2...)：\n");for(k=0;k<g->e;k++){printf("請輸入第％d條邊：”,k);scanf("\n%d,%d",&i,&j);/*將編號為 i的結點添加到鄰接表中 */p=(EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex=j;p->next=g->adjlist[i].firstedge;g->adjlist[i].firstedge=p;/*將編號為 j的結點添加到鄰接表中，有向圖不用添加該結點，去掉下面 if語句*/if(flag==0){p=(EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex=i; /*鄰接點序號為 i*/p->next=g->adjlist[j].firstedge; /*將新邊表結點 p插到頂點 vi邊表頭部 */g->adjlist[j].firstedge=p;}}}voidDispAGraph(AdjList*g){/*輸出圖的鄰接表函數(shù) */inti;EdgeNode*p;printf("\n圖的鄰接表表示如下： \n");for(i=0;i<g->n;i++){printf("%2d[%c]",i,g->adjlist[i].data);p=g->adjlist[i].firstedge;while(p!=NULL){printf("-->[%d]",p->adjvex);p=p->next;}printf("\n");}}voidDFS(AdjList*g,intvi){/*用鄰接表存儲的圖以頂點 vi開始深度優(yōu)先遍歷函數(shù) */EdgeNode*p;printf("(%d,",vi);

printf("%c)",g->adjlist[vi].data);visited[vi]=1;p=g->adjlist[vi].firstedge;while(p!=NULL){if(visited[p->adjvex]==0)DFS(g,p->adjvex);p=p->next;}}voidBFS(AdjList*g,intvi)TOC\o"1-5"\h\z{/*用鄰接表存儲的圖以頂點 vi開始廣度優(yōu)先遍歷函數(shù) */inti,v,visited[MAX];intqu[MAX],front=0,rear=0;EdgeNode*p;for(i=0;i<g->n;i++)visited[i]=0;intqu[MAX],front=0,rear=0;EdgeNode*p;for(i=0;i<g->n;i++)visited[i]=0;printf("(%d,",vi);/*輔助的訪問數(shù)組賦初值 *//*輸出起始訪問頂點 */printf("%c)",g->adjlist[vi].data);visited[vi]=1;rear=(rear+1)%MAX;visited[vi]=1;rear=(rear+1)%MAX;qu[rear]=vi;while(front!=rear)/*隊尾指針后移 *//*將vi入隊*//*當隊不空時 */{{front=(front+1)%MAX;v=qu[front];p=g->adjlist[v].firstedge;while(p!=NULL)TOC\o"1-5"\h\z/*將隊頭元素出隊，賦給頂點 v*//*將頂點v的下一條鄰接邊頂點指針賦給 p*/{if(visited[p->adjvex]==0)/*若未訪問過 */{visited[p->adjvex]=1;/*訪問數(shù)組該元素置 1，已訪問 */printf("(%d,",p->adjvex);/*輸出該頂點編號 */printf("%c)",g->adjlist[p->adjvex].data);/*輸出該頂點信息 */rear=(rear+1)%MAX; /*隊尾指針后移 */qu[rear]=p->adjvex; /*將p所指的頂點入隊 */}p=p->next; /*p指針后移 */}}}voidMenuGraph() /*顯示菜單子函數(shù) */{printf("\n 圖子系統(tǒng) ");printf("\n=================================================");TOC\o"1-5"\h\zprintf("\n| 1——更新鄰接表 |");printf("\n| 2——深度優(yōu)先遍歷 |");printf("\n| 3——廣度優(yōu)先遍歷 |");printf("\n| 0——返回 |");printf("\n=================================================");printf("\n請輸入菜單號( 0-3):");}graph() /*主函數(shù)*/{inti,f;charch1,ch2,a;AdjListg;ch1='y';while(ch1=='y'||ch1=='Y'){MenuGraph();scanf("%c",&ch2);getchar();switch(ch2){case'1':printf("要建立的是有向圖( 1)還是無向圖( 0)，請選擇(輸入 1或 0)：");scanf("%d",&f);CreateAGraph(&g,f);DispAGraph(&g);break;case'2':printf("請輸入開始進行深度遍歷的頂點序號(序號從 0開始編號) ：");scanf("%d",&f);printf("\n從頂點％~開始的深度優(yōu)先遍歷序列為： ",f);for(i=0;i<g.n;i++)visited[i]=0;DFS(&g,f);break;case'3':printf("請輸入開始進行廣度遍歷的頂點序號(序號從 0開始)：");scanf("%d",&i);printf("\n從頂點％~開始的廣度優(yōu)先遍歷序列為： ”,i);BFS(&g,i);break;case'0':ch1='n';break;default:printf("輸入有誤，請輸入 0-3進行選擇！ ");

}if(ch2!='0'){printf("\n按回車鍵繼續(xù)，按任意鍵返回主菜單！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';}}}}TOC\o"1-5"\h\z/*線性表子系統(tǒng) */#include<stdio.h>#include<malloc.h>typedefintDataType; /*定義DataType為int類型*/typedefstructlinknode /*單鏈表存儲類型 */{DataTypedata; /*定義結點的數(shù)據(jù)域 */structlinknode*next;/*定義結點的指針域 */}LinkList;LinkList*InitList(){ /*初始化鏈表函數(shù) */LinkList*head;head=(LinkList*)malloc(sizeof(LinkList));/*動態(tài)分配一個結點空間 */head->next=NULL;returnhead; /*頭結點L指針域為空，表示空鏈表 */}voidCreateListH(LinkList *head,intn){ /*頭插法建立鏈表函數(shù) */LinkList*s;inti;printf("請輸入％~個整數(shù)：",n);for(i=0;i<n;i++)/*生成新結點 /*生成新結點 *//*讀入新結點的數(shù)據(jù)域 *//*將新結點的指針域存放頭結點的指針域 *//*將新結點插入頭結點之后 */scanf("%d",&s->data);s->next=head->next;head->next=s;

}printf（"建立鏈表操作成功！ "）;}voidCreateListL(LinkList *head,intn){/*尾插法建立鏈表函數(shù) */LinkList*s,*last;inti;*/last=head; /*last始終指向尾結點，開始時指向頭結點*/printf（"請輸入％~個整數(shù)：",n）;for(i=0;i<n;i++){TOC\o"1-5"\h\zs=(LinkList*)malloc(sizeof(LinkList));/*生成新結點 */scanf("%d",&s->data);s->next=NULL;last->next=s;last=s;scanf("%d",&s->data);s->next=NULL;last->next=s;last=s;/*將新結點的指針域為空 *//*將新結點插入表尾 *//*將last指針指向表尾結點 */}printf（"建立鏈表操作成功！ "）;intLengthList(LinkList*head){ /*求鏈表長度函數(shù) */LinkList*p=head->next;intj=0;while(p!=NULL)/*當p不指向鏈表尾時 */{p=p->next;j++;}returnj;}voidLocate(LinkList*head,DataTypex){/*在鏈表中查找值為 x的元素位置 */intj=1; /*計數(shù)器*/LinkList*p;p=head->next;while(p!=NULL&&p->data!=x)/*查找及定位 */{p=p->next;j++;}if(p!=NULL)printf("在表白勺第%d位找到值為％~的結點！",j,x);elseprintf（"未找到值為％~的結點！",x）;voidSearchList(LinkList*head,inti)TOC\o"1-5"\h\z{/*在鏈表中按位置查找元素 */LinkList*p;intj=0;p=head; /*p指向鏈表的頭結點 */if(i>LengthList(head))printf("位置錯誤，鏈表中沒有該位置！ ");while(p->next!=NULL&&j<i){p=p->next;j++;}TOC\o"1-5"\h\zif(j==i) /*判斷與給定的序號是否相等 */printf("在第％~位上的元素值為％d!”,i,p->data);}voidInsList(LinkList *head,inti,DataTypex){/*按位置插入元素函數(shù) */intj=0;LinkList*p,*s;p=head;while(p->next!=NULL&&j<i-1) /*定位插入點 */{p=p->next;j++;}if(p!=NULL) /*p不為空則將新結點插到 p后*/{TOC\o"1-5"\h\zs=(LinkList*)malloc(sizeof(LinkList));/*生成新結點 s*/s->data=x; /*將數(shù)據(jù)x放入新結點的數(shù)據(jù)域*/s->next=p->next; /*將新結點s的指針域與p結點后面元素相連*/p->next=s; /*將p與新結點 s鏈接*/printf("插入元素成功！ ");}elseprintf("插入元素失敗 ");}voidDelList(LinkList *head,inti){/*按位置刪除鏈表中元素函數(shù) */intj=0;

DataTypex;LinkList*p=head,*s;/*定位插入點*//*定位插入點*//*q為要刪除結點*//*將要刪除的數(shù)據(jù)放入指針變量 x中*//*將p結點的指針域與q結點后面元素相連*/p=p->next;j++;}if(p->next!=NULL&&j==i-1)(s=p->next;x=s->data;p->next=s->next;free(s);printf("刪除第％d位上的元素％d成功！",i,x);}elseprintf（"刪除結點位置錯誤，刪除失??！ "）;}voidDispList(LinkList*head){/*顯示輸出鏈表函數(shù)*/LinkList*p;p=head->next;while(p!=NULL){printf("%5d",p->data);p=p->next;}}voidMenuLine(){ /*顯示菜單子函數(shù)*/printf("\n 線性表子系統(tǒng)");printf("\n=================================================");TOC\o"1-5"\h\zprintf("\n| 1 建立 |");printf("\n| 2 插入 |");printf("\n| 3 刪除 |");printf("\n| 4 按位置查找 |");printf("\n| 5——按元素值查找 |”);printf("\n| 6——求表長 |");printf("\n| 0 返回 |");printf("\n=================================================");printf("\n請輸入菜單號(0-6):");linklist(){LinkList*head;DataTypex;inti,n;charch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){MenuLine();scanf("%c",&ch2);getchar();switch(ch2){case'1':head=InitList();TOC\o"1-5"\h\zprintf("請輸入要建立線性表的長度： ");scanf("%d",&n);CreateListL(head,n); /*如改為CreateListH(L);則用頭插法建立鏈表 */printf("建立后的線性表為： \n");DispList(head);break;case'2':printf("請輸入要插入的元素位置： ");scanf("%d",&i);getchar();printf("請輸入要插入的元素值： ");scanf("%d",&x);InsList(head,i,x);printf("插入元素%~后的線性表為：\n",x);DispList(head);break;case'3':printf("請輸入要刪除的元素位置： ");scanf("%d",&i);DelList(head,i);printf("刪除第％d位的元素后的線性表為：\n",i);DispList(head);break;case'4':printf("請輸入查找的元素位置(大于等于 1的整數(shù))：");scanf("%d",&i);SearchList(head,i);break;

case'5':printf("請輸入查找的整數(shù)： ");scanf("%d",&x);Locate(head,x);break;case'6':printf("該線性表的長度為 %d！",LengthList(head));break;case'0':ch1='n';break;default:printf("輸入有誤，請輸入 0-9進行選擇！ ");}if(ch2!='0'){printf("\n按回車鍵繼續(xù)，按任意鍵返回主菜單！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';}}}}#include"stdio.h"#include"malloc.h"typedefintDataType;#include"stdio.h"#include"malloc.h"typedefintDataType;typedefstructqnode{DataTypedata;structqnode*next;}LinkListQ;typedefstruct{LinkListQ*front,*rear;}LinkQueue;/*定義DataType為int類型*//*鏈隊列存儲類型 *//*定義結點的數(shù)據(jù)域 *//*定義結點的指針域 *//*定義隊列的隊頭指針和隊尾指針 *//*鏈隊列的頭指針類型 */LinkQueue*InitQueue()TOC\o"1-5"\h\z{ /*初始化鏈隊列函數(shù) */LinkQueue*Q;LinkListQ*p;Q=(LinkQueue*)malloc(sizeof(LinkQueue));/*建立鏈隊列頭指針所指結點 */p=(LinkListQ*)malloc(sizeof(LinkListQ));/*建立鏈隊列的頭結點 */

Q->front=p;/*Q指針所指的 front指針指向 p*/Q->rear=p;/*Q指針所指的 rear指針指向 p*/returnQ;}intEmptyQueue(LinkQueue*Q){ /*判斷隊空函數(shù) */if(Q->front==Q->rear) /*鏈隊為空 */return1;elsereturn0;}voidInQueue(LinkQueue*Q,DataTypex)TOC\o"1-5"\h\z{ /*入隊函數(shù) */LinkListQ*p;p=(LinkListQ*)malloc(sizeof(LinkListQ)); /*生成新結點 */p->data=x; /*將x存入新結點的數(shù)據(jù)域 */p->next=NULL;Q->rear->next=p; /*將新結點插入鏈隊之后 */Q->rear=p; /*隊尾指針指向隊尾元素 */}intDeQueue(LinkQueue*Q,DataType*x){ /*出隊函數(shù) */LinkListQ*p;if(EmptyQueue(Q))/*調用判空函數(shù) EmptyQueue(Q)，判斷隊列是否為空 */{printf("隊空，不能出隊元素 !");else{p=Q->front->next;else{p=Q->front->next;*x=p->data;Q->front->next=p->next;if(p->next==NULL)Q->rear=Q->front;free(p);/*隊不為空 *//*p指向隊頭元素 *//*隊頭元素取出賦給 x*/*/*//**/*//*隊列中只含有一個元素出隊 *//*出隊后隊尾指針指向隊頭指針，此時隊空/*釋放原隊頭結點空間 */return1;intGetFront(LinkQueue*Q,DataType*x){ /*獲取隊頭元素函數(shù) */if(EmptyQueue(Q))/*調用判空函數(shù)EmptyQueue(Q),判斷隊列是否為空*/(printf("隊空，無隊頭元素!");return0;)else /*隊不為空*/(*x=Q->front->next->data;/*隊頭元素賦給變量 x*/return1;))voidShowQueue(LinkQueue*Q){ /*顯示隊中元素函數(shù)*/LinkListQ*p=Q->front->next;if(p==NULL)printf("隊列為空，無元素！")；else{printf("從隊列元素起棧中各元素為： ");while(p!=NULL){printf("%5d",p->data);p=p->next;)))voidMenuQueue(){ /*顯示菜單子函數(shù)*/printf("\n 隊列子系統(tǒng)");printf("\n=================================================");TOC\o"1-5"\h\zprintf("\n| 1 初始化隊列 |");printf("\n| 2 入隊操作 |");printf("\n| 3 出隊操作 |");printf("\n| 4 求隊頭元素 |");printf("\n| 5 顯示隊中所有元素 |");printf("\n| 0 返回 |");printf("\n=================================================");printf("\n請輸入菜單號(0-5):");linkqueue(){inti,n,flag;LinkQueue*Q;DataTypex;charch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){MenuQueue();scanf("%c",&ch2);getchar();switch(ch2){case'1':Q=InitQueue();printf("隊列的初始化完成！ ");break;case'2':printf("請輸入要入隊的元素個數(shù)： ");scanf("%d",&n);printf("請輸入％d個整數(shù)進行入隊：",n);for(i=0;i<n;i++){scanf("%d",&x);InQueue(Q,x);}TOC\o"1-5"\h\zprintf("入隊操作完成 ");break;case'3':printf("請輸入要出隊的元素個數(shù)： ");scanf("%d",&n);printf("出隊的元素順序依次為： ");for(i=0;i<n;i++){flag=DeQueue(Q,&x);printf("%5d",x);}if(flag==1)printf("\n出隊操作成功 !");elseprintf("\n出隊操作失??！ ");break;case'4':if(flag=GetFront(Q,&x))printf("當前的隊頭元素值為： %d",x);break;

case'5':ShowQueue(Q);break;case'0':ch1='n';break;default:printf("輸入有誤，請輸入 0-4進行選擇！ ");}if(ch2!='0'){printf("\n按回車鍵繼續(xù)，按任意鍵返回主菜單！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';}}}}intEmptyStack(LinkStack*S)/*棧子系統(tǒng) /*棧子系統(tǒng) */#include<stdio.h>#include<malloc.h>#defineMAXSIZE1000typedefintDataType;typedefstructstacknode{DataType data;structstacknode*next;}LinkStack;LinkStack*InitStack(){/*初始化鏈棧函數(shù) */LinkStack*S;S=NULL;returnS;/*初始化棧為空 */}/*數(shù)組最大長度為 100*//*定義DataType為int類型*//*鏈棧存儲類型 *//*定義結點的數(shù)據(jù)域 *//*定義結點的指針域 */{/*判斷棧空函數(shù) */if(S==NULL) /*棧為空*/return1;elsereturn0;}LinkStack*Push(LinkStack*S,DataTypex)TOC\o"1-5"\h\z{/*入棧函數(shù) */LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));/*生成新結點 */p->data=x; /*將x放入新結點的數(shù)據(jù)域*/p->next=S; /*將新結點插入鏈表表頭之前 */S=p; /*新結點作為棧頂 */returnS;/*返回棧頂 S*/}LinkStack*Pop(LinkStack*S,DataType*x){/*出棧函數(shù) */LinkStack*p;if(EmptyStack(S))/*調用判空函數(shù)EmptyStack(S),判斷棧是否為空*/{printf("\t?？?，不能出棧 !");returnNULL; /*?？詹荒艹鰲?*/}else /*棧不為空 */{*x=S->data; /*棧頂元素取出賦給 x*/p=S; /*p結點指向原棧頂 S*/S=S->next; /*原棧頂S指向其下一個結點*/free(p); /*釋放原棧頂空間 */returnS; /*返回棧頂 S*/}}intGetTop(LinkStack*S,DataType*x){/*獲取棧頂元素函數(shù) */if(EmptyStack(S))/*調用判空函數(shù)EmptyStack(S),判斷棧是否為空*/{printf("棧空!");return0;}else /*棧不為空 */{/*棧頂元素賦給變量 /*棧頂元素賦給變量 x*/return1;voidShowStack(LinkStack*S){LinkStack*p=S;if(p==NULL)printf("\t?？眨?);else{printf("從棧頂元素起棧中各元素為： ");while(p!=NULL){printf("%d",p->data);p=p->next;}}}voidD_B(LinkStack*S,DataTypex){while(x){TOC\o"1-5"\h\zS=Push(S,x%2);/*余數(shù)入棧 */x/=2; /*被除數(shù)data整除以 2，得到新的被除數(shù) */}printf("轉換后的二進制為： ");while(!EmptyStack(S)){S=Pop(S,&x);/*依次從棧中彈出每一個余數(shù)并輸出 */printf("%d",x);}}voidtrans(char*exp,char*postexp){ /*將中綴表達式轉換成后綴表達式函數(shù) */struct{chardata[MAXSIZE];inttop;}op;/*運算符棧 */inti=0;op.top=-1;while(*exp!='#')/*當表達式沒結束時 */{TOC\o"1-5"\h\zswitch(*exp)/*判斷表達式的每個字符 */{case'(': /*當字符為 '('時*/op.top++;op.data[op.top]=*exp;/*棧頂指針增 1，運算符入棧 */exp++;/*中綴表達式指針增 1*/break;case')': /*當字符為 ')'時*/while(op.data[op.top]!='(')/*只要運算符棧頂元素不是 '('時*/{postexp[i++]=op.data[op.top];/*將棧頂運算符寫入后綴表達式數(shù)組中*/op.top--; /*棧頂指針減 1*/}op.top--;exp++;/* 棧頂指針減 1，表達式指針加 1*/break;case'+':case'-':while(op.top!=-1&&op.data[op.top]!='(')/*運算符棧不為空且棧頂元素不為 '('時*/{postexp[i++]=op.data[op.top];/*將棧頂運算符寫入后綴表達式數(shù)組中*/op.top--; /*運算符棧頂指針減 1*/TOC\o"1-5"\h\z}op.top++;/*運算符棧頂指針加 1*/op.data[op.top]=*exp;/*將中綴表達式元素入符號棧 */exp++;/*中綴表達式指針加 1*/break;case'*':case'/':while(op.data[op.top]=='*'||op.data[op.top]=='/')/*當棧頂元素不是 '*'和'/'時*/{postexp[i++]=op.data[op.top];/*棧頂運算符寫到后綴表達式數(shù)組中*/op.top--; /*棧頂指針減 1*/TOC\o"1-5"\h\z}op.top++;/*棧頂指針加 1*/op.data[op.top]=*exp;/*中綴表達式的元素入棧 */exp++;/*表達式指針加 1*/break;case'':break;default:while(*exp>='0'&&*exp<='9')/*當表達式對象是數(shù)字 */postexp[i++]=*exp;/*將數(shù)字寫到后綴表達式數(shù)組中 */exp++;/*中綴指針加 1*/}postexp[i++]='#'; /*將每個操作數(shù)之間增加分隔符 '#'*/}}while(op.top!=-1)/*當運算符棧不為空時 */{postexp[i++]=op.data[op.top];/*將棧頂運算符寫入后綴表達式數(shù)組中*/op.toppostexp[i++]=op.data[op.top];/*將棧頂運算符寫入后綴表達式數(shù)組中*/op.top--;/*棧頂指針減 1*/}/*為后綴表達式加一個結束標志 /*為后綴表達式加一個結束標志 */}floatcompvalue(char*postexp){ /*根據(jù)后綴表達式求值函數(shù) */struct{floatdata[MAXSIZE];inttop;TOC\o"1-5"\h\z}st;/*數(shù)棧結點類型 */floata,b,c,d;st.top=-1;/*棧頂指針賦初值 -1*/while(*postexp!='\0')/*當后綴表達式沒結束時 */{switch(*postexp){a=st.data[st.top];/*st.topa=st.data[st.top];/*st.top--;b=st.data[st.top];/*st.top--;c=b+a;st.top++;st.data[st.top]=c;/*break;TOC\o"1-5"\h\z數(shù)棧頂元素賦給變量 a*//*棧頂指針減 1*/數(shù)棧頂元素賦給變量 b*//*棧頂指針減 1*//*將a加b的結果存入變量 c*//*棧頂指針加 1*/將變量c入棧*/case'-':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b-a;st.top++;}}st.data[st.top]=c;break;casea=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b*a;st.top++;st.data[st.top]=c;break;case'/':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;if(a!=0){c=b/a;st.top++;st.data[st.top]=c;}else{printf("\n\t除零錯誤 !\n");//exit(0);}break;default:/*后綴表達式的字符是數(shù)字字符時，將其轉換為整數(shù) */d=0;while(*postexp>='0'&&*postexp<='9'){d=10*d+*postexp-'0';postexp++;}st.top++;st.data[st.top]=d;/*將轉換之后的整數(shù)入棧 */break;}postexp++;}returnst.data[st.top];/*返回數(shù)棧的棧頂元素即為所求的結果 */voidMenuStack(){ /*顯示菜單子函數(shù)*/printf("\n 棧子系統(tǒng)");printf("\n=================================================");printf("\n|1—一初始化棧|");printf("\n|2——入棧操作|");printf("\n|3一出棧操作|");printf("\n|4—一求棧頂兀素|");printf("\n|5一顯示棧中兀素|");printf("\n|6十、二進制數(shù)轉換|");printf("\n|7—一表達式轉換并求值|");printf("\n|0一返回|");printf("\n=================================================");printf("\n請輸入菜單號(0-7):");}linkstack(){inti,n,flag;LinkStack*S;DataTypex;charch1,ch2,a;charexp[MAXSIZE],postexp[MAXSIZE];/*求表達式值的兩個數(shù)組*/ch1='y';while(ch1=='y'||ch1=='Y'){MenuStack();scanf("%c",&ch2);getchar();switch(ch2){case'1':S=InitStack();printf("棧的初始化完成！")；break;case'2':printf("請輸入要入棧的元素個數(shù)：");scanf("%d",&n);printf("請輸入％d個整數(shù)進行入棧：",n);for(i=0;i<n;i++){scanf("%d",&x);S=Push(S,x);}printf("入棧成功！");break;case'3':printf("請輸入要出棧的元素個數(shù)： ");scanf("%d",&n);printf("出棧的元素為： ");for(i=0;i<n;i++){S=Pop(S,&x);if(S!=NULL)printf("%5d",x);}break;case'4':if(flag=GetTop(S,&x))printf("當前的棧頂元素值為： %d",x);break;case'5':ShowStack(S);break;case'6':S=InitStack();TOC\o"1-5"\h\zprintf("請輸入十進制正整數(shù)為 :");scanf("%d",&x); /*輸入十進制正整數(shù) */D_B(S,x); /*調用進制轉換函數(shù) */break;case'7':printf("請輸入一個算術表達式(只有 +、-、*、/四種運算符) ，以'#'結束：");scanf("%s",&exp);trans(exp,postexp);printf("則該表達式的中綴表達式為： %s\n",exp);printf("轉換之后的后綴表達式為(每個操作數(shù)用“ #”分隔) ：%s\n",postexp);printf("表達式的值為 :%.2f\n",compvalue(postexp));break;case'0':ch1='n';break;default:printf("輸入有誤，請輸入 0-5進行選擇！ ");}if(ch2!='0'){printf("\n按回車鍵繼續(xù)，按任意鍵返回主菜單！ \n");a=getchar();if(a!='\xA'){getchar();ch1='n';/*數(shù)據(jù)結構實驗系統(tǒng)主函數(shù) */#include"linklist.h"#include"linkstack.h"#include"linkqueue.h#include"string.h"#include"btree.h"#include"graph.h"#include"search.h"#include"sort.h"main(){intchoice;charch;ch='y';while(ch=='y'||ch=='Y'){printf("\n");數(shù)據(jù)結構實驗系統(tǒng)主菜單");數(shù)據(jù)結構實驗系統(tǒng)主菜單");printf("\n==================================================");printf("\n|1—一線性表|");printf("\n|2—棧|");printf("\n|3一隊列|");printf("\n|4—串|");printf("\n|5二叉樹|");printf("\n|6圖|");printf("\n|7——查找|");printf("\n|8一排序|");printf("\n|0退出|");printf("\n==================================================");printf("\n請選擇菜單號(0-8):");scanf("%d",&choice);getchar();switch(choice){case1:linklist();break;case2:linkstack();break;case3:linkqueue();break;case4:string();break;case5:btree();break;case6:graph();break;case7:search();break;case8:sort();break;case0:ch='n';break;default:printf("菜單選擇錯誤！請重新選擇 ");}}}#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefintKeyType;typedefstruct{KeyTypekey;}SearchL;/*順序表的表長 *//*關鍵字類型為 int型*//*存放關鍵字， KeyType為關鍵字類型 */intSeqSearch(SearchLr[],intn,KeyTypek){/*順序查找算法函數(shù)，表中元素下標為 1到n*/inti=n;r[0].key=k; /*設元素r[o]為要查找的關鍵字 k(即監(jiān)視哨)*/while(r[i].key!=k) /*從后向前順序比較 */i--;return(i); /*返回查找元素下標，當為 0時表示查找失敗 */}intBinSearch(SearchLr[],intn,KeyTypek){/*折半查找算法函數(shù)，表中元素下標為 1到n*/intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(k==r[mid].key)return(mid);elseif(k<r[mid].key)/*置區(qū)間初值 *//*查找區(qū)間不為空時 *//*找到待查元素 */high=mid-1;/*未找到，繼續(xù)在前半區(qū)間進行查找 */elseTOC\o"1-5"\h\zlow=mid+1; /*未找到，繼續(xù)在后半區(qū)間進行查找 */}return(0);}typedefstruct /*分塊查找的索引表類型 */{KeyTypekey; /*關鍵字*/intlow,high; /*每塊的低、高地址 */}IdxType;voidCreatIdx(SearchLr[],IdxTypeidx[],intm,intn){ /*分塊查找的建立索引表算法函數(shù) */inti,j,k=0; /*k為索引表下標 */KeyTypemax;for(i=0;i<m;i+=n) /*在順序表中進行分塊 */{max=r[i].key;/*將最大值設為第 i個元素關鍵字 */for(j=i+1;j<i+n&&j<m;j++)/*在每塊中確定該塊的最大值 */if(r[j].key>max)max=r[j].key;idx[k].key=max; /*將該塊最大值賦給索引表第 k個元素的關鍵字*/idx[k].low=i; /*將該塊起始下標 i賦給索引表第 k個元素的低地址 */if(i+n-1<=m-1) /*若該塊長度為 m時*/idx[k].high=i+n-1;/*將該塊終止下標值賦給索引表第 k個元素的高地址 */else /*若該塊長度為小于 m值(最后一塊)時 */idx[k].high=m-1;/*將順序表最大元素下標值賦給該索引表第 k個元素的高地址*/k++; /*索引表下票值加 1*/}}intBlkSearch(SearchLr[],IdxTypeidx[],intm,KeyTypek){/*分塊查找算法函數(shù) */intlow,high,mid,i,j,find=0;i=0;while(idx[i].key<k)/*當索引表的關鍵字小于查找關鍵字 k時，在索引表中定位 */i++;low=idx[i].low;high=idx[i].high;while(low<=high&&!find)/*當在索引表中找到該元素所在塊時 */{/*在該索引表內進行折半查找 */mid=(low+high)/2;if(k<idx[mid].key)high=mid-1;elseif(k>idx[mid].key)low=mid+1;else{high=mid-1;find=1;}}TOC\o"1-5"\h\zif(low<m)/*當在索引表中有該元素所在塊時 */{i=idx[low].low; /*i賦為索引表該塊的低地址 */j=idx[low].high; /*j賦為索引表該塊的高地址 */}*/while(i<j&&r[i].key!=k)/*在順序表的這個塊內進行順序查找*/i++;if(i>=j)return(-1);/*當沒找到時返回 -1*/elsereturn(i);/*當找到時返回下標值 i*/}typedefstructtreenode/*二叉排序樹的結點類型 */{KeyTypekey; /*關鍵字*/structtreenode*lchild,*rchild;/*左、右孩子指針 */}BTNode;voidDispBStree(BTNode*bt){/*用廣義表顯示二叉排序樹函數(shù) */if(bt!=NULL){printf("%d",bt->key);/*輸出根結點的關鍵字 */if(bt->lchild!=NULL||bt->rchild!=NULL){/*當根結點的左、右孩子指針不為空時 */printf("(");/*輸出左括號 */DispBStree(bt->lchild);/*輸出該結點的左孩子 */if(bt->rchild!=NULL)/*若其右指針不為空時 */printf(",");/*輸出逗號 */DispBStree(bt->rchild);/*輸出該結點的右孩子 */printf(")"); /*輸出右括號 */}}}BTNode*BSTInsert(BTNode*bt,KeyTypek){/*二叉排序樹的元素插入函數(shù) */TOC\o"1-5"\h\zBTNode*f,*p=bt; /*p指針指向二叉排序樹的根結點 */*/while(p!=NULL) /*當p指針不為空時，由指針f確定插入位置的雙親結點*/{f=p； /*指針f指向指針p所指結點*/if(p->key>k)/*當p所指結點的關鍵字大于插入值時 */p=p->lchild;/*p 移到它的左孩子結點上 */elsep=p->rchild;/*p 移到它的右孩子結點上 */}p=(BTNode*)malloc(sizeof(BTNode));/*建立新結點 */p->key=k; /*將關鍵字 k存入新結點的數(shù)據(jù)域 */p->lchild=p->rchild=NULL;/*左、右孩子指針設為空 */if(bt==NULL)/*二叉樹為空樹時 */bt=p; /*新建結點作為二叉排序樹的根結點 */elseif(k<f->key)/*若插入關鍵字 k小于其雙親結點關鍵字 */f->lchild=p; /*則插入為雙親結點的左孩子 */elsef->rchild=p; /*則插入為雙親結點的右孩子 */return(bt);}BTNode*CreateBST(KeyTypestr[],intn){/*建立二叉排序樹函數(shù) */inti=0;BTNode*bt=NULL;/*初始化根結點為空 */while(i<n) /*當建立沒結束時 */{bt=BSTInsert(bt,str[i]);/*將第i個元素插入到二叉排序樹中 */i++;}return(bt); /*返回根結點指針 */}BTNode*BSTDelete(BTNode*bt,KeyTypek){ /*在二叉排序樹 t中刪除關鍵字為 k的節(jié)點函數(shù) */BTNode*p,*f,*s,*q;p=bt;f=NULL;while(p)/*查找關鍵字為 k的待刪結點 p*/{if(p->key==k)break; /*找到，則跳出查找循環(huán) */f=p; /*f指向p結點的雙親結點 */if(p->key>k)p=p->lchild;elsep=p->rchild;

if(p==NULL)returnbt;if(p->lchild==NULL){if(f==NULL)bt=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;else/*p是if(p==NULL)returnbt;if(p->lchild==NULL){if(f==NULL)bt=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;else/*p是f的右孩子 */f->rchild=p->rchild;/*free(p);}else/*p有左子樹 */{q=p;s=p->lchild;while(s->rchild)/*p無左子樹 *//*p是原二叉排序樹的根 *//*p是f的左孩子 *//*將p的右子樹鏈到 f的左鏈上 */將p的右子樹鏈到 f的右鏈上 *//*釋放被刪除的節(jié)點 p*//*在p/*在p的左子樹中查找最右下結點 */if(q==p)q->lchild=s->lchild;/*將s的左子樹鏈到 q左孩子指針*/elseq->rchild=s->lchild;p->key=s->key; /*將s的值賦給 p*/free(s);}returnbt;BTNode*BSTSearch(BTNode*bt,KeyTypek)TOC\o"1-5"\h\z{/*二叉排序樹的元素查找函數(shù) */if(bt==NULL)return(NULL);/*空樹則返回空指針 */else{if(k==bt->key)/*關鍵字k等于根結點關鍵字*/return(bt);/*返回根結點指針 */elseif(k<bt->key)/*關鍵字k小于根結點關鍵字 */return(BSTSearch(bt->lchild,k));/*到根結點的左子樹查找 */elsereturn(BSTSearch(bt->rchild,k));/*到根結點的右子樹查找 */}}voidMenuBTree(){ /*顯示二叉排序樹子菜單函數(shù) */printf("\n 二叉排序樹 ");printf("\n==================================================");printf("\n| 1 建立二叉排序樹 |");printf("\n| 2 插入一個元素 |");printf("\n| 3 刪除一個元素 |");printf("\n| 4 查找一個元素 |");

printf("\n|返回|");printf("\n|返回|");printf("\n==================================================");printf("\n請輸入序號( 0-4)選擇要進行的操作 :");}voidBTFun(){/*二叉排序樹子函數(shù) */KeyTypestr[100];BTNode*bt;inti,n,x,menux;MenuBTree();scanf("%d",&menux);do{TOC\o"1-5"\h\zswitch(menux) /*判斷進行何種操作 */{/*建立二叉排序樹 */printf("請輸入要生成二叉排序樹的關鍵字的個數(shù) :");scanf("%d",&n);printf("請輸入二叉排序樹的各個關鍵字 :");for(i=0;i<n;i++)scanf("%d",&str[i]);bt=CreateBST(str,n);printf("建立的二叉排序樹廣義表表示法為 :");DispBStree(bt);break;/*在二叉排序樹中插入一個元素 */printf("請輸入要插入的元素值 :");scanf("%d",&x);bt=BSTInsert(bt,x);printf("插入后的二叉排序樹為 :");DispBStree(bt);break;/*在二叉排序樹中刪除一個元素 */printf("請輸入要刪除的元素 :");scanf("%d",&x);bt=BSTDelete(bt,x);printf("刪除元素％d后的二叉排序樹為：”,x);DispBStree(bt);break;case4： /*在二叉排序樹中查找某元素 */printf("請輸入查找的元素值 ：");scanf("%d",&x);if((BSTSearch(bt,x))!=NULL)printf("在二叉排序樹中存在元素 %d!",x);elseprintf("在二叉排序樹中不存在元素 %d!",x);break;case0:return;break;default:printf("輸入選項錯誤，請重新輸入(0-4)!");}MenuBTree();scanf("%d",&menux);}while(1);}voidMenu(){ /*顯示菜單子函數(shù)*/printf("\n 查找子系統(tǒng)");printf("\n==================================================");printf("\n|1—一順序查找|");printf("\n|2—一折半查找|");printf("\n|3一分塊查找|");printf("\n|4—一二叉樹排序樹查找|");printf("\n|0一返回|");printf("\n==================================================");printf("\n請輸入菜單號(0-4):");}voidsearch(){SearchLr[MAXSIZE];IdxTypeidx[MAXSIZE];inti,m,n,x,k,address;charch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){Menu();scanf("%c",&ch2);getchar();switch(ch2){

case'1':printf("請輸入表的元素個數(shù) (0-%d):",MAXSIZE-1);scanf("%d",&n);printf("請輸入％dj表中的關鍵字(整數(shù)):",n);for(i=1;i<=n;i++)scanf("%d",&r[i].key);printf("請輸入要查找的關鍵字 :");scanf("%d",&x);if((address=SeqSearch(r,n,x))!=0)printf("