数据结构 Data Structure 中南大学 主讲人：王国军，郑瑾 中南大学信息院计科系 {csgjwang,zhengjin}@csu.edu.cn http://trust.csu.edu.cn/ 电话：0731-88877711 手机：13508486821 办公室：校本部计算机楼406-B 本PPT根据《数据结构》教材（清华大学）制作，仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。

第二章 线性表

提 纲 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加

2.1 线性表的类型定义 线性结构的基本特征: 1．集合中必存在唯一的“第一个元素”； 2．集合中必存在唯一的 “最后一个元素”； 线性结构是一个数据元素的有序集。对非空有限集： 1．集合中必存在唯一的“第一个元素”； 2．集合中必存在唯一的 “最后一个元素”； 3．除最后一个元素之外，均有 唯一的后继； 4．除第一个元素之外，均有 唯一的前驱。

线性表的定义 线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式： L=(a1, a2,...,ai-1,ai,ai+1,...,an) 其中： L为线性表的名称； ai为组成该线性表的数据元素，i为数据元素ai在线性表中的位序； n为线性表中数据元素的个数，称为线性表的长度。当n=0时，线性表为空，又称为空线性表。

抽象数据类型线性表的定义 初始化操作 ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1, ai >|ai-1, ai∈D, i=2,...,n } 基本操作： 初始化操作 InitList( &L ) 操作结果： 构造一个空的线性表L。

线性表判空操作 DestroyList( &L ) 初始条件： 线性表 L 已存在。 操作结果： 销毁线性表 L。 线性表 L 已存在。 结构销毁操作 DestroyList( &L ) 初始条件： 操作结果： 线性表 L 已存在。 销毁线性表 L。 线性表判空操作 ListEmpty( L ) 线性表 L 已存在。 初始条件： 操作结果： 若 L 为空表，则返回 TRUE，否则FALSE。

求线性表的长度 求数据元素的前驱 ListLength( L ) 初始条件： 线性表 L 已存在。 操作结果： 返回 L 中数据元素的个数。 PriorElem( L, cur_e, &pre_e ) 初始条件： 操作结果： 线性表 L 已存在。 若 cur_e 是 L 的元素，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。

求数据元素的后继 求线性表中某个数据元素 NextElem( L, cur_e, &next_e ) 初始条件： 线性表 L 已存在。 操作结果： 线性表 L 已存在。 若 cur_e 是 L 的元素，则用next_e 返回它的后继，否则操作失败，next_e无定义。 求线性表中某个数据元素 GetElem( L, i, &e ) 线性表 L 已存在， 初始条件： 操作结果： 并且 1≤i≤ListLength(L) 。 用 e 返回 L 中第 i 个数据元素的值。

定位函数 LocateElem( L, e, compare( ) ) 线性表 L 已存在，e 为给定值， 初始条件： 操作结果： 返回 L 中第 1 个与 e 满足关系 compare( ) 的元素的位序。 若这样的元素不存在，则返回值为 0。

遍历线性表 线性表 L 已存在。 初始条件： visit( ) 为某个访问函数。 操作结果： 依次对 L 中每个元素调用 ListTraverse(L, visit( )) 线性表 L 已存在。 visit( ) 为某个访问函数。 初始条件： 操作结果： 依次对 L 中每个元素调用 函数visit( )。一旦 visit( )失败，则操作失败。

线性表置空 改变数据元素的值 ClearList( &L ) 初始条件： 线性表 L 已存在。 操作结果： 将 L 重置为空表。 PutElem( &L, i, &e ) 初始条件： 操作结果： 线性表 L 已存在， 并且 1≤i≤ListLength(L) 。 L 中第 i 个元素赋值 e 。

插入数据元素 删除数据元素 初始条件： 线性表 L 已存在， 且 1≤i≤ListLength(L)+1 。 操作结果： ListInsert( &L, i, e ) 初始条件： 操作结果： 线性表 L 已存在， 且 1≤i≤ListLength(L)+1 。 在 L 中的第 i 个元素之前插入 新的元素 e，L 的长度增1。 删除数据元素 ListDelete(&L, i, &e ) 线性表 L 已存在并且非空， 初始条件： 操作结果： 且 1≤i≤ListLength(L) 。 删除 L中的第 i 个元素，并且用 e 返回其值，L 的长度减1。 } ADT List

利用上述定义的线性表类型，可以实现其它更为复杂的操作： 例 2-1 例 2-2

例 2-1 有两个集合 A 和 B，分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 求一个新的集合A＝A∪B。 上述问题可转换为： 要求对线性表作如下操作：扩大线性表 LA，将在线性表LB 中而不在线性表 LA 中的数据元素插入到线性表 LA 中去。

