基礎(chǔ)性實(shí)踐環(huán)節(jié)(數(shù)據(jù)結(jié)構(gòu))實(shí)踐報(bào)告.docx

《基礎(chǔ)性實(shí)踐環(huán)節(jié)(數(shù)據(jù)結(jié)構(gòu))實(shí)踐報(bào)告.docx》由會(huì)員分享，可在線閱讀，更多相關(guān)《基礎(chǔ)性實(shí)踐環(huán)節(jié)(數(shù)據(jù)結(jié)構(gòu))實(shí)踐報(bào)告.docx（42頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、重 慶 大 學(xué)基礎(chǔ)性實(shí)踐環(huán)節(jié)(數(shù)據(jù)結(jié)構(gòu))實(shí)踐報(bào)告實(shí)踐課程名稱 數(shù)據(jù)結(jié)構(gòu)與算法 開(kāi)課 實(shí) 驗(yàn) 室 數(shù)學(xué)實(shí)驗(yàn)教學(xué)中心 學(xué) 院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院年 級(jí) 2009級(jí) 專 業(yè) 班 信息與計(jì)算科學(xué)01班學(xué) 生 姓 名 學(xué) 號(hào) 20092250 開(kāi) 課 時(shí) 間 2011 至 2012 學(xué)年 第 一 學(xué)期總 成 績(jī)教師簽名實(shí)驗(yàn)一、單鏈表的基本操作一、實(shí)驗(yàn)?zāi)康?、掌握線性鏈表的操作特點(diǎn)，即指針是邏輯關(guān)系的映像。2、掌握動(dòng)態(tài)產(chǎn)生單鏈表的方法。3、熟練掌握單鏈表的插入、刪除操作特點(diǎn)，即指針賦值的先后次序。二、實(shí)驗(yàn)內(nèi)容1、動(dòng)態(tài)創(chuàng)建單鏈表2、實(shí)現(xiàn)線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中元素的插入。3、實(shí)現(xiàn)線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中元素的刪除。三、

2、具體要求1、單鏈表的存儲(chǔ)結(jié)構(gòu)定義typedef struct LNode ElemType data; / 數(shù)據(jù)域 struct LNode *next; / 指針域 LNode, *LinkList;2、從鍵盤(pán)上依次輸入21、18、30、75、42、56，逆序創(chuàng)建單鏈表，并輸出單鏈表中的各元素值。3、分別在單鏈表的第3個(gè)位置和第9個(gè)位置插入67和10，給出插入成功或失敗的信息，并輸出單鏈表中的各元素值。4、刪除單鏈表中的第6個(gè)數(shù)據(jù)元素和第8個(gè)數(shù)據(jù)元素，給出刪除成功或失敗的信息，并輸出單鏈表中的各元素值。四、完成情況和實(shí)驗(yàn)記錄1、由于程序要求的操作很多，而且C程序要求敏感，所以在編程過(guò)程中只有

3、通過(guò)不斷的修改，不斷的嘗試來(lái)克服遇到的很多錯(cuò)誤和警告問(wèn)題。在調(diào)試過(guò)程要有足夠的耐心和發(fā)現(xiàn)錯(cuò)誤的洞察力。五、完成情況和實(shí)驗(yàn)記錄#include#include#include #include #define LEN sizeof(LNode) /定義LEN為一個(gè)節(jié)點(diǎn)的長(zhǎng)度enum BOOLFalse,True; /定義BOOL型typedef struct nodeint data; /數(shù)據(jù)域 struct node *next;/指向下一個(gè)節(jié)點(diǎn)的指針LNode,*LinkList;void CreatList(LinkList &,int); /生成一個(gè)單鏈表BOOL ListInsert(

