线性表

线性表：零个或多个数据元素的有限序列。

线性表的定义

若将线性表记为(A1,…,Ai,…,An),则表中Ai-1领先于Ai，Ai领先于Ai+1，称Ai-1是Ai的直接前驱元素，Ai+1是Ai的直接后继元素，当i = 1,2,…,n-1时，Ai有且仅有一个直接后继，当i = 2,3,…,n时，Ai有且仅有一个直接前驱。

线性表元素个数n(n >= 0)定义为线性表的长度，当n = 0时，称为空表。

在较复杂的线性表中，一个数据元素可以由若干数据项组成。

线性表的抽象数据类型

上述操作都是基本操作，实际问题中涉及线性表的更复杂的操作可以由这些基本操作的组合来完成。例如：

//将所有在线性表Lb中但不在La中的数据元素插入到La中
void union(List *La,List Lb)
//List代指所有线性表，不是具体的一种结构
{
    int La_len,Lb_len;
    ElemType *e;//声明指向与La和Lb相同的数据元素e的指针
    
    La_len = ListLength(La)；
    Lb_len = ListLength(Lb);
    for (int i = 1;i <= Lb_len;i++)
    {
        GetELem(Lb,i,*e);//取Lb中第i个元素赋值给e
        if (!LocateElem(La,*e))//La中不存在和e相同的数据元素
            ListInsert(La,++La_len,*e);//插入到La的末尾
    }
}//在一些指针方面对书上代码做了些改动，若有大佬发现问题欢迎提出

线性表的顺序存储结构

线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。

结构代码

#define MAXSIZE 20
typedef int ElemType;
typedef struct {
    ElemType deta[MAXSIZE];//数组存储数据元素，最大值为MAXSIZE
    int length;//线性表当前长度
}SqList;

描述顺序存储结构三个属性：

• 存储空间的起始位置：数组data的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度MAXSIZE
• 线性表的当前长度：length

数组长度是存放线性表的存储空间的长度，线性表的长度是线性表中数据元素的个数(变化的)，在任意时刻，线性表的长度应小于等于数组长度

假设每个数据元素占用c个存储单元，则线性表中第i+1个数据元素的存储位置和第i个元素的存储位置满足下列关系(LOC表示获得存储位置的函数)

​ LOC(Ai+1) = LOC(Ai) + c

因此

​ LOC(Ai) = LOC(A1) + (i-1) * c

通过这个公式可以随时算出线性表中任意位置的地址，对于计算机来说都是相等的时间，存储性能为O(1),我们把具有这一特点的存储结构称为随机存取结构。

获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;//函数的类型，其值是函数结果状态代码，如OK等
//初始条件：顺序线性表L已经存在，1 <= i <= ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
Status GetElem (SqList L,int i,ElemType *e)
{
    if (L.length = 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i-1];
    return OK;
}

插入元素操作

//初始条件：顺序线性表已经存在，1 <= i <= ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert (SqList *L,int i,ElemType e)
{
    if (L->length == MAXSIZE || i < 1 || i > L->length+1)
        return ERROR;
    if (i <= L->length)//插入的位置不在表尾
    {
        for (int k = L->length-1;k >= i-1;k--)
            L->data[k+1] = L->data[k];
        //将要插入位置之后的数据元素向后移动一位
    }
    L->data[i-1] = e;
    L->length++;
    return OK;
}

删除元素操作

//初始条件：顺序线性表已经存在，1 <= i <= ListLength(L)
//操作结果：删除L第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete (SqList *L;int i;ElemType *e)
{
    if (L->length = 0 || i < 1 || i > L->length )
        return ERROR;
    *e = L->data[i-1];
    if (i < L->length)//删除的不是最后位置
    {
        for (int k = i;k < L->length;k++)
            L->data[k-1] = L->data[k];
        //将删除位置后继元素前移
    }
    L->length--;
    return OK;
}

插入或删除时平均时间复杂度为O(n)

顺序存储结构的优缺点

优点：

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任意位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的”碎片”

线性表的链式存储结构

存储数据元素信息的域称为数据域，存储直接后继元素位置的域称为指针域，指针域中存储的信息称作指针或链，这两部分组织数据元素Ai的存储映像，称作结点

单链表：每个结点中只包含一个指针域

头指针：链表第一个结点的存储位置(无论链表是否为空，头指针均不为空，是链表的必须元素。若链表有头结点，则是指向头结点的指针)

