线性表的使用

Nuyoah2021-07-152022-11-21

线性表

定义

线性表是具有相同特征的数据元素的一个有限序列
a1,a2,a3·····,ai-1,ai,ai+1,······,an
- 上面元素称为数据元素
- a1 称为线性起点 an是线形终点，n为元素总个数，即表长
- ai-1是ai的直接前趋， ai+1是ai的直接后续
- 当n=0时，称为空表
线性表：
- 由n（n>=0）个数据元素（节点）a1,a2,a3,a4····an组成的有限序列
- 其中数据元素的个数n定义为表的长度
- 当n= 0时称为空表
- 当非空的线性表（n>0）记作：（a1,a2····an）
- 这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同情况下可以不同

逻辑特征

在非空线性表，有且仅有一个开始节点a1，他没有直接前趋，而仅有一个直接后续a2
有且仅有一个终端节点an,他没有直接后续，而且仅有一个直接前趋an-1
其余的内部节点ai(2<=i<=n-1)都有且仅有一个直接前趋ai-1和一个直接后续ai+1

案例

一元多项式的计算
1. 当表达式为p0 + p1x^1 + p2x^2 + p3x^3 + ····pn*x^n;
  - 可以使用以为数组来表示
    
    Pn(x)
  - 0 1 2 3 n
    
    p0 p1 p2 p3 pn
    
    Qn(x)
    
    0 1 2 3 n
    
    q0 q1 q2 q3 qn
    
    则线性表Rn(x) = Pn(x) + Qn(x) 为
    
    0 1 2 3 n
    
    p0+q0 p1+q1 p2+q2 p3+q3 pn+qn
2. 当我们遇见系数多项式的时候
  
  S(x) = 1 + 3X^10000+2X20000
  
  这时候在使用上面的的方法未免有点太浪费空间了
  
  所以我们应只是记录系数不为零的项
  
  0 1 2
  
  1 3 2
  
  0 10000 20000
  
  第二行表示多项式的系数
  
  第三行表示多项式的指数
  
  线性表 A = ((7,0),(3,1),(9,8),(5,17))
  
  线性表 B = ((8,1),(22,7),(-9,8))
  - 创建一个数组c
  - 分别从头遍历比较a和b的每一项
    
    指数相同，对应系数相加，若其和不为零，则在c中增加一个新项
    
    指数不同，则将指数较小的项复制到c中
  - 当一个多项式遍历完毕后，将另一个剩余的项依次复制到c中即可
3. 顺序存储结构存在的问题
  - 存储空间分配不灵活
  - 运算的空间复杂度高
    
    解决方法：采用链式存储结构，动态分配内存

0	1	2	3	n
p0	p1	p2	p3	pn

0	1	2	3	n
q0	q1	q2	q3	qn

0	1	2	3	n
p0+q0	p1+q1	p2+q2	p3+q3	pn+qn

0	1	2
1	3	2
0	10000	20000

总结

线性表中数据元素的类型可以是简单类型（单纯的数字），也可以是复杂类型（有字符串）
许多实际应用问题所涉及的基本操作有很大的相似性，不应为每个具体单位单独编写一个程序
从具体应用中抽象出共性的逻辑结构和基本操作（抽象类型），然后实现其存储结构和基本操作

抽象数据类型线性表

定义

ADT liet

{

数据对象：D = {ai | ai 属于Elemset，（i = 1,2,3,····n,n>=0）}

数据关系：R = {<ai-1, ai>| ai-1, ai属于D(i = 1,2,····，n)}

基本操作：
```
  initlist（&l）；

  DestroyList（&l）;

  ClearList(&l);

  ListEmpty(L);
```
}ADT list

initlist（&l)

操作结果：构造一个空的线性表

DestroyList（&l）

初始条件：线性表L已经存在

操作结果：销毁线性表L；

ClearList(&l)

初始条件：线性表L已经存在

操作结果：将线性表L重置为空表

ListEmpty(L)

初始条件：线性表L已经存在。

