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

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

班級學(xué)號姓名分?jǐn)?shù)

一、實驗?zāi)康模?/p>

1.熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實

現(xiàn)；

2.以線性表的各種操作的實現(xiàn)為重點；

3.通過本次學(xué)習(xí)幫助學(xué)生加深C語言的使用，掌握算法分析方法并對已經(jīng)設(shè)

計出的算法進(jìn)行分析，給出相應(yīng)的結(jié)果。

二、實驗要求：

編寫實驗程序，上機(jī)運行本程序，保存程序的運行結(jié)果，結(jié)合程序進(jìn)行分析

并寫出實驗報告。

三、實驗內(nèi)容及分析：

L順序表的建立

建立一個含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長

度。

程序如下：

頭文件SqList.h的內(nèi)容如下：

#include<stdio.h>

#include<malloc.h>

#defineLISTINITSIZE100

ttdefineLISTINCREMENT10

ttdefineTRUE1

ttdefineFALSE0

tfdefineOK1

ttdefineERROR0

#defineINFEASIBLE-1

ttdefineOVERFLOW-2

typedefintElemType;

typedefintStatus;

typedefstruct{

ElemType*elem;

intlength;

intlistsize;

}SqList;

StatusInitList_Sq(SqList*L)

L->elem=(ElemType*)malloc(LISTINITSIZE*sizeof(ElemType));

if(!?elem)return(OVERFLOW);

L->length=0;

L->listsize=LIST_INIT_SIZE;

returnOK;

)

StatusCreatList_Sq(SqList*L,intn)

(

inti;

printf(〃輸入%(1個整數(shù):\n〃,n);

for(i=0;i<n;i++)

scanf(z，\n%d，z,&L->elem[i]);

returnOK;

〃以下是整個源程序：

#include<stdio.h>

#include，zSqList.h〃

intmainO

inti,n;

SqLista;

SqList*1=&a;

if(InitList_Sq(l)==-2)printf(〃分配失敗〃)；

printf(〃\n輸入要建立的線性表1的長度n:〃)；〃輸入線性表得長度

scanf(〃％d〃，&n);

l->length=n;

printf(〃線性表的長度是:％d\n〃，]>length);

CreatList_Sq(l,n);〃生成線性表

printf(〃輸出線性表1中的元素值：〃)；〃輸出線性表中的元素

for(i=0;i<l->length;i++)

printf(z/%7cl，z,l->elem[i]);

getchar();

)

程序的運行結(jié)果:

2.順序表的插入

利用前面的實驗先建立一個順序表L,然后再第i個位置插入元素，通過對

比插入元素前后的線性表發(fā)生的變化，判斷插入操作是否正確。

參考程序：

#include<stdio.h>

#include<malloc.h>

#includez，SqList.h〃

StatusListInsert_Sq(SqList*L,inti,ElemTypee)

(

〃在線性表L中的第i個位置前插入一個值為e的元素

//i的取值范圍：l<=i〈=ListLength_Sq(L)

ElemType*newbase,*q,*p;

if(i<l|Ii>L->length+l)return￡1^0匕〃1.值不合法

if(L->length>=L->listsize){〃當(dāng)前存儲空間已滿，增加分配量

newbase=(ElemType*)realloc(L->elem,

(L->listsize+LISTINCREMENT)*sizeof(ElemType));

if(Inewbase)return(OVERFLOW);〃存儲分配失敗

L->elem=newbase;〃新基址

L->length=+LISTINCREMENT;〃增加存儲容量

}//if

q=&(L->elem[iT]);//q為插入位置

for(p=&(L->e1em[L->1ength-1]);p>=q;—p)*(p+l)=*p;

〃插入位置及以后的元素右移

*q=e;〃插入e

++L->length;〃表長增1

returnOK;

}//ListInsert_Sq

intmainO

intn,i,x;

SqList*L,a;

L=&a;

InitList_Sq(L);

printf("\n輸入要建立的線性表L得長度：”)；

scanf&n);

L->length=n;

CreatList_Sq(L,n);

printf(〃\n插入元素之前線性表L的長度是:％d〃,L->length);

printf(〃\n插入元素之前線性表L中的元素是:〃)；

for(i=0;i<L->length;i++)

printf(，z%5d，z,L->elem[i]);

printf(〃\n輸入要插入元素的位置:〃)；

scanf(〃%d〃,&i);

printf(〃\n輸入要插入的元素的值:〃)；

