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

1、.實(shí) 驗(yàn) 報(bào) 告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目名稱1單鏈表的實(shí)現(xiàn)與應(yīng)用2堆棧的實(shí)現(xiàn)與應(yīng)用3排序、查找算法的實(shí)現(xiàn)與應(yīng)用實(shí)驗(yàn)類型基本型 / 基本型 / 綜合型實(shí)驗(yàn)學(xué)時(shí)2 / 2 / 4班級(jí)學(xué)號(hào)姓名指導(dǎo)教師實(shí)驗(yàn)室名稱實(shí)驗(yàn)時(shí)間20171127 / 1127 / 1204實(shí)驗(yàn)成績(jī)編號(hào)過程表現(xiàn)預(yù)習(xí)部分實(shí)驗(yàn)報(bào)告小計(jì)總成績(jī)123教師簽字日期哈爾濱工程大學(xué)本科生院制實(shí)驗(yàn)1 單鏈表的實(shí)現(xiàn)與應(yīng)用-【預(yù)習(xí)部分】一、實(shí)驗(yàn)?zāi)康耐ㄟ^編程實(shí)驗(yàn)，進(jìn)一步增強(qiáng)對(duì)單鏈表的理解和掌握。二、實(shí)驗(yàn)要求編寫程序?qū)崿F(xiàn)單鏈表的基本操作（初始化、撤銷、插入、刪除、取數(shù)據(jù)元素、求數(shù)據(jù)元素個(gè)數(shù)），并設(shè)計(jì)測(cè)試數(shù)據(jù)，能全面地測(cè)試所設(shè)計(jì)程序的功能。三、實(shí)驗(yàn)原理1

2、.單鏈表結(jié)構(gòu)線性表是一種可以在任意位置插入和刪除數(shù)據(jù)元素操作、由n(n0)個(gè)相同類型數(shù)據(jù)元素a0, a1, an-1組成的線性結(jié)構(gòu)。單鏈表是線性表的一種。而單鏈表中構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針域。其結(jié)構(gòu)特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。2.單鏈表數(shù)據(jù)插入原理要在帶頭結(jié)點(diǎn)的單鏈表第i（0 i size）個(gè)結(jié)點(diǎn)前插入一個(gè)存放數(shù)據(jù)元素x的結(jié)點(diǎn)，首先要在單鏈表中尋找到第i-1個(gè)結(jié)點(diǎn)并由指針p指示，然后動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)點(diǎn)存儲(chǔ)空間并由指針q指示，并把數(shù)據(jù)元素x的值賦予新結(jié)點(diǎn)的數(shù)據(jù)元素域（即q-data = x），最后修改新結(jié)點(diǎn)的指針域指向ai結(jié)點(diǎn)（即q-next = p-next

3、），并修改ai-1結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)q（即p-next = q）。循環(huán)條件由兩個(gè)子條件邏輯與組成，其中子條件p-next != NULL保證指針?biāo)附Y(jié)點(diǎn)存在，子條件j next），并把數(shù)據(jù)元素ai的值賦予x（即*x = s-data），最后把a(bǔ)i結(jié)點(diǎn)脫鏈（即p-next = p-next-next），并動(dòng)態(tài)釋放ai結(jié)點(diǎn)的存儲(chǔ)空間（即free(s)）。刪除過程如圖2-14所示。圖中的對(duì)應(yīng)算法中的刪除語句。四、實(shí)驗(yàn)環(huán)境Visual Studio 2010-五、實(shí)驗(yàn)步驟（程序代碼）/ 5555.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)/#include stdafx.hint _tmain(int

4、 argc, _TCHAR* argv)return 0;#include #include #include typedef int DataType;typedef struct Node DataType data; struct Node *next; SLNode;void ListInitiate(SLNode *head) *head = (SLNode *)malloc(sizeof(SLNode);(*head)-next = NULL;void Destroy(SLNode *head) SLNode *p, *p1;p = *head; while(p != NULL)