操作结果： 若线性表L为空表，则返回True，否则返回False

顺序表

第二周第八节

顺序表的顺序存储表示

地址连续
依次存放
随机存取
类型相同
- 所以我们可以使用一维数组来表示顺序表
- 但是顺序表和链表都属于线性表，而线性表长度可以变换，但是数组长度不可以动态定义，所以我们需要使用一变量来表示顺序表的长度

#define LIST_LENGTH 100
typedef struct
{
    int realpart;
    int imagpart;
}ElemType;

typedef struct
{
    ElemType elem[LIST_LENGTH];
    int length; 
}Sqlist;

上述代码可以表示线性表的模板， ElemType 可以变化你需要的数据类型， LIST_LENGTH表示动态的数组的长度，length表示实际的数组的长度
- 有两种顺序表的定义形式，一种是上面的直接定义，数据静态分配，还有一种是下面的

typedef struct
{
    ElemType *data;
    int length;
}Sqlist;

这种定义形式，在定义的时候没有给数组分配内存，需要在使用的时候静态分配一下

1 2	Sqlist L; L.data = (ElemType)malloc(sizeof(Elemtype)MaxSize);

补充（顺序表的操作）

#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
// 线性表的初始化
Status InitList_Sq(SqList &L)
{
    L.elem = new ElemType[MAXSIZE];
    if(!L.elem)exit(OVERFLOW);
    L.lengh = 0;
    return OK;
}
// 销毁
void DsetroyList(SqList &L)
{
    if(L.elem)
        delete L.elem; // 释放空间
}
// 清空线性表L
void ClearList(SqList &L)
{
    L.length = 0; // 将线性表的长度置为零
}
// 得到i位置上的元素
int GetElem(SqList L, int i, ElemType &e)
{
    // 判断i的值是否合理，若不合理，返回ERROR
    if(i < 1 || i < L.length)
        return ERROR;
    e = L.elem[i-1];
    return OK;
}

顺序表的查找算法分析

顺序查找法：

将表中元素进行遍历，依次比较如果查找出来则返回对应的记录， 如果没找到则返回0；

例如一个长度为7的数组进行查找，最少找一次，最多找7次，那么平均一共找4次即可。

平均查找长度ASL（Average Search Length）
- 为了确定记录在表中的位置，需要与给定值进行比较的冠军字的个数的期望值叫做查找算法的平均查找长度

对含有n个记录的表，查找成功时：

ASL = （i从1到n加）PiCi = （n+1）/2；

  		Pi第i个记录被查找的概率

  		Ci找到第i个记录需要比较的次数

  		例如上面的长度为7的数组查找到平均长度为1/7乘1 + 1/7乘2 + ····1/7乘7 每一个的查找的概率都是1/7， 只是查找到需要的次数不同。

顺序表的插入算法分析

插入位置在最后：这接放在最后即可
插入位置在中间：让别插入的位置的后面的元素依次向后移
插入位置在最前面：让所有位置依次往后移，给这个位置移出来地方

算法思想

插入位置的判断（0-数组长度）
判断顺序表的存储空间是否已满，若已经满了则返回ERROR
将第n至i为的元素依次向后移动一个位置，空出第i个位置
将要插入的新元素e放入第i个位置

表长加一

Status ListInsert_Sq(SqList &L, int i,ElemType e)
{
    if( i < 1 || i > L.length + 1)return ERROR;
    if(L.length == MAXSIZE) return ERROR;
    for(j = L.length-1; j >= i-1; j--)
    {
        L.elem[j+1] = L.elem[j];
    }
    L.elem[i-1] = e;
    L.length++;
    return OK;
}

时间分析
1. 若插入在为节点则无需移动（特别快）
2. 若插入在首节点。则表中元素都向后移（特别慢）
3. 若要考虑在各种位置插入（共n+1种情况）
  
  E(ins) = 1/(n+1)(从1到n+1)[n-i+1] = 1/(n+1) *(0+1+2+3+·····n) = 1/（n+1） * n(n+1)/2 = n/2;
