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

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

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

一、實(shí)驗(yàn)?zāi)康模?/p>

1.熟悉線性表的基本運(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.通過(guò)本次學(xué)習(xí)幫助學(xué)生加深C語(yǔ)言的使用，掌握算法分析方法并對(duì)已經(jīng)設(shè)

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

二、實(shí)驗(yàn)要求：

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

并寫(xiě)出實(shí)驗(yàn)報(bào)告。

三、實(shí)驗(yàn)內(nèi)容及分析：

L順序表的建立

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

度。

程序如下：

頭文件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個(gè)整數(shù):\n〃,n);

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

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

returnOK;

〃以下是整個(gè)源程序：

#include<stdio.h>

#include，zSqList.h〃

intmainO

inti,n;

SqLista;

SqList*1=&a;

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

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

scanf(〃％d〃，&n);

l->length=n;

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

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

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

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

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

getchar();

)

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

2.順序表的插入

利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L,然后再第i個(gè)位置插入元素，通過(guò)對(duì)

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

參考程序：

#include<stdio.h>

#include<malloc.h>

#includez，SqList.h〃

StatusListInsert_Sq(SqList*L,inti,ElemTypee)

(

〃在線性表L中的第i個(gè)位置前插入一個(gè)值為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)前存儲(chǔ)空間已滿，增加分配量

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

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

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

L->elem=newbase;〃新基址

L->length=+LISTINCREMENT;〃增加存儲(chǔ)容量

}//if

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

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

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

*q=e;〃插入e

++L->length;〃表長(zhǎng)增1

returnOK;

}//ListInsert_Sq

intmainO

intn,i,x;

SqList*L,a;

L=&a;

InitList_Sq(L);

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

scanf&n);

L->length=n;

CreatList_Sq(L,n);

printf(〃\n插入元素之前線性表L的長(zhǎng)度是:％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的長(zhǎng)度是:%d",L->length）;

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

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

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

}//if

else

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

getchar();

)

運(yùn)行結(jié)果：

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

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

程序代碼：

#includez，stdio.h〃

#includezzstdlib.h〃

#includez，string.h〃

#definenull0

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

ttdefineLENGTHsizeof(structNode)

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

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

structNode

(

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

structNode*next;〃指針域

)；

typedefstructNodeNODE;

typedefstructNode*LINKLIST;

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

LINKLISTInitListO

〃返回空鏈表的頭指針

(

LINKLISThead;

head=null;

returnhead;

)

〃新建鏈表，生成一個(gè)有一定結(jié)點(diǎn)的鏈表

LINKLISTCreateListO

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

(

LINKLISThead=null,p,q;

intn,i;

Elemtemp;

do{

printf(〃請(qǐng)輸入要建的結(jié)點(diǎn)數(shù)：”)；

scanf&n);

if(n<ln>MAX)

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

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

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

(

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟新結(jié)點(diǎn)空間

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

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

p->data=temp;

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

一個(gè)結(jié)點(diǎn)

(

head=q=p;

p->next=null;

else〃不是第一個(gè)結(jié)點(diǎn)，則結(jié)點(diǎn)放到

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

{

p->next=null;

q->next=p;

q二P；

}

)

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

)

〃遍歷打印鏈表

intprintList(LINKLISTh)

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

(

LINKLISTpt=h;

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

printf("對(duì)不起，沒(méi)有數(shù)據(jù)！”)；

return0;

)

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

(

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

pt=pt->next;

)

printf('\n");

return1;

)

〃求的鏈表的長(zhǎng)度

intListLength(LINKLISTh)

〃求的鏈表長(zhǎng)度，返回鏈表長(zhǎng)度，若鏈表為空則返回0

(

LINKLISTpt=h;

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

while(pt)

len++;

pt=pt->next;

)

returnlen;〃返回鏈表長(zhǎng)度

)

/*

〃向鏈表鏈表尾部添加結(jié)點(diǎn)，無(wú)輸入

LINKLISTAddNode(LINKLISTh,Eleme)

(

LINKLISThead,pt,p;

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

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟結(jié)點(diǎn)空間

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

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

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

結(jié)點(diǎn)

head=p;

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

后

while(pt->next)

pt=pt->next;

pt->next=p;

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

)

*/

/*

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

LINKLISTAddNode(LINKLISTh)

LINKLISThead,pt,p;

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

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟結(jié)點(diǎn)空間

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

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

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

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

結(jié)點(diǎn)

head=p;

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

后

while(pt->next)

pt=pt->next;

pt->next=p;

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

)

*/

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

LINKLISTAddNode(LINKLISTh,inti,Eleme)

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

(

LINKLISThead,pt,p;

intj;

pt=head=h;

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

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

(

printf(〃程序出錯(cuò)，請(qǐng)檢查參數(shù)！”)；

exit(l);

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

大于鏈表長(zhǎng)度時(shí)

(

while(pt->next)

(

pt=pt->next;

)

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟結(jié)點(diǎn)空間

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

值

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

向空

pt->next=p;

)

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

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟結(jié)點(diǎn)空間

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

值

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

向空

head=p;

)

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

(

if(i==l)〃插入點(diǎn)為第1個(gè)位置

(

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟結(jié)點(diǎn)空間

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

值

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

空

head=p;

else〃插入在鏈表中間位置時(shí)

p=(LINKLIST)malloc(LENGTH);〃開(kāi)辟結(jié)點(diǎn)空間

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

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

pt=pt->next;

p->next=pt->next;

pt->next=p;

returnhead;〃返回頭結(jié)

點(diǎn)指針

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

LINKLISTListDelete(LINKLISTh,inti)

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

LINKLISThead,pt;

intj=l;

pt=head=h;

if(h==null)〃空表

{

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

returnnull;

)

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

(

printf("程序出錯(cuò),請(qǐng)檢查參數(shù)！”)；

exit(1);

)

else//i合法，

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

head=pt->next;

free(pt);

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

while(j<i-l)

pt=pt->next;

j++；

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

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

〃鏈表是否為空

intListEmpty(LINKLISTh)

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

(

if(h==null)

return0;

return1;

)

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

ElemGetElem(LINKLISTh,inti)

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

(

LINKLISTpt=h;

intj=l;

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

(

printf(〃程序出錯(cuò)，請(qǐng)檢查參數(shù)！");

exit(l);

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

結(jié)點(diǎn)

(

pt=pt->next;

j++；

}

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

}

〃鏈表的逆置

LINKLISTInvert(LINKLISTh)

(

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

middle=null;

while(h)

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

指向

trail=middle;

middle』;

h=h->next;

middle->next二trail;

}

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

returnhead;〃返回鏈表表頭

)

〃將兩個(gè)鏈表合并為一個(gè)鏈表

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表頭連接在鏈表