數(shù)據(jù)結構課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：22 大?。?82.06KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩21頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結構課程設計　　計算機科學與通信工程學院　　姓名： 　　學號：　　指導老師： </p&g

2、t;　　時間：2013-1-15　　目錄　　課程設計目的……………………2　　課程設計的要求…………………2　　課程設計具體內容………………2　　二叉排序樹………………2

3、　　（1）需求分析　?。?）設計說明　?。?）代碼　　（4）運行結果　?。ǘ?/p>

4、排序………………………11　?。?）需求分析　?。?）設計說明　?。?）代碼　　（4）運行結果&

5、lt;p>　　心得體會………………………22　　參考文獻………………………22　　一、課程設計目的　　課程設計是一種全面的綜合訓練，是課堂教學的延續(xù)。　　對學生數(shù)據(jù)結構知識的全面綜合訓練，把書上學到的知識用于解決實際問題、培養(yǎng)今

6、后軟件開發(fā)工作所需的動手實踐能力，包括問題分析、總體結構設計、用戶界面的設計、程序設計的基本技能和技巧，以及一整套軟件工作規(guī)范的訓練和團體協(xié)作精神的培養(yǎng)。　　二、課程設計的要求　　程序運行正確。　　報告要求：課程設計報告以書面形式和電子版

7、兩種形式提交。　　遵守誠實代碼原則。　　三、課程設計具體內容　?。ㄒ唬┒媾判驑?lt;/b>　　(1)需求分析：　　1.運行環(huán)境

8、：Microsoft Visual C++6.0　　2.程序所實現(xiàn)的功能：給出一組關鍵值，建立相應的二叉排序樹，完成：　?、俳Y點的刪除操作。要求可以實現(xiàn)刪除根節(jié)點，葉子節(jié)點以及其他任意節(jié)點的功能；　?、诓迦胍粋€新結點的操作　　③對給定的值在二叉排序樹

9、進行操作　　④隨時顯示操作的結果　　(2)設計說明：　　1.算法設計思想：運用結構體建立二叉樹，并實現(xiàn)其各個功能。二叉排序樹的輸出用中序遍歷，則按從小到大的順序依次輸出各元素。　　2.流程圖：&l

10、t;/p>　　(3)代碼：　　#include<iostream>　　using namespace std;　　struct BSTree　　{</

11、p>　　int data;　　BSTree *left;　　BSTree *right;　　};　　bool flag = false;<

12、p>　　int a[100];　　//查找操作　　BSTree *search(BSTree *r,int x)　　{　　if(r==NULL)

13、return NULL;　　else　　{　　if(r->data==x)　　return r;　　else

14、if(r->data>x)　　return search(r->left,x);　　else　　return search(r->right,x);　　}

15、;　　}BSTree* insert(BSTree *r,BSTree *s) //插入操作　　{　　BSTree *p = search(r,s->data); //首先查找樹中是否已存在此節(jié)點　　if(p==NULL)&

16、lt;p>　　{　　if(r==NULL)　　{　　r=s;　　}　　e

17、lse if(s->data<r->data)　　r->left = insert(r->left,s);　　else if(s->data>r->data)　　r->right = insert(r->right,s);<

18、p>　　}　　else　　flag = true;　　return r;　　}<p&

19、gt;　　BSTree * createBSTree(BSTree *r,int *a,int n)　　{　　int i;　　BSTree * t;　　t = r;</b&

20、gt;　　for(i=0;i<n;i++)　　{　　BSTree *s = (BSTree*)malloc(sizeof(BSTree));　　s->data=a[i];　　s-&

21、gt;left=NULL;　　s->right=NULL;　　t = insert(t,s);　　}　　return t;　　}&

22、lt;/b>　　BSTree *getFather(BSTree *r, BSTree *s)　　{　　BSTree *sf;　　if(r==NULL||r==s)

23、　sf=NULL;　　else　　{　　if(s==r->left||s==r->right)　　sf= r;</p&g

24、t;　　else if(s->data > r->data)　　sf=getFather(r->right,s);　　else　　sf=getFather(r->left,s);&l

25、t;b>　　}　　return sf;　　}　　BSTree * deleteNode(BSTree *r,BSTree *s) //刪除操作　　{</

26、p>　　BSTree *temp,*father,*sf;　　sf=getFather(r,s);　　if(s->left==NULL&&s->right==NULL&&sf!=NULL) //被刪除結點是葉子結點, 不是根結點　　if

