數(shù)據(jù)結(jié)構(gòu)試驗(yàn)一順序表的實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一順序表的實(shí)現(xiàn)班級(jí)學(xué)號(hào)姓名分?jǐn)?shù)一、實(shí)驗(yàn)?zāi)康模?. 熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)(順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu))上的實(shí)現(xiàn)；2. 以線性表的各種操作的實(shí)現(xiàn)為重點(diǎn)；3. 通過本次學(xué)習(xí)幫助學(xué)生加深 C語言的使用，掌握算法分析方法并對(duì)已經(jīng)設(shè)計(jì) 出的算法進(jìn)行分析，給出相應(yīng)的結(jié)果。二、實(shí)驗(yàn)要求：編寫實(shí)驗(yàn)程序，上機(jī)運(yùn)行本程序，保存程序的運(yùn)行結(jié)果，結(jié)合程序進(jìn)行分析并寫出實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)內(nèi)容及分析：1順序表的建立建立一個(gè)含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。程序如下：頭文件SqList.h 的內(nèi)容如下：#in clude<stdio.h>#in clude<mal

2、loc.h>#defi ne LIST_INIT_SIZE 100#defi ne LISTINCREMENT 10#define TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0#defi ne INFEASIBLE -1#defi ne OVERFLOW -2typedef int ElemType;typedef int Status;typedef structElemType *elem;int len gth;int listsize;SqList;Status In itList_Sq(SqList *L)L->e

3、lem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L->elem) return(OVERFLOW);L->le ngth=O;L->listsize=LIST_INIT_SIZE; return OK;Status CreatList_Sq(SqList *L,int n)int i;printf("輸入 d個(gè)整數(shù)：n",n); for(i=0;i< n;i+)scan f("n%d",&L->elemi); return OK;/以下是整個(gè)源程

4、序： #in clude<stdio.h> #i nclude"SqList.h" int mai n()int i,n;SqList a;SqList *l = &a;if(InitList_Sq(l)=-2) printf(”分配失敗");printf("n輸入要建立的線性表I的長度n:");/輸入線性表得長度scan f("%d",&n);l->le ngth=n;printf("線性表的長度是：dn",l->length);CreatList_Sq(l, n