scanf(/z\n%d〃，&x);

if(ListInsert_Sq(L,i,x)>0)

printf（"\n插入元素之后線性表L的長度是:%d",L->length）;

printf("\n插入元素之后線性表L的元素是:\n");

for(i=0;i<L->length;i++)

printf("%5d”,L->elem[i]);

}//if

else

printf("不能插入這個元素！\n");

getchar();

)

運行結(jié)果：

4.單鏈表的實現(xiàn)

新建鏈表，生成一個有一定結(jié)點的鏈表，并且順序輸出。

程序代碼：

#includez，stdio.h〃

#includezzstdlib.h〃

#includez，string.h〃

#definenull0

ttdefineMAX100〃最多元素個數(shù)

ttdefineLENGTHsizeof(structNode)

typedefintElem;〃數(shù)據(jù)元素類型

〃單鏈表實現(xiàn)線性表

structNode

(

Elemdata;〃數(shù)據(jù)域

structNode*next;〃指針域

)；

typedefstructNodeNODE;

typedefstructNode*LINKLIST;

〃初始化鏈表,產(chǎn)生一個空鏈表

LINKLISTInitListO

〃返回空鏈表的頭指針

(

LINKLISThead;

head=null;

returnhead;

)

〃新建鏈表，生成一個有一定結(jié)點的鏈表

LINKLISTCreateListO

〃返回新鏈表的首地址(指針)

(

LINKLISThead=null,p,q;

intn,i;

Elemtemp;

do{

printf(〃請輸入要建的結(jié)點數(shù)：”)；

scanf&n);

if(n<ln>MAX)

printf("對不起！請輸入的數(shù)在lid之間，請重新輸入。\n",MAX);

}while(n<l||n>MAX);

for(i=0;i<n;i++)

(

p=(LINKLIST)malloc(LENGTH);〃開辟新結(jié)點空間

printf("請輸入第%d結(jié)點數(shù)據(jù)："，i+1);

scanf&temp);〃輸入結(jié)點數(shù)據(jù)

p->data=temp;

if(head==null)〃如果head指向空，則p結(jié)點為第

一個結(jié)點

(

head=q=p;

p->next=null;

else〃不是第一個結(jié)點，則結(jié)點放到

結(jié)尾并且，尾指針后移

{

p->next=null;

q->next=p;

q二P；

}

)

returnhead;〃返回新鏈表的首地址(指針)

)

〃遍歷打印鏈表

intprintList(LINKLISTh)

〃返回打印結(jié)果，0表示無數(shù)據(jù)，1表示成功打印完成

(

LINKLISTpt=h;

if(pt==null)〃沒有數(shù)據(jù)直接返回

printf("對不起，沒有數(shù)據(jù)！”)；

return0;

)

while(pt)〃結(jié)點不為空就打印結(jié)點內(nèi)容

(

printf(v%d”,pt->data);

pt=pt->next;

)

printf('\n");

return1;

)

〃求的鏈表的長度

intListLength(LINKLISTh)

〃求的鏈表長度，返回鏈表長度，若鏈表為空則返回0

(

LINKLISTpt=h;

intlen=0;〃初始化計數(shù)器為0

while(pt)

len++;

pt=pt->next;

)

returnlen;〃返回鏈表長度

)

/*

〃向鏈表鏈表尾部添加結(jié)點，無輸入

LINKLISTAddNode(LINKLISTh,Eleme)

(

LINKLISThead,pt,p;

pt=head=h;〃指向起始結(jié)點

p=(LINKLIST)malloc(LENGTH);〃開辟結(jié)點空間

p->data=e;〃向結(jié)點數(shù)據(jù)賦值

p->next=null;〃結(jié)點后繼指向空

if(pt==null)〃若鏈表為空，直接作為第一個

結(jié)點

head=p;

else〃若不為空，將結(jié)點插在最

后

while(pt->next)

pt=pt->next;

pt->next=p;

returnhead;〃返回頭結(jié)點指針

)

*/

/*

〃向鏈表鏈表尾部添加結(jié)點，有輸入

LINKLISTAddNode(LINKLISTh)

LINKLISThead,pt,p;

pt二head二h;〃指向起始結(jié)點

p=(LINKLIST)malloc(LENGTH);〃開辟結(jié)點空間

printf(〃請輸入要添加的數(shù)據(jù):〃）；

scanf(〃%d〃,&p->data);

p->next=null;〃結(jié)點后繼指向空

if(pt==null)〃若鏈表為空，直接作為第一個

結(jié)點

head=p;

else〃若不為空，將結(jié)點插在最

后

while(pt->next)

pt=pt->next;

pt->next=p;

returnhead;〃返回頭結(jié)點指針

)

*/

