數據結構實驗一順序表的實現

班級學號姓名分數

一、實驗目的：

1.熟悉線性表的基本運算在兩種存儲結構（順序結構和鏈式結構）上的實

現；

2.以線性表的各種操作的實現為重點；

3.通過本次學習幫助學生加深C語言的使用，掌握算法分析方法并對已經設

計出的算法進行分析，給出相應的結果。

二、實驗要求：

編寫實驗程序，上機運行本程序，保存程序的運行結果，結合程序進行分析

并寫出實驗報告。

三、實驗內容及分析：

L順序表的建立

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

度。

程序如下：

頭文件SqList.h的內容如下：

#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個整數:\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();

)

程序的運行結果:

2.順序表的插入

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

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

參考程序：

#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){〃當前存儲空間已滿，增加分配量

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();

)

運行結果：

4.單鏈表的實現

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

程序代碼：

#includez，stdio.h〃

#includezzstdlib.h〃

#includez，string.h〃

#definenull0

ttdefineMAX100〃最多元素個數

ttdefineLENGTHsizeof(structNode)

typedefintElem;〃數據元素類型

〃單鏈表實現線性表

structNode

(

Elemdata;〃數據域

structNode*next;〃指針域

)；

typedefstructNodeNODE;

typedefstructNode*LINKLIST;

〃初始化鏈表,產生一個空鏈表

LINKLISTInitListO

〃返回空鏈表的頭指針

(

LINKLISThead;

head=null;

returnhead;

)

〃新建鏈表，生成一個有一定結點的鏈表

LINKLISTCreateListO

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

(

LINKLISThead=null,p,q;

intn,i;

Elemtemp;

do{

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

scanf&n);

if(n<ln>MAX)

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

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

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

(

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

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

scanf&temp);〃輸入結點數據

p->data=temp;

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

一個結點

(

head=q=p;

p->next=null;

else〃不是第一個結點，則結點放到

結尾并且，尾指針后移

{

p->next=null;

q->next=p;

q二P；

}

)

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

)

〃遍歷打印鏈表

intprintList(LINKLISTh)

〃返回打印結果，0表示無數據，1表示成功打印完成

(

LINKLISTpt=h;

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

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

return0;

)

while(pt)〃結點不為空就打印結點內容

(

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

pt=pt->next;

)

printf('\n");

return1;

)

〃求的鏈表的長度

intListLength(LINKLISTh)

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

(

LINKLISTpt=h;

intlen=0;〃初始化計數器為0

while(pt)

len++;

pt=pt->next;

)

returnlen;〃返回鏈表長度

)

/*

〃向鏈表鏈表尾部添加結點，無輸入

LINKLISTAddNode(LINKLISTh,Eleme)

(

LINKLISThead,pt,p;

pt=head=h;〃指向起始結點

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

p->data=e;〃向結點數據賦值

p->next=null;〃結點后繼指向空

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

結點

head=p;

else〃若不為空，將結點插在最

后

while(pt->next)

pt=pt->next;

pt->next=p;

returnhead;〃返回頭結點指針

)

*/

/*

〃向鏈表鏈表尾部添加結點，有輸入

LINKLISTAddNode(LINKLISTh)

LINKLISThead,pt,p;

pt二head二h;〃指向起始結點

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

printf(〃請輸入要添加的數據:〃）；

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

p->next=null;〃結點后繼指向空

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

結點

head=p;

else〃若不為空，將結點插在最

后

while(pt->next)

pt=pt->next;

pt->next=p;

returnhead;〃返回頭結點指針

)

*/

〃將結點插入到鏈表的指定位置

LINKLISTAddNode(LINKLISTh,inti,Eleme)

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

(

LINKLISThead,pt,p;

intj;

pt=head=h;

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

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

(

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

exit(l);

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

大于鏈表長度時

(

while(pt->next)

(

pt=pt->next;

)

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

p->data=e;〃向結點數據賦

值

p->next=null;〃結點后繼指

向空

pt->next=p;

)

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

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

p->data=e;〃向結點數據賦

值

p->next=null;〃結點后繼指

向空

head=p;

)

else〃參數正確且鏈表不為空時

(

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

(

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

p->data=e;〃向結點數據賦

值

p->next=pt;〃結點后繼指向

空

head=p;

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

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

p->data=e;〃向結點數據賦

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

pt=pt->next;

p->next=pt->next;

pt->next=p;

returnhead;〃返回頭結

點指針

〃刪除鏈表中的某位置結點

LINKLISTListDelete(LINKLISTh,inti)

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

LINKLISThead,pt;

intj=l;

pt=head=h;

if(h==null)〃空表

{

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

returnnull;

)

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

(

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

exit(1);

)

else//i合法，

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

head=pt->next;

free(pt);

else〃刪除中間節點或尾結點

while(j<i-l)

pt=pt->next;

j++；

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

returnhead;〃返回頭結點指針

〃鏈表是否為空

intListEmpty(LINKLISTh)

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

(

if(h==null)

return0;

return1;

)

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

ElemGetElem(LINKLISTh,inti)

〃返回結點的元素值

(

LINKLISTpt=h;

intj=l;

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

(

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

exit(l);

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

結點

(

pt=pt->next;

j++；

}

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

}

〃鏈表的逆置

LINKLISTInvert(LINKLISTh)

(

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

middle=null;

while(h)

{〃循環交換相鄰兩個的指針

指向

trail=middle;

middle』;

h=h->next;

middle->next二trail;

}

head=middle;〃將最后的結點變為鏈表頭

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