27、(sf->left==s)　　sf->left=NULL;　　else　　sf->right=NULL;　　else if(s->left==NULL&&s->right==NULL&am

28、p;&sf!=NULL) //被刪除結點是葉子結點,又是根結點　　r=NULL;　　else if(s->left==NULL&&s->right!=NULL&&sf!=NULL)　　if(sf->left==s)&

29、lt;/p>　　sf->left=s->right;　　else　　sf->right=s->right; 　　else if(s->left==NULL&&s->right!=NULL&

30、&sf==NULL) //被刪除結點有右孩子,無左孩子.刪結點是根結點　　r=s->right;　　else if(s->left!=NULL&&s->right==NULL&&sf!=NULL) //被刪結點有左孩子,無右孩子.刪結點不是根結點　　if(

31、sf->left==s)　　sf->left=s->left;　　else　　sf->right=s->left;　　else if(s->left!=NULL&&s->rig

32、ht==NULL&&sf==NULL) //被刪結點有左孩子,無右孩子.刪結點是根結點　　r=s->left;　　else if(s->left!=NULL&&s->right!=NULL)　　{&l

33、t;p>　　temp = s->left;　　father = s;　　while(temp->right!=NULL) //找出左子樹最大的節(jié)點　　{　　father=temp;<p&

34、gt;　　temp=temp->right;　　}　　s->data = temp->data;　　if(father!=s)　　father->right = temp->left;

35、　　else　　father->left=temp->left;　　}　　if(r==NULL)　　cout<<"刪除之后，二叉排序樹為空！

36、"<<endl;　　else　　cout<<"刪除成功！"<<endl;　　return r;　　}&

37、lt;p>　　BSTree *inorder(BSTree *r)　　{　　if (r!=NULL)　　{　　inorder(r->left);<p&g

38、t;　　cout<<r->data<<" ";　　inorder(r->right);　　}　　return 0;

39、}　　int main(int argc,char * argv[])　　{　　int cases;　　cout<<"請輸入二叉樹個數(shù)：";

40、　　cin>>cases;　　cout<<endl;　　while(cases--)　　{　　int n;　　flag = fal

41、se;　　BSTree *root=NULL;　　cout<<"請輸入元素個數(shù)：";　　cin>>n;　　cout<<endl;<

42、b>　　int i;　　cout<<"請輸入這些元素：";　　for(i=0;i<n;i++)　　cin>>a[i];　　cout<<endl;

43、;　　cout<<"建立二叉排序樹!"<<endl;　　root = createBSTree(root,a,n);　　if(root!=NULL)　　{cout<<"二叉排序樹建立成功！"<<endl<<inor

44、der(root)<<endl;}　　else　　{　　cout<<"二叉排序樹建立失?。?quot;<<endl;　　return

45、 0;　　}　　cout<<"請選擇您要進行的操作(輸入括號內的字母，大小寫均可)："<<endl;　　cout<<"1.刪除(D/d)"<<endl;</p&g

46、t;　　cout<<"2.插入(I/i)"<<endl;　　cout<<"3.查找(S/s)"<<endl;　　cout<<"4.退出(E/e)"<<endl;

47、　　char s;　　cin>>s;　　while(1)　　{　　if(s=='E'||s=

48、='e')　　break;　　else if(s=='I'||s=='i')　　{　　cout<<"請輸入您要插入的值：&qu

49、ot;<<endl;　　int x;　　cin>>x;　　BSTree *p =(BSTree*)malloc(sizeof(BSTree));　　p->data =

50、 x;　　p->left = NULL;　　p->right = NULL;　　root = insert(root,p);　　if(flag==false)　　cout<<"插入成功！"

51、;<<endl<<inorder(root)<<endl;　　else　　{　　cout<<"此二叉樹中已存在此值！"<<endl;&

52、lt;p>　　flag=false;//恢復原值　　}　　}　　else if(s=='S'||s=='s')　　{&l

53、t;/p>　　cout<<"請輸入您要查找的值："<<endl;　　int x;　　cin>>x;　　BSTree *p=search(root,x);&

54、lt;/p>　　BSTree *pfather=getFather(root,p);　　cout<<"查找的值為："<<p->data<<endl;　　if(pfather!=NULL)　　cout<<"

55、;其父節(jié)點的值為："<<pfather->data<<endl;　　else　　cout<<"它是根節(jié)點，沒有父節(jié)點！"<<endl;　　if(p->left==NULL&&am

56、p;p->right==NULL)　　cout<<"它是葉子節(jié)點，沒有子節(jié)點"<<endl;　　else　　{　　if(p->left !=

57、 NULL)　　cout<<"其左兒子節(jié)點的值為："<<p->left->data<<endl;　　else　　cout<<"其左兒子節(jié)點為空！"<<endl;&l

58、t;/p>　　if(p->right != NULL)　　cout<<"其右兒子的值為："<<p->right->data<<endl;　　else　　cout<<

59、;"其右兒子節(jié)點為空！"<<endl;　　}　　}　　else if(s=='D'||s=='d')　　{<

60、/b>　　cout<<"請輸入您要刪除的節(jié)點的值："<<endl;　　int value;　　cin>>value;　　cout<<"你確定要刪除嗎？(Yy/Nn)"<&l

61、t;endl;　　char order;　　cin>>order;　　while(1)　　{　　if(order=='Y'||

62、order=='y')　　{　　BSTree * node;　　node = search(root,value);　　if(node==NULL)　　cout<<

63、"該節(jié)點不存在！"<<endl;　　else　　{BSTree *nodeDel = deleteNode(root,node);　　cout<<inorder(root)<<endl;}<

64、p>　　break;　　}　　else if(order=='N'||order=='n')　　{

65、break;　　}　　else　　{　　cout<<"命令不正確，請重新輸入！"<<endl;

66、　　cin>>order;　　}　　}　　}　　else</

67、p>　　{　　cout<<"命令有誤，請重新輸入！"<<endl;　　}　　cout<<"請選擇您要進行的操作："<<en

68、dl;　　cin>>s;　　}　　}　　system("pause");<b&

69、gt;　　return 0;　　}　　(4)運行結果　　（二）排序　　(1)需求分析：</p&

