数据结构课件PPT110章全 第二章.ppt

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

1、第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加2.1线性表的逻辑结构线性表(LinearList)：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各

2、种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1

3、和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。1.[初值]获取线性表LA和LB2.[合并线性表]对于LB中的每一个元素做x如下操作：若（x不属于LA）则将x插入到LA的末尾3.[算法结束]算法2.2例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：1.[初值]获取

4、线性表LA和LB，并构造空线性表LC2.[选择插入元素]对于线性表LA和LB，都从其第一个元素开始做如下操作直到其中一个线性表元素全部遍历完毕：若（LA的元素a<=LB的元素b）则将元素a插入到LC的末尾，并选择LA中的下一个元素a否则将元素b插入到LC的末尾，并选择LB中的下一个元素b3.[补充剩下的元素]若（LA还有剩余元素）则将LA的剩余元素全部插入到LC末尾若（LB还有剩余元素）则将LB的剩余元素全部插入到LC末尾4.[算法结束]2.2线性表的顺序存储结构2.2.1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假

5、设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。这是一个动态分配的一维数组：#defineLIST_INIT_SIZE100#defineLI

6、STINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}Sqlist;初始化顺序存储的线性表StatusInitList_Sq(SqList&L){//构造一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.Listsize=LIST_INIT_SIZE;returnOK;}2.2.2顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作

7、，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[i-1]。以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第i(1≦i≦n+1个位置上，插入一个新结点x，使长度为n的线性表(a1，…ai-1，ai，…，an)变成长度为n+1的线性表(a1，…ai-1，x，ai，…，an)1.[初值]获取线性表L，插入位置i，插入元素e2.[检查参数]若（插入位置超出线性表长度范围）则输出错误3.[检查空间]若（