4. 时间复杂度O(n);

顺序表删除

删除位置在最后：直接删除即可，length-1；
删除位置在中间：需要删除该位置的元素，并将该位置后面的元素依次前移
删除位置在最前面：删除完毕后依次前移即可
算法思想
1. 判断删除位置i是否合法（合法值为1<=i<=n）
2. 将欲删除的元素保留在e中
3. 将第i+1至第n位的元素依次前移一个位置
4. 表长减一，删除成功后返回OK
算法的实现

Status ListDelete_Sq(SqList &L, int i, int e)
{
    if((i<1)||(i>L.length))return ERROR;
    e = L.elem[i-1];
    for(j = i;j <=L.length-1; j++)
        L.elem[j-1] = L.elem[j];
    L.length--;
    return e;
}

时间消耗分析

i=1 i=2 i=3 ···· i = n

n-1 n-2 n-3 ···· 0

E(del) = 1/n (i从1到n)（n-i） = 1/n * (n-1)*n/2 = (n-1)/2;

时间复杂度为O(n);

i=1	i=2	i=3	····	i = n
n-1	n-2	n-3	····	0

顺序表总结

顺序表的特点：
- 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系即线性表的逻辑结构与存储结构一致
- 在访问线性表时，可以快速的计算出任何一个数据元素的存储地址，因此可以粗略的认为，访问每个元素所化的时间相等
- 这种存取元素的方法称为随机存取法
顺序表的操作算法分析
- 时间复杂度
  - 查找，插入，删除，算法的平均时间复杂度为O(n)
- 空间复杂度
  - S(n) = O(1)
  - 没有辅助空间

类c语言补充（c语言版）

其中Elemtype表示该数据类型的长度， MaxSize表示数组的长度；
sizeof(Elemtype)*MaxSize 表示需要从内存中获取这么大的地址，而这么大的地址将要去干什么，是存除整形，浮点型，还是结构体，这就需要我们前面括号里的（ElemType *）来表示
使用ElemType*除了表示为这些内存空间需要存放的数据类型，还能进行数据类型的强制转换，因为L.data 应该存储数组的首地址
malloc（m）开辟m字节长度的地址空间，并返回这段空间的首地址
sizeof（x），计算变量x的长度
free（p），释放指针p所指变量的内存，彻底删除一个变量
都需要加载头文件 <stdlib.h>

类c语言补充（c++版）

使用new来代替c语言中malloc的臃长代码

new 类型名T(初始值表)

  功能： 申请用于存放T类型对象的内存空间，并依初值列表来赋初值

  结果值：

  		成功：T类型的指针，指向新分配的内存

  		失败： 0（NULL）

delete 指针p

功能：

释放指针p所指向的内存，p必须是new操作的返回值
函数调用时传送给形参表的实参必须是形参三个一致

类型，个数，顺序

参数传递时有两种方式

传值方式：参数为整型，实型，字符型等；

传地址

参数为指针变量

参数为引用类型

这个是c++中的语法

void main()
{
    int i = 5;
    int &j = i;
    i = 7;
}

则j也等于7；其中第二个步骤的含义就是j 是 i 的别名，他们俩是同一个东西，改一动二

以下是交换a,b值的方法

// 第一种
int main()
{
    float a,b;
    swap(&a,&b);
}
void swap(float *m, float *n)
{
    float temp;
    temp = *m;
    *m = *n;
    *n = temp;
}
// 第二种 c++方法
int main()
{
    float a,b;
    swap(a,b);
}
// 这里就是交换ab的值， 使用c++中的语法 & 来给a,b取别名，从而交换mn的值来交换ab的值
void swap(float &m, float &n)
{
    float temp;
    temp = m;
    m = n;
    n = temp;
}

