中国计量学院数据结构第2章 线性表.ppt

* 线性表的操作 ListDelete (L, i, e) 在链表中的实现: 有序对ai-1, ai 和 ai, ai+1 改变为 ai-1, ai+1 ai-1 ai ai+1 ai-1 * 在单链表中删除第i个结点的基本操作为:找到第i-1个结点，修改其指向后继的指针。 ai-1 ai ai+1 ai-1 q = p-next; p-next = q-next; e = q-data; free(q); p q Status ListDelete_L(LinkList L, int i, ElemType e) { // 删除单链表L中第 i 个结点 } 算法的时间复杂度为: O(ListLength(L)) p = L; j = 0; while (p-next j i-1) { p = p-next; ++j; } // 寻找第 i 个结点，并令 p 指向其前趋 if (!(p-next) || j i-1) return ERROR; // 删除位置不合理 q = p-next; p-next = q-next; // 删除并释放结点 e = q-data; free(q); return OK; * 如何创建单链表？ 链表是一个动态的结构，它不需要事先分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。 * 例如：输入 n 个数据元素的值， 建立带头结点的单链表。 操作步骤： 一、建立一个“空表”； 二、输入数据元素，建立结点并插入； 三、重复二，直至输入n个数据为止。 * 四、其它形式的链表 1. 双向链表 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱 struct DuLNode *next; // 指向后继 } DuLNode, *DuLinkList; * 最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 … ... an 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 2. 循环链表 * 双向循环链表 空表 非空表 a1 a2 … ... an * 在计算机中，可以用一个线性表来表示: P = ( p0 , p1 , … ，pn ) 但是对于形如 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？ 2.4 一元多项式的表示 * 一般情况下的一元稀疏多项式可写成 P(x) = p1xe1 + p2xe2 + … + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 e2 … em = n 可以用下列线性表表示： （（p1, e1）, (p2, e2), … , (pm, em) ） * P999(x) = 7x3 - 2x12 - 8x999 例如: 可用如下线性表表示 ( (7, 3), (-2, 12), (-8, 999) ) * ADT Polynomial { 数据对象： 数据关系： 抽象数据类型一元多项式的定义 D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } R1＝{ ai-1 , ai | ai-1 , ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 } * CreatPolyn ( P, m ) DestroyPolyn ( P ) PrintPolyn ( P ) 基本操作： 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。 * PolynLength( P ) AddPolyn ( Pa, Pb ) SubtractPolyn ( Pa, Pb