數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-實(shí)驗(yàn)2：線性表的順序及鏈?zhǔn)酱鎯?chǔ)

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

學(xué)號(hào)：姓名：班級(jí)：成績：

實(shí)驗(yàn)名稱：線性表的順序及鏈?zhǔn)酱鎯?chǔ)實(shí)驗(yàn)地點(diǎn)：數(shù)學(xué)系機(jī)房

所使用的工具軟件及環(huán)境：VC++

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

1）通過本實(shí)驗(yàn)，掌握線性表的順序存儲(chǔ)和鏈接存儲(chǔ)的表示方法

2）并能在線性結(jié)構(gòu)的基本操作的基礎(chǔ)上，設(shè)計(jì)合適的算法解決實(shí)際問題

2.評(píng)分標(biāo)準(zhǔn)：

3.評(píng)分成績?yōu)锳,B,C,D,E五檔，滿分為A

1）單選題：每錯(cuò)3個(gè)小題，總分降一檔。

2）填空題：每錯(cuò)2個(gè)小題，總分降一檔。

3）程序填空：每錯(cuò)1空，總分降一檔。

4）補(bǔ)交作業(yè)成績降一檔

5）抄襲成績?yōu)榱悖也粶?zhǔn)補(bǔ)交

一、實(shí)驗(yàn)內(nèi)容（1）：

（一）單選題

1、在一個(gè)長度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素（lWiWn+1）之前插入一個(gè)新元素時(shí)，

需要從后向前依次移個(gè)元素。

An-iBn-i+1Cn-i-1Di

2、除了,其它任何指針都不能在算法中作為常量出現(xiàn)，也無法顯示。

A頭指針B尾指針C指針型變量D空指針

3、在一個(gè)長度為n的線性表中順序查找值為x的元素時(shí)，查找成功的平均查找長度（即x

同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為。

AnBn/2C（n+l）/2D（n-l）/2

4、在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)自由指針p指向的結(jié)點(diǎn)，則執(zhí)行。

AHL=p;p->next=HL;Bp->next=HL;HL=p;

Cp->next=HL;p=HL;Dp->next=HL->next;HL->next=p;

5、在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)自由指針p所指向的結(jié)點(diǎn),

則執(zhí)行。

Aq->next=p->next;p->next=q;Bp->next=q->next;q=p;

Cq->next=p->next;p->next=qDp->next=q->next;q->next=p;

6、在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行o

Ap=q->next;p->next=q->next;Bp=q->next;q->next=p;

Cp=q->next;q->next=p->next;Dq->next=q=->next->next;q->next=q;

7、對于順序表，下面說法錯(cuò)誤的是。

A順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址

B順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列

C順序表的特點(diǎn)是:邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰

D順序表的特點(diǎn)是:邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中；

(二)填空題

1.線性表典型的基本運(yùn)算包括：、、、、、等六

種。

2.對于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為,在表

尾插入元素的時(shí)間復(fù)雜度為。

3.線性結(jié)構(gòu)的基本特征是:若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接外，其他

結(jié)點(diǎn)有且僅有一個(gè)直接:除終端結(jié)點(diǎn)沒有直接外，其它結(jié)點(diǎn)有且僅有一

個(gè)直接。

4.在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p,則后繼結(jié)點(diǎn)的地址為

,若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為o

5.在循環(huán)單鏈接表中，最后一個(gè)結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)。

6.在雙向鏈接表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)針域，一個(gè)指向其點(diǎn)，另一個(gè)指向其

結(jié)點(diǎn)。

7.在循環(huán)雙向鏈接表中表頭結(jié)點(diǎn)的左指針域指向結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右指針域指

向結(jié)點(diǎn)。

8.在由數(shù)組a中元素結(jié)點(diǎn)構(gòu)成的單鏈表中，在下標(biāo)為i的結(jié)點(diǎn)的后面插入一個(gè)下標(biāo)為j的

結(jié)點(diǎn)時(shí)，需要進(jìn)行的操作為。

(三)實(shí)驗(yàn)內(nèi)容(2):順序表的實(shí)現(xiàn)-程序填空，

(1)創(chuàng)建順序表

(2)在順序表的第i位插入元素

(3)刪除順序表的第i個(gè)元素

(4瀚出順序表

(5)判斷順序表是否為空

(6)判斷順序表是否滿

(7)求順序表第i個(gè)元素的值

(8)查找值為x的元素

#include<stdio.h>

#include<malloc.h>

#defineMaxSize100

typedefintdataType;

typedefstruct{

dataTypedata[MaxSize];

intsize;

}SqList;

〃創(chuàng)建順序表

SqList*CreateList(){

SqList*t=(SqList*)malloc(sizeof(SqList));

t->size=0;

returnt;

)

//在順序表的第k個(gè)位置插入元素X

voidInsert(SqList*1,intk,dataTypex){

if(k<1||k>l->size+1)exit(l);

if(l->size==MaxSize)exit(l);

for(inti=l->size;i>=k;i—)

l->data[i]=l->data[i-l];

l->data[k-l]=;

l->size++;

)

〃刪除順序表的第k個(gè)元素

voidDelete(SqList*1,intk){

if(k<1||k>l->size)exit(l);

fbr(inti=k;i<l->size;i++)

l->data[i-l]=;

l->size-;

)

〃判斷順序表是否為空

intEmpty(SqList*1){

returnl->size==0;

1

〃判斷順序表是否滿

intFull(SqList*1){

returnl->size==;

)

〃求順序表第i個(gè)元素的值

dataTypeGetData(SqList*1,inti){

if(i<1||i>l->size)exit(l);

returnl->data[];

)

〃查找值為x的元素

intLocate(SqList*1,dataTypex){

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

if(l->data[i]x)

returni+1;

return0;

)

〃輸出順序表

voidPrint(SqList*1){

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

printf(H%d",l->data[i]);

printf(n\nK);

)

intmain(){

SqList*pl=CreateList();

Insert(pl,1,10);

Insert(pl,