参数为数组名
引用类型做形参的三点说明
1. 传递引用给参数与传递指针的效果是一样的，形参变换实参也发生变化
2. 引用类型作为形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量作为参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本，因此，当参数传递数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好
3. 指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“*指针变量名”的形式进行运算，者恒容易产生错误且程序阅读性较差，另一方面，再主调函数的调用点出，必须使用变量的地址作为实参

链表

链表的链式表示和实现

链式存储结构
- 节点在存储器中的位置是任意的，即逻辑上相邻的数据元素，在物理上不一定相邻
- 线性表的链式表又称为非顺序映像或链式映像
- 用一组物理位置任意的存储单元来存放链表的元素
- 这组存储单元可以是连续的，也可以是分散的，
- 链表中元素的逻辑次序和物理次序不一定相同
与链式存储有关的术语
1. 节点：
  - 数据元素的存储映像，由数据域和指针域组成
2. 链表：
  - n个节点由指针链组成一个链表
  - 他是线性表的链式存储映像，称为线性表的链式存储结构

链表形式

单链表
- 结点只有一个指针域的链表，称为单链表，或线性链表
双链表
- 节点有两个指针域的链表称为双链表
循环链表
- 首位相接的链表称为循环链表
头指针，头结点，首元节点
- 头指针：指向链表中的第一个结点的指针
- 首元节点：是指向链表中存储第一个数据元素a1的节点
- 头结点：是在链表中的首元节点之前附设的一个节点
链表的两种形式
- 带头结点的
- 不带头结点的
- 讨论：在链表中设置头结点有什么好处
  1. 便于首元节点的处理
    
    首元节点的地址保存在头结点的指针域中，所以在链表中第一个位置操作和其他位置相同，无需进行任何处理
  2. 便于空表和非空表的统一处理
    
    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就同一了
- 讨论：头结点的数据域内装的是什么
  
  头结点的数据域可以为空，可以存放表的长度等附加信息，但是此节点不能计入链表长度值
如何表示空表
- 无头结点的时候： 头指针为空时表示空表
- 有头结点的时候：头结点的指针域为空表示空表
链表的特点
- 节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
- 访问时只能通过头指针进入链表，并通过每一个节点的指针域依次向后顺序扫描其余节点，所以寻找第一个，和最后一个所花费的时间不同顺序存取法

单链表

单链表的命名

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名，若头指针名是L，则把链表称为表L

单链表基本操作的实现

单链表的初始化
- 即构造一个空表
算法步骤
- 生成新节点作头结点，用头指针L指向头结点
- 将头结点的指针域置空

算法描述

// 初始化
Status LnitList_L(LinkList &L)
{
	L = new LNode;  //  或者 L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	return OK;
}

补充算法------判断链表是否为空
空表：链表中无元素，称为空链表（头指针和头结点仍然存在）

算法思路：判断头结点的指针域是否为空

int ListEmpty(LinkList L)
{
	if(L->next)
        return 0;
	else
		return 1;
}

补充算法-------单链表的销毁，链表销毁后不存在（头结点，头指针都不存在）
算法思路：从头指针开始，依次释放所有的结点，这里需要有两个指针变量，一个指向头结点，另一个指向头结点的下一个

循环结束条件头指针为空

Status DeleteList_L(LinkList *L)//销毁单链表L
{
    Londe  *p;
	p = (LNode*)malloc(sizeof(LNode));
    while(L)//循环结束条件L不为空
    {
        p = L;//先将头结点地址赋值给临时变量
        L = L->next;//再将头指针指向下一个
        free(p);//释放该节点
    }
    return OK;
}

补充算法 ------ 清空链表
链表仍然存在，但链表中无元素，成为空链表（头结点，头指针依然存在）
算法思路，依次释放所有结点，并将头结点指针域设置成空

循环结束条件指向最后一个元素

Status ClearList_L(LinkList *L)//清空单链表L
{
    Londe  *p,*q;
    p = L->next;
    while(p)//循环结束条件指向最后一个了
    {
    	q = p->next;
        free(p);//释放该节点
        p = q;
    }
    L->next == NULL;
    return OK;
}

补充算法 ---- 求单链表的表长

