华师本科生数据结构课件第2章线性表.ppt
《华师本科生数据结构课件第2章线性表.ppt》由会员分享,可在线阅读,更多相关《华师本科生数据结构课件第2章线性表.ppt(89页珍藏版)》请在启牛文库网上搜索。
1、第二章 线性表,线性表是最简单、也是最基本的一种线性数据结构。其存储表示法主要有两种:顺序存储结构和链式存储结构。这一部分内容和方法掌握了,有助于理解和掌握后续章节的内容,如栈队列串是特殊的线性表,数组和广义表是线性表的扩展;有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法,因为树和图的存储结构大多或是这两种存储结构的扩充,或是它们的组合,因此这一章的内容非常重要,同学们要很好地学习理解和掌握。,学习的意义:,2.1 线性表的类型定义 2.4 有序表 2.1.1 线性表的定义 2.5 顺序表和链表的综合比较 2.1.2 线性表的基本操作2.2 线性表的顺序表示和实现 2
2、.2.1 顺序表线性表的顺序存储表示 2.2.2 顺序表中基本操作的实现 2.2.3 顺序表其他算法举例2.3 线性表的链式表示和实现 2.3.1 单链表和指针 2.3.2 单链表的基本操作 2.3.3 单链表的其他基本操作 2.3.4 循环链表 2.3.5 双向链表,主要内容:,线性表是n 个类型相同数据元素的有限序列,表中相邻的数据元素之间存在“序偶”关系。通常记作(a1,a2,a3,an)。,姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555.,2.1 线性表的类型定义,例1、数学中的数列(11,13
3、,15,17,19,21)例2、英文字母表(A,B,C,D,E Z)。例3、某单位的电话号码簿。,2.1.1 线性表的定义,2.1.1 线性表的定义,特性:设 A=(a1,a2,.,ai-1,ai,ai+1,an)是一线性表 线性表的数据元素可以是各种各样的,但同一线性表中的元素必须是同一 类型的;在表中 ai-1 领先于ai,ai 领先于ai+1,称ai-1 是ai 的直接前驱,ai+1 是ai 的直 接后继;在线性表中,除第一个元素和最后一个元素之外,其他元素都有且仅有 一个直接前驱,有且仅有一个直接后继,具有这种结构特征的数据结构 称为线性结构。线性表是一种线性数据结构;线性表中元素的个
4、数n 称为线性表的长度,n=0 时称为空表;ai是线性表的第i 个元素,称i 为数据元素ai 的序号,每一个元素在线性表 中的位置,仅取决于它的序号;,2.1.1 线性表的定义,1、二元组表示 L=,其中:D=a1,a2,a3,,.,an S=R R=,线性表的其他表示方式:,2.1.2 线性表的基本操作,1.初始化线性表L InitList(&L)2.销毁线性表L DestoryList(&L)3.清空线性表L ClearList(&L)4.求线性表L的长度 ListLength(L)5.判断线性表L是否为空 ListEmpty(L)6.获取线性表L中的某个数据元素内容 GetElem(L,
5、i,&e)7.检索值为e的数据元素 LocateELem(L,e)8.返回线性表L中cur_e的直接前驱元素 PriorElem(L,cur_e,&pre_e)9.返回线性表L中cur_e的直接后继元素 NextElem(L,cur_e,&next_e)在线性表L中插入一个数据元素 ListInsert(&L,i,e)(1i ListLength(L)+1)删除线性表L中第i个数据元素 ListDelete(&L,i,&e)(1i ListLength(L)12.输出线性表L中的每个数据元素 ListTraverse(L),2.1.2 线性表的基本操作,说明:1、上面列出的操作,只是线性表的一
6、些常用的基本操作;2、不同的应用,基本操作可能是不同的;3、线性表的复杂操作可通过基本操作实现;,2.1.2 线性表的基本操作,【例2-1】假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下:ListLength(L);GetElem(L,i,e)PriorElem(L,x,&pre_x)NextElem(L,x,&next_x)LocateElem(L,x)ListInsert(&L,i,y)ListDelete(&L,i+1,&e),/结果为5,/e的值为89,/pre_x的值为23,/next_x的值为89,/结果为2,/所得结果为(2
7、3,56,88,89,76,18),/所得结果为(23,56,88,76,18)e的值为89,2.1.2 线性表的基本操作,【例2-2】利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AB。,【分析】这个问题相当于对线性表作如下操作:扩大线性表La,将存在于线性表Lb中而不存在于线性表La中的数据元素插入到线性表La中去。,【具体步骤】(1)从线性表Lb中取得一个数据元素;(2)依该数据元素的值在线性表La中进行查访;(3)若线性表La中不存在和其值相同的数据元素,则将从Lb中删除的这个数据元素插入到线性表La中;(4)重复以上操作直至Lb为空表。,2.1.2 线性表的基
8、本操作,【例2-2】利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AB。,【具体算法】void union(List/销毁线性表Lb,该算法运行完后,线性表Lb被销毁!如果要求Lb保持原先的值,算法又如何写?,【具体算法】_运行后Lb仍保持原先的值 void union(List/将该元素e插入到La中最后一个元素后,2.1.2 线性表的基本操作,【例2-3】已知一个非纯集合(即集合B中可能有相同元素),试构造一个纯集合A,使中只包含B中所有值各不相同的成员。,【分析】假设仍以线性表表示集合,则此问题和例2-2类似,即构造线性表La,使其只包含线性表Lb中所有值不相同的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 本科生 数据结构 课件 线性