70、gt;　　1.運行環(huán)境：Microsoft Visual C++6.0　　2.程序所實現(xiàn)的功能：幾種排序算法的演示，要求給出從初始開始時的每一趟的變化情況，并對各種排序算法的排序性能作分析和比較：　?、僦苯硬迦肱判颍?lt;/b>　?、谡郯?/p>

71、插入排序；　?、勖芭菖判?；　?、芎唵芜x擇排序；　?、菘焖倥判?；　?、薅雅判?；

72、　?、邭w并排序。　　(2)設計說明：　　1.算法設計思想：運用順序表存放數(shù)據(jù)元素，7種排序算法均為順序表類的函數(shù)。主函數(shù)中，為了避免前一個排序結果的影響，采取選擇排序算法的方法，將各個排序算法分開。

73、2.流程圖：　　……　?。?）代碼：　　#include<iostream.h>　　const int maxlen=100;<p&g

74、t;　　int num=0;　　template<class type>　　class seqlist　　{　　public:<b&g

75、t;　　int len;　　type data[maxlen];　　seqlist(void);　　~seqlist(void);　　int length(void);　　void merge(seqlist&

76、lt;type> &sourcetable,seqlist<type> &mergedtable,const int left,const int mid,const int right);　　void insertionsort();　　type insert(const type &item,int i);

77、　　void selectsort();　　void halfsort();　　void bubblesort();　　void swap(type &a,type &b);　　void quicksort(int

78、 low,int high);　　void mergepass(seqlist<type> &sourcetable,seqlist<type> &mergedtable,const int len);　　void mergesort(seqlist<type> &table); </p&

79、gt;　　void print();　　void filterdown(const int start);　　void heapsort();　　};　　template<class type><

80、;/p>　　seqlist<type>::seqlist(void):len(0){}　　template<class type>　　seqlist<type>::~seqlist(void){}　　template<class type>

81、;　　int seqlist<type>::length(void)　　{return len;}　　template<class type>　　void seqlist<type>::swap(type &a,type &am

82、p;b)　　{　　type c;　　c=a;　　a=b;

83、b=c;　　}　　template<class type>　　void seqlist<type>::print()　　{<

84、;p>　　for(int x=0;x<len;x++)　　cout<<data[x]<<" ";　　cout<<endl;　　}　　template<clas

