数据结构第二章(下篇)

2.5.3 循环链表

循环链表：头尾相接的链表
- 优点：从表中任意结点出发均可找到表中其他结点
- 注意：终止条件为判断他们是否等于头指针
- 如果是头指针表示的单循环链表
  - 找$a_1$的时间复杂度：O(1)
  - 找$a_n$的时间复杂度：O(n)
- 若是尾指针表示的单循环链表
  - 找$a_1$的存储是：R->next->next 时间复杂度：O(1)
  - 找$a_n$的存储是：R 时间复杂度：O(1)

带尾指针循环链表的合并

p存表头结点将Tb表头连接到Ta表尾释放Tb表头结点修改指针
p=Ta->next ; Ta->next=Tb->next->next ; delete Tb->next ; Tb->next=p;

LinkList Connect(LinkList Ta,LinkList Tb){
    p=Ta->next;			//  an指向b1,没毛病，但是bn指向a头结点p就找不到了因为第一步你覆盖了an，所以an指向b1前，要利用an找到a头结点，bn指向bn的next
    Ta->next=Tb->next->next:
    delete Tb->next:
    Tb->next=p;
    return Tb;
}						//时间复杂度O(1)

2.5.4 双向链表

双向链表的结构可以定义如下：

typedef struct DuLNode{						//前面的Du是double双向的意思
    Elemtype         data;
    struct DuLNode   *prior,*next;          //一个指向前驱，一个指向后驱
}DuLNode,*DuLinkList;

双向循环列表
- 让头结点的前驱指针指向链表的最后一个结点
- 让最后一个结点的后继指针指向头结点
双向链表结构的对称性：
- $\large p->prior->next=p=p->next->prior$

算法2.13 双向链表的插入

void Listlnsert_DuL(DuLinkList &L, lnt i, ElemType e){
    //双向链表头结点指针L，第i个位置，值为e的元素
    if(!(p=GetElemP_DuL(L,i)))return ERROR;			//确定第i个元素的位置指针P
    S=new DuLNode;			s->date=e;
    s->prior=p->prior;		P->prior->next=s;
    s->next=p;				p->prior=s;
    return OK;
}//Listlnsert_DuL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

**算法2.14 双向链表的删除**

![](E:\备考文件\数据结构\笔记图片\QQ截图20230913192652.png)

```c
void ListDelete_DuL(DuLinkList &L, lnt i, ElemType &e){
    //用e返回
    if(!(p=GetElemP_DuL(L,i)))return ERROR;			//确定第i个元素的位置指针P，顺着链表查找时间复杂度为O(n)
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}//ListDelete_DuL

单链表、循环链表和双向链表的时间效率比较

	查找表头结点（首元结点）	查找表尾结点	查找结点*p的前驱结点
带头结点的单链表L	L->next 时间复杂度O(1)	L->next依次向后遍历时间复杂度O(n)	通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表	L->next 时间复杂度O(1)	L->next依次向后遍历时间复杂度O(n)	通过p->next可以找到其前驱时间复杂度O(n)
带头结点仅设尾指针R的循环单链表	R->next 时间复杂度O(1)	R 时间复杂度O(1)	通过p->next可以找到其前驱时间复杂度O(n)
带头结点的双向循环链表L	L->next 时间复杂度O(1)	L-》prior 时间复杂度O(1)	p->prior 时间复杂度O(1)

2.6顺序表和链表的比较

链式存储结构的优点：
- 结点空间可以动态申请和释放
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素
链式存储结构的缺点：
- 存储密度小，每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
  - $\large 存储密度=\dfrac {结点数据本身占用的空间}{结点占用的空间总量}$
  - 链式存储结构是非随机存储结构。对任一结点的操作都要从头遍历，这增加了算法的复杂度

2.7 线性表的应用

2.7.1 线性表的合并

线性表的合并

问题描述：

假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AUB

La=(7,5,3, 11) Lb=(2, 6, 3) ====》 La=(7, 5, 3, 11, 2, 6)
算法步骤：

从Lb中的每个元素,执行以下操作：
1. 在La中查找该元素
2. 如果找不到，则将其插入到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);
        if(!LocateElem(La,e))  Listlnsert(&La,++La_len,e);
    }
}

时间复杂度为La的长度乘以Lb的长度

2.7.2 有序表的合并

有序表的合并

问题描述：

已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
算法步骤：
1. 创建一个空表Lc
2. 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
3. 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

用顺序表实现合并的代码实现：

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
    pa=LA.elem;		
    pb=LB.elem;										//指针pa和pb的初值分别指向两个表的第一个元素      
    LC.length=LA.length+LB.length;					//新表的长度等于两表长之和
    LC.elem=new ElemType[LC.length];				//为合并后的新表分配一个数组空间
    pc=LC.elem;										//指针pc指向新表第一个元素
    pa_last=LA.elem+LA.length-1;					//指针pa_last指向LA表的最后一个元素（基地址加上长度减一）
    pa_last=LB.elem+LB.length-1;					//指针pa_last指向LB表的最后一个元素（基地址加上长度减一）
	while(pa<pa_last&&pb<=pb_last){					//两个表都非空
    if(*pa<=*pb)*pc++=*pa++;						//依次“摘取”两表中值较小的结点
    else *pc++=*pb++;
	}
    while(pa<=pa_last) *pc++=*pa++;					//LB表已经到达表位，将LA中剩余元素加入LC
    while(pb<=pb_last) *pc++=*pb++;					//LA表已经到达表位，将LB中剩余元素加入LC
}//MergeList_Sq

用链表实现合并的代码实现：

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    pa=La->next; pb=Lb->next; 
    pc=Lc=La;				//用La的头结点作为Lc的头结点
    while( pa && pb){
        if(pa->data<=pb->data) {pc->next=pa; pc=pa; pa=pa->next;}
            else {pc->next=pb; pc=pb; pb=pb->next;}
    }
    pc->next=pa?pa:pb; //插入剩余段delete Lb;
    delete 	LB;
}

算法的时间复杂度是：O(ListLength(La)+ListLength(Lb)）

2.8案例分析与实现

案例2.1 一元多项式的运算：实现两个多项式加、减、乘、除运算 线性表

实现两个多项式相加运算

案例2.2：稀疏多项式的运算 链表

创建一个新数组C
分别从头遍历比较A和B的每一项
- 指数相同，系数相加，和若不为零，则在C中新加一项
- 指数不同，则将指数较小的项复制到C中
一个多项式已遍历完毕时，将另一个剩余项依次复制到C中即可

用顺序存储结构的话，存储空间分配不灵活，运算的空间复杂度高，所以我们常用链式存储结构

创建一个只有头结点的空链表。
根据多项式的项的个数n，循环n次执行以下操作:
生成一个新结点*s;
输入多项式当前项的系数和指数赋给新结点*s的数据域：
设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱pre初值指向头结点;
指针q初始化，指向首元结点;
循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q;
将输入项结点s插入到结点q之前。

算法步骤：
1. 指针p1和p2初始化，分别指向Pa和Pb的首元结点
2. p3指向和多项式的当前结点，初值为Pa的头结点
3. 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值(p1->expn与p2->expn) 有下列3种情况:
  1. 当p1->expn==p2->expn时，则将两个结点中的系数相加
    1. 若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点
    2. 若和为零，则删除p1和p2所指结点;
  2. 当p1->expnexpn时，则应摘取p1所指结点插入到“和多项式”链表中去
  3. 当p1->expn>p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去
4. 将非空多项式的剩余段插入到p3所指结点之后
5. 释放Pb的头结点

案例2.3 图书信息管理系统 线性表或链表