• 数据结构基础内容-----第三章 线性表

    文章目录

    线性表

    线性表的定义

    线性表是由n（n≥0）个数据元素组成的有限序列，其中每个数据元素都与它前面和后面的元素存在一个确定的关系，称为线性关系。线性表中第一个数据元素没有前驱，最后一个数据元素没有后继，其他每个数据元素有且只有一个前驱和一个后继。线性表可以用数组或链表来实现。常见的线性表包括数组、链表、栈、队列等。

    抽象数据类型

    线性表的抽象数据类型描述如下：

    数据对象：D={a1, a2, …, an}，其中ai是数据元素，i为元素序号。

    数据关系：R={, , …, }，即元素之间的线性关系，其中表示a1是a2的前驱，表示a2是a3的前驱，以此类推。

    基本操作：

    • InitList(&L): 初始化操作，建立一个空的线性表L。
    • ListLength(L): 求表长操作，返回线性表L中元素个数。
    • GetElem(L, i, &e): 取值操作，用e返回线性表L中第i个元素的值。
    • LocateElem(L, e): 查找操作，返回线性表L中第一个与e相等的元素的位序。
    • ListInsert(&L, i, e): 插入操作，插入新元素e到线性表L中第i个位置。
    • ListDelete(&L, i, &e): 删除操作，删除线性表L中第i个位置的元素，并用e返回其值。
    • PrintList(L): 输出操作，依次输出线性表L中的每个元素。

    线性表的顺序存储结构

    顺序表
    是一种线性表，可以用数组来实现。具体地，顺序表的存储方式就是将元素放在一块连续的内存空间中，并且按照线性关系依次排列。

    假设顺序表的长度为n，我们可以用一个一维数组data来存储这个顺序表。则顺序表中第i个元素的下标为i-1，即data[i-1]表示顺序表中第i个元素的值。

    顺序表的优点是支持随机访问，因为数组支持O(1)时间复杂度的随机访问操作。但是，它的插入和删除操作比较费时，因为需要对数组进行移动操作，时间复杂度为O(n)。此外，顺序表的空间利用率不高，因为需要预留一定大小的内存空间以供未来使用。

    整体实现

    #include 
#include 

#define MAXSIZE 100     // 定义线性表最大长度为100

typedef struct {
    int data[MAXSIZE];  // 存储数据元素的数组
    int length;         // 当前线性表的长度
} SqList;

// 初始化一个空线性表
void InitList(SqList *L) {
    L->length = 0;
}

// 返回当前线性表的长度
int ListLength(SqList L) {
    return L.length;
}

// 获取线性表中第i个元素的值
int GetElem(SqList L, int i) {
    if (i < 1 || i > L.length) {
        printf("Error: index out of range\n");
        exit(1);
    }
    return L.data[i-1];
}

// 在线性表的第i个位置插入一个元素e
void ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) {
        printf("Error: index out of range\n");
        exit(1);
    }
    if (L->length >= MAXSIZE) {
        printf("Error: list is full\n");
        exit(1);
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
}

// 从线性表中删除第i个元素，并返回该元素的值
int ListDelete(SqList *L, int i) {
    if (i < 1 || i > L->length) {
        printf("Error: index out of range\n");
        exit(1);
    }
    int e = L->data[i-1];
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return e;
}

// 输出线性表中的所有元素
void PrintList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

