第一篇：數(shù)據(jù)結(jié)構(gòu)：教學(xué)計(jì)劃的編制問(wèn)題(實(shí)驗(yàn)10實(shí)驗(yàn)報(bào)告)（范文模版）

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)十:教學(xué)計(jì)劃的編制問(wèn)題

姓名：戴鐵泉 學(xué)號(hào)：20101410305 班級(jí)：物聯(lián)網(wǎng)1001班 完成日期：2012.05.21

一、問(wèn)題描述：

若用有向網(wǎng)表示教學(xué)計(jì)劃，其中頂點(diǎn)表示某門課程，有向邊表示課程之間的先修關(guān)系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序，獲取一個(gè)不沖突的線性的課程教學(xué)流程。（課程線性排列，每門課上課時(shí)其先修課程已經(jīng)被安排）?；疽?/p>

（1）輸入?yún)?shù)：課程總數(shù)，每門課的課程號(hào)（固定占3位的字母數(shù)字串）和直接先修課的課程號(hào)。

（2）若根據(jù)輸入條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔?；否則將教學(xué)計(jì)劃輸出到用戶指定的文件中。

二．需求分析：

1、本程序需要基于圖的基本操作來(lái)實(shí)現(xiàn)

三．概要設(shè)計(jì)

抽象數(shù)據(jù)類型：

為實(shí)現(xiàn)上述功能需建立一個(gè)結(jié)點(diǎn)類，線性表類，圖類。算法的基本思想：

1、圖的構(gòu)建：

建立一個(gè)結(jié)點(diǎn)類，類的元素有字符型變量用來(lái)存儲(chǔ)字母，整形變量用來(lái)存儲(chǔ)位置，該類型的指針，指向下一個(gè)元素。建立一個(gè)線性表類，完成線性表的構(gòu)建。建立一個(gè)圖類，完成圖的信息的讀取，（如有n個(gè)點(diǎn)，則建立n個(gè)線性表，將每個(gè)結(jié)點(diǎn)與其指向的結(jié)點(diǎn)組成一個(gè)線性表，并記錄線性表的長(zhǎng)度）。

2、Topsort算法：

先計(jì)算每個(gè)點(diǎn)的入度，保存在數(shù)組中。找到第一個(gè)入度為0 的點(diǎn)，將該點(diǎn)所連的各點(diǎn)的入度減一。再在這些點(diǎn)中找入度為0 的點(diǎn)。如果找到，重復(fù)上述操作。如果找不到，則跳出while循環(huán)，再搜索其他的點(diǎn)，看入度是否為0。再重復(fù)上述操作，如果所有的入度為0的點(diǎn)都被尋找到，但個(gè)數(shù)少于輸入頂點(diǎn)的個(gè)數(shù)，說(shuō)明該圖存在環(huán)。程序的流程：

（1）輸入模塊： 讀入圖的信息（頂點(diǎn)和邊，用線性表進(jìn)行存儲(chǔ)）。（2）處理模塊：topsort算法。（3）輸出模塊：將結(jié)果輸出。

四．詳細(xì)設(shè)計(jì)：

算法的具體步驟： class Node{//結(jié)點(diǎn)類 public:

string node;

int position;//位置

Node* next;

bool visit;//是否被訪問(wèn)

Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{

//線性表類 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();}

void insert(int v,string ch){

//插入元素

} Node* current=new Node();current->node=ch;current->position=v;fence->next=current;fence=current;num++;};class Graph{

//圖類 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //讀入點(diǎn)

} void pushEdge(){ //讀入邊

string ch1,ch2;int pos1,pos2;for(int i=0;i

} cout<<“請(qǐng)輸入頂點(diǎn)”<>ch;line[i].head->node=ch;line[i].head->position=i;

}

} cout<<“請(qǐng)輸入邊”<>ch1>>ch2;for(int j=0;j

} line[pos1].insert(pos2,ch2);if(line[j].head->node==ch1)pos1=j;

//找到該字母對(duì)應(yīng)的位置

if(line[j].head->node==ch2){

} pos2=line[j].head->position;break;

