数据结构第2章_线性表

《数据结构第2章_线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加2.1线性表的类型定义1.线性表的定义由n(n≥0)个数据元素组成的有限序列。其中数据元素的个数n定义为表的长度，当n=0时称为空表。一般将非空的线性表（n>0）记作：(a1,a2,…,ai,ai+1,…,an)(1≤i≤n)例1：26个英文字母组成的字母表（A，B，C,…,Z）例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3：学生健康情况登记表如下：姓名学号性别

2、年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……………2.线性表的逻辑特征1.非空的线性表中，有且仅有一个开始结点a1无直接前趋，并且仅有一个直接后继a2；2.有且仅有一个终端结点an无直接后继，并且仅有一个直接前趋an-1；3.其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。3.抽象数据类型线性表的定义ADTList{数据对象：D＝{ai

3、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R＝{

4、ai-1,ai∈D,i=2,…,n}设线性表为

5、(a1，a2，…，ai…，an),称i为ai在线性表中的位置。基本操作：}ADTList线性表的基本操作1）InitList(&L)操作结果：结构初始化，构造一个空的线性表L2）DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。3）ListEmpty(L)初始条件：线性表L已存在操作结果：若L为空表，返回TRUE，否则FALSE4）ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数5）GetElem(L,i,&e)初始条件：线性表L已存在，且1≤i≤表长操作结果：用e返回L中第i个元素的值6）LocateElem(L,e,compare

6、())初始条件：L已存在，compare()是元素判定函数操作结果：返回L中第1个与e满足关系compare()的元素的位序；若这样的元素不存在，则返回值为0。7）PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义8）NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义9）ListTraverse(L,visit())初始条件：线

7、性表L已存在。操作结果：依次对L的每个元素调用visit()函数。一旦visit()失败，则操作失败10）ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤表长+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。11）ListDelete(&L,i,&e)初始条件：L已存在且非空，1≤i≤表长操作结果：删除L的第i个元素，用e返回其值，L的长度减1。12）ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。4.利用上述定义的操作完成更复杂的操作例1：假设有两个集合A和B分别用两个线性表LA和LB表示。（即：线性表中的数据元素即为集合中的

8、成员），现要求一个新集合A＝A∪B问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存于线性表LA中的数据元素插入到线性表LA中。则思路即为：1)从线性表LB中依次取得每个数据元素；2)依值在线性表LA中进行查访；3)若不存在，则插入之。voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的元素插入到LaLa_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个元素赋给eif(!LocateElem(La,

9、e,equal())ListInsert(La,++La_len,e);//La中不存在和e相同的元素，则插入之}}//union例2：假已知一个非纯集合B，(即B中包含有相同元素）试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。（假设B为有序序列）则思路即为：1)创建一个空的线性表LA;2)从线性表LB中依次取得每个数据元素；3)依值在线性表LA中进行查访；4)若不存在，则插入之。