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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1、學(xué)校：安徽大學(xué)2、實(shí)驗(yàn)名稱(chēng)：線性表的基本操作的實(shí)現(xiàn)3、姓名：王勇4、學(xué)號(hào)：E010143675、專(zhuān)業(yè)：10級(jí)網(wǎng)絡(luò)工程6、實(shí)驗(yàn)完成時(shí)間：2012年4月5日一實(shí)驗(yàn)?zāi)康模?1熟練掌握線性表的基本操作在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)上的實(shí)現(xiàn)。 2以線性表的各種操作(建立、插入、刪除、遍歷等)的實(shí)現(xiàn)為重點(diǎn)。 3通過(guò)本章實(shí)驗(yàn)加深對(duì)c語(yǔ)言的使用(特別是函數(shù)的參數(shù)調(diào)用、指針類(lèi)型的應(yīng)用和鏈表的建立等各種基本操作)。二、實(shí)驗(yàn)內(nèi)容：1.順序表的基本操作的實(shí)現(xiàn).包括:(1) 順序表的類(lèi)型定義；(2) 創(chuàng)建一個(gè)元素為1，10，9，5的順序表；(3) 向（2）中表的指定位置插入一個(gè)元素；(4) 刪除（3）中順序表

2、中指定位置的元素；(5) 依次輸出（2）（4）順序表中的元素；2.鏈表的基本操作的實(shí)現(xiàn).包括:(1) 鏈表的類(lèi)型定義；(2) 創(chuàng)建一個(gè)元素為5，-4，9，10，3的鏈表；(3) 向（2）表中指定位置插入一個(gè)元素；(4) 刪除（3）表中指定位置的元素；(5) 依次輸出（2）（4）表中的元；三、實(shí)驗(yàn)步驟：1、本實(shí)驗(yàn)用到的數(shù)據(jù)結(jié)構(gòu)（1）邏輯結(jié)構(gòu)：線性結(jié)構(gòu)（2）存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)（順序表）和非順序存儲(chǔ)結(jié)構(gòu)（單鏈表）2、各程序的功能和算法設(shè)計(jì)思想程序一：#include#include#include#define LIST_INIT_SIZE 50#define LISTINCREMENT 5#d

3、efine OK 1#define ERROR 0#define OVERFLOW -2typedef char ElemType;typedef int Status; typedef struct ElemType *elem; int length; int listsize;SqList;void InitListSq(SqList *L) / 算法.3 / 構(gòu)造一個(gè)空的線性表L。 (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!(*L).elem) exit(OVERFLOW); / 存儲(chǔ)分配失

4、敗 (*L).length = 0; / 空表長(zhǎng)度為 (*L).listsize = LIST_INIT_SIZE; / 初始存儲(chǔ)容量 /return L; / InitList_SqStatus ListInsertSq(SqList *L, int i, ElemType e) / 在順序線性表L的第i個(gè)元素之前插入新的元素e， / i的合法值為iListLength_Sq(L)+1 ElemType *p; if (i (*L).length+1) return ERROR; / i值不合法 if (*L).length = (*L).listsize) / 當(dāng)前存儲(chǔ)空間已滿(mǎn)，增加容量

5、ElemType *newbase = (ElemType *)realloc(*L).elem, (*L).listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) return ERROR; / 存儲(chǔ)分配失敗 (*L).elem = newbase; / 新基址 (*L).listsize += LISTINCREMENT; / 增加存儲(chǔ)容量 ElemType *q = (*L).elem+i-1; / q為插入位置 for (p = (*L).elem+(*L).length-1; p=q; -p) *(p+1) = *p / 插入

6、位置及之后的元素右移 *q = e; / 插入e +(*L).length; / 表長(zhǎng)增 return OK; / ListInsert_SqStatus ListDeleteSq(SqList *L, int i, ElemType &e) / 在順序線性表L中刪除第i個(gè)元素，并用e返回其值。 / i的合法值為iListLength_Sq(L)。 ElemType *p, *q; if (i(*L).length) return ERROR; / i值不合法 p = (*L).elem+i-1; / p為被刪除元素的位置 e = *p; / 被刪除元素的值賦給e q = (*L).elem+

