數(shù)據(jù)結(jié)構(gòu)線性表試驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱實(shí)驗(yàn)一 線性表學(xué)號(hào)姓名實(shí)驗(yàn)日期：實(shí)驗(yàn)一線性表實(shí)驗(yàn)?zāi)康模?. 理解線性表的邏輯結(jié)構(gòu)特性；2. 熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的描述方法，以及在該存儲(chǔ)結(jié)構(gòu)下的基本操作；并能靈活運(yùn)用；3. 熟練掌握線性表的鏈表存儲(chǔ)結(jié)構(gòu)的描述方法，以及在該存儲(chǔ)結(jié)構(gòu)下的基本操作；并能靈活運(yùn)用；4. 掌握雙向鏈表和循環(huán)鏈表的的描述方法，以及在該存儲(chǔ)結(jié)構(gòu)下的基本操作。實(shí)驗(yàn)原理：線性表順序存儲(chǔ)結(jié)構(gòu)下的基本算法；線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的基本算法；實(shí)驗(yàn)內(nèi)容：2 21設(shè)計(jì)單循環(huán)鏈表，要求：(1) 單循環(huán)鏈表抽象數(shù)據(jù)類型包括初始化操作、求數(shù)據(jù)元素個(gè)數(shù)操作、插入操作、刪 除操作、取消數(shù)據(jù)元素操作和判非空操作。(

2、2) 設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證所設(shè)計(jì)單循環(huán)鏈表的正確性。2 22 .設(shè)計(jì)一個(gè)有序順序表，要求：(1) 有序順序表的操作集合有如下操作：初始化、求數(shù)據(jù)元素個(gè)數(shù)、插入、刪除和取數(shù)據(jù)元素。有序順序表與順序表的主要區(qū)別是：有序順序表中的數(shù)據(jù)元素按數(shù)據(jù)元素值非遞減有序。(2) 設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證所設(shè)計(jì)有序順序表的正確性。(3) 設(shè)計(jì)合并函數(shù)ListMerge (L1,L2,L3 )，功能是把有序順序表 L1和L2中的數(shù)據(jù)元 素合并到L3,要求L3中的數(shù)據(jù)元素依然保持有序。 并設(shè)計(jì)一個(gè)主函數(shù)， 驗(yàn)證該合并函數(shù)的 正確性。程序代碼：2 - 21 (1)頭文件 LinList.h 如下：

