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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)四學(xué)院：自動(dòng)化學(xué)院班級(jí)：_學(xué)號(hào)：_姓名：_ _一、實(shí)驗(yàn)?zāi)康?1、熟悉VC環(huán)境，學(xué)習(xí)使用C語(yǔ)言實(shí)現(xiàn)鏈表的存儲(chǔ)結(jié)構(gòu)。2、通過(guò)編程、上機(jī)調(diào)試，進(jìn)一步理解線(xiàn)性表、鏈表、環(huán)表的基本概念。3、鍛煉動(dòng)手編程，獨(dú)立思考的能力。二、實(shí)驗(yàn)內(nèi)容 從鍵盤(pán)輸入10個(gè)數(shù)，編程實(shí)現(xiàn)分別用插入排序、交換排序、選擇排序算法進(jìn)行排序，輸出排序后的序列。三、程序設(shè)計(jì) 1、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，應(yīng)用線(xiàn)性表寄存數(shù)字序列。為此，需要線(xiàn)性表的抽象數(shù)據(jù)結(jié)構(gòu)。(1)、線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義為：ADT SqList 數(shù)據(jù)對(duì)象：D=數(shù)據(jù)關(guān)系：R1= 基本操作：CreateList(&

2、amp;L)操作結(jié)果：構(gòu)造一個(gè)線(xiàn)性表L。ShowList(&L)初始條件：線(xiàn)性表L已存在。操作結(jié)果：按順序在屏幕上輸出L的數(shù)據(jù)元素。InsertSort(&L)初始條件：線(xiàn)性表L已存在。操作結(jié)果：對(duì)L的數(shù)據(jù)元素進(jìn)行插入排序。QuickSort(&L)初始條件：線(xiàn)性表L已存在。操作結(jié)果：對(duì)L的數(shù)據(jù)元素進(jìn)行快速排序。SelectSort(&L)初始條件：線(xiàn)性表L已存在。操作結(jié)果：對(duì)L的數(shù)據(jù)元素進(jìn)行選擇排序。ADT SqList (2)、宏定義#define MAXSIZE 10#define OVERFLOW -2#define OK 1#define ERROR

3、0#define TRUE 1#define FALSE 0 (3)、主程序流程主程序首先調(diào)用CreateList(l1)函數(shù)創(chuàng)建順序表l1。隨后調(diào)用InsertSort(l1)、QuickSort(l2)、SelectSort(l3)函數(shù)計(jì)算三種排序結(jié)果，并調(diào)用相應(yīng)的ShowList()函數(shù)顯示排序結(jié)果。(4)、模塊調(diào)用關(guān)系：由主函數(shù)模塊調(diào)用創(chuàng)建模塊，顯示模塊與計(jì)算模塊。(5)、流程圖開(kāi)始創(chuàng)建線(xiàn)性表排序輸出結(jié)果結(jié)束 2、詳細(xì)設(shè)計(jì) (1)、數(shù)據(jù)類(lèi)型設(shè)計(jì)typedef int Status;typedef int ElemType; /定義數(shù)據(jù)元素類(lèi)型typedef structElemType

4、 rMAXSIZE+1;int length;SqList; /定義順序表類(lèi)型(2)、操作算法設(shè)計(jì)Status CreateList(SqList &L)/創(chuàng)建順序表L.length=0;for(int i=1;i<=MAXSIZE;i+)scanf("%d",&L.ri);L.length+;return OK;Status ShowList(SqList &L)/顯示順序表的內(nèi)容for(int i=1;i<=MAXSIZE;i+)printf("%d ",L.ri);return OK;void InsertSor

5、t(SqList &L)/插入排序for(int i=2;i<=L.length;+i)if(L.ri<L.ri-1) /需將L.ri插入有序子表L.r0=L.ri; /復(fù)制為哨兵L.ri=L.ri-1;for(int j=i-2;L.r0<L.rj;-j)L.rj+1=L.rj; /記錄后移L.rj+1=L.r0; /插入到正確位置int Partition(SqList &L, int low, int high)/一趟快速排序L.r0=L.rlow; /用子表第一個(gè)記錄做樞軸元素int pivotkey=L.rlow; /樞軸記錄關(guān)鍵字while(low

6、<high) /從兩端交替向中間掃描while(low<high && L.rhigh>=pivotkey) -high;L.rlow=L.rhigh; /將記錄小的移到低端while(low<high && L.rlow<=pivotkey) +low;L.rhigh=L.rlow; /將記錄大的移到高端 L.rlow=L.r0; /樞軸記錄到位return low; /返回樞軸位置void QSort(SqList &L,int low,int high)/對(duì)low,high做快速排序if(low<high) /長(zhǎng)

