数据结构与算法--线性表

1. 线性表

1.1 线性表的定义和基本运算

定义：线性表是具有相同数据类型的n个数据元素的有限序列。除表头元素外，每个元素有且仅有一个直接前驱；除表尾元素外，每个元素有且仅有一个直接后继。
特点：个数有限；具有逻辑上的顺序性；数据元素类型都相同。
基本操作：初始化；求表长；按值查找；按位查找；插入；删除；输出；判空。

1.2 顺序表

#define maxSize 100
#define ElemType int
typedef struct{
    ElemType data[maxSize];
    int length;
}SqList;

基本操作
（1）插入：在顺序表L的第i个位置插入新元素e。注意i的取值范围为(1<=i<=L.length+1)。第i个元素及其后的所有元素都要后移一个位置。要注意区分顺序表的位序和数组下标。

bool ListInsert(SqList& L, int i, ElemType e){
    if (i < 1 || i > L.length + 1)//插入位置出错
        return false;
    if (L.length >= maxSize)//存储空间已满
        return false;
    for (int j = L.length; j >= i; j--)//元素后移
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;
    return true;
}

平均时间复杂度为O(n)。
（2）删除：删除顺序表L中第i个位置的元素，若成功返回true，并将被删除的元素用引用变量e返回，否则返回false。注意i的范围为1<=i<=L.length。

bool ListDelete(SqList& L, int i, ElemType& e){
    if (i < 1 || i > L.length)//删除位置出错
        return false;
    e = L.data[i-1];
    for (int j = i; j < L.length; j++)//元素前移
        L.data[j-1] = L.data[j];
    L.length--;
    return true;
}

平均时间复杂度为O(n)。
（3）按值查找：在顺序表L中查找第一个元素值等于e的元素，并返回其位序。

int ListFind(SqList L, ElemType e){
    for (int i = 0; i < L.length; i++){
        if (L.data[i] == e)
            return i+1;
    }
    return 0;
}

平均时间复杂度为O(n)。

1.3 单链表

定义：通过一组任意的存储单元来存储线性表中的数据元素，并通过指针建立数据元素之间的逻辑关系。
优点：插入和删除元素不需要移动元素，只要修改对应的指针即可。
缺点：不能随机访问，访问元素时要遍历单链表。
结点类型

typedef struct LNode{
    ElemType data;//数据域
    struct LNode* next;//指针域
}LNode, *LinkList;

基本操作
（1）头插法建表：

LinkList List_HeadInsert(ElemType *arr, int n){
    //使用头插法由长度为n的数组arr创建单链表
    LNode *s;
    LNode *L = (LNode*)malloc(sizeof(LNode));
    L->next = nullptr;
    for (int i = 0; i < n; i++){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = arr[i];
        s->next = L->next;
        L->next = s;
    }
    return L;
}

平均时间复杂度为O(n)。
（2）尾插法建表

LinkList List_TailInsert(ElemType *arr, int n){
    LNode *L = (LNode*)malloc(sizeof(LNode));
    L->next = nullptr;
    LNode *s, *p = L;//p一直指向末尾元素
    for (int i = 0; i < n; i++){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = arr[i];
        p->next = s;
        p = s;
    }
    return L;
}

平均时间复杂度为O(n)。
（3）按序号查找节点

LNode* GetElem(LinkList L, int i){
    //按序号查找节点值
    LNode* res = L;
    for (int j = 0; j < i; j++){
        if (res == nullptr)
           return nullptr;
        res = res->next;
    }
    return res;
}

平均时间复杂度为O(n)。
（4）按值查找节点

LNode* LocateElem(LinkList L, ElemType e){
    //按值查找表节点
    LNode* res = L->next;
    while (res != nullptr && res->data != e)
        res = res->next;
    return res;
}

平均时间复杂度为O(n)。
（5）插入节点：找第i-1个节点，在它的后面插入新的节点

bool LinkListInsert(LinkList& L, int i, ElemType e){
    //在第i个节点处插入节点
    LNode* pre = L;
    int cnt = 0;
    while (pre != nullptr && cnt < i - 1){//找第i-1个节点
        pre = pre->next;
        cnt++;
    }
    if (pre != nullptr){
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = pre->next;
        pre->next = s;
        return true;
    }
    else
        return false;
}

查找第i-1个元素，时间复杂度为O(n)，插入节点的时间复杂度为O(1).
改进：假设s是待插节点，要将s插入到p的前面，可以先将s插入到p的后面，再交换两者元素的值。
（6）删除节点

bool LinkListDelete(LinkList& L, int i){
    //删除第i个节点
    LNode* pre = L;
    int cnt = 0;
    while (pre != nullptr && cnt < i - 1){
        pre = pre->next;
        cnt++;
    }
    if (pre != nullptr){
        LNode *q = pre->next;
        pre->next = q->next;
        free(q);
        return true;
    }
    else
        return false;
}

查找第i-1个元素，时间复杂度为O(n)，删除节点的时间复杂度为O(1).
改进：要删除p所指节点，将p后继节点的值赋给自身，然后删除后继节点。

1.4 双链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
节点类型

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

插入操作：在p所指结点之后插入节点s。

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

删除操作：删除p的后继结点q。

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