操作步骤： 1．从线性表 LB 中依次查看每个数据元素： GetElem(LB, i, e) 2．依次在线性表 LA 中进行查访： LocateElem(LA, e, equal( )) 3．若不存在，则插入之： ListInsert(LA, n+1, e) ( n 表示线性表 LA 当前长度)

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); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之 }//for } // union

接下来，考虑用有序表表示集合： 若线性表中的数据元素相互之间可以比较，并且数据元素在表中按值非递减或非递增有序排列，即 ai≥ai-1 或 ai≤ai-1(i = 2,3,…, n)，则称该线性表为有序表(Ordered List)。

例 2-2 归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。 设 La = (a1, …, ai, …, an), Lb = (b1, …, bj, …, bm) Lc = (c1, …, ck, …, cm+n) 且已由(a1, …, ai-1)和(b1, …,bj-1)归并得 (c1, …, ck-1) 则 k = 1, 2, …, m+n

基本操作： 1．初始化 LC 为空表； 2．分别从 LA和LB中取得当前元素 ai 和 bj； 3．若 ai≤bj，则将 ai 插入到 LC 中，否则将 bj 插入到 LC 中； 4．重复 2 和 3 两步，直至 LA 或 LB 中元素 被取完为止； 5．将 LA 表或 LB 表中剩余元素复制并插入到 LC 表中。

