数据结构复习笔记（线性表）

线性表的顺序表示

数组静态分配。

#define MaxSize 50        // 定义线性表的最大长度
typedef struct {
    int data[MaxSize];    // 顺序表的元素
    int length;            // 顺序表的当前长度 
} SqlList;                // 顺序表的类型定义

课后练习

1、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

算法思路：搜索整个顺序表，查找最小值元素并记住其位置。搜索结束后，用最后一个元素填补空出的原最小值元素的位置。

bool Del_Min(SqList* L, int* value)
{
    // 删除顺序表L中最小元素节点，并通过引用型参数value返回其值
    // 若删除成功，则返回true；否则返回false
    if (L->length == 0)
    {
        return false;    // 表空，终止操作返回
    }
    value = L->data[0];
    int pos = 0;
    for (int i = 1; i < L->length; i++)
    {
        if (L->data[i] < value)
        {
            value = L->data[i];
            pos = i;
        }
    }
    L->data[pos] = L->data[L->length - 1];    // 空出的位置由最后一个元素填补
    L->length--;
    return true;
}

2、设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

算法思路：扫描顺序表L的前半部分元素，对于元素L.data[i]将其与后半部分的对应元素L.data[L.length - i - 1]进行交换。

void Reverse(SqList* L)
{
    int temp;
    for (int i = 0; i < L->length / 2; i++)
    {
        // 交换L.data[i]与L.data[L.length - 1 - i]
        temp = L->data[i];
        L->data[i] = L->data[L->length - 1 - i];
        L->data[L->length - 1 - i] = temp;
    }
}

3、对于长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

算法思路：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），边扫描L边统计k，并将不等于x的元素前移k个位置，最后修改L的长度。

理解：要想到用k下标来接收部位x的值，即重新复制L.data[k]，最后更新length。不要逐个前移。

void del_x(SqList* L)
{
    // 本算法实现删除顺序表L中所有值为x的数据元素
    int k = 0;        // 记录值不等于x的元素个数
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] != 'x')
        {
            L->data[k] = L->data[i];
            k++;    // 不等于x的元素增1
        }
    }
    L->length = k;
}

4、从有序顺序表中删除其值在给定值s与t之间（要求s < t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行。

算法思路：先寻找值大于等于s的第一个元素（第一个删除的元素），然后寻找值大于t的第一个元素（最后一个删除的元素的下一个元素），要将这段元素删除，只需直接将后面的元素前移。

注意：因为是有序表，所以删除的元素必然是相连的整体。

bool Del_s_t2(SqList* L, int s, int t)
{
    // 删除有序顺序表L中的值在给定值s与t之间的所有元素
    int i, j;
    if (s >= t || L->length == 0)
    {
        return false;
    }
    for (i = 0; i < L->length && L->data[i] < s; i++);    // 寻找值大于等于s的第一个元素，并记下i下标
    if (i >= L->length)
    {
        return false;    // 所有元素值均小于s，返回
    }
    for (j = i; j < L->length && L->data[j] <= t; j++);    // 寻找值大于t的第一个元素，记下j下标
    for (; j < L->length; i++, j++)
    {
        L->data[i] = L->data[j];    // 前移，填补被删元素位置
    }
    L->length = i;
    return true;
}

5、从顺序表中删除其值在给定值s与t之间（包含s和t，要求s < t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行。

算法思路：从前向后扫描顺序表L，用k记录元素值在s到t之间元素的个数（初始k=0）。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则执行k++。

优点：每个不在s到t之间的元素仅移动一次，算法效率高。

理解：也是借助k记录位置，重新对L.data[i]赋值。

bool Del_s_t(SqList* L, int s, int t)
{
    // 删除顺序表L中值在给定值s与t之间（要求s < t）的所有元素
    int k = 0;
    if (s >= t || L->length == 0)
    {
        return false;        // 线性表为空或s、t不合法，返回
    }
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] >= s && L->data[i] <= t)
        {
            k++;
        }
        else
        {
            L->data[i - k] = L->data[i];    // 当前元素前移k个位置
        }
    }
    L->length = L->length - k;    // 长度减少
    return true;
}

