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

模塊2線性表

教學(xué)要求：

（1）了解線性表的定義，熟練掌握線性表的操作。

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

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

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

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

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

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

課時(shí)安排：

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

教學(xué)大綱：

模塊2線性表

案例導(dǎo)入

案例分析

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

2.1線性表的定義與操作

2.1.1線性表的定義

2.1.2線性表的操作

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

2.2.1順序表

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

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

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

2.3.1線性單鏈表

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

2.3.3其他形式的鏈表

案例實(shí)施

案例總結(jié)

思考與練習(xí)

主要概念：

1.第一元素

2.最后元素

3.線性表

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

5.文件

6.線性表的特性

7.線性表的抽象數(shù)據(jù)類型

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)編寫程序求解問題，掌握線性表的存儲(chǔ)結(jié)構(gòu)（4課時(shí)）

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

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

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

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

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

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

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

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

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

typedefstruct{

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

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

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

}SqList;

【算法描述】

statusInitListSq(SqList&L){〃構(gòu)造一個(gè)線性表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)過的洞為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)過的洞為0

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

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

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

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

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

returnOK;

}//end

【源代碼】

ftinclude<stdio.h>

#include<stdlib.h>

^defineOK1

#defineOVERFLOW-2

typedefintstatus;

typedefintElemType;

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

typedefstruct{

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

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

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

單位)

}SqList;

statuslnitList_Sq(SqList禮){//構(gòu)造一個(gè)線性表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)過的洞為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)過的洞為0

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

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

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

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

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

returnOK;

)

voidmain0

(

SqList