7、度大于1int pivotloc=Partition(L,low,high); /一分為二QSort(L,low,pivotloc-1); /對(duì)低子表遞歸排序QSort(L,pivotloc+1,high); /對(duì)高子表遞歸排序void QuickSort(SqList &L)/對(duì)L快速排序QSort(L,1,L.length);void SelectSort(SqList &L)/對(duì)L選擇排序for(int i=1;i<L.length;+i) /選擇第i小記錄并交換到位int k=i;for(int j=i+1;j<=L.length;j+) if(L.rj&l

8、t;L.rk)k=j; if(k!=i) L.r0=L.ri;L.ri=L.rk;L.rk=L.r0; /與第i個(gè)元素交換 (3)、主函數(shù)設(shè)計(jì)int main()/主程序SqList l1,l2,l3;printf("Please input 10 numbers:n");CreateList(l1); /創(chuàng)建線(xiàn)性表l1 l2=l1; l3=l1;InsertSort(l1); /對(duì)l1插入排序printf("The result of InsertSort is:n");ShowList(l1);printf("n");QuickS

9、ort(l2); /對(duì)l2快速排序printf("The result of QuickSort is:n");ShowList(l2);printf("n");SelectSort(l3); /對(duì)l3選擇排序printf("The result of SelectSort is:n");ShowList(l3);printf("n");return 0;四、程序調(diào)試分析 1、由于對(duì)于快速排序理解不深，開(kāi)始時(shí)出現(xiàn)了許多細(xì)節(jié)問(wèn)題，導(dǎo)致排序結(jié)果不正常，經(jīng)過(guò)修改后得以解決。2、在選擇排序中，由于不細(xì)心，誤將”<”打

10、為”<=”導(dǎo)致結(jié)果不正常。3、在快速排序中，一些后引入的變量，例如pivotkey沒(méi)有聲明，導(dǎo)致編譯失敗。五、用戶(hù)使用說(shuō)明 1、本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：Sort.exe。2、進(jìn)入程序后，在Please input 10 numbers:后輸入所需排序的十個(gè)整數(shù)，回車(chē)運(yùn)行程序。 3、程序運(yùn)行后即在屏幕上輸出計(jì)算結(jié)果。六、程序運(yùn)行結(jié)果1、2、七、程序清單#define MAXSIZE 10#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#include"std

11、io.h"#include"stdlib.h"typedef int Status;typedef int ElemType; /定義數(shù)據(jù)元素類(lèi)型typedef structElemType rMAXSIZE+1;int length;SqList; /定義順序表類(lèi)型Status CreateList(SqList &L)/創(chuàng)建順序表L.length=0;for(int i=1;i<=MAXSIZE;i+)scanf("%d",&L.ri);L.length+;return OK;Status ShowList(SqLis

12、t &L)/顯示順序表的內(nèi)容for(int i=1;i<=MAXSIZE;i+)printf("%d ",L.ri);return OK;void InsertSort(SqList &L)/插入排序for(int i=2;i<=L.length;+i)if(L.ri<L.ri-1) /需將L.ri插入有序子表L.r0=L.ri; /復(fù)制為哨兵L.ri=L.ri-1;for(int j=i-2;L.r0<L.rj;-j)L.rj+1=L.rj; /記錄后移L.rj+1=L.r0; /插入到正確位置int Partition(SqLis

13、t &L, int low, int high)/一趟快速排序L.r0=L.rlow; /用子表第一個(gè)記錄做樞軸元素int pivotkey=L.rlow; /樞軸記錄關(guān)鍵字while(low<high) /從兩端交替向中間掃描while(low<high && L.rhigh>=pivotkey) -high;L.rlow=L.rhigh; /將記錄小的移到低端while(low<high && L.rlow<=pivotkey) +low;L.rhigh=L.rlow; /將記錄大的移到高端 L.rlow=L.r0; /

14、樞軸記錄到位return low; /返回樞軸位置void QSort(SqList &L,int low,int high)/對(duì)low,high做快速排序if(low<high) /長(zhǎng)度大于1int pivotloc=Partition(L,low,high); /一分為二QSort(L,low,pivotloc-1); /對(duì)低子表遞歸排序QSort(L,pivotloc+1,high); /對(duì)高子表遞歸排序void QuickSort(SqList &L)/對(duì)L快速排序QSort(L,1,L.length);void SelectSort(SqList &L)

15、/對(duì)L選擇排序for(int i=1;i<L.length;+i) /選擇第i小記錄并交換到位int k=i;for(int j=i+1;j<=L.length;j+) if(L.rj<L.rk)k=j; if(k!=i) L.r0=L.ri;L.ri=L.rk;L.rk=L.r0; /與第i個(gè)元素交換int main()/主程序SqList l1,l2,l3;printf("Please input 10 numbers:n");CreateList(l1); /創(chuàng)建線(xiàn)性表l1 l2=l1; l3=l1;InsertSort(l1); /對(duì)l1插入排序printf("The result of InsertSort is:n");ShowList(l1);printf("n&