4、LinkList &,int,int); /在單鏈表中插入一個(gè)元素BOOL ListDelete(LinkList &,int,int); /在單鏈表中刪除一個(gè)元素void ListPrint(LinkList); /顯示單鏈表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1,ch; char j; /程序說(shuō)明 printf(單鏈表的基本操作。n); printf(可以進(jìn)行逆置，插入，刪除等操作。n); printf(請(qǐng)輸入初始時(shí)鏈表長(zhǎng)度:); /輸入生成單鏈表時(shí)的元素個(gè)數(shù) scanf(%d,&num); CreatList(L,

5、num); /生成單鏈表 ListPrint(L); while(flag) printf(請(qǐng)選擇:n); printf(1.顯示所有元素n); /顯示鏈表元素 printf(2.插入一個(gè)元素n); /插入鏈表元素 printf(3.刪除一個(gè)元素n); /刪除鏈表元素 printf(0.退出程序 n); /退出 scanf( %c,&j); switch(j) case 1:ListPrint(L); break; case 2:printf(請(qǐng)輸入數(shù)據(jù)和要插入的位置-1:n);printf(格式：數(shù)據(jù)，位置；例如:12,3，（即把12插入到第3個(gè)位置之后，即第4個(gè)位置）n); scanf(

6、%d,%d,&ch,&loc); /輸入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(temp=False) printf(插入失敗!n); /插入失敗 else printf(插入成功!n); /成功插入 ListPrint(L); break; case 3:printf(請(qǐng)輸入要?jiǎng)h除的元素所在位置-1：（輸入2，即刪除的是第3個(gè)元素）:); scanf(%d,&loc); /輸入要?jiǎng)h除的節(jié)點(diǎn)的位置 temp=ListDelete(L,loc,ch); /刪除 if(temp=False)printf(刪除失敗!n); /刪除失敗 else

7、 printf(成功刪除了一個(gè)元素:%dn,ch); /刪除成功，顯示該元素 ListPrint(L); break; default:flag=0;printf(程序結(jié)束，按任意鍵退出!n); getchar();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è)數(shù)據(jù)：例如：1 2 3n,n); getchar(); for(i=n;i0;-i) p=(LinkList)malloc(

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

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

10、鏈表所有元素 LinkList q; q=v-next; printf(逆置輸出鏈表所有元素:); while(q!=NULL) printf(%d ,q-data);q=q-next; printf(n);六、所輸入的數(shù)據(jù)及相應(yīng)的運(yùn)行結(jié)果實(shí)驗(yàn)二 棧、隊(duì)列算法設(shè)計(jì)一、實(shí)驗(yàn)?zāi)康?、 熟悉棧這種特殊線性結(jié)構(gòu)的特性；2、 熟練掌握棧在順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)下的基本運(yùn)算；3、 熟悉隊(duì)列這種特殊線性結(jié)構(gòu)的特性；4、 熟練掌握隊(duì)列在鏈表存儲(chǔ)結(jié)構(gòu)下的基本運(yùn)算。二、實(shí)驗(yàn)內(nèi)容1、動(dòng)態(tài)創(chuàng)建棧和隊(duì)列2、實(shí)現(xiàn)實(shí)現(xiàn)棧和隊(duì)列中元素的插入。3、實(shí)現(xiàn)實(shí)現(xiàn)棧和隊(duì)列中元素的的刪除。三、具體要求1、用順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別實(shí)現(xiàn)

11、棧的初始化、求長(zhǎng)度、獲取棧頂元素、壓棧、出棧、判空、置空等操作，生成sqStack.h文件和LinkStack.h文件；編寫(xiě)main函數(shù)調(diào)用。四、程序清單順序棧#include#include#includeconst int stackIncreament=20;const int maxSize=50;template class Stackpublic:Stack(int sz=50);Stack() deleteelements;void Push(const T& x);int Pop(); int getTop();bool IsEmpty() const return (top=

12、-1)?true:false;bool IsFull() const return (top=maxSize-1)?true:false;int getSize() const return top+1;void MakeEmpty() top=-1;void print(Stack& s);void Meun();private:T *elements;int top;int maxSize;void overflowProcess();template Stack:Stack(int sz):top(-1),maxSize(sz)elements=new TmaxSize;assert(e

13、lements!=NULL);template void Stack:overflowProcess() T *newArray = new TmaxSize + stackIncreament; if (newArray=NULL) cerr存儲(chǔ)分配失敗!endl; exit(1); for (int i=0;i=top;i+) newArrayi = elementsi; maxSize = maxSize +stackIncreament; delete elements; elements = newArray;template void Stack:Push(const T&x) i

14、f (IsFull()=true) overflowProcess(); elements+top = x;template int Stack:Pop()return elementstop-;template int Stack:getTop()return elementstop;template void Stack:print(Stack& s)for(int i=s.top;i=0;i-)couts.elementsi ;coutendl;template void Stack:Meun()cout操作如下：endl;cout1-輸出棧內(nèi)元素(棧頂?shù)綏Ｎ玻〆ndl;cout2-元素

