《数据结构与算法(C语言版)》教学参考模块2

模块2线性表

教学要求：

（1）了解线性表的定义，熟练掌握线性表的操作。

（2）掌握线性表的顺序存储。

（3）掌握线性表的链式存储。

教学重点：

线性表的顺序存储及其基本操作；线性表的链式存储及其基本操作。

教学难点：

线性表的链式存储结构。

课时安排：

本模块安排8课时。其中，理论讲授4课时，上机实验4课时。

教学大纲：

模块2线性表

案例导入

案例分析

相关知识

2.1线性表的定义与操作

2.1.1线性表的定义

2.1.2线性表的操作

2.2线性表的顺序存储

2.2.1顺序表

2.2.2顺序表上基本运算的实现

2.2.3顺序表基本运算的算法

2.3线性表的链式存储

2.3.1线性单链表

2.3.2线性表上基本运算的实现

2.3.3其他形式的链表

案例实施

案例总结

思考与练习

主要概念：

1.第一元素

2.最后元素

3.线性表

4.记录（结点）

5.文件

6.线性表的特性

7.线性表的抽象数据类型

8.顺序表

9.顺序表的初始化操作

10.顺序表的插入操作

11.顺序表的删除操作

12.链表

13.头结点

14.单链表

15.单链表的建立操作

16.单链表的查找操作

17.单链表的插入操作

18.单链表的删除操作

19.循环链表

20.循环链表的基本操作

21.双向链表

22.双循环链表

23.双向链表的插入操作

24.双向链表的删除操作

实验：

实验编写程序求解问题，掌握线性表的存储结构（4课时）

狐狸逮兔子问题：围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必

须找到我，我就藏身于这十个洞中，你先到1号洞找，第二次隔1个洞（即3号洞）找，第

三次隔2个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000

次，仍没有找到兔子。编写算法找出兔子究竟藏在哪个洞里，并用程序语言实现算法？（提

示：这实际上是一个反复查找线性表的过程。）

【数据描述】

定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的

一个洞，下标为洞的编号。

#defineLIST_INIT_SIZE10〃线性表存储空间的初始分配量

typedefstruct{

ElemType*elem;〃存储空间基址

intlength;〃当前长度

intlistsize;〃当前分配的存储容量（以sizeof（ElemType）为单位）

}SqList;

【算法描述】

statusInitListSq(SqList&L){〃构造一个线性表L

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

If(!L.elem)returnOVERFLOW;〃存储分配失败

L.length=0;//空表长度为0

L.listsize=LISTINIT_SIZE;〃初始存储容量

returnOK;

}//InitList_Sq

statusRabbit(SqList&L){//构造狐狸逮兔子函数

intcurrents：〃定义一个当前洞口号的记数器，初始位置为第一个洞口

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

L.elem[i]=l;〃给每个洞作标记为1,表示狐狸未进之洞

L.elem[LIST_INIT_SIZE-l>L.elem[0]=0;〃首先进入第一个洞，标记进过的洞为0。

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

current=(current+i)%LIST_INIT_SIZE;//实现顺序表的循环引用

L.elem[i]=0;〃标记进过的洞为0

}〃第二次隔1个洞找，第三次隔2个洞找，以后如此类推，经过一千次

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

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

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

printf(w第/d个洞\n”,i+D;〃输出未进过的洞号

returnOK;

}//end

【源代码】

ftinclude<stdio.h>

#include<stdlib.h>

^defineOK1

#defineOVERFLOW-2

typedefintstatus;

typedefintElemType;

^defineLISTINIT_SIZE10〃线性表存储空间的初始分配量

typedefstruct{

ElemType*elem;〃存储空间基址

intlength;〃当前长度

intlistsize;〃当前分配的存储容量(以sizeof(ElemType)为

单位)

}SqList;

statuslnitList_Sq(SqList礼){//构造一个线性表L

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

if(!((*L).elem))returnOVERFLOW;〃存储分配失败

(*L).lengths;〃空表长度为0

(*L).listsize=LIST_INIT_SIZE;〃初始存储容量

returnOK;

}//InitList_Sq

statusRabbit(SqList*L){〃构造狐狸逮兔子函数

inti,current=0;〃定义一个当前洞口号的记数器，初始位置为第一个洞口

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

(*L).elem[i]=1;〃给每个洞作标记为1,表示狐狸未进之洞

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

(*L).elem[O]=O;//第一次进入第一个洞，标记进过的洞为0

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

current=(current+i)%LIST_INITSIZE;〃实现顺序表的循环引用

(*L).elem[current]=O;〃标记进过的洞为0

}〃第二次隔1个洞找，第三次隔2个洞找，以后如此类推,经过一千次

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

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

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

printfC\n此洞是第%d号洞”，i+1);〃输出未进过的洞号

returnOK;

)

voidmain0

(

SqList