數(shù)據(jù)結(jié)構(gòu)與算法與實(shí)踐數(shù)據(jù)結(jié)構(gòu)實(shí)踐實(shí)驗(yàn)指導(dǎo)書參考

1、據(jù) 結(jié) 構(gòu) 實(shí) 踐實(shí)驗(yàn)指導(dǎo)書2013 年 8 月實(shí)驗(yàn)一C 語(yǔ)言編程復(fù)習(xí) 3實(shí)驗(yàn)二線形表基本操作的實(shí)現(xiàn) 5實(shí)驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用 15實(shí)驗(yàn)四二叉樹算法的實(shí)現(xiàn) 30實(shí)驗(yàn)五圖的算法的實(shí)現(xiàn) 46實(shí)驗(yàn)六查找算法的實(shí)現(xiàn) 66實(shí)驗(yàn)七 排序算法的實(shí)現(xiàn)7847實(shí)驗(yàn)一 C 語(yǔ)言編程復(fù)習(xí)一、實(shí)驗(yàn)?zāi)康? .熟悉C 語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C 語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2 .理解指針與應(yīng)用的區(qū)別。3 .掌握結(jié)構(gòu)體的使用。4 .掌握簡(jiǎn)單排序方法。二、實(shí)驗(yàn)內(nèi)容1、使用指針和引用兩種方式，完成兩個(gè)學(xué)生的交換。5 、寫一函數(shù)，根據(jù)成績(jī)，對(duì)包含有n 個(gè)學(xué)生的數(shù)組進(jìn)行排序。三、實(shí)驗(yàn)步驟1 .定義一個(gè)Student的結(jié)構(gòu)體類型，

2、包含學(xué)號(hào)、姓名、成績(jī)等成員。2 . 分別寫 Swap1(Student *s1, Student *s2) 和 Swap2(Student &s1, Student &s2),完成兩個(gè)學(xué)生的交換。3 .寫一排序函數(shù)SortStu(Student *s, int n),使用冒泡或者簡(jiǎn)單選擇排序算法根據(jù)成績(jī)完成學(xué)生的排序。四、實(shí)現(xiàn)提示struct Studentchar name20;/ 姓名char num10; / 學(xué)號(hào)float score; / 成績(jī);void Swap1( Student *, Student *);/ 交換兩個(gè)結(jié)構(gòu)體變量(指針)void Swap2( Student &

3、, Student &);/ 交換兩個(gè)結(jié)構(gòu)體變量(引用)void SortStu ( Student*,int);/ 按成績(jī)(高到低)排序 五、思考與提高思考為何void Swap1(Student, Student )這個(gè)函數(shù)無(wú)法實(shí)現(xiàn)兩個(gè)學(xué)生的交換？ 六、完整參考程序void Swap1( Student *s1, Student *s2) Student temp;temp=*s1;*s1=*s2;*s2=temp;void Swap2( Student &s1, Student &s2) STUDENT temp;temp=s1;s1=s2;s2=temp;void SortStu( S

4、tudent S,int n) Student temp;for(int i=0;in;i+)int idx = i;for(int j=i+1;jSj.score) idx = j;if (idx != i)temp= Sidx;Sidx = Si;Si = temp;實(shí)驗(yàn)二 線形表基本操作的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康? .熟悉 C 語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C 語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2 .掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C 語(yǔ)言實(shí)現(xiàn)。3 .掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表的定義及C 語(yǔ)言實(shí)現(xiàn)。4 .掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5 .掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表中的各種基本操作。二、實(shí)

5、驗(yàn)內(nèi)容1 .順序線性表的建立、插入及刪除。2 .鏈?zhǔn)骄€性表的建立、插入及刪除。三、實(shí)驗(yàn)步驟1 .建立含 n 個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng) 度。2 .利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L=21 ， 23， 14， 5， 56， 17， 31，然后在第i 個(gè)位置插入元素68。3 .建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。四、實(shí)現(xiàn)提示1 .由于C 語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C 語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。在此，我們利用C 語(yǔ)言的結(jié)構(gòu)體類型定義順序表：#define M