15、進(jìn)棧(單個(gè)元素）endl;cout3-元素出棧endl;cout4-讀取棧頂元素endl;cout5-得到棧中元素個(gè)數(shù)endl;cout6-清空棧endl;cout0-退出endl;cout請(qǐng)輸入操作：;void main() Stack A(50); int choice,x; A.Meun(); cinchoice; while(choice!=0) switch(choice) case 1: cout從棧頂?shù)綏Ｎ苍氐妮敵鰹椋篹ndl; A.print(A); break; case 2: coutx; A.Push(x); break; case 3: cout彈出的元素是：A.Po

16、p()endl; break; case 4: cout棧頂元素是：A.getTop()endl; break; case 5: cout棧中元素個(gè)數(shù)是：A.getSize()endl; break; case 6: cout清空棧的內(nèi)容：endl; A.MakeEmpty(); break; default: break; coutchoice; 鏈棧#include#include#include#includetypedef int StackElementType;typedef struct LinkStackNodeStackElementType data;struct Link

17、StackNode *next;LinkStackNode;typedef structstruct LinkStackNode *top; /棧頂指針LinkStack;void InitStack(LinkStack *s)/初始化鏈棧s-top=NULL;printf(n已經(jīng)初始化鏈棧！n);void ClearStack(LinkStack *s)/鏈棧置空s-top=NULL;printf(n鏈棧被置空！n);void Push(LinkStack *s, StackElementType x)/入棧LinkStackNode *p;p=(LinkStackNode *)malloc