6、从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法思路：用类似于直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有有序表的最后一个元素相同，若相同则继续向后判断，若不同则插入到前面的非重复有序表的最后，直至判断到表尾为止。

注意：因为是有序顺序表，值相同的元素一定在连续的位置上。

bool Delete_Same(SqList* L)
{
    if (L->length == 0)
    {
        return false;
    }
    int i, j;    // i存储第一个不相同的元素，j为工作指针
    for (i = 0, j = 1; j < L->length; j++)
    {
        if (L->data[i] != L->data[j])    // 查找下一个与上个元素值不同元素
        {
            L->data[i++] = L->data[j];    // 找到后，将元素前移
        }
    }
    L->length = i + 1;
    return true;
}

7、将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思路：首先，按顺序不断取下两个顺序表表头较小的节点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

理解：两个有序表逐个元素比较，把小的值插入到新的顺序表。搞完一个表后，另一个表剩下的部分就直接插入到新的顺序表的后面。

注意：本算法非常典型，需牢固掌握。

bool Merge(SqList A, SqList B, SqList* C)
{
    // 将有序顺序表A与B合并为一个新的有序顺序表C
    if (A.length + B.length > C->MaxSize)    // 大于顺序表的最大长度
    {
        return false;
    }
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length)        // 循环，两两比较，小者存入结果表
    {
        if (A.data[i] <= B.data[j])
        {
            C->data[k++] = A.data[i++];
        }
        else
        {
            C->data[k++] = B.data[j++];
        }
    }
    while (i < A.length)    // 还剩一个没有比较完的顺序表
    {
        C->data[k++] = A.data[i++];
    }
    while (j < B.length)
    {
        C->data[k++] = B.data[j++];
    }
    C->length = k;
    return true;
}

8、已知在一维数组A[m + n]中依次存放两个线性表(a1, a2, a3, …, am)和(b1, b2, b3, …, bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1, b2, b3,…, bn)放在(a1, a2, a3, …, am)的前面。

算法思路：先将数组A[m + n]中的全部元素(a1, a2, a3, …, am, b1, b2, b3, …, bn)原地逆置为(bn, bn-1, bn-2, …, b1, am, am-1, am-2, …, a1)，再对前n个元素和后m个元素分别使用逆置算法，即可得到(b1, b2, b3, …, a1, a2, a3, …, am)，从而实现顺序表的位置互换。

void Reverse(int A[], int left, int right, int arraySize)
{
    if (left >= right || right >= arraySize)
    {
        return;
    }
    int mid = (left + right) / 2;
    for (int i = 0; i < mid - left; i++)
    {
        int temp = A[left + i];
        A[left + i] = A[right - i];
        A[right - i] = temp;
    }
}

void Exchange(int A[], int m, int n, int arraySize)
{
    /*
    数组A[m + n]中，从0到m-1存放顺序表(a1, a2, a3, ..., am)，
    从m到m+n-1存放顺序表(b1, b2, b3, ..., bn)，算法将这两个表的位置互换
    */
    Reverse(A, 0, m + n - 1, arraySize);
    Reverse(A, 0, n - 1, arraySize);
    Reverse(A, n, m + n - 1, arraySize);
}

9、线性表(a1, a2, a3, …, an)中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序。

算法思路：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求“用最少的时间”，这里应使用折半查找法。

oid SearchExchangeInsert(int A[], int n, int x)
{
    int low = 0, high = n - 1, mid;        // low和high指向顺序表下界和上界的下标
    while (low <= high)
    {
        mid = (low + high) / 2;        // 找中间位置
        if (A[mid] == x)
        {
            break;        // 找到x，推出while循环
        }
        else if (A[mid] < x)
        {
            low = mid + 1;    // 到中点mid的右半部去查
        }
        else
        {
            high = mid - 1;    // 到中点mid的左半部去查
        }
    }
    // 下面两个if语句只会执行一个，也可能两个都不执行
    if (A[mid] == x && mid != n - 1)    // 若最后一个元素与x相等，则不存在与其后继交换的操作
    {
        int temp = A[mid];
        A[mid] = A[mid + 1];
        A[mid + 1] = temp;
    }
    if (low > high)        // 查找失败，插入数据元素x
    {
        int i;
        for (i = n - 1;i > high;i--)
        {
            A[i + 1] = A[i];    // 后移元素
        }
        A[i + 1] = x;        // 插入x
    }
}

