第一篇：數(shù)據(jù)結構迷宮問題實驗報告
《數(shù)據(jù)結構與算法設計》
迷宮問題實驗報告
——實驗二
專業(yè)：物聯(lián)網工程 班級：物聯(lián)網1班 學號：15180118 姓名：劉沛航
一、實驗目的
本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標記所走過的路徑結束程序；當迷宮無路徑時，提示輸入錯誤結束程序。
二、實驗內容
用一個m*m長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序對于任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。
三、程序設計
1、概要設計
（1）設定棧的抽象數(shù)據(jù)類型定義
ADT Stack{
數(shù)據(jù)對象：D={ai|ai屬于CharSet，i=1、2…n，n>=0} 數(shù)據(jù)關系：R={
操作結果：構造一個空棧 Push（&S，e）
初始條件：棧已經存在
操作結果：將e所指向的數(shù)據(jù)加入到棧s中 Pop（&S,&e）
初始條件：棧已經存在
操作結果：若棧不為空，用e返回棧頂元素，并刪除棧頂元素 Getpop（&S，&e）
初始條件：棧已經存在
操作結果：若棧不為空，用e返回棧頂元 StackEmpty(&S)
初始條件：棧已經存在
操作結果：判斷棧是否為空。若棧為空，返回1，否則返回0 Destroy(&S)
初始條件：棧已經存在 操作結果：銷毀棧s }ADT Stack
（2）設定迷宮的抽象數(shù)據(jù)類型定義
ADT yanshu{
數(shù)據(jù)對象：D={ai,j|ai,j屬于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 數(shù)據(jù)關系：R={ROW,COL}
ROW={
InitMaze(MazeType &maze, int a[][COL], int row, int col){
初始條件：二維數(shù)組int a[][COL],已經存在，其中第1至第m-1行，每行自第1到第n-1列的元素已經值，并以值0表示障礙，值1表示通路。
操作結果：構造迷宮的整形數(shù)組，以空白表示通路，字符‘0’表示障礙
在迷宮四周加上一圈障礙
MazePath（&maze）{
初始條件：迷宮maze已被賦值
操作結果：若迷宮maze中存在一條通路，則按如下規(guī)定改變maze的狀態(tài)；以字符‘*’表示路徑上的位置。字符‘@’表示‘死胡同’；否則迷宮的狀態(tài)不變 }
PrintMaze（M）{ 初始條件：迷宮M已存在 操作結果：以字符形式輸出迷宮 }
}ADTmaze
（3）本程序包括三個模塊
a、主程序模塊 void main(){ 初始化； 構造迷宮； 迷宮求解； 迷宮輸出； }
b、棧模塊——實現(xiàn)棧的抽象數(shù)據(jù)類型 c、迷宮模塊——實現(xiàn)迷宮的抽象數(shù)據(jù)類型
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中的每個節(jié)點調用函數(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)){ //如果當前位置可以通過,即是未曾走到的通道塊 FootPrint(maze,curpos);//留下足跡
e = CreateSElem(curstep,curpos,1);//創(chuàng)建元素 Push(s,e);if(PosEquare(curpos,end))return TRUE;curpos =NextPos(curpos,1);//獲得下一節(jié)點:當前位置的東鄰 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.首先呢，想自己讀入數(shù)據(jù)的，回來發(fā)現(xiàn)那樣，很麻煩，所以還是事先定義一個迷宮。
2.棧的元素類型 一開始有點迷惑，后來就解決了
3.本題中三個主要算法；InitMaze，MazePath和PrintMaze的時間復雜度均為O（m*n）本題的空間復雜度也是O（m*n）
五、用戶使用說明
1．本程序運行在windows系列的操作系統(tǒng)下，執(zhí)行文件為：Maze_Test.exe。
六、程序運行結果
1.建立迷宮： 2．通過1功能建立8*8的迷宮后，通過2功能繼續(xù)建立迷宮內部：
通過建立自己設定單元數(shù)目建立迷宮內墻。3．通過3功能觀察已建立的迷宮結構：
4．通過4功能確立迷宮起點和終點：
（此處像我們隨機選擇4,4和2,7分別為起點終點）
5．執(zhí)行5功能，判斷是否有路徑走出迷宮：
這種情況無法走出迷宮。
我們再次觀察圖像設4,4和1,6分別為起點終點，再運行5功能。
觀察到可以成功解開迷宮步數(shù)從1依次開始。
七、程序清單
#include
// 列值
#define MAXLENGTH 25 // 設迷宮的最大行列為25
typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宮數(shù)組[行][列]
typedef struct // 棧的元素類型
{ int ord;// 通道塊在路徑上的＂序號＂
PosType seat;// 通道塊在迷宮中的＂坐標位置＂
int di;// 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北)}SElemType;
// 全局變量
MazeType m;// 迷宮數(shù)組
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;
// 這個等式的++ * 優(yōu)先級相同，但是它們的運算方式，是自右向
(*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點的序號變?yōu)樽阚E(curstep)，表示經過 { m[a.x][a.y]=curstep;}
// 根據(jù)當前位置及移動方向，返回下一位置
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點的序號變?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)){// 當前位置可以通過，即是未曾走到過的通道塊
FootPrint(curpos);// 留下足跡
e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e);// 入棧當前位置及狀態(tài)
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 //清屏函數(shù) printf(“***************************************************nnn”);printf(“ 1請輸入迷宮的行數(shù),列數(shù)n”);printf(“ 2請輸入迷宮內墻單元數(shù)n”);printf(“ 3迷宮結構如下n”);printf(“ 4輸入迷宮的起點和終點n”);printf(“ 5輸出結果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) 網 班 -15180118-劉沛 航 } }break; case 2: {printf(“請輸入迷宮內墻單元數(shù)：”); scanf(“%d”,&j); printf(“請依次輸入迷宮內墻每個單元的行數(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(“請輸入起點的行數(shù),列數(shù)：（空格隔開）”); scanf(“%d%d”,&begin.x,&begin.y); printf(“請輸入終點的行數(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);// 輸出此通路 注意：實驗結束后提交一份實驗報告電子文檔 電子文檔命名為“學號+姓名”，如：E01214058宋思怡 《數(shù)據(jù)結構》實驗報告 （一）學號：姓名：專業(yè)年級： 實驗名稱：線性表 實驗日期：2014年4月14日 實驗目的： 1、熟悉線性表的定義及其順序和鏈式存儲結構； 2、熟練掌握線性表在順序存儲結構上實現(xiàn)基本操作的方法； 3、熟練掌握在各種鏈表結構中實現(xiàn)線性表基本操作的方法； 4、掌握用 C/C++語言調試程序的基本方法。 實驗內容： 一、編寫程序實現(xiàn)順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能： （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。 源代碼 調試分析（給出運行結果界面） 二、編寫程序實現(xiàn)單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能： ???? ???? 小結或討論: （1）實驗中遇到的問題和解決方法 （2）實驗中沒有解決的問題 （3）體會和提高 南京信息工程大學實驗（實習）報告 實驗（實習）名稱數(shù)據(jù)結構實驗（實習）日期 2011-11-2得分指導教師周素萍 系公共管理系專業(yè)信息管理與信息系統(tǒng)年級10級班次1姓名常玲學號2010230700 3實驗一順序表的基本操作及C語言實現(xiàn) 【實驗目的】 1、順序表的基本操作及 C 語言實現(xiàn) 【實驗要求】 1、用 C 語言建立自己的線性表結構的程序庫，實現(xiàn)順序表的基本操作。 2、對線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個集合的并的結果存儲在一個新的線性表集合中，并輸出。 【實驗內容】 1、根據(jù)教材定義的順序表機構，用 C 語言實現(xiàn)順序表結構的創(chuàng)建、插入、刪除、查找等操作； 2、利用上述順序表操作實現(xiàn)如下程序：建立兩個順序表表示的集合（集合中無重 復的元素），并求這樣的兩個集合的并。 【實驗結果】 [實驗數(shù)據(jù)、結果、遇到的問題及解決] 一． 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; 順序表就是把線性表的元素存儲在數(shù)組中，元素之間的關系直接通過相鄰元素的位置來表達。 優(yōu)點：簡單，數(shù)據(jù)元素的提取速度快； 缺點：（1）靜態(tài)存儲，無法預知問題規(guī)模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n） 求兩個集合的并集 該算法是求兩個集合s1和s2的并集，并將結果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數(shù)集合中得到并集。 實驗報告4 排序 一、實驗目的 1、掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。 2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用。 3、了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時間復雜度的分析方法。 二、實驗要求及內容 要求編寫的程序所能實現(xiàn)的功能包括： 1、從鍵盤輸入要排序的一組元素的總個數(shù) 2、從鍵盤依次輸入要排序的元素值 3、對輸入的元素進行快速排序 4、對輸入的元素進行折半插入排序 三、實驗代碼及相關注釋 #include 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 L.r[low] = L.r[high];//小于基準對象的移到區(qū)間的左側 while(low L.r[high] = L.r[low];//大于基準對象的移到區(qū)間的右側 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列l(wèi)ow-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<<“請輸入要排序的所有元素的總個數(shù)：”; 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] high=mid-1;//插入點在前半?yún)^(qū) else low=mid+1;//插入點在后半?yún)^(qū) } 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<<“請輸入要排序的所有元素的總個數(shù)：”;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< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函數(shù)功能說明 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的結構體，調試運行時出現(xiàn)錯誤，仔細查看才意識到Partition函數(shù)中L中應該包含元素key，而我建立結構體時沒有注意，然后我將key這個元素補充進去，繼續(xù)調試，又出現(xiàn)錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經寫了函數(shù)定義，為什么會這樣，當我又回過頭來閱讀程序時，我發(fā)現(xiàn)QuickSort函數(shù)中調用了Partition函數(shù)，但是我的Partition函數(shù)的定義在QuickSort函數(shù)的后面，于是我將Partition函數(shù)放到了QuickSort函數(shù)的前面，再次調試運行，就可以正常運行，得出結果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。 運行程序錯誤截圖： 2、本來我是編寫了兩個程序，分別實現(xiàn)快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現(xiàn)不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續(xù)思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環(huán)到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現(xiàn)所需功能的前提下，多想問題，看是否能使程序更加實用簡便。 修改程序前兩個運行結果截圖 （兩個程序，調試運行兩次，每次只能進行一次排序） 1、快速排序程序運行結果截圖： 2、折半插入排序程序結果截圖： 程序重要模塊修改截圖： 修改程序后運行截圖： （一個程序，調試運行一次，可多次進行不同序列的不同排序） 數(shù) 據(jù) 結 構 實 驗 報 告 1.問題描述 為某個單位建立一個員工通訊錄管理系統(tǒng)，可以方便地查詢每一個員工的辦公室電話號碼、手機號碼及電子郵箱。2.設計分析 在本設計中，整個通訊錄可以采用順序表或鏈表方式存儲。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除以及整個通訊錄表的輸出。3.員工通訊信息的結構類型定義和通訊錄鏈表的結點類型 typedef struct { char num[5];/*員工編號*/ char name[8];/*員工姓名*/ char phone[9];/*辦公室電話號碼*/ char call[12];/*手機號碼*/ }DataType；/*員工通訊信息的結構類型*/ typedef struct node { DataType data;/*結點的數(shù)據(jù)域*/ struct node *next;/*結點的指針域*/ }ListNode,*LinkList；/*通訊錄鏈表的結構類型*/ 4.實驗源代碼 // Address_List1.cpp : 定義控制臺應用程序的入口點。// //#include “stdafx.h” #include“stdio.h” #include “stdlib.h” # include char num[5]; /*員工編號*/ char name[8]; /*員工姓名*/ char phone[9]; /*辦公室電話號碼*/ char call[12]; /*手機號碼*/ char mail[15]; /*郵箱*/ }DataType;/*通訊錄單鏈表的結點類型*/ typedef struct node { DataType data; /*結點的數(shù)據(jù)域*/ struct node *next; /*結點的指針域*/ }LNode, *LinkList;void CreateList(LinkList &L){//逆位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L LinkList p; int i,n; L =(LinkList)malloc(sizeof(LNode)); L->next = NULL; cout <<“請輸入創(chuàng)建員工的通訊信息的個數(shù)：”; cin >> n; for(i = 0;i p =(LinkList)malloc(sizeof(LNode)); cout <<“ 請輸入員工信息”< cout <<“ 員工編號：”; cin>> p->data.num; cout <<“ 員工姓名：”; cin >> p->data.name; cout <<“辦公室電話號碼：”; cin >> p->data.phone; cout <<“ 手機號碼：”; cin >> p->data.phone; cout <<“ 員工郵箱：”; cin >> p->data.mail; cout <<“================================”<< endl; p->next = L->next; L->next = p; } } void InitList(LinkList &L){//初始化線性表 L =(LinkList)malloc(sizeof(LNode)); L->next = NULL;} void DestroyList(LinkList &L){//銷毀線性表 LinkList p, q; p = L; q = p->next; while(q!= NULL) { free(p); } } int ListEmpty(LinkList &L){//判斷線性表是否為空 if(L->next == NULL) return TRUE; else return FALSE;} int ListLength(LinkList &L){//求鏈表的長度 LinkList p = L; int c = 0; while(p->next!= NULL){ c++; p = p->next; } return(c);} void GetElem(LinkList &L){//取鏈表第i個數(shù)據(jù)元素 LinkList p = L->next; string s; cout <<“輸入員工的編號或名字:”; cin >> s; while(p!= NULL)//根據(jù)相關信息，查找員工。 { if(p->data.num == s || p->data.name == s || p->data.phone == s || p->data.call == s || p->data.mail == s) break; p = p->next; } if(!p) cout <<“查無此人!”<< endl; else{ cout <<“ 員工信息”<< endl; cout <<“ 員工編號：”<< p->data.num << endl; cout <<“ 員工姓名：”<< p->data.name << endl; cout <<“辦公室電話號碼：”<< p->data.phone << endl; cout <<“ 手機號碼：”<< p->data.phone << endl; cout <<“ 員工郵箱：”<< p->data.mail << endl; cout <<“================================”<< endl; } } void ReviseList(LinkList &L)//修改信息 { LinkList p = L->next; char j[20]; string s; int i; cout <<“輸入員工的編號或名字:”; cin >> s; while(p!= NULL){//根據(jù)相關信息，查找員工。 if(p->data.num == s || p->data.name == s || p->data.phone == s || p->data.call == s || p->data.mail == s) break; p = p->next; } if(!p) cout <<“查無此人!”<< endl; else { cout <<“n想修改什么信息？_1-編號 2-姓名 3-辦公室電話號碼 4-手機號碼 5-郵箱”<< endl; cin >> i; cout <<“想修改成什么？”<< endl; cin >> j; switch(i){ case 1:strcpy(p->data.num, j);break; case 2:strcpy(p->data.name, j);break; case 3:strcpy(p->data.phone, j);break; case 4:strcpy(p->data.call, j);break; case 5:strcpy(p->data.mail, j);break; default: cout <<“輸入錯誤，”<< endl; system(“pause”); } cout <<“修改完畢！”; system(“pause”); return; } } void ListDelete(LinkList &L)//刪除第i個元素 { LinkList p, q; int j = 0,i;p = L; cout <<“請輸入你要刪除第幾個員工的信息：”; cin >> i; while(p->next && j < i1)//刪除位置不合理 cout <<“刪除位置不合理”<< endl; q = p->next; p->next = q->next;//刪除并釋放結點 free(q);} void ListInsert(LinkList &L){ LinkList s, p = L; s =(LinkList)malloc(sizeof(LNode)); cout <<“ 請輸入員工信息”<< endl; cout <<“ 員工編號：”; cin >> s->data.num; cout <<“ 員工姓名：”; cin >> s->data.name; cout <<“辦公室電話號碼：”; cin >> s->data.phone; cout <<“ 手機號碼：”; cin >> s->data.phone; cout <<“ 員工郵箱：”; cin >> s->data.mail; cout <<“================================”<< endl; s->next = p->next; p->next = s;} void PrintList(LinkList &L)//打印線性表 { LinkList p = L->next; int i = 1; if(p == NULL) cout <<“通訊錄為空！”<< endl; while(p!= NULL) { cout <<“第 ”< cout <<“ 員工編號：”<< p->data.num << endl; cout <<“ 員工姓名：”<< p->data.name << endl; cout <<“辦公室電話號碼：”<< p->data.phone << endl; cout <<“ 手機號碼：”<< p->data.phone << endl; cout <<“ 員工郵箱：”<< p->data.mail << endl; cout <<“==============================”<< endl; p = L; cout <<“請輸入你要刪除第幾個員工的信息：”; cin >> i; while(p->next && j < i1)//刪除位置不合理 cout <<“刪除位置不合理”<< endl; q = p->next; p->next = q->next;//刪除并釋放結點 free(q);} void ListInsert(LinkList &L){ LinkList s, p = L; s =(LinkList)malloc(sizeof(LNode)); cout <<“ 請輸入員工信息”<< endl; cout <<“ 員工編號：”; cin >> s->data.num; cout <<“ 員工姓名：”; cin >> s->data.name; cout <<“辦公室電話號碼：”; cin >> s->data.phone; cout <<“ 手機號碼：”; cin >> s->data.phone; cout <<“ 員工郵箱：”; cin >> s->data.mail; cout <<“================================”<< endl; s->next = p->next; p->next = s;} void PrintList(LinkList &L)//打印線性表 { LinkList p = L->next; int i = 1; if(p == NULL) cout <<“通訊錄為空！”<< endl; while(p!= NULL) { cout <<“第 ”< cout <<“ 員工編號：”<< p->data.num << endl; cout <<“ 員工姓名：”<< p->data.name << endl; cout <<“辦公室電話號碼：”<< p->data.phone << endl; cout <<“ 手機號碼：”<< p->data.phone << endl; cout <<“ 員工郵箱：”<< p->data.mail << endl; cout <<“==============================”<< endl;break; case 4: //添加 ListInsert(L); cout <<“添加信息成功！”; system(“pause”); break; case 5: PrintList(L); ListDelete(L); cout <<“刪除信息成功！”; system(“pause”); break;//輸出全部信息 case 6: PrintList(L); system(“pause”); break; case 7: cout <<“該通訊錄共有 ”<< ListLength(L)<<“ 員工信息！”<< endl;; system(“pause”); break; default: cout <<“輸入錯誤!”<< endl; system(“pause”); } } while(in!= 0);} 5.實驗截圖.第二篇：數(shù)據(jù)結構實驗報告
第三篇：數(shù)據(jù)結構實驗報告
第四篇：數(shù)據(jù)結構實驗報告
第五篇：數(shù)據(jù)結構實驗報告
點擊咨詢 