6、AXSIZE 1024typedef int elemtype; /* 線性表中存放整型元素*/typedef struct elemtype vecMAXSIZE;int len; /* 順序表的長(zhǎng)度*/sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h 里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出順序表的建立及常量的定義。2 . 注意如何取到第i 個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。3 .單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C 語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：typedef int elemtype;typed

7、ef struct node elemtype data; /數(shù)據(jù)域struct node *next; /指針域linklist;注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc(),如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：p=(linklist *)malloc(sizeof(linklist); 該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為linklist 的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值(NULL)。五、思考與提高1. 如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。

8、2. 在 main 函數(shù)里如果去掉L=&a 語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？六、完整參考程序#include #include #define MAX 30/定義線性表的最大長(zhǎng)度enum BOOLFalse,True;/定義BOOL 型typedef structchar elemMAX;/線性表int last;/last 指示當(dāng)前線性表的長(zhǎng)度sqlist;void initial(sqlist &);/初始化線性表BOOL insert(sqlist &,int,char); / 在線性表中插入元素BOOL del(sqlist&,int,char &);/在線性表中刪除元素int locate(s

9、qlist,char);/在線性表中定位元素void print(sqlist);/顯示線性表中所有元素void main()sqlist S; /S 為一線性表int loc,flag=1;char j,ch;BOOL temp;printf( 本程序用來(lái)實(shí)現(xiàn)順序結(jié)構(gòu)的線性表。n);printf( 可以實(shí)現(xiàn)查找、插入、刪除等操作。n);initial(S);/初始化線性表while(flag) printf( 請(qǐng)選擇 :n);printf(1.顯示所有元素n);printf(2.插入一個(gè)元素n);printf(3.刪除一個(gè)元素n);printf(4.查找一個(gè)元素n);printf(5.退出程

10、序n);scanf( %c,&j);switch(j)case 1:print(S); break; / 顯示所有元素case 2:printf( 請(qǐng)輸入要插入的元素(一個(gè)字符)和插入位置:n);printf( 格式：字符，位置；例如:a,2n);scanf( %c,%d,&ch,&loc);/輸入要插入的元素和插入的位置temp=insert(S,loc,ch);/插入if(temp=False) printf( 插入失敗!n);/插入失敗else printf( 插入成功!n); print(S); / 插入成功break;case 3:printf( 請(qǐng)輸入要?jiǎng)h除元素的位置:);scan

11、f(%d,&loc); /輸入要?jiǎng)h除的元素的位置temp=del(S,loc,ch);/刪除if(temp=True) printf( 刪除了一個(gè)元素:%cn,ch); / 刪除成功else printf( 該元素不存在!n);/刪除失敗print(S);break;case 4:printf( 請(qǐng)輸入要查找的元素:);scanf( %c,&ch);/輸入要查找的元素loc=locate(S,ch);/定位if(loc!=-1) printf( 該元素所在位置:%dn,loc+1); / 顯示該元素位置else printf(%c 不存在 !n,ch);/ 當(dāng)前元素不存在break; defa

12、ult:flag=0;printf( 程序結(jié)束，按任意鍵退出!n); getch();void initial(sqlist &v)/初始化線性表 int i; printf( 請(qǐng)輸入初始線性表長(zhǎng)度：n=); /輸入線性表初始化時(shí)的長(zhǎng)度scanf(%d,&v.last);printf( 請(qǐng)輸入從1 到 %d 的各元素(字符)，例如:abcdefgn,v.last);getchar();for(i=0;iv.last;i+) scanf(%c,&v.elemi); / 輸入線性表的各元素BOOL insert(sqlist &v,int loc,char ch)插入一個(gè)元素，成功返回 True,

13、失敗返回False int i;if(locv.last+1)printf( 插入位置不合理!n);/位置不合理return False;else if(v.last=MAX)/線性表已滿printf( 線性表已滿!n);return False;else for(i=v.last-1;i=loc-1;i-) v.elemi+1=v.elemi;/其后元素依次后移v.elemloc-1=ch;/插入元素v.last+;/線性表長(zhǎng)度加一return True;BOOL del(sqlist &v,int loc,char &ch)刪除一個(gè)元素，成功返回 True,并用ch返回該元素值，失敗返回F