思路：从首元节点开始，依次计数所有结点

int ListLength_L(LinkList L) // 返回值中数据元素的个数
{
    int i = 0;
    LNode *p;
    p = L->next;
    while(p)
    {
		i++;
        p = p->next;
    }
    return i;
}

取值-----取单链表中第i个元素的内容
思路：从链表的头指针出发顺着链域next逐个结点往下搜索，知道索搜到第i个结点为止，因此，链表不是随机存取结构

步骤：

从第一个结点（L->next）顺链扫描用指针p记录当前所扫描到的结点，p的初值为p=L->next
.j做计数器，累计当前扫描过的节点数，j的初值为1
当p指向扫描到的下一节点的时候，计数器j+1

当j === i时找到，退出程序

Status GetElem_L(LinkList L, int i, ElemType &e)
// 获取线性表中的某个数据元素，通过变量e返回
{
    p = L->next;
    while(p&&j<i)
    {
        p = p->next;
        j++;
    }
    if( j == i)
    {
        e = p->date;
    }
    else
    {
        return ERROR;
    }
}

查找：
1. 按值查找：根据指定数据获取该数据所在的位置（该数据的地址）
2. 按值查找：根据指定数据获取该数据所在的位置序号（是第几个数据元素）

插入：在第i个结点前插入新结点

Lnode *LocateElem_L(LinkList L, Elemtype e)
// 在线性表中查找值为e的数据元素
// 找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
{
    LinkList p;
    p = L->next;
    while(p&&p->data!=e)
    {
        p = p->next; 
    }
    // 返回地址
    return p;
}

Lnode *LocateElem_L(LinkList L, Elemtype e)
// 在线性表中查找值为e的数据元素
// 找到，则返回L中值为e的数据元素的位置，查找失败返回NULL
{
    int i = 1;
    LinkList p;
    p = L->next;
    while(p&&p->data!=e)
    {
        p = p->next; 
        i++
    }
    // 返回地址
    if( p!=NULL)
    {
        return i;
    }
    else
    {
        return 0;
    }
}

插入：在第i个结点前插入新节点

Status ListInsert_L(LinkList &L, int i, Elemtype e)
// 在L中第i个元素之前插入数据元素e
{
    int a = 0;
    LinkList p, q;
    p = L;
    while(a < i-1 && p)
    {
        p = p->next;
        a++;
    }
    if( a == i-1 )
    {
       q = (LNode*)malloc(sizeof(LNode))
    	q->date = e;
    	p->next = q->next;
    	p->next = q; 
        // 这两步交换位置的算法不能颠倒先后位置，否则会导致，数据丢失，交换失败
        return OK;
    }
    else
    {
        return ERROR
    }
        
    
}

删除删除第i个结点

Status ListDelete_L(LinkList &L, int i, Elemptype &e)
// 在L中删除第i个元素
{
    int a = 0;
    LinkList p, q;
    p = L;
    while(p->next && a <i-1)
    {
        p=p->next;
        a++;
    }
    if( !(p->next) || a >i-1)
        return ERROR;
    q = p->next;
    e = q->date;//保存要删除的元素的位置
    p->next = q->next;
    free(q);
    return OK;
}

分析单链表插入，查找，删除算法的时间效率
1. 查找：
  - 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O（n）
2. 插入和删除
  - 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)
  - 但是，如果要在单链表中进行前插或删除的操作，由于要从头查找前驱结点，所耗的时间复杂度为O(n);

建立单链表：

头插法--------元素插入在链表头部，也叫做前插法

从一个空表开始，重复读入数据；
生成新节点，将重复读入的数据存放到新节点的数据域中

从最后一个结点开始，依次将个节点插入到链表的前端、

算法描述

void CreateList_H(LinkList L, int n)
{
    L = (LNode *)malloc(sizeof(LNode));
    LinkList p;
    L->next = NULL;   // 初始化建立一个带头结点的单链表
    for(int i=n; i > 0; i--)
    {
        p = (LNode *)malloc(sizeof(LNode)); //生成新节点
        scanf("%f", p->date);//输入元素值
        p->next = L->next;//插到表头
        L->next = p;
    }
}

