婷婷五月综合色中文字幕,青青草av国产精品,东京热一精品无码av

第一篇：數據結構課程設計—綜合排序

東華理工大學

東華理工大學課程設計報告

課程設計題目：綜合排序的設計

學生姓名：何楊班

級：1223202 專

業：信息與計算科學指導教師：郭樹蕻

2014年 12 月 13 日

東華理工大學

摘要..............................................................2

一、題目的內容及要求-----------------4

二、需求分析------------------------------4

三、概要設計------------------------------5 四、四種排序源代碼詳細設計--------5

五、程序輸出的結果-------------------10

六、運行結果及分析-------------------12

七、收獲及體會-------------------------13

八、參考文獻-----------------------------1

東華理工大學

摘要

數據結構是由數據元素依據某種邏輯聯系組織起來的。對數據元素間邏輯關系的描述稱為數據的邏輯結構；數據必須在計算機內存儲，數據的存儲結構是數據結構的實現形式，是其在計算機內的表示；此外討論一個數據結構必須同時討論在該類數據上執行的運算才有意義。在許多類型的程序的設計中，數據結構的選擇是一個基本的設計考慮因素。許多大型系統的構造經驗表明，系統實現的困難程度和系統構造的質量都嚴重的依賴于是否選擇了最優的數據結構。許多時候，確定了數據結構后，算法就容易得到了。有些時候事情也會反過來，我們根據特定算法來選擇數據結構與之適應。不論哪種情況，選擇合適的數據結構都是非常重要的。排序算法是數據結構學科經典的內容，其中內部排序現有的算法有很多種，其中包含冒泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有其特點。對排序算法比較的分析可以遵循若干種不同的準則，通常以排序過程所需要的算法步數作為度量，有時也以排序過程中所作的鍵比較次數作為度量。特別是當作一次鍵比較需要較長時間，例如，當鍵是較長的字符串時，常以鍵比較次數作為排序算法計算時間復雜性的度量。當排序時需要移動記錄，且記錄都很大時，還應該考慮記錄的移動次數。究竟采用哪種度量方法比較合適要根據具體情況而定。在下面的討論中我們主要考慮用比較的次數作為復雜性的度量。

關鍵字：數據結構；算法比較；比較次數；時間復雜度

東華理工大學

一、題目的內容及要求

排序綜合

利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。要求：

(1)至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。

(2)統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。

(3)如果采用4種或4種以上的方法者，可適當加分。

二、需求分析

2.1 問題描述

此次的任務要求是輸入20000個以上的隨機整數，對這些數進行多種方法進行排序。（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。

約束：程序可由用戶自行設定排序數的個數，但排序數具體值需要由計算機生成，然后用三種以上的排序方法對隨機數組進行排序，每一種排序方法執行后需統計出數據移動次數以判斷排序方法的對比隨機數組的執行優劣性。另：用戶自行算出每一種排序方法的時間復雜度與空間復雜度。

2.2 基本要求

2.2.1輸入的形式和輸入值的范圍；

設定的隨機數據的范圍為20000以上，用戶自定義隨機數的個數n，隨機數的數據類型均為整形。

2.2.2輸出的形式；

程序是以一個完整的有序數組來進行輸出。

2.2.3程序所達到的功能：

將一個無序數組進行排序隨機生成20000以上個隨機整數，對這些數進行多種方法進行排序。分別采用以下方法實現上述問題求解（可采用的方法有簡單排序、希爾排序、冒泡排序、快速排序這四種排序方法）。

東華理工大學

三、概要設計

3.1可排序表的抽象數據類型定義：

typedef int KeyType;//關鍵字為整型 typedef int OtherType;//關鍵字為整型

typedef struct { KeyType key;//關鍵字為KeyType型 OtherType other_data;}RecordType;//定義一個RecordType型結構體，存放關鍵字 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()//主函數運行入口四、四種排序源代碼詳細設計：

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

東華理工大學

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);//繼續處理左邊的，這是一個遞歸的過程

quicksort(a,i+1,right);//繼續處理右邊的，這是一個遞歸的過程 } /* 快速排序算法 */

4.2冒泡排序模塊：

