第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮求解范文

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

迷宮求解

學(xué)院：湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院

教師：沈華老師

班級：12網(wǎng)絡(luò)工程1班

學(xué)號：1210322118

姓名：饒進(jìn)陽

時(shí)間：2013年12月22日

目

錄

問題描述

.........................................................思路解析

.........................................................程序流程

.........................................................核心代碼

.........................................................源程序代碼........................................................程序運(yùn)行實(shí)例.....................................................課設(shè)總結(jié)

.........................................................3 4 5 6 12 14 迷宮求解

問題描述：

可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；

要求：

在上交資料中請寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

比如這是一個(gè)迷宮

電腦找出的出路

思

路

設(shè)定當(dāng)前位置的初值為入口位置： do｛

若當(dāng)前位置可通，則｛

將當(dāng)前位置插入棧頂；} 若該位置是出口位置，則結(jié)束；

否則切換當(dāng)前位置的東鄰塊為新的當(dāng)前位置； 否則｛

若棧不空且棧頂位置還有其他方向未被探索，則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；} 若{ 棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；} 若{ 棧不空，則重新測試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至?？?；｝ ｝while(棧不空)｛?？照f明沒有路徑存在｝

PS：類似動(dòng)態(tài)求解方法

程序流程

第一次用visio做程序框圖，所以只把程序的大概流程畫出來了。

核心代碼

//棧相關(guān)操作 int initlStack(Stack *S)int pushStack(Stack S, coordinate e)int popStack(Stack S, coordinate *e)int getTop(Stack S, coordinate *e)void show(Stack S)

//創(chuàng)建一個(gè)迷宮 int creatMaze(Maze *m)

//打印出一個(gè)迷宮 void showMaze(Maze *m)

//求當(dāng)前結(jié)點(diǎn)的下一個(gè)通路

coordinate passNext(Maze *m, int i, int j)//求迷宮路徑

int solveMaze(Maze *m, Stack S)//模擬出路徑

void showRoad(Maze m, Stack S)

程序源碼：

#include #include

#define MAX 100

#define SIZE sizeof(Node)//**************************** //棧

typedef struct { int x;//行

int y;//列 }coordinate;//坐標(biāo)

typedef struct node{ coordinate data;struct node *next;}Node, *Stack;

//棧的相關(guān)操作

//棧初始化

//帶頭結(jié)點(diǎn)的鏈棧

int initlStack(Stack *S){(*S)=(Node *)malloc(SIZE);if((*S)== NULL){

return 1;}(*S)->next = NULL;return 0;}

//入棧

int pushStack(Stack S, coordinate e){ Node *p;

p =(Node *)malloc(SIZE);p->data.x = e.x;p->data.y = e.y;p->next = S->next;S->next = p;return 0;}

//出棧

int popStack(Stack S, coordinate *e){ Node *p;if(S->next == NULL){

printf(“nStack is empty!n”);

return 2;} e->x = S->next->data.x;e->y = S->next->data.y;p = S->next;S->next = p->next;free(p);return 0;}

//讀取棧頂

int getTop(Stack S, coordinate *e){ e->x = S->next->data.x;e->y = S->next->data.y;return 0;}

//顯示

void show(Stack S){ Node *p;p = S->next;while(p!= NULL){

printf(“%d %d <-”, p->data.x, p->data.y);

p = p->next;} printf(“startn”);} //***************************

//*************************** //迷宮

typedef struct { int row;int col;int arr[MAX][MAX];}Maze;

//創(chuàng)建一個(gè)迷宮

int creatMaze(Maze *m){ int i, j;printf(“nplease input Maze's row and col:n”);scanf(“%d%d”, &(m->row), &(m->col));printf(“nplease input the Maze's message:(0 is ok),(1 is no)n”);for(i = 0;i <= MAX1;j++){

m->arr[i][j] = 1;

} } for(i = 1;i <= m->row;i++){

for(j = 1;j <= m->col;j++){

scanf(“%d”, &(m->arr[i][j]));

} } return 0;}

//顯示迷宮信息

void showMaze(Maze *m){ int i, j;printf(“nthe Maze you hava input:n”);for(i = 1;i <= m->row;i++){

for(j = 1;j <= m->col;j++){

printf(“%d ”, m->arr[i][j]);

}

printf(“n”);}

printf(“nlike this:n”);for(i = 1;i <= m->row;i++){

for(j = 1;j <= m->col;j++){

if(m->arr[i][j]!= 0){

printf(“■ ”);

}

else {

printf(“□ ”);

}

}

printf(“n”);} } //求當(dāng)前結(jié)點(diǎn)的下個(gè)通路 //順時(shí)針找

coordinate passNext(Maze *m, int i, int j){ coordinate k;if(m->arr[i][j+1] == 0){//東

k.x = i;

k.y = j+1;

return k;}

if(m->arr[i+1][j] == 0){//南

k.x = i+1;

k.y = j;

return k;} if(m->arr[i][j-1] == 0){//西

k.x = i;

k.y = j-1;

return k;} if(m->arr[i-1][j] == 0){//北

k.x = i-1;

k.y = j;

return k;} else {//不存在 k.x =-1;

k.y =-1;

return k;} }

//求解迷宮

int solveMaze(Maze *m, Stack S){ int i, j;int boolean;coordinate a;i = 1;j = 1;do {

if(m->arr[i][j] == 0){

a.x = i;

a.y = j;

m->arr[i][j] = 2;

pushStack(S, a);

if(i == m->row && j == m->col){

return 0;

}

}

a = passNext(m, i, j);

if(a.x!=-1){

i = a.x;

j = a.y;

continue;

}

else if(a.x ==-1){

boolean = popStack(S, &a);

if(2 == boolean){

return 0;

}

getTop(S, &a);

i = a.x;

j = a.y;

} }while(S->next!= NULL);return 0;}

//模擬出路徑

void showRoad(Maze m, Stack S){ coordinate e;int i, j;if(S->next == NULL){

printf(“nSorry!you can't go out the Maze!n”);} while(S->next!= NULL){

popStack(S, &e);

m.arr[e.x][e.y] =-1;} for(i = 1;i <= m.row;i++){

for(j = 1;j <= m.col;j++){

if(m.arr[i][j] >= 0){

printf(“■ ”);

}

else {

printf(“□ ”);

}

}

printf(“n”);} } //*************************** //主函數(shù) int main(){ Maze m;Stack S;printf(“※ 歡迎玩耍迷宮求解游戲 ※n”);initlStack(&S);creatMaze(&m);showMaze(&m);solveMaze(&m, S);printf(“nthe root is here:n”);show(S);showRoad(m, S);return 0;}

程序運(yùn)行結(jié)果：

第一步：輸入迷宮行列大小

第二步：輸入迷宮信息

第四步：程序會(huì)自動(dòng)求出路徑

課 設(shè) 總 結(jié)

敬愛的沈華老師您好，感謝您這半年對我們的教誨，說實(shí)話，很喜歡上您的課，您上課的風(fēng)采深深的吸引了我，每次上您的課，我都聽得特別認(rèn)真。好吧，言歸正傳，談?wù)勥@次課程設(shè)計(jì)的感想。

首先看到這道題的時(shí)候，真心沒多少思路，我抱著試一試的態(tài)度，去網(wǎng)上搜索相關(guān)的算法。網(wǎng)上資源蠻多的，剛開始就搜索到了，嚴(yán)蔚敏老師的相關(guān)算法講解視頻，雖然她講的是思想（就是他并沒有源程序的實(shí)現(xiàn)），但是足夠讓我理解了基本算法流程。

其實(shí)先開始都不知道怎么下筆，但是我還是想著從基本棧開始寫吧，慢慢寫著，程序大概思想框架就成型了，最后在實(shí)現(xiàn)求解迷宮路徑的時(shí)候，著手用筆在草稿紙上面模擬，然后才敲到編譯器中，最好幾經(jīng)調(diào)試，終于得到了想要的結(jié)果。

做完這次課設(shè)后，深刻的體會(huì)到一些道理，在信息時(shí)代，解決問題的最好方法是運(yùn)用現(xiàn)代的信息資源。并且在實(shí)際中，開始沒思路的事，慢慢完成小部分，那么你的總體思維會(huì)漸漸地成型。

做事做人，平心氣和的干，總會(huì)得到成功！

第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 背包問題的求解

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

背包問題的求解

摘要 組合優(yōu)化問題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點(diǎn)，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價(jià)值，同時(shí)也在于它們能在現(xiàn)實(shí)生活中廣泛的應(yīng)用。背包問題是一個(gè)典型的組合優(yōu)化問題，本課程設(shè)計(jì)用遞歸算法求解背包問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。關(guān)鍵詞 背包問題；

遞歸算法；

1問題描述

1.1問題描述

背包問題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值之和最大。

1.2基本思想

（1）分別輸入n件物品的重量和價(jià)值。（2）采用遞歸尋找物品的方案。

（3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價(jià)值為多少。

2問題分析

背包問題的求解是一個(gè)很經(jīng)典的案例。對于它的分析與研究已經(jīng)到達(dá)了一定的深度，解決這個(gè)問題有很多很多的辦法。其中遞歸方法是比較簡化程序，也比較難理解的一個(gè)。

設(shè)n件物品的重量分別為w0,w1,?,wn-1,物品的價(jià)值分別為v0,v1,?,vn-1。采用遞歸尋找物品的選擇方案。設(shè)前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[],設(shè)方案的的總價(jià)值存于變量maxv,當(dāng)前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當(dāng)前方案已經(jīng)考慮了前i-1件物品，現(xiàn)在正在考慮第i件物品；當(dāng)前方案已經(jīng)包含的物品的質(zhì)量之和為tw;至此，若其余物品都選擇可能的話，本方案能達(dá)到的總價(jià)值的期望值設(shè)為tv，算法引入tv是當(dāng)一旦當(dāng)前方案的總價(jià)值的期望值也小于前面方案的總價(jià)值maxv時(shí)，急需考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會(huì)不會(huì)再被考察。這同時(shí)保證函數(shù)后找到的方案一定會(huì)比前面的方案更好。2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 對于第i件物品的選擇有兩種可能：

（1）物品i被選擇，這種可能性僅當(dāng)包含它不會(huì)超過方案總重量的限制時(shí)才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇；

（2）物品i不被選擇，這種可能性僅當(dāng)不包物品i也有可能會(huì)找大價(jià)值更大的方案的情況。

就此，通過不斷地對從第一件開始的物品到第n件物品進(jìn)行選擇或是不選擇，從而從各個(gè)方案的比較中選擇出最優(yōu)方案。

采用option[]和cop[]兩個(gè)數(shù)組，來輔助完成遞歸尋找物品的選擇方案。數(shù)組option[]起到一個(gè)“旗幟”作用，用來區(qū)別于未被選擇的物品，從而達(dá)到輸出被選擇的函數(shù)。而cop[]則像是一個(gè)中間變量，它在遞歸過程中不斷地發(fā)生變化，將有效的最終數(shù)據(jù)傳輸給數(shù)組option[]，起到一個(gè)橋梁作用。

3數(shù)據(jù)結(jié)構(gòu)描述

背包問題結(jié)構(gòu)體：

struct{

int weight;

int value;

}a[N];4算法設(shè)計(jì)

4.1程序流程圖

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

圖4-1 程序流程圖

4.2算法設(shè)計(jì)

根據(jù)問題分析中的思想寫出遞歸算法如下：

find（物品當(dāng)前選擇已達(dá)到的重量和tw,本方案可能達(dá)到的總價(jià)值為tv）｛

/*考慮物品i包含在當(dāng)前方案中的可能性*/ if（包含物品i是可接受的）｛

將物品i包含在當(dāng)前方案中；

if(i

以當(dāng)前方案作為臨時(shí)最佳方案保存；

恢復(fù)物品i不包含狀態(tài)；

｝ 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

/*考慮物品i不包含在當(dāng)前方案中的可能性*/ if（不包含物品i僅是可考慮的）

if(i

以當(dāng)前方案作為臨時(shí)最佳方案保存；

｝

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

/*物品i包含在當(dāng)前方案的可能性*/ { cop[i]=1;if(imaxv)

/*物品i不包含在當(dāng)前方案的可能性*/ if(i

opion[k]=cop[k];maxv=tv-a[i].value;} } 5詳細(xì)程序清單

詳細(xì)程序清單見附錄。

6程序運(yùn)行結(jié)果

背包問題求解界面如圖6-1所示。

圖6-1 背包問題求解界面

程序調(diào)試成功。

在課程設(shè)計(jì)代碼調(diào)試過程中也出了不少差錯(cuò)，比如頭文件很容易忽略，同學(xué)指出才發(fā)現(xiàn)；一些符號像“；”也很容易丟掉或是中英文格式不正確；甚至像0和 O這種小錯(cuò)誤有時(shí)也會(huì)發(fā)生，在經(jīng)過調(diào)試和完善程序的過程中，這些錯(cuò)誤已經(jīng)全部改正。在此過程中我們學(xué)到了不少調(diào)試的技巧，極大得豐富了編程的知識(shí)，這些在程序的優(yōu)化方面幫助很大。

7心得體會(huì)

通過此次課程設(shè)計(jì)的實(shí)踐，感觸較深。不僅使我們加深了對書本知識(shí)的理解，而且鍛煉了我們編寫程序、調(diào)試程序的能力。同時(shí)，此次課程設(shè)計(jì)也充分彌補(bǔ)了課堂教學(xué)中知識(shí)的缺陷。這次課程設(shè)計(jì)由于時(shí)間有限，對有些地方考慮的還不夠周到。

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

在本課題中，我們研究了如何用遞歸算法求解組合優(yōu)化問題中的背包問題，背包問題是一個(gè)典型的組合優(yōu)化問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。所以我們試著用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)以及遞歸法來解決普通的背包問題。背包問題的遞歸思想確實(shí)有點(diǎn)難以理解，為了理解這個(gè)思想，我們確實(shí)花了很長時(shí)間，不過很高興最后經(jīng)過我們的討論掌握了這個(gè)思想。

參考文獻(xiàn)

[1] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn).北京：清華大學(xué)出版社，2002:100-132 [2] 張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.北京：電子工業(yè)出版，2000:3-5 [3] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京： 清華大學(xué)出版社，2002:100-132 [4] 李春葆.數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析（修訂版）.北京：清華大學(xué)出版，2000:45-66

Knapsack problem solving

Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

附錄：詳細(xì)程序清單

#include #define N 100 int limitw，/*限制的總重量*/ totv，/*全部物品的總價(jià)*/ maxv;

/*可實(shí)現(xiàn)最大總價(jià)值*/ int opion[N]，cop[N];

struct{

int weight;

int value;

}a[N];int n;

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

{ cop[i]=1;if(i

/*方案的選擇*/ /*當(dāng)前方案的選擇*/ /*背包問題結(jié)構(gòu)體*/

/*物品種數(shù)*/ /*物品i包含在當(dāng)前方案的可能性*/ 7

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

if(tv-a[i].value>maxv)

/*物品i不包含在當(dāng)前方案的可能性*/ if(i

第%d種物品（重量，價(jià)值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的總重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k

printf(“最佳裝填方案是：n”);for(k=0;k

第三篇：數(shù)據(jù)結(jié)構(gòu)迷宮問題實(shí)驗(yàn)報(bào)告

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》

迷宮問題實(shí)驗(yàn)報(bào)告

——實(shí)驗(yàn)二

專業(yè)：物聯(lián)網(wǎng)工程 班級：物聯(lián)網(wǎng)1班 學(xué)號：15180118 姓名：劉沛航

一、實(shí)驗(yàn)?zāi)康?/p>

本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認(rèn)后程序自動(dòng)運(yùn)行，當(dāng)迷宮有完整路徑可以通過時(shí)，以0和1所組成的迷宮形式輸出，標(biāo)記所走過的路徑結(jié)束程序；當(dāng)迷宮無路徑時(shí)，提示輸入錯(cuò)誤結(jié)束程序。

二、實(shí)驗(yàn)內(nèi)容

用一個(gè)m*m長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序?qū)τ谌我庠O(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。

三、程序設(shè)計(jì)

1、概要設(shè)計(jì)

（1）設(shè)定棧的抽象數(shù)據(jù)類型定義

ADT Stack{

數(shù)據(jù)對象：D={ai|ai屬于CharSet，i=1、2…n，n>=0} 數(shù)據(jù)關(guān)系：R={|ai-1,ai屬于D，i=2,3,…n} 基本操作： InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧 Push（&S，e）

初始條件：棧已經(jīng)存在

操作結(jié)果：將e所指向的數(shù)據(jù)加入到棧s中 Pop（&S,&e）

初始條件：棧已經(jīng)存在

操作結(jié)果：若棧不為空，用e返回棧頂元素，并刪除棧頂元素 Getpop（&S，&e）

初始條件：棧已經(jīng)存在

操作結(jié)果：若棧不為空，用e返回棧頂元 StackEmpty(&S)

初始條件：棧已經(jīng)存在

操作結(jié)果：判斷棧是否為空。若棧為空，返回1，否則返回0 Destroy(&S)

初始條件：棧已經(jīng)存在 操作結(jié)果：銷毀棧s }ADT Stack

（2）設(shè)定迷宮的抽象數(shù)據(jù)類型定義

ADT yanshu{

數(shù)據(jù)對象：D={ai,j|ai,j屬于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 數(shù)據(jù)關(guān)系：R={ROW,COL}

ROW={|ai-1,j,ai,j屬于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j屬于D,i=0,1,…M，j=1,2,…N} 基本操作：

InitMaze(MazeType &maze, int a[][COL], int row, int col){

初始條件：二維數(shù)組int a[][COL],已經(jīng)存在，其中第1至第m-1行，每行自第1到第n-1列的元素已經(jīng)值，并以值0表示障礙，值1表示通路。

操作結(jié)果：構(gòu)造迷宮的整形數(shù)組，以空白表示通路，字符‘0’表示障礙

在迷宮四周加上一圈障礙

MazePath（&maze）{

初始條件：迷宮maze已被賦值

操作結(jié)果：若迷宮maze中存在一條通路，則按如下規(guī)定改變maze的狀態(tài)；以字符‘*’表示路徑上的位置。字符‘@’表示‘死胡同’；否則迷宮的狀態(tài)不變 }

PrintMaze（M）{ 初始條件：迷宮M已存在 操作結(jié)果：以字符形式輸出迷宮 }

}ADTmaze

（3）本程序包括三個(gè)模塊

a、主程序模塊 void main(){ 初始化； 構(gòu)造迷宮； 迷宮求解； 迷宮輸出； }

b、棧模塊——實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型 c、迷宮模塊——實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型

2、詳細(xì)設(shè)計(jì)

（1）坐標(biāo)位置類型：

typedef struct{ int row;//迷宮中的行 int col;//......的列

}PosType;//坐標(biāo)

（2）迷宮類型：

typedef struct{ int m,n;int arr[RANGE][RANGE];}MazeType;//迷宮類型

void InitMaze(MazeType &maze, int a[][COL], int row, int col)//設(shè)置迷宮的初值，包括邊緣一圈的值

Bool MazePath(MazeType &maze,PosType start, PosType end)//求解迷宮maze中，從入口start到出口end的一條路徑 //若存在，則返回true，否則返回false Void PrintMaze（MazeType maze）//將迷宮打印出來

（3）棧類型：

typedef struct{ int step;//當(dāng)前位置在路徑上的“序號” PosType seat;//當(dāng)前的坐標(biāo)位置

DirectiveType di;//往下一個(gè)坐標(biāo)位置的方向 }SElemType;//棧的元素類型

typedef struct{ SElemType *base;SElemType *top;int stacksize;}SqStack;棧的基本操作設(shè)置如下： Void InitStack（SqStack & S）

//初始化，設(shè)S為空棧（S.top=NUL）Void DestroyStack(Stack &S)//銷毀棧S，并釋放空間

Void ClearStack（SqStack & S）//將棧S清空

Int StackLength（SqStack &S）//返回棧S的長度

Status StackEmpty（SqStack &S）？、若S為空棧（S.top==NULL），則返回TRUE，否則返回FALSE Statue GetTop（SqStack &S，SElemType e）

//r若棧S不空，則以e待會(huì)棧頂元素并返回TRUE，否則返回FALSE Statue Pop(SqStack&S，SElemType e)//若分配空間成功，則在S的棧頂插入新的棧頂元素s并返回TRUE //否則棧不變，并返回FALSE Statue Push(SqStack&S，SElemType &e)//若分配空間程控，則刪除棧頂并以e帶回其值，則返回TRUE //否則返回FALSE Void StackTraverse（SqStack &S，Status）（*Visit）（SElemType e））//從棧頂依次對S中的每個(gè)節(jié)點(diǎn)調(diào)用函數(shù)Visit 4求迷宮路徑的偽碼算法：

Status MazePath(MazeType &maze,PosType start, PosType end){ //求解迷宮maze中,從入口start到出口end的一條路徑 InitStack(s);PosType curpos = start;int curstep = 1;//探索第一部 do{ if(Pass(maze,curpos)){ //如果當(dāng)前位置可以通過,即是未曾走到的通道塊 FootPrint(maze,curpos);//留下足跡

e = CreateSElem(curstep,curpos,1);//創(chuàng)建元素 Push(s,e);if(PosEquare(curpos,end))return TRUE;curpos =NextPos(curpos,1);//獲得下一節(jié)點(diǎn):當(dāng)前位置的東鄰 curstep++;//探索下一步 }else{ //當(dāng)前位置不能通過 if(!StackEmpty(s)){ Pop(s,e);while(e.di==4 &&!StackEmpty(s)){ MarkPrint(maze,e.seat);Pop(s,e);//留下不能通過的標(biāo)記,并退回步 } if(e.di<4){ e.di++;Push(s,e);//換一個(gè)方向探索

curpos = NextPos(e.seat,e.di);//設(shè)定當(dāng)前位置是該方向上的相塊 }//if }//if }//else }while(!StackEmpty(s));return FALSE;} //MazePath

四、程序調(diào)試分析

1.首先呢，想自己讀入數(shù)據(jù)的，回來發(fā)現(xiàn)那樣，很麻煩，所以還是事先定義一個(gè)迷宮。

2.棧的元素類型 一開始有點(diǎn)迷惑，后來就解決了

3.本題中三個(gè)主要算法；InitMaze，MazePath和PrintMaze的時(shí)間復(fù)雜度均為O（m*n）本題的空間復(fù)雜度也是O（m*n）

五、用戶使用說明

1．本程序運(yùn)行在windows系列的操作系統(tǒng)下，執(zhí)行文件為：Maze_Test.exe。

六、程序運(yùn)行結(jié)果

1.建立迷宮： 2．通過1功能建立8*8的迷宮后，通過2功能繼續(xù)建立迷宮內(nèi)部：

通過建立自己設(shè)定單元數(shù)目建立迷宮內(nèi)墻。3．通過3功能觀察已建立的迷宮結(jié)構(gòu)：

4．通過4功能確立迷宮起點(diǎn)和終點(diǎn)：

（此處像我們隨機(jī)選擇4,4和2,7分別為起點(diǎn)終點(diǎn)）

5．執(zhí)行5功能，判斷是否有路徑走出迷宮：

這種情況無法走出迷宮。

我們再次觀察圖像設(shè)4,4和1,6分別為起點(diǎn)終點(diǎn)，再運(yùn)行5功能。

觀察到可以成功解開迷宮步數(shù)從1依次開始。

七、程序清單

#include #include #include #include // 迷宮坐標(biāo)位置類型 typedef struct { int x;int y;}PosType;// 行值

// 列值

#define MAXLENGTH 25 // 設(shè)迷宮的最大行列為25

typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宮數(shù)組[行][列]

typedef struct // 棧的元素類型

{ int ord;// 通道塊在路徑上的＂序號＂

PosType seat;// 通道塊在迷宮中的＂坐標(biāo)位置＂

int di;// 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北)}SElemType;

// 全局變量

MazeType m;// 迷宮數(shù)組

int curstep=1;// 當(dāng)前足跡,初值為1

#define STACK_INIT_SIZE 10 // 存儲(chǔ)空間初始分配量

#define STACKINCREMENT 2 // 存儲(chǔ)空間分配增量

// 棧的順序存儲(chǔ)表示

typedef struct SqStack { SElemType *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL

SElemType *top;

int stacksize;

// 構(gòu)造一個(gè)空棧S int InitStack(SqStack *S){ // 為棧底分配一個(gè)指定大小的存儲(chǔ)空間

(*S).base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)

(*S).top =(*S).base;

return 1;

// 棧底與棧頂相同表示一個(gè)空棧

(*S).stacksize = STACK_INIT_SIZE;exit(0);}SqStack;// 順序棧

// 棧頂指針

// 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 }

// 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。int StackEmpty(SqStack S){ if(S.top == S.base)

else

}

// 插入元素e為新的棧頂元素。int Push(SqStack *S, SElemType e){ if((*S).top-(*S).base >=(*S).stacksize)// 棧滿，追加存儲(chǔ)空間

{

} *((*S).top)++=e;return 1;} // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top ==(*S).base)

左

return 1;} // 定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡 // 當(dāng)迷宮m的b點(diǎn)的序號為1(可通過路徑)，return 1;否則，return 0。int Pass(PosType b){

if(m[b.x][b.y]==1)

else return 0;return 1;return 0;*e = *--(*S).top;

// 這個(gè)等式的++ * 優(yōu)先級相同，但是它們的運(yùn)算方式，是自右向

(*S).base =(SElemType *)realloc((*S).base ，(*S).top =(*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;((*S).stacksize + STACKINCREMENT)* sizeof(SElemType));exit(0);if(!(*S).base)return 0;return 1;}

void FootPrint(PosType a)

// 使迷宮m的a點(diǎn)的序號變?yōu)樽阚E(curstep)，表示經(jīng)過 { m[a.x][a.y]=curstep;}

// 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置

PosType NextPos(PosType c,int di){ PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// {行增量,列增量}

// 移動(dòng)方向,依次為東南西北

c.x+=direc[di].x;c.y+=direc[di].y;return c;}

// 使迷宮m的b點(diǎn)的序號變?yōu)?1(不能通過的路徑)void MarkPrint(PosType b){

m[b.x][b.y]=-1;} // 若迷宮maze中存在從入口start到出口end的通道，則求得一條

// 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 int MazePath(PosType start,PosType end){

SqStack S;PosType curpos;SElemType e;

InitStack(&S);curpos=start;do {

if(Pass(curpos)){// 當(dāng)前位置可以通過，即是未曾走到過的通道塊

FootPrint(curpos);// 留下足跡

e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e);// 入棧當(dāng)前位置及狀態(tài)

curstep++;// 足跡加1

if(curpos.x==end.x&&curpos.y==end.y)// 到達(dá)終點(diǎn)(出口)

} else return 1;curpos=NextPos(curpos,e.di);{// 當(dāng)前位置不能通過

} if(!StackEmpty(S)){

} Pop(&S,&e);// 退棧到前一位置

curstep--;while(e.di==3&&!StackEmpty(S))// 前一位置處于最后一個(gè)方向(北){

} if(e.di<3)// 沒到最后一個(gè)方向(北){

}

e.di++;// 換下一個(gè)方向探索

Push(&S,e);curstep++;// 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 curpos=NextPos(e.seat,e.di);

MarkPrint(e.seat);// 留下不能通過的標(biāo)記(-1)Pop(&S,&e);// 退回一步

curstep--;}while(!StackEmpty(S));return 0;}