14、alseint j;if(locv.last) /刪除位置不合理return False;else ch=v.elemloc-1; /ch 取得該元素值for(j=loc-1;jv.last-1;j+) v.elemj=v.elemj+1;/其后元素依次前移v.last-;/線性表長(zhǎng)度減一return True; int locate(sqlist v,char ch)/在線性表中查找ch 的位置，成功返回其位置，失敗返回-1int i=0; while(iv.last&v.elemi!=ch) i+;/當(dāng)前位置后移，直到找到為止if(v.elemi=ch)/找到當(dāng)前元素return i;el

15、se return(-1);void print(sqlist v)/顯示當(dāng)前線性表所有元素int i;for(i=0;iv.last;i+) printf(%c ,v.elemi); printf(n);2. 鏈?zhǔn)骄€性表的建立、插入及刪除。#include #include #include #define LEN sizeof(LNode)/定義LEN 為一個(gè)節(jié)點(diǎn)的長(zhǎng)度enum BOOLFalse,True;/定義BOOL 型typedef struct nodechar data;/數(shù)據(jù)域struct node *next;/ 指向下一個(gè)節(jié)點(diǎn)的指針LNode,*LinkList;void

16、 CreatList(LinkList &,int);/生成一個(gè)單鏈表BOOL ListInsert(LinkList &,int,char); / 在單鏈表中插入一個(gè)元素BOOL ListDelete(LinkList &,int,char &); / 在單鏈表中刪除一個(gè)元素BOOL ListFind_keyword(LinkList,char,int &); / 按關(guān)鍵字查找一個(gè)元素BOOL ListFind_order(LinkList,char &,int);/按序號(hào)查找一個(gè)元素void ListPrint(LinkList);/顯示單鏈表所有元素void main()LinkList

17、 L;BOOL temp;int num,loc,flag=1;char j,ch;printf（ 本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的線性表的操作。n）;printf（ 可以進(jìn)行插入，刪除，定位，查找等操作。n）;printf（ 請(qǐng)輸入初始時(shí)鏈表長(zhǎng)度:）; /輸入生成單鏈表時(shí)的元素個(gè)數(shù)scanf（%d,&num）;CreatList（L,num）;/生成單鏈表ListPrint（L）;while（flag） printf（ 請(qǐng)選擇 :n）;printf（1.顯示所有元素n）;/顯示鏈表元素printf（2.插入一個(gè)元素n）;/插入鏈表元素printf（3.刪除一個(gè)元素n）;/刪除鏈表元素printf（4.

18、按關(guān)鍵字查找元素n）;/按關(guān)鍵字查找printf（5. 按序號(hào)查找元素n）; /按序號(hào)查找printf（6. 退出程序n）; /退出scanf（ %c,&j）;switch（j）case 1:ListPrint（L）; break;case 2:printf（ 請(qǐng)輸入元素（一個(gè)字符）和要插入的位置:n）;printf（ 格式:字符，位置；例如:a,3n）;scanf（ %c,%d,&ch,&loc）;/輸入要插入的元素和要插入的位置temp=ListInsert（L,loc,ch）;/插入if（temp=False） printf（ 插入失敗!n）; / 插入失敗else printf（ 插入

19、成功!n）; / 成功插入ListPrint（L）;break;case 3:printf（ 請(qǐng)輸入要?jiǎng)h除的元素所在位置:）;scanf（%d,&loc）;/輸入要?jiǎng)h除的節(jié)點(diǎn)的位置temp=ListDelete（L,loc,ch）;/刪除if（temp=False） printf（ 刪除失敗!n）; / 刪除失敗else printf（ 成功刪除了一個(gè)元素:%cn,ch）;/刪除成功，顯示該元素ListPrint（L）;break;case 4:if（L-next=NULL）/鏈表為空printf（ 鏈表為空!n）;elseprintf（ 請(qǐng)輸入要查找的元素（一個(gè)字符）:）;scanf( %c

20、,&ch);/輸入要查找的元素temp=ListFind_keyword(L,ch,loc); / 按關(guān)鍵字查找if(temp=False) printf( 沒有找到該元素!n); / 查找失敗else printf( 該元素在鏈表的第%d 個(gè)位置。n,loc);/成功查找，顯示該元素位置break;case 5:if(L-next=NULL)/鏈表為空printf( 鏈表為空!n);elseprintf( 請(qǐng)輸入要查找的位置:);scanf(%d,&loc);/輸入要查找的元素的位置temp=ListFind_order(L,ch,loc); / 按序號(hào)查找 if(temp=False) p