7、(*L).length-1; / 表尾元素的位置 for (+p; p=q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移 -(*L).length; / 表長(zhǎng)減 return OK; / ListDelete_Sqvoid main() int i,n,m; ElemType e; SqList L;InitListSq(&L);/建立空表；printf(請(qǐng)輸入順序表元素個(gè)數(shù):n);scanf(%d,&m);if(m=0)do printf(ERROR 請(qǐng)重新輸入：n); scanf(%d,&m);while(m=0);printf(請(qǐng)輸入順序表元素:n);for(i=1;

8、i=m;i+) scanf(%d,&e);ListInsertSq(&L,i,e);printf(輸出初始順序表:n); for(i=1;i=m;i+) printf(%d ,L.elemi-1); printf(n);printf(請(qǐng)輸入插入位置:n);scanf(%d,&n);printf(請(qǐng)輸入插入的元素值:n);scanf(%d,&e); ListInsertSq(&L, n, e);/插入指定元素； printf(輸出插入后的順序表：n);for(i=1;i=L.length;i+)printf(%d ,L.elemi-1);printf(n); printf(請(qǐng)輸入刪除的位置:n)

9、;scanf(%d,&n); ListDeleteSq(&L, n, e);/刪除指定元素； printf(輸出刪除后的順序表：n); for(i=1;i=L.length;i+)printf(%d ,L.elemi-1); printf( e=%dn,e); 功 能：創(chuàng)建一個(gè)順序表L，初始化該順序表：輸入順序表元素個(gè)數(shù)，輸入順序表的元素的值；在順序表的指定位置插入一個(gè)元素；在順序表的指定位置刪除一個(gè)元素，并用e返回該元素的值；輸出各操作后的順序表。算法設(shè)計(jì)思想：首先寫(xiě)好頭文件，接著是線性表的結(jié)構(gòu)定義，定義成順序表結(jié)構(gòu)，在主函數(shù)之前定義了空表建立函數(shù)（InitListSq(SqList *L)

10、），插入函數(shù)（ListInsertSq(SqList *L, int i, ElemType e)），刪除函數(shù)（ListDeleteSq(SqList *L, int i, ElemType &e)），這樣在主函數(shù)中就無(wú)需聲明了，就可以直接在主函數(shù)中調(diào)用上面的函數(shù)。程序二：#include#include#include#define OK 1#define ERROR 0typedef char ElemType;typedef int Status; typedef struct lnodeElemType data;struct lnode *next;lnode,*linklist;v

11、oid createlist(linklist &L,int n)/逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線性表L。int i;linklist p;L=(linklist) malloc (sizeof(lnode);L-next=NULL;for(i=n;i0;-i)p=(linklist ) malloc (sizeof(lnode);scanf(%d,&p-data);p-next=L-next;L-next=p;/創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表LStatus linklistinsert(linklist &L,int i,ElemType e)/在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元

12、素elinklist p,s;p=L;int j=0;while(p&jnext;+j;if(!p|ji-1) return ERROR;s=(linklist) malloc (sizeof(lnode);s-data=e;s-next=p-next;p-next=s;return OK;Status listdelete(linklist &L,int i,ElemType &e)/在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)元素，并由e返回其值linklist p,q;p=L;int j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1) return ERROR

13、; q=p-next;e=q-data;p-next=q-next;free(q);return OK;/刪除單鏈表中指定位置的元素void main()linklist L;linklist p;int i,j;ElemType e;printf(請(qǐng)逆序輸入單鏈表元素個(gè)數(shù)和元素：n);scanf(%d,&j); createlist(L,j);printf(輸出初始單鏈表L：n);p=L-next;while(p) printf(%d ,p-data);p=p-next;printf(n);printf(請(qǐng)輸入插入的位置：n);scanf(%d,&i);printf(請(qǐng)輸入插入的元素的值：n

14、);scanf(%d,&e); linklistinsert(L,i,e);printf(輸出插入后的單鏈表L：n); p=L-next;while(p) printf(%d ,p-data);p=p-next;printf(n);printf(請(qǐng)輸入刪除的元素位置：n);scanf(%d,&i); listdelete(L, i, e);printf(輸出刪除后的單鏈表L和被刪除元素的值e：n); p=L-next;while(p) printf(%d ,p-data);p=p-next;printf( e=%dn,e);功 能：創(chuàng)建一個(gè)單鏈表L，初始化該單鏈表：輸入單鏈表元素個(gè)數(shù)，輸入單鏈

15、表的元素的值；在單鏈表的指定位置插入一個(gè)元素；在單鏈表的指定位置刪除一個(gè)元素，并用e返回該元素的值；輸出各操作后的單鏈表。算法設(shè)計(jì)思想：首先寫(xiě)好頭文件，接著是線性表的結(jié)構(gòu)定義，定義成單鏈表結(jié)構(gòu)，在主函數(shù)之前定義了空表建立函數(shù)（createlist(linklist &L,int n)），插入函數(shù)（linklistinsert(linklist &L,int i,ElemType e)），刪除函數(shù)（listdelete(linklist &L,int i,ElemType &e)），這樣在主函數(shù)中就無(wú)需聲明了，就可以直接在主函數(shù)中調(diào)用上面的函數(shù)。輸入/輸出要求（1）輸入數(shù)據(jù)：元素個(gè)數(shù)：自定義（本

16、次實(shí)驗(yàn)以4為例）；輸入的元素的值：自定義（本次實(shí)驗(yàn)以1，10，9，5為例）；插入元素的位置：自定義（本次實(shí)驗(yàn)以2為例）；插入元素的值：自定義（本次實(shí)驗(yàn)以7為例）；刪除元素的位置：自定義（本次實(shí)驗(yàn)以4為例）。 數(shù)據(jù)類(lèi)型：整型（int 型）。 值域范圍：元素個(gè)數(shù)：m0；輸入元素的值：32768，32767；插入元素的位置：i0；刪除元素的位置：i0。（2）輸出數(shù)據(jù)：元素個(gè)數(shù)：自定義（本次實(shí)驗(yàn)以5為例）；輸入的元素的值：自定義（本次實(shí)驗(yàn)以5，-4，9，10，3為例）；插入元素的位置：自定義（本次實(shí)驗(yàn)以4為例）；插入元素的值：自定義（本次實(shí)驗(yàn)以21為例）；刪除元素的位置：自定義（本次實(shí)驗(yàn)以3為例）。 數(shù)據(jù)類(lèi)型：整型（int 型）。 值域范圍：元素個(gè)數(shù)：m0；輸入元素的值：32768，32767；插入元素的位置：i0；