//此處是一次冒泡排序過程，在主函數中會通過循環調用此冒泡函數過程 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)//根據待排序的個數生成合適的步長，gap是步長

{

gap = gap * 3 + 1;

東華理工大學

}

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)/*對記錄數組r進行折半插入排序，length為數組的長度*/ { 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*/

東華理工大學

4.5主函數模塊：

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.產生隨機數并輸出

* n”);

printf(“

3.采用快速排序法排序

* n”);

printf(“

4.采用冒泡排序法排序

* n”);

printf(“

5.采用希爾排序法排序

* n”);

printf(“

6.采用折半插入排序法排序

* n”);

printf(“

7.輸出

* n”);printf(“

0.退出系統

* n”);printf(“

*------------------------* n”);

printf(“

”);

b = getch();

switch(b)

{

case '1':

printf(“%cn”,b);

printf(“請輸入待排序記錄的長度：”);

scanf(“%d”,&n);break;

東華理工大學

case '2':

printf(“%cn”,b);

srand((unsigned)time(NULL));

printf(“下面隨機生成%d個數字存儲在數組中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

-----------------快速排序結束-------------------

nn”);

quicksort(a,1,n);

q=true;break;

case '4':

printf(“%cn”,b);

for(i=0;i

{

bubbleSort(a,n-i);

}

printf(“n

-----------------冒泡排序結束-------------------

nn”);

q=true;break;

case '5':

printf(“%cn”,b);

printf(“n

-----------------希爾排序結束-------------------

nn”);

shellSort(a,n);

q=true;break;

case '6':

printf(“%cn”,b);

BinSort(a,n);

printf(“n

-----------------折半插入排序結束-------------------nn”);

q=true;break;

case '7':

printf(“%cn”,b);

東華理工大學

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(“

您未對待排序數據排序

* n”);

printf(“

請重新選擇排序的序號

* n”);

printf(“

*------------------------* n”);

}

break;

case '0':

printf(“%cn”,b);

printf(“n

感謝使用綜合排序程序n

按任意鍵退出......n”);

return;break;

default:printf(“nn”);

} } }

五、程序輸出的結果： 5.1輸入和輸出：

(1)主函數運行的輸出結果：

東華理工大學

(2)選擇1，讀取待排序長度（這里以20000為例）：

(3)選擇2，產生隨機數并輸出：

(4)選擇3，采用快速排序法排序：

東華理工大學

（選擇4、5、6的其他排序法的輸出雷同，此處就不再重復）(5)選擇7，輸出排序結果：

六、運行結果及分析

6.1各算法的比較方法

1.穩定性比較

折半插入排序、冒泡排序是穩定的希爾排序、快速排序是不穩定的 2.時間復雜性比較

折半插入排序、冒泡排序的時間復雜性為O(n2)其它非線形排序的時間復雜性為O(nlog2n)3.輔助空間的比較

東華理工大學

線形排序的輔助空間為O(n),其它排序的輔助空間為O(1);4.其它比較

插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。

反而在這種情況下，快速排序反而慢了。

當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。

當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。

七、收獲及體會

根據四種排序法的基礎理論實際性模仿和編寫算法程序，很是困難，算法是程序的靈魂，數據結構確是算法的基礎，但是不斷的實踐也是一種進步的好途徑。這次課程設計主要是對基礎知識的靈活應用，這就讓我進一步提高了對數結構知識的鞏固。這次設計的完成，困難是少不了的，還有很多其它的難題讓我都不知道所措，但是通過努力最終解決他們讓我體會到成就感，更重要的是我的能力在實踐中得到了提升和優化，特別是對常用的排序算法的應用，這對我以后從事軟件應用程序開發是有很大的幫助的。這次課程設計的心得體會通過實習我的收獲如下

1、鞏固和加深了對數據結構的理解，提高綜合運用本課程所學知識的能力。

2、培養了我選用參考書，查閱手冊及文獻資料的能力。培養獨立思考，深入研究，分析問題、解決問題的能力。

3、通過實際編譯系統的分析設計、編程調試，掌握應用軟件的分析方法和工程設計方法。