5、);生成線性表printf(" 輸出線性表I中的元素值：”);/輸出線性表中的元素for(i=0;i<l->le ngth;i+)prin tf("%7d",l->elemi);getchar();程序的運(yùn)行結(jié)果：2.順序表的插入利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L,然后再第i個(gè)位置插入元素，通過對(duì)比插入元素前后的線性表發(fā)生的變化，判斷插入操作是否正確。參考程序：#in clude<stdio.h>#in clude<malloc.h> #i nclude"SqList.h"Status List In s

6、ert_Sq(SqList *L,i nt i,ElemType e)/在線性表L中的第i個(gè)位置前插入一個(gè)值為e的元素i的取值范圍：1<=i<=ListLe ngth_Sq(L)ElemType *n ewbase,*q,*p;if(i<1|i>L->le ngth+1) return ERROR;/i值不合法if(L->le ngth>=L->listsize) /當(dāng)前存儲(chǔ)空間已滿，增加分配量n ewbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(

7、ElemType);if(! newbase) return (OVERFLOW); /存儲(chǔ)分配失敗L->elem=n ewbase;/新基址L->le ngth=+LISTINCREMENT; /增加存儲(chǔ)容量/ifq=&(L->elemi-1); /q為插入位置for(p=&(L->elemL->le ngth-1);p>=q;-p) *(p+1)=*p;/*q=e;/ 插入 e+L->le ngth; / 表長增 1 return OK;/ListI nsert_Sqint mai n()int n,i,x;SqList *L,a;

8、L=&a;In itList_Sq(L);prin tf("n輸入要建立的線性表scan f("%d",&n);L->le ngth=n;CreatList_Sq(L ,n);prin tf("n插入元素之前線性表prin tf("n插入元素之前線性表for(i=0;i<L->le ngth;i+)插入位置及以后的元素右移L得長度:");L 的長度是:%d",L->length);L中的元素是:");prin tf("%5d",L->elemi);p

9、rin tf("n輸入要插入元素的位置：”);scan f("%d",&i);prin tf("n輸入要插入的元素的值：”);scan f("n %d"，& x);if(Listl nsert_Sq(L,i,x)>0)printf("n插入元素之后線性表L的長度是：%d ",L->length);printf("n插入元素之后線性表L的元素是:n");for(i=0;i<L->le ngth;i+)prin tf("%5d", L-&g

10、t;elemi);/ifelseprintf(”不能插入這個(gè)元素！n ”);getchar();運(yùn)行結(jié)果：5617 31Prt?ss any Ike to continuea丄 4 IBS' G;C DebngVcia nxi ngbiao l.exe:?是31A7亍.厘12417 J132度一兀 番£ 線線童一翌刖元 之之入 fs 元元要AA2厶164. 單鏈表的實(shí)現(xiàn)新建鏈表，生成一個(gè)有一定結(jié)點(diǎn)的鏈表，并且順序輸出。 程序代碼：#i nclude"stdio.h"#i nclude"stdlib.h"#i nclude"st

11、ri ng.h"#defi ne null 0#defi ne MAX 100 /最多元素個(gè)數(shù)#defi ne LENGTH sizeof(struct Node) typedef int Elem ;/數(shù)據(jù)元素類型/單鏈表實(shí)現(xiàn)線性表struct NodeElem data; II 數(shù)據(jù)域 struct Node *next;II 指針域； typedef struct Node NODE; typedef struct Node *LINKLIST;/初始化鏈表，產(chǎn)生一個(gè)空鏈表LINKLIST In itList()/返回空鏈表的頭指針LINKLIST head;head=null

12、;retur n head;/新建鏈表，生成一個(gè)有一定結(jié)點(diǎn)的鏈表LINKLIST CreateList()/返回新鏈表的首地址(指針)LINKLIST head=null,p,q;int n,i;Elem temp;doprin tf("請(qǐng)輸入要建的結(jié)點(diǎn)數(shù)：");scan f("%d", &n);if(n<1 | n>MAX)printf(" 對(duì)不起！請(qǐng)輸入的數(shù)在1-%d之間，請(qǐng)重新輸入。n ”,MAX);while( n<1 | n>MAX);for(i=0;i< n;i+)開辟新結(jié)點(diǎn)空間",i

13、+1);輸入結(jié)點(diǎn)數(shù)據(jù)如果head指向空，貝U p結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)不是第一個(gè)結(jié)點(diǎn)，則結(jié)點(diǎn)放到結(jié)尾并且，尾指針p=(LINKLIST)malloc(LENGTH); / printf("請(qǐng)輸入第d結(jié)點(diǎn)數(shù)據(jù)：scan f("%d"，& temp);/p->data=temp;if(head=n ull)/head=q=p; p->n ext =n ull;else/后移p->n ext =n ull; q_>n ext=p;q=p;return head; /返回新鏈表的首地址(指針)/遍歷打印鏈表int prin tList(LINKL

14、IST h)/返回打印結(jié)果，0表示無數(shù)據(jù)，1表示成功打印完成LINKLIST pt=h;if(pt=null) /沒有數(shù)據(jù)直接返回prin tf("對(duì)不起，沒有數(shù)據(jù)！");return 0;while(pt) /結(jié)點(diǎn)不為空就打印結(jié)點(diǎn)內(nèi)容prin tf("%d ",pt->data); pt=pt- >n ext;prin tf("n");return 1;/求的鏈表的長度int ListLe ngth(LINKLIST h)/求的鏈表長度，返回鏈表長度，若鏈表為空則返回0LINKLIST pt=h;int len=0;/初

15、始化計(jì)數(shù)器為0while(pt)len+;pt=pt- >n ext;return len; /返回鏈表長度 /*/向鏈表鏈表尾部添加結(jié)點(diǎn)，無輸入9LINKLIST AddNode(LINKLIST h,Elem e)LINKLIST head,pt,p;pt=head=h;/指向起始結(jié)點(diǎn)p=(LINKLIST)malloc(LENGTH); p->data=e;/p->n ext=n ull;if(pt=null)/head=p;else/while(pt->n ext)pt=pt->n ext;pt- >n ext=p;return head;/*/*/

16、向鏈表鏈表尾部添加結(jié)點(diǎn)，有輸入LINKLIST AddNode(LINKLIST h)LINKLIST head,pt,p; pt=head=h; p=(LINKLIST)malloc(LENGTH); printf(”請(qǐng)輸入要添加的數(shù)據(jù):scan f("%d",&p->data);p->n ext=n ull;if(pt=null)/head=p;else/while(pt->n ext)pt=pt->n ext;pt- >n ext=p;return head;/ 開辟結(jié)點(diǎn)空間向結(jié)點(diǎn)數(shù)據(jù)賦值/結(jié)點(diǎn)后繼指向空若鏈表為空，直接作為第一個(gè)

17、結(jié)點(diǎn)若不為空，將結(jié)點(diǎn)插在最后返回頭結(jié)點(diǎn)指針/指向起始結(jié)點(diǎn)/開辟結(jié)點(diǎn)空間");/結(jié)點(diǎn)后繼指向空若鏈表為空，直接作為第一個(gè)結(jié)點(diǎn)若不為空，將結(jié)點(diǎn)插在最后返回頭結(jié)點(diǎn)指針*/將結(jié)點(diǎn)插入到鏈表的指定位置LINKLIST AddNode(LINKLIST h,i nt i,Elem e)/插入位置i,0<i,若i大于鏈表長度，則直接插在鏈表最后 10LINKLIST head,pt,p;int j; pt=head=h;if(i<1)/程序prin tf("程序出錯(cuò)，請(qǐng)檢查參數(shù)!exit(1);if(pt && i>ListLe ngth(h)插入位置錯(cuò)

18、誤(i<1)，輸出信息并結(jié)束");/鏈表不為空，且位置大于鏈表長度時(shí)/開辟結(jié)點(diǎn)空間向結(jié)點(diǎn)數(shù)據(jù)賦值/結(jié)點(diǎn)后繼指向空/鏈表為空時(shí)/開辟結(jié)點(diǎn)空間向結(jié)點(diǎn)數(shù)據(jù)賦值/結(jié)點(diǎn)后繼指向空/參數(shù)正確且鏈表不為空時(shí)if(i=1)/插入點(diǎn)為第1個(gè)位置p=(LINKLIST)malloc(LENGTH);/p->data=e;/p_>n ext=pt;/開辟結(jié)點(diǎn)空間向結(jié)點(diǎn)數(shù)據(jù)賦值 結(jié)點(diǎn)后繼指向空while(pt->n ext)pt=pt->n ext;p=(LINKLIST)malloc(LENGTH); p->data=e;/p->n ext=n ull;pt-&g

19、t;n ext=p;else if(pt=nu II)p=(LINKLIST)malloc(LENGTH);p->data=e;/p->n ext=n ull;head=p;elsehead=p;else/插入在鏈表中間位置時(shí)p=(LINKLIST)malloc(LENGTH);p->data=e;/for(j=1;j<i-1;j+)pt=pt- >n ext;p->n ext=pt->n ext;pt- >n ext=p;return head;/開辟結(jié)點(diǎn)空間向結(jié)點(diǎn)數(shù)據(jù)賦值返回頭結(jié)點(diǎn)指針18/刪除鏈表中的某位置結(jié)點(diǎn)LINKLIST ListDe

20、lete(LINKLIST h,i nt i) /i 在 1 至U ListLength(h) 之間LINKLIST head,pt;int j=1;pt=head=h;if(h=null)/空表"）;檢查i的范圍prin tf(" 對(duì)不起，沒有內(nèi)容!return n ull;if(i<1 | i>ListLe ngth(h)/prin tf（" 程序出錯(cuò)，請(qǐng)檢查參數(shù)！"）;exit(1);else/iif(i=1)/head=pt- >n ext; free(pt);else/while(j<i-1)合法，刪除首結(jié)點(diǎn)刪除中間節(jié)點(diǎn)

21、或尾結(jié)點(diǎn)pt=pt- >n ext;j+;pt-> next=pt-> next-next;return head;/返回頭結(jié)點(diǎn)指針/鏈表是否為空int ListEmpty(LINKLIST h)/返回0表示空，1表示鏈表不空if(h=n ull)return 0;return 1;/取得指定位置的元素的值Elem GetElem(LINKLIST h,i nt i)/返回結(jié)點(diǎn)的元素值LINKLIST pt=h;int j=1;if(i>ListLe ngth(h) | i<1)/prin tf("程序出錯(cuò)，請(qǐng)檢查參數(shù)!exit(1);while(j&l

22、t;i)/pt=pt- >n ext;j+；return (pt->data);/鏈表的逆置LINKLIST In vert(LINKLIST h)LINKLIST head,middle,trail; / middle=n ull;while(h) /檢查參數(shù)");找到第i個(gè)結(jié)點(diǎn)返回結(jié)點(diǎn)值定義三個(gè)指針指向三個(gè)相鄰的結(jié)點(diǎn)循環(huán)交換相鄰兩個(gè)的指針指向trail=middle; middle=h;h=h->n ext; middle-next=trail;head=middle;/將最后的結(jié)點(diǎn)變?yōu)殒湵眍^return head;/返回鏈表表頭/將兩個(gè)鏈表合并為一個(gè)鏈表LIN

23、KLIST Un io n(LINKLIST La,LINKLIST Lb)/將La和Lb連接在一塊，返回連接后的鏈表頭指針LINKLIST head,pa;if(La=n ull)head=Lb;elsehead=pa=La;while(pa->n ext)pa=pa->n ext;La的結(jié)尾pa->next=Lb;/將Lb表頭連接在鏈表return head;/返回鏈表表頭/將鏈表按非遞減排序LINKLIST ToUpSort(LINKLIST h)/返回排好序后的頭指針LINKLIST p=h,q,temp;temp=(LINKLIST)malloc(LENGTH); /開辟臨時(shí)交換結(jié)點(diǎn)while(p)q=p->n ext;while(q)if(q->data<p->data) /比較大小交換數(shù)據(jù)temp->data=p->data; p_>data=q_>data;q->data=temp->data;q=q_>n ext;p=p->n ext;free(temp);/釋放臨時(shí)空間return h;/返回頭結(jié)點(diǎn)/將鏈表按非遞增排序LINKLIST ToDow nSort(LINKLIST