尾插法 ----- 元素插入在链表的尾部，也叫做后插法

从一个空表L开始，将新节点逐个插入到链表的尾部，尾指针r指向链表的尾结点。

初始时，r同L均指向头结点，每读入一个元素则申请一个新节点，将新节点插入到尾结点后r，指向新节点

void CreateList_R(LinkList L, int n)
{
    L = (LNode)malloc(sizeof(LNode));// 申请位置
    LinkList r,p; //创建尾结点和临时结点
    L->next = NULL; //初始化头结点
    r = L; // 使r和L同时指向头结点（初始化r）
    for( int i = 0; i < n; i++)
    {
        p = (LNode)malloc(sizeof(LNode));// 创建
        scanf("%f", p->date);// 输入数据
        p->next = NULL;// 初始化
        r->next = p;// 零尾结点指向它
        r = p;//  令它成为尾结点
    }
}

循环链表

定义

循环链表使一种头尾相接的链表（即表中最后一个结点的指针域指向头节点，整个链表形成一个环）
在单链表中当链表为空的时候，头结点的指针域指向NULL，在循环链表中，当链表为空的时候，头结点的指针域指向本身
优点：从表中任意节点出发均可找到表中的其他结点
判断结束方式
- 由于循环链表中没有NULL指针，故涉及遍历操作的时候，其终止条件就不再是像非循环链表那样判断p或p->next是否为空，而是判断他们是否等于头指针
- 循环条件
  
  p != NULL --------------> p != L
  
  p->next != NULL------> p->next != L
- 头指针表示单循环链表
  1. 找到a1的时间复杂度：O(1)
  2. 找到an的时间复杂度为：O(n)
    
    注意：表的操作通常是在表的首位位置上进行的
    
    所以，在使用循环链表的时候我们同通常使用尾指针来运算；
注意：不管是头指针还是尾指针，都需要创建头结点
- 在使用尾指针的时候
  1. a1的存储位置是：R—>next—>next;
  2. an的存储位置是：R；
  3. 他们的时间复杂度都为O(1);

循环链表的合并

操作：

保存A链表的头结点的地址 p = A->next;
先让A链表的最后一个指向B链表的第一个 A->next = B ->next->next;
释放B链表的头结点 free(B->next);

将B链表的尾指针指向A链表的头结点 B->next = p;

算法描述

LinkList Connect(LinkList A, LinkList B)  //参数为两个循环链表的尾指针
{
    LinkList p;
    p = A->next; // 保留A链表的头结点的位置
    A->next = B->next->next;// 让A链表的尾部指向B链表的头部
    free(B->next);//  释放B链表的头结点
    B->next = p;//  让B链表的尾指针指向A链表的头结点
    return B;
}
// 时间复杂度为O(1);

双向链表

单链表的结点->有指示后继的指针域->找后继节点方便；

即：查找某节点的后继结点的执行时间为O(1)

->无指示前驱的指针域->找前趋结点难（从表头出发查找）

即：查找某节点的前驱结点的执行时间为O(n)

双向链表可以克服这种困难

双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表

双向链表的结构定义：

typedef struct DuLNode
{
    Elemtype date;
    struct DuLNode *prior, *next;
}DuLNode, *DuLinkList;

其中空链表表示：只有头结点存在，并且头结点中前驱和后继都为空

双向循环链表

让头结点的前驱指针指向链表的最后一个结点
让最后一个结点的后继指针指向头结点
双向链表结构的对称性
- p->prior->next = p = p->next->prior
- 可以通过一个结点的前驱，或者后继结点来找到自己本身的位置

双向链表的插入

思路：在p结点初添加一个元素s
1. 先给s申请内存，并给数据域赋值
2. 令s->prior = p->prior;
3. 令p->prior->next = s;
4. s->next = p;
5. p->prior = s;
6. 添加完毕

