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

模块2线性表
教学要求：
(1) 了解线性表的定义，熟练掌握线性表的操作。
(2)掌握线性表的顺序存储。
(3)掌握线性表的链式存储。
教学重点：
线性表的顺序存储及其基本操作；线性表的链式存储及其基本操作。
教学难点：
线性表的链式存储结构。
课时安排：
本模块安排8课时。其中，理论讲授4课时，上机实验4课时。
教学大纲：
模块2线性表
案例导入
案例分析
相关知识
2.1线性表的定义与操作
2. 1. 1线性表的定义
2. 1.2线性表的操作
2.2线性表的顺序存储
2. 2. 1顺序表
顺序表上基本运算的实现
顺序表基本运算的算法
2.3线性表的链式存储
2. 3. 1线性单链表
线性表上基本运算的实现
2. 3. 3其他形式的链表
案例实施
案例总结
思考与练习主要概念：
1 .第一元素.最后兀素
2 .线性表.记录（结点）
3 .文件.线性表的特性
4 .线性表的抽象数据类型.顺序表
5 .顺序表的初始化操作.顺序表的插入操作
6 .顺序表的删除操作.链表
7 .头结点.单链表
8 .单链表的建立操作.单链表的查找操作
9 .单链表的插入操作.单链表的删除操作
10 .循环链表.循环链表的基本操作
11 .双向链表.双循环链表
12 .双向链表的插入操作.双向链表的删除操作
实验：
实验 编写程序求解问题，掌握线性表的存储结构（4课时）狐狸逮兔子问题：围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必
须找到我，我就藏身于这十个洞中，你先到1号洞找，第二次隔1个洞（即3号洞）找，第三次隔2个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了 1000 次，仍没有找到兔子。编写算法找出兔子究竟藏在哪个洞里，并用程序语言实现算法？（提 示：这实际上是一个反复查找线性表的过程。）
【数据描述】定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的 一个洞，下标为洞的编号。
ttdefine LIST_INIT_SIZE 10 〃线性表存储空间的初始分配量typedef struct
ElemType *elem;
//存储空间基址
int length;

int length;
〃当前长度

int listsize;
〃当前分配的存储容量（以sizeof （ElemType）为单位）}SqList;
【算法描述】status InitList_Sq(SqList &L) { 〃构造一个线性表 L
L. elem=(ElemType )malloc(LIST INIT SIZE^sizeof(ElemType));
If(!L. elem) return OVERFLOW; 〃存储分配失败
L length^;〃空表长度为0L. listsize=LIST_INIT_SIZE;〃初始存储容量
return OK;} //InitList_Sq
status Rabbit (SqList &L) {〃构造狐狸逮兔子函数
int current=0;〃定义一个当前洞口号的记数器，初始位置为第一个洞口
for(i=0;i<LIST_INIT_SIZE;i++)Lelem[i]=l;〃给每个洞作标记为1,表示狐狸未进之洞
L. elem[LIST_INIT_SIZE-l]=L elem[0]=0;〃首先进入第一个洞,标记进过的洞为0。 for(i=2;iC1000;i++) {current= (current+i) %LIST_INIT_SIZE;〃实现顺序表的循环引用
L. elem[i]=0; 〃标记进过的洞为0}//第二次隔1个洞找，第三次隔2个洞找，以后如此类推,经过一千次
printf（〃兔子可能藏在如下的洞中：〃）for(i=0;i<LIST_INIT_SIZE;i++) if (L. elem[i] = l)
printf(“第%(1 个洞\n "，i+1);
return OK;
}//end
【源代码】

for(i=0;i<LIST_INIT_SIZE;i++) if (L. elem[i] = l)
printf(“第%(1 个洞\n "，i+1);
return OK;
}//end
【源代码】
〃输出未进过的洞号
ttinclude <stdio.h>
ttinclude <stdlib. h>
ttdefine OK 1
ttdefine OVERFLOW -2
typedef int status;
typedef int ElemType;
#define LIST_INIT_SIZE 10
typedef struct {
ElemType *elem;
〃线性表存储空间的初始分配量
〃存储空间基址
int length;
〃当前长度
int listsize;

int listsize;
〃当前分配的存储容量(以sizeof (ElemType)为单位)
}SqList;status InitList_Sq(SqList *L) { 〃构造一个线性表 L
(*L). elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (! ((*L). elem)) return OVERFLOW;〃存储分配失败
(礼).length^;〃空表长度为0(*L). listsize-LIST_INIT_SIZE; 〃初始存储容量
return 0K;} //InitList_Sq status Rabbit (SqList *L) {〃构造狐狸逮兔子函数
int i, current=0; 〃定义一个当前洞口号的记数器，初始位置为第一个洞口
for(i=0;i<LIST_INITJIZE;i++)〃给每个洞作标记为1,表示狐狸未进之洞
(*L). elemELIST_INIT_SIZE-l]=O;
(*L). elem[O]=O;〃第一次进入第一个洞，标记进过的洞为0for(i=2;i<=1000;i++) {
current= (current+i) %LIST_INIT_SIZE; //实现顺序表的循环引用(*L). elem[current]=O; 〃标记进过的洞为 0
}〃第二次隔1个洞找，第三次隔2个洞找，以后如此类推,经过一千次
printf(〃\n兔子可能藏在如下的洞中：〃);
for(i=0;i<LIST_INIT_SIZE;i++)if((*L). elem[i]==l)
printfC \n此洞是第%01号洞〃，i+1); 〃输出未进过的洞号return OK;
)void main()
(SqList *L;
InitList_Sq(L);Rabbit(L);
getch ();)
【运行结果】最后的输出结果为：2 4 7 9
【实验总结】本算法思路比拟简单，采用了顺序表表示围着山顶的10个洞，首先对所有洞设置标志为1, 然后通过1000次循环，对每次所进之洞修改标志为0,最后输出标志为1的洞。