85、s type>　　void seqlist<type>::halfsort()　　{　　type temp;　　int left,right;　　for(int i=1;i&

86、lt;len;i++)　　{　　left=0;　　right=i-1;　　temp=data[i];　　while (left<=right)<

87、;/p>　　{　　int mid=(left+right)/2;　　if (temp<data[mid])　　right=mid-1;　　else left=mid+1;<

88、;p>　　}　　for(int k=i-1;k>=left;k--)　　data[k+1]=data[k];　　data[left]=temp;　　cout<<"第"<<++nu

89、m<<"趟折半插入排序:";　　for(int x=0;x<len;x++)　　cout<<data[x]<<" ";　　cout<<endl;　　}<

90、/b>　　num=0;　　}　　template<class type>　　void seqlist<type>::selectsort()&

91、lt;p>　　{　　int k;　　for(int i=0;i<len-1;i++)　　{　　k=i;<

92、;/p>　　for(int j=i+1;j<len;j++)　　if (data[j]<data[k])　　k=j;　　if(k!=i)　　swap(dat

93、a[i],data[k]);　　cout<<"第"<<i+1<<"趟選擇排序:";　　print();　　}<b

94、>　　}　　template<class type>　　void seqlist<type>::quicksort(int low,int high)　　{　　int i=low,j=

95、high;static int a=1;　　type temp=data[low];　　if(i<j)　　{　　while(i<j)<b

96、>　　{　　while(i<j&&temp<data[j])　　j--;　　if(i<j)　　{&

97、lt;/p>　　data[i]=data[j];　　i++;　　}　　while(i<j&&temp>=data[i])

98、　i++;　　if(i<j)　　{　　data[j]=data[i];　　j--;<

99、b>　　}　　}　　data[i]=temp;　　cout<<"第"<<a++<<"趟快速排序:";　　pr

100、int();　　quicksort(low,i-1);　　quicksort(i+1,high);　　}　　}　　template&l

101、t;class type>　　void seqlist<type>::bubblesort()　　{　　int i=1;　　int finish=0;&l

102、t;p>　　while(i<len&&!finish)　　{　　finish=1;　　for(int j=0;j<len-i;j++)　　if(data[j]&g

103、t;data[j+1])　　{swap(data[j],data[j+1]);　　finish=0;　　}　　cout<<"第"<<++num<

104、<"趟冒泡排序:";　　for(int x=0;x<len;x++)　　cout<<data[x]<<" ";　　cout<<endl;　　i++;</b&g

105、t;　　}　　num=0;　　}　　template<class type>　　void seqlist

106、<type>::merge(seqlist<type> &sourcetable,seqlist<type> &mergedtable,const int left,const int mid,const int right)　　{　　int i=left,j=m

107、id+1,k=left;　　while(i<=mid&&j<=right)　　if(sourcetable.data[i]<=sourcetable.data[j])　　{　　mergedtable.

108、data[k]=sourcetable.data[i];　　i++;　　k++;　　}　　else

109、　　{　　mergedtable.data[k]=sourcetable.data[j];　　j++;　　k++;　　}

110、　　if(i<=mid)　　for(int p=k,q=i;q<=mid;p++,q++)　　mergedtable.data[p]=sourcetable.data[q];　　else for (int p=k,q=j;q<=rig

111、ht;p++,q++)　　mergedtable.data[p]=sourcetable.data[q];　　}　　template<class type>　　void seqlist<type>::merge

112、pass(seqlist<type> &sourcetable,seqlist<type> &mergedtable,const int len)　　{　　int i=0;　　while (i+2*

113、len<=length()-1)　　{　　merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);　　i+=2*len;　　}

114、　　if (i+len<=length()-1)　　merge(sourcetable,mergedtable,i,i+len-1,length()-1);　　else for(int j=i;j<=length()-1;j++)　　mer

115、gedtable.data[j]=sourcetable.data[j];　　if(len<=length()-1)　　{if(num<length())　　{　　cout<<"第"<

116、<++num<<"趟歸并排序結果為:";　　for(int t=0;t<length();t++)　　cout<<mergedtable.data[t]<<" ";　　cout<<endl;

117、　　}　　}　　}　　template<class type>　　void seqlist<type>::merg

118、esort(seqlist<type> &table)　　{　　seqlist<type> temptable;　　int len=1;　　while(len<table.length())<

119、;/p>　　{　　mergepass(table,temptable,len);　　len*=2;　　mergepass(temptable,table,len);&l

120、t;b>　　len*=2;　　}　　}　　template<class type>　　void seqlist<type>::insertions