void topsort(){

//拓?fù)渑判?/p>

int i;int *d=new int[numVertex];

for(i=0;i

//數(shù)組初始化

for(i=0;i

Node* p=line[i].head;while(p->next!=NULL){ d[p->next->position]++;//計(jì)算每個(gè)點(diǎn)的入度

}

p=p->next;} int top=-1,m=0,j,k;

for(i=0;i

} while(top!=-1){ if(d[i]==0){ d[i]=top;

//找到第一個(gè)入度為0的點(diǎn)

top=i;

j=top;

top=d[top];

cout<node<<“ ”;

m++;

Node* p=line[j].head;

while(p->next!=NULL){

k=p->next->position;

d[k]--;

//當(dāng)起點(diǎn)被刪除，時(shí)后面的點(diǎn)的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

} }

cout<

if(m

//輸出點(diǎn)的個(gè)數(shù)小于輸入點(diǎn)的個(gè)數(shù)，不能完全遍歷

cout<<“網(wǎng)絡(luò)存在回路”<

delete []d;} };int main(){

int n,m;cout<<“請(qǐng)輸入節(jié)點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)”<>n>>m;Graph G(n,m);

G.pushVertex();G.pushEdge();G.topsort();system(“pause”);

return 0;} 五．調(diào)試分析：

將建立的線性表輸出來(lái)檢驗(yàn)圖的信息是否完全被讀入，構(gòu)建是否正確。

六．測(cè)試結(jié)果：

七．實(shí)驗(yàn)心得：

1、本實(shí)驗(yàn)是在圖的遍歷問(wèn)題的基礎(chǔ)上做的，圖的構(gòu)建大部分是采用圖 的遍歷問(wèn)題中的代碼（不過(guò)要將結(jié)點(diǎn)類中的char改為string型），自己另外寫(xiě)了topsort函數(shù)，就完成了整個(gè)程序。

2、topsort函數(shù)中一開(kāi)始采用的方法是找到一個(gè)入度為0的點(diǎn)，完成 相應(yīng)的操作后，重新進(jìn)行搜索，后來(lái)改進(jìn)代碼，先搜索入度為0的 點(diǎn)后面連接的點(diǎn)，這樣減少了算法復(fù)雜度。

八、附件

教學(xué)計(jì)劃的編制問(wèn)題.cpp #include #include using namespace std;class Node{//結(jié)點(diǎn)類 public:

string node;

int position;//位置

Node* next;

bool visit;//是否被訪問(wèn)

Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{

//線性表類 public:

int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();}

void insert(int v,string ch){

//插入元素

Node* current=new Node();current->node=ch;current->position=v;

};

} fence->next=current;fence=current;num++;class Graph{

//圖類 private:

int numVertex;int numEdge;Line* line;public:

Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //讀入點(diǎn)

} void pushEdge(){ //讀入邊 string ch;for(int i=0;i

} cout<<“請(qǐng)輸入頂點(diǎn)”<>ch;line[i].head->node=ch;line[i].head->position=i;

} string ch1,ch2;int pos1,pos2;for(int i=0;i

} cout<<“請(qǐng)輸入邊”<>ch1>>ch2;for(int j=0;j

} line[pos1].insert(pos2,ch2);if(line[j].head->node==ch1)pos1=j;

//找到該字母對(duì)應(yīng)的位置

if(line[j].head->node==ch2){

} pos2=line[j].head->position;break;

void topsort(){

//拓?fù)渑判?/p>

int i;int *d=new int[numVertex];

for(i=0;i

//數(shù)組初始化

for(i=0;i

} Node* p=line[i].head;while(p->next!=NULL){ d[p->next->position]++;//計(jì)算每個(gè)點(diǎn)的入度

p=p->next;} int top=-1,m=0,j,k;

for(i=0;i

} while(top!=-1){ if(d[i]==0){ d[i]=top;

//找到第一個(gè)入度為0的點(diǎn)

top=i;

j=top;

top=d[top];

cout<node<<“ ”;

m++;

Node* p=line[j].head;

while(p->next!=NULL){

k=p->next->position;

d[k]--;

//當(dāng)起點(diǎn)被刪除，時(shí)后面的點(diǎn)的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

} }

cout<

//輸出點(diǎn)的個(gè)數(shù)小于輸入點(diǎn)的個(gè)數(shù)，不能完全遍歷

cout<<“網(wǎng)絡(luò)存在回路”<

delete []d;} };int main(){

int n,m;cout<<“請(qǐng)輸入節(jié)點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)”<>n>>m;Graph G(n,m);G.pushVertex();

G.pushEdge();G.topsort();system(“pause”);

return 0;}

第二篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告十—教學(xué)計(jì)劃編制問(wèn)題

問(wèn)題描述：

若用有向網(wǎng)表示教學(xué)計(jì)劃，其中頂點(diǎn)表示某門課程，有向邊表示課程之間的先修關(guān)系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序，獲取一個(gè)不沖突的線性的課程教學(xué)流程。（課程線性排列，每門課上課時(shí)其先修課程已經(jīng)被安排）。

基本要求：

（1）輸入?yún)?shù)：課程總數(shù)，每門課的課程號(hào)（固定占3位的字母數(shù)字串）和直接先修課的課程號(hào)。

