1、# include<stdio.h> #include<iostream.h> #include<stdlib.h> #define MAX 100 struct node char data;struct node *next;int ishs(struct node *head,int n) char stackMAX/2; struct node *p=head;int top=0; while(top<n/2) stacktop=p->data; top+;p=p->next; if(n%2=1)p=p->next; top-

2、; while(p!=NULL&&top>=0&&p->data=stacktop) top-;p=p->next; if(top=-1&&p=NULL) return(1);else return(0); void main() char sMAX;struct node *head=NULL,*p,*q; int i=0;cout«"輸入一個回文數："<<e ndl;scanf("%s",s);while(si!='0') p=new node;p

3、->data=si;p->next=head;head=p;i+;if(ishs(head ,i)printf("%s 是回文數 n",s);else printf("%s 不是回文數 n",s); 目錄一、?順序表根本操作的實現?實驗二、?順序表?實驗 學生成績治理三、?鏈表的應用?實驗 求兩個一元多項式之和四、?鏈表的應用?實驗五、?棧的應用?實驗 判斷一個數是否是回文數六、?隊列的應用?實驗 利用隊列解決分油問題七、?串的應用?實驗 求兩個串的最長公共子串八、?二叉樹的應用?實驗 設計一個表示家譜的二叉樹九、?二叉樹的應用?實驗 借助二

4、叉樹實現排序十、?二叉樹的三種遍歷?實驗一 十一、?二叉樹的三種遍歷?實驗二 十二、?圖?實驗一十三、?圖?實驗二 十四、?圖的應用?實驗 最小生成樹十五、?快速排序的設計?實驗 十六、?哈希表查找設計?實驗一、?順序表根本操作的實現?實驗練習實驗一實驗目的1、掌握用 Visual C+ 6.0 上機調試線性表的根本方法.2、掌握線性表的根本操作, 插入、刪除及查找等運算在順序存儲結構上的運算.二實驗內容與要求 掌握線性表在順序存儲結構上的根本操作,插入、刪除及查找等運算.三算法*定義一個線性表的順序存儲類型：#define MAX 50typedefchar或 int 類型等elemtype

5、;struct listelemtype listMAX;int size;注意：在后面的算法中,成員 list 數組的下標是從 0 開始,而 順序表結點編號是從 1 開始的,因此進行它們之間的轉換 要小心.1. 置空表運算void setnul(struct list *p )p->size=0; 2. 求順序表長度運算int length(struct list *p)return (p->size);3. 取順序表中第 i 個結點運算elemtype get(struct list *p,int i) if(i<1&&i<p->size)pr

6、intf( “位置參數不正確 n); else return(p->listi-1);4. 按值查找：int locate(struct list *p,elemtype x)int i=0;while (i<p->size&&p->listi!=x)i+;if(i=p->size)return(-1);else return(i+1);5插入結點：該操作在順序表 list 的第 i 個位置上插入新結點 X viod insert(struct list *p,elemtype x,int i) int j;if(i<1&&i

7、<p->size+1)printf( “位置參數不正確,不能進行插入操作 )； elsep->size+;for(j=p->size-1;j>=i;j-)p->listj=p->listj-1;p->listj=x;6、刪除結點該操作刪除順序表 list 的第 i 個結點.viod delete(struct list *p,int i) int j;if(i<1|i>p->size)printf “位置參數不正確,不能進行刪除操作 ；else for(j=;j<p->size-1;j+)p->listj=p-

8、>listj+1;p->size-;7、顯示順序表：void display(struct list *p)int j;if(p->size=0)printf( “該順序表為空,不能顯示 )；elseprintf( “順序表： )；if(p->size=1)printf( “%c,p->listp->size);else /*有一個以上結點 */for(j=0;j<p->size-1;j+)printf( “%c> ,p->listj); printf( “%c,p->listj);printf( “n);8、當順序表的根本操作

9、設計好后,給出調用這些根本操作函數： void main()struct list q;setnull(&q);insert(&q, 'a',1);insert(&q, 'b',2);insert(&q, 'a',1);insert(&q, 'c',2);insert(&q, 'd',1);insert(&q, 'e',2);display(&q);printf( “值： %c 位置： %dn,'a',locate(&a

10、mp;q,'a');printf( “位置： %d 值： %cn,4,get(&q,4);printf( “刪除第 2 個結點后順序表： )； delete(&q,2);display(&q);printf( “刪除第 2 個結點后順序表： )； delete(&q,2);display(&q);printf( “刪除第 1 個結點后順序表： )；delete(&q,1);display(&q);printf( “刪除第 1 個結點后順序表： )； delete(&q,1);display(&q);9、本程

11、序的執行結果如下：順序表： d e a c a b值：a位置：3位置： 4 值： c刪除第 2 個結點后順序表： d a c a b 刪除第 2 個結點后順序表 : d c a b 刪除第 1 個結點后順序表 : c a b 刪除第 1 個結點后順序表 : a b四)分析程序寫出小結、體會.二、?順序表應用?實驗一 學生成績治理一實驗目的3、 掌握用 Visual C+ 6.0 上機調試線性表的根本方法.4、掌握線性表的根本操作, 插入、刪除及查找等運算在順序存儲結構上的運 算.二實驗內容與要求1、問題描述學生成績治理是學校教務治理的重要局部,其處理的信息量很大.本實驗對 學生的成績治理做一個

12、簡單的模擬,用菜單項選擇擇操作方式完成以下功能： *登記學生成績*插入學生成績*刪除學生成績2、算法輸入3、操作要求：學生信息.5、算法要點： 此問題可看成對線性表的操作. 將學生成績組織成順序表, 那么 登記學生成績既即是建立順序表操作, 查詢學生成績、 插入學生成績和刪 除學生成績即是建立在順序表中進行查找、插入和刪除操作.三算法1、數據類型定義學生成績存儲結構定義為：#define MAXNUM 100struct studentint number;char name10;int score;struct lstudentstudent sMAXNUM;int length;2、操作算

13、法( 1) 登記成績算法void create(struct lstudent *ls)int n,i;cout<<n 請輸入學生人數： ；cin>>n;ls->length=n;for(i=0;i<n;i+)printf( “n 請輸入學生 %d 的數據： n,i+);cout<<n 學號： ；cin>>ls->si.number; 或 scanf(“%d,&ls->si.number);cout<<n 姓名： ；scanf(“%s,ls->);cout<<n 成績 :

14、;scanf(“%d,&ls->si.score);( 2)查詢成績算法： void find(struct lstudent *ls) 請同學們自己完成 ( 3)插入成績算法 : void insert(struct lstudent *ls)請同學們自己完成 根據輸入插入學生數 N 將記錄插入表尾( 4)刪除成績算法 : void del(struct lstudent *ls) 請同學們自己完成 根據輸入要刪除成績學生號 X 將該記錄刪除3、程序#in cludeviostream.h #in clude<sdtio.h>#include<sdlib.h&

15、gt;#define MAXNUM 100struct studentint number;char name10;int score;struct lstudentstudent sMAXNUM;int length;void main( ) struct lstudent *ls;ls=new lstudent;int k;cout<<n cout<<學生成績治理ncout<<n cout<<1、登記成績n;cout<<2、查詢成績n;cout<<3、插入成績n;cout<<4、刪除程序n;cout<

16、<0、退出程序n;coutn;while( 1 )coutn 請輸入選擇的功能號： n;cin>>k;switch(k)case 1:create(ls);break;case 2:find(ls);break;case 3:insert(ls);break;case 4 :del(ls);break;case 0:return;default:cout<< 選擇錯誤！ ;(四) 測試數據1、登記成績數據學生數據：學號姓名分數1王紅772李平853張軍762、插入成績數據插入學生數：2插入學生數據：學號姓名分數5王小紅798陳紅953、程序運行結果程序運行后顯示菜

17、單：學生成績治理1、登記成績2、查詢成績3、插入成績4、刪除程序0、退出程序 請輸入選擇的功能號： 在菜單的提示下做如下操作： 1 選擇功能項 1；登記成績.可按測試數據輸入,或自擬. 2 選擇功能項 2；查詢成績.輸入學號 2,顯示如下：學號姓名分數2李平85 3選擇功能項 3；插入成績.輸入待插入的人數及插入學生的信息. 4選擇功能項 4；輸入學號 2,顯示：己刪除！ 5在做插入或刪除操作后,應隨時選擇功能 2 查看操作是否成功4、小結、體會.三、?鏈表的應用一?實驗二 求兩個一元多項式之和或P70頁實習題1題一實驗目的 掌握單鏈表的各種根本操作,包括單鏈表的建立和查找.二實驗內容與要求1

18、 、用單鏈表存儲一元多項式,將兩個存儲一元多項式的單鏈表相加產生結果 單鏈表.2、假設要求用戶按冪從大到小次序輸入各結點,并且沒有兩個結點具有相 同冪,這樣一個一元多項式的鏈表是按冪 expn 從大到小順序排列的.將這 兩個有序單鏈表pa和pb按幕expn值相加得到一個新的有序單鏈表.三算法1 、數據類型定義結點存儲結構定義為：struct polynodeint coef;系數int expn;冪struct polynode *next;2、操作算法1建立單鏈表算法struct polynode *create int a,n,i=1;struct polynode *head,*s,*p

19、;coutvv輸入一元多項式(以0, 0標志結束)：n；coutvv要求：1.按幕從大到小次序輸入各結點n；cout<<2.沒有兩個結點具有相同的冪 n；head=new polynode；head->next=NULL；p=head；doprintf(第%d 次->系數,幕：,i+);scanf(“%d,%d,&a,&n)；if(a!=0|n!=0)s=new polynode；s->coef=a； s->expn=n；s->next=NULL；p->next=s； p=s；while(a!=0|n!=0)；cout<&l

20、t;n；return(head)；顯示由head指向的一個一元多項式算法void display(struct polynode *head) 同學們自己寫 ( 3) 兩個一元多項式相加算法struct polynode *addpoly(struct polynode *pa, struct polynode *pb) int n；struct polynode *pc,*s,*p；pa=pa->next； pb=pb->next；pc=new polynode； pc->next=NULL； p=pc；while(pa!=NULL&&pb!=NULL)同學

21、們自己寫.return(pc);(4)主函數main( ) struct polynode *poly1,*poly2,*poly3;coutvv建立第一個一元多項式=>n;poly1=create( );cout«建立第二個一元多項式=>n;poly2=create( );poly3=addpoly(poly1,poly2);coutvv第一個一元多項式為：n；display(poly1);coutvv第二個一元多項式為：n；display(poly2)；coutvv相加后一元多項式為：n；display(poly3)；(四) 調試程序并給出實驗結果1、給出兩個一元多項

22、式：323x3+2x2-5x+632-2x3-2x2+5x+42、請同學們寫出程序執行過程和顯示結果并分析程序3、小結、體會.四、?鏈表的應用二?實驗三一實驗目的 掌握單鏈表的各種根本操作,包括單鏈表的建立和查找.二實驗內容與要求1、設計一個算法,將以單鏈表作存儲結構實現線性表的就地逆置,即在原來 的存儲空間中將線性表ai,a2,a3,an逆置為&,an-i,an-2,.ai.2、設計一個算法,采用單鏈表作存儲結構,實現將X 插入到一個有序從小到大排序的線性表的適當位置上,并保持線性表有序性.三算法同學們自己寫 要求：1、寫出完整的程序：建立單鏈表算法、顯示單鏈表算法、操作算法、主 函

23、數.2、調試程序并寫出程序執行過程3、分析程序并小結、體會.五、?棧的應用?實驗四 判斷一個數是否是回文數一實驗目的 掌握棧的特點即先進后出的原那么及其根本操作,包括入棧、退棧與棧空判斷 等.二實驗內容與要求1、將用戶輸入的數以單鏈表方式存儲.2、問題描述 從頭掃描該單鏈表,將前面的一半元素入棧,假設元素總個數 為奇數,那么跳過中間的哪個元素,然后開始循環：邊退棧邊在單 鏈表中后移指針,假設當前棧頂元素與單鏈表中當前結點的值域不 相等,那么推出循環.最后如果棧空且鏈表比擬完畢,那么是回文數, 否那么不是回文數.三算法1、數據類型定義 結點存儲結構定義為： struct node char da

24、ta;struct node *next;2、操作算法(1) 輸入一個回文數,建立字符串的單鏈表算法(2) 判斷是否是回文數算法. int ishs(struct node *head,int n) char stackMAXCHAR/2;struct node *p=head;int top=0;.同學們補充完整 3、主函數 main( ) char sMAXCHAR;struct node *head=NULL,*p,*q;int i=0;coutvv輸入一個回文數：；scanf(“%s,s);while(si!= '0') 建立字符串的單鏈表,請同學們自己寫. . if(

25、ishs(head ,i)pri ntf( s 是回文數 n,s);else printf(s不是回文數 n,s);(四) 調試程序并給出實驗結果1、判別兩個數 1234567890987654321和 123456789是否是回文數.2、程序執行過程如下：請同學們給出.3、分析程序并小結、體會.六、?隊列的應用?實驗五實驗目的1、掌握隊列的順序存儲結構和鏈式存儲結構,以便在實際背景下靈活運用.2、掌握隊列的特點,即先進先出的原那么.3、掌握隊列的根本運算,如入隊與出隊等運算在順序存儲結構和鏈式存儲結構上的實現.二實驗內容與要求1、建立順序存儲循環隊列,輸入 N 個整型數據,編寫與此結構相應的

26、入隊與 出隊算法,編寫計算隊列長度算法并顯示該隊列.2、假設以帶頭結點的循環鏈表表示隊列,并且只設一個指向隊尾元素結點, 建立順序鏈式存儲循環隊列,輸入 N 個字符型數據,編寫相應的隊列入隊和出 隊的算法,并顯示該隊列.3、程序運行結果：請同學們寫出.4、分析程序并小結、體會七、?串的應用?實驗 -六 求兩個串的最長公共子串一實驗目的 掌握順序串的根本操作.二實驗內容與要求1、采用順序存儲結構用戶輸入的兩個串,輸出這兩個串的最長公共子串2、問題描述先給最長公共子串的下標 index 和長度 maxlen 均賦值為 0.設s=aoaia/,t= bobibm,掃描串s,對于當前字符a,掃描t,

27、假設bj=a,計算它們其后相同字符的個數,并賦給leng假設leng>maxlen,說明它是當前最長公共子串,那么index=i,然后繼續掃描t,直到t完畢.當t完畢后,又繼續 掃描s,直到s完畢.這樣s串中從index開始的 maxlen個字符構成的串便是 最長子串.三算法1、數據類型定義struct strchar vecMAXCHAR;int len;2、操作算法(1) 找最長公共子串算法void maxcomstr(struct str *s, struct str *t) 補充完整,s->vec,t->vec)；printf( n字符串s'和's&#

28、39;的最長公共子串: for(i=0;i<maxlen;i+)printf( “%c,s->vecindex+i); (2)主函數 main( )3、程序#include<stdio.h> #include< iostream.h > #include<string.h.> #define MAXCHAR 30struct strchar vecMAXCHAR;int len; 找最長公共子串算法 void main( ) struct str *r,*r1;r=new str; r1= new str;coutvv輸入第一個字符串：； san

29、f(“%s,r->vec);r->len=strlen(r->vec)； coutvv輸入第二個字符串：； sanf(“%s,r1->vec)； r1->len=strlen(r1->vec)； maxcomstr(r,r1)；(二) 實驗結果1、求兩個串ababcabcdabcde和Xyabcdxy的最長公共子串2、程序執行過程：請同學們寫出3、分析程序并給出小結、體會.八、?二叉樹的三種遍歷?實驗七一實驗目的1 、掌握鏈式存儲方式下二叉樹結點數據結構.2、掌握前序二叉樹的創立二叉樹算法.3、掌握二叉樹前序遍歷、中序遍歷、后序遍歷的遞歸算法.二實驗內容與要

30、求1 、問題描述 1 采用鏈式存儲方式,動態指針變量方法建立一棵給定的二叉樹同學自 己給定,根據其前序遍歷的順序輸入結點值,遍歷過程遇到空子樹時,必須使 用#代替.2二叉樹前序遍歷、中序遍歷、后序遍歷的遞歸算法實現.三操作算法1 、數據類型定義struct nodechar data;struct node *lchild,*rchild;2、操作算法前序遍歷的順序輸入結點值建立二叉樹以代替空子樹算法struct node *set補充完整前序遍歷遞歸算法void perorder(struct node *p) 同學自己寫 中序遍歷遞歸算法void inorder(struct node *

31、p) 同學自己寫 后序遍歷遞歸算法void postorder(struct node *p) 同學自己寫 按樹狀打印二叉樹算法Void display(struct node *p,int n) 補充完整3、完整的算法#include<stdio.h>#include< iostream.h >struct nodechar data;struct node *lchild,*rchild;前序遍歷的順序輸入結點值建立二叉樹(以 代替空子樹)算法 前序遍歷遞歸算法中序遍歷遞歸算法后序遍歷遞歸算法 按樹狀打印二叉樹算法 void main()struct node *b

32、; int x;cout<<" 輸入字符 :"<<endl;b=set();perorder(b);inrorder(b);postorder(b);cin>>x;displayb,x四實驗結果1、畫出一棵二叉樹并采用前序遍歷的順序輸入結點值.2、測試數據： ABDEFGC<CR>寫出程序運行的結果 :測試數據： abcdefg<CR> 寫出程序運行的結果并畫出該二叉樹 : 測試數據： abdefgc<CR> 寫出程序運行的結果并畫出該二叉樹 :3、小結、體會.九?二叉樹的應用一?實驗八 設計一個表示家

33、譜的二叉樹一實驗目的1、進一步掌握指針變量、動態變量的含義.2、掌握二叉樹的結構特征,以及各種存儲結構的特點及適應范圍.3、掌握用指針類型描述、訪問和處理二叉樹的運算.二實驗內容與要求1、問題描述采用一棵鏈式存儲結構二叉樹表示一個家譜關系, 對于給定的父親顯示所有的 兒子.由于家譜為樹形,但不是一棵二叉樹, 所以在存儲時要轉換二叉樹形式. 規定： 一個父親結點的左子樹根結點表示母親結點, 母親結點的右子樹表示他們的所有 兒子.這樣就將家譜樹轉換成二叉樹了,對于二叉樹的操作是比擬容易實現的.三算法1、數據類型定義struct treenodechar name10;struct treenode

34、 *left,*right;2、操作算法(1) 建立家譜二叉樹(以 #結尾)算法struct treenode *craetree()int contin=1;int first=1;/int n;int m;int i;char xm10;struct treenode *btree,*s,*t,*p;cout«endlvv"建立一個家譜二叉樹(以#結尾)：n"«endl; while(contin)if(first=1)btree=new treenode;coutvv"姓名："cin>>btree->name;

35、 btree->right=NULL;s=new treenode;coutvv"妻子："；cin>>s->name; s->right=s->left=NULL; btree->left=s; first=0;else coutvv"父親："cin>>xm; 或 gets(xm);或 /scanf("%s",&xm);if(strcmp(xm,"#")=0)contin=0; else p=findfather(btree,xm);if(p!=NULL

36、)p=p->left; if(p=NULL)coutvv"不能有兒子,由于沒有妻子"<<endl;else while(p->right!=NULL)p=p->right; s=new treenode; s->right=NULL; p->right=s;coutvv"兒子："cin>>s->name;/gets(s->name); coutvv"兒妻："cin>>xm; if(strcmp(xm," ")!=0)t=new treen

37、ode;strcpy(t->name,xm); t->left=t->right=NULL;s->left=t;else s->left=NULL;else cout<<" 不存在這樣的父親結點！ "<<endl;return(btree);(2) 找父親結點算法struct treenode *findfather(struct treenode *p,char xm) 補充完整 (3) 顯示家譜凹入表示法算法void disptree(struct treenode *bt) struct treenode *sta

38、ckMAXSIZE,*p;int levelMAXSIZE2,top,n,i,width=4;if(bt!=NULL)cout<<" 家譜凹入表示法 "<<endl;top=1;stacktop=bt;leveltop0=width; while(top>0)p=stacktop;n=leveltop0;for(i=1;i<=n;i+) printf(" "); printf("%6s",p->name);for(i=n+1;i<=MAXWIDTH-6;i+=2) printf(&quo

39、t;-"); printf("n"); top-;if(p->right!=NULL)top+;stacktop=p->right;leveltop0=n+width;leveltop1=2;if(p->left!=NULL) top+; stacktop=p->left; leveltop0=n+width; leveltop1=2;(4) 查找指定父親的所有兒子算法void findson(struct treenode *bt) 補充完整 3、完整算法#include<stdio.h>#include< iostre

40、am.h >#include<string.h.>#define MAXSIZE 30#define MAXWIDTH 40struct treenodechar name10;struct treenode *left,*right;找父親結點算法建立家譜二叉樹算法顯示家譜凹入表示法算法 查找指定父親的所有兒子算法 void main( ) struct treenode *bt;bt=creatree( );disptree(bt);findson(bt);6、 實驗結果1) 畫出一個家譜關系樹并轉換為二叉樹.2) 輸入家譜關系樹元素并查找“張德所有兒子. (設有父親張德

41、) 測試數據 姓名：張德 CR 妻子：陳氏 CR 父親：張德 CR 兒子：張文 CR 兒妻：劉氏 CR 父親：張德 CR 兒子：張武 CR 兒妻：王氏 CR 父親：張文 CR 兒子：張兵 CR 兒妻：李氏 CR 父親：張文 CR 兒子：張強 CR兒妻：CR父親：張武 CR兒子：張華 CR兒妻： CR父親： # CR3) 調試程序并寫出運算過程、畫出樹形結構、小結、體會.十、?二叉樹的應用二?實驗九 借助二叉樹實現排序一實驗目的1、進一步掌握指針變量、動態變量的含義.2、掌握二叉樹的結構特征,以及各種存儲結構的特點及適應范圍.3、掌握用指針類型描述、訪問和處理二叉樹的運算.二實驗內容與要求1、問

42、題描述1對于給定的 N 個關鍵字值,采用二叉排序樹方法對其進行排序.2算法輸入： N 個關鍵值.3算法輸出：排序結果.4算法要點：采用建立二叉排序樹的方法,將N 個關鍵值為結點值,生成一棵二叉排序樹.對生成的二叉排序樹進行中序遍歷,得到遞增序列.三算法1、數據類型定義struct treenodeint data;struct treenode *lchild,*rchild;2、操作算法二叉排序樹的插入算法 在二叉排序樹上插入關鍵值為 K 的結點,假設二叉樹為空, 那么插入結點 為新結點,否那么根據 K 的大小插入到 *t 的左子樹(或右子樹)中. struct treenode *inse

43、rt(struct treenode *t, int x) 補充完整 建立二叉排序樹算法struct treenode *create( ) struct treenode *t;int x; t=NULL;coutvv輸入一組正整數(以-1作為結束標志)：<<endl; .補充完 中序遍歷二叉排序樹算法void inorder(struct treenode *t) 同學們自己編寫 3、完整算法#include<stdio.h>#include< iostream.h >#include<stdlib.h.>#define NULL 0stru

44、ct treenode int data;struct treenode *lchild,*rchild;算法清單void main( )struct treenode *root; root= create( );cout« 排序結果： <<e ndl;inorder(root);4、測試數據輸入 3 9 2 8 5 6 1-1注意：為了防止出現單枝樹,不要輸入有序序列5、寫出程序運行結果并畫出該二叉排序樹、小結、體會.十一、?二叉樹的靜態鏈表?實驗一實驗目的1、掌握靜態二叉鏈式存儲方式下二叉樹結點數據結構.2、掌握后序二叉樹的創立和擴展后序序列輸入創立二叉樹算法.3、

45、掌握二叉樹前序遍歷、中序遍歷、后序遍歷的遞歸算法.二實驗內容與要求1、問題描述1采用鏈式存儲方式,靜態指針變量方法建立一棵給定的二叉樹同學自 己給定,根據擴展后序序列輸入結點值,遍歷過程遇到空子樹時,必須使用 # 代替.根本思想：讀入擴展后序序列,從左往右檢測每一個符號,如果是#,那么將空地址壓入棧中； 如果是字母, 那么首先為新結點分配存儲空間, 將讀入的字母 存入新結點的數值字段中； 然后從棧頂彈出兩個元素, 分別作為新結點的右孩子 指針和左孩子指針,最后將新結點壓入棧中.2二叉樹前序遍歷、中序遍歷、后序遍歷的遞歸算法實現.三操作算法1、數據類型定義struct nodechar data

46、;itn lchild, rchild;struct node treeN+1;int root;2、操作算法( 1)“擴展后序序列“插入表示空子樹(以 #代替空子樹) ( 以 表示結束 )的符 號值建立二叉樹算法int settree( )int sN+1;int t=0,i=0;char c;coutvv請輸入結點值(以#代替空子樹,以表示結束)：vvendl;cin>>c;while(c!= '')if(c= '#')s+t=0;elsei+;treei.data=c;treei.rchild=st; treei.lchild=st-1;st-

47、1=i;t-;cin>>c;return(i);(2)前序遍歷遞歸算法void perorder(int p)if(p>0)coutvvtreep.data;perorder(treep.lchild); perorder(treep.rchild);(3) 中序遍歷遞歸算法void inorder(int p) 同學自己寫 (4) 后序遍歷遞歸算法void postorder(int p) 同學自己寫 3、程序#define N 20#include<stdio.h>#include< iostream.h >struct nodechar data

48、;int lchild, rchild;struct node treeN+1;int root;“擴展后序序列“插入表示空子樹 (以#代替空子樹)(以表示結束 )的符號值建 立二叉樹算法；前序遍歷遞歸算法；中序遍歷遞歸算法；后序遍歷遞歸算法；void main()int root;coutvv"輸入字符:"<<endl; root=settree( );perorder(root); inrorder(root);postorder(root);(四) 實驗結果1、畫出一棵二叉樹并采用 “擴展后序序列“插入表示空子樹 (以#代替空子樹) 的符號序列.2、測試數

49、據： #ji#fed#hg#cb#a<CR> 寫出程序運行的結果 :測試數據： #db#e#fca<CR>寫出程序運行的結果 :測試數據： #dc#b#g#fea<CR>寫出程序運行的結果 :2、寫出程序運行的結果.3、小結、體會.十二、?圖的應用一?實驗十一實驗目的1、掌握圖的根本存儲方法.2、掌握圖的兩種搜索路徑的遍歷方法.二實驗內容與要求1、問題描述采用鄰接矩陣實現圖的深度優先遍歷和廣度優先遍歷三操作算法1、數據類型定義#define MAXVEX 100struct vertexint num;char data;struct graphstruct

50、 vertex vexsMAXVEX;int edgesMAXVEX MAXVEX;2、操作算法1創立一個有向圖的鄰接矩陣算法struct graph creatgraphint *n 補充完整 (2) 顯示鄰接矩陣表示圖算法void dispgraph(struct graph adj, int n) int i,j,k;printf( “n 顯示鄰接矩陣表示圖： n);for(i=1;i<=n;i+) for(j=1;j<=n;j+) printf( “(%c,%c):%dn,adj.vexsi.data,adj.vexsj.data, adj.edgesij);3、完整算法#

51、define MAXVEX 100 #include<stdio.h> #include< iostream.h > struct vertexint num;char data;struct graphstruct vertex vexsMAXVEX;int edgesMAXVEX MAXVEX; 創立一個有向圖的鄰接矩陣算法； 顯示鄰接矩陣表示圖算法；void main( ) struct graph adj;int n;adj= creatgraph(&n); dispgraph(adj, n);(三)實驗結果1、測試數據：頂點數(n)和邊數(e):5,7

52、 <CR> 第1個頂點的信息： a <CR> 第 2個頂點的信息： b <CR>第 3 個頂點的信息： c<CR>第 4 個頂點的信息： d<CR>第 5 個頂點的信息： e<CR>第1條邊=> 起點：a終點：b權值：1<CR>第2條邊=> 起點： a 終點: c 權值: 2<CR>第3條邊=> 起點： c 終點： e 權值： 3<CR>第4條邊=> 起點： b 終點： d 權值： 4<CR>第5條邊=> 起點： b 終點： e 權值： 5<

53、;CR>第6條邊=> 起點： a 終點： d 權值： 6<CR> 第7條邊=> 起點： e 終點： d 權值： 7<CR>2、寫出程序運行的結果并畫出該圖 ：3、分析程序并寫出小結、體會.十三、?圖得應用二?實驗十一一實驗目的1、掌握圖的根本存儲方法.2、掌握圖的兩種搜索路徑的遍歷方法.二實驗內容與要求1、問題描述采用鄰接表實現圖的深度優先遍歷和廣度優先遍歷三操作算法1、數據類型定義#define MAXVEX 30struct edgenodeint adjvex;char data;struct edgenode *next;struct vexn

54、odechar data;struct edgenode *link;struct vexnode adjlistMAXVEX;2、操作算法(1) 創立一個無向圖的鄰接表算法 void creagraph(struct vexnode g,int *n) 補充完整 (2) 顯示鄰接表表示圖算法 void dispgraph(struct vexnode g, int n) int i;struct edgenode *p;cout«圖的鄰接表表示如下： <<e ndl;for(i=1;i<=n;i+) printf( “%d,%c=>,i,gi.data);p

55、=gi.link;while(p!=NULL) printf(%d,%c ,p->adjvex,p->data);p=p->next;coutvv <<e ndl; (3) 深度優先搜索遞歸算法void dfs(struct vexnode adj, int v, int visited) 補充完整 (4) 寬度優先搜索遞歸算法int queueMAXVEX;void bfs(struct vexnode adj, int vi, int visited) 補充完整3、完整的算法 #define MAXVEX 30#include<stdio.h> #include< iostream.h >struct edgenodeint adjvex;char data; struc