121、ort()　　{　　type temp;　　int j;　　for(int i=1;i<len;i++)　　{

122、　　temp=data[i];　　j=i;　　while(j>0&&data[i]<data[j-1])　　{　　data[j

123、]=data[j-1];　　j--;　　}　　data[j]=temp;　　cout<<"第"<<i<<"趟直接插入排序:&quo

124、t;;　　print();　　}　　}　　template <class type>　　void seq

125、list<type>::filterdown(const int start)　　{　　int i=start,j=2*i+1;　　int tablesize=len;　　type temp=data[i];</p&

126、gt;　　while(j<=len-1)　　{　　if(j<len-1 && data[j]<data[j+1])　　j++;　　if(te

127、mp>=data[j])break;　　else{data[i]=data[j];i=j;j=2*j+1;　　}　　}　　data[i]=temp;

128、　　}　　template <class type>　　void seqlist<type>::heapsort()　　{　　int tablesize=len;</

129、p>　　for(int i=(len-2)/2;i>=0;i--)　　filterdown(i); 　　for(i=len-1;i>=1;i--)　　{　　swap(data[0],

130、data[i]);　　len--;　　filterdown(0);　　cout<<"第"<<++num<<"趟堆排序結果為:";　　for(int x=0;x

131、<tablesize;x++)　　cout<<data[x]<<" ";　　cout<<endl;　　}　　num=0;</p

132、>　　len=tablesize;　　}　　#include<iostream.h>　　#include"seqlist.h"　　int main()

133、　　{　　int a=1;　　while(a!=0)　　{　　int m;&

134、lt;p>　　cout<<"選擇排序類型"<<endl<<"1 冒泡排序"<<endl<<"2 快速排序"<<endl<<"3 直接插入排序"<<endl;　　cout<<"4 折半插入排序&q

135、uot;<<endl<<"5 堆排序"<<endl<<"6 選擇排序"<<endl<<"7 歸并排序"<<endl<<"0 退出排序"<<endl;　　cout<<"請選擇:";

136、　　int choice;　　cin>>choice;　　if (choice==0)　　{　　cout<<"退出"<<endl;<

137、;/p>　　return 0;　　}　　if(choice<0||choice>7)cout<<"請從0-7中選擇一個正確的數(shù)字完成排序！"<<endl;

138、　　else　　{　　seqlist<int> be;　　cout<<"輸入待排序數(shù)的總個數(shù):";　　cin>>m;<

139、;/b>　　cout<<"輸入待排序數(shù)，用空格隔開:";　　for(int i=0;i<m;i++)　　cin>>be.data[i];　　be.len=m;

140、　　switch(choice)　　{　　case 1:　　cout<<"冒泡排序:"<<endl;　　be.bubblesor

141、t();　　break;　　case 2:　　cout<<"快速排序:"<<endl;　　be.quicksort(0,m-1);

142、　　break;　　case 3:　　cout<<"直接插入排序:"<<endl;　　be.insertionsort();<

143、b>　　break;　　case 4:　　cout<<"折半插入排序:"<<endl;　　be.halfsort();　　break;</b

144、>　　case 5:　　cout<<"堆排序:"<<endl;　　be.heapsort();　　break;<p&

145、gt;　　case 6:　　cout<<"選擇排序:"<<endl;　　be.selectsort();　　break;　　case

146、7:　　cout<<"歸并排序:"<<endl;　　be.mergesort(be);　　break;　　}

147、　　}　　}　　return 0;　　}　?。?）運行結果

148、　　四、心得體會　　剛開始做課程設計的時候認為這個很簡單，書上大部分的代碼都有，直接輸入到電腦里就可以運行了。但是做起來遠比想象的復雜，因為c++學完半年，許多基礎知識都忘了，只好重新拾起一些零碎的知識點慢慢改錯。　　我選的兩個題目分別是排序和二叉排序樹。二叉排序樹比較簡單，只要建立一個二叉樹并按順序存入即可，再根據(jù)

149、二叉樹特點進行插入、刪除和查找，然后用中序遍歷將其輸出。排序則比較復雜，每一個排序算法共用一個順序表類，很容易出錯，而且剛開始的錯相當多，通過請教老師以及和同學討論才一步步的將程序調試好。　　總之，這一周的課程設計，不僅讓我重拾了c++的一些知識點，而且鞏固了這學期的數(shù)據(jù)結構知識，收獲很大。即使其間錯誤多到差點放棄，但運行結果出來的時候一切都很值得！&l

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載