// 輸出迷宮的結(jié)構(gòu)

void Print(int x,int y){

int i,j;

for(i=0;i

} }

void main(){ PosType begin,end;int i,j,x,y,x1,y1,n,k;for(j=0;j

//清屏函數(shù)

printf(“***************************************************nnn”);printf(“

1請輸入迷宮的行數(shù),列數(shù)n”);printf(“

2請輸入迷宮內(nèi)墻單元數(shù)n”);printf(“

3迷宮結(jié)構(gòu)如下n”);printf(“

4輸入迷宮的起點(diǎn)和終點(diǎn)n”);printf(“

5輸出結(jié)果n”);printf(“

0退出n”);printf(“nn請選擇

”);scanf(“%d”,&n);switch(n){ case 1:{

printf(“請輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開)”);

scanf(“%d%d”, &x, &y);

for(j=1;j

{

for(i=1;i

for(j=1;j

// 迷宮左邊列的周邊即左邊墻

m[j][y-1]=0;// 迷宮右邊列的周邊即右邊墻

for(i=0;i

// 迷宮上面行的周邊即上邊墻

m[x-1][i]=0;// 迷宮下面行的周邊即下邊墻

物

聯(lián)

網(wǎng)

班

-15180118-劉沛

航

}

}break;

case 2:

{printf(“請輸入迷宮內(nèi)墻單元數(shù)：”);

scanf(“%d”,&j);

printf(“請依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù),列數(shù)：(空格隔開)n”);

for(i=1;i<=j;i++)

{ scanf(“%d%d”,&x1,&y1);

} m[x1][y1]=0;

}break;

case 3:{ Print(x,y);printf(“劉沛航建立的迷宮，定義墻元素值為0,可通過路徑為1，輸入0退出”);scanf(“%d”,&k);}break;

case 4:{ printf(“請輸入起點(diǎn)的行數(shù),列數(shù)：（空格隔開）”);

scanf(“%d%d”,&begin.x,&begin.y);

printf(“請輸入終點(diǎn)的行數(shù),列數(shù)：（空格隔開）”);

scanf(“%d%d”,&end.x,&end.y);}break;

case 5:{

if(MazePath(begin,end))// 求得一條通路

{

} else printf(“此迷宮沒有從入口到出口的路徑，謝謝使用劉沛航的程序n”);printf(“輸入0退出”);scanf(“%d”,&k);}break;} }while(n!=0);} printf(“此迷宮從入口到出口的一條路徑如下，謝謝使用劉沛航的程序:n”);Print(x,y);// 輸出此通路

第四篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

數(shù) 據(jù) 結(jié) 構(gòu)

課程設(shè)計(jì)報(bào)告

題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學(xué) 號： 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)對多項(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ù)對象名。

(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)式申請足夠的存儲(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ù)要求需要對多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進(jìn)行處理，此處由于反復(fù)使用指針對各個(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)；對于乘除算法的大致流程都是：首先建立多項(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ò)，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4

代碼編寫。

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

最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。

六、測試（程序截圖）

1.數(shù)據(jù)輸入及主菜單

2.加法和減法模塊

3.乘法和除法模塊

七、總結(jié)

通過本次應(yīng)用C語言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語言程序設(shè)計(jì)的知識(shí)，以前對指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計(jì)對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對自己以后學(xué)習(xí)其他語言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。

八、指導(dǎo)老師評語及成績

附錄：（課程設(shè)計(jì)代碼）

#include #include #include typedef struct Polynomial {

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->expnexpn)//查找插入位置

{

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(“請輸入第%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->expnexpn)return-1;

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

數(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 #include #include #include #define N 200

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請輸入權(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)

//對結(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]='