〃將結(jié)點插入到鏈表的指定位置

LINKLISTAddNode(LINKLISTh,inti,Eleme)

〃插入位置i,0<i,若i大于鏈表長度，則直接插在鏈表最后

(

LINKLISThead,pt,p;

intj;

pt=head=h;

if(i<l)〃插入位置錯

誤(i<l),輸出信息并結(jié)束程序

(

printf(〃程序出錯，請檢查參數(shù)！”)；

exit(l);

if(pt&&i>ListLength(h))〃鏈表不為空，且位置

大于鏈表長度時

(

while(pt->next)

(

pt=pt->next;

)

p=(LINKLIST)malloc(LENGTH);〃開辟結(jié)點空間

p->data=e;〃向結(jié)點數(shù)據(jù)賦

值

p->next=null;〃結(jié)點后繼指

向空

pt->next=p;

)

elseif(pt==null)〃鏈表為空時

p=(LINKLIST)malloc(LENGTH);〃開辟結(jié)點空間

p->data=e;〃向結(jié)點數(shù)據(jù)賦

值

p->next=null;〃結(jié)點后繼指

向空

head=p;

)

else〃參數(shù)正確且鏈表不為空時

(

if(i==l)〃插入點為第1個位置

(

p=(LINKLIST)malloc(LENGTH);〃開辟結(jié)點空間

p->data=e;〃向結(jié)點數(shù)據(jù)賦

值

p->next=pt;〃結(jié)點后繼指向

空

head=p;

else〃插入在鏈表中間位置時

p=(LINKLIST)malloc(LENGTH);〃開辟結(jié)點空間

p->data=e;〃向結(jié)點數(shù)據(jù)賦

for(j=l;j<i-l;j++)

pt=pt->next;

p->next=pt->next;

pt->next=p;

returnhead;〃返回頭結(jié)

點指針

〃刪除鏈表中的某位置結(jié)點

LINKLISTListDelete(LINKLISTh,inti)

//i在1到ListLength(h)之間

LINKLISThead,pt;

intj=l;

pt=head=h;

if(h==null)〃空表

{

printf("對不起，沒有內(nèi)容！”)；

returnnull;

)

if(i<li>ListLength(h))〃檢查i的范圍

(

printf("程序出錯,請檢查參數(shù)！”)；

exit(1);

)

else//i合法，

if(i==l)〃刪除首結(jié)點

head=pt->next;

free(pt);

else〃刪除中間節(jié)點或尾結(jié)點

while(j<i-l)

pt=pt->next;

j++；

pt->next=pt->next->next;

returnhead;〃返回頭結(jié)點指針

〃鏈表是否為空

intListEmpty(LINKLISTh)

〃返回0表示空，1表示鏈表不空

(

if(h==null)

return0;

return1;

)

〃取得指定位置的元素的值

ElemGetElem(LINKLISTh,inti)

〃返回結(jié)點的元素值

(

LINKLISTpt=h;

intj=l;

if(i>ListLength(h)i<l)〃檢查參數(shù)

(

printf(〃程序出錯，請檢查參數(shù)！");

exit(l);

while(j<i)〃找到第i個

結(jié)點

(

pt=pt->next;

j++；

}

return(pt->data);〃返回結(jié)點值

}

〃鏈表的逆置

LINKLISTInvert(LINKLISTh)

(

LINKLISThead,middle,trail;〃定義三個指針指向三個相鄰的結(jié)點

middle=null;

while(h)

{〃循環(huán)交換相鄰兩個的指針

指向

trail=middle;

middle』;

h=h->next;

middle->next二trail;

}

head=middle;〃將最后的結(jié)點變?yōu)殒湵眍^

returnhead;〃返回鏈表表頭

)

〃將兩個鏈表合并為一個鏈表

LINKLISTUnion(LINKLISTLa,LINKLISTLb)

〃將La和Lb連接在一塊，返回連接后的鏈表頭指針

{

LINKLISThead,pa;

if(La==nul1)

head=Lb;

else

head=pa=La;

while(pa->next)

pa=pa->next：

}

pa->next=Lb;〃將Lb表頭連接在鏈表