数据结构第02讲线性表类型定义与顺序表.ppt

第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 2.1 线性表的类型定义 1.线性表的定义 由 n(n0)个数据元素组成的有限序列。其 中数据元素的个数 n 定义为表的长度，当 n=0 时称为空表。 一般将非空的线性表（n0）记作： (a1,a2,ai,ai+1,an) (1in) 例1：26个英文字母组成的字母表 （A，B，C, , Z） 例2：某校从1978年到1983年各种型号的计算 机拥有量的变化情况。 （6，17，28，50，92，188） 例3：学生健康情况登记表如下： 姓名学号性别年龄健康情况 王小林790631男18健康 陈 红790632女20一般 刘建平790633男21健康 张立立790634男17 神经衰弱 2. 线性表的逻辑特征 1. 非空的线性表中，有且仅有一个开始结点 a1 无直接前趋，并且仅有一个直接后继 a2； 2. 有且仅有一个终端结点 an 无直接后继，并且 仅有一个直接前趋 an-1； 3. 其余的内部结点 ai(2in-1)都有且仅有一 个直接前趋 ai-1 和一个直接后继 ai+1。 3. 抽象数据类型线性表的定义 ADT List 数据对象： D ai | aiElemSet, i=1,2,n, n0 数据关系： R |ai-1 ,aiD, i=2,n 设线性表为 (a1 ， a2 ， ， ai ， an), 称 i 为 ai 在线性表中的位置。 基本操作： ADT List 线性表的基本操作 1）InitList( Lb_len = ListLength(Lb); for (i = 1; i b void mergelist(list la, list lb, list i=j=1; k=0; la_len = listlength(la); lb_len = listlength(lb); while( (i, （a1, , ai-1, e, ai, , an） a1 a2 ai-1 ai an a1 a2 ai-1 ai e an 表的长度增加1 插入的过程为： (1)检查i的合法性； (2)检查线性表是否为满，若是则动态分配存储； (3)从第i个插入位置起，将该位置元素以及其后所 有位置上的元素均后移一个位置； (4)把新元素写入到空出的位置上； (5)线性表的长度加1。 status listinsert (SqList / i值不合法 if (L.len = = L.lsize) / 当前存储空间已满，增加分配 newbase = (Elemtype * ) realloc(L.elem, (L.lsize + LISTINCREMENT) * (sizeof(ElemType); if (!newbase) exit(overflow); / 存储分配失败 L.elem = newbase; / 新基址 lsize += LISTINCREMENT; / 增加存储容量 q = / q为插入位置 for (p = p=q;-p) *(P+1) = * P; / 元素后移 *q = e; +L.len; / 插入e，表长增1 return OK; /listinsert 注意：C语言中数组的下 标从“0”开始，因此，若L 是SqList类型的顺序表， 则表中第i个数据元素是 L.elemi-1。 21 18 30 75 42 56 87 21 18 30 75 例：ListInsert_Sq(L, 5, 66) L.len-1 0 ppp q 87564266 q = for (p = p = q; -p) *(p+1) = *p; *q = e; p for (j=L.len-1; j=i-1; j) L.elemj+1=L.elemj; L.elemi-1=e 考虑移动元素的平均情况： 假设在第i个元素之前插入的概率为 Pi，则 在长度为n 的线性表中插入一个元素所需移动元 素次数的期望值为： 若假定在线性表中任何一个位置上进行插入 的概率都是相等的，则移动元素的期望值为： +-= + = 1 1 ) 1( n i iis inpE +- + = + = 1 1 ) 1( 1 1 n i is in n E 2 n = a1 a2 ai-1 ai ai+1 an 例2：从线性表中删除第i个位置的元素。 分析：删除元素时，线性表的逻辑结构发生什么 变化？ （a1, ai-1, ai, ai+1, an） 改变为 , （a1, ai-1, ai+1, an） ai+1 an a1 a2 ai-1 表长度减1 删除的过程为： (1)检查i的合法性； (2)删除第i个位置的元素，即使后面第i至第n个 元素（共 ni个）依次前移一个位置； (3)使线性表的长度减1；返回删除成功。 status ListDelete (SqList / 删除位置不合法 p = / p 为被删除元素的位置 e = *p; / 被删除元素的值赋给 e q = L.elem + L.len 1; / 表尾元素的位置 for (+p; pq; +p) *(P - 1) = * P; / 被删除元素之后的元素左移 - L.len; / 表长减1 return OK; / ListDelete 21 18 30 75 42 56 87 21 18 30 75 L.len-10 ppp q 8756 p = q = L.elem+L.len-1; for (+p; p = q; +p) *(p-1) = *p; 例：ListDelete_Sq(L, 5, e) p e=L.elemi-1; for (j=i; j=L.len-1; j+) L.elemj-1=L.elemj; 考虑移动元素的平均情况： 假设删除第i个元素的概率为qi ,则在长度 为n 的线性表中删除一个元素所需移动元素次 数的期望值为： 假定在线性表中任何一个位置上进行删除 的概率相等，则移动元素的期望值