第一篇：數據結構實驗報告十—教學計劃編制問題

問題描述：

若用有向網表示教學計劃，其中頂點表示某門課程，有向邊表示課程之間的先修關系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設計一個教學計劃編制程序，獲取一個不沖突的線性的課程教學流程。（課程線性排列，每門課上課時其先修課程已經被安排）。

基本要求：

（1）輸入參數：課程總數，每門課的課程號（固定占3位的字母數字串）和直接先修課的課程號。

（2）若根據輸入條件問題無解，則報告適當的信息；否則將教學計劃輸出到用戶指定的文件中。

一、需求分析：

本程序需要基于圖的基本操作來實現

二、概要設計 ：

抽象數據類型 ：

為實現上述功能需建立一個結點類，線性表類，圖類。

算法的基本思想 ：

1、圖的構建：

建立一個結點類，類的元素有字符型變量用來存儲字母，整形變量用來存儲位置，該類型的指針，指向下一個元素。建立一個線性表類，完成線性表的構建。建立一個圖類，完成圖的信息的讀取，（如有n個點，則建立n個線性表，將每個結點與其指向的結點組成一個線性表，并記錄線性表的長度）。

2、Topsort算法：

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

程序由三個模塊組成：

輸入模塊： 讀入圖的信息（頂點和邊，用線性表進行存儲）。處理模塊：topsort算法。輸出模塊：將結果輸出。

三、詳細設計