4、通過課程設計，培養了我嚴肅認真的工作作風，逐步建立正確的生產觀念、經濟觀念和全局觀念。根據我在實習中遇到得問題，我將在以后的學習過程中注意以下幾點：

1、認真上好專業實驗課，多在實踐中鍛煉自己。

2、寫程序的過程中要考慮周到，嚴密。

3、在做設計的時候要有信心，有耐心，切勿浮躁。

4、認真的學習課本知識，掌握課本中的知識點，并在此基礎上學會靈活運用。

5、在課余時間里多寫程序，熟練掌握在調試程序的過程中所遇到的常見錯誤，以便能節省調試程序的時間。我通過課程設計建立系統設計的整體思想，鍛煉編寫程序、調試程序的能力，學習文檔編寫規范，培養獨立學習、吸取他人經驗，樹立團隊協作精神。同時，充分彌補了課堂教學及普通實驗中知識深度與廣度有限的缺陷，更好地幫助從全局角度把握

東華理工大學

課程體系，并且可以將理論與實際聯系。在課程設計的過程中不僅僅是書本上的知識，這便促使我去查閱更多的課外資料來充實自己的內容，同時學會在面對困難時要耐心得分析它細心得解決它以及通過合作更完美得深入了解剖析它以便得到提高。細心、耐心、團結、求知，是我這次課程設計最大的收獲。同時要感謝老師這幾天的悉心教導。

八、參考文獻

[1] 啊哈磊，《啊哈！算法》，人民郵電出版社，2014-6-1 [2] 劉艷飛，《C語言范例開發大全》清華大學出版社，2010 [3] 嚴蔚敏，吳偉民。數據結構。北京：清華大學出版社，2001

第二篇：數據結構課程設計-查找排序

查找及排序算法實現

一、實驗目的

1、熟練掌握二叉排序樹查找算法及C語言描述。

2、熟練掌握折半查找算法及C語言描述。

3、熟練掌握簡單選擇排序算法及C語言描述。

4、熟練掌握簡單插入排序算法及C語言描述。

5、熟練掌握冒泡（起泡）排序算法及C語言描述。

6、了解各種查找及排序算法的優缺點、實用性及應用。

7、將理論與實際相結合，切實提高自己的邏輯能力和動手能力。

二、設計內容

1.折半查找算法

折半查找算法的思路：

初始狀態：假設表長為n，low、high和mid分別指向待查元素所在區間的下界、上界和中點,key為給定值，初始時，令low=0,high=n-1,mid=(low+high)/2 讓key與mid指向的記錄比較

若key==r[mid].key，查找成功,算法結束；若keyr[mid].key，則low=mid+1；重復上述操作，直至low>high時，查找失敗。2.起泡排序算法

起泡排序的思路：

首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較【第二個記錄和第三個記錄】的關鍵字。以此類推，直至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。上述過程稱做第一趟起泡排序，其結果使得關鍵字最大的記錄被安置到最后一個記錄的位置上，然后進行第二趟起泡排序，對前n-1個記錄進行同樣操作，其結果是使關鍵字次大的記錄被安置到第n-1個記錄的位置上。一般地，第i躺起泡排序是從L.r[1]到L.r[n-i+1]以此比較相鄰兩個記錄的關鍵字，并在“逆序”時交換相鄰記錄，其結果是這n-i+1個記錄中關鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進行k(1<=k

首先以一個元素為基準，從一個方向開始掃描，比如從左至右掃描，以a[0]為基準，接下來從a[0]...a[9] 中找出最小的元素，將其與a[0]交換，然后將基準位置右

移一位，重復上面的動作，比如，以a[1]為基準，找出a[1]至a[9]中最小的，將其與a[1]交換，一直進行到基準位置移到數組最后一個元素時排序結束（此時基準左邊所有元素均遞增有序，而基準為最后一個元素，故完成排序）。4.直接插入排序算法

直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數增1的有序表。

一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1...i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r[1....i].在自i-1起往前搜索的過程中，可以同時后移記錄。

整個排序過程為進行n-1躺插入，即：先將序列中的第一個記錄看成是一個有序的子序列，然后從第二個記錄起逐個進行插入，直至整個序列變成按關鍵字非遞減有序序列為止

三、程序源代碼

1.二叉排序樹的創建、遍歷和查找刪除算法

#include #include typedef int KeyType;typedef struct node { KeyType data;struct node *lchild,*rchild;}LNode,*Tree;

void Insert(Tree &T,KeyType key){

if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else

} {

} if(keydata)Insert(T->lchild,key);else Insert(T->rchild,key);void CreatTree(Tree &T)//二叉排序樹的創建 {

} 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該結點不存在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(“該結點不存在”);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()//主函數 { Tree T,p;T=NULL;KeyType x;