实现

void ListInsert_Dul(DuLinkList L, int i, ElemType e)//在位置为i处插入数据e
{
    DuLinkList p, s;
    int n = 0;
    p = L->next;
    while(p && n < i )
    {
        n++;
        p=p->next;
    }
    if( n > i || p)
    {
        return ERROR;
    }
    s = (DuLinkList)malloc(sizeof(DuLinkList));
    s->date = e;
    s->prior = p->prior;
    s->next = p;
    p->prior->next = s;
    p->prior = s;
    return OK;
}

双向链表的删除

思路：删除p结点的方法
1. 令p的前趋结点的后续指针指向p的后续结点
2. 令p的后续节点的前趋指针指向p的前趋结点
3. p->prior->next = p->next;
4. p->next->prior = p->prior;

实现

void ListDelete_Dul(DuLinkList L, int i,ElemType *e)//删除i位置的结点
{
    DuLinkList p;
    int n = 0;
    p = L->next;
    while(p && n < i )
    {
        n++;
        p=p->next;
    }
    if( n > i || p)
    {
        return ERROR;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    e = p->date;
    free(p);
    return OK;
}

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

链式存储结构的优点
- 节点空间可以动态申请和释放
- 数据元素的逻辑次序靠结点的指针来表示，插入和删除时不需要移动数据元素
链式存储的缺点
- 存储密度小，每个结点的指针域需额外占用存储空间，当每个结点的数据与所占字节不多时，指针域所占存储空间的比重显的很大
  - 存储密度是指结点数据本身所占的存储量，和整个结点结构中所占的存储量之比，即：
    
    存储密度 = （结点数据本身所占用的空间）/（节点占用的空间总量）
    
    例如在一个节点中 date域占用8个字节，指针域占用4个字节 则存储密度 = 8/12 = 67%
  一般的，存储密度越大，存储空间的利用率就越高，显然，顺序表的存储密度为1，而链表的存储密度小于1
- 链式存储结构时非随机存取结构，对任意一点的操作都要从头指针，依指针链查找到该节点，这增加了算法的复杂度

顺序表和链表的比较

	顺序表	链表
存储空间（空间）	预先分配，会导致空间闲置或溢出现象	动态分配，不会出现空间闲置或溢出等情况
存储密度（空间）	不用为表示节点的逻辑关系而增加额外的开销，存储密度为 1	需要借助指针来体现元素之间的逻辑关系，存储密度小于 1
存取元素（时间）	随机存取，按位置访问元素时间复杂度为O(1)	顺序存取，按位置访问元素时间复杂度为O(n)
插入，删除（时间）	平均移动表中一半的元素时间复杂度为O(n)	不需要移动元素，确定插入删除位置后时间复杂度为O(1)
适用情况	1.表长变换不大，且能事先确定变化的范围 2.很少进行插入或者删除操作，经常按元素位置序号访问数据元素	1.长度变化较大 2.频繁的进行插入或删除操作

线性表的合并

问题描述：将两个线性表合并，并且里面相同的元素只出现一次

La = (7,5,3,11) 			Lb(2,6,3)  ===>     La(7,5,3,11,2,6)

算法步骤：

	依次取出Lb中的没一个元素，执行以下操作：

在La中查找该元素

如果找不到，则将其插入到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); // 查找i位置的元素，并将其存在e中
        if(!LocateElem(La,e)) // 如果La中不存在e，则进行下一步
        {
            ListInsert(&La, ++La_len, e); // 插入操作
        }
    }
}

有序表合并

已知线性表La和Lb中的数据元素按值非递减（可能有重复的）有序排序，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列

La = (1,7,8)    Lb = (2,4,6,8,10,11)   =====>   Lc = (1,2,4,6,7,8,8,10,11)

算法步骤

创建一个空表Lc
依次从La或Lb中“摘取“元素较小的结点插入到Lc表的最后，直至其中一个表，遍历完毕为止

