第一篇：數據結構課程設計_集合的并、交和差運算（推薦）

一、課程題目 集合的并、交和差運算

二、問題描述

功能： 編制一個能演示執行集合的并、交和差運算的程序。

三、基本要求

1）集合的元素限定為小寫字母字符【‘a’..‘z’】 2）演示程序以用戶和計算機的對話方式執行。

四、測試數據

（1）Set1=”magazine”, Set2=’paper”, Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”;(2)Set1=”012oper4a6tion89”,Set2=”error data”, Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”, Set1-Set2=”inp”.五、算法思想

為了實現上述程序的功能，應以有序鏈表表示集合。為此，需要兩個抽象數據類型：有序表和集合。

1、有序表的抽象數據類型定義為： input(linklist l)初始條件：l是以l為頭節點的空鏈表。操作結果：生成以l為頭節點的非空鏈表。

output(linklist l)初始條件：l是以l為頭節點的非空鏈表。

操作結果：將以l為頭節點的鏈表中數據逐個輸出。

2、集合的抽象數據類型定義為： heji(linklist A,linklist B,linklist C)初始條件：鏈表A、B、C已存在

操作結果：生成一個由A和B的并集構成的集合C。jiaoji(linklist A,linklist B ,linklist ,C)初始條件：鏈表A、B、C已存在

操作結果：生成一個由A和B的交集構成的集合C。

六、模塊化分 本程序抱含四個模塊：

1）節點結構單元模塊——定義有序表的節點結構； 2）有序表單元模塊——實現有序表的抽象數據類型； 3）集合單元模塊——實現集合獲得抽象數據類型； 4）主程序模塊： Void main（）{ 初始化； do{ 接受命令； 處理命令；

}while（“命令”!=“退出”）；

}