（2）若根據(jù)輸入條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。

一、需求分析：

本程序需要基于圖的基本操作來(lái)實(shí)現(xiàn)

二、概要設(shè)計(jì) ：

抽象數(shù)據(jù)類型 ：

為實(shí)現(xiàn)上述功能需建立一個(gè)結(jié)點(diǎn)類，線性表類，圖類。

算法的基本思想 ：

1、圖的構(gòu)建：

建立一個(gè)結(jié)點(diǎn)類，類的元素有字符型變量用來(lái)存儲(chǔ)字母，整形變量用來(lái)存儲(chǔ)位置，該類型的指針，指向下一個(gè)元素。建立一個(gè)線性表類，完成線性表的構(gòu)建。建立一個(gè)圖類，完成圖的信息的讀取，（如有n個(gè)點(diǎn)，則建立n個(gè)線性表，將每個(gè)結(jié)點(diǎn)與其指向的結(jié)點(diǎn)組成一個(gè)線性表，并記錄線性表的長(zhǎng)度）。

2、Topsort算法：

先計(jì)算每個(gè)點(diǎn)的入度，保存在數(shù)組中。找到第一個(gè)入度為0的點(diǎn)，將該點(diǎn)所連的各點(diǎn)的入度減一。再在這些點(diǎn)中找入度為0 的點(diǎn)。如果找到，重復(fù)上述操作。如果找不到，則跳出while循環(huán)，再搜索其他的點(diǎn)，看入度是否為0。再重復(fù)上述操作，如果所有的入度為0的點(diǎn)都被尋找到，但個(gè)數(shù)少于輸入頂點(diǎn)的個(gè)數(shù)，說(shuō)明該圖存在環(huán)。程序的流程

程序由三個(gè)模塊組成：

輸入模塊： 讀入圖的信息（頂點(diǎn)和邊，用線性表進(jìn)行存儲(chǔ)）。處理模塊：topsort算法。輸出模塊：將結(jié)果輸出。

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

