线性表

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

  • 线性表是最基础的数据结构，它是一种线性结构，即数据元素之间是一对一的关系，线性表一般需要包含以下功
    • 初始化线性表： 将一个线性表进行初始化，得到一个全新的线性表。
    • 获取指定位置上的元素： 直接获取线性表指定位置i上的元素。
    • 检查线性表是否为空表： 检查线性表是否为空表。
    • 获取元素的位置： 获取某个元素在线性表上的位置i。
    • 插入元素： 在指定位置i上插入一个元素。
    • 删除元素： 删除指定位置i上的一个元素。
    • 获取长度： 返回线性表的长度。

顺序表

顺序表是利用数组实现的，采用顺序存储结构的线性表

初始化顺序表

1.首先定义一个结构体类型，将可能用到的数据保存在一起,以int类型为例

1
2
3
4
5
6
7
typedef int E;  //这里为int类型起别名，这样可以方便随时切换元素的类型

struct List {
    E array[10];   //实现顺序表的底层数组
    int capacity;   //表示底层数组的容量（可存储长度）
    int size;   //表示当前线性表中的元素个数（已存储长度）
};

2.为了使用方便将List结构体的指针取别名
1
2
//这里起什么别名都可以，这里起的别名是ArrayList
typedef struct List* ArrayList;

3.逐个完善线性表的功能，先完成线性表初始化操作
1
2
3
4
5
//因为初始化操作是一定要改变最初线性表的容量的，所以这里传入的参数是线性表指针，结构指针已经在前面重命名过了
void initList(ArrayList list){
    list->capacity = 10;    //直接将数组的容量设定为10即可
    list->size = 0;         //初始时，表中没有元素，所以元素数量为0
}

4.在刚才的初始化函数中，我们简单的将数组容量设为10，但线性表容量的设置应该根据实际情况来定，这里我们使用动态扩容，直接用一个指针来指向底层数组的内存区域，当装不下时，创建一个更大的内存空间来存放数据，以此来实现动态扩容。同时创建更大的内存空间也有失败的可能，所以此处应当返回一个结果告诉调用者是否扩容成功，修改前面的代码：

1
2
3
4
5
struct List {
    E * array;   //指向顺序表的底层数组
    int capacity;   //数组的容量
    int size;   //表中的元素数量
};
1
2
3
4
5
6
7
8
_Bool initList(ArrayList list){
    //初始生成容量为10的空间
    list->array = malloc(sizeof(E) * 10);
    if(list->array == NULL) return 0;  //需要判断如果申请的结果为NULL的话表示内存空间申请失败
    list->capacity = 10;
    list->size = 0;
    return 1;   //正常情况下返回true也就是1
}

实现插入操作

  • 先设计好函数的参数和返回值
1
2
3
4
5
//list就是待操作的表
//element就是需要插入的元素
//index就是插入的位置（注意顺序表的index是按位序计算的，从1开始，一般都是第index个元素）
void insertList(ArrayList list, E element, int index){
}
  • 按照先前的思路编写代码
    • 先不断循环找到要插入的位置
    • 找到后，将要插入位置以后的元素全部向后移动一位
    • 移动后空出一位，将新元素插入
    • 成功插入后，更新长度
1
2
3
4
5
6
7
8
9
void insertList(ArrayList list, E element, int index){
    //size指示当前元素的最后一位，不断向前遍历，直到index位置
    for (int i = list->size; i > index - 1; i--){ 
        //将Index位置后的元素全部向后挪一位
        list->array[i] = list->array[i - 1];
    }
    list->array[index - 1] = element;    //挪完之后，位置就腾出来了，直接设定即可
    list->size++;   //插入之后相当于多了一个元素，记得size + 1
}

判断数据合法性

  • 此时正常插入便能成功进行，但如果我们在非法位置插入元素依旧会有问题,比如这个位置小于0或者大于现在的元素数量，故我们应当检查插入位置是否合法
  • 转换成位序，也就是[1, size + 1]这个闭区间，所以我们在一开始的时候进行判断：
