
《数据结构与算法(C语言版)》教学参考模块2.docx
6页模块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 structElemType *elem;//存储空间基址int length;int length;〃当前长度int listsize;〃当前分配的存储容量(以sizeof (ElemType)为单位)}SqList;【算法描述】status InitList_Sq(SqList &L) { 〃构造一个线性表 LL. elem=(ElemType )malloc(LIST INIT SIZE^sizeof(ElemType));If(!L. elem) return OVERFLOW; 〃存储分配失败L length^;〃空表长度为0L. listsize=LIST_INIT_SIZE;〃初始存储容量return OK;} //InitList_Sqstatus Rabbit (SqList &L) {〃构造狐狸逮兔子函数int current=0;〃定义一个当前洞口号的记数器,初始位置为第一个洞口for(i=0;i for(i=2;iC1000;i++) {current= (current+i) %LIST_INIT_SIZE;〃实现顺序表的循环引用L. elem[i]=0; 〃标记进过的洞为0}//第二次隔1个洞找,第三次隔2个洞找,以后如此类推,经过一千次printf(〃兔子可能藏在如下的洞中:〃)for(i=0;i