void MergeList(List La, List Lb, List &Lc) { // 本算法将非递减的有序表 La 和 Lb 归并为 Lc InitList(Lc); // 构造空的线性表 Lc i = j = 1; k = 0; // i,j,k分别用来指向La,Lb,Lc //当前操作的元素位置 La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i <= La_len) && (j <= Lb_len)) { // La 和 Lb 均非空

GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { // 将 ai 插入到 Lc 中 ListInsert(Lc, ++k, ai); ++i; } else { // 将 bj 插入到 Lc 中 ListInsert(Lc, ++k, bj); ++j; } }

O(ListLength(La) + ListLength(Lb)) while (i <= La_len) { // 当La不空时 GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } // 插入 La 表中剩余元素 while (j <= Lb_len) { // 当Lb不空时 GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); } // 插入 Lb 表中剩余元素 } // merge_list O(ListLength(La) + ListLength(Lb)) 算法的时间复杂度为：

2.2 线性表的顺序表示和实现 一、线性表的顺序表示 顺序映象： 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系<x, y>。 最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。

定义：用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构。 a1 a2 … ai-1 ai … an 线性表的起始地址， 也称为线性表的基地址。

元素地址（存储位置）计算方法： LOC(ai)=LOC(a1)+(i-1)*m 其中：m—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 LOC(a1)—线性表首址，又称为基址 顺序表的特点： 实现逻辑上相邻—物理地址相邻 实现随机存取

顺序表的表示 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量，初始化时等于LIST_INIT_SIZE }SqList;

数据元素不是简单类型时,可定义结构体数组。 a1 a2 an 1 n-1 2 n 内存 数组下标 元素序号 M #define M 100 typedef struct{ ElemType elem[M]; int length; } SqList; 例： typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; } Library[M]; 备用空间 数据元素不是简单类型时,可定义结构体数组。

线性表的基本操作在顺序表中的实现 InitList(&L) // 结构初始化 LocateElem(L, e, compare()) // 查找 ListInsert(&L, i, e) // 插入元素 ListDelete(&L, i) // 删除元素

Status InitList_Sq( SqList &L) { // 构造一个空的线性表Ｌ } // InitList_Sq L.elem = (ElemType *)malloc(LIST_INIT_SIZE* sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; 算法时间复杂度： O(1)

O(L.length) 算法的时间复杂度为： Status (*compare)(ElemType, ElemType)) int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { // 在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回 0 } // LocateElem_Sq i = 1; // i 的初值为第 1 个元素的位序 p = L.elem; // p 的初值为第 1 个元素的存储位置 while (i <= L.length && !(*compare)(*p++, e)) ++i; if (i <= L.length) return i; else return 0; //找到满足条件的元素 // 没有找到满足条件的元素 算法的时间复杂度为： O(L.length)

线性表操作 ListInsert(&L, i, e)的实现： 首先分析: 插入元素时， 线性表的逻辑结构发生什么变化？

(a1, …, ai-1, ai, …, an) 改变为 (a1, …, ai-1, e, ai, …, an) <ai-1, ai> <ai-1, e>, <e, ai> a1 a2 … ai-1 ai … an an a1 a2 … ai-1 e ai … 表的长度增加1

{ // 在顺序表L的第 i 个元素之前插入新的元素e, Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1 if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法 if (L.length >= L.listsize) { newbase=(ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)* sizeof(ElemType) if(! newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; }

q = &(L.elem[i-1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入e ++L.length; // 表长增1 return OK; } // ListInsert_Sq 算法时间复杂度为: O(L.length)

考虑移动元素的平均情况 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为： 假设在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素次数的期望值为：

线性表操作 ListDelete(&L, i, &e)的实现： 首先分析： 删除元素时， 线性表的逻辑结构发生什么变化？

(a1, …, ai-1, ai, ai+1, …, an) 改变为 (a1, …, ai-1, ai+1, …, an) <ai-1, ai>, <ai, ai+1> <ai-1, ai+1> a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an 表的长度减少1

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { } // ListDelete_Sq if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法 p = &(L.elem[i-1]); // p 为被删除元素的位置 e = *p; // 被删除元素的值赋给 e q = L.elem+L.length-1; // 表尾元素的位置 for ( ++p; p <= q; ++p ) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; // 表长减1 return OK; 算法时间复杂度为: O(L.length)

考虑移动元素的平均情况 假设删除第 i 个元素的概率为 , 则在长度 为 n 的线性表中删除一个元素所需移动元素次数的期望值为： 假设在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素次数的期望值为： 算法时间复杂度为: O (n)

顺序存储结构的优缺点 优点： 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点： 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分

2.3 线性表的链式表示和实现

一、单链表（线性链表） 二、结点和单链表的 C 语言描述 三、线性表的操作在单链表中的实现 四、循环链表 五、双向链表

一、单链表 用一组地址任意的存储单元存放线性表中的数据元素。 以元素(数据元素的映象) + 指针(指示后继元素的存储位置) = 结点 (表示数据元素及关系的映象) 以“结点的序列”表示线性表  称作链表

以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。 线性表为空表时， 头结点的指针域为空 头指针 头指针 空指针 头结点 a1 a2 … ... an ^  以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。 有时为了操作方便，在第一个数据元素结点之前增加一个“虚”的“头结点”，并且以指向头结点的指针作为链表的头指针。

二、结点和单链表的 C 语言描述 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; LinkList L； // L 为单链表的头指针

三、单链表操作的实现 GetElem(L, i, &e) // 取第i个数据元素 ListInsert(&L, i, e) // 插入数据元素 ListDelete(&L, i, &e) // 删除数据元素 ClearList(&L) // 重置线性表为空表 CreateList(&L, n) // 生成含 n 个数据元素的链表

线性表的操作 GetElem(L, i, &e) 单链表是一种顺序存取的存储结构，为找第 i 个数据元素，先要找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。 令指针 p 始终指向线性表中第 j 个数据元素。

Status GetElem_L(LinkList L, int i, ElemType &e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L p = L->next; j = 1; //p指向第一个结点，j为计数器 while (p && j<i) { p = p->next; ++j; } // 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空 if ( !p || j>i ) return ERROR; // 第 i 个元素不存在 e = p->data; // 取得第 i 个元素 return OK; 算法时间复杂度为: O(ListLength(L))

线性表的操作 ListInsert(&L, i, e) 在单链表中的实现： 有序对 <ai-1, ai> 改变为 <ai-1, e> 和<e, ai>

s->next = p->next; p->next = s; p ai-1 ai-1 ai e s

可见，在链表中插入结点只需要修改指针。但是，如果要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。

Status ListInsert_L(LinkList &L, int i, ElemType e) p = L; j = 0; while (p && j < i-1) { p = p->next; ++j; } // 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; // i 大于表长或者小于1 s=(LinkList)malloc(sizeof(LNode));

s->data = e; s->next = p->next; p->next = s; // 插入 return OK; } // ListInsert_L 算法的时间复杂度为： O(ListLength(L))

这里的变量初始化能否改为 p=L->next; j=1; 为什么? 不行!因为插入时修改的是前驱结点的指针，因此算法中的目标是找第 i个结点的前驱，如果一开始 p 就指向第一个结点，那么当i=1时就找不到它的前驱了。 如果单链表没有头结点，则需对在第一个结点之前进行插入的情况单独进行处理。

改变为 <ai-1, ai+1> ai-1 ai-1 ai ai+1 线性表的操作ListDelete (&L, i, &e)在链表中的实现： 有序对 <ai-1, ai> 和 <ai, ai+1> 改变为 <ai-1, ai+1> ai-1 ai-1 ai ai+1

在单链表中删除第 i 个结点的基本操作为：找到线性表中第i-1个结点，修改其指向后继的指针。 q = p->next; p->next = q->next; e = q->data; free(q); p q ai-1 ai-1 ai ai+1

Status ListDelete_L(LinkList &L, int i, ElemType &e) 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; 算法的时间复杂度为： O(ListLength(L))

因为对插入而言，只要“前驱”存在即可；而对删除而言，不仅“前驱”要存在，被删结点也必须存在。 在删除算法中参数不合理的判断条 件和插入的情况不同。为什么？ 插入 删除 因为对插入而言，只要“前驱”存在即可；而对删除而言，不仅“前驱”要存在，被删结点也必须存在。 如果单链表没有头结点，需要对删除第一个结点的情况进行单独处理。

操作 ClearList(&L) 在链表中的实现： void ClearList(&L) { // 将单链表（带头结点）重新置为一个空表 while (L->next) { p=L->next; L->next=p->next; } } // ClearList free(p); 算法时间复杂度： O(ListLength(L))

如何从线性表得到单链表？ 链表是一个动态的结构，生成链表的过程是一个结点“逐个插入” 的过程。

an an an-1 例如：逆位序输入 n 个数据元素的值，建立带 头结点的单链表。 操作步骤： 建立一个“空表”； 输入数据元素an， 建立结点并插入； an 输入数据元素an-1， 建立结点并插入； an an-1 依次类推，直至输入a1为止。

void CreateList_L(LinkList &L, int n) L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; for (i = n; i > 0; --i) { p = (LinkList)malloc(sizeof(LNode)); scanf(&p->data); // 输入元素值 p->next = L->next; L->next = p; // 插入 } 算法的时间复杂度为: O(ListLength(L))

建立单链表例题 假设线性表中结点的数据类型是字符型，我们逐个输入这些字符型的结点，并以换行符’\n’为输入结束标记。 动态地建立单链表的常用方法有如下两种：

1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。

linklist createlist_f(void) { char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!='\n') { p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; p–>next=head; head=p; ch=getchar( ); } return (head);

listlink createlist_f( int n) { int data; linklist head; listnode *p; head=null; for(i=n;i>0;--i) { p=(listnode*)malloc(sizeof(listnode)); scanf(("%d", &p–>data); p–>next=head; head=p; } return (head);

2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

while((ch=getchar( )!='\n'){ p=(listnode *)malloc(sizeof(listnode)); linklist createlist_r( ) { char ch; linklist head; listnode *p, *r; head=NULL; r=NULL; while((ch=getchar( )!='\n'){ p=(listnode *)malloc(sizeof(listnode)); p–>data=ch; if(head=NULL) head=p; else

r=p; } if (r!=NULL) r–>next=NULL; return(head); r–>next=p; 说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前驱结点的指针域中。

算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。 如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在

表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点 所在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。 其算法如下： linklist createlist_r( ) { char ch; linklist head=(linklist)malloc(sizeof(listnode)); listnode *p，*r;

r=head; while((ch=getchar( ))!='\n') { p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; p–>next=p; r=p; } r–>next=NULL; return(head);

编写算法删除单链表中“多余”的数据元素，使得操作之后的单链表中所有元素的值都各不相同。 解题分析： 　 设想新建一个链表，然后顺序考察原链表中每一个结点的数据元素，在“新表”中进行查找，如果有相同的则舍弃之，否则就插入到新表中。

void purge_L(LinkList &L ) { p = L->next; L->next = NULL; // 设新表为空表 while ( p )　　　 // 顺序考察原表中每个元素 { succ = p->next;　// 记下结点 *p 的后继 q = L->next;　　// q 指向新表的第一个结点 while( q && p->data!=q->data ) q = q->next; // 在新表中查询是否存在和p->data相同的元素

if ( !q )　// 将结点 *p 插入到新的表中 　　　{ 　　　　p->next = L->next; 　　　　L->next = p; 　　　} else free( p );　// 释放结点 *p p = succ; } // for } // purge_L 算法的时间复杂度为: O (ListLength2(L))。

循环链表 最后一个结点的指针域的指针又指回第一个结点的链表。 a1 a2 … ... an 头指针 空的循环链表 头结点

由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。

在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单向循环链表就显得不够方便。如果改用尾指针rear来表示单向循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next) ––>next和rear。显然，查找时间都是O(1)。因此，实际中大多采用尾指针表示单向循环链表。 rear a1 a2 … ... an

例如：在链表上实现将两个线性表(a1，a2，a3，…, an)和(b1，b2，b3，…, bn)链接成一个线性表的运算。

ra—>next=(rb—>next)—>next; p=ra—>next; p ra a1 a2 … ... an rb a1 a2 … ... an ra—>next=(rb—>next)—>next; free(rb—>next); rb—>next=p;

linklist connect(linklist &ra, linklist &rb) { p=ra—>next; ra—>next=(rb—>next)—>next; free(rb—>next); rb—>next=p; }

双向链表 双向链表(Doubly linked list)：在单链表的每个结点中再增加一个指向其前驱的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList;

双向循环链表 空表 非空表 a1 a2 … ... an

设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (p—>prior)—>next==p==(p—>next)—>prior 即结点*p的存储位置既存放在其前驱结点*(p—>prior)的后继指针域中，也存放在它的后继结点*(p—>next)的前驱指针域中。

双向链表的操作特点： “查询” 和单链表相同，查找结点也是要从头指针指示的头结点开始。不同的是可以进行两个方向的查询。 “插入” 和“删除”时需要同时修改两个方向上的指针。

插入 ai-1 ai s p ai-1 ai e s->next = p->next; p->next = s; s->next->prior = s; s->prior = p;

删除 ai-1 ai-1 ai ai+1 p p–>prior–>next=p–>next; p–>next–>prior=p–>prior; free(p);

将两个有序链表合并为一个有序链表 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) { pa = La->next; pb = Lb->next; Lc = pc = La; // 用La的头结点作为Lc的头结点   while (pa && pb) 　{ if (pa->data <= pb->data) 　　{ pc->next = pa; pc = pa; pa = pa->next; 　　} // if 　　

else { pc->next = pb; pc = pb; pb = pb->next; 　　} // else 　} // while pc->next = pa ? pa : pb;　// 插入剩余段 free(Lb); // 释放Lb的头结点 } // MergeList_L 算法中没有设置Lc的表尾的语句，那么，在算法结束之后，Lc的表尾是否"正常"结束了呢？ 不论什么情况，语句 　　pc->next = pa ? pa : pb; 都使Lc表中最后一个结点的指针为"NULL"。 算法的时间复杂度为： O (ListLength(La)+ListLength(Lb))

2.4 一元多项式的表示及相加 S(x) = 1 + 3x10000 – 2x20000 在计算机中，可以用一个线性表来表示： P = (p0, p1, …, pn) 但是，对于形如： S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？

一般情况下的一元稀疏多项式可写成： Pn(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 ) … … } ADT Polynomial 初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。 初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。

一元多项式的实现： typedef LinkList Polynomial; // 用带表头结点的链表表示一元多项式 结点的数据元素类型定义为： typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType;

多项式链表中的每一个非零项结点结构用C语言描述如下： typedef struct poly { float coef; /*系数为单精度实型*/ int expn; /*指数为正整数*/ struct poly *next; /*指针域*/ }poly;

两个多项式相加的运算规则： 假设指针qa和qb分别指向多项式A(x)和多项式B(x)中当前进行比较的某个结点，则比较两个结点的数据域的指数项，有三种情况： （1）指针qa所指结点的指数值＜指针qb所指结点的指数值时，则保留qa指针所指向的结点，qa指针后移； （2）指针qa所指结点的指数值＞指针qb所指结点的指数值时，则将qb指针所指向的结点插入到qa所指结点前，qb指针后移；

（3）指针qa所指结点的指数值＝指针qb所指结点的指数值时，将两个结点中的系数相加，若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A(x)的链表中删除相应结点，并释放指针qa和qb所指结点。

多项式相加算法 struct poly *add_poly(struct poly *Ah, struct poly *Bh) { struct poly *qa,*qb,*s,*r,*Ch; qa=Ah->next; qb=Bh->next;/*qa和qb分别指向两个链表的 第一个结点*/ r=Ah; Ch=Ah; /*将链表Ah作为相加后的和链表*/ while(qa!=NULL&&qb!=NULL) /*两链表均非空*/ { if (qa->expn==qb->expn) /*两者指数值相等*/ { x=qa->coef+qb->coef; if( x!=0 ) { qa->coef=x; r->next=qa; r=qa; s=qb++; free(s); qa++; } /*相加后系数不为零时*/

else {s=qa++; free(s); s=qb++; free(s);} /*相加后系数为零时*/ } else if( qa->expn<qb->expn ) { r->next=qa; r=qa; qa++;}/*多项式Ah的指数值小*/ else {r->next=qb; r=qb; qb++;} /*多项式Bh的指数值小*/ if (qa==NULL) r->next=qb; else r->next=qa; /*链接多项式Ah或Bh中的剩余结点*/ return (Ch);

作 业 习题集二