数据结构讲义第2章.ppt

第二章线性表线性结构的特点：在数据元素的非空有限集中存在唯一的一个被称做“第一个”的数据元素；存在唯一的一个被称做“最后一个”的数据元素；除第一个之外，每个元素都只有一个前驱；除最后一个之外，每个元素都只有一个后继。2.1线性表的逻辑结构线性表是一种最简单的数据结构，它是一种线性结构。线性表是n(n≥0)个数据元素的有限序列，通常记为： (a1，a2，…ai-1，ai，ai+1，…an) 其中:同一线性表中的数据元素必须具有相同数据类型，ai是线性表的第i个元素，称i为数据元素ai的序号相邻数据元素间存在序偶关系： 将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。 a1是表中第一个元素，它没有前趋； an是最后一个元素无后继； 其余有且仅有一个直接前趋，有且仅有一个直接后继n为表长，n＝0时称为空表（）。线性表的数据元素，或者叫结点，或者叫记录，是独立的信息。 它可以是一个数：例某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用线性表表示为：（6，17，28，50，92，188） 或一个符号，如英文字母表（A，B，…，Z）； 也可以由若干个数据项组成：如：学生健康情况登记表如下：线性表的基本操作：表的初始化存取操作：存、取线性表中第i个数据元素查找操作：在线性表中查找满足条件元素插入操作：在线性表的第i个元素之前插入删除操作：删除线性表的第i个元素遍历求表长说明： (1)上面列出的操作，只是线性表的一些常用的基本操作； (2)线性表的复杂操作可通过基本操作实现。 2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现顺序表的定义：二顺序表上的基本操作插入功能：在顺序表v中的第i(1=i=n+1)个数据元素之前插入一个新元素x,插入前线性表为(a1,a2,a3,…,ai-1,ai,,…an) 插入后,线性表长度为n+1,线性表为(a1,a2,a3,…,ai-1,x,ai,,…an)插入操作示意图采用定义：顺序表插入算法分析平均移动数据元素的次数： 这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度T(n)＝Ｏ(n)。 功能：在顺序表删除第i(1=i=n+1)个数据元素，将被删除元素值存入e,删除前线性表为(a1,a2,a3,…,ai-1,ai,,…an) 删除后,线性表长度为n－1,线性表为(a1,a2,a3,…,ai-1,ai+1,…an)删除操作示意图顺序表删除算法分析设删除第i个元素的概率为Pi，当Pi=1/n，即为等概率情况，则平均移动数据元素的次数： 这说明：在顺序表上做删除操作需移动表中一半的数据元素。显然时间复杂度T(n)＝Ｏ(n)。3.初始化空表三顺序表应用举例设有两个按元素值递增有序排列的顺序表A和B，请编写算法将A和B归并成一个按元素值递增有序排列的线性表C。小结2.3线性表的链式表示和实现由于顺序表的存贮特点是用物理上的相邻实现了逻辑上的相邻，优点是可以随机存取，但插入和删除操作会移动大量的结点。本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。2.3.1线性链表

一线性链表的概念

二线性链表的基本操作算法

三线性链表的其它操作2.3.2循环链表

2.3.3双向链表

一双向链表的概念

二双向链表的基本操作算法2.3.1线性链表2.3.1线性链表2.3.1线性链表2.3.1线性链表2.3.1线性链表建立链表例：线性表（25,45,18,76,29）之链表的建立过程。建立链表2.查找(1)按序号查找LinklistGet_LinkList(LinkListL,inti)(2)按值查找Locate_LinkList(L,x)LinklistLocate_LinkList(LinkListL,elemtypex)3.插入(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插