1
2
3
4
5
6
7
8
9
_Bool insertList(ArrayList list, E element, int index){
    //如果在非法位置插入，返回0表示插入操作执行失败
    if(index < 1 || index > list->size + 1) return 0;   
    for (int i = list->size; i > index - 1; i--)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;   //正常情况返回1
}

扩容线性表

  • 刚才只是说明了扩容的方法，现在我们来实现一下，判断size是否等于capacity，如果等于，则需要扩容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
_Bool insertList(ArrayList list, E element, int index){
    if(index < 1 || index > list->size + 1) return 0;
    //如果当前元素数量等于容量，则需要扩容
    if(list->size == list->capacity) { 
        //这里用一个位运算，表示新容量是原先容量的1.5倍
        int newCapacity = list->capacity + (list->capacity >> 1);  
        //这里使用新的函数realloc重新申请更大的内存空间 
        E * newArray = realloc(list->array, sizeof(E) * newCapacity);  
        if(newArray == NULL) return 0;   //如果申请失败，那么就确实没办法插入了，只能返回0表示插入失败了
        list->array = newArray;
        list->capacity = newCapacity;
    }

    //扩容成功后，线性表就能和之前一样插入元素了
    for (int i = list->size; i > index - 1; i--)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;
}
relloc函数

函数原型：void* relloc(void* memblock, size_t size)

  • relloc函数返回的是void*类型的指针，指向新开辟的内存块的起始地址。
  • memblock是需要扩容的内存块指针，如果原本的内存块之后又足够的空间可以追加，则直接追加，否则会开辟新的空间并返回
  • size是新的内存块大小，注意是新的，而不是新增加的。
  • 如果memblock是NULL，那么就相当于malloc函数，申请一个新的内存块。
  • 如果size是0，那么就相当于free函数，释放掉memblock指向的内存块。

删除元素

删除操作与插入操作类似，当删除元素时，需要对元素进行批量移动，但是不需要考虑扩容问题了。

  • 先设计函数的返回值和参数
1
2
3
//list就是待操作的表，index是要删除的元素位序
void deleteList(ArrayList list, int index){
}
  • 删除和插入一样，需要考虑位置的合法性
  • 换算成位序就是[1, size]这个闭区间内容
1
2
3
4
5
6
7
8
9
10
11
_Bool deleteList(ArrayList list, int index){
    //保证位置合法
    if(index < 1 || index > list->size) return 0;

    //执行删除操作
    for (int i = index - 1; i < list->size - 1; ++i)
    //实际上只需要依次把后面的元素覆盖到前一个即可
        list->array[i] = list->array[i + 1];   
    list->size--;   //最后别忘了size - 1
    return 1;
}

获取长度

获取顺序表长度的操作非常简单，只需要返回当前Size即可

1
2
3
int sizeList(ArrayList list){
    return list->size;   //直接返回size就完事
}

查找元素

查找元素在线性表中，需要遍历线性表，当出现目标元素时，返回该元素的索引，否则返回-1

1
2
3
4
5
6
int findList(ArrayList list, E element){
    for (int i = 0; i < list->size; ++i) {   //一直遍历，如果找到那就返回位序
        if(list->array[i] == element) return i + 1;
    }
    return -1;  //如果遍历完了都没找到，那么就返回-1
}

按位置获取元素，这是线性表的一个基本操作，直接返回索引值即可
1
2
3
4
5
6
E * getList(ArrayList list, int index){
    //判断位置是否在线性表中
    if(index < 1 || index > list->size) 
        return NULL;   //如果超出范围就返回NULL
    return &list->array[index - 1];
}

顺序表完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化顺序表
_Bool initList(ArrayList list);
// 插入元素
_Bool insertList(ArrayList list, E element, int index)
// 删除元素
_Bool deleteList(ArrayList list, int index)
// 获取顺序表长度
int sizeList(ArrayList list)
// 获取指定位置的元素
E * getList(ArrayList list, int index)
// 查找元素下标
int findList(ArrayList list, E element)
// 打印当前线性表
void printList(ArrayList list)
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
110
111
#include <stdio.h>
#include <stdlib.h>

typedef int E;

