數(shù)據(jù)結(jié)構(gòu)與算法與實踐數(shù)據(jù)結(jié)構(gòu)實踐實驗指導書參考

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

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

3、, Student &);/ 交換兩個結(jié)構(gòu)體變量(引用)void SortStu ( Student*,int);/ 按成績(高到低)排序 五、思考與提高思考為何void Swap1(Student, Student )這個函數(shù)無法實現(xiàn)兩個學生的交換？ 六、完整參考程序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;實驗二 線形表基本操作的實現(xiàn)一、實驗?zāi)康? .熟悉 C 語言的上機環(huán)境，進一步掌握C 語言的結(jié)構(gòu)特點。2 .掌握線性表的順序存儲結(jié)構(gòu)的定義及C 語言實現(xiàn)。3 .掌握線性表的鏈式存儲結(jié)構(gòu)單鏈表的定義及C 語言實現(xiàn)。4 .掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。5 .掌握線性表在鏈式存儲結(jié)構(gòu)單鏈表中的各種基本操作。二、實

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

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

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

8、2. 在 main 函數(shù)里如果去掉L=&a 語句，會出現(xiàn)什么結(jié)果？六、完整參考程序#include #include #define MAX 30/定義線性表的最大長度enum BOOLFalse,True;/定義BOOL 型typedef structchar elemMAX;/線性表int last;/last 指示當前線性表的長度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( 本程序用來實現(xiàn)順序結(jié)構(gòu)的線性表。n);printf( 可以實現(xiàn)查找、插入、刪除等操作。n);initial(S);/初始化線性表while(flag) printf( 請選擇 :n);printf(1.顯示所有元素n);printf(2.插入一個元素n);printf(3.刪除一個元素n);printf(4.查找一個元素n);printf(5.退出程

10、序n);scanf( %c,&j);switch(j)case 1:print(S); break; / 顯示所有元素case 2:printf( 請輸入要插入的元素(一個字符)和插入位置: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( 請輸入要刪除元素的位置:);scan

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

12、ult:flag=0;printf( 程序結(jié)束，按任意鍵退出!n); getch();void initial(sqlist &v)/初始化線性表 int i; printf( 請輸入初始線性表長度：n=); /輸入線性表初始化時的長度scanf(%d,&v.last);printf( 請輸入從1 到 %d 的各元素(字符)，例如:abcdefgn,v.last);getchar();for(i=0;iv.last;i+) scanf(%c,&v.elemi); / 輸入線性表的各元素BOOL insert(sqlist &v,int loc,char ch)插入一個元素，成功返回 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+;/線性表長度加一return True;BOOL del(sqlist &v,int loc,char &ch)刪除一個元素，成功返回 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-;/線性表長度減一return True; int locate(sqlist v,char ch)/在線性表中查找ch 的位置，成功返回其位置，失敗返回-1int i=0; while(iv.last&v.elemi!=ch) i+;/當前位置后移，直到找到為止if(v.elemi=ch)/找到當前元素return i;el

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

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

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

18、按關(guān)鍵字查找元素n）;/按關(guān)鍵字查找printf（5. 按序號查找元素n）; /按序號查找printf（6. 退出程序n）; /退出scanf（ %c,&j）;switch（j）case 1:ListPrint（L）; break;case 2:printf（ 請輸入元素（一個字符）和要插入的位置: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（ 請輸入要刪除的元素所在位置:）;scanf（%d,&loc）;/輸入要刪除的節(jié)點的位置temp=ListDelete（L,loc,ch）;/刪除if（temp=False） printf（ 刪除失敗!n）; / 刪除失敗else printf（ 成功刪除了一個元素:%cn,ch）;/刪除成功，顯示該元素ListPrint（L）;break;case 4:if（L-next=NULL）/鏈表為空printf（ 鏈表為空!n）;elseprintf（ 請輸入要查找的元素（一個字符）:）;scanf( %c

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

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

22、kList)malloc(LEN); / 生成新結(jié)點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 個元素的位置 if(!p|ji-1) return False;/沒有找到s=(LinkList)malloc(LEN);/生成一個新結(jié)點s-data=e; s-next=p-next;/將新結(jié)點插入

23、到單鏈表中p-next=s;return True;BOOL ListDelete(LinkList &v,int i,char &e)False/在單鏈表中刪除第i個元素，成功刪除返回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 指針指向下一個，直到p=p-next; i+;/找到或到鏈表尾為止if(p-data!=e)/該元素在鏈表中不存在return False; else return True;BOOL ListFind_order(LinkList v,char &e,int i)i個元素，成功返回 True,并用e返回該元素值,/在單鏈表中查找第/

25、失敗返回FalseLinkList p;int j=0;/移動指針，直到找到第i 個元素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);實驗三 棧和隊列基本操作的實現(xiàn)及應(yīng)用一、實驗?zāi)康?. 掌握棧的順序表

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

