第一篇：數(shù)據(jù)結(jié)構(gòu)課程設計論文
09數(shù)據(jù)結(jié)構(gòu)課程設計論文
課題：
一、迷宮求解
二、撲克牌游戲
三、joseph環(huán)
四、商品貨架管理
五、航空客運訂票系統(tǒng)
………………………………………………………………………………
班級：07信息與計算科學 學生：XXX 學號：
指導老師：XXX
目錄
課程設計封…………………………………………………………………1 目錄……………………………………………………………………2 迷宮求解………………………………………………………………3—9
（一）需求分析……………………………………………………………3
（二）源程序……………………………………………………………4—5
（三）測試后的結(jié)果……………………………………………………6—7
（四）結(jié)果分析……………………………………………………………8 撲克牌游戲……………………………………………………………9—10
（一）需求分析……………………………………………………………9
（二）源程序……………………………………………………………9
（三）測試后的結(jié)果………………………………………………………9
（四）結(jié)果分析…………………………………………………………10 joseph環(huán)……………………………………………………………10—16
（一）需求分析……………………………………………………………11
（二）源程序…………………………………………………………12—14
（三）測試后的結(jié)果…………………………………………………15—16
（四）結(jié)果分析……………………………………………………………16 商品貨架管理………………………………………………………16—17
（一）需求分析……………………………………………………………16
（二）源程序……………………………………………………………16
（三）測試后的結(jié)果……………………………………………………16
（四）結(jié)果分析…………………………………………………………17 航空客運訂票系統(tǒng)…………………………………………………18—24
（一）需求分析……………………………………………………………18
（二）源程序……………………………………………………19—20
（三）測試后的結(jié)果…………………………………………………20—22
（四）結(jié)果分析…………………………………………………………24 課程設計心得體會…………………………………………………24—25
課題設計1：迷宮求解
一.需求分析：
本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。
首先由用戶輸入一組二維數(shù)組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標記所走過的路徑結(jié)束程序；當迷宮無路徑時，提示輸入錯誤結(jié)束程序。
二、概要設計： 1.抽象數(shù)據(jù)類型定義：
ADT Find{ 數(shù)據(jù)對象：D={ai?ai ∈ElemSet,i=1,2,…,n,n≥0} 數(shù)據(jù)關系：R1={
find(&S)初始條件：已初始化棧S，且棧為空
操作結(jié)果：從棧Ｓ中找出相對應的數(shù)據(jù)關系，并輸出結(jié)果 }ADT Find 2.主程序的流程以及各程序模塊之間的調(diào)用關系：(1).定義變量i、j、w、z為整形變量(2).輸入迷宮二維數(shù)組maze(0:m,0:n)(3).調(diào)用子程序find()(4).結(jié)束程序
三、相應的源程序如下： #include
{ int row, line;
}PosType;
typedef struct
{
int di, ord;
PosType seat;
}SElemType;
typedef struct { SElemType * base;SElemType * top;int
stacksize;}SqStack;Status InitStack(SqStack &S);
Status Push(SqStack &S,SElemType &a);
Status Pop(SqStack &S,SElemType &a);
Status StackEmpty(SqStack S);
Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end);void Initmaze(int maze[12][12],int size);
void printmaze(int maze[12][12],int size);
Status Pass(int maze[12][12],PosType CurPos);
void Markfoot(int maze[12][12], PosType CurPos);
PosType NextPos(PosType CurPos, int Dir);
void printpath(int maze[12][12],SqStack S,int size);void main(void){
SqStack S;int size,maze[12][12];for(int n=0;n<10;n++){
printf(“創(chuàng)建一個正方形迷宮，請輸入迷宮尺寸(注意不要大于50):n”);
scanf(“%d”,&size);if(size<1 || size>10){printf(“輸入錯誤!”);return;}
Initmaze(maze,size);
printmaze(maze,size);
PosType start,end;
printf(“輸入入口行坐標和列坐標:”);scanf(“%d”,&start.row);scanf(“%d”,&start.line);
printf(“輸入出口行坐標和列坐標:”);scanf(“%d”,&end.row);scanf(“%d”,&end.line);
if(MazePath(maze,S,start,end))
printpath(maze,S,size);
else printf(“找不到通路!nn”);} } Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end)
{
PosType curpos;int curstep;SElemType e;InitStack(S);curpos = start;
curstep = 1;
do {
if(Pass(maze,curpos))
{
Markfoot(maze,curpos);
e.di =1;
e.ord = curstep;
e.seat= curpos;
Push(S,e);
if(curpos.row==end.row && curpos.line==end.line)
return OK;
curpos = NextPos(curpos, 1);
curstep++;
}
else
{
if(!StackEmpty(S))
{
Pop(S,e);
while(e.di==4 &&!StackEmpty(S))
{
Markfoot(maze,e.seat);
Pop(S,e);
}
if(e.di<4)
{
e.di++;
Push(S, e);
curpos = NextPos(e.seat, e.di);
}
}
}
} while(!StackEmpty(S));return ERROR;}
void Initmaze(int maze[12][12],int size){
char select;
printf(“選擇創(chuàng)建方式 A:自動生成 B:手動創(chuàng)建n”);
label:scanf(“%c”,&select);if(select=='a'||select=='A')
{
for(int i=0;i for(i=1;i { maze[i][0]=1; for(int j=1;j maze[i][j]=rand()%2; maze[i][size+1]=1; } for(i=0;i } else if(select=='b'||select=='B') { printf(“按行輸入%d*%d數(shù)據(jù),0代表可通,1代表不可通(每行以Enter結(jié)束):n”,size,size); for(int i=0;i for(i=1;i { maze[i][0]=1; for(int j=1;j scanf(“%d”,&maze[i][j]); maze[i][size+1]=1; } for(i=0;i } else if(select=='n')goto label; else printf(“輸入錯誤!”);} void printmaze(int maze[12][12],int size){ printf(“nn”);printf(“顯示所建的迷宮(#表示外面的墻):n”); for(int i=0;i printf(“%c ”,'#'); for(int j=1;j { printf(“%d ”,maze[i][j]); } printf(“%c”,'#'); printf(“n”); } for(i=0;i void printpath(int maze[12][12],SqStack S,int size){ printf(“nn通路路徑為:n”);SElemType * p=S.base;while(p!=S.top){ maze[p->seat.row][p->seat.line]=2; p++;} for(int i=0;i printf(“%c ”,'#'); for(int j=1;j { if(maze[i][j]==2)printf(“%c ”,'0'); else printf(“ ”); } printf(“%c”,'#'); printf(“n”);} for(i=0;i Status Pass(int maze[12][12],PosType CurPos){ if(maze[CurPos.row][CurPos.line]==0) return OK; else return ERROR; } void Markfoot(int maze[12][12],PosType CurPos){ maze[CurPos.row][CurPos.line]=1;} PosType NextPos(PosType CurPos, int Dir){ PosType ReturnPos;switch(Dir) { case 1: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line+1; break; case 2: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line; break; case 3: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line-1; break; case 4: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line; break;} return ReturnPos;} Status InitStack(SqStack &S){ S.base=(SElemType *)malloc(100*sizeof(SElemType));if(!S.base)return ERROR;S.top=S.base;S.stacksize=100;return OK;} Status Push(SqStack &S,SElemType &a){ *S.top++=a;return OK;} Status Pop(SqStack &S,SElemType &a){ if(S.top==S.base)return ERROR;a=*--S.top;return OK;} Status StackEmpty(SqStack S){ if(S.top==S.base)return OK;return ERROR;} 以下為測試數(shù)據(jù)： 輸入一個矩陣，例如：1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 輸入入口行坐標和列坐標：1 2 輸入出口行坐標和列坐標：5 5 通路路徑為： 課題設計2：撲克牌游戲 1、問題描述 編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到 最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過，輸出：這時正面向上的牌有哪些？ 存儲結(jié)構(gòu)： 源程序：#include int i,j,a[52];for(i=2;i<=52;i++)for(j=i-1;j<52;j+=i) a[j]=!a[j];printf(“正面向上的牌有:”);for(i=0;i<52;i++)if(a[i]) printf(“%4d”,i+1);} 測試結(jié)果：正面向上的牌有：1 4 9 16 25 36 49 算法的時間復雜度：T（n）=O（n2） 課題設計3：joseph環(huán) 一.需求分析：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。首先創(chuàng)建一個空鏈表，初始化鏈表，構(gòu)造出一個只有頭結(jié)點的空鏈表，建立好一個約瑟夫環(huán)。1.輸入的形式和輸入值的范圍 本程序中，輸入報數(shù)上限值m和人數(shù)上限l，密碼，均限定為正整數(shù)，輸入的形式為一個以“回車符”為結(jié)束標志的正整數(shù)。2.輸出的形式 從屏幕顯示出列順序。3.程序功能 提供用戶從鍵盤輸入，Joseph約瑟夫環(huán)的必要數(shù)據(jù)，并顯示出列順序。 二、概要設計 以單向循環(huán)鏈表實現(xiàn)該結(jié)構(gòu)。1.抽象數(shù)據(jù)類型的定義為： ADT LNode { 10 數(shù)據(jù)對象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0} 數(shù)據(jù)關系：R1={< ai-1，ai > | ai ∈D，I=2，…，n} 三．源程序：#include struct Node *next;//指向下一個節(jié)點 }Node,*Link;void InitList(Link &L)//創(chuàng)建一個空的鏈表 { L=(Node *)malloc(sizeof(Node));if(!L)exit(1);L->key=0;L->num=0;L->next=L;} void Creater(int n,Link &L)//初始化鏈表 { Link p,q;q=L;for(int i=1;i<=n;i++){ p=(Node *)malloc(sizeof(Node));if(!p)exit(1);printf(“the key_%d is:”,i);scanf(“%d”,&p->key);p->num=i;L->next=p;L=p;} L->next=q->next;free(q);} void main(){ Link L,p,q;int n,x;L=NULL;InitList(L);//構(gòu)造出一個只有頭結(jié)點的空鏈表 printf(“please input the totle number of people:”);scanf(“%d”,&n);//總共的人數(shù)n printf(“the start key is:”); scanf(“%d”,&x);//初始密碼為x Creater(n,L);//建立好一個約瑟夫環(huán) p=L;for(int i=1;i<=n;i++){ for(int j=1;j 四、測試數(shù)據(jù)： m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4 輸出：6 7 4 1 5 3 2 課題設計4：商品貨架管理 1、需求分析：設計一個算法，每一次上貨后始終保持生產(chǎn)日期越近的商品越靠近棧底。求貨架上剩余貨物M、每天銷售件數(shù)N、員工每天上貨工作時間T，三者之間有何關系及T的最小值。 2、源程序：#include #include“stdio.h” const int maxsize=100;const int k=10;#define elemtype char typedef struct { int Month;int Day;int Year;}DATE;typedef struct { int num;DATE date;} Node;class seqstack { public: Node stack[maxsize];int top;void inistack(){ top=0;} void push(int x,int day,int month,int year){ if(top==maxsize)cout<<“貨架已滿”< } } void pop(){ if(top==0)cout<<“貨架已空”< int Tx[k+1];//第i種每天上貨的總時間 int T=0;//每天上貨用的總時間 char yn='Y';for(int i=1;i<=k;i++){ cout<<“ ******************************”< char year,month;int count;//貨架上第i種商品的數(shù)目 int x,d,m,y;//x為第i種商品的序號 cout<<“請輸入貨架上第”< cin>>numbers>>nian>>yue>>ri;if(numbers>maxsize-count){ cout<<“要上的貨物數(shù)目超出了貨架的最大容量，請重新輸入”< 3、測試結(jié)果： 五、課程設計5：航空客運訂票系統(tǒng) 1、需求分析： 對于本設計，可采用基數(shù)排序法對于一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快遞查找，按其他次關鍵字的查找可采用最簡單的順序查找方法進行，因為它們用的較少。 2、源程序：#include { keytype keys[keylen];infotype others;int next;}slnode;typedef struct { slnode sl[maxspace];int keynum;int length;}sllist;typedef int arrtype_n[radix_n];typedef int arrtype_c[radix_c];void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e){ int j,p;for(j=0;j while(j p=l.sl[p].next;q=l.sl[p].next;if(p!=i){ temp=l.sl[p];l.sl[p]=l.sl[i];l.sl[i]=temp;l.sl[i].next=p;} p=q;} } int binsearch(sllist l,keytype key[]){ int low,high,mid;low=1;high=l.length;while(low<=high){ mid=(low+high)/2;if(strcmp(key,l.sl[mid].keys)==0)return mid;else if(strcmp(key,l.sl[mid].keys)<0)high=mid-1;else low=mid+1;} return 0;} void seqsearch(sllist l,keytype key[],int i){ int j,k,m=0;printf(“*************************************************************n”);printf(“* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *n”);for(j=1;j<=l.length;j++){ 20 switch(i){ case 2:k=strcmp(key,l.sl[j].others.start);break;case 3:k=strcmp(key,l.sl[j].others.end);break;case 4:k=strcmp(key,l.sl[j].others.time1);break;case 5:k=strcmp(key,l.sl[j].others.time2);break;} if(k==0){ m=1;printf(“* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n”,l.sl[j].keys,l.sl[j].others.start,l.sl[j].others.end,l.sl[j].others.sche,l.sl[j].others.time1,l.sl[j].others.time2,l.sl[j].others.model,l.sl[j].others.price);} } if(m==0)printf(“* 無此航班信息，可能是輸入錯誤！*n”);printf(“*************************************************************n”);} void searchcon(sllist l){ keytype key[keylen];int i=1,k;while(i>=1&&i<=5){ printf(“n ********************n”);printf(“ * 航班信息查詢系統(tǒng) *n”);printf(“ ********************n”);printf(“ * 1.航 班 號 *n”);printf(“ * 2.起 點 站 *n”);printf(“ * 3.終 點 站 *n”);printf(“ * 4.起飛時間 *n”);printf(“ * 5.到達時間 *n”);printf(“ * 0.退出系統(tǒng) *n”);printf(“ ********************n”);printf(“ 請選擇(0-5):”);21 scanf(“%d”,&i);printf(“n”);switch(i){ case 1:printf(“輸入要查詢的航班號(字母要大寫):”);scanf(“%s”,key);k=binsearch(l,key);printf(“*************************************************************n”);if(k==0)printf(“* 無此航班信息，可能是輸入錯誤！*n”);else { printf(“* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *n”);printf(“* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n”,l.sl[k].keys,l.sl[k].others.start,l.sl[k].others.end,l.sl[k].others.sche,l.sl[k].others.time1,l.sl[k].others.time2,l.sl[k].others.model,l.sl[k].others.price);} printf(“*************************************************************n”);break;case 2:printf(“輸入要查詢的航班起點站名:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 3:printf(“輸入要查詢的航班終點站名:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 4:printf(“輸入要查詢的航班起飛時間:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 5:printf(“輸入要查詢的航班到達時間:”);scanf(“%s”,key);seqsearch(l,key,i);break;case 0:printf(“nnn 再 見nnn”);22 } } } void inputdata(sllist &l){ int i=++l.length;char yn='y';while(yn=='y'||yn=='Y'){ printf(“航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價n”);scanf(“%s%s%s%s%s%s%s%d”,l.sl[i].keys,l.sl[i].others.start,l.sl[i].others.end,l.sl[i].others.sche,l.sl[i].others.time1,l.sl[i].others.time2,l.sl[i].others.model,&l.sl[i].others.price);++i;getchar();radixsort(l);arrange(l);printf(“繼續(xù)輸入嗎?y/n:”);scanf(“%c”,&yn);} l.length=i-1;} void main(){ sllist l;l.keynum=6;l.length=0;inputdata(l);searchcon(l);} 3、測試結(jié)果： 航班信息：航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 輸入：CA1544 合肥 北京 1.2.4.5 1055 1240 733 960 提示：繼續(xù)輸入嗎？y/n：y 顯示：航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 MU5341 上海 廣州 每日 1420 1615 M90 1280 提示：繼續(xù)輸入嗎？y/n：y …… 提示：繼續(xù)輸入嗎？y/n:n 最后，課程設計心得體會： 通過這次課程設計，我感覺到要真正做出一個程序并不很容易，但只要用心去做，總會有收獲，特別是當我遇到一個問題，想辦法去解決時，最后終于找到方法時，心里的那份喜悅之情真是難以形容。編寫的過程中不可避免的遇到問題，這些問題有的只是一個符號錯了，一個括號少了，應耐心探究其中的原因，從出現(xiàn)問題的地方起，并聯(lián)系前后程序，仔細推敲，逐個排查。直到最終搞清為止。當然，在學習中不要害怕提問，但是這個問題最好是你找不到答案的時候再去提。要經(jīng)過自己的思考后在去提問，那樣才會有效果。 通過一些課程設計，也讓自己對于數(shù)據(jù)結(jié)構(gòu)有了更深層次的理解，雖然有很多的東西并不是自己編，而是在網(wǎng)上找的，但是在調(diào)試的那個過程中也是收獲很多。本次課程設計，使我對《數(shù)據(jù)結(jié)構(gòu)》這門課程有了更深入的理解。《數(shù)據(jù)結(jié)構(gòu)》是一門實踐性較強的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。指針其實是C語言的靈魂，許多的數(shù)據(jù)結(jié)構(gòu)在我們學到這里之前都可以說是精通了。所以我們的任務就是，讓數(shù)據(jù)結(jié)構(gòu)在指針中運行。當然，剛剛開始接觸到這些新的東西，是一件非常痛苦的事情，所以我們一定要用非常形象的思維去看待指針，不能太固化。所以，新的東西，比如結(jié)構(gòu)體在指針中的表現(xiàn)方法，數(shù)組及 24 多維數(shù)組在結(jié)構(gòu)體中的運用，都一點一點的加了進來，同時豐滿了我們對原來C的數(shù)據(jù)機構(gòu)，數(shù)據(jù)表示的理解。 《數(shù)據(jù)結(jié)構(gòu)》就是編程的思維，編程的靈魂，算法的精髓所在，沒有了數(shù)據(jù)結(jié)構(gòu)，程序就好像一個空核，是低效率的。學習數(shù)據(jù)結(jié)構(gòu)的目的就是提高自己的思想，數(shù)據(jù)結(jié)構(gòu)的高低是確定于你寫的程序的運行效率，想不想到奇異的方法解決問題，程序的壯健性，并不是你記得多少算法。就好像我現(xiàn)在排序算法已經(jīng)忘記了很多，平衡二叉樹的建立跟刪除，圖論完全忘記。難道這樣我就是初學者？？肯定不是，自要有思想在，有些算法用到的時候看看書就可以了。在課程設計中，我明白了理論與實際應用相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設計技能以及合作能力。這次課程設計同樣提高了我的綜合運用所學知識的能力。 課程設計是培養(yǎng)學生綜合運用所學知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學生實際工作能力的具體訓練和考察過程.隨著科學技術發(fā)展的日新日異，單片機已經(jīng)成為當今計算機應用中空前活躍的領域，在生活中可以說得是無處不在。 通過這段時間的課程設計，我認識到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程。需要多花時間上機練習。這次的程序訓練培養(yǎng)了我實際分析問題、編程和動手能力，使我掌握了程序設計的基本技能，提高了我適應實際，實踐編程的能力。 剛開始做這個程序的時候，感到完全無從下手，覺得讓我完成這次程序設計根本就是不可能的，于是開始查閱一些資料，如：蘇仕華的《數(shù)據(jù)結(jié)構(gòu)課程設計》之后便開始著手對于一些程序調(diào)試以及去看明白。 整個程序和以往所編的程序最大的區(qū)別就是要求從文件讀入信息，文件是C語言中極其重要的部分，通過課程設計，加深了對文件知識的掌握。我的程序原先是只能從固定的一個文件讀入圖的信息，經(jīng)過修改，它可以通過輸入文件名來選擇要讀入的文件，使程序更加靈活，功能更加完善。 通過課程設計還提高了一點改錯能力，對于一些常見問題加深了印象。如果我們把編程當作一種樂趣的話，用興趣去引領學習的話，你會發(fā)現(xiàn)學習編碼的速度會更快，因為在這個過程中你會有強烈的欲望去看懂它，你會把編碼分到最細，這樣的成功，對于我們今后的編程學習將會有很大的信心。 數(shù) 據(jù) 結(jié) 構(gòu) 課程設計報告 題 目： 一元多項式計算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學 號： 201201011367 姓 名： 左帥帥 指導老師： 郝慎學 時 間： 一、課程設計題目分析 本課程設計要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項式的加法、減法、乘法、除法運算等功能。 二、設計思路 本程序采用C語言來完成課程設計。 1、首先，利用順序存儲結(jié)構(gòu)來構(gòu)造兩個存儲多項式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運算分成五個主要的模塊：實現(xiàn)多項式輸入模塊、實現(xiàn)加法的模塊、實現(xiàn)減法的模塊、實現(xiàn)乘法的模塊、實現(xiàn)除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實現(xiàn)其功能，盡量減少程序運行時錯誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實現(xiàn)對多項式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。 三、設計算法分析 1、相關函數(shù)說明： (1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈式存儲結(jié)構(gòu)類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項式函數(shù)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) 輸出函數(shù)輸出多項式，void Print(Polyn P) 銷毀多項式函數(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表示每一項前的系數(shù)，expn表示每一項的指數(shù)，polyn為結(jié)點指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對象名。 (2)當用戶輸入兩個一元多項式的系數(shù)和指數(shù)后，建立鏈表，存儲這兩個多項式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數(shù)為m的一元多項式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點 這就建立一元多項式的關鍵步驟 (3)由于多項式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對多項式按指數(shù)進行降冪排序。在這個程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進行處理，此處由于反復使用指針對各個結(jié)點進行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進行插入操作。(4)加、減、乘、除、的算法實現(xiàn)： 在該程序中，最關鍵的一步是實現(xiàn)四則運算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負的加法實現(xiàn)；對于乘除算法的大致流程都是：首先建立多項式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數(shù)。這就實現(xiàn)了多項式計算模塊的主要功能。 (5)另一個子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計算合并的鏈表逐個結(jié)點依次輸出，便得到整鏈表，也就是最后的計算式計算結(jié)果。由于考慮各個結(jié)點的指數(shù)情況不同，分別進行了判斷處理。 四、程序新點 通過多次寫程序，發(fā)現(xiàn)在程序在控制臺運行時總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺背景顏色，0是控制臺輸出字體顏色。 五、設計中遇到的問題及解決辦法 首先是，由于此次課程設計里使用指針使用比較多，自己在指針多的時候易腦子混亂出錯，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進行 4 代碼編寫。 其次是，在寫除法模塊時比較復雜，自己通過查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設計時的一個經(jīng)驗吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過本次應用C語言設計一元多項式基本計算程序，使我更加鞏固了C語言程序設計的知識，以前對指針這一點使用是比較模糊，現(xiàn)在通過此次課程設計對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關算法和函數(shù)的調(diào)用方面知識的加深。本次的課程設計，一方面提高了自己獨立思考處理問題的能力；另一方面使自己再設計開發(fā)程序方面有了一定的小經(jīng)驗和想法，對自己以后學習其他語言程序設計奠定了一定的基礎。 八、指導老師評語及成績 附錄：（課程設計代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點 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é)點 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時將結(jié)點插入 } 7 } //建立一個頭指針為head、項數(shù)為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));//建立新結(jié)點以接收數(shù)據(jù) printf(“請輸入第%d項的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點 } 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;//項數(shù)計數(shù)器 if(!q)//若多項式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項 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多項式已空，但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));//建立頭結(jié)點 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);//當相加系數(shù)為0時，釋放該結(jié)點 } return headc;} //求解并建立多項式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) //恢復pb的系數(shù) 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));//建立頭結(jié)點 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ù)相同的項 } } 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));//建立頭結(jié)點,存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點，存儲余數(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)的項數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項式A printf(“n”);printf(“請輸入B(x)的項數(shù):”);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(”執(zhí)行操作:“); 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);} 數(shù)據(jù)結(jié)構(gòu)課程設計 1.赫夫曼編碼器 設計一個利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并處理以下項目，直到選擇退出為止。要求： 1)將權值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個字符和26個權值（統(tǒng)計一篇英文文章中26個字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實現(xiàn)屏幕輸出，然后實現(xiàn)文件輸出）； 5)界面優(yōu)化設計。 代碼如下： #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) //把權值保存到文件 { 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) //對結(jié)點進行譯碼 { 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]='
第二篇：2012數(shù)據(jù)結(jié)構(gòu)課程設計
第三篇：數(shù)據(jù)結(jié)構(gòu)課程設計