《数据结构》 第二章
《 数据结构》 第二章
数据结构 第二章线性表 2.1线性表的类型定义 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.3.1线性链表 2.3.2循环链表 2.3.3双向链表 2.4一元多项式的表示及相加
数据结构 tjm
数据结构 线性结构是:一个数据元素的有序集。 线性结构的基本特征: 在数据元素的非空有限集合中, 1、存在唯一的一个被称做“第一个”的数据元素 2、存在唯一的一个被称做“最后一个”的数据元 素 3、除第一个之外,集合中的每个数据元素均只有 个前驱 4、除最后一个之外,集合中每个数据元素均只有 个后继 例1:26个英文字母组成的字母表(A,B, ■■■ 7)
数据结构 tjm
数据结构 例2:学生健康情况登记表如下: 姓名学号性别年龄健康情况 王小林790631 男18健康 陈红790632 女20 般 刘建平790633 男|21 健康 张立立790634 男17神经衰弱 (王小林、790631、男、18、健康), (陈红、790632、女、20、一般),…)
数据结构 tjm
数据结构 2.1线性表的类型定义 线性表( Linear list):由n(n≥0)个数据元 素〔结点)a1,a2,…,an组成的有限序列。其 中数据元素的个数n定义为表的长度。当n=0 时称为空表,常常将非空的线性表(n>0)记作: (a1,a2 9■■■ an) 这里的数据元素a(1≤i≤n)只是一个抽象的符 号,其具体含义在不同的情况下可以不同
数据结构 tjm
数据结构 线性表的逻辑特征是: 在非空的线性表中,有且仅有一个开始结点a1, 它没有直接前趋,而仅有一个直接后继a2;有 且仅有一个终端结点an,它没有直接后继,而 仅有一个直接前趋an-1;其余的内部结点 a(2≤i≤n-1)都有且仅有一个直接前趋a; 和一个直接后继a+1 结论:线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的,而运算的具 体实现则是在存储结构上进行的。 线性表的抽象数据类型的定义:P19
数据结构 tjm
数据结构 例2-1利用两个线性表LA和LB分别表示两个集合A 和B(即线性表中的数据元素即为集合中的成员), 现要求一个新的集合A=AUB void union (List &La, List Lb) La_len=ListLength (Lai 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)
数据结构 tjm
数据结构 打展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(! Locate Elem(Lb, e, equaD)) i ListDelete(la,i, e)i ii--La len; r t r
数据结构 tjm
数据结构 例2-2已知线性表LA和线性表LB中的数据元素按 值非递减有序排列,现要求将LA和LB归并为 个新的线性表LC,且LC中的元素仍按值非递减 有序排列。此问题的算法如下: void Mergelist(List La, List Lb, List &lc) InitList(Lc); i=j=1:k=0 La_ len=ListLength (La) Lb_len=ListLength (Lb)i while((i<=La_len) &&<=Lb_len))
数据结构 tjm
数据结构 GetElem(La, i, aD);getElem (Lb, j, bji if(ai<=b]) RListInsert(Lc,++k, ai;++i;y else i ListInsert(LC,++k, b]i++jry while (i<=La len) GetElem ((La, i++, ai; ListInsert(Lc, ++k, ai;y while<=Lb len) GetElem((Lb,j++, b]) ListInsert(Lc,++k, b]i3 }
数据结构 tjm