printf(“請輸入二叉樹各結點：n”);

CreatTree(T);

printf(“中序遍歷為：n”);In_Order(T);printf(“n請輸入要查找和刪除的結點：n”);scanf(“%d”,&x);p=Search(T, x);if(p){

} DelNode(T, x);printf(“中序遍歷為：n”);In_Order(T);

}

2、冒泡排序和折半查找算法

#include #include #define M 10 //冒泡排序

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您所輸入的數字的升序排列是: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請輸入您要查找的數字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2;

} return 1;if(t==b[mid]){ printf(“n您要查找的數字的排列位置是：%dn”,mid+1);break;} else if(t

int main(int argc,char *argv[]){

int a[10];printf(“請您輸入數據:nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]);

} } BubbleSort(a);BinarySearch(a);return 0;

3、簡單選擇排序和簡單插入排序算法

#include int SelectionSort(int*a,int n){

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(“請輸入關鍵字的個數：”);scanf(“%d”,&n);printf(“排序類型：n”);printf(“1.選擇排序n”);printf(“2.插入排序n”);printf(“請選擇：”);scanf(“%d”,&b);switch(b){

case 1:

printf(“請輸入關鍵字：n”);for(i=0;i

SelectionSort(a,n);

return 1;

break;

case 2:

printf(“請輸入關鍵字：n”);

for(i=1;i<=n;i++){

scanf(“%d”,&a[i]);} printf(“插入排序的流程以及結果：n”);

InserSort(a,n);return 1;

} break;}while(a!=0);

四、實驗運行結果

1.二叉排序樹的創建、遍歷和查找刪除算法

2、冒泡排序和折半查找算法

3、簡單選擇排序和簡單插入排序算法

七、心得體會

通過本次的數據結構課程設計報告，掌握了查找和排序的幾種基本排序算法，了解了他們各自的特點和優缺點，完成了對于他們C語言的描述和實際應用，對他們有了一個更加具體、深刻的認識，同時也鍛煉了我們的邏輯思維能力和動手實踐能力，使我們受益匪淺，給我們今后的計算機專業課程學習帶來很大的幫助。

第三篇：綜合課程設計1-數據結構教學大綱

綜合課程設計1 ——《數據結構課程設計》教學大綱

一、課程的性質、教學目的和要求

《數據結構》是一門實踐性較強的軟件基礎課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際問題在計算機內部表示出來，并培養基本的、良好的程序設計技能

二、設計要點

1、通過這次設計，要求在數據結構的邏輯特性和物理表示、數據結構的選擇應用、算法的設計及其實現等方面加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。

2、學生必須仔細研讀《數據結構》課程設計(實習)要求，以學生自學為主、指導教師指導為輔，認真、獨立地完成課程設計的任務，有問題及時主動與指導教師溝通。

3、本次課程設計按照教學要求需要獨立完成，學生要發揮自主學習的能力，充分利用時間，安排好課程設計的時間計劃，并在課程設計過程中不斷檢測自己的計劃完成情況，及時地向指導教師匯報。

4、編程語言任選。

三、設計題目

1、集合的并、交和算差運

任務：編制一個能演示執行集合的并、交和差運算的程序。要求:(1)集合的元素限定為小寫字母字符 [‘a’..’z’]。(2)演示程序以用戶和計算機的對話方式執行。實現提示:以鏈表表示集合。

選作內容:(1)集合的元素判定和子集判定運算。

(2)求集合的補集。

(3)集合的混合運算表達式求值。

(4)集合的元素類型推廣到其他類型，甚至任意類型。

