第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
課 程 設(shè) 計(jì) 任 務(wù) 書
信息 學(xué)院 信息管理與信息系統(tǒng) 專業(yè) 09級(jí)1班 班 孫鵬一、二、課程設(shè)計(jì)題目： 迷宮求解、一元多項(xiàng)式
課程設(shè)計(jì)主要參考資料： 數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏、吳偉民 編著
數(shù)據(jù)結(jié)構(gòu)題集（C語言版）嚴(yán)蔚敏、吳偉民、米寧 編著
數(shù)據(jù)結(jié)構(gòu)課件
三、設(shè)計(jì)應(yīng)解決下列各主要問題：
1.實(shí)現(xiàn)迷宮的路徑求解，并輸出最終路徑，標(biāo)記走過卻未選擇的路徑和最終選擇的路徑
2.對(duì)一元多項(xiàng)式實(shí)現(xiàn)加法，減法，乘法，求導(dǎo)的計(jì)算，并按指數(shù)由大到小排序輸出
四、課程設(shè)計(jì)相關(guān)附件（如：圖紙、軟件等）：
五、命題發(fā)出日期：2011-3-15 設(shè)計(jì)應(yīng)完成日期： 2010-6-20
設(shè)計(jì)指導(dǎo)教師（簽章）：
系主任（簽章）：
指導(dǎo)教師對(duì)課程設(shè)計(jì)的評(píng)語
指導(dǎo)教師（簽章）：
年 月 日
山東科技大學(xué)學(xué)生課程設(shè)計(jì)
課程設(shè)計(jì)1 迷宮問題
一、需求分析：
1.2.3.4.以二維數(shù)組Maze[][]表示迷宮
用戶輸入迷宮的數(shù)據(jù)：構(gòu)建迷宮，行數(shù)m，列數(shù)n 迷宮的入口位置和出口位置可由用戶隨時(shí)設(shè)定
若設(shè)定的迷宮存在通路，則以長方陣形式將迷宮及其通路輸出到標(biāo)準(zhǔn)輸出文件（即終端）上，其中，字符“#”表示障礙，字符“*”表示路徑上的位置，字符“@”表示“死胡同”，即曾經(jīng)途徑然而不能到達(dá)出口的位置，余者用空格符印出。若設(shè)定的迷宮不存在通路，則報(bào)告相應(yīng)信息。
5.本程序只求出一條成功的通路。然而，只需要對(duì)迷宮求解的函數(shù)做小量修改，便可求得全部路徑。
二、概要設(shè)計(jì)：
抽象數(shù)據(jù)類型線性表的定義如下： ⒈ 設(shè)計(jì)棧的抽象數(shù)據(jù)類型定義：
ADT Stack { 數(shù)據(jù)對(duì)象：D={ai:|ai∈PositionSet,i=1?n,n≥0} 數(shù)據(jù)關(guān)系：R1={
Push(&S,e)Pop(&S,e)
返回其值 }ADT Stack；
⒉ 迷宮的抽象數(shù)據(jù)類型定義： ADT Maze{ 數(shù)據(jù)對(duì)象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0}
數(shù)據(jù)關(guān)系：R={ROW.COL} Row={
第1頁
操作結(jié)果
構(gòu)造一個(gè)空棧，完成棧用e返回棧S的棧頂元將新的元素e壓入棧頂 刪除棧頂元素，并用eInitStack(&S)
山東科技大學(xué)學(xué)生課程設(shè)計(jì)
Col={
基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始條件：已知目前迷宮狀態(tài), 傳過起始位置，和終止位置 操作結(jié)果：搜索迷宮，用sqstack s返回搜索所得路徑。如不存在，返回2 }ADT MAZE
三、詳細(xì)設(shè)計(jì)：
#include
typedef int Status;
typedef struct { int r;int c;}PostType;//坐標(biāo)位置
迷宮的r行c列 typedef struct { int ord;//通道塊在路徑上的序號(hào)
PostType seat;//通道塊的當(dāng)前坐標(biāo)位置
int di;//通道塊指向下一通道塊的方向 }SElemType;//棧元素的類型 typedef struct { SElemType *base;//棧底指針
SElemType *top;//棧頂指針
int stacksize;//棧的最大容量 }Stack;//棧的類型
第2頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
Status InitStack(Stack &S)//初始化棧 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)
exit(OVERFLOW);//存儲(chǔ)分配失敗;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頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
return OK;}//Pop
Status DestroyStack(Stack &S)//銷毀棧 { free(S.base);S.top=S.base;return OK;}//DestroyStack
//maze.cpp #define MAXLEN 20//迷宮包括外墻最大行列數(shù)目 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(“輸入迷口的行數(shù)和列數(shù): ”);
scanf(“%d%d”,&maze.r,&maze.c);//迷宮行和列數(shù)
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的坐標(biāo)(以坐標(biāo)(0,0)結(jié)束輸入): ”,k);
scanf(“%d%d”,&m,&n);
k++;
while(m!=0)
{
if(m>maze.r || n>maze.c)//越界
第4頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
exit(ERROR);
maze.adr[m][n]='#';//迷宮障礙用'#'標(biāo)記
printf(“輸入障礙物%d的坐標(biāo)(以坐標(biāo)(0,0)結(jié)束輸入): ”,k);
scanf(“%d%d”,&m,&n);
k++;
}
return OK;}//InitMaze
Status Pass(MazeType maze,PostType curpos){ //當(dāng)前位置可通則返回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){ //指示并返回下一位置的坐標(biāo)
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){ //曾走過但不是通路標(biāo)記并返回OK
第5頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
maze.adr[curpos.r][curpos.c]='@';//“@”表示曾走過但不通
return OK;}//MarkPrint
void PrintMaze(MazeType &maze)//將最后標(biāo)記好的迷宮輸出 { int i,j;printf(“n輸出迷宮的路徑:n”);for(i=0;i<=maze.c+1;i++)
printf(“%4d”,i);//輸出列數(shù)
printf(“n”);for(i=0;i<=maze.r+1;i++){
printf(“%d”,i);//輸出行數(shù)
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))//當(dāng)前位置可通過而未曾走過留下足跡
{
FootPrint(maze,curpos);
e.ord=curstep;e.seat=curpos;e.di=1;
Push(S,e);//加入棧路徑中
if(curpos.r==end.r && curpos.c==end.c)//到達(dá)出口返回TRUE
{
第6頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
if(!DestroyStack(S))
exit(OVERFLOW);
else return TRUE;
}
else
{
curpos=NextPos(curpos,1);//下一位置是當(dāng)前位置
curstep++;//探索下一步
}
}//if
else//當(dāng)前位置不能通過
{
if(!StackEmpty(S))
{
Pop(S,e);//提取前一位置
while(e.di==4 &&!StackEmpty(S))//4個(gè)方向都不能通過則留下記號(hào)@ 提取前一個(gè)位置進(jìn)行判斷是否是能通過
{
MarkPrint(maze,e.seat);
Pop(S,e);
}
if(e.di<4)//換下一個(gè)方向探索
設(shè)定當(dāng)前位置為該新方向上的鄰位
{
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頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
do {
printf(“**********迷宮求解**********n”);
if(!InitMaze(maze))
{
printf(“n 初始化迷宮失??！!”);
exit(ERROR);
}
do
{
printf(“n請(qǐng)輸入入口的坐標(biāo):”);
scanf(“%d%d”,&start.r,&start.c);//輸入入口坐標(biāo)
if(start.r>maze.r || start.c>maze.c)
printf(“n輸入錯(cuò)誤,請(qǐng)重新輸入入口的坐標(biāo)！n”);
continue;
}
while(start.r>maze.r || start.c>maze.c);
do
{
printf(“n請(qǐng)輸入出口的坐標(biāo):”);//輸入出口的坐標(biāo)
scanf(“%d%d”,&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c)
printf(“n輸入錯(cuò)誤,請(qǐng)重新輸入出口坐標(biāo)！n”);
continue;
}
while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
printf(“n不能找到一條路徑！!n”);
else PrintMaze(maze);//輸出迷宮
printf(“是否要繼續(xù)?(y/n):”);
scanf(“%s”,&c);} while(c=='y' || c=='Y');}。測(cè)試結(jié)果：
第8頁
四、山東科技大學(xué)學(xué)生課程設(shè)計(jì)
課程設(shè)計(jì)2 一元多項(xiàng)式
一、需求分析：
第9頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
1.2.3.首先定義一個(gè)結(jié)構(gòu)體，其中定義一元多項(xiàng)式中的兩個(gè)參數(shù):系數(shù)和指數(shù)和鏈表中結(jié)點(diǎn)的指針域；
然后一一羅列每個(gè)在主程序中用到的函數(shù)，并一一實(shí)現(xiàn)； 最后在主程序中主要完成用戶的輸入和相關(guān)函數(shù)的調(diào)用。
二、概要設(shè)計(jì)：
void insert(PLOYList *head,PLOYList *input)
//查找位置插入新鏈節(jié)的函數(shù)，且讓輸入的多項(xiàng)式呈降序排列 PLOYList *creat(char ch)//輸入多項(xiàng)式
PLOYList *add(PLOYList *head,PLOYList *pre)//多項(xiàng)式相加，head為第一個(gè)多項(xiàng)式建立的鏈表表頭，pre為第二個(gè)多項(xiàng)式建立的鏈表表頭
PLOYList *sub(PLOYList *head,PLOYList *pre)//多項(xiàng)式相減
PLOYList *mul(PLOYList *head,PLOYList *pre)//多項(xiàng)式相乘
PLOYList *der(PLOYList *head)//多項(xiàng)式求導(dǎo)
void print(PLOYList *fun)//輸出多項(xiàng)式，fun指要輸出的多項(xiàng)式鏈表的表頭 void start()//用戶選擇界面
三、詳細(xì)設(shè)計(jì)：
#include
//定義節(jié)點(diǎn)類型 { float coef;
//多項(xiàng)式的系數(shù)
int expn;
//多項(xiàng)式的指數(shù)
struct node * next;//結(jié)點(diǎn)指針域 }PLOYList;void insert(PLOYList *head,PLOYList *input)
//查找位置插入新鏈節(jié)的函數(shù)，且讓輸入的多項(xiàng)式呈降序排列 {
PLOYList *pre,*now;
int signal=0;
pre=head;
第10頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
if(pre->next==NULL){pre->next=input;} //如果只有一個(gè)頭結(jié)點(diǎn)，則把新結(jié)點(diǎn)直接連在后面
else {
now=pre->next;//如果不是只有一個(gè)頭結(jié)點(diǎn)，則設(shè)置now指針
while(signal==0)
{
if(input->expn < now->expn)
{
if(now->next==NULL)
{
now->next=input;
signal=1;
}
else
{
pre=now;
now=pre->next;//始終讓新輸入的數(shù)的指數(shù)與最后一個(gè)結(jié)點(diǎn)中的數(shù)的指數(shù)比較，小于則插在其后面
}
}
else if(input->expn > now->expn)
{
input->next=now;
pre->next=input;
signal=1;
}//若新結(jié)點(diǎn)中指數(shù)比最后一個(gè)結(jié)點(diǎn)即now中的指數(shù)大，則插入now之前
else//若指數(shù)相等則需合并為一個(gè)結(jié)點(diǎn)，若相加后指數(shù)為0則釋放該結(jié)點(diǎn)
{
now->coef=now->coef+input->coef;
signal=1;
free(input);
if(now->coef==0)
{
pre->next=now->next;
free(now);
}
}//else } //while
第11頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
}//else }//void
PLOYList *creat(char ch)
//輸入多項(xiàng)式 {
PLOYList *head,*input;
float x;
int y;
head=(PLOYList *)malloc(sizeof(PLOYList));
//創(chuàng)建鏈表頭
head->next=NULL;
scanf(“%f %d”,&x,&y);//實(shí)現(xiàn)用戶輸入的第一個(gè)項(xiàng)，包括其指數(shù)和系數(shù)
while(x!=0)
{
input=(PLOYList *)malloc(sizeof(PLOYList));//創(chuàng)建新鏈節(jié)
input->coef=x;
input->expn=y;
input->next=NULL;
insert(head,input);//每輸入一項(xiàng)就將其排序，是的鏈表中多項(xiàng)式呈降序排列
scanf(“%f %d”,&x,&y);
} return head;}
PLOYList *add(PLOYList *head,PLOYList *pre)
//多項(xiàng)式相加，head為第一個(gè)多項(xiàng)式建立的鏈表表頭，pre為第二個(gè)多項(xiàng)式建立的鏈表表頭 {
PLOYList *input;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//若該鏈表為空，則無需進(jìn)行加法運(yùn)算，跳出循環(huán)
else
{
pre=pre->next;
input=(PLOYList *)malloc(sizeof(PLOYList));
第12頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
input->coef=pre->coef;
input->expn=pre->expn;
input->next=NULL;
insert(head,input);// 把g(x)插入到f(x）中，相當(dāng)于兩者相加，結(jié)果保存于f(x)
}
} return head;}
PLOYList *sub(PLOYList *head,PLOYList *pre)//多項(xiàng)式相減 {
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;//將第二個(gè)多項(xiàng)式里的數(shù)變?yōu)槠湎喾磾?shù)，再用和加法一樣的方法實(shí)現(xiàn)減法
input->expn=pre->expn;
input->next=NULL;
insert(head,input);
}
} return head;}
PLOYList *mul(PLOYList *head,PLOYList *pre)//多項(xiàng)式項(xiàng)乘 { PLOYList *hf,*pf,*qa,*qb;
qa = head-> next;
qb = pre-> next;//定義指針指向表頭后一個(gè)元素，即鏈表中第一個(gè)元素
hf =(PLOYList *)malloc(sizeof(PLOYList));//新創(chuàng)建一個(gè)結(jié)點(diǎn)，當(dāng)做表頭
hf-> next = NULL;for(;qa;qa = qa-> next)
第13頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
{
for(qb = pre-> next;qb;qb= qb-> next)//用兩個(gè)循環(huán)，實(shí)現(xiàn)兩個(gè)多項(xiàng)式之間每個(gè)項(xiàng)相乘，結(jié)果用insert函數(shù)進(jìn)行排序與合并
{
pf =(PLOYList *)malloc(sizeof(PLOYList));
pf-> coef = qa-> coef * qb-> coef;//系數(shù)相乘
pf-> expn = qa-> expn + qb-> expn;//指數(shù)相加
pf-> next = NULL;
insert(hf,pf);
} } return hf;}
PLOYList *der(PLOYList *head)//多項(xiàng)式求導(dǎo) { PLOYList *p;p = head-> next;while(p){
p-> coef = p-> coef * p-> expn;
p-> expn = p-> expn--;
p = p-> next;} return head;}//將多項(xiàng)式的每項(xiàng)系數(shù)和指數(shù)相乘得到新的系數(shù)，指數(shù)減一得到新的指數(shù)即完成求導(dǎo)
void print(PLOYList *fun)//輸出多項(xiàng)式，fun指要輸出的多項(xiàng)式鏈表的表頭 {
PLOYList *printing;
int flag=0;
printing=fun->next;
if(fun->next==NULL)//若為空表，則無需輸出
{
printf(“0n”);
return;
}
while(flag==0)
{
第14頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
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.兩個(gè)一元多項(xiàng)式相加
*n”);
printf(“ *
2.兩個(gè)一元多項(xiàng)式相減
*n”);
printf(“ *
3.兩個(gè)一元多項(xiàng)式相乘
*n”);
printf(“ *
4.對(duì)一個(gè)一個(gè)一元多項(xiàng)式求導(dǎo) *n”);
printf(“ *
0.退出系統(tǒng)
*n”);
printf(“ *
*n”);
printf(“ ************************************n”);
printf(“
n”);
printf(“ 注釋：輸入多項(xiàng)式格式（可無序）：系數(shù)1 指數(shù)1 系數(shù)2 指數(shù)2 ??，并以0 0 結(jié)束：n”);
printf(“
n”);
printf(“ 請(qǐng)選擇操作: ”);}
int main(){ PLOYList *f,*g,*pf,*hf,*p;
第15頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
int sign=-1;
start();
while(sign!=0)
{
scanf(“%d”,&sign);
switch(sign)
{
case 0:
break;
case 1://多項(xiàng)式相加
{
printf(“ 你選擇的操作是多項(xiàng)式相加:n”);
printf(“ 請(qǐng)輸入第一個(gè)多項(xiàng)式f(x)：”);
f=creat('f');
printf(“ 第一個(gè)多項(xiàng)式為：f(x)=”);
print(f);
printf(“ 請(qǐng)輸入第二個(gè)多項(xiàng)式g(x)：”);
g=creat('g');
printf(“ 第二個(gè)多項(xiàng)式為：g(x)=”);
print(g);
printf(“ 結(jié)果為：F(x)=f(x)+g(x)=”);
f=add(f,g);
print(f);
printf(“nn”);
printf(“ 繼續(xù)請(qǐng)選擇相應(yīng)操作，退出請(qǐng)按0.break;
}
case 2://多項(xiàng)式相減
{
printf(” 你選擇的操作是多項(xiàng)式相減:n“);
printf(” 請(qǐng)輸入第一個(gè)多項(xiàng)式f(x)：“);
f=creat('f');
printf(” 第一個(gè)多項(xiàng)式為：f(x)=“);
print(f);
printf(” 請(qǐng)輸入第二個(gè)多項(xiàng)式g(x)：“);
g=creat('g');
printf(” 第二個(gè)多項(xiàng)式為：g(x)=“);
print(g);
printf(” 結(jié)果為：F(x)=f(x)-g(x)=“);
f=sub(f,g);
print(f);
”);第16頁
山東科技大學(xué)學(xué)生課程設(shè)計(jì)
printf(“nn”);
printf(“ 繼續(xù)請(qǐng)選擇相應(yīng)操作，退出請(qǐng)按0.”);
break;
}
case 3://多項(xiàng)式相乘
{
printf(“ 你選擇的操作是多項(xiàng)式相乘:n”);
printf(“ 請(qǐng)輸入第一個(gè)多項(xiàng)式f(x)：”);
f=creat('f');
printf(“ 第一個(gè)多項(xiàng)式為：f(x)=”);
print(f);
printf(“ 請(qǐng)輸入第二個(gè)多項(xiàng)式g(x)：”);
g=creat('g');
printf(“ 第二個(gè)多項(xiàng)式為：g(x)=”);
print(g);
printf(“ 結(jié)果為：F(x)=f(x)* g(x)=”);
pf=mul(f,g);
print(pf);
printf(“nn”);
printf(“ 繼續(xù)請(qǐng)選擇相應(yīng)操作，退出請(qǐng)按0.”);
break;
}
case 4://多項(xiàng)式求導(dǎo)
{
printf(“您選擇的是對(duì)一個(gè)一元多項(xiàng)式求導(dǎo)：n”);
printf(“請(qǐng)輸入一個(gè)一元多項(xiàng)式：”);
f = creat('f');
printf(“這個(gè)多項(xiàng)式為：f(x)= ”);
print(f);
printf(“求導(dǎo)結(jié)果為：F(x)=f'(x)= ”);
f=der(f);
print(f);
printf(“nn”);
printf(“ 繼續(xù)請(qǐng)選擇相應(yīng)操作，退出請(qǐng)按0.”);
break;
}
}//swith
}//while }//void
四、測(cè)試結(jié)果：
第17頁 山東科技大學(xué)學(xué)生課程設(shè)計(jì)
第18頁
第二篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
數(shù) 據(jù) 結(jié) 構(gòu)
課程設(shè)計(jì)報(bào)告
題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級(jí)： 2012級(jí)普本班 學(xué) 號(hào)： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時(shí) 間：
一、課程設(shè)計(jì)題目分析
本課程設(shè)計(jì)要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。
二、設(shè)計(jì)思路
本程序采用C語言來完成課程設(shè)計(jì)。
1、首先，利用順序存儲(chǔ)結(jié)構(gòu)來構(gòu)造兩個(gè)存儲(chǔ)多項(xiàng)式A(x)和 B(x)的結(jié)構(gòu)。
2、然后把輸入，加，減，乘，除運(yùn)算分成五個(gè)主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。
3、然后各個(gè)模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時(shí)錯(cuò)誤的出現(xiàn)。
4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對(duì)多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。
三、設(shè)計(jì)算法分析
1、相關(guān)函數(shù)說明：
(1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型變量
typedef struct Polynomial{}
(2)其他功能函數(shù)
插入函數(shù)void Insert(Polyn p,Polyn h)
比較函數(shù)int compare(Polyn a,Polyn b)
建立一元多項(xiàng)式函數(shù)Polyn Create(Polyn head,int m)
求解并建立多項(xiàng)式a+b，Polyn Add(Polyn pa,Polyn pb)
求解并建立多項(xiàng)式a-b，Polyn Subtract(Polyn pa,Polyn pb)2
求解并建立多項(xiàng)式a*b，Polyn Multiply(Polyn pa,Polyn pb)
求解并建立多項(xiàng)式a/b，void Device(Polyn pa,Polyn pb)
輸出函數(shù)輸出多項(xiàng)式，void Print(Polyn P)
銷毀多項(xiàng)式函數(shù)釋放內(nèi)存，void Destroy(Polyn p)
主函數(shù)，void main（）
2、主程序的流程基函數(shù)調(diào)用說明(1)typedef struct Polynomial {
float coef;
int expn;
struct Polynomial *next;} *Polyn,Polynomial;
在這個(gè)結(jié)構(gòu)體變量中coef表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對(duì)象名。
(2)當(dāng)用戶輸入兩個(gè)一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲(chǔ)這兩個(gè)多項(xiàng)式，主要說明如下：
Polyn CreatePolyn(Polyn head,int m)建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式
p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xiàng)式申請(qǐng)足夠的存儲(chǔ)空間
p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù)
Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn)
這就建立一元多項(xiàng)式的關(guān)鍵步驟
(3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對(duì)多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對(duì)指數(shù)大小的比較，對(duì)各種情況進(jìn)行處理，此處由于反復(fù)使用指針對(duì)各個(gè)結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)：
在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實(shí)現(xiàn)；對(duì)于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲(chǔ)所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計(jì)算模塊的主要功能。
(5)另一個(gè)子函數(shù)是輸出函數(shù) PrintPolyn（）；
輸出最終的結(jié)果，算法是將最后計(jì)算合并的鏈表逐個(gè)結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計(jì)算式計(jì)算結(jié)果。由于考慮各個(gè)結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。
四、程序新點(diǎn)
通過多次寫程序，發(fā)現(xiàn)在程序在控制臺(tái)運(yùn)行時(shí)總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺(tái)背景顏色，0是控制臺(tái)輸出字體顏色。
五、設(shè)計(jì)中遇到的問題及解決辦法
首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時(shí)候易腦子混亂出錯(cuò)，對(duì)于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4
代碼編寫。
其次是，在寫除法模塊時(shí)比較復(fù)雜，自己通過查資料最后成功寫出除法模塊功能。
最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。
六、測(cè)試（程序截圖）
1.數(shù)據(jù)輸入及主菜單
2.加法和減法模塊
3.乘法和除法模塊
七、總結(jié)
通過本次應(yīng)用C語言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語言程序設(shè)計(jì)的知識(shí)，以前對(duì)指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計(jì)對(duì)指針理解的比較深刻了。而且對(duì)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對(duì)自己以后學(xué)習(xí)其他語言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。
八、指導(dǎo)老師評(píng)語及成績(jī)
附錄：（課程設(shè)計(jì)代碼）
#include
float coef;6
int expn;
struct Polynomial *next;} *Polyn,Polynomial;
//Polyn為結(jié)點(diǎn)指針類型 void Insert(Polyn p,Polyn h){
if(p->coef==0)free(p);
//系數(shù)為0的話釋放結(jié)點(diǎn)
else
{
Polyn q1,q2;
q1=h;q2=h->next;
while(q2&&p->expn
{
q1=q2;q2=q2->next;}
if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 {
q2->coef+=p->coef;
free(p);
if(!q2->coef)//系數(shù)為0的話釋放結(jié)點(diǎn)
{ q1->next=q2->next;free(q2);}
}
else { p->next=q2;q1->next=p;
}//指數(shù)為新時(shí)將結(jié)點(diǎn)插入
} 7
} //建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 Polyn Create(Polyn head,int m){
int i;
Polyn p;
p=head=(Polyn)malloc(sizeof(struct Polynomial));
head->next=NULL;
for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf(“請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn) } return head;} //銷毀多項(xiàng)式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項(xiàng)式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器 if(!q)//若多項(xiàng)式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng) 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空 } //求解并建立多項(xiàng)式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) } return headc;} //求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng) } } return hf;} //求解并建立多項(xiàng)式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn),存儲(chǔ)商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)，存儲(chǔ)余數(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(“請(qǐng)輸入A(x)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請(qǐng)輸入B(x)的項(xiàng)數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項(xiàng)式B printf(“n”);printf(“**********************************************n”);printf(“* 多項(xiàng)式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項(xiàng)式A(x):“);Print(pa);*n”); printf(“多項(xiàng)式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項(xiàng)式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項(xiàng)式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項(xiàng)式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 1.赫夫曼編碼器 設(shè)計(jì)一個(gè)利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。要求： 1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個(gè)字符和26個(gè)權(quán)值（統(tǒng)計(jì)一篇英文文章中26個(gè)字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實(shí)現(xiàn)屏幕輸出，然后實(shí)現(xiàn)文件輸出）； 5)界面優(yōu)化設(shè)計(jì)。 代碼如下： #include typedef struct HTNode //結(jié)構(gòu)體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權(quán)值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進(jìn)行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請(qǐng)輸入權(quán)值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對(duì)結(jié)點(diǎn)進(jìn)行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)