七、源程序 # include #include #include #include typedef struct node {

}lnode,*linklist;lnode *init_lnode();void input(linklist l);void jiaoji(linklist A,linklist B,linklist C);void heji(linklist A,linklist B,linklist C);void output(linklist l);void main(){ lnode *a,*b,*c;a=init_lnode();b=init_lnode();int data;struct node* next;

c=init_lnode();printf(“求AB集合的交集和并集n”);printf(“請輸入A集合的元素:”);input(a);printf(“n請輸入B集合的元素:”);input(b);printf(“n輸入完成n”);printf(“n按任意鍵進入主菜單:”);getch();do {

};

printf(“%s”,menu);printf(“n請在0-3中選擇:”);scanf(“%d”,&sel);switch(sel){ case 1: char menu[]={“nnn-----☆ 1.交集運算 ☆---------nn”

“---------☆ 2和集運算☆---------nn”

“---------☆3.差集運算 ☆---------nn”

“---------☆ 0.退出 ☆---------nn”

printf(“AB集合的交集是:”);

jiaoji(A,B,C);

output(C);

C->next=NULL;

break;

case 2:

printf(“AB的合集是:”);

heji(A,B,C);output(C);

C->next=NULL;break;case 3:

chaji(A,B,C);

break;

case 0:

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

/*主函數結束*/ /**********初始化函數***************/ lnode * init_lnode(){

lnode *l;

l=(lnode *)malloc(sizeof(lnode));

l->next=NULL;

return l;} /***************錄入函數********************/ void input(linklist l){

} /************交集函數*********************/ void jiaoji(linklist A,linklist B,linklist C)lnode *s;int x;scanf(“%d”,&x);while(x!=0){

} s=(lnode *)malloc(sizeof(lnode));s->data=x;s->next=l->next;l->next=s;scanf(“%d”,&x);

{lnode *p,*q,*t;

} /***********輸出函數*****************/ void output(linklist l){ lnode *s;s=l->next;p=A->next;while(p!=NULL){

} q=B->next;while((q!=NULL)&&(q->data!=p->data))q=q->next;if((q!=NULL)&&(q->data==p->data)){

} p=p->next;t=(lnode*)malloc(sizeof(lnode));t->data=p->data;t->next=C->next;C->next=t;

while(s!=NULL){printf(“%5d”,s->data);} printf(“n”);} s=s->next;/********并集函數*************************/ void heji(linklist A,linklist B,linklist C){

lnode *p,*q,*t;p=A->next;while(p!=NULL){

} q=B->next;while(q!=NULL){ t=(lnode*)malloc(sizeof(lnode));t->data=p->data;t->next=C->next;C->next=t;p=p->next;

} p=A->next;while((p!=NULL)&&(p->data!=q->data))

p=p->next;if(p==NULL){

} q=q->next;t=(lnode*)malloc(sizeof(lnode));t->data=q->data;t->next=C->next;C->next=t;/*********************差集函數****************/ void chaji(linklist A,linklist B, linklist C){ lnode *p,*q,*s,*t;

p=A->next;

printf(“A與B的差集是:n”);while(p!=NULL){ q=B->next;while((q!=NULL)&&(p->data!=q->data))

} q=q->next;if(q==NULL){

} p=p->next;s=(lnode*)malloc(sizeof(lnode));s->data=p->data;s->next=C->next;C->next=s;output(C);C->next=NULL;

q=B->next;

printf(“B與A的差集是:n”);while(q!=NULL){

p=A->next;while((p!=NULL)&&(p->data!=q->data))p=p->next;if(p==NULL){ t=(lnode*)malloc(sizeof(lnode));

}

}

} t->data=q->data;t->next=C->next;C->next=t;q=q->next;output(C);}

四、測試數據及程序運行情況

程序運行結果:

八、心得體會

1、由于對集合的三種運算的算法推敲不足，在鏈表類型及其尾指針的設置時出現錯誤，導致程序低效。

2、剛開始時曾忽略了一些變量參數的標識”&”，使調試程序浪費時間不少。今后應重視確定參數的變量和賦值屬性的區分和標識。

3、開始時輸入集合后，程序只能進行一次運算，后來加入switch語句,成功解決了這一難題。

4、該算法并不能排除重復輸入相同字符的情況，也不能自動濾去非法字符(如空格、阿拉伯數字等)。

5、本程序的模塊劃分比較合理，且盡可能的將指針的操作封裝在節點和鏈表的兩個模塊中，致使集合模塊的調試比較

順利。

6、本實習作業采用數據抽象的程序設計方案，將程序化分為四個層次結構，使得設計時思路清晰，實現時調試順利，各模塊具有較好的可用性，確實得到了一次良好的程序設計訓練。

第二篇：數據結構課程設計(矩陣的運算)

數 據 結 構

課程設計報告

題 目： 專 業： 班 級： 學 號： 姓 名： 指導老師： 時 間：

一、課程設計題目及所涉及知識點

設計題目是“矩陣的運算”，所涉及的知識點主要是：

1、數據結構中的對于結構體的定義，用typedef struct來實現，根據所設計的問題在結構體里面定義數據類型及其變量，用define定義數組的大小，然后利用typedef 來實現對于變量的未知類型確定正確的類型。

2、利用數組的形式來儲存數據，在實現不同操作過程中，有的用一維結構體數組（三元組順序表）來存儲，有的用二維數組來儲存。

3、轉置的過程中利用的是快速轉置的方法，附設了num和cpot兩個輔助變量。

4、矩陣的加法、減法、乘法、逆運算的基本算法方式。

5、通過調用每個函數，來實現每個算法的功能。

二、課程設計思路及算法描述

設計思路：

1、首先是對于轉置的考慮，要運用快速轉置的方法實現，必須用三元組順序表來儲存數據，所以在第一個結構體中存在int類型的行數（mu）列數（nu）以及非零元素的個數（tu）；然后第二個結構體中分別有非零元素的行下標（i）、列下標（j）和元素數值（e），最后在第一個結構體中實現對第二個結構體成為數組結構體類型。

2、對于其余加法、減法、乘法和逆運算則是運用另一個結構體來實現，里面只有矩陣的行數、列數和一個二維數組（用float來定義類型）。

3、在main函數里面，來實現對于數據的輸入操作，利用if語句進行選擇來執行操作，利用do……while語句來實現功能的循環操作。

4、分五個函數調用分別來實現轉置、加法、乘法、和逆運算，每個里面都有最終輸出結果的方式。

算法1：矩陣的轉置

輸入：mu中存放矩陣的行數，tu存放矩陣的列數，i接收行下標的數值，j接收列下標的數值，e來存儲數據。輸出：轉置后的新矩陣。

輸入兩行兩列數據，在第二行第一列中有個數據為12，其余都為0，則輸出的結果為第一行第二列數據為12，其余為0。

算法2：矩陣的加法運算 輸入：i中存放矩陣的行數，j中存放矩陣的列數，二維數組b中存放每個數據。

輸出：矩陣加完后的另一個新矩陣。

輸入兩個兩行三列的矩陣，在第一個矩陣里面第一行第一列有個數據20，其余為0，在第二個矩陣里面第一行第二列中有個數據30，其余為0，則輸出的結果為一個兩行三列的矩陣，其中第一行第一列數據為20，第一行第二列數據為30，其余為0。

算法3：矩陣的減法運算

輸入：i中存放矩陣的行數，j中存放矩陣的列數，二維數組b中存放每個數據。

輸出：矩陣相減后的另一個新矩陣。

輸入兩個兩行三列的矩陣，在第一個矩陣里面第一行第一列有個數據20，其余為0，在第二個矩陣里面第一行第一列中有個數據30，其余為0，則輸出的結果為一個兩行三列的矩陣，其中第一行第一列數據為-10，其余為0。

算法4：矩陣的乘法運算

輸入：i中存放矩陣的行數，j中存放矩陣的列數，二維數組b中存放每個數據。

輸出：矩陣加完后的另一個新矩陣。

輸入兩行兩列的矩陣，第一個矩陣里面第一行第一列有個數據2第二列有個數據3，其余為0，在第二個矩陣里面第一行第一列有個數據2第二列中有個數據3，其余為0，則輸出的結果為一個兩行兩列的矩陣，其中第一行第一列數據為4，第二列為6，第一行第二列數據為30，其余為0。

算法五：矩陣的逆運算

輸入：i中存放矩陣的行數，j中存放矩陣的列數，二維數組b中存放每個數據。

輸出：矩陣進行逆運算完后的另一個新矩陣。

輸入三行三列的矩陣，第一個矩陣里面第一行第一列有個數據3個數據分別為1，2，3；第二行的數據分別為2，2，1；第三行的暑假分別為3，4，3；則輸出的結果為三行三列矩陣，其中第一行的數據為1，3，-2；第二行的數據分別為-1.5，-3，2.5；

第三行的數據分別為1，1，-1。

三、課程設計中遇到的難點及解決辦法

1、在轉置的過程中，要求把轉置后的矩陣輸出出來，因為用的是三元組順序表的存儲形式，所以不知道怎么去實現，然后通過進一步思考，運用先把一個矩陣存入零元素，然后在對其進行更改，最后完成了此項的工作。

2、就是對于矩陣的乘法運算和逆運算，掌握的不夠熟練，先是通過書籍對于矩陣的乘 法和逆運算得到更深的了解，然后通過一步步寫程序最后實現了矩陣的乘法運算和逆運算。

四、總結

通過此次課程設計，讓我對于編程有了更深的認識，老師的精心指導讓我學會到了很多，不僅僅是代碼，最主要的讓我的思維開闊了很多，在這個過程中，通過不斷的嘗試，不斷的修改，最終克服了困難，完成了自己的任務，心里有種無比的喜悅，但同時又感覺到了自己的知識面的狹隘，還有好多知識的海洋還沒有暢游，等待自己將是一回更大的考驗。

對于現在的自己，對學習程序還是有很大的興趣，它讓我體驗到了很多的快樂，我要進步跟進現在的課程，努力去發展自己，按照老師說的最主要的是具有了編程的思想，則具有了編程的能力，我想我可以成功完成自己的目標。

五、附錄—主要源程序代碼及運行結果

1、主要源程序代碼: # include # define max 100 # define maxsize 100 typedef float elemtype;typedef struct { float b[max][max];int i;//矩陣的行數 int j;// 矩陣的列數 } tsmatrix;typedef struct { int i,j;//該非零元的行下標和列下標

elemtype e;}triple;typedef struct { triple data[maxsize+1];//非零元三元組,data[0]未用 int mu,nu,tu;//矩陣的行數、列數和非零元個數 }sqlist;void zhuanzhi(sqlist s1,tsmatrix &l2)//矩陣的轉置

{ sqlist s2;int col,t9,p,q,a1,b1;int num[100],copt[100];s2.mu=s1.mu;s2.nu=s1.nu;s2.tu=s1.tu;if(s2.tu>0){ for(col=1;col<=s1.nu;++col)num[col]=0;for(t9=1;t9<=s1.tu;++t9)

++num[s1.data[t9].j];//求s1中每一列含非零元個數

copt[1]=1;//求第col列中第一個非零元在s2.data中序號

for(col=2;col<=s1.nu;++col)copt[col]=copt[col-1]+num[col-1];for(p=1;p<=s1.tu;++p)

{ col=s1.data[p].j;

q=copt[col];

s2.data[q].i=s1.data[q].j;s2.data[q].j=s1.data[q].i;s2.data[q].e=s1.data[q].e;++copt[col];

l2.b[s2.data[q].i][s2.data[q].j]=s2.data[q].e;} printf(“轉置后的數據是:n”);printf(“**************************************n”);for(a1=1;a1<=s1.nu;a1++){ for(b1=1;b1<=s1.mu;b1++){printf(“%10.3f”,l2.b[a1][b1]);

printf(“t”);} printf(“n”);} printf(“************************************”);printf(“n”);} } void jiafa(tsmatrix l4, tsmatrix l5)//矩陣的加法 {tsmatrix l6;for(int t=0;t

for(j=0;j<(2*s.i);j++)

{ if(j

else if(j==s.i+i)s1.b[i][j]=1.0;

else s1.b[i][j]=0.0;

}

for(i=0;i

{ for(k=0;k

{if(k!=i)

{ t=s1.b[k][i]/s1.b[i][i];

for(j=0;j<(2*s.i);j++)

{ x=s1.b[i][j]*t;

s1.b[k][j]=s1.b[k][j]-x;

}

}

}} for(i=0;i

s1.b[i][j]=s1.b[i][j]/t;} float y=1.0;for(i=0;i

printf(“對不起，您輸入的矩陣沒有逆矩陣”);

else

{ for(i=0;i

for(j=0;j

{ for(j=0;j

printf(“%10.3f”,s.b[i][j]);

printf(“n”);}}} void main(){ tsmatrix l,l1,l3;sqlist s;int m,n,m1,n1,n4,n5,t,t1,t2,t3,t4,t5,t6,t7,t8;do{ printf(“請輸入你要進行的操作：n”);

printf(“******************************n”);

printf(“矩陣轉置運算請按1n矩陣的加法運算請按2n矩陣的乘法運算請按3n矩陣的減法運算請按4n矩陣的逆運算請按5n結束請按0:n”);printf(“******************************n”);scanf(“%d”,&m1);if(m1==1){ printf(“您選擇進行的操作是矩陣的轉置運算nn”);

printf(“請輸入你要轉置矩陣的行數、列數和非零元的個數n”);scanf(“%d”,&t1);

scanf(“%d”,&t2);scanf(“%d”,&t3);s.mu=t1;s.nu=t2;s.tu=t3;printf(“請輸入你要轉置矩陣非零元的行下標、列下標(從[1][1]開始由左至右由上到下)及其數據(按行逐個輸入)n”);for(t4=1;t4<=s.tu;t4++){scanf(“%d”,&t5);scanf(“%d”,&t6);

s.data[t4].i=t5;s.data[t4].j=t6;

scanf(“%f”,&s.data[t4].e);} for(t7=1;t7<=s.nu;t7++){ for(t8=1;t8<=s.mu;t8++)l1.b[t7][t8]=0.0;} zhuanzhi(s,l1);} if(m1==2){ printf(“您選擇進行的操作是矩陣的加法運算nn”);printf(“請輸入矩陣的行數和列數:n”);scanf(“%d”,&n);scanf(“%d”,&m);l.i=n;l.j=m;l3.i=n;l3.j=m;printf(“******************************n”);printf(“請輸入第一個%d行%d列的矩陣n”,l.i,l.j);{ for(t=0;t

if(m1==5){ printf(“您選擇進行的操作是矩陣的逆運算nn”);printf(“請輸入矩陣的維數(即行和列相等的矩陣):n”);scanf(“%d”,&n);l.i=n;l.j=n;printf(“******************************n”);printf(“請輸入%d行%d列的矩陣n”,l.i,l.j);{ for(t=0;t

2、運行結果（如下圖）：

（1）、執行的首界面：

（2）、矩陣的轉置運算：

（3）、矩陣的加法運算：

（4）、矩陣的減法運算：

（5）、矩陣的乘法

（6）、矩陣的逆運算：

（7）、矩陣可以循環運算：

六、指導老師評語及成績

第三篇：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]='