第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—綜合排序
東華理工大學(xué)
東華理工大學(xué) 課程設(shè)計(jì)報告
課程設(shè)計(jì)題目： 綜合排序的設(shè)計(jì)
學(xué)生姓名：何楊 班
級：1223202 專
業(yè)：信息與計(jì)算科學(xué) 指導(dǎo)教師：郭樹蕻
2014年 12 月 13 日
東華理工大學(xué)
目錄
摘要..............................................................2
一、題目的內(nèi)容及要求-----------------4
二、需求分析------------------------------4
三、概要設(shè)計(jì)------------------------------5 四、四種排序源代碼詳細(xì)設(shè)計(jì)--------5
五、程序輸出的結(jié)果-------------------10
六、運(yùn)行結(jié)果及分析-------------------12
七、收獲及體會-------------------------13
八、參考文獻(xiàn)-----------------------------1
東華理工大學(xué)
摘 要
數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示；此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算才有意義。在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)有的算法有很多種，其中包含冒泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有其特點(diǎn)。對排序算法比較的分析可以遵循若干種不同的準(zhǔn)則，通常以排序過程所需要的算法步數(shù)作為度量，有時也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當(dāng)作一次鍵比較需要較長時間，例如，當(dāng)鍵是較長的字符串時，常以鍵比較次數(shù)作為排序算法計(jì)算時間復(fù)雜性的度量。當(dāng)排序時需要移動記錄，且記錄都很大時，還應(yīng)該考慮記錄的移動次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復(fù)雜性的度量。
關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)；算法比較；比較次數(shù)；時間復(fù)雜度
東華理工大學(xué)
一、題目的內(nèi)容及要求
排序綜合
利用隨機(jī)函數(shù)產(chǎn)生N個隨機(jī)整數(shù)（20000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：
(1)至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。
(2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。
(3)如果采用4種或4種以上的方法者，可適當(dāng)加分。
二、需求分析
2.1 問題描述
此次的任務(wù)要求是輸入20000個以上的隨機(jī)整數(shù)，對這些數(shù)進(jìn)行多種方法進(jìn)行排序。（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。
約束：程序可由用戶自行設(shè)定排序數(shù)的個數(shù)，但排序數(shù)具體值需要由計(jì)算機(jī)生成，然后用三種以上的排序方法對隨機(jī)數(shù)組進(jìn)行排序，每一種排序方法執(zhí)行后需統(tǒng)計(jì)出數(shù)據(jù)移動次數(shù)以判斷排序方法的對比隨機(jī)數(shù)組的執(zhí)行優(yōu)劣性。另：用戶自行算出每一種排序方法的時間復(fù)雜度與空間復(fù)雜度。
2.2 基本要求
2.2.1輸入的形式和輸入值的范圍；
設(shè)定的隨機(jī)數(shù)據(jù)的范圍為20000以上，用戶自定義隨機(jī)數(shù)的個數(shù)n，隨機(jī)數(shù)的數(shù)據(jù)類型均為整形。
2.2.2輸出的形式；
程序是以一個完整的有序數(shù)組來進(jìn)行輸出。
2.2.3程序所達(dá)到的功能：
將一個無序數(shù)組進(jìn)行排序隨機(jī)生成20000以上個隨機(jī)整數(shù)，對這些數(shù)進(jìn)行多種方法進(jìn)行排序。分別采用以下方法實(shí)現(xiàn)上述問題求解（可采用的方法有簡單排序、希爾排序、冒泡排序、快速排序這四種排序方法）。
東華理工大學(xué)
三、概要設(shè)計(jì)
3.1可排序表的抽象數(shù)據(jù)類型定義：
typedef int KeyType;//關(guān)鍵字為整型 typedef int OtherType;//關(guān)鍵字為整型
typedef struct { KeyType key;//關(guān)鍵字為KeyType型 OtherType other_data;}RecordType;//定義一個RecordType型結(jié)構(gòu)體，存放關(guān)鍵字 void quicksort(RecordType a[],int left,int right)//快速排序 void bubbleSort(RecordType a[],int length)//冒泡排序 void shellSort(RecordType a[],int n)//希爾排序
void BinSort(RecordType r[], int length)//折半插入排序 void main()//主函數(shù)運(yùn)行入口 四、四種排序源代碼詳細(xì)設(shè)計(jì)：
4.1快速排序模塊：
void quicksort(RecordType a[],int left,int right){ RecordType t;int i,j,temp;
if(left>right)
return;
temp=a[left].key;
i=left;
j=right;
while(i!=j)
{
while(a[j].key>=temp && i j--; while(a[i].key<=temp && i 東華理工大學(xué) i++; if(i { t=a[i]; a[i]=a[j]; a[j]=t; } } a[left] = a[i]; a[i].key = temp; quicksort(a,left,i-1);//繼續(xù)處理左邊的，這是一個遞歸的過程 quicksort(a,i+1,right);//繼續(xù)處理右邊的，這是一個遞歸的過程 } /* 快速排序算法 */ 4.2冒泡排序模塊： //此處是一次冒泡排序過程，在主函數(shù)中會通過循環(huán)調(diào)用此冒泡函數(shù)過程 void bubbleSort(RecordType a[],int length){ int i,temp; for(i=1;i { if(a[i].key>a[i+1].key) { temp = a[i].key; a[i].key=a[i+1].key; a[i+1].key=temp; } } }/* 冒泡排序算法 */ 4.3希爾排序模塊： void shellSort(RecordType a[],int n){ int i, j, temp; int gap = 0; while(gap<=n)//根據(jù)待排序的個數(shù)生成合適的步長，gap是步長 { gap = gap * 3 + 1; 東華理工大學(xué) } } while(gap > 0){ for(i = gap;i < n;i++){ j = igap; } a[j+gap+1].key = temp;} gap =(gap-1)/ 3;} 4.4希爾折半插入排序模塊： /*折半插入排序法*/ void BinSort(RecordType r[], int length)/*對記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長度*/ { int i,j;RecordType x;int low,high,mid;for(i=2;i<=length;++i) { x= r[i]; low=1;high=i-1; while(low<=high) /* 確定插入位置*/ { mid=(low+high)/ 2; if(x.key< r[mid].key) high=mid-1; else low=mid+1; } for(j=i-1;j>= low;--j) r[j+1]= r[j]; /* 記錄依次向后移動 */ r[low]=x; /* 插入記錄 */ } }/*BinSort*/ 東華理工大學(xué) 4.5主函數(shù)模塊： void main(){ int n,i,j,t; char b; bool q=false; RecordType a[40000]; while(1) { printf(“nn”);printf(“ ************** 綜 合 排 序*****************************nn”); printf(“ *********************菜 單***************************nn”);printf(“ * ========= * n”); printf(“ * 1.讀 取 待排序長度 * n”); printf(“ * 2.產(chǎn)生隨機(jī)數(shù)并輸出 * n”); printf(“ * 3.采用快速排序法排序 * n”); printf(“ * 4.采用冒泡排序法排序 * n”); printf(“ * 5.采用希爾排序法排序 * n”); printf(“ * 6.采用折半插入排序法排序 * n”); printf(“ * 7.輸 出 * n”);printf(“ * 0.退 出 系 統(tǒng) * n”);printf(“ *------------------------* n”); printf(“ ”); b = getch(); switch(b) { case '1': printf(“%cn”,b); printf(“請輸入待排序記錄的長度：”); scanf(“%d”,&n);break; 東華理工大學(xué) case '2': printf(“%cn”,b); srand((unsigned)time(NULL)); printf(“下面隨機(jī)生成%d個數(shù)字存儲在數(shù)組中n”,n); for(i=1;i<=n;i++) { a[i].key = rand()%20000; printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } printf(“n”); break; case '3': printf(“%cn”,b); printf(“n -----------------快速排序結(jié)束------------------- nn”); quicksort(a,1,n); q=true;break; case '4': printf(“%cn”,b); for(i=0;i { bubbleSort(a,n-i); } printf(“n -----------------冒泡排序結(jié)束------------------- nn”); q=true;break; case '5': printf(“%cn”,b); printf(“n -----------------希爾排序結(jié)束------------------- nn”); shellSort(a,n); q=true;break; case '6': printf(“%cn”,b); BinSort(a,n); printf(“n -----------------折半插入排序結(jié)束-------------------nn”); q=true;break; case '7': printf(“%cn”,b); 東華理工大學(xué) if(q) { printf(“n -----------------排序后輸出------------------- n”); for(i=1;i<=n;i++) { printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } } else { printf(“n * ========= * n”); printf(“ * 您未對待排序數(shù)據(jù)排序 * n”); printf(“ * 請重新選擇排序的序號 * n”); printf(“ *------------------------* n”); } break; case '0': printf(“%cn”,b); printf(“n 感謝使用綜合排序程序n 按任意鍵退出......n”); return;break; default:printf(“nn”); } } } 五、程序輸出的結(jié)果： 5.1輸入和輸出： (1)主函數(shù)運(yùn)行的輸出結(jié)果： 東華理工大學(xué) (2)選擇1，讀取待排序長度（這里以20000為例）： (3)選擇2，產(chǎn)生隨機(jī)數(shù)并輸出： (4)選擇3，采用快速排序法排序： 東華理工大學(xué) （選擇4、5、6的其他排序法的輸出雷同，此處就不再重復(fù)）(5)選擇7，輸出排序結(jié)果： 六、運(yùn)行結(jié)果及分析 6.1各算法的比較方法 1.穩(wěn)定性比較 折半插入排序、冒泡排序是穩(wěn)定的希爾排序、快速排序是不穩(wěn)定的 2.時間復(fù)雜性比較 折半插入排序、冒泡排序的時間復(fù)雜性為O(n2)其它非線形排序的時間復(fù)雜性為O(nlog2n)3.輔助空間的比較 東華理工大學(xué) 線形排序的輔助空間為O(n),其它排序的輔助空間為O(1);4.其它比較 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達(dá)到較快的速度。 反而在這種情況下，快速排序反而慢了。 當(dāng)n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。 當(dāng)n較大時，關(guān)鍵字元素比較隨機(jī)，對穩(wěn)定性沒要求宜用快速排序。 七、收獲及體會 根據(jù)四種排序法的基礎(chǔ)理論實(shí)際性模仿和編寫算法程序，很是困難，算法是程序的靈魂，數(shù)據(jù)結(jié)構(gòu)確是算法的基礎(chǔ)，但是不斷的實(shí)踐也是一種進(jìn)步的好途徑。這次課程設(shè)計(jì)主要是對基礎(chǔ)知識的靈活應(yīng)用，這就讓我進(jìn)一步提高了對數(shù)結(jié)構(gòu)知識的鞏固。這次設(shè)計(jì)的完成，困難是少不了的，還有很多其它的難題讓我都不知道所措，但是通過努力最終解決他們讓我體會到成就感，更重要的是我的能力在實(shí)踐中得到了提升和優(yōu)化，特別是對常用的排序算法的應(yīng)用，這對我以后從事軟件應(yīng)用程序開發(fā)是有很大的幫助的。這次課程設(shè)計(jì)的心得體會通過實(shí)習(xí)我的收獲如下 1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識的能力。 2、培養(yǎng)了我選用參考書，查閱手冊及文獻(xiàn)資料的能力。培養(yǎng)獨(dú)立思考，深入研究，分析問題、解決問題的能力。 3、通過實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。 4、通過課程設(shè)計(jì)，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟(jì)觀念和全局觀念。根據(jù)我在實(shí)習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點(diǎn)： 1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。 2、寫程序的過程中要考慮周到，嚴(yán)密。 3、在做設(shè)計(jì)的時候要有信心，有耐心，切勿浮躁。 4、認(rèn)真的學(xué)習(xí)課本知識，掌握課本中的知識點(diǎn)，并在此基礎(chǔ)上學(xué)會靈活運(yùn)用。 5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。我通過課程設(shè)計(jì)建立系統(tǒng)設(shè)計(jì)的整體思想，鍛煉編寫程序、調(diào)試程序的能力，學(xué)習(xí)文檔編寫規(guī)范，培養(yǎng)獨(dú)立學(xué)習(xí)、吸取他人經(jīng)驗(yàn)，樹立團(tuán)隊(duì)協(xié)作精神。同時，充分彌補(bǔ)了課堂教學(xué)及普通實(shí)驗(yàn)中知識深度與廣度有限的缺陷，更好地幫助從全局角度把握 東華理工大學(xué) 課程體系，并且可以將理論與實(shí)際聯(lián)系。在課程設(shè)計(jì)的過程中不僅僅是書本上的知識，這便促使我去查閱更多的課外資料來充實(shí)自己的內(nèi)容，同時學(xué)會在面對困難時要耐心得分析它細(xì)心得解決它以及通過合作更完美得深入了解剖析它以便得到提高。細(xì)心、耐心、團(tuán)結(jié)、求知，是我這次課程設(shè)計(jì)最大的收獲。同時要感謝老師這幾天的悉心教導(dǎo)。 八、參考文獻(xiàn) [1] 啊哈磊，《啊哈！算法》，人民郵電出版社，2014-6-1 [2] 劉艷飛，《C語言范例開發(fā)大全》清華大學(xué)出版社，2010 [3] 嚴(yán)蔚敏，吳偉民。數(shù)據(jù)結(jié)構(gòu)。北京：清華大學(xué)出版社，2001 查找及排序算法實(shí)現(xiàn) 一、實(shí)驗(yàn)?zāi)康?/p> 1、熟練掌握二叉排序樹查找算法及C語言描述。 2、熟練掌握折半查找算法及C語言描述。 3、熟練掌握簡單選擇排序算法及C語言描述。 4、熟練掌握簡單插入排序算法及C語言描述。 5、熟練掌握冒泡（起泡）排序算法及C語言描述。 6、了解各種查找及排序算法的優(yōu)缺點(diǎn)、實(shí)用性及應(yīng)用。 7、將理論與實(shí)際相結(jié)合，切實(shí)提高自己的邏輯能力和動手能力。 二、設(shè)計(jì)內(nèi)容 1.折半查找算法 折半查找算法的思路： 初始狀態(tài)：假設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的下界、上界和中點(diǎn),key為給定值，初始時，令low=0,high=n-1,mid=(low+high)/2 讓key與mid指向的記錄比較 若key==r[mid].key，查找成功,算法結(jié)束；若key 起泡排序的思路： 首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較【第二個記錄和第三個記錄】的關(guān)鍵字。以此類推，直至第n-1個記錄和第n個記錄的關(guān)鍵字進(jìn)行過比較為止。上述過程稱做第一趟起泡排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個記錄的位置上，然后進(jìn)行第二趟起泡排序，對前n-1個記錄進(jìn)行同樣操作，其結(jié)果是使關(guān)鍵字次大的記錄被安置到第n-1個記錄的位置上。一般地，第i躺起泡排序是從L.r[1]到L.r[n-i+1]以此比較相鄰兩個記錄的關(guān)鍵字，并在“逆序”時交換相鄰記錄，其結(jié)果是這n-i+1個記錄中關(guān)鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進(jìn)行k(1<=k 首先以一個元素為基準(zhǔn)，從一個方向開始掃描，比如從左至右掃描，以a[0]為基準(zhǔn)，接下來從a[0]...a[9] 中找出最小的元素，將其與a[0]交換，然后將基準(zhǔn)位置右 移一位，重復(fù)上面的動作，比如，以a[1]為基準(zhǔn)，找出a[1]至a[9]中最小的，將其與a[1]交換，一直進(jìn)行到基準(zhǔn)位置移到數(shù)組最后一個元素時排序結(jié)束（此時基準(zhǔn)左邊所有元素均遞增有序，而基準(zhǔn)為最后一個元素，故完成排序）。4.直接插入排序算法 直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數(shù)增1的有序表。 一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1...i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r[1....i].在自i-1起往前搜索的過程中，可以同時后移記錄。 整個排序過程為進(jìn)行n-1躺插入，即：先將序列中的第一個記錄看成是一個有序的子序列，然后從第二個記錄起逐個進(jìn)行插入，直至整個序列變成按關(guān)鍵字非遞減有序序列為止 三、程序源代碼 1.二叉排序樹的創(chuàng)建、遍歷和查找刪除算法 #include void Insert(Tree &T,KeyType key){ if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else } { } if(key } int num;char c;while(scanf(“%d”,&num)){ } Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍歷 { if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){ Tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){ } if(!T){ printf(“n該結(jié)點(diǎn)不存在n”);return;} else { } if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序樹查找 { if(!T){ } printf(“該結(jié)點(diǎn)不存在”);return 0;else if(key == T->data)return T;else if(key < T->data) return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函數(shù) { Tree T,p;T=NULL;KeyType x; printf(“請輸入二叉樹各結(jié)點(diǎn)：n”); CreatTree(T); printf(“中序遍歷為：n”);In_Order(T);printf(“n請輸入要查找和刪除的結(jié)點(diǎn)：n”);scanf(“%d”,&x);p=Search(T, x);if(p){ } DelNode(T, x);printf(“中序遍歷為：n”);In_Order(T); } 2、冒泡排序和折半查找算法 #include int BubbleSort(int c[]){ int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所輸入的數(shù)字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int BinarySearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn請輸入您要查找的數(shù)字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的數(shù)字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“請您輸入數(shù)據(jù):nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } BubbleSort(a);BinarySearch(a);return 0; 3、簡單選擇排序和簡單插入排序算法 #include int i,j,min,p,key,k; for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int InserSort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“請輸入關(guān)鍵字的個數(shù)：”);scanf(“%d”,&n);printf(“排序類型：n”);printf(“1.選擇排序n”);printf(“2.插入排序n”);printf(“請選擇：”);scanf(“%d”,&b);switch(b){ case 1: printf(“請輸入關(guān)鍵字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“請輸入關(guān)鍵字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及結(jié)果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、實(shí)驗(yàn)運(yùn)行結(jié)果 1.二叉排序樹的創(chuàng)建、遍歷和查找刪除算法 2、冒泡排序和折半查找算法 3、簡單選擇排序和簡單插入排序算法 七、心得體會 通過本次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告，掌握了查找和排序的幾種基本排序算法，了解了他們各自的特點(diǎn)和優(yōu)缺點(diǎn)，完成了對于他們C語言的描述和實(shí)際應(yīng)用，對他們有了一個更加具體、深刻的認(rèn)識，同時也鍛煉了我們的邏輯思維能力和動手實(shí)踐能力，使我們受益匪淺，給我們今后的計(jì)算機(jī)專業(yè)課程學(xué)習(xí)帶來很大的幫助。 綜合課程設(shè)計(jì)1 ——《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱 一、課程的性質(zhì)、教學(xué)目的和要求 《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門課程，必須在掌握理論知識的同時，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能 二、設(shè)計(jì)要點(diǎn) 1、通過這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。 2、學(xué)生必須仔細(xì)研讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)(實(shí)習(xí))要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，認(rèn)真、獨(dú)立地完成課程設(shè)計(jì)的任務(wù)，有問題及時主動與指導(dǎo)教師溝通。 3、本次課程設(shè)計(jì)按照教學(xué)要求需要獨(dú)立完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課程設(shè)計(jì)的時間計(jì)劃，并在課程設(shè)計(jì)過程中不斷檢測自己的計(jì)劃完成情況，及時地向指導(dǎo)教師匯報。 4、編程語言任選。 三、設(shè)計(jì)題目 1、集合的并、交和算差運(yùn) 任務(wù)：編制一個能演示執(zhí)行集合的并、交和差運(yùn)算的程序。要求:(1)集合的元素限定為小寫字母字符 [‘a(chǎn)’..’z’]。(2)演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行。實(shí)現(xiàn)提示:以鏈表表示集合。 選作內(nèi)容:(1)集合的元素判定和子集判定運(yùn)算。 (2)求集合的補(bǔ)集。 (3)集合的混合運(yùn)算表達(dá)式求值。 (4)集合的元素類型推廣到其他類型，甚至任意類型。 2、停車場管理 任務(wù)：設(shè)停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次有北向南排列（大門在最南端，最先到達(dá)的第一車停放在車場的最北端），若車場內(nèi)已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。 要求：以棧模擬停車場，以隊(duì)列模擬車場外的便道。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停車不收費(fèi)）。棧以順序存儲結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。 3、哈夫曼碼的編/譯碼系統(tǒng) 【問題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€完整的系統(tǒng)應(yīng)具有以下功能： （1）I:初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。 （2）E:編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D:譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。 （4）P:打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。 （5）T:打印哈夫曼樹（Tree printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中?！緶y試數(shù)據(jù)】 （1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。 （2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【實(shí)現(xiàn)提示】 （1）編碼結(jié)果以文本方式存儲在文件CodeFile中。 （2）用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。 （3）在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或E命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。 4、校園導(dǎo)游咨詢 任務(wù)：設(shè)計(jì)一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。 要求： （1）設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個，以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。 （2）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。 （3）為來訪客人提供景點(diǎn)的問路查詢，即已知一個景點(diǎn)，查詢到某景點(diǎn)之間的一條最短路徑及長度。 5、散列表的設(shè)計(jì)與實(shí)現(xiàn) 任務(wù)：設(shè)計(jì)散列表實(shí)現(xiàn)電話號碼查找系統(tǒng)。要求： （1）設(shè)每個記錄有下列數(shù)據(jù)項(xiàng)：用戶名、電話號碼、地址； 2（2）從鍵盤輸入各記錄，以用戶名（漢語拼音形式）為關(guān)鍵字建立散列表；（3）采用一定的方法解決沖突； （4）查找并顯示給定電話號碼的記錄； 選作內(nèi)容： （1）系統(tǒng)功能的完善； （2）設(shè)計(jì)不同的散列函數(shù)，比較沖突率； （3）在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。 6、文章編輯 功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行； 要求:（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。 存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實(shí)現(xiàn)相應(yīng)的功能； 輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號。輸出形式： （1）分行輸出用戶輸入的各行字符； （2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章； 四、參考書目 《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社 數(shù) 據(jù) 結(jié) 構(gòu) 課程設(shè)計(jì)報告 題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學(xué) 號： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時 間： 一、課程設(shè)計(jì)題目分析 本課程設(shè)計(jì)要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。 二、設(shè)計(jì)思路 本程序采用C語言來完成課程設(shè)計(jì)。 1、首先，利用順序存儲結(jié)構(gòu)來構(gòu)造兩個存儲多項(xiàng)式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運(yùn)算分成五個主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時錯誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。 三、設(shè)計(jì)算法分析 1、相關(guān)函數(shù)說明： (1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項(xiàng)式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項(xiàng)式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項(xiàng)式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項(xiàng)式，void Print(Polyn P) 銷毀多項(xiàng)式函數(shù)釋放內(nèi)存，void Destroy(Polyn p) 主函數(shù)，void main（） 2、主程序的流程基函數(shù)調(diào)用說明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個結(jié)構(gòu)體變量中coef表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對象名。 (2)當(dāng)用戶輸入兩個一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲這兩個多項(xiàng)式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xiàng)式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn) 這就建立一元多項(xiàng)式的關(guān)鍵步驟 (3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進(jìn)行處理，此處由于反復(fù)使用指針對各個結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)： 在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實(shí)現(xiàn)；對于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計(jì)算模塊的主要功能。 (5)另一個子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計(jì)算合并的鏈表逐個結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計(jì)算式計(jì)算結(jié)果。由于考慮各個結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。 四、程序新點(diǎn) 通過多次寫程序，發(fā)現(xiàn)在程序在控制臺運(yùn)行時總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺背景顏色，0是控制臺輸出字體顏色。 五、設(shè)計(jì)中遇到的問題及解決辦法 首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時候易腦子混亂出錯，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4 代碼編寫。 其次是，在寫除法模塊時比較復(fù)雜，自己通過查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計(jì)時的一個經(jīng)驗(yàn)吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過本次應(yīng)用C語言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語言程序設(shè)計(jì)的知識，以前對指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計(jì)對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對自己以后學(xué)習(xí)其他語言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。 八、指導(dǎo)老師評語及成績 附錄：（課程設(shè)計(jì)代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點(diǎn) else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數(shù)為0的話釋放結(jié)點(diǎn) { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時將結(jié)點(diǎn)插入 } 7 } //建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf(“請輸入第%d項(xiàng)的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn) } return head;} //銷毀多項(xiàng)式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項(xiàng)式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器 if(!q)//若多項(xiàng)式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng) 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空 } //求解并建立多項(xiàng)式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當(dāng)相加系數(shù)為0時，釋放該結(jié)點(diǎn) } return headc;} //求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng) } } return hf;} //求解并建立多項(xiàng)式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn),存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)，存儲余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請輸入A(x)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請輸入B(x)的項(xiàng)數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項(xiàng)式B printf(“n”);printf(“**********************************************n”);printf(“* 多項(xiàng)式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項(xiàng)式A(x):“);Print(pa);*n”); printf(“多項(xiàng)式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項(xiàng)式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項(xiàng)式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項(xiàng)式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 1.赫夫曼編碼器 設(shè)計(jì)一個利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。要求： 1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個字符和26個權(quán)值（統(tǒng)計(jì)一篇英文文章中26個字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實(shí)現(xiàn)屏幕輸出，然后實(shí)現(xiàn)文件輸出）； 5)界面優(yōu)化設(shè)計(jì)。 代碼如下： #include typedef struct HTNode //結(jié)構(gòu)體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權(quán)值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進(jìn)行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請輸入權(quán)值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對結(jié)點(diǎn)進(jìn)行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-查找排序
第三篇：綜合課程設(shè)計(jì)1-數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱
第四篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)