27、 /*申請空間*/)/*入棧函數(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 個數(shù)據(jù)元素是：%6dn,i,p-stacki);/*置空順序棧函數(shù)*/void setEmpty(SqStack *p) p-top= -1;2. /*定義鏈隊列*/typedef struct Qnode ElemType data;struct Qnode *next;Qnodetype;typedef struct Qnodetype *front;Qnodetype *rear;Lqueue;/*初始化并建立鏈隊列函數(shù)*/void creat(Lqueue *q) h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申請空間*

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;/*出鏈隊列函數(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); /* 釋放空間*/*遍歷鏈隊列函數(shù)*/void display(Lqueue *q) while(p!=NULL) /*利用條件判斷是否到隊尾*/ printf(%d-,p-data);p=

30、p-next;五、思考與提高1. 讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？2. 如果一個程序中要用到兩個棧，為了不發(fā)生上溢錯誤，就必須給每個棧預(yù)先分配一個足夠大的存儲空間。若每個棧都預(yù)分配過大的存儲空間，勢必會造成系統(tǒng)空間緊張。如何解決這個問題？（ 1）鏈棧只有一個top 指針，對于鏈隊列，為什么要設(shè)計一個頭指針和一個尾指針？（ 2）一個程序中如果要用到兩個棧時，可通過兩個棧共享一維數(shù)組來實現(xiàn)。即雙向棧共享鄰接空間。如果一個程序中要用到兩個隊列，能否實現(xiàn)？如何實現(xiàn)？六、完整參考程序1. 棧的順序表示和實現(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;/ 棧的順序存儲表示#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)造一個空棧SS.base = (SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) e

33、xit(OVERFLOW); / 存儲分配失效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)/ 棧滿，追加存儲空間S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if( ! S.base ) exit(OVERFLOW);/ 存儲分配失敗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（ 可以進行入棧，出棧，取棧

36、頂元素等操作。n）;InitStack（St）;/初始化堆棧Stwhile（flag）printf（ 請選擇 :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( 請輸入要入棧的元素(一個整數(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( 成功出棧一個元素:%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. 隊列的鏈式表示和實現(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;/單鏈隊列-隊列的鏈式存儲結(jié)構(gòu)typede

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

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

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

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

43、尾指針指向頭結(jié)點Q.front-next=NULL;return OK;Status DestroyLinkQueue(LinkQueue &Q)/ 銷毀一個隊列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)/ 隊列的長度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)/ 入隊列QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);/ 生成一個新結(jié)點p-data=e;/賦值 p-next=NULL;Q.rear-next=p;/插入至隊列尾Q.rear=p;/修改隊尾指針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出隊列/判斷隊列是否已空，已空返回ERROR/p 指向隊列中第一個元素/取得該元素值/修改隊首指針/若隊列已空，把隊尾指針指向頭結(jié)點/成功出隊列，返回OK顯示隊列中所有元素隊列為空!n);/ 隊列為空return OK;while(p)/否則顯示隊列中所有元素printf(%d:%d,+i,p-data);p=p-next;printf(n);return O

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