18、(sizeof(LinkStackNode); /建立一個(gè)節(jié)點(diǎn)p-data=x;p-next=s-top; /由于是在棧頂Push，所以要指向棧頂s-top=p; /插入StackElementType Pop(LinkStack *s)/出棧StackElementType x;LinkStackNode *p;p=s-top; /指向棧頂if (s-top=0)printf(棧空，不能出棧！n);exit(-1);x=p-data; s-top=p-next; /當(dāng)前的棧頂指向原棧的nextfree(p); /釋放return x;StackElementType GetTop(LinkS

19、tack *s)/取棧頂元素if (s-top=0)printf(鏈棧為空，無(wú)棧頂元素！n);exit(-1);return s-top-data;void Disp(LinkStack *s)/鏈棧的遍歷printf(n當(dāng)前鏈棧中的數(shù)據(jù)為：n);printf(=n);LinkStackNode *p;p=s-top;while(p!=NULL) printf(t| %d |n,p-data); p=p-next;printf(=n);void main() int cord;int i,m,n,a;LinkStack *s;s=(LinkStack *)malloc(sizeof(LinkS

20、tack);printf(= 鏈棧操作=n);printf(t 第一次使用必須初始化！n);do printf(n 操作 );printf(n 1： 初始化鏈棧 );printf(n 2： 入棧 );printf(n 3： 出棧 );printf(n 4： 取棧頂元素 );printf(n 5： 置空鏈棧 );printf(n 6： 結(jié)束程序運(yùn)行 n);printf(n=n);printf(請(qǐng)輸入您的選擇(1,2,3,4,5,6);scanf(%d,&cord);printf(n);switch(cord)case 1:InitStack(s);Disp(s);break;case 2:pri

21、ntf(輸入將要壓入鏈棧的數(shù)據(jù)的個(gè)數(shù)：n=);scanf(%d,&n);printf(依次將%d個(gè)數(shù)據(jù)壓入鏈棧：n,n);for(i=1;i=n;i+)printf(請(qǐng)輸入第%d個(gè)數(shù)據(jù)：,i);scanf(%d,&a);Push(s,a);Disp(s);break;case 3:printf(n出棧操作開(kāi)始!n);printf(輸入將要出棧的數(shù)據(jù)個(gè)數(shù)：m=);scanf(%d,&m);for(i=1;i=m;i+)printf(n第%d次出棧的數(shù)據(jù)是：%d,i,Pop(s);Disp(s);break;case 4:printf(nn鏈棧的棧頂元素為：%dn,GetTop(s);printf

22、(n);break; case 5:ClearStack(s);Disp(s);break;case 6:exit(0);while (cord=6);鏈?zhǔn)酱鎯?chǔ)的隊(duì)列：#include #define MAXSIZE 40 /隊(duì)列的最大長(zhǎng)度#define QueueElementType int#define TRUE 1#define FALSE 0typedef structQueueElementType elementMAXSIZE; /隊(duì)列的元素空間 int front; int rear ; SeqQueue;void InitQueue(SeqQueue * Q) /將*Q初始化

23、為一個(gè)空的循環(huán)隊(duì)列 Q-front=Q-rear=0; void print(SeqQueue *Q)int w; if(Q-frontrear)for(w=Q-front;wrear;w+)printf(%4d,Q-elementw);if(Q-frontQ-rear)for(w=Q-front;welementw);for(w=0;wrear;w+)printf(%4d,Q-elementw);int EnterQueue(SeqQueue *Q, QueueElementType x)/將元素x入隊(duì) if(Q-rear+1)%MAXSIZE=Q-front) /隊(duì)列已經(jīng)滿了 return

24、(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /重新設(shè)置隊(duì)尾指針print(Q);return(TRUE); /操作成功int DeleteQueue(SeqQueue *Q, QueueElementType * x) /刪除隊(duì)列的隊(duì)頭元素，用x返回其值 if(Q-front=Q-rear) /隊(duì)列為空 return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /重新設(shè)置隊(duì)頭指針 return(TRUE); /操作成功int choose()int d;prin

25、tf(1:插入隊(duì)尾元素n);printf(2:刪除隊(duì)頭元素n);printf(n);scanf(%d,&d);return d;void main()SeqQueue Q;int i,f,m,x,n=0; InitQueue(&Q); /將*Q初始化為一個(gè)空的循環(huán)隊(duì)列 while(!n) switch(choose() case 1: printf(請(qǐng)輸入你要插入的數(shù)字n); scanf(%d,&i); f=EnterQueue(&Q, i); if(f) printf(插入成功n); else printf(隊(duì)列已滿n); break; case 2: printf(刪除隊(duì)列的隊(duì)頭元素是：)

26、; m=DeleteQueue(&Q, &x); if(m) printf(%dn,x); else printf(刪除失敗n); print(&Q); break;default :n=1; 五、完成情況和實(shí)驗(yàn)記錄在完成這個(gè)實(shí)驗(yàn)的過(guò)程中計(jì)較麻煩，程序的結(jié)構(gòu)的優(yōu)化比較重要，選用case語(yǔ)句進(jìn)行編程，條理會(huì)比較清晰，在算法上沒(méi)有太大的創(chuàng)新。只要將有用的算法進(jìn)行編寫(xiě)就能夠是現(xiàn)實(shí)例的應(yīng)用了。六、實(shí)驗(yàn)結(jié)果順序棧結(jié)果：鏈棧結(jié)果：隊(duì)列實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)三、二叉樹(shù)的遍歷一、實(shí)驗(yàn)?zāi)康?、掌握二叉樹(shù)的特點(diǎn)及其存儲(chǔ)方式。2、掌握二叉樹(shù)的創(chuàng)建。3、掌握二叉樹(shù)遍歷的基本方法：前序、中序、后序。二、實(shí)驗(yàn)內(nèi)容1、用前序方法建

27、立一棵二叉樹(shù)。2、編寫(xiě)前序遍歷、中序遍歷、后序遍歷二叉樹(shù)的程序。三、具體要求1.二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)類型 typedef struct BiTNode datatype data; struct BiTNode *lchild ,*rchild ; BiTNode，*BiTree;2.建立下圖所示的二叉樹(shù)cabefd3.編程實(shí)現(xiàn)以上二叉樹(shù)的前序、中序和后序遍歷操作，輸出遍歷序列4.統(tǒng)計(jì)以上二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)四、完成情況和實(shí)驗(yàn)記錄1、這個(gè)程序主要是了解算法本身，不同的遍歷順序的算法是有區(qū)別的，我們可以在遍歷的同時(shí)統(tǒng)計(jì)葉子節(jié)點(diǎn)的個(gè)數(shù)，還有比較重要的一點(diǎn)是，葉子節(jié)點(diǎn)的輸入形式，由于數(shù)字和字母

