版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、<p> 《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》</p><p><b> 報告書</b></p><p> 2012/2013 第1學期</p><p> 專業(yè)班級:_________</p><p> 學 號:_________</p><p> 學生姓名:_________&l
2、t;/p><p><b> 計算機信息工程學院</b></p><p><b> 一.課程認識</b></p><p> 數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程,它是計算機程序設(shè)計、數(shù)據(jù)
3、庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ),廣泛的應用于信息學、系統(tǒng)工程等各種領(lǐng)域。</p><p> 學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學生的思維能力,促進學生的綜合應用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的:</p><p> 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法,具備初步的獨立分析和設(shè)計能力;<
4、/p><p> 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能;</p><p> 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力;</p><p> 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā),培養(yǎng)軟件工者所應具備的科學的工作方法和作風。</p><p><b> 二.課題選擇</
5、b></p><p><b> 1、內(nèi)部排序演示</b></p><p> ?。ㄒ唬﹩栴}描述及分析:</p><p> 設(shè)計一個測試程序比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受。(1) 對起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法進行比較;(2) 待排序的元素的關(guān)鍵字為整數(shù)。其中的數(shù)據(jù)要用
6、偽隨機產(chǎn)生程序產(chǎn)生(如10000個),至少</p><p> 用5組不同的輸入數(shù)據(jù)做比較,再使用各種算法對其進行排序,記錄其排序時間,再匯總</p><p> 比較。(gettickcount())(二)數(shù)據(jù)結(jié)構(gòu)描述: </p><p> 本程序采用順序表結(jié)構(gòu),具體結(jié)構(gòu)定義如下:</p><p> typedef struct &l
7、t;/p><p><b> {</b></p><p> ElemType *elem;</p><p> int length;</p><p><b> }SqList;</b></p><p> (三)主要算法流程描述:</p><p>&
8、lt;b> 1.主要函數(shù)流程</b></p><p> 1.void addlist(SqList &L)//初始化順序表</p><p> 2.void random(SqList &L)//隨機數(shù)產(chǎn)生程序</p><p> 3. void memory(SqList &M,SqList &L)//記錄L,
9、使每個排序算法都用一組相同的隨機數(shù)</p><p> 4. void BubbleSort(SqList &L)//冒泡排序</p><p> 5. void InsertSort(SqList &L)//直接插入排序</p><p> 6. void SelectSort(SqList &L)//選擇排序</p><
10、;p> 7. int Partition(SqList &L,int low,int high)//快速排序</p><p> 8. void QSort(SqList &L,int low,int high)//對順序表的子序列作快速排序</p><p> 9. void ShellSort(SqList &L)//希爾排序</p>&
11、lt;p> 10. void HeapAdjust(SqList &L,int s,int m )//調(diào)整L.elem[s]的關(guān)鍵字,使L.elem[s…..m]成為一個大根堆</p><p> 11. void HeapSort(SqList &L)//對順序表L進行堆排序</p><p> 12. void main()主函數(shù)</p><
12、p> 2. 主要代碼及程序說明</p><p> #include"iostream"</p><p> #include"stdio.h"</p><p> #include"stdlib.h"</p><p> #include"string.h&quo
13、t;</p><p> #include"time.h"</p><p> using namespace std;</p><p> #define LIST_INIT_SIZE 50000</p><p> int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,
14、bj5=0,yd5=0,bj6=0,yd6=0,n;//yd,bj為記錄關(guān)鍵字比較和移動的次數(shù)</p><p> typedef struct </p><p><b> {</b></p><p><b> int key; </b></p><p> }ElemType;</p&g
15、t;<p> typedef struct </p><p><b> {</b></p><p> ElemType *elem;</p><p> int length;</p><p><b> }SqList;</b></p><p> vo
16、id addlist(SqList &L)//初始化順序表</p><p><b> {</b></p><p> a: printf("請輸入你要輸入的個數(shù):");</p><p> scanf("%d",&n);</p><p> if(n>500
17、00)</p><p><b> {</b></p><p> printf("超出范圍重新輸入!!!\n");</p><p><b> goto a;</b></p><p><b> }</b></p><p> L.
18、elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));</p><p> if(!L.elem)exit(0);</p><p><b> }</b></p><p> void random(SqList &L)//隨機數(shù)產(chǎn)生程序</p><p>
19、<b> {</b></p><p> L.length=0;</p><p> static bool first=true;</p><p><b> if(first)</b></p><p><b> {</b></p><p> s
20、rand(time(0));</p><p> first=false;</p><p> }//使輸入相同個數(shù)時每次產(chǎn)生的隨機數(shù)不同</p><p> for(int i=1;i<n+1;i++)</p><p><b> a: { </b></p><p> L.elem[i
21、].key=rand();</p><p> if(L.elem[i].key>30000)</p><p><b> goto a;</b></p><p> ++L.length;</p><p><b> }</b></p><p><b>
22、}</b></p><p> void memory(SqList &M,SqList &L)//記錄L,使每個排序算法都用一組相同的隨機數(shù)</p><p><b> { </b></p><p> M.length=0;</p><p> for(int i=1;i<n+1
23、;i++)</p><p> {M.elem[i].key=L.elem[i].key;</p><p> ++M.length;</p><p><b> }</b></p><p><b> }</b></p><p> void BubbleSort(SqLi
24、st &L)//冒泡排序</p><p><b> {</b></p><p><b> int i,j;</b></p><p> for(i=1;i<L.length;i++)</p><p> {for(j=1;j<L.length-i+1;j++)</p&
25、gt;<p><b> {bj1++;</b></p><p> if(L.elem[j].key>L.elem[j+1].key)</p><p><b> {</b></p><p> L.elem[0].key=L.elem[j].key;</p><p> L.
26、elem[j].key=L.elem[j+1].key;</p><p> L.elem[j+1].key=L.elem[0].key;</p><p><b> yd1+=3;</b></p><p><b> }</b></p><p><b> }</b><
27、/p><p><b> }</b></p><p><b> }</b></p><p> void InsertSort(SqList &L)//直接插入排序</p><p><b> {</b></p><p><b> in
28、t i,j;</b></p><p> for(i=2;i<=L.length;i++)</p><p><b> {</b></p><p> if(L.elem[i].key<L.elem[i-1].key)</p><p><b> {</b></p>
29、;<p> L.elem[0].key=L.elem[i].key;</p><p><b> yd2++;</b></p><p><b> j=i-1;</b></p><p><b> bj2++;</b></p><p> while(L.ele
30、m[0].key<L.elem[j].key)</p><p><b> {</b></p><p> L.elem[j+1].key=L.elem[j].key;</p><p><b> j--;</b></p><p><b> yd2++;</b><
31、/p><p><b> bj2++;</b></p><p><b> }</b></p><p> L.elem[j+1].key=L.elem[0].key;</p><p><b> yd2++;</b></p><p><b>
32、}</b></p><p><b> }</b></p><p><b> }</b></p><p> void SelectSort(SqList &L)//選擇排序</p><p><b> {</b></p><p>
33、 int i,j,k;</p><p> for(i=1;i<L.length;i++)</p><p><b> {</b></p><p><b> k=i;</b></p><p> for(j=i+1;j<L.length;j++)</p><p&g
34、t;<b> {</b></p><p><b> bj3++;</b></p><p> if(L.elem[j].key<L.elem[k].key)k=j;</p><p><b> }</b></p><p><b> if(i!=k)<
35、/b></p><p><b> {</b></p><p> L.elem[0].key=L.elem[i].key;</p><p> L.elem[i].key=L.elem[k].key;</p><p> L.elem[k].key=L.elem[0].key;</p><p&
36、gt;<b> yd3+=3;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> int Partition(SqList &L,int low,i
37、nt high)//快速排序 </p><p><b> {</b></p><p> int pivotkey;</p><p> L.elem[0]=L.elem[low];</p><p><b> yd4++;</b></p><p> pivotkey=L
38、.elem[low].key;</p><p> while (low<high) </p><p><b> {</b></p><p><b> yd4++;</b></p><p> while(low<high&&L.elem[high].key>=
39、pivotkey)</p><p><b> --high;</b></p><p> L.elem[low]=L.elem[high];</p><p><b> bj4++;</b></p><p><b> yd4++;</b></p><p&
40、gt; while (low<high&&L.elem[low].key<=pivotkey)</p><p><b> ++low;</b></p><p> L.elem[high]=L.elem[low];</p><p><b> bj4++;</b></p>&l
41、t;p><b> yd4++;</b></p><p><b> }</b></p><p> L.elem[low]=L.elem[0];</p><p><b> yd4++;</b></p><p> return low;</p><
42、p><b> }</b></p><p> void QSort(SqList &L,int low,int high)</p><p> {//對順序表的子序列作快速排序 </p><p> int pivotloc;</p><p> if(low<high)</p>&
43、lt;p><b> {</b></p><p> pivotloc=Partition(L,low,high);</p><p> QSort(L,low,pivotloc-1);</p><p> QSort(L,pivotloc+1,high);</p><p><b> }</b&g
44、t;</p><p><b> }</b></p><p> void QuickSort(SqList &L)</p><p> {//對順序表L作快速排序</p><p> QSort(L,1,L.length);</p><p><b> }</b>&
45、lt;/p><p> void ShellSort(SqList &L)//希爾排序</p><p><b> {</b></p><p> int i,d=L.length/2,j,w=0,k;</p><p> while(w<d)</p><p><b> {&
46、lt;/b></p><p><b> w=1;</b></p><p> for(i=w;i<L.length;i=i+d)</p><p><b> {</b></p><p><b> k=i;</b></p><p> fo
47、r(j=i+d;j<L.length;j=j+d)</p><p><b> {</b></p><p> if(L.elem[i].key>L.elem[j].key)</p><p><b> {</b></p><p><b> k=j;</b><
48、;/p><p><b> bj5++;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> if(i!=k)</b></p><p><b> {</b
49、></p><p> L.elem[0].key=L.elem[i].key;</p><p> L.elem[i].key=L.elem[k].key;</p><p> L.elem[k].key=L.elem[0].key;</p><p><b> yd5+=3;</b></p>&l
50、t;p><b> }</b></p><p><b> w++;</b></p><p><b> }</b></p><p><b> d=d/2;</b></p><p><b> w=1;</b></p&g
51、t;<p><b> }</b></p><p><b> }</b></p><p> void HeapAdjust(SqList &L,int s,int m )</p><p> {//調(diào)整L.elem[s]的關(guān)鍵字,使L.elem[s…..m]成為一個大根堆</p>&
52、lt;p> SqList rc;</p><p> rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));</p><p> if(!rc.elem)exit(0);</p><p><b> int j;</b></p><p> rc.e
53、lem[0]=L.elem[s];</p><p> for(j=2*s;j<=m;j*=2)</p><p><b> {bj6++;</b></p><p> if(j<m&&L.elem[j].key<L.elem[j+1].key)</p><p><b> +
54、+j;</b></p><p><b> bj6++;</b></p><p> if(!(rc.elem[0].key<L.elem[j].key)) break;</p><p> L.elem[s]=L.elem[j];</p><p><b> s=j;</b>&l
55、t;/p><p><b> yd6+=3;</b></p><p><b> }</b></p><p> L.elem[s]=rc.elem[0];</p><p><b> }</b></p><p> void HeapSort(SqList
56、 &L)</p><p> {//對順序表L進行堆排序</p><p><b> int i;</b></p><p> for(i=L.length/2;i>0;--i)</p><p> HeapAdjust(L,i,L.length);</p><p> for(i=
57、L.length;i>1;--i)</p><p> {L.elem[1]=L.elem[i];</p><p><b> yd6+=3;</b></p><p> HeapAdjust(L,1,i-1);</p><p><b> }</b></p><p>
58、<b> }</b></p><p> void main()</p><p><b> {</b></p><p> SqList L,M;</p><p><b> int a;</b></p><p> M.elem=(ElemType
59、*)malloc(LIST_INIT_SIZE*sizeof(ElemType));</p><p> if(!M.elem)exit(0);</p><p><b> a:</b></p><p> cout<<" ---------------------------------內(nèi)部排序算法比較---------
60、--------------------\n"; cout<<"************************************歡迎使用***********************************\n";</p><p> cout<<"**********************************(1)運行程序******
61、****************************\n";</p><p> cout<<"**********************************(2)退出系統(tǒng)**********************************\n";</p><p> cout<<endl;</p><p&
62、gt; cout<<"請選擇:";</p><p> scanf("%d",&a);</p><p><b> switch(a)</b></p><p><b> {</b></p><p> case 1:system(&qu
63、ot;cls");addlist(L);break;</p><p> case 2:cout<<"謝謝使用";exit(0);break;</p><p><b> }</b></p><p> random(L);</p><p> memory(M,L);</
64、p><p> BubbleSort(M);</p><p> memory(M,L);</p><p> InsertSort(M);</p><p> memory(M,L);</p><p> SelectSort(M);</p><p> memory(M,L);</p>
65、;<p> QuickSort(M);</p><p> memory(M,L);</p><p> ShellSort(M);</p><p> memory(M,L);</p><p> HeapSort(L);</p><p> cout<<" **
66、*******比較次數(shù)**********移動次數(shù)*********\n";</p><p> cout<<"冒泡排序: "<<bj1<<" "<<yd1<<endl;</p><p> cout<<"直接插入:
67、 "<<bj2<<" "<<yd2<<endl;</p><p> cout<<"簡單選擇: "<<bj3<<" "<<yd3<<endl;</p><
68、;p> cout<<"快速排序: "<<bj4<<" "<<yd4<<endl;</p><p> cout<<"希爾排序: "<<bj5<<" "&
69、lt;<yd5<<endl;</p><p> cout<<"堆排序 : "<<bj6<<" "<<yd6<<endl;</p><p> cout<<endl;</p><p><b&g
70、t; goto a;</b></p><p><b> }</b></p><p><b> ?。ㄋ模┦褂谜f明:</b></p><p><b> 運行程序:</b></p><p><b> 選擇1:</b></p>&
71、lt;p><b> 選擇10:</b></p><p> 選擇1,重復上述步驟,分別輸入100,200得到如下結(jié)果:</p><p><b> 輸入2,退出程序:</b></p><p> 結(jié)果分析:冒泡排序,直接插入排序以及簡單選擇排序比較次數(shù)較多,快速排序,希爾排序及堆排序比較次數(shù)較少;并可得冒泡排序和直
72、接插入排序相對較穩(wěn)定,其他四種內(nèi)部排序為不穩(wěn)定排序。</p><p> 5、一元多項加法運算的實現(xiàn)</p><p> (一)問題描述及分析:</p><p> 設(shè)計一個程序,求解一元多項加法。如:A(x)=15+6x+9x7+3x18 B(x)=4x+5x6+16x7 求 A+B 。</p><p> ?。ǘ?shù)據(jù)結(jié)構(gòu)描述: &
73、lt;/p><p> 本程序采用鏈表結(jié)構(gòu),具體結(jié)構(gòu)定義如下:</p><p> typedef struct polynode </p><p><b> { </b></p><p> int coef; //多項式的系數(shù) </p><p> int exp; //指數(shù) </p>
74、;<p> struct polynode *next; </p><p><b> }node;</b></p><p> ?。ㄈ┲饕惴鞒堂枋觯?lt;/p><p><b> 1.主要函數(shù)流程</b></p><p> 1. node *create() //用尾插法建立一
75、元多項式的鏈表</p><p> 2. void print(node *p) //輸出函數(shù),打印出一元多項式</p><p> 3. void polyadd(node *ha, node *hb)//一元多項式相加函數(shù),用于將兩個多項式相加,然后將和多項式存放在多項式ha中,并將多項式hb刪除</p><p> 4. void main()主函數(shù)</
76、p><p> 2. 主要代碼及程序說明</p><p> #include<stdio.h> </p><p> #include<malloc.h> </p><p> #include<stdlib.h> </p><p> typedef struct polynode
77、</p><p><b> { </b></p><p> int coef; //多項式的系數(shù) </p><p> int exp; //指數(shù) </p><p> struct polynode *next; </p><p><b> }node; </b>&l
78、t;/p><p> node *create() //用尾插法建立一元多項式的鏈表 </p><p><b> { </b></p><p> node *h,*r,*s; </p><p><b> int c,e; </b></p><p> h=(node*)ma
79、lloc(sizeof(node)); </p><p><b> r=h; </b></p><p> printf("coef:"); </p><p> scanf("%d",&c); </p><p> printf("exp: ");
80、</p><p> scanf("%d",&e); </p><p> while(c!=0) //輸入系數(shù)為0時,多項式的輸入結(jié)束 </p><p><b> { </b></p><p> s=(node*)malloc(sizeof(node)); </p><
81、;p> s->coef=c; </p><p> s->exp=e; </p><p> r->next=s; </p><p><b> r=s; </b></p><p> printf("coef:"); </p><p> scanf
82、("%d",&c); </p><p> printf("exp: "); </p><p> scanf("%d",&e); </p><p><b> } </b></p><p> r->next=NULL; </p&g
83、t;<p> return(h); </p><p><b> } </b></p><p> void print(node *p) //輸出函數(shù),打印出一元多項式 </p><p><b> { </b></p><p> while(p->next!=NULL)
84、</p><p><b> { </b></p><p> p=p->next; </p><p> printf(" %d*x^%d",p->coef,p->exp); </p><p><b> } </b></p><p>
85、<b> } </b></p><p> void polyadd(node *ha, node *hb)//一元多項式相加函數(shù),用于將兩個多項式相加,然后將和多項式存放在多項式ha中,并將多項式hb刪除 </p><p><b> { </b></p><p> node *p,*q,*pre,*temp; &l
86、t;/p><p><b> int sum; </b></p><p> p=ha->next; </p><p> q=hb->next; </p><p><b> pre=ha; </b></p><p> while(p!=NULL&&
87、;q!=NULL) </p><p><b> { </b></p><p> if(p->exp<q->exp) </p><p><b> { </b></p><p> pre->next=p; </p><p> pre=pre-&g
88、t;next; </p><p> p=p->next; </p><p><b> } </b></p><p> else if(p->exp==q->exp) </p><p><b> { </b></p><p> sum=p->c
89、oef+q->coef; </p><p> if(sum!=0) </p><p><b> { </b></p><p> p->coef=sum; </p><p> pre->next=p;pre=pre->next;p=p->next; </p><p&
90、gt; temp=q;q=q->next;free(temp); </p><p><b> } </b></p><p> else //如果系數(shù)和為零,則刪除結(jié)點p與q,并將指針指向下一個結(jié)點 </p><p><b> { </b></p><p> temp=p->ne
91、xt;free(p);p=temp; </p><p> temp=q->next;free(q);q=temp; </p><p><b> } </b></p><p><b> } </b></p><p><b> else </b></p>
92、<p><b> { </b></p><p> pre->next=q; </p><p> pre=pre->next; </p><p> q=q->next; </p><p><b> } </b></p><p><b
93、> } </b></p><p> if(p!=NULL) //將多項式A中剩余的結(jié)點加入到和多項式中 </p><p> pre->next=p; </p><p><b> else </b></p><p> pre->next=q; </p><p>
94、;<b> } </b></p><p> void main() </p><p><b> { </b></p><p> node *ha,*hb; </p><p> printf("請輸入多項式ha的系數(shù)與指數(shù):\n"); </p><p&
95、gt; ha=create(); </p><p> print(ha); </p><p> printf("\n"); </p><p> printf("請輸入多項式hb的系數(shù)與指數(shù):\n"); </p><p> hb=create(); </p><p>
96、print(hb); </p><p> printf("\n"); </p><p> printf("多項式的和是:\n"); </p><p> polyadd(ha,hb); </p><p> print(ha); </p><p> printf("
97、;\n"); </p><p><b> }</b></p><p><b> ?。ㄋ模┦褂谜f明:</b></p><p><b> 運行程序:</b></p><p> 分別輸入多項式ha的系數(shù)和指數(shù),直到系數(shù)和指數(shù)都為0結(jié)束:</p><
98、p> 繼續(xù)輸入hb的系數(shù)和指數(shù),直到系數(shù)和指數(shù)都為0結(jié)束,于是輸出ha+hb該多項式的和::</p><p> 3. 二叉排序樹結(jié)點的插入、刪除算法的實現(xiàn)</p><p> ?。ㄒ唬﹩栴}描述及分析:</p><p> 設(shè)計一個程序,插入和刪除二叉排序樹中給定的結(jié)點,要求插入和刪除后仍然保持</p><p><b> 它
99、的有序性。</b></p><p> ?。ǘ?shù)據(jù)結(jié)構(gòu)描述: </p><p> struct node</p><p><b> {</b></p><p><b> int data;</b></p><p> struct node*lchild,*
100、rchild;</p><p><b> };</b></p><p> (三)主要算法流程描述:</p><p><b> 1.主要函數(shù)流程</b></p><p> 1. struct node *searchnode(int w,struct node *r)</p>&
101、lt;p> 2. struct node*insert(int w,struct node*p)</p><p> 3. struct node*father(struct node *p,struct node *r)</p><p> 4. struct node *dele(struct node *p,struct node *r)</p><p&g
102、t; 5. void printf(struct node *p)</p><p> 6. struct node*creat()創(chuàng)建二叉排序樹</p><p> 7. struct node*insertnode(struct node*root)插入結(jié)點</p><p> 8. struct node *delenode(struct node *roo
103、t)刪除結(jié)點</p><p> 9. void main()主函數(shù)</p><p> 2. 主要代碼及程序說明</p><p> #include"stdio.h"</p><p> #include"string.h"</p><p> #include"m
104、alloc.h"</p><p> struct node</p><p><b> {</b></p><p><b> int data;</b></p><p> struct node*lchild,*rchild;</p><p><b>
105、; };</b></p><p> struct node *searchnode(int w,struct node *r)</p><p><b> {</b></p><p> struct node *p;</p><p> if(r==NULL)</p><p>&
106、lt;b> p=NULL;</b></p><p><b> else</b></p><p><b> {</b></p><p> if(w==r->data)</p><p><b> p=r;</b></p><p&
107、gt; else if(w>r->data)</p><p> p=searchnode(w,r->rchild);</p><p><b> else</b></p><p> p=searchnode(w,r->lchild);</p><p><b> }</b&g
108、t;</p><p> return(p);</p><p><b> }</b></p><p> struct node*insert(int w,struct node*p)</p><p><b> {</b></p><p> if(p==NULL)<
109、;/p><p><b> {</b></p><p> p=(struct node*)malloc(sizeof(struct node));</p><p> p->lchild=NULL;p->rchild=NULL;p->data=w;</p><p><b> }</b&g
110、t;</p><p> else if(w>p->data) //大于欲插入值進行右子樹比較和插入</p><p> p->rchild=insert(w,p->rchild);</p><p> else //小于欲插入值
111、進行左子樹比較和插入</p><p> p->lchild=insert(w,p->lchild);</p><p> return(p); //返回根節(jié)點</p><p><b> }</b></p><p> struct node*father(struct node *p,struct nod
112、e *r)</p><p><b> {</b></p><p> struct node *p3;</p><p> if(r==NULL||p==r)</p><p><b> p3=NULL;</b></p><p><b> else </b
113、></p><p><b> {</b></p><p> if(p==r->lchild||p==r->rchild)</p><p><b> p3=r;</b></p><p> else if(p->data>r->data) </p>
114、<p> p3=father(p,r->rchild);</p><p> else p3=father(p,r->lchild);</p><p><b> }</b></p><p> return(p3);</p><p><b> }</b></p&
115、gt;<p> struct node *dele(struct node *p,struct node *r)</p><p><b> {</b></p><p> struct node*p1,*p2,*p3;</p><p> p3=father(p,r);</p><p> if(p-&
116、gt;lchild==NULL&&p->rchild==NULL&&p3!=NULL) //被刪節(jié)點是非根節(jié)點的葉子節(jié)點</p><p> if(p3->lchild==p)</p><p> p3->lchild=NULL;</p><p><b> else</b></p&
117、gt;<p> p3->rchild=NULL; //相應的父親節(jié)點的孩子指針置為空</p><p> if(p->lchild==NULL&&p->rchild==NULL&&p3==NULL)</p><p> r=NULL;
118、 //</p><p> if(p->lchild!=NULL&&p->rchild==NULL&&p3==NULL) //</p><p> r=p->lchild;</p><p> if(p->lchild==NULL&&p->rchild
119、!=NULL&&p3==NULL) //</p><p> r=p->rchild;</p><p> if(p->lchild==NULL&&p->rchild!=NULL&&p3!=NULL)</p><p> if(p3->lchild==p)</p><
120、;p> p3->lchild=p->rchild;</p><p><b> else</b></p><p> p3->rchild=p->rchild;</p><p> if(p->lchild!=NULL&&p->rchild==NULL&&p3!=NUL
121、L)</p><p> if(p3->lchild==p)</p><p> p3->lchild=p->lchild;</p><p><b> else</b></p><p> p3->rchild=p->lchild;</p><p> if(p-&
122、gt;lchild!=NULL&&p->rchild!=NULL)</p><p><b> {</b></p><p> p1=p->lchild;p3=p;</p><p> while(p1->rchild!=NULL)</p><p><b> {</b&
123、gt;</p><p><b> p3=p1;</b></p><p> p1=p1->rchild;</p><p><b> }</b></p><p> p->data=p1->data;</p><p> if(p3!=p)
124、 //p的左孩子有右節(jié)點時操作</p><p> p3->rchild=p1->lchild;</p><p><b> else</b></p><p> p3->lchild=p1->lchild;</p><p><b> }</b></p>&l
125、t;p> printf("\n");</p><p> if(r==NULL)</p><p> printf("sorry this tree is empty!");</p><p> return(r);</p><p><b> }</b></p>
126、;<p> void printf(struct node *p)</p><p><b> {</b></p><p> if(p!=NULL)</p><p><b> {</b></p><p> printf(p->lchild);</p><
127、;p> printf("%d ",p->data);</p><p> printf(p->rchild);</p><p><b> }</b></p><p><b> }</b></p><p> struct node*creat()</
128、p><p><b> {</b></p><p> struct node*root,*p;</p><p> int s,t=0;</p><p> root=NULL;</p><p> printf("if you enter 0,tree is created!"
129、);</p><p><b> do</b></p><p><b> {</b></p><p> printf("\n");</p><p> printf("please enter data");</p><p> s
130、canf("%d",&s);</p><p><b> if(s==0)</b></p><p><b> t=1;</b></p><p><b> else</b></p><p><b> {</b></p&
131、gt;<p> p=searchnode(s,root);</p><p> if(p==NULL)</p><p> root=insert(s,root);</p><p> else printf("the data exist,don't insert!\n");</p><p>&l
132、t;b> }</b></p><p> }while(!t);</p><p> return(root);</p><p><b> }</b></p><p> struct node*insertnode(struct node*root)</p><p><
133、;b> {</b></p><p><b> int s;</b></p><p> struct node*p;</p><p> printf("\n");</p><p> printf("please enter data");</p>
134、;<p> scanf("%d",&s);</p><p><b> if(s!=0)</b></p><p><b> {</b></p><p> p=searchnode(s,root);</p><p> if(p==NULL)</p
135、><p> root=insert(s,root);</p><p><b> else</b></p><p> printf("the data exist,don't insert again!\n");</p><p><b> }</b></p>
136、<p> return(root);</p><p><b> }</b></p><p> struct node *delenode(struct node *root)</p><p><b> {</b></p><p><b> int s;</b&
137、gt;</p><p> struct node*p;</p><p><b> char ch;</b></p><p> printf("please enter the deleting node'value:");</p><p> scanf("%d",&
138、amp;s);</p><p><b> if(s!=-1)</b></p><p><b> {</b></p><p> p=searchnode(s,root);</p><p> if(p==NULL)</p><p> printf("sorry
139、 the data don't exist!");</p><p><b> else</b></p><p><b> {</b></p><p> printf("the node exist ,delete?(Y/N)");</p><p> ge
140、tchar();</p><p> scanf("%c",&ch);</p><p> if((ch=='y')||(ch=='Y'))</p><p> root=dele(p,root);</p><p><b> }</b></p>
141、<p><b> }</b></p><p> return(root);</p><p><b> }</b></p><p> void main()</p><p><b> {</b></p><p> struct nod
142、e*root;</p><p> int c,t=1;</p><p> printf("1:creat sort tree\n");</p><p> printf("2:delete sort tree\n");</p><p> printf("3:insert sort tre
143、e\n");</p><p> printf("4:printf sort tree\n");</p><p><b> while(t)</b></p><p><b> {</b></p><p> printf("please enter you
144、r choice:");</p><p> scanf("%d",&c);</p><p><b> switch(c)</b></p><p><b> {</b></p><p> case 1:root=creat();break;</p&g
145、t;<p> case 2:root=delenode(root);break;</p><p> case 3:root=insertnode(root);break;</p><p> case 4:printf(root);break;</p><p> default:break;</p><p><b&g
146、t; }</b></p><p> printf("continue:>0?");</p><p> scanf("%d",&t);</p><p><b> }</b></p><p><b> }</b></p&g
147、t;<p><b> ?。ㄋ模┦褂谜f明:</b></p><p><b> 運行程序:</b></p><p><b> 輸入1:</b></p><p> 輸入一串數(shù)據(jù),到0結(jié)束:</p><p> 繼續(xù)程序,刪除結(jié)點2:</p><
148、p> 輸入4,輸出二叉排序樹排序好的數(shù)據(jù):</p><p><b> 三、總結(jié)</b></p><p> 一周的課程設(shè)計結(jié)束了,在這次的課程設(shè)計中不僅檢驗了我所學習的知識,也培養(yǎng)了我如何去把握一件事情,如何去做一件事情,又如何完成一件事情的方法和技巧,心里有一種成就感。這次課程設(shè)計,我學到了很多東西:學會了在編寫幾百行程序時如何查找錯誤,如何改錯誤;了解數(shù)
149、據(jù)結(jié)構(gòu)在編寫比較復雜的程序的重要作用鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解,提高綜合運用本課程所學知識的能力。培養(yǎng)了我選用參考書,查閱手冊及文獻資料的能力。培養(yǎng)獨立思考,深入研究,分析問題、解決問題的能力。通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試,掌握應用軟件的分析方法和工程設(shè)計方法。夠按要求編寫課程設(shè)計報告書,能正確闡述設(shè)計和實驗結(jié)果,正確繪制系統(tǒng)和程序框圖。通過課程設(shè)計,培養(yǎng)了我嚴肅認真的工作作風,逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。同時
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 (3)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 (3)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——課程設(shè)計報告模板
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 (2)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 (4)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實習報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告.doc
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 (2)
評論
0/150
提交評論