线性表的链式表示

单链表

线性表的链式存储又称为单链表。其中data为数据域，存放数据元素，next为指针域，存放其后继结点的地址。

单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

单链表的定义如下。

typedef struct LNode {        // 定义单链表结点类型
    int data;                // 数据域
    struct LNode* next;        // 指针域
}LNode, * LinkList;
// LNode* L            声明一个指向单链表第一个节点的指针
// LinkList L        代码可读性更强
// 使用LNode*：        强调这是一个节点
// 使用LinkList L;        强调这是一个单链表

增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点。

struct LNode* p = (struct LNode*)malloc(sizeof(struct LNode));    // 不使用typedef的声明
LNode* p1 = (LNode*)malloc(sizeof(LNode));    // 使用typedef后不需要写struct LNode

单链表又分为带头结点和不带头结点。带头结点写代码方便，不带头结点写代码麻烦。

初始化一个空的单链表。

// 初始化一个空的单链表（不带头结点）
bool InitList(LinkList L)
{
    L = NULL;
    return true;
}

// 初始化一个单链表
bool InitList(LinkList L)
{
    L = (LNode*)malloc(sizeof(LNode));    // 分配一个头结点
    if (L == NULL) return false;        // 内存不足
    L->next = NULL;
    return true;
}

判断单链表是否为空。

// 判断单链表是否为空（不带头结点）
bool Empty(LinkList L)
{
    return (L == NULL);
}

// 判断单链表是否为空（带头结点）
bool Empty(LinkList L)
{
    return (L->next == NULL);
}

单链表的优点：不要求大片连续空间，改变内容方便。

单链表的缺点：不可以随机存取，要耗费一定空间存放指针。

C语言的typedef关键字

C语言的typedef关键字，用于数据类型重命名。

语法：typdef <数据类型> <别名>

typedef int zhengshu;
typedef int* zhengshuzhizhen;

int x = 1;    // 等价于zhengshu x = 1;
int* p;        // 等价于zhengshuzhizhen p;

单链表上基本操作的实现

按位序插入（带头结点）

最好时间复杂度是O(1)，平均、最坏时间复杂度是O(n)。

// 在第i个位置插入元素e
bool ListInsert(LinkList L, int i, int e)
{
    if (i < 1) return false;
    LNode* p;    // 指针p指向当前扫描到的结点
    int j = 0;    // 当前p指向的是第几个结点
    p = L;        // L指向头结点，头结点是第0个结点
    while (p != NULL && j < i - 1)
    {
        p = p->next;    // 循环找到第i-1个结点
        j++;
    }
    if (p == NULL) return false;    // i的值不合法
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;    // 将结点s连到p之后
    return true;
}

按位序插入（不带头结点）

如果不带头结点，则插入、删除第1个元素时，需要更改头指针L。

// 在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList L, int i, int e)
{
    if (i < 1) return false;
    if (i == 1)    // 插入第一个节点的操作与其他结点不同
    {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;    // 让s指向原来的第一个元素a1
        L = s;            // 让头指针指向新结点s
        return true;
    }
    // ...
    int j = 1;    // 当前p指向的结点从1开始
    // ...
}

因此，不带头结点的话，代码写起来更加麻烦，推荐写代码时带头结点。

指定结点的后插操作

时间复杂度是O(1)。

// 后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode* p, int e)
{
    if (p == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) return false;    // 某些情况下有可能分配失败，如内存不足
    s->data = e;            // 用结点s保存数据元素e
    s->next = p->next;        // 让结点s指向p的后继
    p->next = s;            // 让结点p指向结点s
    return true;
}

指定节点的前插操作（偷天换日法）

时间复杂度是O(1)。

// 前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode* p, int e)
{
    if (p == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) return false;    // 内存分配直白
    s->next = p->next;        // 让s指向p的后继
    p->next = s;            // 让p指向s
    s->data = p->data;        // 将p中元素复制到s中
    p->data = e;            // p中元素覆盖为e
    return true;
}

按位序删除（带头结点）

