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

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

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

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

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

5、num); /生成單鏈表 ListPrint(L); while(flag) printf(請選擇:n); printf(1.顯示所有元素n); /顯示鏈表元素 printf(2.插入一個元素n); /插入鏈表元素 printf(3.刪除一個元素n); /刪除鏈表元素 printf(0.退出程序 n); /退出 scanf( %c,&j); switch(j) case 1:ListPrint(L); break; case 2:printf(請輸入數(shù)據(jù)和要插入的位置-1:n);printf(格式：數(shù)據(jù)，位置；例如:12,3，（即把12插入到第3個位置之后，即第4個位置）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(請輸入要刪除的元素所在位置-1：（輸入2，即刪除的是第3個元素）:); scanf(%d,&loc); /輸入要刪除的節(jié)點的位置 temp=ListDelete(L,loc,ch); /刪除 if(temp=False)printf(刪除失敗!n); /刪除失敗 else

7、 printf(成功刪除了一個元素:%dn,ch); /刪除成功，顯示該元素 ListPrint(L); break; default:flag=0;printf(程序結(jié)束，按任意鍵退出!n); getchar();void CreatList(LinkList &v,int n)/生成一個帶頭結(jié)點的有n個元素的單鏈表 int i; LinkList p; v=(LinkList)malloc(LEN); /生成頭結(jié)點 v-next=NULL; printf(請輸入%d個數(shù)據(jù)：例如：1 2 3n,n); getchar(); for(i=n;i0;-i) p=(LinkList)malloc(

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

9、t=s; return True;BOOL ListDelete(LinkList &v,int i,int e)/在單鏈表中刪除第i個元素，成功刪除返回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)的運行結(jié)果實驗二 棧、隊列算法設(shè)計一、實驗?zāi)康?、 熟悉棧這種特殊線性結(jié)構(gòu)的特性；2、 熟練掌握棧在順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)下的基本運算；3、 熟悉隊列這種特殊線性結(jié)構(gòu)的特性；4、 熟練掌握隊列在鏈表存儲結(jié)構(gòu)下的基本運算。二、實驗內(nèi)容1、動態(tài)創(chuàng)建棧和隊列2、實現(xiàn)實現(xiàn)棧和隊列中元素的插入。3、實現(xiàn)實現(xiàn)棧和隊列中元素的的刪除。三、具體要求1、用順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)分別實現(xiàn)

11、棧的初始化、求長度、獲取棧頂元素、壓棧、出棧、判空、置空等操作，生成sqStack.h文件和LinkStack.h文件；編寫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存儲分配失敗!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、進棧(單個元素）endl;cout3-元素出棧endl;cout4-讀取棧頂元素endl;cout5-得到棧中元素個數(shù)endl;cout6-清空棧endl;cout0-退出endl;cout請輸入操作：;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棧中元素個數(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); /建立一個節(jié)點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(鏈棧為空，無棧頂元素！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é)束程序運行 n);printf(n=n);printf(請輸入您的選擇(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ù)的個數(shù)：n=);scanf(%d,&n);printf(依次將%d個數(shù)據(jù)壓入鏈棧：n,n);for(i=1;i=n;i+)printf(請輸入第%d個數(shù)據(jù)：,i);scanf(%d,&a);Push(s,a);Disp(s);break;case 3:printf(n出棧操作開始!n);printf(輸入將要出棧的數(shù)據(jù)個數(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)酱鎯Φ年犃校?include #define MAXSIZE 40 /隊列的最大長度#define QueueElementType int#define TRUE 1#define FALSE 0typedef structQueueElementType elementMAXSIZE; /隊列的元素空間 int front; int rear ; SeqQueue;void InitQueue(SeqQueue * Q) /將*Q初始化

23、為一個空的循環(huán)隊列 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入隊 if(Q-rear+1)%MAXSIZE=Q-front) /隊列已經(jīng)滿了 return

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

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

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

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