21、rintf( 該位置不存在!n); / 查找失敗else printf( 第 %d 個(gè)元素是：%cn,loc,ch);/成功查找，顯示該元素break;default:flag=0;printf( 程序結(jié)束，按任意鍵退出!n);getch();void CreatList(LinkList &v,int n)/生成一個(gè)帶頭結(jié)點(diǎn)的有n 個(gè)元素的單鏈表int i;LinkList p;v=(LinkList)malloc(LEN); / 生成頭結(jié)點(diǎn)v-next=NULL;printf( 請(qǐng)輸入 %d 個(gè)字符：例如：abcdefgn,n);getchar();for(i=n;i0;-i)p=(Lin

22、kList)malloc(LEN); / 生成新結(jié)點(diǎn)scanf(%c,&p-data);p-next=v-next;v-next=p;BOOL ListInsert(LinkList &v,int i,char e)/在單鏈表的第i各位置插入元素 e,成功返回True,失敗返回FalseLinkList p,s; int j=0; p=v; while(p&jnext;+j; / 查找第 i-1 個(gè)元素的位置 if(!p|ji-1) return False;/沒有找到s=(LinkList)malloc(LEN);/生成一個(gè)新結(jié)點(diǎn)s-data=e; s-next=p-next;/將新結(jié)點(diǎn)插入

23、到單鏈表中p-next=s;return True;BOOL ListDelete(LinkList &v,int i,char &e)False/在單鏈表中刪除第i個(gè)元素，成功刪除返回True,并用e返回該元素值，失敗返回 LinkList p,q;int j=0; p=v;while(p-next&jnext;+j;if(!(p-next)|ji-1) return False; / 查找失敗 q=p-next;p-next=q-next; / 刪除該元素 e=q-data;/e 取得該元素值free(q);/釋放該元素空間return True;BOOL ListFind_keyword

24、(LinkList v,char e,int &i)/在單鏈表中查找關(guān)鍵字為e的元素，成功返回 True,并用i返回該元素位置，/失敗返回Falsei=1;LinkList p;p=v-next;while(p-data!=e)&(p-next!=NULL)/p 指針指向下一個(gè)，直到p=p-next; i+;/找到或到鏈表尾為止if(p-data!=e)/該元素在鏈表中不存在return False; else return True;BOOL ListFind_order(LinkList v,char &e,int i)i個(gè)元素，成功返回 True,并用e返回該元素值,/在單鏈表中查找第/

25、失敗返回FalseLinkList p;int j=0;/移動(dòng)指針，直到找到第i 個(gè)元素p=v;while(p-next&jnext;+j; if(j!=i) return False; / else e=p-data;return True;查找失敗/查找成功，用e 取得該元素值void ListPrint(LinkList v)/顯示鏈表所有元素LinkList q;q=v-next;printf( 鏈表所有元素:);while(q!=NULL)printf(%c ,q-data);q=q-next; printf(n);實(shí)驗(yàn)三 棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 掌握棧的順序表

26、示和實(shí)現(xiàn)2. 掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容1. 編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2. 實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。三、實(shí)驗(yàn)步驟1. 初始化順序棧2. 插入元素3. 刪除棧頂元素4. 取棧頂元素5. 遍歷順序棧6. 置空順序棧7. 初始化并建立鏈隊(duì)列8. 入鏈隊(duì)列9. 出鏈隊(duì)列10. 遍歷鏈隊(duì)列四、實(shí)現(xiàn)提示1. /*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化順序棧函數(shù)*/void InitStack(SqStack *p)q=(SqStack*)malloc(sizeof(SqStack)

27、 /*申請(qǐng)空間*/)/*入棧函數(shù)*/void Push(SqStack *p,ElemType x)if(p-toptop=p-top+1;/*棧頂 +1*/p-stackp-top=x; /*數(shù)據(jù)入棧*/*出棧函數(shù)*/ElemType Pop(SqStack *p)x=p-stackp-top; /* 將棧頂元素賦給x*/p-top=p-top-1; /* 棧頂 -1*/*獲取棧頂元素函數(shù)*/ElemType GetTop(SqStack *p) x=p-stackp-top;/*遍歷順序棧函數(shù)*/void OutStack(SqStack *p) for(i=p-top;i=0;i-)pr

28、intf( 第 %d 個(gè)數(shù)據(jù)元素是：%6dn,i,p-stacki);/*置空順序棧函數(shù)*/void setEmpty(SqStack *p) p-top= -1;2. /*定義鏈隊(duì)列*/typedef struct Qnode ElemType data;struct Qnode *next;Qnodetype;typedef struct Qnodetype *front;Qnodetype *rear;Lqueue;/*初始化并建立鏈隊(duì)列函數(shù)*/void creat(Lqueue *q) h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申請(qǐng)空間*

29、/h-next=NULL;q-front=h;q-rear=h;for(i=1;idata=x;s-next=NULL;q-rear-next=s;q-rear=s;/*出鏈隊(duì)列函數(shù)*/ElemType Ldelete(Lqueue *q) p=q-front-next;q-front-next=p-next;if(p-next=NULL) q-rear=q-front;x=p-data;free(p); /* 釋放空間*/*遍歷鏈隊(duì)列函數(shù)*/void display(Lqueue *q) while(p!=NULL) /*利用條件判斷是否到隊(duì)尾*/ printf(%d-,p-data);p=

30、p-next;五、思考與提高1. 讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？2. 如果一個(gè)程序中要用到兩個(gè)棧，為了不發(fā)生上溢錯(cuò)誤，就必須給每個(gè)棧預(yù)先分配一個(gè)足夠大的存儲(chǔ)空間。若每個(gè)棧都預(yù)分配過(guò)大的存儲(chǔ)空間，勢(shì)必會(huì)造成系統(tǒng)空間緊張。如何解決這個(gè)問(wèn)題？（ 1）鏈棧只有一個(gè)top 指針，對(duì)于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針？（ 2）一個(gè)程序中如果要用到兩個(gè)棧時(shí)，可通過(guò)兩個(gè)棧共享一維數(shù)組來(lái)實(shí)現(xiàn)。即雙向棧共享鄰接空間。如果一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？六、完整參考程序1. 棧的順序表示和實(shí)現(xiàn)#include #include #include # define TRUE1#

31、define FALSE0# define OK1# define ERROR 0# define INFEASIBLE -1# define OVERFLOW -2typedef int Status;typedef int SElemType;/ 棧的順序存儲(chǔ)表示#define STACK_INIT_SIZE 100#define STACKINCREMENT10typedef struct SElemType *base;SElemType *top;int stacksize; SqStack;Status InitStack(SqStack &S);Status DestroySta

32、ck(SqStack &S);Status StackDisplay(SqStack &S);Status GetTop(SqStack S,SElemType &e);Status Push(SqStack &S,SElemType e);Status Pop(SqStack &S,SElemType &e);Status StackEmpty(SqStack S);Status InitStack(SqStack &S)/ 構(gòu)造一個(gè)空棧SS.base = (SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) e

33、xit(OVERFLOW); / 存儲(chǔ)分配失效S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/InitStackStatus DestroyStack(SqStack &S)/ 銷毀棧 Sif(S.base) free(S.base);S.top = S.base = NULL;return OK;/InitStackStatus StackDisplay(SqStack &S)/ 顯示棧 SSElemType * p=S.base;int i = 0;if(S.base = S.top)printf( 堆棧已空!n);retur

34、n OK;while( p =S.stacksize)/ 棧滿，追加存儲(chǔ)空間S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if( ! S.base ) exit(OVERFLOW);/ 存儲(chǔ)分配失敗S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top + = e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)/若棧不為空，則刪除S 的棧頂元素，用

35、e返回其值，并返回 OK;否則返回ERRORif （S.top = S.base） return ERROR;e = * -S.top;return OK;/PopStatus StackEmpty（SqStack S）/若 S 為空棧，則返回TRUE ，否則返回FALSE。if（S.top = S.base） return TRUE;else return FALSE;/ StackEmptyvoid main（）SqStack St;Status temp;int flag=1,ch;int e;printf（ 本程序?qū)崿F(xiàn)順序結(jié)構(gòu)的堆棧的操作。n）;printf（ 可以進(jìn)行入棧，出棧，取棧

36、頂元素等操作。n）;InitStack（St）;/初始化堆棧Stwhile（flag）printf（ 請(qǐng)選擇 :n）;printf（1. 顯示棧中所有元素n）;printf（2. 入棧n）;printf（3. 出棧n）;printf（4. 取棧頂元素n）;printf（5. 退出程序n）;scanf（%d,&ch）;switch(ch)case 1:StackDisplay(St);break;case 2:printf( 請(qǐng)輸入要入棧的元素(一個(gè)整數(shù)):);scanf(%d,&e);/輸入要入棧的元素temp=Push(St,e);/入棧if(temp!=OK) printf( 堆棧已滿!

37、入棧失敗!n);else printf( 成功入棧!n);/成功入棧StackDisplay(St);break;case 3:temp=Pop(St,e); /出棧if(temp=ERROR) printf( 堆棧已空!n);else printf( 成功出棧一個(gè)元素:%dn,e); / 成功出棧StackDisplay(St);break;case 4:temp=GetTop(St,e); / 取得棧頂元素if(temp=ERROR) printf( 堆棧已空!n);else printf( 棧頂元素是:%dn,e); /顯示棧頂元素break;default:flag=0;printf(

38、 程序結(jié)束，按任意鍵退出!n);getch();DestroyStack(St);2. 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)#include #include #include # define TRUE1# define FALSE0# define OK1# define ERROR 0# define INFEASIBLE -1# define OVERFLOW -2/Status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Status;/ElemType 是順序表數(shù)據(jù)元素類型,此程序定義為int 型typedef int QElemType;/單鏈隊(duì)列-隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typede

39、f struct QNode/定義結(jié)點(diǎn)結(jié)構(gòu)QElemType data; /數(shù)據(jù)域struct QNode *next;/指針域QNode,*QueuePtr;typedef struct linkqueue /定義隊(duì)列結(jié)構(gòu)QueuePtr front;/隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針/初始化一個(gè)隊(duì)列LinkQueue;Status InitLinkQueue(LinkQueue &);Status DestroyLinkQueue(LinkQueue &);/銷毀一個(gè)隊(duì)列int LinkQueueLength(LinkQueue &Q);/隊(duì)列的長(zhǎng)度Status EnLink

40、Queue(LinkQueue &,QElemType);/將一個(gè)元素入隊(duì)列/顯示隊(duì)列中所有元素Status DeLinkQueue(LinkQueue &,QElemType &);/ 將一個(gè)元素出隊(duì)列Status DisplayLinkQueue(LinkQueue);void main()LinkQueue LQ;QElemType e;int flag=1,ch,len;Status temp;printf( 本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列的操作。n);printf( 可以進(jìn)行入隊(duì)列、出隊(duì)列等操作。n);InitLinkQueue(LQ);/初始化隊(duì)列while(flag)printf( 請(qǐng)選

41、擇 :n);printf(1. 顯示隊(duì)列所有元素n);printf(2. 入隊(duì)列 n);printf(3. 出隊(duì)列 n);printf(4. 求隊(duì)列的長(zhǎng)度n);printf(5. 退出程序n);scanf(%d,&ch);switch(ch)case 1:DisplayLinkQueue(LQ); /顯示隊(duì)列中所有元素break;case 2:printf( 請(qǐng)輸入要人隊(duì)的元素(一個(gè)整數(shù)):);scanf(%d,&e);/輸入要入隊(duì)列的字符EnLinkQueue(LQ,e);/ 入隊(duì)列DisplayLinkQueue(LQ); break;case 3:temp=DeLinkQueue(LQ,

42、e); /出隊(duì)列if(temp=OK)printf( 出隊(duì)一個(gè)元素:%dn,e);DisplayLinkQueue(LQ);else printf( 隊(duì)列為空!n);break;case 4:len=LinkQueueLength(LQ);printf( 隊(duì)列的長(zhǎng)度為:%dn,len);break;default:flag=0;printf( 程序運(yùn)行結(jié)束，按任意鍵退出!n);getch();Status InitLinkQueue(LinkQueue &Q)/ 隊(duì)列初始化Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); / 生成一個(gè)頭結(jié)點(diǎn)，并把首

43、尾指針指向頭結(jié)點(diǎn)Q.front-next=NULL;return OK;Status DestroyLinkQueue(LinkQueue &Q)/ 銷毀一個(gè)隊(duì)列QueuePtr p;QElemType e;while(Q.front!=Q.rear)DeLinkQueue(Q,e);free(Q.front);Q.front=Q.rear=NULL;return OK;int LinkQueueLength(LinkQueue &Q)/ 隊(duì)列的長(zhǎng)度int i=0;QueuePtr p=Q.front;while(p!=Q.rear)+i;p=p-next;return i;Status En

44、LinkQueue(LinkQueue &Q,QElemType e)/ 入隊(duì)列QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);/ 生成一個(gè)新結(jié)點(diǎn)p-data=e;/賦值 p-next=NULL;Q.rear-next=p;/插入至隊(duì)列尾Q.rear=p;/修改隊(duì)尾指針Status DeLinkQueue(LinkQueue &Q,QElemType &e)/QueuePtr p;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)