最好时间复杂度是O(1)，平均、最坏时间复杂度是O(n)。

// 按位序删除（带头结点）
bool ListDelete(LinkList L, int i, int e)
{
    if (i < 1) return false;
    LNode* p;    // 指针p指向当前扫描到的结点
    int j = 0;    // 当前p指向的是第几个结点
    p = L;        // L指向头结点，头结点是第0个结点（不存数据）
    while (p != NULL && j < i - 1)    // 循环找到第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;    // i的值不合法
    if (p->next == NULL) return false;    // 第i-1个节点之后无其他结点
    LNode* q = p->next;        // 令q指向被删除结点
    e = q->data;            // 用e返回元素的值
    p->next = q->next;        // 将*q结点从链中“断开”
    free(q);                // 释放结点的存储空间
    return true;
}

删除指定结点p（偷天换日法）

删除结点p，需要修改其前驱结点的next。

方法1：传入头指针，循环寻找p的前驱结点。

方法2：偷天换日（类似于结点的前插的实现）。时间复杂度为O(1)。

// 按指定结点删除
bool DeleNode(LNode* p)
{
    if (p == NULL) return false;
    LNode* q = p->next;            // 令q指向*p的后继结点
    p->data = p->next->data;    // 和后继结点交换数据域
    p->next = q->next;            // 将*q结点从链中“断开”
    free(q);                    // 释放后继结点的存储空间
    return true;
}

按位查找（带头结点）

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

// 按位查找（带头结点）
LNode* GetElem(LinkList L, int i)
{
    if (i < 0) return NULL;
    LNode* p;        // 指针p指向当前扫描到的结点
    int j = 0;        // 当前p指向的是第几个结点
    p = L;            // L指向头结点，头结点是第0个结点（不存数据）
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}

封装后的按位插入

// 封装后的按位插入
bool ListInsert(LinkList L, int i, int e)
{
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);    // 找到第i-1个结点
    return InsertNextNode(p, e);    // p后插入新元素e
}

按值查找

时间复杂度为O(1)。

// 按值查找，找到数据域==e的结点
LNode* LocateElem(LinkList L, int e)
{
    LNode* p = L->next;    // 从第一个结点开始查找数据域为e的结点
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;    // 找到后返回该结点指针，否则返回NULL

}

求表的长度

时间复杂度为O(n)。