5、p1 = p; p = p-next;free(p1); *head = NULL;int ListInsert(SLNode *head, int i, DataType x) SLNode *p, *q; int j;p = head; j = -1; while(p-next != NULL & j next; j+; if(j != i - 1) printf(插入位置參數(shù)錯(cuò)！);return 0; q = (SLNode *)malloc(sizeof(SLNode); q-data = x; q-next = p-next; p-next = q; return 1;int Lis

6、tDelete(SLNode *head, int i, DataType *x) SLNode *p, *s; int j;p = head; j = -1; while(p-next != NULL & p-next-next!= NULL & j next;j+; if(j != i - 1)printf(插入位置參數(shù)錯(cuò)！);return 0;s = p-next; *x = s-data; p-next = p-next-next; free(s); return 1;int ListGet(SLNode *head, int i, DataType *x) SLNode *p; in

7、t j;p = head; j = -1; while(p-next != NULL & j next;j+; if(j != i) printf(取元素位置參數(shù)錯(cuò)！);return 0; *x = p-data; return 1; int ListLength(SLNode *head)SLNode *p = head;int size = 0;while(p-next != NULL)p = p-next;size +;return size; void main(void) SLNode *head; int i , x;ListInitiate(&head); for(i = 0;

8、i 10; i+) ListInsert(head, i, i+1) ; for(i = 0; i ListLength(head); i+) ListGet(head, i, &x); printf(%d , x); printf(n, x); ListDelete(head, 6, &x) ; for(i = 0; i ListLength(head); i+) ListGet(head, i, &x); printf(%d , x); Destroy(&head); 六、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果如下：主程序?qū)崿F(xiàn)的功能為：建立一個(gè)線性表，首先依次輸入數(shù)據(jù)元素1，2，3，10，然后刪除數(shù)據(jù)元素7，最

9、后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。由實(shí)驗(yàn)結(jié)果可知，實(shí)驗(yàn)程序正確執(zhí)行了功能。七、分析與總結(jié)單鏈表和順序表相比，主要優(yōu)點(diǎn)是不需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除操作不需要移動(dòng)數(shù)據(jù)元素；主要缺點(diǎn)是查找數(shù)據(jù)元素時(shí)需要順序進(jìn)行，不能像順序表那樣隨機(jī)查找任意一個(gè)數(shù)據(jù)元素。另外，每個(gè)結(jié)點(diǎn)中要有一個(gè)指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復(fù)雜。經(jīng)過本次實(shí)驗(yàn)，我掌握了單鏈表的基本操作初始化、撤銷、插入、刪除、取數(shù)據(jù)元素、求數(shù)據(jù)元素個(gè)數(shù)等，提高了自己的編程能力。實(shí)驗(yàn)2 堆棧的實(shí)現(xiàn)與應(yīng)用-【預(yù)習(xí)部分】一、實(shí)驗(yàn)?zāi)康耐ㄟ^編程實(shí)驗(yàn)，進(jìn)一步增強(qiáng)對(duì)堆棧的理解和掌握。二、實(shí)驗(yàn)要求編寫程序?qū)崿F(xiàn)順序堆棧的基本

10、操作（初始化、非空否、入棧、出棧、取棧頂數(shù)據(jù)元素），并設(shè)計(jì)測(cè)試數(shù)據(jù)，能全面地測(cè)試所設(shè)計(jì)程序的功能。三、實(shí)驗(yàn)原理1.順序堆棧結(jié)構(gòu)堆棧定義為限定只能在固定一端進(jìn)行插入和刪除操作的線性表。其特點(diǎn)是后進(jìn)先出。允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。它的作用是可以完成從輸入數(shù)據(jù)序列到某些輸出數(shù)據(jù)序列的轉(zhuǎn)換。順序堆棧是順序存儲(chǔ)結(jié)構(gòu)的堆棧。順序棧的存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。2.數(shù)據(jù)集合a0,a1,an-1ai的數(shù)據(jù)類型為DataType。3操作集合 (1) StackInitiate(S) ：初始化堆棧 (2) StackNotEmpty(S)：堆棧S

11、非空否 (3) StackPush(S, x) ：入棧 (4) StackPop(S, d)：出棧 (5) StackTop(S, d)：取棧頂數(shù)據(jù)元素四、實(shí)驗(yàn)環(huán)境Visual Studio 2010-五、實(shí)驗(yàn)步驟（程序代碼）/ 5555.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)/#include stdafx.h int _tmain(int argc, _TCHAR* argv)return 0;#include #include #define MaxStackSize 100typedef int DataType;typedef struct DataType stackMaxStac