28、都有對(duì)應(yīng)的碼符，所以不能用他們來(lái)終止輸入，而用的是結(jié)束符#號(hào)。而且在運(yùn)行程序的時(shí)候要注意輸入的格式，而且要先自己畫(huà)圖，看能否構(gòu)成一顆二叉樹(shù)。五、程序清單#include #include #include #define NULL 0 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; BiTree Create(BiTree T) char ch; ch=getchar(); if(ch=#) T=NULL; else if(!(T=(BiTNode *)malloc(sizeo

29、f(BiTNode) printf(Error!); T-data=ch; T-lchild=Create(T-lchild); T-rchild=Create(T-rchild); return T; void Preorder(BiTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); void inorder(BiTree T) if(T) inorder(T-lchild); printf(%c,T-data); inorder(T-rchild); void postorder(BiTree T

30、) if(T) postorder(T-lchild); postorder(T-rchild); printf(%c,T-data); int Sumleaf(BiTree T) int sum=0,m,n; if(T) if(!T-lchild)&(!T-rchild) sum+; m=Sumleaf(T-lchild); sum+=m; n=Sumleaf(T-rchild); sum+=n; return sum; void main() BiTree T; int sum; T=Create(T); printf(前序遍歷為：); Preorder(T); printf(中序遍歷為：

31、); inorder(T); printf(后序遍歷為：); postorder(T);sum=Sumleaf(T); printf(葉子節(jié)點(diǎn)個(gè)數(shù)為：%d,sum);五、輸入的數(shù)據(jù)及所得結(jié)果：實(shí)驗(yàn)四、折半查找和二叉排序樹(shù)一、實(shí)驗(yàn)?zāi)康?、掌握查找的特點(diǎn)。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序樹(shù)的特點(diǎn)，掌握二叉排序樹(shù)的插入、刪除操作。二、實(shí)驗(yàn)內(nèi)容和具體要求1、設(shè)有關(guān)鍵字序列k= 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 ，查找key=21和key=25的數(shù)據(jù)元素。2、根據(jù)關(guān)鍵字序列45、24、53、12、37、93構(gòu)造二叉排序樹(shù)，并完成刪除關(guān)鍵字53和24的操作。三

32、、具體要求1、折半查找1、從鍵盤(pán)輸入上述8個(gè)整數(shù)5 ,14 ,18 ,21 ,23 ,29 ,31 ,35，存放在數(shù)組bub8中，并輸出其值。2、從鍵盤(pán)輸入21，查找是否存在該數(shù)據(jù)元素，若存在，則輸出該數(shù)據(jù)元素在表中的位置，否則給出查找失敗的信息。3、從鍵盤(pán)輸入25，查找是否存在該數(shù)據(jù)元素，若存在，則輸出該數(shù)據(jù)元素在表中位置，否則給出查找失敗的信息。2、二叉排序樹(shù)1、二叉排序樹(shù)結(jié)點(diǎn)定義typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;2

33、、從鍵盤(pán)上輸入六個(gè)整數(shù)45、24、53、12、37、9構(gòu)造二叉排序樹(shù)3、輸出其中序遍歷結(jié)果。4、刪除數(shù)據(jù)元素24，輸出其中序遍歷結(jié)果。5、刪除數(shù)據(jù)元素53，輸出其中序遍歷結(jié)果。三、完成情況和實(shí)驗(yàn)記錄這道題相對(duì)來(lái)說(shuō)在程序方面這邊較簡(jiǎn)單一點(diǎn)，以數(shù)組的形式來(lái)進(jìn)行折半查找，并進(jìn)行插入和刪除操作。四、程序清單折半查找：# include # define N 8main()int i,number,top,bott,mid,loca,aN,flag=1,sign=1;char c;printf(請(qǐng)輸入一個(gè)有序數(shù)組:n);scanf(%d,&a0);i=1;while(iai-1)i+;elseprint

34、f(Enter this data again:);printf(n);for(i=0;iN;i+)printf(%4d,ai);printf(n);flag=1;while(flag)printf(請(qǐng)輸入查找元素:);scanf(%d,&number);loca=0;top=0;bott=N-1;if(numberaN-1)loca=-1;sign = 1;while(sign=1)&(top=bott)mid=(bott+top)/2;if(number=amid)loca=mid;printf(找到 %d,它的位置是 %d n,number,loca+1);sign=0;else if(

35、numberamid)bott=mid-1;elsetop=mid+1;if(sign=1|loca=-1)printf(%d 不能被找到。n,number);printf(繼續(xù)查找嗎(Y/N)?);scanf( %c,&c);if(c=N|c=n)flag=0;二叉排序樹(shù)：#include#include#includetypedef int KeyType;typedef struct tree/聲明樹(shù)的結(jié)構(gòu) struct tree *left; /存放左子樹(shù)的指針struct tree *right; /存放又子樹(shù)的指針KeyType key; /存放節(jié)點(diǎn)的內(nèi)容 BSTNode, * B

