冯毅《数据结构》ppt课件.ppt

《冯毅《数据结构》ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实例线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构下一章第二章线性表线性表的应用举例顺序表与链表比较书目自动检索系统书目文件1、各条书目信息之间存在一个对一个的线性关系2、如何在计算机中存储书目信息3、数据操作：查找，插入，删除，修改等线性表实例约瑟夫环(JosephCircle)问题描述：编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，

2、从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。请编写程序求出圈的顺序。45961573182132245例：m：密码k：计数出队序列：start526743k=1311、各元素之间存在一个对一个的线性关系2、如何在计算机中存储3、数据操作：查找，删除等约瑟夫环(JosephCircle)在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素

3、均只有一个后继线性结构特点定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素特征：有限、序列、同构元素个数n—表长度，n=0空表1

4、aiElemSet,i=1,2,…,n,n≥0},n—表长,n=0,空表数据关系：R={

5、ai-1，aiD,

6、i=2，…，n},i为ai在线性表中位序基本操作：结构初始化操作结构销毁操作引用型操作(只读操作)加工型操作(修改操作)}ADTList线性表的抽象数据类型定义初始化操作：InitList(&L)操作结果：构造一个空线性表L结构销毁操作：DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表L引用型操作：ListEmpty(L)//线性表判空初始条件：线性表L已存在操作结果：若L为空表，返回TRUE;否则返回FALSEListLength(L)//求线性表的表长初始条件：线性表L已存在操作结

7、果：返回L中数据元素个数GetElem(L,i,&e)//求线性表的第i个元素初始条件：线性表L已存在，且1≤i≤ListLength(L)操作结果：用e返回L中第i个数据元素的值线性表的抽象数据类型定义引用型操作：LocateElem(L,e,compare())//定位函数初始条件：线性表L已存在，compare()是元素判定函数操作结果：返回L中第1个与e满足关系compare()的元素的位序。PriorElem(L,cur_e,&pre_e)//求数据元素的前驱初始条件：线性表L已存在操作结果：若cur

8、_e是L中元素，且不是第一个，则用pre_e返回其前驱；否则操作失败，pre_e无定义NextElem(L,cur_e,&next_e)//求数据元素的后继初始条件：线性表L已存在操作结果：若cur_e是L中元素,且不是最后一个,则用next_e返回其后继;否则操作失败，next_e无定义ListTraverse(L,visit())//线性表遍历初始条件：线性表L已存在,visit()为某个访问函数操作结果：依次对L中每个元素调用函数visit()。一旦visit()失败，则操作失败线性表的抽象数据类型定义加

9、工型操作：ClearList(&L)//线性表置空初始条件：线性表L已存在操作结果：将L重置为空表ListInsert(&L,i,e)//插入数据元素初始条件：线性表L已存在，且1≤i≤ListLength(L)+1操作结果：在L中第第i个位置之前插入元素e,L的长度加1ListDelete(&L,i,&e)//删除数据元素初始条件：线性表L已存在且非空，1≤i≤ListLength(L)操作结果：删除L的第i个元素,并用e返回其值,L的长度减1线性表的抽象数据类型定义线性表的顺序存储结构an……..ai…….

10、.a2a1LLOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现顺序表定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：length表长listsize表容量elem存储区首地址a1a2an