2、停車場管理

任務：設停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次有北向南排列（大門在最南端，最先到達的第一車停放在車場的最北端），若車場內已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。

要求：以棧模擬停車場，以隊列模擬車場外的便道。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數據進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停車不收費）。棧以順序存儲結構實現，隊列以鏈表結構實現。

3、哈夫曼碼的編/譯碼系統【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/譯碼系統。【基本要求】一個完整的系統應具有以下功能：

（1）I:初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。

（2）E:編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。（3）D:譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。

（4）P:打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。

（5）T:打印哈夫曼樹（Tree printing）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。【測試數據】

（1）利用下面這道題中的數據調試程序。某系統在通信聯絡中只可能出現八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計哈夫曼編碼。

（2）用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“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

【實現提示】

（1）編碼結果以文本方式存儲在文件CodeFile中。

（2）用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。

（3）在程序的一次執行過程中，第一次執行I，D或E命令之后，哈夫曼樹已經在內存了，不必再讀入。每次執行中不一定執行I命令，因為文件hfmTree可能早已建好。

4、校園導游咨詢

任務：設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。

要求：

（1）設計學校的校園平面圖，所含景點不少于10個，以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。

（2）為來訪客人提供圖中任意景點相關信息的查詢。

（3）為來訪客人提供景點的問路查詢，即已知一個景點，查詢到某景點之間的一條最短路徑及長度。

5、散列表的設計與實現

任務：設計散列表實現電話號碼查找系統。要求：

（1）設每個記錄有下列數據項：用戶名、電話號碼、地址；

2（2）從鍵盤輸入各記錄，以用戶名（漢語拼音形式）為關鍵字建立散列表；（3）采用一定的方法解決沖突；

（4）查找并顯示給定電話號碼的記錄；選作內容：

（1）系統功能的完善；

（2）設計不同的散列函數，比較沖突率；

（3）在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

6、文章編輯

功能：輸入一頁文字，程序可以統計出文字、數字、空格的個數。靜態存儲一頁文章，每行最多不超過80個字符，共N行；要求:（1）分別統計出其中英文字母數和空格數及整篇文章總字數；（2）統計某一字符串在文章中出現的次數，并輸出該次數；（3）刪除某一子串，并將后面的字符前移。

存儲結構使用線性表，分別用幾個子函數實現相應的功能；

輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。輸出形式：

（1）分行輸出用戶輸入的各行字符；

（2）分4行輸出“全部字母數”、“數字個數”、“空格個數”、“文章總字數”（3）輸出刪除某一字符串后的文章；

四、參考書目

《數據結構 C語言》嚴蔚敏清華大學出版社《c語言程序設計》譚浩強清華大學出版社《數據結構》高教出版社

《數據結構習題》李春保清華大學出版社《數據結構習題》嚴蔚敏清華大學出版社

《c語言與數據結構》王立柱清華大學出版社

《數據結構（C語言篇）習題與解析》李春葆清華大學出版社

第四篇：2012數據結構課程設計

數據結構

課程設計報告

題目：一元多項式計算專業：信息管理與信息系統班級： 2012級普本班學號： 201201011367 姓名：左帥帥指導老師：郝慎學時間：

一、課程設計題目分析

本課程設計要求利用C語言或C++編寫，本程序實現了一元多項式的加法、減法、乘法、除法運算等功能。

二、設計思路

本程序采用C語言來完成課程設計。

1、首先，利用順序存儲結構來構造兩個存儲多項式A(x)和 B(x)的結構。

2、然后把輸入，加，減，乘，除運算分成五個主要的模塊：實現多項式輸入模塊、實現加法的模塊、實現減法的模塊、實現乘法的模塊、實現除法的模塊。

3、然后各個模塊里面還要分成若干種情況來考慮并通過函數的嵌套調用來實現其功能，盡量減少程序運行時錯誤的出現。

4、最后編寫main()主函數以實現對多項式輸入輸出以及加、減、乘、除，調試程序并將不足的地方加以修改。

三、設計算法分析

1、相關函數說明：

(1)定義數據結構類型為線性表的鏈式存儲結構類型變量