头结点：单链表第一个结点之前的结点，其指针域存储指向第一个结点的指针(实现了在第一个元素结点前插入结点和删除第一个结点的操作与其他结点操作的统一，不是链表的必须元素)

结构代码

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;

以下代码均假定头结点存在。

获取元素操作

//初始条件：顺序线性表L已经存在，1 <= i <= ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
Status GetElem (SqList L,int i,ElemType *e)
{
    int j = 1;
    LinkList p;
    
    p = L->next;//让p指向链表第一个结点(非头结点)
    while (p && j < i)//p不为空或计数器j还没等于i时，循环继续
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;//第i个元素不存在
    *e = p->data;
    return OK;
}

单链表的插入

//初始条件：顺序线性表已经存在，1 <= i <= ListLength(L)
//操作结果：在L中第i个结点之前插入新的数据元素e，L的长度加1
Status ListInsert (SqList *L,int i,ElemType e)
{
    LinkList p,s;
    int j = 1;
    
    p = L->next;
    while (p && j < i-1)//寻找第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;//第i个元素不存在
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;//将p的后继结点赋值给s的后继
    p->next = s;//将s赋值给p的后继
    return OK;
}

单链表的删除

//初始条件：顺序线性表已经存在，1 <= i <= ListLength(L)
//操作结果：删除L第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete (SqList *L;int i;ElemType *e)
{
    int j = 1;
    LinkList p,q;
    
    p = L->next;
    while (p && j < i-1)//寻找第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;//第i个元素不存在
    q = p->next;//q指向第i个结点
    p->next = q->next;//将q的后继结点赋值给p的后继结点
    *e = q->data;
    free(q);
    return OK;
}

单链表的整表创建(头插法)

//随机产生n个元素的值，建立带头结点的单链表L
void CreateListHead(LinkList *L,int n)
    // 必须传入指针的地址，这样*L才为原指针，对*L的操作才是对原指针的操作；若函数参数为LinkList L，传入原指针，则L表示的是原指针的值，即为空，那么对L的操作与原指针没有任何关系。  --2019.1.15
{
    LinkList p;
    
    srand(time(0));//初始化随机种子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;//建立一个带头结点的单链表
    for (int i = 0;i < n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand()%100+1；//随机生成100以内的数字
        p->next = (*L)->next;
        (*L)->next = p;//插入到表头
    }
}

单链表的整表创建(尾插法)

void CreateListHead(LinkList *L,int n)
{
    LinkList p,r;
    
    srand(time(0));//初始化随机种子
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;//r为指向尾部的结点
    for (int i = 0;i < n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+1；
        r->next = p;
        r = p;
    }
    r->next = NULL;//表示当前链表结束
}

单链表的整表删除

//初始条件：顺序线性表L已经存在
//操作结果：将L重置为空表
Status ClearList (LinkList *L)
{
    LinkList p,q;
    
    p = (*L)->next;//p指向第一个结点
    while (p)//没到表尾
    {
        q = p;
        p = p->next;
        free(q);
      /*书上代码：
        q = p->next;
        free(p);
        p = q;
      */
    }
    (*L)->next = NULL;
    return OK;
}

单链表结构与顺序存储结构的优缺点

结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；若需要频繁插入与删除时，宜采用单链表结构。
• 当线性表中元素个数变化较大或根本不知道有多大时，最好采用单链表结构，而若事先知道线性表大致长度，则顺序存储结构效率高很多。

其他链表

静态链表

用数组描述的链表(给没有指针的高级语言设计的一种实现单链表能力的方法)

优点：

• 在插入和删除操作时，只需修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点

缺点：

• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了顺序存储结构随机存取的特性

(具体代码日后没事再更，详情可见大话数据结构P71页)

循环链表

将单链表中终端结点的指针端由空结点改为头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

循环链表解决了一个很麻烦的问题，即如何从当中一结点出发，访问到链表全部结点。

单链表中头指针访问第一个结点需要O(1)时间，访问最后一个结点需要O(n)时间。

循环链表中若设置尾指针，则查找终端结点与开始结点的时间复杂度均为O(1)。

用尾指针非常容易合并两个循环链表。

双向链表

在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

结构代码：

typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
}DulNode, *DulLinkList;

p->next->prior = p = p->prior->next

在p与p->next之间插入结点s：

s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;

先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继

删除结点p：

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);