《数据结构》课程PPT教学课件（2015）第2章 线性表

《数据结构》 第二章线性表

《 数据结构》

数据结构 第二章 线性表 2.1线性表的类型定义 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4一元多项式的表示及相加

数据结构

数据结构 线性结构是：一个数据元素的有序集。 线性结构的基本特征： 在数据元素的非空有限集合中， 1、存在唯一的一个被称做“第一个”的数据元素 2、存在唯一的一个被称做“最后一个”的数据元 素 3、除第一个之外，集合中的每个数据元素均只有 一 个前驱 4、除最后一个之外，集合中每个数据元素均只有 一个后继 例1：26个英文字母组成的字母表(A,B, C、{ Z)

数据结构

激据猪构 例2：学生健康情况登记表如下： 姓名 学 号 性别 年龄 健康情况 王小林 790631 男 18 健康 陈红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 ■■■n8■ 8n■n8n■0 n■I8n■ 0”n■■■ a1"■1■口 (王小林、790631、男、18、健康)， (陈红、790632、女、20、一般)，.)

数据结构

数据结构 2.1线性表的类型定义 线性表(Linear List):由n(n≥O)个数据元 素（结点）a1,a2,an组成的有限序列。其 中数据元素的个数n定义为表的长度。当n=0 时称为空表，常常将非空的线性表(>0)记作： (a1,a2,an) 这里的数据元素a(I≤i≤n)只是一个抽象的符 号，其具体含义在不同的情况下可以不同

数据结构

激据猪构 线性表的逻辑特征是： 在非空的线性表中，有且仅有一个开始结点a1, 它没有直接前趋，而仅有一个直接后继a2；有 且仅有一个终端结点an,它没有直接后继，而 仅有一个直接前趋an-1;其余的内部结点 a(2≤i≤n-1)都有且仅有一个直接前趋ai-1 和一个直接后继a+1。 结论：线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具 体实现则是在存储结构上进行的。 线性表的抽象数据类型的定义：P19

数据结构

数据结构 例2-1利用两个线性表LA和LB分别表示两个集合A 和B(即线性表中的数据元素即为集合中的成员)， 现要求一个新的集合A=AUB。 void union(List &La,List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++) GetElem(Lb,i,e); if(!LocateElem(La,e,equal)) ListInsert(la,++La_len,e)

数据结构

数据传物 扩展1：利用两个线性表LA和LB分别表示两个集合 A和B,现要求一个新的集合A=A∩B。 void JiHeJiao(List &La,List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i<=La_len;i++) GetElem(La,i,e); if(!LocateElem(Lb,e,equal)) ListDelete(la,i,e); -i;-La_len;

数据结构

数据结构 例2-2己知线性表LA和线性表LB中的数据元素按 值非递减有序排列，现要求将LA和LB归并为一 个新的线性表LC,且LC中的元素仍按值非递减 有序排列。此问题的算法如下： void MergeList(List La,List Lb,List &Lc) InitList(Lc) i=j=1k=0; La_len=ListLength(La); Lb_len=ListLength(Lb); while((i<=La_len)&&(j<=Lb_len))

数据结构

GetElem(La,i,ai);getElem(Lb,j, if(ai<=bj) ListInsert(Lc,++k,ai);++i;} else ListInsert(Lc,++k,bj);++j;} } while(i<=La_len) GetElem((La,i++,ai); ListInsert(Lc,++k,ai);} while(j<=Lb_len) GetElem((Lb,j++,bj); ListInsert(Lc,++k,bj);}

数据结构