typedef struct Polynomial{}

(2)其他功能函數

插入函數void Insert(Polyn p,Polyn h)

比較函數int compare(Polyn a,Polyn b)

建立一元多項式函數Polyn Create(Polyn head,int m)

求解并建立多項式a+b，Polyn Add(Polyn pa,Polyn pb)

求解并建立多項式a-b，Polyn Subtract(Polyn pa,Polyn pb)2

求解并建立多項式a*b，Polyn Multiply(Polyn pa,Polyn pb)

求解并建立多項式a/b，void Device(Polyn pa,Polyn pb)

輸出函數輸出多項式，void Print(Polyn P)

銷毀多項式函數釋放內存，void Destroy(Polyn p)

主函數，void main（）

2、主程序的流程基函數調用說明(1)typedef struct Polynomial {

float coef;

int expn;

struct Polynomial *next;} *Polyn,Polynomial;

在這個結構體變量中coef表示每一項前的系數，expn表示每一項的指數，polyn為結點指針類型，屬于抽象數據類型通常由用戶自行定義，Polynomial表示的是結構體中的數據對象名。

(2)當用戶輸入兩個一元多項式的系數和指數后，建立鏈表，存儲這兩個多項式，主要說明如下：

Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數為m的一元多項式

p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項式申請足夠的存儲空間

p=(Polyn)malloc(sizeof(struct Polynomial));建立新結點以接收數據

Insert(p,head);調用Insert函數插入結點

這就建立一元多項式的關鍵步驟

(3)由于多項式的系數和指數都是隨即輸入的，所以根據要求需要對多項式按指數進行降冪排序。在這個程序模塊中，使用鏈表，根據對指數大小的比較，對各種情況進行處理，此處由于反復使用指針對各個結點進行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進行插入操作。(4)加、減、乘、除、的算法實現：

在該程序中，最關鍵的一步是實現四則運算和輸出，由于加減算法原則是一樣，減法可通過系數為負的加法實現；對于乘除算法的大致流程都是：首先建立多項式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數。這就實現了多項式計算模塊的主要功能。

(5)另一個子函數是輸出函數 PrintPolyn（）；

輸出最終的結果，算法是將最后計算合并的鏈表逐個結點依次輸出，便得到整鏈表，也就是最后的計算式計算結果。由于考慮各個結點的指數情況不同，分別進行了判斷處理。

四、程序新點

通過多次寫程序，發現在程序在控制臺運行時總是黑色的，本次寫程序就想著改變一下，于是經過查資料利用system(“Color E0”);可以函數解決，這里“E0，”E是控制臺背景顏色，0是控制臺輸出字體顏色。

五、設計中遇到的問題及解決辦法

首先是，由于此次課程設計里使用指針使用比較多，自己在指針多的時候易腦子混亂出錯，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進行 4

代碼編寫。

其次是，在寫除法模塊時比較復雜，自己通過查資料最后成功寫出除法模塊功能。

最后是，前期分析不足開始急于寫代碼，中途出現各種問題，算是給自己以后設計時的一個經驗吧。

六、測試（程序截圖）

1.數據輸入及主菜單

2.加法和減法模塊

3.乘法和除法模塊

七、總結

通過本次應用C語言設計一元多項式基本計算程序，使我更加鞏固了C語言程序設計的知識，以前對指針這一點使用是比較模糊，現在通過此次課程設計對指針理解的比較深刻了。而且對于數據結構的相關算法和函數的調用方面知識的加深。本次的課程設計，一方面提高了自己獨立思考處理問題的能力；另一方面使自己再設計開發程序方面有了一定的小經驗和想法，對自己以后學習其他語言程序設計奠定了一定的基礎。

八、指導老師評語及成績

附錄：（課程設計代碼）

#include #include #include typedef struct Polynomial {

float coef;6

int expn;

struct Polynomial *next;} *Polyn,Polynomial;

//Polyn為結點指針類型 void Insert(Polyn p,Polyn h){

if(p->coef==0)free(p);

//系數為0的話釋放結點

else