算法的具體步驟： class Node{//結(jié)點(diǎn)類 public: string node;int position;//位置 Node* next;bool visit;//是否被訪問(wèn)

Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{ //線性表類 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素

Node* current=new Node();

current->node=ch;

current->position=v;

fence->next=current;

fence=current;

num++;} };class Graph{ //圖類 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //讀入點(diǎn)

string ch;

for(int i=0;i

cout<<“請(qǐng)輸入頂點(diǎn)”<

cin>>ch;

line[i].head->node=ch;

line[i].head->position=i;

} } void pushEdge(){ //讀入邊

string ch1,ch2;

int pos1,pos2;

for(int i=0;i

{

cout<<“請(qǐng)輸入邊”<

cin>>ch1>>ch2;

for(int j=0;j

if(line[j].head->node==ch1)

pos1=j;//找到該字母對(duì)應(yīng)的位置

if(line[j].head->node==ch2){

pos2=line[j].head->position;

break;

}

}

line[pos1].insert(pos2,ch2);

} } void topsort(){ //拓?fù)渑判?/p>

int i;

int *d=new int[numVertex];

for(i=0;i

d[i]=0;//數(shù)組初始化

for(i=0;i

Node* p=line[i].head;

while(p->next!=NULL){

d[p->next->position]++;//計(jì)算每個(gè)點(diǎn)的入度

p=p->next;

}

} int top=-1,m=0,j,k;

for(i=0;i

if(d[i]==0){

d[i]=top;//找到第一個(gè)入度為0的點(diǎn)

top=i;

}

while(top!=-1){ j=top;top=d[top];

cout<node<<“ ”;m++;

Node* p=line[j].head;

while(p->next!=NULL){

k=p->next->position;

d[k]--;//當(dāng)起點(diǎn)被刪除，時(shí)后面的點(diǎn)的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

}

} cout<

cout<<“網(wǎng)絡(luò)存在回路”<>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(“pause”);return 0;}

四、調(diào)試分析

略。

五、測(cè)試結(jié)果

本實(shí)驗(yàn)的測(cè)試結(jié)果截圖如下：

注：此處由于不會(huì)用文件流輸入和輸出，故在命令提示符上直接進(jìn)行輸入。

六、用戶使用說(shuō)明（可選）

1、本程序的運(yùn)行環(huán)境為windows 操作系統(tǒng)，執(zhí)行文件為Untitled1.exe 2、運(yùn)行程序時(shí)

提示輸入數(shù)據(jù) 并且輸入數(shù)據(jù)然后回車就可以繼續(xù)輸入相應(yīng)數(shù)據(jù)，最后即可得到結(jié)果。

七、實(shí)驗(yàn)心得（可選）

1、本實(shí)驗(yàn)是在圖的遍歷問(wèn)題的基礎(chǔ)上做的，圖的構(gòu)建大部分是采用圖 的遍歷問(wèn)題中的代碼（不過(guò)要將結(jié)點(diǎn)類中的char改為string型），自己另外寫(xiě)了topsort函數(shù)，就完成了整個(gè)程序。

2、topsort函數(shù)中一開(kāi)始采用的方法是找到一個(gè)入度為0的點(diǎn)，完成 相應(yīng)的操作后，重新進(jìn)行搜索，后來(lái)改進(jìn)代碼，先搜索入度為0的 點(diǎn)后面連接的點(diǎn)，這樣減少了算法復(fù)雜度。

附錄（實(shí)驗(yàn)代碼）：

#include #include using namespace std;class Node{//結(jié)點(diǎn)類 public: string node;int position;//位置 Node* next;bool visit;//是否被訪問(wèn)

Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{ //線性表類 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素

Node* current=new Node();

current->node=ch;

current->position=v;

fence->next=current;

fence=current;

num++;} };class Graph{ //圖類 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //讀入點(diǎn)

string ch;

for(int i=0;i

cout<<“請(qǐng)輸入頂點(diǎn)”<

cin>>ch;

line[i].head->node=ch;

line[i].head->position=i;

} } void pushEdge(){ //讀入邊

string ch1,ch2;

int pos1,pos2;

for(int i=0;i

{

cout<<“請(qǐng)輸入邊”<

cin>>ch1>>ch2;

for(int j=0;j

if(line[j].head->node==ch1)

pos1=j;//找到該字母對(duì)應(yīng)的位置

if(line[j].head->node==ch2){

pos2=line[j].head->position;

break;

}

}

line[pos1].insert(pos2,ch2);

} } void topsort(){ //拓?fù)渑判?/p>

int i;

int *d=new int[numVertex];

for(i=0;i

d[i]=0;//數(shù)組初始化

for(i=0;i

Node* p=line[i].head;

while(p->next!=NULL){

d[p->next->position]++;//計(jì)算每個(gè)點(diǎn)的入度

p=p->next;

}

} int top=-1,m=0,j,k;

for(i=0;i

if(d[i]==0){

d[i]=top;//找到第一個(gè)入度為0的點(diǎn)

top=i;

}

while(top!=-1){ j=top;top=d[top];

cout<node<<“ ”;m++;

Node* p=line[j].head;

while(p->next!=NULL){

k=p->next->position;

d[k]--;//當(dāng)起點(diǎn)被刪除，時(shí)后面的點(diǎn)的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

}

} cout<

cout<<“網(wǎng)絡(luò)存在回路”<>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(“pause”);return 0;}

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

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

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

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

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

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

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

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

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

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

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

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

ADT Stack{

數(shù)據(jù)對(duì)象：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ù)對(duì)象：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）//將迷宮打印出來(lái)

（3）棧類型：

typedef struct{ int step;//當(dāng)前位置在路徑上的“序號(hào)” 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的長(zhǎng)度

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））//從棧頂依次對(duì)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)前位置可以通過(guò),即是未曾走到的通道塊 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)前位置不能通過(guò) if(!StackEmpty(s)){ Pop(s,e);while(e.di==4 &&!StackEmpty(s)){ MarkPrint(maze,e.seat);Pop(s,e);//留下不能通過(guò)的標(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ù)的，回來(lái)發(fā)現(xiàn)那樣，很麻煩，所以還是事先定義一個(gè)迷宮。

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

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

五、用戶使用說(shuō)明

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

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

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

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

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

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

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

這種情況無(wú)法走出迷宮。

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

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

七、程序清單

#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;// 通道塊在路徑上的＂序號(hào)＂

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,可通過(guò)路徑為1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡 // 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，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)先級(jí)相同，但是它們的運(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)的序號(hào)變?yōu)樽阚E(curstep)，表示經(jīng)過(guò) { 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)的序號(hào)變?yōu)?1(不能通過(guò)的路徑)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)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊

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)前位置不能通過(guò)

} if(!StackEmpty(S)){

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

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

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

}

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

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

MarkPrint(e.seat);// 留下不能通過(guò)的標(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請(qǐng)輸入迷宮的行數(shù),列數(shù)n”);printf(“

2請(qǐng)輸入迷宮內(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請(qǐng)選擇

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

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

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(“請(qǐng)輸入迷宮內(nèi)墻單元數(shù)：”);

scanf(“%d”,&j);

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

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

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

} m[x1][y1]=0;

}break;

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

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

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

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

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

case 5:{

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

{

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

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

注意：實(shí)驗(yàn)結(jié)束后提交一份實(shí)驗(yàn)報(bào)告電子文檔

電子文檔命名為“學(xué)號(hào)+姓名”，如：E01214058宋思怡

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告

（一）學(xué)號(hào)：姓名：專業(yè)年級(jí)：

實(shí)驗(yàn)名稱：線性表

實(shí)驗(yàn)日期：2014年4月14日

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

1、熟悉線性表的定義及其順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；

2、熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法；

3、熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表基本操作的方法；

4、掌握用 C/C++語(yǔ)言調(diào)試程序的基本方法。

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

一、編寫(xiě)程序?qū)崿F(xiàn)順序表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：

（1）初始化順序表L；

（2）依次在L尾部插入元素-1,21,13,24,8；

（3）輸出順序表L；

（4）輸出順序表L長(zhǎng)度；

（5）判斷順序表L是否為空；

（6）輸出順序表L的第3個(gè)元素；

（7）輸出元素24的位置；

（8）在L的第4個(gè)元素前插入元素0；

（9）輸出順序表L；

（10）刪除L的第5個(gè)元素；

（11）輸出順序表L。

源代碼

調(diào)試分析（給出運(yùn)行結(jié)果界面）

二、編寫(xiě)程序?qū)崿F(xiàn)單鏈表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：

????

????

小結(jié)或討論:

（1）實(shí)驗(yàn)中遇到的問(wèn)題和解決方法

（2）實(shí)驗(yàn)中沒(méi)有解決的問(wèn)題

（3）體會(huì)和提高

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

南京信息工程大學(xué)實(shí)驗(yàn)（實(shí)習(xí)）報(bào)告

實(shí)驗(yàn)（實(shí)習(xí)）名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)（實(shí)習(xí)）日期 2011-11-2得分指導(dǎo)教師周素萍

系公共管理系專業(yè)信息管理與信息系統(tǒng)年級(jí)10級(jí)班次1姓名常玲學(xué)號(hào)2010230700

3實(shí)驗(yàn)一順序表的基本操作及C語(yǔ)言實(shí)現(xiàn)

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

1、順序表的基本操作及 C 語(yǔ)言實(shí)現(xiàn)

【實(shí)驗(yàn)要求】

1、用 C 語(yǔ)言建立自己的線性表結(jié)構(gòu)的程序庫(kù)，實(shí)現(xiàn)順序表的基本操作。

2、對(duì)線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應(yīng)的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個(gè)集合的并的結(jié)果存儲(chǔ)在一個(gè)新的線性表集合中，并輸出。

【實(shí)驗(yàn)內(nèi)容】

1、根據(jù)教材定義的順序表機(jī)構(gòu)，用 C 語(yǔ)言實(shí)現(xiàn)順序表結(jié)構(gòu)的創(chuàng)建、插入、刪除、查找等操作；

2、利用上述順序表操作實(shí)現(xiàn)如下程序：建立兩個(gè)順序表表示的集合（集合中無(wú)重

復(fù)的元素），并求這樣的兩個(gè)集合的并。

【實(shí)驗(yàn)結(jié)果】

[實(shí)驗(yàn)數(shù)據(jù)、結(jié)果、遇到的問(wèn)題及解決]

一． Status InsertOrderList(SqList &va,ElemType x)

{

}

二． Status DeleteK(SqList &a,int i,int k)

{//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x

}

//注意i的編號(hào)從0開(kāi)始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK;

三．// 將合并逆置后的結(jié)果放在C表中，并刪除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅(qū)指針 // 保存pb的前驅(qū)指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data

data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qa;

}

} pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;

順序表就是把線性表的元素存儲(chǔ)在數(shù)組中，元素之間的關(guān)系直接通過(guò)相鄰元素的位置來(lái)表達(dá)。

優(yōu)點(diǎn)：簡(jiǎn)單，數(shù)據(jù)元素的提取速度快；

缺點(diǎn)：（1）靜態(tài)存儲(chǔ)，無(wú)法預(yù)知問(wèn)題規(guī)模的大小，可能空間不足，或浪費(fèi)存儲(chǔ)空間；（2）插入元素和刪除元素時(shí)間復(fù)雜度高——O（n）

求兩個(gè)集合的并集

該算法是求兩個(gè)集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復(fù)制到s中，然后把s2中的每個(gè)元素依次插入到集合s中，當(dāng)然重復(fù)的元素不應(yīng)該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對(duì)應(yīng)的實(shí)際參數(shù)集合中得到并集。