第一篇：信管軟件11級數據結構課程設計
11級軟件、信管課程設計
要求：
本課程設計要求在17-18周完成，課程設計題目如附件所示，共有46題，題目分配方案如下：學號1號和16、31號可做1、16、31題，2號和17、32號可做2、17、32題?依此類推，每人可3選1做。信管1101、02、軟件1101班19周星期一下午15:00-17:00在我辦公室2501答辯（按學號來），課程設計的源程序學習委員將其匯總起來，然后一個班刻錄成一個光盤答辯時給我交過來，答辯人則只需帶好課程設計報告和演示程序過來。課程設計報告規范見另外一個文件，請大家重視這次課程設計，我會根據你的課程設計報告和答辯情況當時給該門課程的成績，不再另外安排時間接收課程設計報告的答辯要求，謝謝配合！
（光盤名字命名為軟件1101數據結構課程設計（每個同學一個文件夾，文件夾命名規則 學號+姓名+課題名））
-戴成秋 2012-12-27 課程設計題目：
1.運動會分數統計（難度***）
任務：參加運動會有10個學校，學校編號為1??10。比賽分成18個男子項目，和12個女子項目。項目編號為男子1??18，女子19??30。不同的項目取前三名積分，前三名的積分分別為：5、3、2。
功能要求：
1)可以輸入各個項目的前三名的成績； 2)能統計各學校總分；
3)可以按學校編號或名稱、學校總分、男女團體總分排序輸出； 4)數據存入文件并能隨時查詢
5)規定：輸入數據形式和范圍：可以輸入學校的名稱，運動項目的名稱
輸出形式：有中文提示，各學校分數為整型
存儲結構：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。（數據文件的數據讀寫方法等相關內容在java語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；
測試數據：測試數據及測試結果請在上交的資料中寫明；
2.飛機訂票系統（難度****）
任務：通過此系統可以實現如下功能：
錄入：
可以錄入航班情況（數據可以存儲在一個數據文件中，數據結構、具體數據自定）
查詢：
可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；
可以輸入起飛抵達城市，查詢飛機航班情況；
訂票：（訂票情況可以存在一個數據文件中，結構自己設定）
可以訂票，如果該航班已經無票，可以提供相關可選擇航班；
3.退票： 可退票，退票后修改相關數據文件；
客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。要求：
根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；
文章編輯（難度***）
功能：從鍵盤輸入一頁文字，靜態存儲在一個文件中 要求：（1）分別統計出其中英文字母數和空格數及整篇文章總字數；
（2）統計某一字符串在文章中出現的次數，并輸出該次數；（3）刪除某一子串，并將后面的字符前移。
存儲結構使用線性表，分別用幾個子函數實現相應的功能；
輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。
輸出形式：（1）分行輸出用戶輸入的各行字符；
（2）分4行輸出“全部字母數”、“數字個數”、“空格個數”、“文章總字數”（3）輸出刪除某一字符串后的文章；
4.哈希表設計[問題描述]
針對某個集體中人名設計一個哈希表，使得平均查找長度不超過R，并完成相應的建表和查表程序。
[基本要求]
假設人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數用除留余數法構造，用線性探測再散列法或鏈地址法處理沖突。
[測試數據]
取讀者周圍較熟悉的30個人名。
[選作內容]
（1）從教科書上介紹的集中哈希函數構造方法中選出適用者并設計幾個不同的哈希函數，比較他們的地址沖突率（可以用更大的名字集合作實驗）。
（2）研究這30個人名的特點，努力找一個哈希函數，使得對于不同的拼音名一定不發生地址沖突。
（3）在哈希函數確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希表中關鍵字的聚集性。
5.宿舍管理查詢軟件（難度**）
任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求：
（1）建立數據文件，數據文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)（2）實現如下查詢功能: 按姓名查詢 按學號查詢 按房號查詢
（3）打印任一查詢結果（可以連續操作）
6.校園導航問題（難度**）
設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。
7.圖書借閱管理系統（難度***）
主要分為兩大功能：
1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)；
8.學生成績管理（難度***）
實現功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。
9.活期儲蓄帳目管理（難度***）
活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統設計要求：
1)能比較迅速地找到儲戶的帳戶，以實現存款、取款記賬；
2)能比較簡單，迅速地實現插入和刪除，以實現開戶和銷戶的需要。
10.二叉排序樹的實現（難度**）
用順序和二叉鏈表作存儲結構
1)以回車('n')為輸入結束標志,輸入數列L，生成一棵二叉排序樹T； 2)對二叉排序樹T作中序遍歷，輸出結果；
3)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執行操作2)；否則輸出信息“無x”；
11.最小生成樹問題（難度**）
設計要求：在n個城市之間建設網絡，只需保證連通即可，求最經濟的架設方法。
12.通訊錄的制作（難度***）設計目的：用〈〈數據結構〉〉中的雙向鏈表作數據結構，結合java語言基本知識。編寫一個通訊錄管理系統。以把所學數據結構知識應用到實際軟件開發中去。設計內容：本系統應完成一下幾方面的功能：
1)輸入信息——enter();2)顯示信息———display();3)查找以姓名作為關鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設計要求：
1)每條信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項
2)作為一個完整的系統，應具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設計報告
13.哈夫曼編碼/譯碼器（難度**）【問題描述】
設計一個利用哈夫曼算法的編碼系統，重復地顯示并處理以下項目，直到選擇退出為止。【基本要求】
1)將權值數據存放在數據文件(文件名為data.txt，位于執行程序的當前目錄中)2)初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼；
5)設字符集及頻度如下表：
字符 空格 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
14.圖書管理系統（難度****）【問題描述】
設計一個計算機管理系統完成圖書管理基本業務。【基本要求】
1)每種書的登記內容包括書號、書名、著作者、現存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統主要功能如下：
*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加；
*借閱：如果一種書的現存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現存量；
*歸還：注銷對借閱者的登記，改變該書的現存量。
15.走迷宮游戲（難度***）
程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務是使用鍵盤上的方向鍵操縱老鼠在規定的時間內走到糧倉處。要求：
1)老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動； 2)迷宮的墻足夠結實，老鼠不能穿墻而過；
3)正確檢測結果，若老鼠在規定時間內走到糧倉處，提示成功，否則提示失敗； 4)找出走出迷宮的所有路徑，以及最短路徑。
16.順序結構、動態鏈表結構下的一元多項式加法的實現。（難度**）
設有一元多項式Am(x)和Bn(x).123m Am(x)=A0+A1x+A2x+A3x+? +Amx
123n Bn(x)=B0+B1x+B2x+B3x+? +Bnx
請實現求M(x)= Am(x)+Bn(x)要求：
1)結果M(x)中無重復階項和無零系數項； 2)要求輸出結果的升冪和降冪兩種排列情況
17.利用棧求表達式的值，可供小學生作業，并能給出分數。（難度*）要求：（1）判斷表達式是否正確，主要是括號問題
（2）題目涉及加減乘除，帶括弧的混合運算
18.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現，應包含建樹的實現。（難度*）要求：遍歷的內容應是千姿百態的。
19.敢死隊問題（難度**）
有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數數的辦法來決定哪個戰士去執行任務。如果前一個戰士沒完成任務，則要再派一個戰士上去。現給每個戰士編一個號，大家圍坐成一圈，隨便從某一個戰士開始計數，當數到5時，對應的戰士就去執行任務，且此戰士不再參加下一輪計數。如果此戰士沒完成任務，再從下一個戰士開始數數，被數到第5時，此戰士接著去執行任務。以此類推，直到任務完成為止。
排長是不愿意去的，假設排長為1號，請你設計一程序，求出從第幾號戰士開始計數才能讓排長最后一個留下來而不去執行任務。
20.猴子吃桃子問題（難度**）
有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現求出原來這群猴子共摘了多少個桃子。
要求：
1)采用數組數據結構實現上述求解 2)采用鏈數據結構實現上述求解 3)采用遞歸實現上述求解
21.數制轉換問題（難度**）
將一個十進制數轉換為二、八、十六進制數
22.排序綜合（難度**）
利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。要求：
1)至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。
2)統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。
23.最小生成樹求解實現（難度**）要求：
1)先任意創建一個圖；
2)設計克魯斯卡爾類，求出該圖的最小生成樹
24.線索二叉樹的應用（難度**）要求：建立線索樹。
25.稀疏矩陣應用（難度**）
要求：實現三元組下的稀疏矩陣的乘法。
26.樹的應用（難度**）
要求：實現樹與二叉樹的轉換的實現。
27.HTML文檔標記匹配算法（難度**）
要求：輸入一段HTML代碼，判斷該代碼是否符合HTML的語法
提示：HTML文檔由不同的標記劃分為不同的部分與層次。與括號類似，這些標記需要成對出現，對于名為
:節的頭部
?
HTML語言有合理的嵌套，如
第二篇：數據結構課程設計
課 程 設 計 任 務 書
信息 學院 信息管理與信息系統 專業 09級1班 班 孫鵬一、二、課程設計題目： 迷宮求解、一元多項式
課程設計主要參考資料： 數據結構（C語言版）嚴蔚敏、吳偉民 編著
數據結構題集（C語言版）嚴蔚敏、吳偉民、米寧 編著
數據結構課件
三、設計應解決下列各主要問題：
1.實現迷宮的路徑求解，并輸出最終路徑，標記走過卻未選擇的路徑和最終選擇的路徑
2.對一元多項式實現加法，減法，乘法，求導的計算，并按指數由大到小排序輸出
四、課程設計相關附件（如：圖紙、軟件等）：
五、命題發出日期：2011-3-15 設計應完成日期： 2010-6-20
設計指導教師（簽章）：
系主任（簽章）：
指導教師對課程設計的評語
指導教師（簽章）：
年 月 日
山東科技大學學生課程設計
課程設計1 迷宮問題
一、需求分析：
1.2.3.4.以二維數組Maze[][]表示迷宮
用戶輸入迷宮的數據：構建迷宮，行數m，列數n 迷宮的入口位置和出口位置可由用戶隨時設定
若設定的迷宮存在通路，則以長方陣形式將迷宮及其通路輸出到標準輸出文件（即終端）上，其中，字符“#”表示障礙，字符“*”表示路徑上的位置，字符“@”表示“死胡同”，即曾經途徑然而不能到達出口的位置，余者用空格符印出。若設定的迷宮不存在通路，則報告相應信息。
5.本程序只求出一條成功的通路。然而，只需要對迷宮求解的函數做小量修改，便可求得全部路徑。
二、概要設計：
抽象數據類型線性表的定義如下： ⒈ 設計棧的抽象數據類型定義：
ADT Stack { 數據對象：D={ai:|ai∈PositionSet,i=1?n,n≥0} 數據關系：R1={
Push(&S,e)Pop(&S,e)
返回其值 }ADT Stack；
⒉ 迷宮的抽象數據類型定義： ADT Maze{ 數據對象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0}
數據關系：R={ROW.COL} Row={
第1頁
操作結果
構造一個空棧，完成棧用e返回棧S的棧頂元將新的元素e壓入棧頂 刪除棧頂元素，并用eInitStack(&S)
山東科技大學學生課程設計
Col={
基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始條件：已知目前迷宮狀態, 傳過起始位置，和終止位置 操作結果：搜索迷宮，用sqstack s返回搜索所得路徑。如不存在，返回2 }ADT MAZE
三、詳細設計：
#include
typedef int Status;
typedef struct { int r;int c;}PostType;//坐標位置
迷宮的r行c列 typedef struct { int ord;//通道塊在路徑上的序號
PostType seat;//通道塊的當前坐標位置
int di;//通道塊指向下一通道塊的方向 }SElemType;//棧元素的類型 typedef struct { SElemType *base;//棧底指針
SElemType *top;//棧頂指針
int stacksize;//棧的最大容量 }Stack;//棧的類型
第2頁 山東科技大學學生課程設計
Status InitStack(Stack &S)//初始化棧 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)
exit(OVERFLOW);//存儲分配失敗;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//InitStack
Status StackEmpty(Stack S)//判斷棧是否為空,如果為空返回TRUE,否則返回FALSE { if(S.top==S.base)
return TRUE;
return FALSE;}//StackEmpty
Status Push(Stack &S,SElemType e)//插入元素為e的棧頂元素 { if(S.top-S.base>=S.stacksize){
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;} *S.top++=e;return OK;}//Push
Status Pop(Stack &S,SElemType &e)//刪除棧頂元素存入e { if(S.top==S.base)
return ERROR;e=*--S.top;
第3頁 山東科技大學學生課程設計
return OK;}//Pop
Status DestroyStack(Stack &S)//銷毀棧 { free(S.base);S.top=S.base;return OK;}//DestroyStack
//maze.cpp #define MAXLEN 20//迷宮包括外墻最大行列數目 typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType;
//迷宮類型
Status InitMaze(MazeType &maze){ //初始化迷宮若成功返回TRUE,否則返回FALSE
int m,n,i,j,k=1;
printf(“輸入迷口的行數和列數: ”);
scanf(“%d%d”,&maze.r,&maze.c);//迷宮行和列數
for(i=0;i<=maze.c+1;i++){//迷宮行外墻
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i<=maze.r+1;i++){//迷宮列外墻
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宮
printf(“輸入障礙物%d的坐標(以坐標(0,0)結束輸入): ”,k);
scanf(“%d%d”,&m,&n);
k++;
while(m!=0)
{
if(m>maze.r || n>maze.c)//越界
第4頁 山東科技大學學生課程設計
exit(ERROR);
maze.adr[m][n]='#';//迷宮障礙用'#'標記
printf(“輸入障礙物%d的坐標(以坐標(0,0)結束輸入): ”,k);
scanf(“%d%d”,&m,&n);
k++;
}
return OK;}//InitMaze
Status Pass(MazeType maze,PostType curpos){ //當前位置可通則返回TURE,否則返回FALSE
if(maze.adr[curpos.r][curpos.c]==' ')//可通
return TRUE;
else
return FALSE;}//Pass
Status FootPrint(MazeType &maze,PostType curpos){ //若走過并且可通返回TRUE,否則返回FALSE //在返回之前銷毀棧S
maze.adr[curpos.r][curpos.c]='*';//“*”表示可通
return OK;}//FootPrint
PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐標
PostType cpos;
cpos=curpos;
switch(i){
//1.2.3.4分別表示東,南,西,北方向
case 1 : cpos.c+=1;break;
case 2 : cpos.r+=1;break;
case 3 : cpos.c-=1;break;
case 4 : cpos.r-=1;break;
default: exit(ERROR);
}
return cpos;}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){ //曾走過但不是通路標記并返回OK
第5頁 山東科技大學學生課程設計
maze.adr[curpos.r][curpos.c]='@';//“@”表示曾走過但不通
return OK;}//MarkPrint
void PrintMaze(MazeType &maze)//將最后標記好的迷宮輸出 { int i,j;printf(“n輸出迷宮的路徑:n”);for(i=0;i<=maze.c+1;i++)
printf(“%4d”,i);//輸出列數
printf(“n”);for(i=0;i<=maze.r+1;i++){
printf(“%d”,i);//輸出行數
for(j=0;j<=maze.c+1;j++)
printf(“%4c”,maze.adr[i][j]);//輸出迷宮
printf(“n”);} }//PrintMaze
Status MazePath(MazeType &maze,PostType start,PostType end)//若迷宮從入口start到end的通道則求得一條存放在棧中 { Stack S;//初始化棧
PostType curpos;int curstep;SElemType e;InitStack(S);curpos=start;curstep=1;do {
if(Pass(maze,curpos))//當前位置可通過而未曾走過留下足跡
{
FootPrint(maze,curpos);
e.ord=curstep;e.seat=curpos;e.di=1;
Push(S,e);//加入棧路徑中
if(curpos.r==end.r && curpos.c==end.c)//到達出口返回TRUE
{
第6頁 山東科技大學學生課程設計
if(!DestroyStack(S))
exit(OVERFLOW);
else return TRUE;
}
else
{
curpos=NextPos(curpos,1);//下一位置是當前位置
curstep++;//探索下一步
}
}//if
else//當前位置不能通過
{
if(!StackEmpty(S))
{
Pop(S,e);//提取前一位置
while(e.di==4 &&!StackEmpty(S))//4個方向都不能通過則留下記號@ 提取前一個位置進行判斷是否是能通過
{
MarkPrint(maze,e.seat);
Pop(S,e);
}
if(e.di<4)//換下一個方向探索
設定當前位置為該新方向上的鄰位
{
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}
}//if
} }while(!StackEmpty(S));if(!DestroyStack(S))
exit(ERROR);else return FALSE;}//MazePath
int main(){ MazeType maze;PostType start,end;char c;
第7頁 山東科技大學學生課程設計
do {
printf(“**********迷宮求解**********n”);
if(!InitMaze(maze))
{
printf(“n 初始化迷宮失敗！!”);
exit(ERROR);
}
do
{
printf(“n請輸入入口的坐標:”);
scanf(“%d%d”,&start.r,&start.c);//輸入入口坐標
if(start.r>maze.r || start.c>maze.c)
printf(“n輸入錯誤,請重新輸入入口的坐標！n”);
continue;
}
while(start.r>maze.r || start.c>maze.c);
do
{
printf(“n請輸入出口的坐標:”);//輸入出口的坐標
scanf(“%d%d”,&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c)
printf(“n輸入錯誤,請重新輸入出口坐標！n”);
continue;
}
while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
printf(“n不能找到一條路徑！!n”);
else PrintMaze(maze);//輸出迷宮
printf(“是否要繼續?(y/n):”);
scanf(“%s”,&c);} while(c=='y' || c=='Y');}。測試結果：
第8頁
四、山東科技大學學生課程設計
課程設計2 一元多項式
一、需求分析：
第9頁 山東科技大學學生課程設計
1.2.3.首先定義一個結構體，其中定義一元多項式中的兩個參數:系數和指數和鏈表中結點的指針域；
然后一一羅列每個在主程序中用到的函數，并一一實現； 最后在主程序中主要完成用戶的輸入和相關函數的調用。
二、概要設計：
void insert(PLOYList *head,PLOYList *input)
//查找位置插入新鏈節的函數，且讓輸入的多項式呈降序排列 PLOYList *creat(char ch)//輸入多項式
PLOYList *add(PLOYList *head,PLOYList *pre)//多項式相加，head為第一個多項式建立的鏈表表頭，pre為第二個多項式建立的鏈表表頭
PLOYList *sub(PLOYList *head,PLOYList *pre)//多項式相減
PLOYList *mul(PLOYList *head,PLOYList *pre)//多項式相乘
PLOYList *der(PLOYList *head)//多項式求導
void print(PLOYList *fun)//輸出多項式，fun指要輸出的多項式鏈表的表頭 void start()//用戶選擇界面
三、詳細設計：
#include
//定義節點類型 { float coef;
//多項式的系數
int expn;
//多項式的指數
struct node * next;//結點指針域 }PLOYList;void insert(PLOYList *head,PLOYList *input)
//查找位置插入新鏈節的函數，且讓輸入的多項式呈降序排列 {
PLOYList *pre,*now;
int signal=0;
pre=head;
第10頁 山東科技大學學生課程設計
if(pre->next==NULL){pre->next=input;} //如果只有一個頭結點，則把新結點直接連在后面
else {
now=pre->next;//如果不是只有一個頭結點，則設置now指針
while(signal==0)
{
if(input->expn < now->expn)
{
if(now->next==NULL)
{
now->next=input;
signal=1;
}
else
{
pre=now;
now=pre->next;//始終讓新輸入的數的指數與最后一個結點中的數的指數比較，小于則插在其后面
}
}
else if(input->expn > now->expn)
{
input->next=now;
pre->next=input;
signal=1;
}//若新結點中指數比最后一個結點即now中的指數大，則插入now之前
else//若指數相等則需合并為一個結點，若相加后指數為0則釋放該結點
{
now->coef=now->coef+input->coef;
signal=1;
free(input);
if(now->coef==0)
{
pre->next=now->next;
free(now);
}
}//else } //while
第11頁 山東科技大學學生課程設計
}//else }//void
PLOYList *creat(char ch)
//輸入多項式 {
PLOYList *head,*input;
float x;
int y;
head=(PLOYList *)malloc(sizeof(PLOYList));
//創建鏈表頭
head->next=NULL;
scanf(“%f %d”,&x,&y);//實現用戶輸入的第一個項，包括其指數和系數
while(x!=0)
{
input=(PLOYList *)malloc(sizeof(PLOYList));//創建新鏈節
input->coef=x;
input->expn=y;
input->next=NULL;
insert(head,input);//每輸入一項就將其排序，是的鏈表中多項式呈降序排列
scanf(“%f %d”,&x,&y);
} return head;}
PLOYList *add(PLOYList *head,PLOYList *pre)
//多項式相加，head為第一個多項式建立的鏈表表頭，pre為第二個多項式建立的鏈表表頭 {
PLOYList *input;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//若該鏈表為空，則無需進行加法運算，跳出循環
else
{
pre=pre->next;
input=(PLOYList *)malloc(sizeof(PLOYList));
第12頁 山東科技大學學生課程設計
input->coef=pre->coef;
input->expn=pre->expn;
input->next=NULL;
insert(head,input);// 把g(x)插入到f(x）中，相當于兩者相加，結果保存于f(x)
}
} return head;}
PLOYList *sub(PLOYList *head,PLOYList *pre)//多項式相減 {
PLOYList *input;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;
else
{
pre=pre->next;
input=(PLOYList *)malloc(sizeof(PLOYList));
input->coef=0-pre->coef;//將第二個多項式里的數變為其相反數，再用和加法一樣的方法實現減法
input->expn=pre->expn;
input->next=NULL;
insert(head,input);
}
} return head;}
PLOYList *mul(PLOYList *head,PLOYList *pre)//多項式項乘 { PLOYList *hf,*pf,*qa,*qb;
qa = head-> next;
qb = pre-> next;//定義指針指向表頭后一個元素，即鏈表中第一個元素
hf =(PLOYList *)malloc(sizeof(PLOYList));//新創建一個結點，當做表頭
hf-> next = NULL;for(;qa;qa = qa-> next)
第13頁 山東科技大學學生課程設計
{
for(qb = pre-> next;qb;qb= qb-> next)//用兩個循環，實現兩個多項式之間每個項相乘，結果用insert函數進行排序與合并
{
pf =(PLOYList *)malloc(sizeof(PLOYList));
pf-> coef = qa-> coef * qb-> coef;//系數相乘
pf-> expn = qa-> expn + qb-> expn;//指數相加
pf-> next = NULL;
insert(hf,pf);
} } return hf;}
PLOYList *der(PLOYList *head)//多項式求導 { PLOYList *p;p = head-> next;while(p){
p-> coef = p-> coef * p-> expn;
p-> expn = p-> expn--;
p = p-> next;} return head;}//將多項式的每項系數和指數相乘得到新的系數，指數減一得到新的指數即完成求導
void print(PLOYList *fun)//輸出多項式，fun指要輸出的多項式鏈表的表頭 {
PLOYList *printing;
int flag=0;
printing=fun->next;
if(fun->next==NULL)//若為空表，則無需輸出
{
printf(“0n”);
return;
}
while(flag==0)
{
第14頁 山東科技大學學生課程設計
if(printing->coef>0&&fun->next!=printing)
printf(“+”);
if(printing->coef==1);
else if(printing->coef==-1)
printf(“-”);
else
printf(“%f”,printing->coef);
if(printing->expn!=0)printf(“x^%d”,printing->expn);
else if((printing->coef==1)||(printing->coef==-1))
printf(“1”);
if(printing->next==NULL)
flag=1;
else
printing=printing->next;
} printf(“n”);}
void start()//用戶選擇界面 { printf(“
#n”);
printf(“
用戶選擇界面
n”);
printf(“ ************************************n”);
printf(“ *
*n”);
printf(“ *
1.兩個一元多項式相加
*n”);
printf(“ *
2.兩個一元多項式相減
*n”);
printf(“ *
3.兩個一元多項式相乘
*n”);
printf(“ *
4.對一個一個一元多項式求導 *n”);
printf(“ *
0.退出系統
*n”);
printf(“ *
*n”);
printf(“ ************************************n”);
printf(“
n”);
printf(“ 注釋：輸入多項式格式（可無序）：系數1 指數1 系數2 指數2 ??，并以0 0 結束：n”);
printf(“
n”);
printf(“ 請選擇操作: ”);}
int main(){ PLOYList *f,*g,*pf,*hf,*p;
第15頁 山東科技大學學生課程設計
int sign=-1;
start();
while(sign!=0)
{
scanf(“%d”,&sign);
switch(sign)
{
case 0:
break;
case 1://多項式相加
{
printf(“ 你選擇的操作是多項式相加:n”);
printf(“ 請輸入第一個多項式f(x)：”);
f=creat('f');
printf(“ 第一個多項式為：f(x)=”);
print(f);
printf(“ 請輸入第二個多項式g(x)：”);
g=creat('g');
printf(“ 第二個多項式為：g(x)=”);
print(g);
printf(“ 結果為：F(x)=f(x)+g(x)=”);
f=add(f,g);
print(f);
printf(“nn”);
printf(“ 繼續請選擇相應操作，退出請按0.break;
}
case 2://多項式相減
{
printf(” 你選擇的操作是多項式相減:n“);
printf(” 請輸入第一個多項式f(x)：“);
f=creat('f');
printf(” 第一個多項式為：f(x)=“);
print(f);
printf(” 請輸入第二個多項式g(x)：“);
g=creat('g');
printf(” 第二個多項式為：g(x)=“);
print(g);
printf(” 結果為：F(x)=f(x)-g(x)=“);
f=sub(f,g);
print(f);
”);第16頁
山東科技大學學生課程設計
printf(“nn”);
printf(“ 繼續請選擇相應操作，退出請按0.”);
break;
}
case 3://多項式相乘
{
printf(“ 你選擇的操作是多項式相乘:n”);
printf(“ 請輸入第一個多項式f(x)：”);
f=creat('f');
printf(“ 第一個多項式為：f(x)=”);
print(f);
printf(“ 請輸入第二個多項式g(x)：”);
g=creat('g');
printf(“ 第二個多項式為：g(x)=”);
print(g);
printf(“ 結果為：F(x)=f(x)* g(x)=”);
pf=mul(f,g);
print(pf);
printf(“nn”);
printf(“ 繼續請選擇相應操作，退出請按0.”);
break;
}
case 4://多項式求導
{
printf(“您選擇的是對一個一元多項式求導：n”);
printf(“請輸入一個一元多項式：”);
f = creat('f');
printf(“這個多項式為：f(x)= ”);
print(f);
printf(“求導結果為：F(x)=f'(x)= ”);
f=der(f);
print(f);
printf(“nn”);
printf(“ 繼續請選擇相應操作，退出請按0.”);
break;
}
}//swith
}//while }//void
四、測試結果：
第17頁 山東科技大學學生課程設計
第18頁
第三篇：數據結構課程設計
南京航空航天大學金城學院
《數據結構》 課程設計報告
題目：一元多項式的加減乘法運算
班級： 20100232 學號： 2010023220 姓名： 祁博 成績：
指導教師： 葉延風
完成日期： 2012年 2月18 日
課程設計的主要內容 需求分析
1.1課程設計題目
用線性表實現一元多項式的加法減法與乘法。
1.2課程設計的任務及要求
任務：利用所學線性表知識來完成計算器中一元多項式的加法減法與乘法的運算。要求：能自己創建線性表，能自主的進行線性表的有關插入刪除操作，并且可以在此基礎上實現線性表之間的加減乘除運算。
1.3課程設計思想
首先要定義一個結構體，其中定義一元多項式的兩個參數，系數和指數和鏈表中的指針域，然后一一羅列每個在主程序中得到的函數，并一一實現，最后在主程序中主要完成用戶的輸入和相關程序的調用。
1.4軟件開發的環境
VC++6.0。
? 2.程序源代碼
#include
typedef struct node{//定義節點類型
float coef;int expn;
struct node * next;}Ployn;
void menu()//用戶選擇界面
{
printf(“************************************n”);
printf(“ 兩個一元多項式的相加/相減，相乘:n”);
printf(“************************************n”);
printf(“請選擇操作:n”);
printf(“0.退出n”);
printf(“1.兩個一元多項式相加n”);
printf(“2.兩個一元多項式相乘n”);
printf(“3.兩個一元多項式相減n”);
}
void insert(Ployn *head,Ployn *inpt)//查找位置插入新鏈節程序
{
Ployn *pre,*now;
int signal=0;
pre=head;//pre定義為現在的前一個鏈節
if(pre->next==NULL){pre->next=inpt;}
else {now=pre->next;while(signal==0){
if(inpt->expn>now->expn)//當新鏈節小于現在的連接時向后移一個鏈節
{
if(now->next==NULL)
{
now->next=inpt;
signal=1;
}
else
{
pre=now;
now=pre->next;
}
}
else if(inpt->expn
{
inpt->next=now;
pre->next=inpt;
signal=1;
}
else
{
now->coef=now->coef+inpt->coef;
signal=1;
free(inpt);//與當前鏈節相等指數
if(now->coef==0)
{
pre->next=now->next;
free(now);
}
} } } }
Ployn *creat(char ch)//輸入多項式
{
Ployn *head,*inpt;
float x;
int y;
head=(Ployn *)malloc(sizeof(Ployn));//創建鏈表頭
head->next=NULL;
printf(“請輸入一元多項式%c:(格式是：系數 指數；以0 0 結束！)n”,ch);
scanf(“%f %d”,&x,&y);
while(x!=0)
{
inpt=(Ployn *)malloc(sizeof(Ployn));//創建新鏈節
inpt->coef=x;
inpt->expn=y;
inpt->next=NULL;
insert(head,inpt);//不然就查找位置并且插入新鏈節
printf(“請輸入一元多項式%c的下一項:(以0 0 結束！)n”,ch);
scanf(“%f %d”,&x,&y);
}
return head;}
Ployn *addPloyn(Ployn *head,Ployn *pre)//多項式相加
{
Ployn *inpt;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//當現在指向空時跳出循環
else
{
pre=pre->next;
inpt=(Ployn *)malloc(sizeof(Ployn));//創建新鏈節
inpt->coef=pre->coef;
inpt->expn=pre->expn;
inpt->next=NULL;
insert(head,inpt);
}//否則把當前“g(x)”的鏈節插入到“y(x)”中
}
return head;}
Ployn *minusPloyn(Ployn *head,Ployn *pre)//多項式相加
{
Ployn *inpt;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//當現在指向空時跳出循環
else
{
pre=pre->next;
inpt=(Ployn *)malloc(sizeof(Ployn));//創建新鏈節
inpt->coef=0-pre->coef;
inpt->expn=pre->expn;
inpt->next=NULL;
insert(head,inpt);
}//否則把當前“g(x)”的鏈節插入到“y(x)”中
}
return head;}
Ployn *byPloyn(Ployn *head1,Ployn *head2)//多項式相乘
{
Ployn *inpt,*res,*pre;
int flag=0;
res=(Ployn *)malloc(sizeof(Ployn));//創建鏈表頭
res->next=NULL;
head1=head1->next;
pre=head2;
while(flag==0)
{
if(pre->next==NULL)
{
pre=head2;//當現在指向空時跳出循環
head1=head1->next;
continue;
}
if(head1==NULL)
{
flag=1;//當現在指向空時跳出循環
continue;
}
pre=pre->next;
inpt=(Ployn *)malloc(sizeof(Ployn));//創建新鏈節
inpt->coef=pre->coef*head1->coef;
inpt->expn=pre->expn+head1->expn;
inpt->next=NULL;
insert(res,inpt);//把當前“g(x)”的鏈節插入到“y(x)”中
}
return res;}
void print(Ployn *fun)//輸出多項式
{
Ployn *printing;
int flag=0;
printing=fun->next;//正在被打印的鏈節
if(fun->next==NULL)//如果函數為空打印0
{
printf(“0n”);
return;}
while(flag==0)
{
if(printing->coef>0 && fun->next!=printing)
printf(“+”);//為正數且不為第一項時打印“+”號
if(printing->coef==1);//如果為“1”就不用打印系數了
else if(printing->coef==-1)
printf(“-”);//如果為“-1”就打印“-”號就行了
else
printf(“%f”,printing->coef);//其余情況都得打印
if(printing->expn!=0)//如果指數為“0”不打印指數項
{ if(printing->expn==1)printf(“x”);
else printf(“x^%d”,printing->expn);
}
else if((printing->coef==1)||(printing->coef==-1))
printf(“1”);
if(printing->next==NULL)
flag=1;//如果現在的鏈節沒有下一個就結束
else
printing=printing->next;
}
printf(“n”);}
void main(){
Ployn *f,*g;
int sign=-1;//設置標志
menu();
while(sign!=0)
{
scanf(“%d”,&sign);
switch(sign){
case 0: break;//退出
case 1:
{
printf(“你選擇的操作是多項式相加:n”);
f=creat('f');//輸入多項式f(x)
printf(“f(x)=”);
print(f);
g=creat('g');//輸入多項式g(x)
printf(“g(x)=”);
print(g);
printf(“F(x)=f(x)+g(x)=”);
f=addPloyn(f,g);//兩個多項式相加
print(f);
sign=-1;//復位標志
menu();//回復用戶選擇界面
break;
}
case 2:
{
printf(“你選擇的操作是多項式相乘:n”);
f=creat('f');//輸入多項式f(x)
printf(“f(x)=”);
print(f);
g=creat('g');//輸入多項式g(x)
printf(“g(x)=”);
print(g);
printf(“F(x)=f(x)*g(x)=”);
f=byPloyn(f,g);//兩個多項式相加
print(f);
sign=-1;//復位標志
menu();//回復用戶選擇界面
break;
}
case 3:
{
printf(“你選擇的操作是多項式相減:n”);
f=creat('f');//輸入多項式f(x)
printf(“f(x)=”);
print(f);
g=creat('g');//輸入多項式g(x)
printf(“g(x)=”);
print(g);
printf(“F(x)=f(x)-g(x)=”);
f=minusPloyn(f,g);//兩個多項式相加
print(f);
sign=-1;//復位標志
menu();//回復用戶選擇界面
break;
}
default:
{
printf(“輸入有誤!請重新選擇操作!n”);//選擇錯誤,返回選擇界面
menu();
break;
}
}
} }
? 3.心得體會
每次做課設都有很大的收獲。課設不僅是對課本知識的理論實踐，更是對自我的一種挑戰。
這次課設過程中，遇到很多的問題，讓我有種無從下手的感覺，但是辦法總比困難多，于是，在老師、同學的幫助下，以及自己在翻書、上網找資料的情況下，順利解決問題。于是，我又上課的認識到，團隊的重要性。
第四篇：數據結構課程設計
河海大學計算機與信息學院（常州）
數據結構課程設計
課程設計題目：
多 項 式 問 題
專業、年級：計算機科學與技術09級 學
號：
0962810226
姓
名：
王
超
目 錄
一、問題描述-------------3
二、需求分析-------------4
三、概要設計-------------4 1.概要設計目的與要求--4 2.概要設計內容--------4 3.功能算法描述與數據結構說明-------------------------5
四、詳細設計-------------5
五、系統測試-------------8
六、使用說明-------------9
七、總結及心得體會-----10
多項式問題
一．問題描述
給你九個整數，這九個整數分別是x的8次方至0次方的系數，請你按照多項式的一半形式合理地構造（去除不必要的）。例如九個系數分別是為0,0，0,1,22，-333,0,1，-1，你要構造并輸出一行多項式：x^5 + 22x^4 – 333x^3 + x – 1。
它的格式規則如下：
1.多項式的項必須按其指數從高到低排列。2.指數必須跟在符號“^”后顯示。3.有常數的只顯示常數項（無需跟x^0）。
4.只顯示系數不為0的項；若系數全為0，需顯示常數項。
5.在多項式中唯一需要空格的地方是項與項之間的加號或減號的兩邊需加上空格。
6.如果首項的系數是正數，則系數前不加符號；如果首項的系數是負數，則符號與數字之間不加空格，就如：-3x^2 +-2x。
7.系數為1，指數為0時，系數的1才顯示（推廣到系數為-1）。
輸入/輸出說明
1.輸入/輸出方式為文件方式，輸入文件有一行或多行的系數，系數之間有空格分隔。
2.每行共有九個系數，每個系數的絕對值為小于1000的整數。輸出文件包含構造完地多項式，每行一個多項式。
輸入范例
0 0 0 1 22-333 0 1-1 0 0 0 0 0 0-55 5 0
輸出范例
x^5 + 22x^4 – 333x^3 + x – 1-55x^2 + 5x
二．需求分析
2.1可行性研究
該程序主要從技術的角度來分析可行性。技術上的可行性研究主要分析技術條件能否順利完成開發工作，硬、軟件能否滿足開發者的需要等。該系統采用了Windows 7操作系統結合Visual C++ 6.0等軟件開發平臺已成熟可行。硬件方面，科技飛速發展的今天，硬件更新的速度越來越快，容量越來越大，可靠性越來越高，其硬件平臺也比較能滿足此系統的需要。
2.2結構與主要功能模塊
從實現多項式輸出過程的角度來分析，至少需要這樣一些子功能模塊。如： 1.多項式創建功能；
2.多項式輸出功能；
3.釋放多項式功能；
4.操作界面顯示功能；
三．概要設計
1.概要設計目的與要求
通過多項式程序設計，使我們進一步掌握和利用C++語言進行結構化程序設計的能力；進一步理解和運用結構化程設計的思想和方法；初步掌握開發一個小型系統程序設計的基本方法；學會調試一個較長程序的基本方法；以及掌握書寫課程設計開發文檔的能力（書寫課程設計報告）。總之，通過本課程設計加深對《C++語言》及《數據結構》課程所學知識的理解，進一步鞏固C++語言語法規則，在程序中體現出算法的思想，提高程序的運行效率。學會編制結構清晰、風格良好、數據結構適當的C++語言程序，從而具備解決綜合性實際問題的能力。
2.概要設計內容
多項式輸出程序具有以下基本功能：
1．創建多項式。接收輸入的數據，并保存到鏈表中。
2．Txt文檔輸入輸出功能。
3． 清除內存內容，釋放創建的鏈表，退出程序。
3.功能算法描述與數據結構說明
該多項式程序除了main()函數外，主要有以下函數：
node *CreatePolyn()
void firstnode(node *p)
void othernode(node *p)
void PrintPolyn(node *Pa)
void deletechain(node *h)
下面對這些函數逐一介紹。①.main（）函數
main函數主要調用其他函數，用來實現輸入、顯示功能。
在main（）函數中，定義一維數組p[]用來保存多項式的系數，Pa定義程序所需鏈表的頭指針。在程序開始要求輸入多項式的系數，隨后創建鏈表以保存多項式，再顯示出構建的符合要求的多項式。②.node *CreatePolyn()該函數功能是創建新的多項式鏈表。使用for語句，控制輸入多項式的每一項。
③.void firstnode(node *p)該函數功能是判斷輸出多項式第一項。對于第一項的系數為1或-1，指數為0或-1等五種情況進行討論。④.void othernode(node *p)該函數功能是判斷輸出多項式除第一項外的其它項。對于第一項的系數為1或-1，指數為0或-1等五種情況進行討論。⑤.void PrintPolyn(node *Pa)該函數功能：顯示構造的符合要求的多項式鏈表。在該函數中調用③、④函數，進行多項式的輸出。⑥.void deletechain(node *h)該函數的功能是釋放掉創建的鏈表，釋放內存。
四．詳細設計
下面討論重要函數具體實現過程：
1.node *CreatePolyn()定義int i=9計數，當i>0時，for語句反復提示用戶輸入該多項式的每一項的指數。當i=1時，輸入完畢，該鏈表也創建完畢。詳細的實現過程如下：
node *CreatePolyn(){ node *head,*pa,*s;int i;
pa=head=new node;//創建一個新的結點
head->next=NULL;
for(i = 9;i >0;i--)// 依次輸入9項
{
s=new node;
s->next=NULL;
s->coef = p[9-i];
s->exp=i-1;//x指數從8遞減到0
if(s->coef!=0)//系數不為零時，結點p鏈接s
{
pa->next=s;
pa=s;
} } return head;} 2.void firstnode(node *p)對多項式第一項輸出可能性進行多種分類討論。
void firstnode(node *p)//輸出多項式第一個結點 { //指數不為1且不為0,系數絕對值不為1（正常的輸出）if(p->exp!=1&&p->exp&&fabs(p->coef)!=1)
{
if(p->coef>0)
{
outfile<
coef<<“X^”<
exp;
}
else
{
outfile<
coef<<“X^”<
exp;
} } if(p->exp==0)//指數為0，即常數項
{
if(p->coef>0)
{
outfile<
coef;
}
else
{
outfile<
coef;
} }
//指數大于0且不為1，系數絕對值為1 if(p->exp>0&&fabs(p->coef)==1&&p->exp!=1){
if(p->coef>0)
{
outfile<<“X^”<
exp;
}
else
{
outfile<<“-X^”<
exp;
} } if(p->exp==1&&fabs(p->coef)!=1)//指數為1且系數絕對值不為1 {
if(p->coef>0&&p->coef!=1)
{
outfile<
coef<<“X”;
}
if(p->coef<0&&p->coef!=-1)
{
outfile<
coef<<“X”;
} } if(p->exp==1&&fabs(p->coef)==1)//指數為1且系數絕對值為1 {
if(p->coef==1)
outfile<<“X”;
else
outfile<<“-X”;} }
3.void PrintPolyn(node *Pa)該函數有一個參數，該指針指向多項式鏈表的頭指針，以下是實現插入的關鍵代碼： void PrintPolyn(node *Pa){ node *p;if(Pa->next==NULL)//首項判斷，如果首項無，則顯示“0”
outfile<<“0”;
return;else {
firstnode(Pa->next);} p=Pa->next->next;//定義指針p指向Pa的下下個指針
while(p!=NULL){
othernode(p);
p=p->next;
//將p指向下個一個結點
}
outfile< 五．系統測試 該程序在VC6.0中調試通過，沒有錯誤和警告，運行結果經過檢驗為正確。以下圖為該程序運行結果效果圖： 圖5-1 范例 圖5-2 一行輸出 圖5-3 多行輸出 六．使用說明 1．打開1.txt文件，在里面任意輸入9個整數，每個數字間要有空格，可以輸入一行或者多行，輸入多行的時候需要換行。 2.編譯運行后，打開2.txt文件，即可看到輸出的符合要求的多項式。 七．總結及心得體會 通過這次課程設計練習，使我更深刻地理解了C++語言的精髓-----指針的使用。完成整個程序設計有很大的收獲，對指針掌握的更加熟練。 同時通過直接對單鏈表的操作，加深了對數據結構的理解和認識。并在完成課程設計的過程作主動查閱了相關資料，學到了不少課本上沒有的技術知識。 經過這次課程設計，我深刻認識到算法在程序設計中的重要性，如何讓程序簡單、易讀是這個課程設計的難點。程序總是由若干個函數構成的，這些相應的函數體現了算法的基本思想。 編程是一件枯燥乏味工作，但是只要認真專研，我們會從中學到很多在課本上學不到或者無法在課堂上掌握的知識，同時也能從中感受到編程的樂趣。興趣是可以培養的，只要堅持下去，面對困難我們總能夠找到解決問題的方法。 計算多項式的輸出-----該程序雖然不是很大，但是自己獨立完成這一任務也遇到不少的困難。另外也需要提出的是，非常感謝老師對我們的耐心指導，尤其是上機的時候給了我很多鍛煉的機會。所以這次課程設計我才能夠順利的完成。 一、課程題目：一元稀疏多項式計算器 二、需求分析 1、一元稀疏多項式簡單計算器的功能是： 1.1 輸入并建立多項式； 1.2 輸出多項式，輸出形式為整數序列：n，c1,e1,c2,e2,???cn,en,其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數降序排列； 1.3多項式a和b相加，建立多項式a+b； 1.4 多項式a和b相減，建立多項式a-b。 2、設計思路: 2、設計思路： 2.1 定義線性表的動態分配順序存儲結構； 2.2 建立多項式存儲結構，定義指針*next 2.3利用鏈表實現隊列的構造。每次輸入一項的系數和指數，可以輸出構造的一元多項式 2.4演示程序以用戶和計算機的對話方式執行，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規定的運行命令； 根據相應的輸入數據（濾去輸入中的非法字符）和運算結果顯示在其后。 3、程序執行的命令包括： 1）輸入多項式a；2）輸入多項式b;3）求a+b;4)求a-b；5）求a*b；6）求a的導數；7）求b的導數；8）退出程序。 4、測試數據： 1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); 2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x); 3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5); 4、(x+x^3)+(-x-x^3)=0; 5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200); 6、(x+x^2+x^3)+0=x+x^2+x^3.7、互換上述測試數據中的前后兩個多項式 三、概要設計 為了實現上述功能需用帶表頭結點的單鏈表存儲多項式。為此需要兩個抽象的數據類型：線性表和多項式。 1.有序表的抽象數據類型定義為： ADT List{ 數據對象：D={ai|ai∈Elemset,i=1,2,?，n,n≥0} 數據關系：R1={ 2、多數據類型定義為： ADT Polynomial { 數據對象:D={ai,bi|ai為不為0的實數，bi為整數，i=2,?,n} 數據關系:R1={ai，bi} 基本操作： PrintPolyn(Polyn p)操作結果:輸出多項式p。DestroyPolyn(Polyn p)操作結果:銷毀多項式p。 Polyn CreatePolyn(Polyn head,int m)操作結果:創建一個m項的多項式。Polyn AddPolyn(Polyn pa,Polyn pb)初始條件:多項式鏈表pa,pb存在。 操作結果:創建一新多項式鏈表p，其結點為pa，pb相加。Polyn SubtractPolyn(Polyn pa,Polyn pb)初始條件:多項式鏈表pa，pb存在。 操作結果:創建一新多項式鏈表p，其結點為怕pa，pb相減。ValuePolyn(Polyn head,int x)操作結果:輸入x值，計算并返回多項式的值 }ADT Polynomial 四、詳細設計 1、元素類型、結點類型和指針類型 typedef int Status;typedef struct{ int coef;int expn;}Term;typedef Term ElemType;typedef struct LNode{ ElemType data;//數據域 struct LNode *next;//指針域 }LNode,* LinkList; 2、主函數和其他函數 void main(){ int m,n,a,x;int flag;Polynomial pa,pb,pc;printf(“ 歡迎使用多項式操作程序n”); //輸出菜單 printf(“n 1: 創建多項式a n”);printf(“n 2: 創建多項式b n”);printf(“n 3: 輸出多項式a n”);printf(“n 4: 輸出多項式b n”);printf(“n 5: 輸出a+b n”);printf(“n 6: 輸出a-b n”);printf(“n 7: 輸出a的導數 n”);printf(“n 8: 輸出b的導數 n”);printf(“n 9: 代入x的值計算a n”);printf(“n 10: 代入x的值計算b n”);printf(“n 11: 輸出a*b n”);printf(“n 12:退出程序 n”);while(a){ printf(“n請選擇操作：”);scanf(“ %d”,&flag); switch(flag) { case 1 : { printf(“請輸入a的項數:”);scanf(“%d”,&m);CreatePolyn(pa,m); break; } case 2 : { printf(“請輸入b的項數:”);scanf(“%d”,&n);CreatePolyn(pb,n); break; } case 3 : { printf(“n 多項式a=”); PrintPolyn(pa); break; } case 4 : { printf(“n 多項式b=”); PrintPolyn(pb); break; } case 5 : { AddPolyn(pa,pb,pc);printf(“n a+b=”); PrintPolyn(pc); break; } case 6 : { SubtractPolyn(pa,pb,pc);printf(“n a-b=”); PrintPolyn(pc); break; } case 7 : { Polynomial_derivatePolyn(pa,pc); printf(“n 多項式a的導函數為：a'=”); PrintPolyn(pc); break; } case 8 : { Polynomial_derivatePolyn(pb,pc); printf(“n 多項式b的導函數為：b'=”); PrintPolyn(pc); break; } case 9 : { printf(“輸入x的值：x=”); scanf(“%d”,&x); printf(“n x=%da=%.3fn”,x,ValuePolyn(pa,x)); break; } case 10 : { printf(“輸入x的值：x=”); scanf(“%d”,&x); printf(“n x=%d，時 時b=%.3fn”,x,ValuePolyn(pb,x)); break; } case 11 : { MultiplyPolyn(pa,pb,pc);printf(“n a*b=”); PrintPolyn(pc); break; } case'12': { printf(“n 感謝使用此程序！n”); DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; } default: printf(“n 您的選擇錯誤，請重新選擇!n”); } } } 3、建立一個頭指針為head、項數為m的一元多項式, 建立新結點以接收數據, 調用Insert函數插入結點 Status CreatePolyn(Polynomial &head,int m){ //建立一個頭指針為head、項數為m的一元多項式 int i;LNode *p;p=head=(Polynomial)malloc(sizeof(struct LNode));head->next=NULL;for(i=0;i printf(“請輸入第%d項的系數與指數:”,i+1);scanf(“%d %d”,&p->data.coef,&p->data.expn);Insert(p,head);//調用Insert函數插入結點 } return OK;}//CreatePolyn 4、求解并建立多項式a+b Status AddPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多項式a+b，返回其頭指針 LNode *qa=pa->next;LNode *qb=pb->next;LNode *headc,*hc,*qc;hc=(Polynomial)malloc(sizeof(struct LNode));//建立頭結點 hc->next=NULL;headc=hc;while(qa||qb){ qc=(Polynomial)malloc(sizeof(struct LNode));switch(compare(qa,qb)){ case 1: { qc->data.coef=qa->data.coef;qc->data.expn=qa->data.expn;qa=qa->next;break; } case 0: { qc->data.coef=qa->data.coef+qb->data.coef;qc->data.expn=qa->data.expn;qa=qa->next;qb=qb->next;break; } case-1: { qc->data.coef=qb->data.coef;qc->data.expn=qb->data.expn;qb=qb->next;break; } } if(qc->data.coef!=0) { qc->next=hc->next;hc->next=qc;hc=qc; } else free(qc);//當相加系數為0時，釋放該結點 } pc=headc;return OK;} 5、求解并建立多項式a-b Status SubtractPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多項式a-b，返回其頭指針 LNode *h=pb;LNode *p=pb->next;LNode *pd,*pf;while(p){ //將pb的系數取反 p->data.coef*=-1;p=p->next;} AddPolyn(pa,h,pf);pd=pf;for(p=h->next;p;p=p->next)//恢復pb的系數 p->data.coef*=-1;pc=pd;return OK;} float ValuePolyn(Polynomial head,int x){ //輸入x值，計算并返回多項式的值 LNode *p;int i,t;float sum=0;for(p=head->next;p;p=p->next){ t=1;for(i=p->data.expn;i!=0;) { if(i<0){t/=x;i++;} //指數小于0，進行除法 else{t*=x;i--;} //指數大于0，進行乘法 } sum+=p->data.coef*t;} return sum;} 6、求解并建立導函數多項式 Status Polynomial_derivatePolyn(Polynomial P,Polynomial &pc)//求導 { LNode *p,*pf,*ph;//用于遍歷結點 p=P->next; ph=(Polynomial)malloc(sizeof(struct LNode)); ph->next=NULL; //pre=P; while(p!=NULL) { pf=(Polynomial)malloc(sizeof(struct LNode)); if(p->data.expn==0) { p=p->next; //free(p); //p=pre->next; } else { pf->data.coef=p->data.coef*p->data.expn; pf->data.expn=p->data.expn-1; Insert(pf,ph); p=p->next; } } pc=ph;return OK;} 7、求解并建立多項式a*b Status MultiplyPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多項式a*b，返回其頭指針 LNode *hf,*pf;LNode *qa=pa->next;LNode *qb=pb->next;hf=(Polynomial)malloc(sizeof(struct LNode));//建立頭結點 hf->next=NULL;for(;qa;qa=qa->next){ for(qb=pb->next;qb;qb=qb->next) { pf=(Polynomial)malloc(sizeof(struct LNode));pf->data.coef=qa->data.coef*qb->data.coef;pf->data.expn=qa->data.expn+qb->data.expn;Insert(pf,hf);//調用Insert函數以合并指數相同的項 } } pc=hf;return OK;} 8、函數的調用關系圖 主函數Pa pb pc數meadreturn headc*h項回*h 建立鏈表Polyn CreatePolyn(Polyn head,int m)多項式相加Polyn AddPolyn(Polyn pa,Polyn pb)返回*hc返輸出多項式While{Printf(“”); 四、調試分析 5.1 運行該程序的操作平臺： 5.1.1 硬件要求： 此程序需在一臺PC機上運行,要用INTER或AMD的CPU,其他沒多大要求。5.1.2 軟件要求： 本程序能在Visual C++ 6.0下運行。5.2 錯誤分析： 1、函數名拼寫錯誤 2、括號匹配錯誤 3、變量類型名定義錯誤 4、分號沒有在英文環境下輸出，導致運行出錯 5、參數表出現語法錯誤，函數調用的一組參數之間沒有以逗號隔開，并以一個右括號結束 六、用戶手冊 1、本程序的執行文件為：Cpp1.exe。 2、進入演示程序后即顯示文本方式的用戶界面。 3、根據提示數字執行操作。如輸入數字“1” 4、執行相應命令后顯示操作結果。 七、測試結果 1、最初的界面 2、選擇操作“1”、“2”“3”、“4”，輸入數字得到的結果，即創建多項式a和b 3、a+b 4、a-b 5、a*b 6、求導 7、帶入x值求a，b 八、心得體會 通過這次課程設計，我覺得我們對于《數據結構》的學習不僅包括理論部分的學習，還要勤動手，多實踐。真正將這個程序做出來很不容易，但只要只要用心去做，總會有收獲,特別是當我遇到問題時，通過向同學請教,最后終于找到方法時,并理解代碼的含義時，心中是無比喜悅的。編寫程序中遇到問題再所難免,應耐心探究其中的原因,從出現問題的地方起,并聯系前后程序,仔細推敲,逐個排查.直到最終搞清為止。第五篇：數據結構課程設計
點擊咨詢 