{

Polyn q1,q2;

q1=h;q2=h->next;

while(q2&&p->expnexpn)//查找插入位置

{

q1=q2;q2=q2->next;}

if(q2&&p->expn==q2->expn)//將指數相同相合并 {

q2->coef+=p->coef;

free(p);

if(!q2->coef)//系數為0的話釋放結點

{ q1->next=q2->next;free(q2);}

}

else { p->next=q2;q1->next=p;

}//指數為新時將結點插入

} 7

} //建立一個頭指針為head、項數為m的一元多項式 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));//建立新結點以接收數據

printf(“請輸入第%d項的系數與指數:”,i+1);

scanf(“%f %d”,&p->coef,&p->expn);

Insert(p,head);

//調用Insert函數插入結點

}

return head;} //銷毀多項式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;

} } //輸出多項式p int Print(Polyn P){

Polyn q=P->next;

int flag=1;//項數計數器

if(!q)//若多項式為空，輸出0

{

putchar('0');

printf(“n”);

return;

}

while(q)

{

if(q->coef>0&&flag!=1)putchar('+');//系數大于0且不是第一項 9

if(q->coef!=1&&q->coef!=-1)//系數非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->expnexpn)return-1;

else return 0;

}

else if(!a&&b)return-1;//a多項式已空，但b多項式非空

else return 1;//b多項式已空，但a多項式非空 } //求解并建立多項式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));//建立頭結點 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);//當相加系數為0時，釋放該結點

}

return headc;} //求解并建立多項式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){

Polyn h=pb;

Polyn p=pb->next;

Polyn pd;

while(p)//將pb的系數取反

{ p->coef*=-1;p=p->next;}

pd=Add(pa,h);

for(p=h->next;p;p=p->next)

//恢復pb的系數

p->coef*=-1;13

return pd;} //求解并建立多項式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));//建立頭結點

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);//調用Insert函數以合并指數相同的項

}

return hf;}

//求解并建立多項式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));//建立頭結點,存儲商

hf->next=NULL;

pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點，存儲余數

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(“余數是:”);

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)的項數:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項式A printf(“n”);printf(“請輸入B(x)的項數:”);16

scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項式B printf(“n”);printf(“**********************************************n”);printf(“*

多項式操作菜單

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(”執行操作:“);

scanf(”%d“,&flag);

switch(flag)

{

case 1:

printf(”多項式A(x):“);Print(pa);*n”);

printf(“多項式B(x):”);Print(pb);

break;

case 2:

pc=Add(pa,pb);

printf(“多項式A(x)+B(x):”);Print(pc);

Destroy(pc);break;

case 3:

pd=Subtract(pa,pb);

printf(“多項式A(x)-B(x):”);Print(pd);

Destroy(pd);break;

case 4:

pf=Multiply(pa,pb);

printf(“多項式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);}

第五篇：數據結構課程設計

數據結構課程設計

1.赫夫曼編碼器

設計一個利用赫夫曼算法的編碼和譯碼系統，重復地顯示并處理以下項目，直到選擇退出為止。要求：

1)將權值數據存放在數據文件(文件名為data.txt，位于執行程序的當前目錄中)

2)初始化：鍵盤輸入字符集大小26、26個字符和26個權值（統計一篇英文文章中26個字母），建立哈夫曼樹；

3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；

4)輸出編碼（首先實現屏幕輸出，然后實現文件輸出）； 5)界面優化設計。

代碼如下：

#include #include #include #include #define N 200

typedef struct HTNode

//結構體 { int Weight;

char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode;

void Save(int n,HTNode *HT)

//把權值保存到文件 {

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)

//建立赫夫曼樹，進行編碼 {

int w,k,j;char c;for(k=1;k<=m;k++){

if(k<=n)

{

printf(“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)

//對結點進行譯碼 { 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]='

久久99精品久久久久久琪琪,久久人人爽人人爽人人片亞洲,熟妇人妻无码中文字幕,亚洲精品无码久久久久久久

數據結構課程設計—綜合排序

第一篇：數據結構課程設計—綜合排序

第二篇：數據結構課程設計-查找排序

第三篇：綜合課程設計1-數據結構教學大綱

第四篇：2012數據結構課程設計

第五篇：數據結構課程設計