《数据结构与算法(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其他形式的链表案例实施案例总结思考与练习主要概念：.第一元素.最后兀素.线性表.记录（结点）.文件.线性表的特性.线性表的抽象数据类型.顺序表.顺序表的初始化操作.顺序表的插入操作.顺序表的删除操作.链表.头结点.单链表.单链表的建立操作.单链表的查找操作.单链表的插入操作.单链表的删除操作.循环链表.循环链表的基本操作.双向链表.双循环链表.双向链表的插入操作.双向链表的删除操作实验：实验编写程序求解问题，掌握线性表的存储结构（4课时）狐狸逮兔子问题：围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到1号洞找，第二次隔1个洞（即3号洞）找，第三次隔2个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。编写算法找出兔子究竟藏在哪个洞里，并用程序语言实现算法？（提示：这实际上是一个反复查找线性表的过程。）【数据描述】定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。ttdefineLIST_INIT_SIZE10〃线性表存储空间的初始分配量typedefstructElemType*elem;//存储空间基址intlength;intlength;〃当前长度intlistsize;〃当前分配的存储容量（以sizeof（ElemType）为单位）}SqList;【算法描述】statusInitList_Sq(SqList&L){〃构造一个线性表LL.elem=(ElemType)malloc(LISTINITSIZE^sizeof(ElemType));If(!L.elem)returnOVERFLOW;〃存储分配失败Llength^;〃空表长度为0L.listsize=LIST_INIT_SIZE;〃初始存储容量returnOK;}//InitList_SqstatusRabbit(SqList&L){〃构造狐狸逮兔子函数intcurrent=0;〃定义一个当前洞口号的记数器，初始位置为第一个洞口for(i=0;i<LIST_INIT_SIZE;i++)Lelem[i]=l;〃给每个洞作标记为1,表示狐狸未进之洞L.elem[LIST_INIT_SIZE-l]=Lelem[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);returnOK;}//end【源代码】for(i=0;i<LIST_INIT_SIZE;i++)if(L.elem[i]=l)printf(“第%(1个洞\n"，i+1);returnOK;}//end【源代码】〃输出未进过的洞号ttinclude<stdio.h>ttinclude<stdlib.h>ttdefineOK1ttdefineOVERFLOW-2typedefintstatus;typedefintElemType;#defineLIST_INIT_SIZE10typedefstruct{ElemType*elem;〃线性表存储空间的初始分配量〃存储空间基址intlength;〃当前长度intlistsize;intlistsize;〃当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;statusInitList_Sq(SqList*L){〃构造一个线性表L(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!((*L).elem))returnOVERFLOW;〃存储分配失败(礼)