算法的具體步驟： class Node{//結點類 public: string node;int position;//位置 Node* next;bool visit;//是否被訪問

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(){ //讀入點

string ch;

for(int i=0;i

cout<<“請輸入頂點”<

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<<“請輸入邊”<

cin>>ch1>>ch2;

for(int j=0;j

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

pos1=j;//找到該字母對應的位置

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

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

break;

}

}

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

} } void topsort(){ //拓撲排序

int i;

int *d=new int[numVertex];

for(i=0;i

d[i]=0;//數組初始化

for(i=0;i

Node* p=line[i].head;

while(p->next!=NULL){

d[p->next->position]++;//計算每個點的入度

p=p->next;

}

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

for(i=0;i

if(d[i]==0){

d[i]=top;//找到第一個入度為0的點

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]--;//當起點被刪除，時后面的點的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

}

} cout<

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

四、調試分析

略。

五、測試結果

本實驗的測試結果截圖如下：

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

六、用戶使用說明（可選）

1、本程序的運行環境為windows 操作系統，執行文件為Untitled1.exe 2、運行程序時

提示輸入數據 并且輸入數據然后回車就可以繼續輸入相應數據，最后即可得到結果。

七、實驗心得（可選）

1、本實驗是在圖的遍歷問題的基礎上做的，圖的構建大部分是采用圖 的遍歷問題中的代碼（不過要將結點類中的char改為string型），自己另外寫了topsort函數，就完成了整個程序。

2、topsort函數中一開始采用的方法是找到一個入度為0的點，完成 相應的操作后，重新進行搜索，后來改進代碼，先搜索入度為0的 點后面連接的點，這樣減少了算法復雜度。

附錄（實驗代碼）：

#include #include using namespace std;class Node{//結點類 public: string node;int position;//位置 Node* next;bool visit;//是否被訪問

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(){ //讀入點

string ch;

for(int i=0;i

cout<<“請輸入頂點”<

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<<“請輸入邊”<

cin>>ch1>>ch2;

for(int j=0;j

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

pos1=j;//找到該字母對應的位置

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

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

break;

}

}

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

} } void topsort(){ //拓撲排序

int i;

int *d=new int[numVertex];

for(i=0;i

d[i]=0;//數組初始化

for(i=0;i

Node* p=line[i].head;

while(p->next!=NULL){

d[p->next->position]++;//計算每個點的入度

p=p->next;

}

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

for(i=0;i

if(d[i]==0){

d[i]=top;//找到第一個入度為0的點

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]--;//當起點被刪除，時后面的點的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

}

} cout<

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

第二篇：數據結構迷宮問題實驗報告

《數據結構與算法設計》

迷宮問題實驗報告

——實驗二

專業：物聯網工程 班級：物聯網1班 學號：15180118 姓名：劉沛航

一、實驗目的

本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標記所走過的路徑結束程序；當迷宮無路徑時，提示輸入錯誤結束程序。

二、實驗內容

用一個m*m長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序對于任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。

三、程序設計

1、概要設計

（1）設定棧的抽象數據類型定義

ADT Stack{

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

操作結果：構造一個空棧 Push（&S，e）

初始條件：棧已經存在

操作結果：將e所指向的數據加入到棧s中 Pop（&S,&e）

初始條件：棧已經存在

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

初始條件：棧已經存在

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

初始條件：棧已經存在

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

初始條件：棧已經存在 操作結果：銷毀棧s }ADT Stack

（2）設定迷宮的抽象數據類型定義

ADT yanshu{

數據對象：D={ai,j|ai,j屬于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=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){

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

操作結果：構造迷宮的整形數組，以空白表示通路，字符‘0’表示障礙

在迷宮四周加上一圈障礙

MazePath（&maze）{

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

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

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

}ADTmaze

（3）本程序包括三個模塊

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

b、棧模塊——實現棧的抽象數據類型 c、迷宮模塊——實現迷宮的抽象數據類型

2、詳細設計

（1）坐標位置類型：

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

}PosType;//坐標

（2）迷宮類型：

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

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

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

（3）棧類型：

typedef struct{ int step;//當前位置在路徑上的“序號” PosType seat;//當前的坐標位置

DirectiveType di;//往下一個坐標位置的方向 }SElemType;//棧的元素類型

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

//初始化，設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待會棧頂元素并返回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中的每個節點調用函數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)){ //如果當前位置可以通過,即是未曾走到的通道塊 FootPrint(maze,curpos);//留下足跡

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

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

四、程序調試分析

1.首先呢，想自己讀入數據的，回來發現那樣，很麻煩，所以還是事先定義一個迷宮。

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

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

五、用戶使用說明

1．本程序運行在windows系列的操作系統下，執行文件為：Maze_Test.exe。

六、程序運行結果

1.建立迷宮： 2．通過1功能建立8*8的迷宮后，通過2功能繼續建立迷宮內部：

通過建立自己設定單元數目建立迷宮內墻。3．通過3功能觀察已建立的迷宮結構：

4．通過4功能確立迷宮起點和終點：

（此處像我們隨機選擇4,4和2,7分別為起點終點）

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

這種情況無法走出迷宮。

我們再次觀察圖像設4,4和1,6分別為起點終點，再運行5功能。

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

七、程序清單

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

// 列值

#define MAXLENGTH 25 // 設迷宮的最大行列為25

typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宮數組[行][列]

typedef struct // 棧的元素類型

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

PosType seat;// 通道塊在迷宮中的＂坐標位置＂

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

// 全局變量

MazeType m;// 迷宮數組

int curstep=1;// 當前足跡,初值為1

#define STACK_INIT_SIZE 10 // 存儲空間初始分配量

#define STACKINCREMENT 2 // 存儲空間分配增量

// 棧的順序存儲表示

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

SElemType *top;

int stacksize;

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

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

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

return 1;

// 棧底與棧頂相同表示一個空棧

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

// 棧頂指針

// 當前已分配的存儲空間，以元素為單位 }

// 若棧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)// 棧滿，追加存儲空間

{

} *((*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,通過路徑為足跡 // 當迷宮m的b點的序號為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;

// 這個等式的++ * 優先級相同，但是它們的運算方式，是自右向

(*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點的序號變為足跡(curstep)，表示經過 { m[a.x][a.y]=curstep;}

// 根據當前位置及移動方向，返回下一位置

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

// 移動方向,依次為東南西北

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

// 使迷宮m的b點的序號變為-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)){// 當前位置可以通過，即是未曾走到過的通道塊

FootPrint(curpos);// 留下足跡

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

curstep++;// 足跡加1

if(curpos.x==end.x&&curpos.y==end.y)// 到達終點(出口)

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

} if(!StackEmpty(S)){

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

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

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

}

e.di++;// 換下一個方向探索

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

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

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

// 輸出迷宮的結構

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

//清屏函數

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

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

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

3迷宮結構如下n”);printf(“

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

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

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

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

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

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;// 迷宮下面行的周邊即下邊墻

物

聯

網

班

-15180118-劉沛

航

}

}break;

case 2:

{printf(“請輸入迷宮內墻單元數：”);

scanf(“%d”,&j);

printf(“請依次輸入迷宮內墻每個單元的行數,列數：(空格隔開)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(“請輸入起點的行數,列數：（空格隔開）”);

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

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

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);// 輸出此通路

第三篇：數據結構實驗報告

注意：實驗結束后提交一份實驗報告電子文檔

電子文檔命名為“學號+姓名”，如：E01214058宋思怡

《數據結構》實驗報告

（一）學號：姓名：專業年級：

實驗名稱：線性表

實驗日期：2014年4月14日

實驗目的：

1、熟悉線性表的定義及其順序和鏈式存儲結構；

2、熟練掌握線性表在順序存儲結構上實現基本操作的方法；

3、熟練掌握在各種鏈表結構中實現線性表基本操作的方法；

4、掌握用 C/C++語言調試程序的基本方法。

實驗內容：

一、編寫程序實現順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：

（1）初始化順序表L；

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

（3）輸出順序表L；

（4）輸出順序表L長度；

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

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

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

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

（9）輸出順序表L；

（10）刪除L的第5個元素；

（11）輸出順序表L。

源代碼

調試分析（給出運行結果界面）

二、編寫程序實現單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能：

????

????

小結或討論:

（1）實驗中遇到的問題和解決方法

（2）實驗中沒有解決的問題

（3）體會和提高

第四篇：數據結構實驗報告

南京信息工程大學實驗（實習）報告

實驗（實習）名稱數據結構實驗（實習）日期 2011-11-2得分指導教師周素萍

系公共管理系專業信息管理與信息系統年級10級班次1姓名常玲學號2010230700

3實驗一順序表的基本操作及C語言實現

【實驗目的】

1、順序表的基本操作及 C 語言實現

【實驗要求】

1、用 C 語言建立自己的線性表結構的程序庫，實現順序表的基本操作。

2、對線性表表示的集合，集合數據由用戶從鍵盤輸入（數據類型為整型），建立相應的順序表，且使得數據按從小到大的順序存放，將兩個集合的并的結果存儲在一個新的線性表集合中，并輸出。

【實驗內容】

1、根據教材定義的順序表機構，用 C 語言實現順序表結構的創建、插入、刪除、查找等操作；

2、利用上述順序表操作實現如下程序：建立兩個順序表表示的集合（集合中無重

復的元素），并求這樣的兩個集合的并。

【實驗結果】

[實驗數據、結果、遇到的問題及解決]

一． 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的編號從0開始 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;

三．// 將合并逆置后的結果放在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的前驅指針 // 保存pb的前驅指針 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;//將當前最小結點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結點插入A表表頭 A->next=qa;

}

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

順序表就是把線性表的元素存儲在數組中，元素之間的關系直接通過相鄰元素的位置來表達。

優點：簡單，數據元素的提取速度快；

缺點：（1）靜態存儲，無法預知問題規模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n）

求兩個集合的并集

該算法是求兩個集合s1和s2的并集，并將結果存入s引用參數所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數集合中得到并集。

第五篇：數據結構實驗報告

實驗報告4 排序

一、實驗目的

1、掌握常用的排序方法，并掌握用高級語言實現排序算法的方法。

2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用。

3、了解各種方法的排序過程及其依據的原則，并掌握各種排序方法的時間復雜度的分析方法。

二、實驗要求及內容

要求編寫的程序所能實現的功能包括：

1、從鍵盤輸入要排序的一組元素的總個數

2、從鍵盤依次輸入要排序的元素值

3、對輸入的元素進行快速排序

4、對輸入的元素進行折半插入排序

三、實驗代碼及相關注釋

#include using namespace std;#include “malloc.h”

typedef struct { int key;}RedType;

typedef struct { RedType r[100];int length;}SqList;

//1 快速排序的結構體

typedef struct {

int data[100];

int last;}Sequenlist;//2 折半插入排序的結構體

int Partition(SqList &L, int low, int high)

//1 尋找基準

{

L.r[0]=L.r[low];//子表的第一個記錄作基準對象

int pivotkey = L.r[low].key;//基準對象關鍵字 while(low

while(low= pivotkey)--high;

L.r[low] = L.r[high];//小于基準對象的移到區間的左側

while(low

L.r[high] = L.r[low];//大于基準對象的移到區間的右側 }

L.r[low] = L.r[0];return low;}

void QuickSort(SqList &L, int low, int high)

//1 快速排序 { //在序列low-high中遞歸地進行快速排序

if(low < high)

{

int pivotloc= Partition(L, low, high);

//尋找基準

QuickSort(L, low, pivotloc-1);//對左序列同樣遞歸處理

QuickSort(L, pivotloc+1, high);//對右序列同樣遞歸處理

} }

Sequenlist *Sqlset()

//2 輸入要折半插入排序的一組元素

{

Sequenlist *L;

int i;

L=(Sequenlist *)malloc(sizeof(Sequenlist));

L->last=0;

cout<<“請輸入要排序的所有元素的總個數：”;

cin>>i;

cout<

cout<<“請依次輸入所有元素的值：”;

if(i>0)

{

for(L->last=1;L->last<=i;L->last++)

cin>>L->data[L->last];

L->last--;

}

return(L);}

middlesort(Sequenlist *L)

//2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]data[mid])

high=mid-1;//插入點在前半區

else

low=mid+1;//插入點在后半區

}

for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0];//插入 } return 0;}

int main(){ gg: cout<<“請選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout<

if(m==1){ SqList L;int n;cout<<“請輸入要排序的所有元素的總個數：”;cin>>n;cout<

cin>>L.r[i].key;

} cout<

QuickSort(L,1,L.length);

for(int j=1;j<=L.length;j++)

{

cout<

}

cout<

cout<

}

if(m==2){

Sequenlist *L;

int i;

L=Sqlset();

cout<

middlesort(L);

cout<<“折半插入排序后為：”;

for(i=1;i<=L->last;i++)

{

cout<data[i]<<“ ”;

}

cout<

cout<

goto gg;}

if(m==3){

exit(0);

cout<

四、重要函數功能說明

1、Sequenlist *Sqlset()

輸入要折半插入排序的一組元素

2、int Partition(SqList &L, int low, int high)

尋找快速排序的基準

3、void QuickSort(SqList &L, int low, int high)

快速排序

4、middlesort(Sequenlist *L)

折半插入排序

五、程序運行結果

下圖僅為分別排序一次，可多次排序，后面有相關截圖：

六、實驗中遇到的問題、解決及體會

1、起初編寫快速排序的程序時，我是完全按照老師PPT上的算法敲上去的，然后建立了一個SqList的結構體，調試運行時出現錯誤，仔細查看才意識到Partition函數中L中應該包含元素key，而我建立結構體時沒有注意，然后我將key這個元素補充進去，繼續調試，又出現錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經寫了函數定義，為什么會這樣，當我又回過頭來閱讀程序時，我發現QuickSort函數中調用了Partition函數，但是我的Partition函數的定義在QuickSort函數的后面，于是我將Partition函數放到了QuickSort函數的前面，再次調試運行，就可以正常運行，得出結果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。

運行程序錯誤截圖：

2、本來我是編寫了兩個程序，分別實現快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現所需功能的前提下，多想問題，看是否能使程序更加實用簡便。

修改程序前兩個運行結果截圖

（兩個程序，調試運行兩次，每次只能進行一次排序）

1、快速排序程序運行結果截圖：

2、折半插入排序程序結果截圖：

程序重要模塊修改截圖：

修改程序后運行截圖：

（一個程序，調試運行一次，可多次進行不同序列的不同排序）