继续将La或Lb其中的一个表的剩余结点插在Lc表的最后

算法描述(用顺序表实现)

void MergeList_Sq(SqList LA, SqList LB,SqList &LC)
{
    float *pa, *pb, *pa_last, *pb_last, *pc;
    pa = LA.elem;
    pb = LB.elem;
    pc = LC.elem;
    pa_last = LA.elem + LA.length-1;
    pb_last = LB.elem + LB.length-1;
    while(pa != pa_last && pb != pb_last)
    {
        if( *pa <= *pb)
        {
            *pc++ = *pa++;
        }
        else( *pa > *pb)
        {
            *pc++ = *pb++;
        }
    }
    if( pa == pa_last && pb != pb_last)
    {
       	while(pb != pb_last)
        {
            *pc = *pb;
            pc++;
            pb++;
        }
    }
    else if(pa != pa_last && pb == pb_last)
    {
        while(pa != pa_last)
        {
            *pc = *pa;
            pc++;
            pa++;
        }
    }
}
//算法的时间复杂度为：O(ListLength(La) + ListLength(Lb))
//算法的空间复杂度为：O(ListLength(La) + ListLength(Lb))

算法描述（用链表实现）

void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
{
    pa = La->next;
    pb = Lb->next;
    pc = Lc = La;
    while(pa && pb)
    {
        if( pa->date <= pb -> date)
        {
            pc->next = pa;
            pc = pc->next;
            pa = pa->next;
        }
        else( pa ->date > pb->date)
        {
            pc->next = pb;
            pc = pc->next;
            pb = pb->next;
        }
    }
    pc->next = pa?pa:pb; // 插入剩余段
    free(Lb);
}
// 时间复杂度O(La.length + Lb.length)
// 空间复杂度O(1)

线性表案例的分析和实现

案例 1：一元多项式的运算：实现两个多项式的加减乘除运算

Pn(x) = p0+p1x+p2x+p3X^{2+·····+pnx}n;

线性表 p = (p0, p1,p2····pn)

(每一项的指数i隐含在其指数pi的序号中)

可以使用数组来存储这些多项式的系数和指数

例如

Pa(x) = 10 + 5x - 4x^2 + 3x^3 + 2x^4;

Pb(x) = -3 + 8x + 4x^2 - 5x^4 + 7x^5 - 2x^6;

新建一个数组pc来存储系数

系数pa[i]	10	5	-4	3	2				5
系数pb[i]	-3	8	4	0	-5	7	2		7
系数pc[i]	7	13	0	3	-3	7	2		7

案例 2：稀疏多项式的运算

多项式非零项的数组的表示

a). A(x) = 7+3x+9x^8+5x17

下标i 0 1 2 3

系数a[i] 7 3 9 5

指数 0 1 8 17

b). B(x) = 8x+22x^7-9x8

下标i 0 1 2

系数a[i] 8 22 -9

指数 1 7 8

c). C(x) = A(x)+B(x)

下标i 0 1 2 3

系数a[i] 7 11 22 5

指数 0 1 7 17

下标i	0	1	2	3
系数a[i]	7	3	9	5
指数	0	1	8	17

下标i	0	1	2
系数a[i]	8	22	-9
指数	1	7	8

下标i	0	1	2	3
系数a[i]	7	11	22	5
指数	0	1	7	17

实现（顺序表）

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

实现（链式表）

指针p1和p2初始化，分别指向Pa和Pb的首元节点
p3指向多项式的当前节点，初值为Pa的头结点
当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值

（p1->expn和p2->expn ）有下列三种情况
- 当p1->expn == p2->expn时，则将两个节点中的系数相加
  - 若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点
  - 若和为零，则删除p1和p2所指结点
- 当p1->expn < p2->expn时，则应摘取p1所指结点插入到”和多项式“链表中去
- 当p1->expn>p2->expn 时，则应摘取p2所指结点插入到”和多项式“链表中去
将非空多项式的剩余段插入到p3所指结点之后
释放Pb的头节点