45、 Q.rear=Q.front;return OK;Status DisplayLinkQueue(LinkQueue Q)/QueuePtr p;int i=0;p=Q.front-next;if(p=NULL) printf(else出隊(duì)列/判斷隊(duì)列是否已空，已空返回ERROR/p 指向隊(duì)列中第一個(gè)元素/取得該元素值/修改隊(duì)首指針/若隊(duì)列已空，把隊(duì)尾指針指向頭結(jié)點(diǎn)/成功出隊(duì)列，返回OK顯示隊(duì)列中所有元素隊(duì)列為空!n);/ 隊(duì)列為空return OK;while(p)/否則顯示隊(duì)列中所有元素printf(%d:%d,+i,p-data);p=p-next;printf(n);return O

46、K;實(shí)驗(yàn)四 二叉樹算法的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?. 通過(guò)實(shí)驗(yàn)，掌握二叉樹的建立與存儲(chǔ)2. 通過(guò)實(shí)驗(yàn)，掌握二叉樹的遍歷方法二、實(shí)驗(yàn)內(nèi)容1. 練習(xí)二叉樹的建立與存儲(chǔ)2. 練習(xí)二叉樹的遍歷三、實(shí)驗(yàn)步驟1 .建立自己的頭文件BT.H,內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹的 建立、二叉樹的先序、中序與后序遍歷算法。2 . 建立二叉樹,并通過(guò)調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。四、實(shí)現(xiàn)提示建立二叉樹的代碼如下：BTCHINALR * createbt( ) BTCHINALR *q;struct node1 *s30;int j,i,x;printf( 建立二叉樹，輸入結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)和值,編號(hào)和值之間用逗號(hào)nn);printf(i,x = );scanf(%d,%c,&i,&x);while(i != 0 & x != $)q = (BTCHINALR*)malloc(sizeof(BTCHINALR); /*建立一個(gè)新結(jié)點(diǎn) q*/q-data = x; q-lchild = NULL; q-rchild = NULL;si = q;/*q 新結(jié)點(diǎn)地址存入s 指針數(shù)組中*/if(i != 1) /*i = 1 ，對(duì)應(yīng)的結(jié)點(diǎn)是根結(jié)點(diǎn)*/j = i / 2;/*求雙親結(jié)點(diǎn)的編號(hào)j*/if(i % 2 = 0) sj-lchild = q; /*q 結(jié)點(diǎn)編號(hào)為偶數(shù)則