36、STree; /聲明二叉樹(shù)的鏈表BSTree insertBST(BSTree tptr,KeyType key)/ 在二叉排序樹(shù)中插入結(jié)點(diǎn) /若二叉排序樹(shù)tptr中沒(méi)有關(guān)鍵字為key的結(jié)點(diǎn)，則插入，否則直接返回BSTree f,p=tptr; /p的初值指向根結(jié)點(diǎn)while(p) /查找插入位置，循環(huán)結(jié)束時(shí)，p是空指針，f指向待插入結(jié)點(diǎn)的雙親if(p-key=key) /樹(shù)中已有key，無(wú)須插入return tptr;f=p; /f保存當(dāng)前查找的結(jié)點(diǎn)，即f是p的雙親p=(keykey)?p-left:p-right; p=(BSTree )malloc(sizeof(BSTNode); /生

37、成新結(jié)點(diǎn)p-key=key; p-left=p-right=NULL;if(tptr=NULL) /原樹(shù)為空，新插入的結(jié)點(diǎn)為新的根tptr=p;elseif(keykey)f-left=p;elsef-right=p;return tptr;BSTree createBST()/建立二叉樹(shù) BSTree t=NULL; /根結(jié)點(diǎn)KeyType key;cinkey;while(key!=-1)t=insertBST(t,key);cinkey;return t;void inorder_btree(BSTree root)/ 中序遍歷打印二叉排序樹(shù)BSTree p=root;if(p!=NUL

38、L) inorder_btree(p-left );cout keyright );int searchBST(BSTree t,KeyType key)/查找if(key=t-key)return 1;if(t=NULL)return 0;if(keykey)return searchBST(t-left,key);elsereturn searchBST(t-right,key);BSTree deleteBST(BSTree tptr,KeyType key)/刪除 BSTree p,tmp,parent=NULL; p=tptr; while(p) if(p-key=key) brea

39、k; parent=p; p=(keykey)?p-left:p-right; if(!p) return NULL; tmp=p; if(!p-right&!p-left) /*p的左右子樹(shù)都為空*/ if(!parent) /要?jiǎng)h根，須修改根指針 tptr=NULL; else if(p=parent-right) parent-right=NULL; else parent-left=NULL; free(p); else if(!p-right) /p的右子樹(shù)為空，則重接p的左子樹(shù) p=p-left; if(!parent) /要?jiǎng)h根，須修改根指針 tptr=p; else if(tm

40、p=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(!p-left) /的左子樹(shù)為空，則重接p的左子樹(shù) p=p-right; if(!parent) /要?jiǎng)h根，須修改根指針 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(p-right&p-left) /p有左子樹(shù)和右子樹(shù)，用p的后繼覆蓋p然后刪去后繼 /另有方法：用p的前驅(qū)覆蓋p然后刪去前驅(qū)|合并p的左右子樹(shù) parent=p;

41、 /由于用覆蓋法刪根，則不必特殊考慮刪根 p=p-right; while(p-left) parent=p; p=p-left; tmp-key=p-key; if(p=parent-left) parent-left=NULL; else parent-right=NULL; free(p); return tptr;int main()KeyType key;int flag,test;char cmd;BSTree root;docouttt C.創(chuàng)建一棵二叉排序樹(shù)n;couttt E.結(jié)束本程序n;flag=0;doif(flag!=0)coutcmd;flag+; while(cm

42、d!=c&cmd!=C&cmd!=e&cmd!=E);if(cmd=c|cmd=C)cout請(qǐng)輸入你所要?jiǎng)?chuàng)建的二叉樹(shù)的結(jié)點(diǎn)的值，以-1結(jié)束：n;root=createBST();doflag=0;coutnn中序遍歷二叉樹(shù)：endl; inorder_btree(root);coutendl;couttt輸入 D 刪除你想要?jiǎng)h除的結(jié)點(diǎn)endl;doif(flag!=0)cout選擇操作錯(cuò)誤！請(qǐng)重新選擇！n;fflush(stdin);scanf(%c,&cmd);flag+;while(cmd!=d&cmd!=D);switch(cmd)case d:case D:coutkey;root=d