// 求表的长度
int Length(LinkList L)
{
    int len = 0;    // 统计表长
    LNode* p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

尾插法建立单链表

时间复杂度为O(n)。尾插法可以省略L->next = NULL;这一句初始化，因为后续会改变L的指向。但是，编程时，最好都要进行初始化，防止使用脏数据。

// 正向建立单链表
LinkList List_TailInsert(LinkList L)
{
    int x;    // 设元素类型为整型
    L = (LinkList)malloc(sizeof(LNode));
    LNode* s, * r = L;    // r为表尾指针
    scanf("%d", &x);    // 输入结点的值
    while (x != 9999)    // 输入9999表示结束
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;            // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;        // 尾结点指针置空
    return L;
}

头插法建立单链表

时间复杂度为O(n)。头插法的重要应用是链表的逆置。

// 逆向建立单链表
LinkList List_HeadInsert(LinkList L)
{
    LNode* s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));    // 创建头结点
    L->next = NULL;        // 初始为空链表
    scanf("%d", &x);    // 输入结点的值
    while (x != 9999)    // 输入9999表示结束
    {
        s = (LNode*)malloc(sizeof(LNode*));    // 创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;    // 将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

双链表

双链表克服了单链表的缺点，可以双向访问。

双链表定义。

typedef struct DNode {    // 定义双链表结点类型
    int data;    // 数据域
    struct DNode* prior, * next;    // 前驱和后继指针
} DNode, * DLinkList;

初始化双链表

bool InitDLinkList(DLinkList L)
{
    L = (DNode*)malloc(sizeof(DNode));    // 分配一个头结点
    if (L == NULL) return false;    // 内存不足，分配失败
    L->prior = NULL;    // 头结点的prior永远指向NULL
    L->next = NULL;        // 头结点之后暂时还没有结点
    return true;
}

判断双链表是否为空（带头结点）

// 判断双链表是否为空（带头结点）
bool Empty(DLinkList L)
{
    return (L->next == NULL);
}

双链表的插入操作（后插操作）

// 在p结点之后插入s结点（后插操作）
bool InsertNextDNode(DNode* p, DNode* s)
{
    if (p == NULL || s == NULL) return false;    // 非法参数
    s->next = p->next;        // 将结点*s插入到结点*p之后
    if (p->next != NULL)    // 如果p有后续结点
    {
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

注意：

修改指针要注意顺序合法。
如果p是最后一个结点，则p->next指向NULL，会出现空指针异常，因此需要先判断p->next是否为空。
按位序插入、前插操作，都可以转换为后插操作去实现。

按位序插入思路：从头结点开始遍历，找到某个位序的前驱结点，对这个结点进行后插操作。

前插操作思路：找到给定结点的前驱结点，在对该结点的前驱结点进行后插操作。

双链表的删除操作

// 删除p结点的后继结点
bool DeleteNextNode(DNode* p)
{
    if (p == NULL) return false;
    DNode* q = p->next;    // 找到p的后继结点q
    if (q == NULL) return false;    // p没有后继
    p->next = q->next;
    if (q->next != NULL)    // q结点不是最后一个结点
    {
        q->next->prior = p;
    }
    free(q);    // 释放结点空间
    return true;
}

注意：如果p是最后一个结点，也需要先判断p->next是否为空。

销毁一个双链表

// 销毁一个双链表
void DestoryList(DLinkList L)
{
    // 循环释放各个数据结点
    while (L->next != NULL)
    {
        DeleteNextNode(L);
    }
    free(L);    // 释放头结点
    L = NULL;    // 头指针指向NULL
}

双链表的遍历

// 向右遍历
while (p != NULL)
{
    // 对结点p做相应处理，如打印，按位查找（i++），按值查找（p->data == e）
    p = p->next;
}

// 向前遍历
while (p != NULL)
{
    // ...
    p = p->prior;
}

// 向前遍历（跳过头结点）
while (p->prior != NULL)
{
    // ...
    p = p->prior;
}

注意：双链表不可随机存取。按位查找、按值查找都只能用遍历的方式实现。时间复杂度为O(n)。

循环链表

循环单链表

初始化一个循环单链表。

// 初始化一个循环单链表
bool InitList(LinkList L)
{
    L = (LNode*)malloc(sizeof(LNode));    // 分配一个头结点
    if (L == NULL) return false;    // 内存不足
    L->next = L;    // 头结点next指向头结点
    return true;
}

判断循环单链表是否为空。

// 判断循环单链表是否为空
bool Empty(LinkList L)
{
    return (L->next == L);
}

判断节点p是否为循环单链表的表尾结点。

// 判断结点p是否为循环单链表的表尾结点
bool IsTail(LinkList L, LNode* p)
{
    return(p->next == NULL);
}

循环双链表

初始化空的循环双链表。

// 初始化空的循环双链表
bool InitDLink(DLinkList L)
{
    L = (DNode*)malloc(sizeof(DNode));    // 分配一个头结点
    if (L == NULL) return false;    // 内存不足，分配失败
    L->prior = L;    // 头结点的prior指向头结点
    L->next = L;    // 头结点的next指向头结点
    return true;
}

判断循环双链表是否为空。

// 判断循环双链表是否为空
bool Empty(DLinkList L)
{
    return (L->next == L);
}

判断结点p是否为循环双链表的表尾结点。

// 判断结点p是否为循环双链表的表尾结点
bool IsTail(DLinkList L, DNode* p)
{
    return (p->next == L);
}

循环双链表的处插入：实现代码和双链表的后插操作一样。但是不需要判断p->next是否为空。

循环双链表的删除：代码和双链表的删除一样。同样也不需要判断p->next是否为空。

静态链表

静态链表是用数组方式实现的链表。

优点：增、删操作不需要大量移动元素。

缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不变。

用代码定义一个静态链表。

#define MaxSize 10    // 静态链表的最大长度
typedef struct {    // 静态链表数据类型定义
    int data;        // 存储数据袁术
    int next;        // 下一个元素的数组下标
} SLinkList[MaxSize];