struct List {
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

_Bool initList(ArrayList list){
    list->array = malloc(sizeof(E) * 10);
    if(list->array == NULL) return 0;
    list->capacity = 10;
    list->size = 0;
    return 1;
}

_Bool insertList(ArrayList list, E element, int index){
    if(index < 1 || index > list->size + 1) return 0;

    if(list->size == list->capacity) {
        int newCapacity = list->capacity + (list->capacity >> 1);
        E * newArray = realloc(list->array, newCapacity * sizeof(E));
        if(newArray == NULL) return 0;
        list->array = newArray;
        list->capacity = newCapacity;
    }

    for (int i = list->size; i > index - 1; --i)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;
}

_Bool deleteList(ArrayList list, int index){
    if(index < 1 || index > list->size) return 0;
    for (int i = index - 1; i < list->size - 1; ++i)
        list->array[i] = list->array[i + 1];
    list->size--;
    return 1;
}

int sizeList(ArrayList list){
    return list->size;
}

E * getList(ArrayList list, int index){
    if(index < 1 || index > list->size) return NULL;
    return list->array[index - 1];
}

int findList(ArrayList list, E element){
    for (int i = 0; i < list->size; ++i) {
        if(list->array[i] == element) return i + 1;
    }
    return -1;
}
void printList(ArrayList list){   //编写一个函数用于打印表当前的数据
    for (int i = 0; i < list->size; ++i)   //表里面每个元素都拿出来打印一次
        printf("%d ", list->array[i]);
    printf("\n");
}
int main(){

    struct List list;
    ArrayList arraylist =&list;
    if(initList(arraylist)){

//        //测试初始化结果
//        printf(arraylist->capacity);
//        printf(arraylist->size);

        //测试插入操作
        insertList(arraylist, 666, 1);  //每次插入操作后都打印一下表，看看当前的情况
        printList(arraylist);
        insertList(arraylist, 777, 1);
        printList(arraylist);
        insertList(arraylist, 888, 2);
        printList(arraylist);

        //测试删除操作
        if(deleteList(arraylist,1))
            printList(arraylist);
        else
            printf("删除失败，未找到该元素");
        if(deleteList(arraylist,2))
            printList(arraylist);
        else
            printf("删除失败，未找到该元素");

        //获取顺序表长度
        printf("%d\n",sizeList(arraylist));

        //获取指定位置的元素
        int i=1;
        printf("第%d个元素的位置为%d\n",i,getList(arraylist,i));

        //查找元素下标
        printf("666的下标为：%d\n",findList(arraylist,666));
        printf("888的下标为：%d\n",findList(arraylist,888));

    } else{
        printf("顺序表初始化失败，无法启动程序！");
    }

}
1
2
3
4
5
6
7
8
9
666 
777 666 
777 888 666 
888 666 
888 
1
第1个元素的位置为888
666的下标为：-1
888的下标为：1

在使用printf时要严格格式化字符串，我在使用时因太长时间未用C语言，直接使用了printf(arraylist->size)导致一直报错而不知道原因是什么，此处是因为传过去的值，系统会将其当做地址使用，结果就是乱掉甚至崩溃，应当写成printf("%d",arraylist->size)

问题： 请问顺序实现的线性表，插入、删除、获取元素操作的时间复杂度为？

  • 插入： 因为要将后续所有元素都向后移动，所以平均时间复杂度为 O(n)
  • 删除： 同上，因为要将所有元素向前移动，所以平均时间复杂度为 O(n)
  • 获取元素： 因为可以利用数组特性直接通过下标访问到对应元素，所以时间复杂度为 O(1)

单链表

  • 尝试编写一个带头结点的链表：

初始化链表

  • 先定义链表的节点：
1
2
3
4
5
6
7
8
typedef int E;   //这个还是老样子

struct ListNode {
    E element;              //数据域：保存元素数据
    struct ListNode * next; //指针域：指向下一个结点的指针
};

typedef struct ListNode * Node;   //这里我们直接为结点指针起别名，可以直接作为表实现
  • 完成链表的初始化
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //定义初始化函数
    void initList(Node head){
        head->next = NULL;   //头结点默认下一个为NULL
    }

    int main() {
        //这里创建一个新的头结点，头结点不存放任何元素，只做连接，连接整个链表
        struct Node head;   
        initList(head);  //先进行初始化
    }