28、都有對應(yīng)的碼符，所以不能用他們來終止輸入，而用的是結(jié)束符#號。而且在運行程序的時候要注意輸入的格式，而且要先自己畫圖，看能否構(gòu)成一顆二叉樹。五、程序清單#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é)點個數(shù)為：%d,sum);五、輸入的數(shù)據(jù)及所得結(jié)果：實驗四、折半查找和二叉排序樹一、實驗?zāi)康?、掌握查找的特點。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序樹的特點，掌握二叉排序樹的插入、刪除操作。二、實驗內(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)造二叉排序樹，并完成刪除關(guān)鍵字53和24的操作。三

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

33、、從鍵盤上輸入六個整數(shù)45、24、53、12、37、9構(gòu)造二叉排序樹3、輸出其中序遍歷結(jié)果。4、刪除數(shù)據(jù)元素24，輸出其中序遍歷結(jié)果。5、刪除數(shù)據(jù)元素53，輸出其中序遍歷結(jié)果。三、完成情況和實驗記錄這道題相對來說在程序方面這邊較簡單一點，以數(shù)組的形式來進行折半查找，并進行插入和刪除操作。四、程序清單折半查找：# include # define N 8main()int i,number,top,bott,mid,loca,aN,flag=1,sign=1;char c;printf(請輸入一個有序數(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(請輸入查找元素:);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;二叉排序樹：#include#include#includetypedef int KeyType;typedef struct tree/聲明樹的結(jié)構(gòu) struct tree *left; /存放左子樹的指針struct tree *right; /存放又子樹的指針KeyType key; /存放節(jié)點的內(nèi)容 BSTNode, * B

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

37、成新結(jié)點p-key=key; p-left=p-right=NULL;if(tptr=NULL) /原樹為空，新插入的結(jié)點為新的根tptr=p;elseif(keykey)f-left=p;elsef-right=p;return tptr;BSTree createBST()/建立二叉樹 BSTree t=NULL; /根結(jié)點KeyType key;cinkey;while(key!=-1)t=insertBST(t,key);cinkey;return t;void inorder_btree(BSTree root)/ 中序遍歷打印二叉排序樹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的左右子樹都為空*/ if(!parent) /要刪根，須修改根指針 tptr=NULL; else if(p=parent-right) parent-right=NULL; else parent-left=NULL; free(p); else if(!p-right) /p的右子樹為空，則重接p的左子樹 p=p-left; if(!parent) /要刪根，須修改根指針 tptr=p; else if(tm

40、p=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(!p-left) /的左子樹為空，則重接p的左子樹 p=p-right; if(!parent) /要刪根，須修改根指針 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(p-right&p-left) /p有左子樹和右子樹，用p的后繼覆蓋p然后刪去后繼 /另有方法：用p的前驅(qū)覆蓋p然后刪去前驅(qū)|合并p的左右子樹 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)建一棵二叉排序樹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請輸入你所要創(chuàng)建的二叉樹的結(jié)點的值，以-1結(jié)束：n;root=createBST();doflag=0;coutnn中序遍歷二叉樹：endl; inorder_btree(root);coutendl;couttt輸入 D 刪除你想要刪除的結(jié)點endl;doif(flag!=0)cout選擇操作錯誤！請重新選擇！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對不起，你所刪除的結(jié)點 key 不存在!n;elsecoutn成功刪除結(jié)點 key ;break;while(cmd!=q&cmd!=Q);while(cmd!=e&cmd!=E);return 0;六、實驗結(jié)果1.折半查找2.二叉排序樹：實驗五、內(nèi)部排序一、實驗?zāi)康?、掌握排序的有關(guān)概念和特點。2、熟練掌握直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序、基數(shù)排序等算法的基本思想。3、關(guān)鍵字序列有序與無序，對于不同的排序方法有不同的影響，通過該實驗進一步加深理解。二、實驗

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

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

46、 printf(n請輸入初始數(shù)據(jù)(每個數(shù)據(jù)以空格隔開，-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; /簡單選擇排序/