int main() {
    SqList L;
    InitList(&L);        // 初始化一个空线性表

    ListInsert(&L, 1, 100);      // 在第1个位置插入元素100
    ListInsert(&L, 2, 200);      // 在第2个位置插入元素200
    ListInsert(&L, 3, 300);      // 在第3个位置插入元素300
    PrintList(L);       // 输出当前线性表的所有元素

    int e = GetElem(L, 2);        // 获取第2个元素的值，并打印结果
    printf("The value of the second element is %d\n", e);

    int deleted = ListDelete(&L, 2);   // 删除第2个元素，并获取其值
    printf("Deleted element is %d\n", deleted);
    PrintList(L);       // 输出当前线性表的所有元素

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    顺序表的时间复杂度

    顺序表是一种基于数组实现的线性数据结构，它可以用于存储和操作具有相同数据类型的元素集合。对于顺序表的常见操作，其时间复杂度如下：

    • 随机访问元素：O(1)
    • 在表尾插入元素：O(1)（平均情况下）
    • 在表头插入元素：O(n)
    • 在表中间插入元素：O(n)
    • 删除元素：O(n)
      其中，随机访问元素的时间复杂度为 O(1)，是顺序表的优势之一。而在表头或表中间插入或删除元素时，需要将后续元素向后或向前移动，因此时间复杂度为 O(n)。在表尾插入元素时，只需在数组末尾添加元素，因此时间复杂度为 O(1)。总体来说，顺序表在随机访问和表尾插入元素方面具有较好的性能，但在表头或表中间插入或删除元素时效率较低。
    顺序表的优缺点

    优点

    1. 随机访问元素方便。由于顺序表中的元素存储在数组中，因此可以根据下标直接访问任何一个元素，时间复杂度为O(1)。
    2. 存储密度高。顺序表的元素都存储在一个连续的内存块中，节省了指针等额外空间开销，并且对计算机缓存友好。
    3. 插入和删除操作简单。在表尾插入元素时，只需要在数组末尾添加元素即可，时间复杂度为O(1)；在删除元素时，只需要将元素删除并将后面的元素向前移动即可，时间复杂度为O(n)。

    缺点：

    1. 表头或表中间插入和删除元素效率低。由于在插入和删除元素时需要将后面的元素向前或向后移动，时间复杂度为O(n)。
    2. 容量固定。顺序表的容量是预先设定好的，如果要添加更多的元素，必须重新分配更大的内存空间，并把原有的元素拷贝到新的内存空间中，这样会造成一定的时间复杂度和空间浪费。
    3. 内存空间不够灵活。当顺序表中存储的元素数量很少时，如果容量过大，会造成空间浪费，而如果容量过小，则无法存储足够多的元素。

    SqList *是指向SqList类型的指针，而不是SqList类型本身。在函数中，我们通常使用指针作为参数，以便可以直接修改传递的变量的值。如果我们使用SqList本身作为参数，则只能对副本进行操作，无法修改原始变量的值。

    因此，当我们需要在函数中修改一个线性表的内容时，需要使用指向该线性表的指针作为参数，并使用指针操作来修改其内容。在函数声明中，我们将指向SqList类型的指针声明为SqList *。

    数据长度与线性表长度的区别？

    数据长度指的是某个数据对象所占用的存储空间大小，可以通过计算该对象在内存中所占用的字节数来确定。而线性表长度则是指线性表中元素的个数，即该线性表中包含多少个数据元素。

    举例来说，如果我们有一个包含了10个整数的数组，那么它的数据长度就为40个字节（假设每个整数占用4个字节），而它的线性表长度为10个元素。

    因此，数据长度和线性表长度虽然都与数据结构有关，但是其概念是不同的，需要注意区分。

    线性表的地址计算方法通常有两种，分别为下标法和指针法。

    下标法：在使用下标法时，我们需要先定义一个基地址，然后通过元素在线性表中的下标来计算其对应的物理地址。假设线性表的基地址为addr，元素下标为i（其中0 ≤ i < n），每个元素占用的字节数为elemSize，则第i个元素的地址为：

    addr + i * elemSize

    • 1

    指针法：在使用指针法时，我们则直接使用指向线性表元素的指针进行地址计算。假设线性表的头指针为p，第i个元素的指针为p_i，则第i个元素的地址为：

    p_i = p + i

    • 1

    这里的加法操作是指将指针p向后移动i个元素所占用的空间大小。需要注意的是，在使用指针法时，我们需要确保每个元素的大小是已知的，以便于正确地计算其地址。

    线性表的链式存储结构

    线性表的链式存储结构是指使用一组任意的存储单元来存储线性表中的元素，每个存储单元中除了数据元素本身之外还包含一个指针域，用于指向下一个存储单元的地址。将这些存储单元按照某种特定的顺序连接起来，就形成了一个链式结构，也称为链表。

    链表中的每个存储单元通常被称为节点（Node），其中包括数据域和指针域两部分。数据域保存着该节点所存储的元素值，而指针域则保存着指向下一个节点的地址。

    由于链表中的节点可以动态地分配和释放，因此链式存储结构具有很好的灵活性和扩展性，在实际应用中非常常见。同时，链表的插入和删除操作也比较便捷，只需要修改相应节点的指针域即可，无需移动大量元素，因此在某些场景下性能更优。

    链表通常可以分为单链表、双向链表和循环链表等不同类型，每种类型的链表都有其特殊的应用场景和适用条件。

    线性表的链式存储和线性存储的区别主要在于数据元素在内存中的存储方式不同。

    • 线性存储结构是指将数据元素顺序地存放在一段连续的内存空间中，通常使用数组来实现。每个元素在内存中所占用的位置是固定的，可以通过下标直接访问。由于内存空间是连续的，因此随机访问某个元素时效率比较高，但插入和删除操作需要移动其他部分的元素，效率较低。

    • 链式存储结构则是使用一组任意的存储单元来存储线性表中的元素，每个存储单元中除了数据元素本身之外还包含一个指针域，用于指向下一个存储单元的地址。将这些存储单元按照某种特定的顺序连接起来，就形成了一个链式结构，也称为链表。由于链表中的节点可以动态地分配和释放，因此链式存储结构具有很好的灵活性和扩展性，在实际应用中非常常见。同时，链表的插入和删除操作也比较便捷，只需要修改相应节点的指针域即可，无需移动大量元素，因此在某些场景下性能更优。

    总的来说，线性存储适合于元素个数比较固定，需要频繁随机访问元素的场景，而链式存储则适合于元素个数不确定，需要频繁进行插入和删除操作的场景。

    头指针和头节点都是链表中的概念，但它们的含义不同。

    头指针： 头指针是指向链表中第一个节点的指针，通常作为链表的入口，用于访问整个链表。头指针本身并不存储任何数据元素，只是作为链表结构的一部分，用于标识链表的起始位置。

    头节点： 头节点是在链表的第一个节点之前附加的一个额外节点，通常不存储任何实际的数据元素，只包含一个指针域，用于指向链表中的第一个节点。头节点的存在主要是为了方便操作，在某些情况下可以简化链表插入、删除等操作的实现。

    因此，头指针和头节点的区别在于，头指针是指向链表中第一个实际节点的指针，而头节点则是在第一个实际节点之前附加的一个额外节点。两者都是为了方便对链表进行操作而引入的概念，但它们的具体使用方式和目的略有不同。

    带头节点和不带头节点的链表都是指单链表或双向链表中是否存在头节点的情况。

    1. 不带头的链表：不带头的链表是指链表的第一个节点就是存储数据元素的节点。在这种链表中，第一个节点既存储数据元素，又保存下一个节点的地址，相当于将头节点和第一个数据节点合二为一。这种链表通常比较简洁，但需要特别注意边界条件的处理。

    2. 带头的链表：带头的链表是指链表中附加了一个额外的头节点，用于标识链表的起始位置。头节点不存储任何实际的数据元素，只包含一个指针域，用于指向链表中的第一个实际节点。在带头的链表中，第一个节点才是存储数据元素的节点。这种链表通常比较常用，因为头节点可以简化链表插入、删除等操作的实现。

    总的来说，带头和不带头的链表都有各自的优缺点，具体使用哪种方式主要取决于具体的应用场景和实现需求

    typedef struct LNode
{
	int data;//节点的数据域
	struct LNode *next;//节点的指针域
}LNode,*LinkList;

    • 1
    • 2
    • 3
    • 4
    • 5

    带头节点
    1
    2
    3
    head 
    //带头节点的链表
#include 
#include 

/* 定义链表节点结构体 */
struct node {
    int data;           // 节点保存的数据
    struct node *next;  // 指向下一个节点的指针
};

int main() {
    struct node *head, *p, *q;
    int i, n, num;

    /* 创建头节点 */
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;

    printf("请输入节点个数：");
    scanf("%d", &n);

    p = head;
    for (i = 0; i < n; i++) {
        q = (struct node *)malloc(sizeof(struct node));
        printf("请输入第%d个节点的值：", i + 1);
        scanf("%d", &num);
        q->data = num;
        q->next = NULL;
        p->next = q;
        p = q;
    }

    /* 遍历输出链表 */
    p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    /* 释放链表内存 */
    p = head;
    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    不带头节点
    1
    2
    3 
    
    
//不带头节点
#include 
#include 

/* 定义链表节点结构体 */
struct node {
    int data;           // 节点保存的数据
    struct node *next;  // 指向下一个节点的指针
};

int main() {
    struct node *head, *p, *q;
    int i, n, num;

    /* 创建第一个节点 */
    printf("请输入节点个数：");
    scanf("%d", &n);

    printf("请输入第1个节点的值：");
    scanf("%d", &num);

    head = (struct node *)malloc(sizeof(struct node));
    head->data = num;
    head->next = NULL;
    p = head;

    for (i = 1; i < n; i++) {
        q = (struct node *)malloc(sizeof(struct node));
        printf("请输入第%d个节点的值：", i + 1);
        scanf("%d", &num);
        q->data = num;
        q->next = NULL;
        p->next = q;
        p = q;
    }

    /* 遍历输出链表 */
    p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    /* 释放链表内存 */
    p = head;
    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    带头和不带头的链表都是指单链表或双向链表中是否存在头节点的情况。

    1. 不带头的链表：不带头的链表是指链表的第一个节点就是存储数据元素的节点。在这种链表中，第一个节点既存储数据元素，又保存下一个节点的地址，相当于将头节点和第一个数据节点合二为一。这种链表通常比较简洁，但需要特别注意边界条件的处理。

    2. 带头的链表：带头的链表是指链表中附加了一个额外的头节点，用于标识链表的起始位置。头节点不存储任何实际的数据元素，只包含一个指针域，用于指向链表中的第一个实际节点。在带头的链表中，第一个节点才是存储数据元素的节点。这种链表通常比较常用，因为头节点可以简化链表插入、删除等操作的实现。

    总的来说，带头和不带头的链表都有各自的优缺点，具体使用哪种方式主要取决于具体的应用场景和实现需求

    
//单链表的读取
typedef struct LNode
{
	int data;//节点的数据域
	struct LNode *next;//节点的指针域
}LNode,*LinkList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    单链表的读取

    //单链表的读取
#include 
#include 

typedef struct LNode {
    int data;           // 节点值
    struct LNode* next; // 下一节点指针
}LNode, *LinkList;

// 创建链表
void create_list(LinkList* L, int n) {
    (*L) = (LinkList)malloc(sizeof(LNode)); // 创建头结点
    (*L)->next = NULL;
    LinkList p = (*L);
    for (int i = 0; i < n; i++) {
        LinkList new_node = (LinkList)malloc(sizeof(LNode)); // 创建新节点
        new_node->data = rand() % 100; // 随机节点值
        new_node->next = NULL;
        p->next = new_node; // 将新节点接在当前节点后面
        p = new_node; // 指向新节点
    }
}

// 输出链表
void print_list(LinkList L) {
    printf("链表中的元素为：\n");
    LinkList p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 获取第i个节点的值
int get_elem(LinkList L, int i) {
    LinkList p = L->next;
    int j = 1; // 记录当前遍历到的节点位置
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    if (p == NULL || j > i) {
        printf("获取节点失败：位置已越界\n");
        return -1;
    }
    return p->data;
}

int main() {
    LinkList L;
    create_list(&L, 10);
    print_list(L);

    int elem = get_elem(L, 5);
    printf("第5个节点的值为：%d\n", elem);

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    单链表的删除和插入

    #include 
#include 

typedef struct LNode {
    int data;           // 节点值
    struct LNode* next; // 下一节点指针
}LNode, *LinkList;

// 创建链表
void create_list(LinkList* L, int n) {
    (*L) = (LinkList)malloc(sizeof(LNode)); // 创建头结点
    (*L)->next = NULL;
    LinkList p = (*L);
    for (int i = 0; i < n; i++) {
        LinkList new_node = (LinkList)malloc(sizeof(LNode)); // 创建新节点
        new_node->data = rand() % 100; // 随机节点值
        new_node->next = NULL;
        p->next = new_node; // 将新节点接在当前节点后面
        p = new_node; // 指向新节点
    }
}

// 输出链表
void print_list(LinkList L) {
    printf("链表中的元素为：\n");
    LinkList p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 获取第i个节点的值
int get_elem(LinkList L, int i) {
    LinkList p = L->next;
    int j = 1; // 记录当前遍历到的节点位置
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    if (p == NULL || j > i) {
        printf("获取节点失败：位置已越界\n");
        return -1;
    }
    return p->data;
}

// 在第i个节点前插入节点，节点值为elem
void insert_node(LinkList L, int i, int elem) {
    LinkList p = L;
    int j = 0; // 记录当前遍历到的节点位置
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL || j > i - 1) {
        printf("插入节点失败：位置已越界\n");
        return;
    }
    LinkList new_node = (LinkList)malloc(sizeof(LNode));
    new_node->data = elem;
    new_node->next = p->next;
    p->next = new_node;
}

// 删除第i个节点
void delete_node(LinkList L, int i) {
    LinkList p = L;
    int j = 0; // 记录当前遍历到的节点位置
    while (p->next != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p->next == NULL || j > i - 1) {
        printf("删除节点失败：位置已越界\n");
        return;
    }
    LinkList q = p->next;
    p->next = q->next;
    free(q);
}

int main() {
    LinkList L;
    create_list(&L, 10);
    print_list(L);

    insert_node(L, 3, 100); // 在第3个节点前插入节点
    print_list(L);

    delete_node(L, 5); // 删除第5个节点
    print_list(L);

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97

    单链表的删除

    //单链表的整链表删除
void destroy_list(LinkList* L) {
    LinkList p = (*L)->next;
    while (p != NULL) {
        LinkList q = p;
        p = p->next;
        free(q);
    }
    (*L)->next = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    单链表和顺序链表都是常用的数据结构，它们各自具有一些优点和缺点。

    单链表的优点包括：

    1. 空间利用率高：每个节点只需存储一个指针和一个数据元素，相对于顺序链表来说，不需要预留大块空间，因此可以灵活使用内存空间。

    2. 插入、删除操作方便：由于单链表中每个节点只保存了下一个节点的地址信息，在插入或删除某个节点时，只需修改前一个节点指向后一个节点的指针即可，时间复杂度为O(1)。

    3. 长度不受限制：因为单链表的节点可以动态地分配内存，所以其长度不受任何限制。

    单链表的缺点包括：

    1. 不能随机访问：在单链表中，如果要查找第k个节点，必须从头节点开始往后遍历k-1次，时间复杂度为O(n)，效率较低。

    2. 存取速度慢：由于单链表中的节点在内存中并不是连续存放的，访问一个节点需要先访问前面的所有节点，这样就会产生大量的缓存未命中，导致存取速度慢。

    顺序链表的优点包括：

    1. 可以快速访问：由于顺序链表中的节点在内存中是连续存放的，因此可以快速访问任何一个节点，时间复杂度为O(1)。

    2. 存取速度较快：由于顺序链表中的节点在内存中是连续存放的，所以会产生大量的缓存命中，可以提高存取速度。

    顺序链表的缺点包括：

    1. 空间利用率低：由于顺序链表要预留一定的空间，因此空间利用率比单链表低。

    2. 插入、删除操作不方便：由于顺序链表中每个节点在内存中是连续存放的，插入或删除某个节点时需要移动后面的所有节点，时间复杂度为O(n)。

    静态链表

    静态链表是在数组中模拟链表结构的一种方法。它由两个数组组成：一个存储数据元素，另一个存储指针信息。具体来说，每个数据元素都包括两个部分：数据域和指针域。其中，数据域存储该节点的数据，而指针域则存储下一个节点的位置（通常是下一个节点在数组中的下标）。

    因此，静态链表的结构类似于这样：

    +----------+----------+
|  数据元素  |  指针元素  |
+----------+----------+
|  数据域  |  指针域  |
+----------+----------+
|  数据域  |  指针域  |
+----------+----------+
|  数据域  |  指针域  |
+----------+----------+

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    其中，第一个节点的位置通常被称为“头节点”，它的指针域指向链表的第一个实际数据节点。而最后一个节点的指针域则指向一个特殊的值（通常是-1），表示该节点为链表的末尾。

    静态链表的优点是可以避免动态分配内存带来的时间和空间开销，并且可以利用数组的连续性提高缓存命中率和访问效率。但是其缺点也很明显，即需要事先确定链表的长度，不能像动态链表那样随时插入或删除节点，且可能会浪费一定的内存空间。

    在实际应用中，静态链表常用于文件系统、数据库、编译器等需要频繁增删文件、记录、符号表等数据结构的场合。

    #include 
#define MAXSIZE 100

typedef struct {
    int data;
    int next;
} Node;

Node list[MAXSIZE];
int head = -1; // 头结点位置

void init() {
    for (int i = 0; i < MAXSIZE - 1; i++) {
        list[i].next = i + 1;
    }
    list[MAXSIZE - 1].next = -1;
}

int get_node() {
    int p = list[0].next;
    if (p == -1) {
        return -1;
    }
    list[0].next = list[p].next;
    return p;
}

void free_node(int k) {
    list[k].next = list[0].next;
    list[0].next = k;
}

void insert(int x) {
    int p = head;
    int q = get_node();
    if (q == -1) {
        printf("Static List Full!\n");
        return;
    }
    list[q].data = x;
    if (p == -1 || x < list[p].data) {
        list[q].next = p;
        head = q;
        return;
    }
    while (list[p].next != -1 && list[list[p].next].data < x) {
        p = list[p].next;
    }
    list[q].next = list[p].next;
    list[p].next = q;
}

void delete(int x) {
    int p = head;
    while (p != -1 && list[list[p].next].data != x) {
        p = list[p].next;
    }
    if (p == -1) {
        printf("Data Not Exist!\n");
        return;
    }
    int q = list[p].next;
    list[p].next = list[q].next;
    free_node(q);
}

void display() {
    if (head == -1) {
        printf("Static List Empty!\n");
        return;
    }
    int p = head;
    while (p != -1) {
        printf("%d ", list[p].data);
        p = list[p].next;
    }
    printf("\n");
}

int main() {
    init();
    insert(3);
    insert(1);
    insert(2);
    display();
    delete(2);
    display();
    return 0;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    循环链表

    循环链表是一种链表数据结构，它与普通链表的区别在于，最后一个节点的指针指向第一个节点而不是 NULL。这样就形成了一个环形结构，也就是说，可以从任何一个节点开始遍历整个链表。

    
//C语言的实现
#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct CircularLinkedList {
    Node* head;
} CircularLinkedList;

void append(CircularLinkedList* list, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    if (list->head == NULL) {
        list->head = new_node;
        new_node->next = list->head;
    } else {
        Node* current = list->head;
        while (current->next != list->head) {
            current = current->next;
        }
        current->next = new_node;
        new_node->next = list->head;
    }
}

void print_list(CircularLinkedList* list) {
    if (list->head == NULL) {
        printf("List is empty\n");
    } else {
        Node* current = list->head;
        do {
            printf("%d ", current->data);
            current = current->next;
        } while (current != list->head);
        printf("\n");
    }
}

int main() {
    CircularLinkedList list = {NULL};
    append(&list, 1);
    append(&list, 2);
    append(&list, 3);
    print_list(&list);
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    双向链表

    **双向链表（Doubly Linked List）**是一种链表数据结构，每个节点都包含了指向其前驱和后继的两个指针。与单向链表相比，双向链表可以使得在链表中的任意一个节点都能够方便地进行删除、插入操作，更加灵活。

    由于每个节点都有指向前驱和后继节点的指针，因此双向链表的节点通常占用更多的内存空间。但是，双向链表具有许多优点，例如允许从头部或尾部快速遍历、可逆遍历、以及删除结点时不需要遍历整个链表等。

    #include 
#include 

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct DoublyLinkedList {
    Node* head;
} DoublyLinkedList;

void append(DoublyLinkedList* list, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    if (list->head == NULL) {
        new_node->prev = NULL;
        list->head = new_node;
    } else {
        Node* current = list->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
        new_node->prev = current;
    }
}

void insert_before(DoublyLinkedList* list, int key, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    if (list->head == NULL) {
        new_node->prev = NULL;
        new_node->next = NULL;
        list->head = new_node;
    } else if (list->head->data == key) {
        new_node->prev = NULL;
        new_node->next = list->head;
        list->head->prev = new_node;
        list->head = new_node;
    } else {
        Node* current = list->head;
        while (current != NULL && current->data != key) {
            current = current->next;
        }
        if (current == NULL) {
            printf("Key not found\n");
        } else {
            new_node->prev = current->prev;
            new_node->next = current;
            current->prev->next = new_node;
            current->prev = new_node;
        }
    }
}

void delete(DoublyLinkedList* list, int key) {
    if (list->head == NULL) {
        printf("List is empty\n");
    } else if (list->head->data == key) {
        Node* temp = list->head;
        list->head = list->head->next;
        if (list->head != NULL) {
            list->head->prev = NULL;
        }
        free(temp);
    } else {
        Node* current = list->head;
        while (current != NULL && current->data != key) {
            current = current->next;
        }
        if (current == NULL) {
            printf("Key not found\n");
        } else {
            current->prev->next = current->next;
            if (current->next != NULL) {
                current->next->prev = current->prev;
            }
            free(current);
        }
    }
}

void print_list(DoublyLinkedList* list) {
    if (list->head == NULL) {
        printf("List is empty\n");
    } else {
        Node* current = list->head;
        while (current != NULL) {
            printf("%d ", current->data);
            current = current->next;
        }
        printf("\n");
    }
}

int main() {
    DoublyLinkedList list = {NULL};
    append(&list, 1);
    append(&list, 2);
    append(&list, 3);
    insert_before(&list, 2, 4);
    delete(&list, 2);
    print_list(&list);
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
  • 相关阅读:
    从零开始配置vim(24)——自动补全
    SpringBoot 学习（九）Redis
    linux rsyslog综合实战1
    QT：反射机制
    DES算法是对称算法吗，能否通过在线工具进行DES解密？
    __wakeup绕过版本_PHP__wakeup()方法
    PPOCRLabel 半标注工具全平台安装使用
    推荐系统常用知识点
    我的创作纪念日
    iOS OC项目中引入SwiftUI文件
  • 原文地址：https://blog.csdn.net/weixin_45626953/article/details/130907192