第2章 基本线性结构.ppt

第2章 基本线性结构 ⒈教学内容 线性表的逻辑结构、线性表的顺序存储、线性表的链式存储、顺序表和链表的比较;栈和队列的逻辑结构、存储实现及基本运算。 ⒉教学目的 理解线性表的定义及其运算,理解顺序表和链表的定义、组织形式、结构特征和类型说明,掌握在这两种表上实现的插入、删除和按值查找的算法,了解循环链表、双链表的结构特点;理解栈和队列的定义、特征及基本运算；掌握栈和队列的两种存储结构及基本运算的实现。 2015年12月10日 星期四 ⒊教学重点 ⒋教学难点 线性表与线性结构的联系与区别，头结点在链表中的作用、指针操作，删除、插入运算中的指针操作顺序，双链表上指针的操作顺序；顺序栈的溢出判断条件，循环队列的队空、队满判断条件，循环队列上的插入、删除操作。 2015年12月10日 星期四 线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。 线性表是最简单、最基本、也是最常用的线性结构，本章我们讨论这种最基本的线性结构， 线性表有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。 2.1 线性表的逻辑结构 2015年12月10日 星期四 2.1.1 问题的提出 问题1：日常生活中看到的学生花名册、学生的成绩单、通讯录、单位的职工工资表以及图书馆的图书目录等等，这些表单具有一个共同的特点，都是由一行行结构相同的数据构成。对这些表单经常进行的操作是修改、查找、插入和删除。 问题2：日常生活中我们将洗好的盘子由下而上摆放起来，使用的时候再从上至下依次取出，如果用计算机模拟这一过程，盘子之间的逻辑关系是线性结构，但处理盘子的摆放顺序需要遵循后摆放先取出的原则进行处理。 问题3：日常生活中排队购物、汽车进站出站、到银行办理业务等事务处理过程，如果用计算机模拟，一般情况是一个需要遵循先来先服务的处理原则的线性结构。 2015年12月10日 星期四 问题4：程序设计语言对函数嵌套调用的实现，需要保存调用点的数据，并按照调用的顺序后调用先返回。调用的过程是线性的，返回的过程也是线性的，只是返回的过程与调用的过程正好相反。 问题5：如何实现一元多项式的存储表示及加、减、乘等运算的实现。由于一元多项式的每一项都是由系数和指数构成，因此可将一元多项式抽象地表示为由系数和指数构成的序偶序列 ，各个序偶之间的逻辑关系是线性的，为便于运算，可以约定按照指数递增的顺序排列。 。。。。。。 2015年12月10日 星期四 2.1.2 线性表的定义 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。 2015年12月10日 星期四 2.1.3 线性表的基本运算 ⑴ 线性表初始化：Init_List(L) ⑵ 求线性表的长度：Length_List(L) ⑶ 取表元：Get_List(L,i) ⑷ 按值查找：Locate_List(L,x) ⑸ 插入操作：Insert_List(L,i,x) ⑹ 删除操作：Delete_List(L,i) 2015年12月10日 星期四 2.2.1 顺序表 顺序存储可以按序号随机访问每一个数据元素： 设 a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a１)+(i-1)*d 1≤i≤n 2.2 线性表的顺序存储与实现 2015年12月10日 星期四 用一维数组来示实现顺序表的数据存储区域。 可以是： datatype data[MAXSIZE]; int last; 2015年12月10日 星期四 从结构性上考虑，通常将 data 和 last 封装成一个结构: typedef struct { datatype data[MAXSIZE]; int last; } SeqList; 定义一个顺序表的存储变量： SeqList L; 通常用一个指向SeqList 类型的指针对实现顺序表的操作更为方便：SeqList *L; L是一个指针变量，通过“L=(SeqList )malloc(sizeof (SeqList));”