12、kSize; int top; SeqStack;void StackInitiate(SeqStack *S)S-top = 0;int StackNotEmpty(SeqStack S) if(S.top top = MaxStackSize) printf(堆棧已滿無法插入！n); return 0; else S-stackS-top = x; S-top +; return 1; int StackPop(SeqStack *S, DataType *d) if(S-top top -;*d = S-stackS-top; return 1; int StackTop(SeqStac

13、k S, DataType *d) if(S.top = 0) printf(堆棧已空!n); return 0; else *d = S.stackS.top - 1; return 1; void main(void) SeqStack myStack; int i , x; StackInitiate(&myStack); for(i = 0; i = 20）；（2）編程實(shí)現(xiàn)一種排序算法，對(duì)這N個(gè)數(shù)據(jù)進(jìn)行遞增排序；（3）編程實(shí)現(xiàn)一種查找算法，在已排序的數(shù)據(jù)序列中查找指定數(shù)據(jù)。 三、實(shí)驗(yàn)原理1.排序原理排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過程,是把一個(gè)數(shù)據(jù)元素序列整理成按關(guān)鍵字遞增（或遞

14、減）排列的過程。主要有以下幾種排序方法：交換排序的基本思想是利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。插入排序的基本思想是每步將一個(gè)待排序的數(shù)據(jù)元素，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組數(shù)據(jù)元素的適當(dāng)位置上，直到數(shù)據(jù)元素全部插入為止。選擇排序的基本思想是是每次從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最?。ɑ蜃畲螅┑臄?shù)據(jù)元素放到數(shù)據(jù)元素集合的最前（或最后），數(shù)據(jù)元素集合不斷縮小，當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序結(jié)束。歸并排序主要是二路歸并排序,基本思想是可以把一個(gè)長(zhǎng)度為n 的無序序列看成是 n 個(gè)長(zhǎng)度為 1 的有序子序列 ，首先做兩兩歸并，得到 n / 2 個(gè)長(zhǎng)度為 2 的有序子序列 ；再做兩兩歸并，如

15、此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為 n 的有序序列。2.查找原理查找是查詢某個(gè)關(guān)鍵字是否在(數(shù)據(jù)元素集合）表中的過程，也稱作檢索。常用的一種算法為二分查找（又稱折半查找）。算法的基本思想是先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素值相比，若key小，則縮小至前半部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。反之，如果key大，則縮小至后半部?jī)?nèi)查找。四、實(shí)驗(yàn)環(huán)境Visual Studio 2010-五、實(shí)驗(yàn)步驟（程序代碼）/ paixu.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include #include

16、int b20;int SelectSort(int b, int n)int i, j, small;int temp;for(i = 0; i n-1; i+) small = i; /設(shè)第i個(gè)數(shù)據(jù)元素關(guān)鍵字最小 for(j = i+1; j n; j+)/尋找關(guān)鍵字最小的數(shù)據(jù)元素 if(bj bsmall) small=j; /記住最小元素的下標(biāo) if(small != i)/當(dāng)最小元素的下標(biāo)不為i時(shí)交換位置 temp = bi; bi = bsmall; bsmall = temp; for(i=0;in;i+)printf(%d,bi);printf( );return 1;int

17、BiSearch(int b, int n, int key) int low = 0, high = n - 1;/確定初始查找區(qū)間上下界 int mid;while(low = high) mid = (low + high)/2;/確定查找區(qū)間中心下標(biāo) if(bmid = key) return 1;/查找成功 else if(bmid key) low = mid + 1; else high = mid - 1; return 0;/查找失敗int random(int n)int i,a;srand(unsigned int)time(NULL); /當(dāng)前時(shí)間作種子，每次都不同for(i=0;i= 20）、對(duì)這N個(gè)數(shù)據(jù)進(jìn)行遞增排序并在已排序的數(shù)據(jù)序列中查找指定數(shù)據(jù)。 七、分析與總結(jié)交換排序的基本思想是利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。交換排序主要包括冒泡排序和快速排序兩種。我在實(shí)驗(yàn)中采用的是冒泡排序的算法，其基本思想是每趟不斷將數(shù)據(jù)元素兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。這種排序方法的優(yōu)點(diǎn)是每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