    链表的插入和删除

  • 按照以下步骤进行插入
    • 首先先将要插入的节点的后继节点指向原本这个位置的节点
    • 然后将插入位置的前驱结点的后继结点指向改为要插入的节点
  • 首先来设计函数
1
2
3
4
5
6
//head是头结点
//element为待插入元素
//index是待插入下标
void insertList(Node head, E element, int index){
		
}
  • 接着要想插入，需要先找到待插入结点的前驱结点
1
2
3
4
5
6
7
8
9
10
11
//返回值来告诉调用者是否插入成功
_Bool insertList(Node head, E element, int index){
    if(index < 1) return 0;   //如果插入的位置小于1，那肯定是非法的
    while (--index) {   //通过--index的方式不断向后寻找前驱结点
        head = head->next;   //正常情况下继续向后找
      	if(head == NULL) return 0;  
      	//如果在寻找的过程中发型已经没有后续结点了，那么说明index超出可插入的范围了，也是非法的，直接润
    }
    
    return 1;
}
  • 在循环操作完成后，如果没问题就能找到对应插入位置的前驱结点，我们只需要按照上面分析的操作来编写代码即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_Bool insertList(Node head, E element, int index){
    if(index < 1) return 0;
    //直到index减为0，则为找到第index个结点，在此插入
    while (--index) {
        head = head->next;
      	if(head == NULL) return 0;
    }
    //创建一个新的结点,存储需要插入的值
    Node node = malloc(sizeof (struct ListNode));
    if(node == NULL) return 0;   //创建一个新的结点，如果内存空间申请失败返回0
    node->element = element;   //将元素保存到新创建的结点中
    node->next = head->next;   //先让新插入的节点指向原本位置上的这个结点
    head->next = node;   //接着将前驱结点指向新的这个结点
    return 1;
}
  • 这样便完成了链表的插入操作，删除操作同理，这里直接给出删除的完整代码
1
2
3
4
5
6
7
8
9
10
11
12
_Bool deleteList(Node head, int index){
    if(index < 0) return 0;
    while (index--) {
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;
    Node tmp = head->next;   //先拿到待删除结点
    head->next = head->next->next;   //直接让前驱结点指向下一个的下一个结点
    free(tmp);   //最后使用free函数释放掉待删除结点的内存
    return 1;
}

其他函数

  • 查找元素位置
1
2
3
4
5
6
7
8
9
10
11
12
int findList(Node head, E element){
    //先找到头结点
    head = head->next;    
    int i = 1;   //计数器
    while (head) {
        if(head->element == element) return i;   //如果找到，那么就返回i
        head = head->next;   //没找到就继续向后看
        i++;   //i记住要自增
    }
    //全部遍历后依旧没找到，则返回-1表示未找到
    return -1;   
}
  • 查找链表长度
    • 其实就是遍历一遍，计数器挨个加1，最后返回计数器的值
1
2
3
4
5
6
7
8
int sizeList(Node head){
    int i = 0;  //从0开始
    while (head->next) {   //如果下一个为NULL那就停止
        head = head->next;
        i++;   //每向后找一个就+1
    }
    return i;
}

  • 因为每次测试都要重新插入数据非常繁琐，所以这里写一个函数，用来随机为链表插入指定个数的数据

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void randomInsertHead(Node head,int n){
        Node tempNode;

        for(int i=0;i<n;i++){
            tempNode=(Node)malloc(sizeof(struct ListNode));
            tempNode->element=rand()%100+1;
            tempNode->next=head->next;
            head->next=tempNode;
        }
    }

  • 除了在头结点后面插入元素，还可以插在链表的末尾

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void randomInsertTail(Node node,int n){
        Node tempNode;
        Node tail;
        if(node==NULL)
            tail=node;
        while(node){
            if(node->next==NULL)
                tail=node;
            node=node->next;
        }

        for(int i=0;i<n;i++){
            tempNode=(Node)malloc(sizeof(struct ListNode));
            tempNode->element=rand()%100+1;
            tail->next=tempNode;
            tail=tempNode;
        }
    }

链表完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//初始化链表
initList(Node): void
//插入元素
insertList(Node, E, int): _Bool
//删除元素
deleteList(Node, int): _Bool
//查找元素的下标
findList(Node, E): int
//获取链表长度
sizeList(Node): int
//获取元素
getList(Node, int): E
//为链表随机插入值(头插)
randomInsertHead(Node, int): void
//为链表随机插入值(尾插)
randomInsertTail(Node, int): void

//打印链表
PrintNode(Node): void
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int E;

struct ListNode {
    E element;
    struct ListNode * next;
};

typedef struct ListNode * Node;

void initList(Node node){
    node->next = NULL;
}

_Bool insertList(Node head, E element, int index){
    if(index < 1) return 0;
    while (--index) {
        head = head->next;
        if(head == NULL) return 0;
    }

    Node node = malloc(sizeof(struct ListNode));
    if(node == NULL) return 0;
    node->element = element;
    node->next = head->next;
    head->next = node;
    return 1;
}

_Bool deleteList(Node head, int index){
    if(index < 1) return 0;   //大体和上面是一样的
    while (--index) {
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;

    Node tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    return 1;
}

E  getList(Node head, int index){
    if(index < 1) return 0;
    do {
        head = head->next;
        if(head == NULL) return 0;
    } while (--index);
    return head->element;
}

int findList(Node head, E element){
    head = head->next;
    int i = 1;
    while (head) {
        if(head->element == element) return i;
        head = head->next;
        i++;
    }
    return -1;
}

int sizeList(Node head){
    //因为链表包含头结点，如果不为空，计算头结点后链表依旧是从0开始计算
    int i = -1;
    while (head) {
        head = head->next;
        i++;
    }
    return i;
}

void randomInsertHead(Node head,int n){
    Node tempNode;

    for(int i=0;i<n;i++){
        tempNode=(Node)malloc(sizeof(struct ListNode));
        tempNode->element=rand()%100+1;
        tempNode->next=head->next;
        head->next=tempNode;
    }
}

void randomInsertTail(Node node,int n){
    Node tempNode;
    Node tail;
    if(node==NULL)
        tail=node;

    //先遍历找到链表尾端
    while(node){
        if(node->next==NULL)
            tail=node;
        node=node->next;
    }

    for(int i=0;i<n;i++){
        tempNode=(Node)malloc(sizeof(struct ListNode));
        tempNode->element=rand()%100+1;
        tail->next=tempNode;
        tail=tempNode;
    }
}

void PrintNode(Node node){
    Node p = node->next;
    while(p != NULL){
        printf("%d ", p->element);
        p = p->next;  // 移动到下一个节点
    }
    printf("\n");
}

int main(){
    //必须写在主函数中只执行一次，否则如果两次调用间隔小于 1 秒，会导致随机数种子相同，生成完全相同的随机数序列
    srand(time(0));

    //开辟的是结构体占用的空间二不能填Node，Node是指针所占空间固定
    Node head =(Node)malloc(sizeof(struct ListNode));

    initList(head);
    printf("头插后： ");
    randomInsertHead(head,15);
    PrintNode(head);
    printf("\n");

    printf("尾插后： ");
    randomInsertTail(head,10);
    PrintNode(head);
    printf("\n");

    printf("插入元素22后： ");
    insertList(head,22,1);
    PrintNode(head);
    printf("\n");

    printf("删除第二个元素后: ");
    deleteList(head,2);
    PrintNode(head);
    printf("\n");

    printf("查找22这个元素的位置： %d",findList(head,22));
    printf("\n");

    printf("返回链表长度： %d",sizeList(head));
    printf("\n");

    printf("获取第一个元素： %d", getList(head,1));
    printf("\n");

}
最开始我遇到的错误
  • 为链表开辟内存部分，我直接使用了Node head =(Node)malloc(sizeof(Node))，Node是指针，所占大小是固定8个字节，所以这里应该使用Node head =(Node)malloc(sizeof(struct ListNode))
  • 期初我将随机数种子放到了随机数值的函数中，但这样导致了如果两次调用间隔小于 1 秒，会导致随机数种子相同，生成完全相同的随机数序列，所以我将随机数种子放到了主函数中

问题： 请问链式实现的线性表，插入、删除、获取元素操作的时间复杂度为？

  • 插入： 因为要寻找对应位置的前驱结点，所以平均时间复杂度为O(n)O(n)，但是不需要做任何的移动操作，效率肯定是比顺序表要高的。
  • 删除： 同上，所以平均时间复杂度为O(n)O(n)
  • 获取元素： 由于必须要挨个向后寻找，才能找到对应的结点，所以时间复杂度为O(n)O(n)，不支持随机访问，只能顺序访问，比顺序表慢。
  • 链表在随机访问元素时，需要通过遍历来完成，而顺序表则利用数组的特性直接访问得到
    • 所以读取数据多于插入或是删除数据的情况下时，使用顺序表会更好。
  • 顺序表在插入元素时就显得有些鸡肋了，因为需要移动后续元素，整个移动操作会浪费时间，而链表则不需要，只需要修改结点 指向即可完成插入
    • 所以频繁出现插入或删除的情况下，使用链表会更好。

双向链表和循环链表

双向链表

  • 在单链表中，可以不像顺序表那样，一次申请一段连续空间，而且在插入和删除速度上也更快，但是当我们想要操作某一个结点，比如删除或是插入，那么由于单链表的性质，我们只能先去找到它的前驱结点，才能进行。
  • 为了解决这个问题，我们让单链表不仅保存后续结点的指针，同时保存他的前驱结点的指针
  • 首先变更一下单链表的结构体和初始化方法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    typedef int E;

    struct ListNode {
        E element;   //保存当前元素
        struct ListNode * next;   //指向下一个结点的指针
        struct ListNode * prev;   //指向上一个结点的指针
    };

    typedef struct ListNode * Node;
    1
    2
    3
    void initNode(Node node){
        node->next = node->prev = NULL;
    }

双向链表的插入和删除操作

  • 双向链表的插入操作，是在单链表的插入基础上,还需要连接和修改结点的前驱指针
  • 插入操作的步骤：
    • 先将准备插入的结点的前驱指针和后驱指针置为NULL
    • 将新节点的前驱指针指向插入位置的前一个结点
    • 将新节点的后驱指针指向插入位置的结点
    • 将插入位置的前一个结点的后驱指针指向新节点
    • 将插入位置的结点的前驱指针指向新节点
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
// 个人感觉先将要插入的结点的前驱和后继指针挂到待插入位置的结点上，再对原链表的节点进行更改更容易理解
_Bool insertDoubleList(List head,E e,int pos){
    if(pos<1)
        return 0;
    while(--pos){
        head=head->next;
        //代表插入的位置不合法
        if(head==NULL)
            return 0;
    }
    List doubleList =malloc(sizeof(struct DoubleList));
    if(doubleList==NULL)
        return 0;
    doubleList->element=e;

//    当插入位置后继结点存在时，即不是最后一个元素
    if(head->next){
        doubleList->next=head->next;
        doubleList->pre=head;
        head->next->pre=doubleList;
        head->next=doubleList;
    }
    else{
        doubleList->pre=head;
        doubleList->next=NULL;
        head->next=doubleList;
    }

    return 1;
}

删除操作相比插入操作更加简单，只需要遍历到删除的位置的前一个结点，让前一个结点与删除的后一个节点相连，最后再释放掉要删除的结点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
_Bool deleteList(List list,int pos){
    //和插入操作一样先找到要删除的位置的前一个节点
    while(--pos){
        list=list->next;
        //说明下标不合法
        if(list==NULL)
            return 0;
    }
    //说明删除位置没有元素
    if(!list->next)
        return 0;
    //记录一下要删除的节点，最后释放该节点
    List temp=list->next;
    //如果要删除的不是最后一个元素
    if(list->next->next){
        list->next->next->pre=list;
        list->next=list->next->next;
    }
    else{
        list->next=NULL;
    }
    free(temp);
}

其他操作类似，在此不过多赘述

完整实现

1
2
3
4
5
6
7
8
initDoubleList(List):void
insertDoubleList(List,E,int):bool
deleteList(List,int):bool
printList(List):void
randomInsertHead(List,int):bool
findList(List,E):int
sizeList(List):int
getListElement(List,int):int
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int E;

struct DoubleList{
    E element;
    struct DoubleList* pre;
    struct DoubleList* next;
};

typedef struct DoubleList* List;
void initDoubleList(List list){
    list->pre=NULL;
    list->next=NULL;
}
_Bool insertDoubleList(List head,E e,int pos){
    if(pos<1)
        return 0;
    while(--pos){
        head=head->next;
        //代表插入的位置不合法
        if(head==NULL)
            return 0;
    }
    List doubleList =(List)malloc(sizeof(struct DoubleList));
    if(doubleList==NULL)
        return 0;
    doubleList->element=e;

//    当插入位置后继结点存在时，即不是最后一个元素
    if(head->next){
        doubleList->next=head->next;
        doubleList->pre=head;
        head->next->pre=doubleList;
        head->next=doubleList;
    }
    else{
        doubleList->pre=head;
        doubleList->next=NULL;
        head->next=doubleList;
    }

    return 1;
}

_Bool deleteList(List list,int pos){
    //和插入操作一样先找到要删除的位置的前一个节点
    while(--pos){
        list=list->next;
        //说明下标不合法
        if(list==NULL)
            return 0;
    }
    //说明删除位置没有元素
    if(!list->next)
        return 0;
    //记录一下要删除的节点，最后释放该节点
    List temp=list->next;
    //如果要删除的不是最后一个元素
    if(list->next->next){
        list->next->next->pre=list;
        list->next=list->next->next;
    }
    else{
        list->next=NULL;
    }
    free(temp);
}
void printList(List list){
    list=list->next;
    if(list==NULL)
        return;

    while(list!=NULL){
        printf("%d ",list->element);
        list=list->next;
    }
    printf("\n");
}

_Bool randomInsertHead(List doubleList,int n){
    List tempList;
    for(int i=0;i<n;i++){
        tempList=(List)malloc(sizeof(struct DoubleList));
        if(tempList==NULL)
            return 0;
        tempList->element=rand()%100+1;
        if(doubleList->next){
            tempList->next=doubleList->next;
            tempList->pre=doubleList;
            doubleList->next->pre=tempList;
            doubleList->next=tempList;
        }
        else{
            tempList->next=doubleList->next;
            tempList->pre=doubleList;

            doubleList->next=tempList;
        }
    }
    return 1;
}
int findList(List list,E e){
    if(list==NULL)
        return -1;
    int count=0;
    //第一个是头结点，所以直接跳过
    list=list->next;
    while(list){
        count++;
        if(list->element==e)
            return count;
        list=list->next;
    }
    return -1;

}
int sizeList(List list){
    list=list->next;
    int count=0;
    while(list){
        count++;
        list=list->next;
    }
    return count;
}
int getListElement(List list,int index){
    //找到指定位置
    for(int i=0;i<index;i++){
        list=list->next;
    }
    return list->element;
}


int main(){
    srand(time(0));
    List list;
    list=(List)malloc(sizeof(struct DoubleList));
    initDoubleList(list);
    randomInsertHead(list,10);
    printf("随机生成长度为10的链表:\n");
    printList(list);
    insertDoubleList(list,10,2);
    printf("添加元素10后:\n");
    printList(list);
    deleteList(list,1);
    printf("删除第一个元素后:\n");
    printList(list);
    int find = findList(list,10);
    printf("10位于链表第%d位\n",find);
    int size =sizeList(list);
    printf("该链表的长度为：%d\n",size);
    int elem=getListElement(list,1);
    printf("链表第一位元素为：%d\n",elem);
}
1
2
3
4
5
6
7
8
随机生成长度为10的链表:
73 19 59 65 16 47 85 59 50 51 
添加元素10后:
73 10 19 59 65 16 47 85 59 50 51 
10 19 59 65 16 47 85 59 50 51 
10位于链表第1位
该链表的长度为：10
链表第一位元素为：10

循环链表

循环链表，这种链表实际上和前面的链表是一样的，只是它的最后一个结点，是与头结点相连的，双向链表和单向链表都可以做成这样的环形结构