3、typedef struct node(DataType data;struct node *next;SLNode;/* (1)初始化 ListInitiate(SLNode * * head)*/void ListInitiate(SLNode * * head)( /*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/if(*head=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1);(*head)->next=NULL; /* 置結(jié)束標(biāo)記 NULL*/*(2)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)ListLength(SLNode * head)*

4、/int ListLength(SLNode * head)(SLNode *p=head;int size=0;while(p->next!=head)(p=p->next;size+;return size;/*(3)插入 ListInsert(SLNode * head , int i, DataType x)*/*在帶頭結(jié)點(diǎn)的單鏈表的第i(0<=i<=size)個(gè)結(jié)點(diǎn)前*/*插入一個(gè)存放數(shù)據(jù)元素x的結(jié)點(diǎn)。插入成功時(shí)返回 1,失敗返回0*/int ListInsert(SLNode * head, int i, DataType x)(SLNode *p, *q;

5、int j;p=head;j=-1;while(p->next!=head && j<i-1)/*最終讓指針指向第i-1個(gè)結(jié)點(diǎn)*/(p=p->next;j+;if(j!=i-1)(printf("The inserted position is error!");return 0;/*生成新結(jié)點(diǎn)由指針q指示*/if(q=(SLNode *)malloc(sizeof(SLNode)=NULL) exit(1); q->data=x;q->next=p->next;p->next=q;return 1;/*(4)刪除

6、ListDelete(SLNode * head , int i, DataType *x) */*刪除帶頭結(jié)點(diǎn)的單鏈表head的第i(0<=i<=size)個(gè)結(jié)點(diǎn)前*/*被刪除結(jié)點(diǎn)的數(shù)據(jù)元素域由x帶回。刪除成功時(shí)返回1,失敗返回0*/int ListDelete(SLNode * head, int i, DataType *x)SLNode *p, *s;int j;p=head;j=-1;while(p->next!=head && p->next->next!=head && j<i-1)/*最終讓指針指向第i-1個(gè)結(jié)

7、點(diǎn)*/p=p->next;j+;if(j!=i-1)printf("The deleted position of parameter is error!");return 0;s=p->next; /*指針s指指向ai結(jié)點(diǎn)*/*x=s->data;p->next=p->next->next; /* 刪除 */free(s); /*釋放指針s所指結(jié)點(diǎn)的內(nèi)存空間*/return 1;/*(5)取數(shù)據(jù)元素 ListGet(SLNode * head , int i, DataType *x)*/int ListGet(SLNode * hea

8、d, int i, DataType *x) SLNode *p;int j;p=head;j=-1；while(p->next!=head && j<i)(p=p->next;j+;if(j!=i)(printf("The gotten position of parameter is error!");return 0; *x=p->data;return 1;/*(6)撤銷單鏈表 Destroy(SLNode * * head)*/void Destroy(SLNode * * head) (SLNode *p, *p1;p=*

9、head;while(p!=NULL)(p1=p;p=p->next;free(p1);*head=NULL;/*包含printf()函數(shù)*/*包含exit()函數(shù)*/*包含 malloc()函數(shù)*/* 定義 DataType 為 int*/*包含單鏈表的頭文件*/(2)測(cè)試主函數(shù)如下：#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef int DataType;#include "LinList.h"void main(void)/*定義頭指針變量*/SL

10、Node *head;int i, x;ListInitiate(&head); /* 初始化 */for(i=0;i<10;i+)/* 插入 10 個(gè)數(shù)據(jù)元素 */(if(ListInsert(head, i, i+1)=0) (printf("error!n");return;if(ListDelete(head, 4, &x)=0) /*(printf("error!n");return;for(i=0; i<ListLength(head); i+)(if(ListGet(head, i, &x)=0)(pri

11、ntf("error!n");return;elseprintf("%d ", x);Destroy(&head);2 - 22設(shè)計(jì)一個(gè)有序順序表頭文件程序如下：#define NULL 0typedef struct(DataType ListMaxSize;int size;SeqList;刪除第四個(gè)數(shù)據(jù)元素*/*顯示當(dāng)前數(shù)據(jù)元素*/*取數(shù)據(jù)元素*/*顯示*/*撤銷單鏈表*/void listInitiate(SeqList *L)/*初始化順序表L */L->size=0;/*定義初始化數(shù)據(jù)元素個(gè)數(shù)*/void main(void)i

12、nt ListLength(SeqList L)(return L.size;int ListInsert(SeqList *L, int i, DataType x)(int j;if (L->size>=MaxSize)(printf("順序表已滿無(wú)法插入！n");return 0;else if (i<0|i>L->size)(printf("參數(shù)i不合法！ n");return 0;else(for(j=L->size; j>i; j-)L->Listj=L->Listj-1;L->Li

13、sti=x;L->size+;return 1;int ListDelete(SeqList *L, int i, DataType *x)(int j;if(L->size<=0)(printf("順序表已空無(wú)數(shù)據(jù)元素可刪！n");return 0;else if(i<0|i>L->size-1)(printf("參數(shù)i不合法！ n");return 0;else(*x=L->Listi;for(j=i+1; j<L->size-1;j+)L->Listj-1=L->Listj;L-&g

14、t;size-;return 1;int ListGet(SeqList L, int i, DataType *x)if(i<0|i>L.size-1)printf("參數(shù)i不合法！ n");return 0;else*x=L.Listi;return 1;/*測(cè)試主函數(shù)設(shè)計(jì)如下：*/#include<stdio.h>#define MaxSize 100typedef int DataType;#include "SeqList.h"int SLOrderInsert(SeqList *L,DataType x)int j;i

15、f(L->size>=MaxSize-1 )printf("順序表已滿無(wú)法插入!n");return 0;for(j=L->size-1;j>0&& x<L->listj;j-)L->listj+1=L->listj;L->listj+1=x;L->size+;return 1;SeqList MyList;int a=1,2,4,5,6,8,9;/*數(shù)組a中的數(shù)據(jù)元素遞增有序*/int i,n=7;int x;ListInitiate(&MyList);for(i=0;i<n+1;i+)ListInitiate(&MyList);SLOrderInsert(&MyList,ai);for(i=0;i<n+1;i+)ListGet(MyList,i,x);printf("%d”,ai);實(shí)驗(yàn)結(jié)果：(1) 2-21運(yùn)行結(jié)果如下:e F:shiijnTC2TC, ESE回(2) 2-22運(yùn)行結(jié)果如下:R F:shujuTC2TC_EXE 12456