43、eleteBST(root,key); /注意必須將值傳回根if(root=NULL)coutn對(duì)不起，你所刪除的結(jié)點(diǎn) key 不存在!n;elsecoutn成功刪除結(jié)點(diǎn) key ;break;while(cmd!=q&cmd!=Q);while(cmd!=e&cmd!=E);return 0;六、實(shí)驗(yàn)結(jié)果1.折半查找2.二叉排序樹(shù)：實(shí)驗(yàn)五、內(nèi)部排序一、實(shí)驗(yàn)?zāi)康?、掌握排序的有關(guān)概念和特點(diǎn)。2、熟練掌握直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序、基數(shù)排序等算法的基本思想。3、關(guān)鍵字序列有序與無(wú)序，對(duì)于不同的排序方法有不同的影響，通過(guò)該實(shí)驗(yàn)進(jìn)一步加深理解。二、實(shí)驗(yàn)

44、內(nèi)容 設(shè)有關(guān)鍵字序列k= 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 ,試用各種排序算法進(jìn)行排序。三、具體要求 1、從鍵盤(pán)輸入上述8個(gè)整數(shù)，存放在數(shù)組quick8中，并輸出值。 2、輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。 3、如果上述8個(gè)整數(shù)按照升序輸入，即k1= 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 ，輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。 4、如果上述8個(gè)整數(shù)按照降序輸入，即k2= 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2，輸出各種排序算法每一趟排序的結(jié)果，

45、觀察關(guān)鍵字次序的變化。5、測(cè)試各排序算法的執(zhí)行時(shí)間，比較執(zhí)行效率。6、隨機(jī)產(chǎn)生3萬(wàn)個(gè)數(shù)，對(duì)其進(jìn)行排序，觀察其結(jié)果。四、完成情況和實(shí)驗(yàn)記錄這道題的難點(diǎn)在于不同的排序方法的比較你，單一算法是比較容易實(shí)現(xiàn)的，但是他們整合到同一個(gè)工程中，而且對(duì)他們的算法進(jìn)行分析就比較困難了。在產(chǎn)生隨機(jī)數(shù)的過(guò)程中遇到了很大的問(wèn)題，我已經(jīng)聲明了stdlib.h和time.h但是c+仍然不能識(shí)別rand函數(shù)。五、程序清單#define MAXSIZE 50 #include typedef struct int key; RECNODE; int b,t; int MakeList(RECNODE *r) int j,k;

46、 printf(n請(qǐng)輸入初始數(shù)據(jù)(每個(gè)數(shù)據(jù)以空格隔開(kāi)，-1結(jié)束）： ); k=0; scanf(%d,&j); while(j!=-1) k+; rk.key=j; scanf(%d,&j); return k; void UndealoutList(RECNODE *r,int n) int i; printf(n未排序前的數(shù)據(jù) ： ); for(i=0;in;i+) printf( %d,ri+1.key); printf(nn); void DealoutList(RECNODE*r,int n) int i; printf(排序后的數(shù)據(jù) ： ); for(i=0;in;i+) prin

47、tf( %d,ri+1.key); printf(nn); printf(交換或比較的次數(shù)： %dn,b); printf(排序的趟數(shù)： %dn,t); /直接插入排序/ void InsertSort(RECNODE*r,int n) int i,j; b=0,t=0; for(i=2;i=n;i+) r0=ri; j=i-1; while(r0.keyrj.key) rj+1=rj; j-; b+; rj+1=r0; b+; t+; /冒泡排序/ void BubleSort(RECNODE *r,int n) int i,j; b=0,t=0; RECNODE temp; for(i=1

48、;i=i;j-) if(rj+1.key=temp.key)&(ij) j-; w+; if(ij) ri=rj; i+; w+; while(ri.key=temp.key)&(ij) i+; w+; if(ij) rj=ri; j-; w+; while(i!=j); ri=temp; b=w; return i; /快速排序/ void QuickSort(RECNODE*r,int start,int end) int i; static int q=0; if(startend) i= Partition(r,&start,&end); q+; QuickSort(r,start,i-1); QuickSort(r,i+1,end); t=q; /簡(jiǎn)單選擇排序/