《數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)》教學(xué)參考模塊2

模塊2線(xiàn)性表

教學(xué)要求：

（1）了解線(xiàn)性表的定義，熟練掌握線(xiàn)性表的操作。

（2）掌握線(xiàn)性表的順序存儲(chǔ)。

（3）掌握線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)。

教學(xué)重點(diǎn)：

線(xiàn)性表的順序存儲(chǔ)及其基本操作；線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)及其基本操作。

教學(xué)難點(diǎn)：

線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

課時(shí)安排：

本模塊安排8課時(shí)。其中，理論講授4課時(shí)，上機(jī)實(shí)驗(yàn)4課時(shí)。

教學(xué)大綱：

模塊2線(xiàn)性表

案例導(dǎo)入

案例分析

相關(guān)知識(shí)

2.1線(xiàn)性表的定義與操作

2.1.1線(xiàn)性表的定義

2.1.2線(xiàn)性表的操作

2.2線(xiàn)性表的順序存儲(chǔ)

2.2.1順序表

2.2.2順序表上基本運(yùn)算的實(shí)現(xiàn)

2.2.3順序表基本運(yùn)算的算法

2.3線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)

2.3.1線(xiàn)性單鏈表

2.3.2線(xiàn)性表上基本運(yùn)算的實(shí)現(xiàn)

2.3.3其他形式的鏈表

案例實(shí)施

案例總結(jié)

思考與練習(xí)

主要概念：

1.第一元素

2.最后元素

3.線(xiàn)性表

4.記錄（結(jié)點(diǎn)）

5.文件

6.線(xiàn)性表的特性

7.線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型

8.順序表

9.順序表的初始化操作

10.順序表的插入操作

11.順序表的刪除操作

12.鏈表

13.頭結(jié)點(diǎn)

14.單鏈表

15.單鏈表的建立操作

16.單鏈表的查找操作

17.單鏈表的插入操作

18.單鏈表的刪除操作

19.循環(huán)鏈表

20.循環(huán)鏈表的基本操作

21.雙向鏈表

22.雙循環(huán)鏈表

23.雙向鏈表的插入操作

24.雙向鏈表的刪除操作

實(shí)驗(yàn)：

實(shí)驗(yàn)編寫(xiě)程序求解問(wèn)題，掌握線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)（4課時(shí)）

狐貍逮兔子問(wèn)題：圍繞著山頂有10個(gè)圓形排列的洞，狐貍要吃兔子，兔子說(shuō)：“可以，但必

須找到我，我就藏身于這十個(gè)洞中，你先到1號(hào)洞找，第二次隔1個(gè)洞（即3號(hào)洞）找，第

三次隔2個(gè)洞（即6號(hào)洞）找，以后如此類(lèi)推，次數(shù)不限?！钡倧脑绲酵磉M(jìn)進(jìn)出出了1000

次，仍沒(méi)有找到兔子。編寫(xiě)算法找出兔子究竟藏在哪個(gè)洞里，并用程序語(yǔ)言實(shí)現(xiàn)算法？（提

示：這實(shí)際上是一個(gè)反復(fù)查找線(xiàn)性表的過(guò)程。）

【數(shù)據(jù)描述】

定義一個(gè)順序表，用具有10個(gè)元素順序表來(lái)表示這10個(gè)洞。每個(gè)元素分別表示圍著山頂?shù)?/p>

一個(gè)洞，下標(biāo)為洞的編號(hào)。

#defineLIST_INIT_SIZE10〃線(xiàn)性表存儲(chǔ)空間的初始分配量

typedefstruct{

ElemType*elem;〃存儲(chǔ)空間基址

intlength;〃當(dāng)前長(zhǎng)度

intlistsize;〃當(dāng)前分配的存儲(chǔ)容量（以sizeof（ElemType）為單位）

}SqList;

【算法描述】

statusInitListSq(SqList&L){〃構(gòu)造一個(gè)線(xiàn)性表L

L.elem=(ElemType)malloc(LIST_INIT_SIZE*sizeof(ElemType));

If(!L.elem)returnOVERFLOW;〃存儲(chǔ)分配失敗

L.length=0;//空表長(zhǎng)度為0

L.listsize=LISTINIT_SIZE;〃初始存儲(chǔ)容量

returnOK;

}//InitList_Sq

statusRabbit(SqList&L){//構(gòu)造狐貍逮兔子函數(shù)

intcurrents：〃定義一個(gè)當(dāng)前洞口號(hào)的記數(shù)器，初始位置為第一個(gè)洞口

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

L.elem[i]=l;〃給每個(gè)洞作標(biāo)記為1,表示狐貍未進(jìn)之洞

L.elem[LIST_INIT_SIZE-l>L.elem[0]=0;〃首先進(jìn)入第一個(gè)洞，標(biāo)記進(jìn)過(guò)的洞為0。

for(i=2;i<=1000;i++){

current=(current+i)%LIST_INIT_SIZE;//實(shí)現(xiàn)順序表的循環(huán)引用

L.elem[i]=0;〃標(biāo)記進(jìn)過(guò)的洞為0

}〃第二次隔1個(gè)洞找，第三次隔2個(gè)洞找，以后如此類(lèi)推，經(jīng)過(guò)一千次

printf（"兔子可能藏在如下的洞中：”）

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

if(L.elem[i]==l)

printf(w第/d個(gè)洞\n”,i+D;〃輸出未進(jìn)過(guò)的洞號(hào)

returnOK;

}//end

【源代碼】

ftinclude<stdio.h>

#include<stdlib.h>

^defineOK1

#defineOVERFLOW-2

typedefintstatus;

typedefintElemType;

^defineLISTINIT_SIZE10〃線(xiàn)性表存儲(chǔ)空間的初始分配量

typedefstruct{

ElemType*elem;〃存儲(chǔ)空間基址

intlength;〃當(dāng)前長(zhǎng)度

intlistsize;〃當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為

單位)

}SqList;

statuslnitList_Sq(SqList禮){//構(gòu)造一個(gè)線(xiàn)性表L

(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!((*L).elem))returnOVERFLOW;〃存儲(chǔ)分配失敗

(*L).lengths;〃空表長(zhǎng)度為0

(*L).listsize=LIST_INIT_SIZE;〃初始存儲(chǔ)容量

returnOK;

}//InitList_Sq

statusRabbit(SqList*L){〃構(gòu)造狐貍逮兔子函數(shù)

inti,current=0;〃定義一個(gè)當(dāng)前洞口號(hào)的記數(shù)器，初始位置為第一個(gè)洞口

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

(*L).elem[i]=1;〃給每個(gè)洞作標(biāo)記為1,表示狐貍未進(jìn)之洞

(*L).elem[LISTINIT_SIZE-1]=O;

(*L).elem[O]=O;//第一次進(jìn)入第一個(gè)洞，標(biāo)記進(jìn)過(guò)的洞為0

for(i=2;i<=1000;i++){

current=(current+i)%LIST_INITSIZE;〃實(shí)現(xiàn)順序表的循環(huán)引用

(*L).elem[current]=O;〃標(biāo)記進(jìn)過(guò)的洞為0

}〃第二次隔1個(gè)洞找，第三次隔2個(gè)洞找，以后如此類(lèi)推,經(jīng)過(guò)一千次

printf("\n兔子可能藏在如下的洞中：");

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

if((*L).elem[i]==l)

printfC\n此洞是第%d號(hào)洞”，i+1);〃輸出未進(jìn)過(guò)的洞號(hào)

returnOK;

)

voidmain0

(

SqList