线性表
#数据结构 #线性表

总结: 1. 线性表的逻辑结构特性是指数据元素之间存在着线性关系 2. 对于顺序表，元素存储的相邻位置反应出其逻辑上的线性关系，可借助数组来表示。给定数组的下标，便可以存取相应的元素，可称为随机存储结构。 3. 链表由一系列不必在内存中相连的结构组成。 每一个结构均含有表元素和指向包含该元素后继元的结构的指针。

顺序表和链表的比较
顺序表 链表
空间 存储空间 预先分配，会导致空间闲置或溢出现象 动态分配，不会出现存储空间闲置或溢出现象
存储密度 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1 需要借助指针来体现元素间的逻辑关系，存储密度小于1
时间 存取元素 随机存取，按位置访问元素的时间复杂度为O(1) 顺序存储，按位置访问元素时间复杂度为O(n)
插入、删除 平均移动约表中一半元素，时间复杂度为O(n) 不需要移动元素，确定插入、删除位置后，时间复杂度为O(1)
使用情况
  • 表长变化不大，且能事先确定变化的范围
  • 很少进行插入或者删除操作，经常按元素位置序号访问数据元素
  • 长度变化较大
  • 频繁进行插入和删除操作

单链表、循环链表和双向链表的比较
查找表头结点 查找表尾结点 查找结点*p的前驱结点
带头结点的单链表L L->next 时间复杂度O(1) 从L->next依次向后遍历 时间复杂度O(n) 通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表 L->next 时间复杂度O(1) 从L->next依次向后遍历 时间复杂度O(n) 通过p->next找到其前驱 时间复杂度O(n)
带头结点仅设尾指针R的循环单链表 R->next 时间复杂度O(1) R 时间复杂度O(1) 通过p->next找到其前驱 时间复杂度O(n)
带头结点的双向循环链表L L->next 时间复杂度O(1) L->prior 时间复杂度O(1) p->prior 时间复杂度O(1)

链表基础操作

结构体定义

1
2
3
4
5
6
typedef struct Node* PtrNode;
typedef struct Node Node;
struct Node {
    PtrNode next;
    int value;
}

链表是否为空

1
2
3
4
int isEmpty(PtrNode head)
{
    return head == NULL;
}

查找链表中元素为x的结点

1
2
3
4
5
6
7
8
9
10
11
PtrNode Find(PtrNode head, int x) {
    PtrNode p;
    if (head == NULL) {
        return NULL;
    }
    p = head->next;
    while (p!=NULL && p->value != x) {
        p = p->next;
    }
    return p;
}

删除链表中元素为x的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
PtrNode Delete(PtrNode head, int x) {
    if (head == NULL) {
        return head;
    }

    PtrNode dummyHead = (PtrNode)malloc(sizeof(Node));
    dummyHead->next = head;

    PtrNode cur = dummyHead;
    while (cur->next!=NULL) {
        if (cur->next->value == x) {
            PtrNode tmp = cur->next;
            cur->next = tmp->next;
            free(tmp);
            break;
        }
        cur = cur->next;
    }
    return dummyHead->next;
}

链表中指定位置插入元素x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Insert(PtrNode head, int index, int x) {
    PtrNode cur = head;
    // 获取到指定位置的上一个结点
    while (cur!=NULL&&index!=1) {
        cur=cur->next;
        index--;
    }
    if (cur == NULL) {
        return;
    }

    PtrNode node = (PtrNode)malloc(sizeof(Node));
    node->value = x;

    node->next = cur->next;
    cur->next = node;
    return;
}

打印链表

1
2
3
4
5
6
7
8
9
10
11
void Print(PtrNode head) {
    if (head == NULL) {
        return;
    }
    PtrNode cur = head;
    while (cur != NULL) {
        printf("%d->", cur->value);
        cur = cur->next;
    }
    printf("NULL\n");
}

链表的应用

多项式相加和相乘

通过递归实现链表归并排序

  • 分割 cut 环节：找到当前链表中点，并从中点将链表断开（以便在下次递归cut时，链表拥有正确的边界）
    • 使用fast, slow快慢指针，奇数个结点找到中点，偶数个结点找到中心左边的结点
    • 找到中点slow结点后，执行slow.next=None将链表切断
    • 递归分割时，输入当前链表左端点head和中心结点slow的下一个结点tmp（因为链表是从slow切断的）
    • cut 递归终止条件，当head.next=None时，说明只有一个结点了，直接返回此结点
  • 合并 merge 环节：将两个有序链表合并，转化成一个有序链表
    • 双指针法合并，建立辅助PtrNode dummyHead作为头部
    • 设置两指针shadowHeadA，shadowHeadB分别指向两指针头部，比较两指针处结点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表
    • 返回辅助PtrNode dummyHead作为头部的下个结点dummyHead->next
    • 时间复杂度O(m+n), m, n分别是两个链表的长度
多项式相加和相乘 
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include<stdio.h>
#include<stdlib.h>

typedef struct Node Polynomial;
typedef struct Node* PtrNode;
struct Node {
    PtrNode next;
    double coefficient; // 系数
    int exponent; // 指数
};

void Print(PtrNode head) {
    if (head == NULL) {
        return;
    }
    PtrNode cur = head;

    int first = 0;
    printf("表达式:\t");
    while (cur != NULL) {
        if (cur->coefficient > 0 && first) {
            printf("+");
        }
        if (cur->exponent == 0) {
            printf("%d", cur->exponent);
        } else if (cur->exponent == 1) {
            printf("%dx", cur->exponent);
        } else {
            printf("%lgx^%d", cur->coefficient, cur->exponent);
        }
        cur = cur->next;
        first = 1;
    }
    printf("\n");
}

// Merge 合并两个有序链表
PtrNode Merge(PtrNode headA, PtrNode headB) {
    PtrNode dummyHead = (PtrNode) malloc(sizeof(Polynomial));
    PtrNode cur = dummyHead;
    PtrNode shadowHeadA = headA;
    PtrNode shadowHeadB = headB;

    while (shadowHeadA != NULL && shadowHeadB != NULL) {
        if (shadowHeadA->exponent <= shadowHeadB->exponent)
        {
            cur->next = shadowHeadA;
            shadowHeadA = shadowHeadA->next;
        } else {
            cur->next = shadowHeadB;
            shadowHeadB = shadowHeadB->next;
        }
        cur = cur->next;
    }
    if (shadowHeadA != NULL) {
        cur->next = shadowHeadA;
    }
    if (shadowHeadB != NULL) {
        cur->next = shadowHeadB;
    }
    return dummyHead->next;
}

// Sort 按指数降序排序
// 二分法归并排序(快慢指针)
PtrNode Sort(PtrNode head, PtrNode tail) {
    if (head == NULL) {
        return head;
    }
    if (head->next == tail) {
        head->next = NULL;
        return head;
    }

    PtrNode fast = head;
    PtrNode slow = head;
    while (fast != tail) {
        fast = fast->next;
        slow = slow->next;
        if (fast != tail) {
            fast = fast->next;
        }
    }
    return Merge(Sort(head, slow), Sort(slow, tail));
}

// CreatePolynomial 创建多项式
PtrNode CreatePolynomial(int length) {
    double coefficient;
    int exponent;

    PtrNode dummyHead = (PtrNode)malloc(sizeof(Polynomial));
    PtrNode cur = dummyHead;

    while (length--) {
        PtrNode node = (PtrNode)malloc(sizeof(Polynomial));
        scanf("%lg %d", &coefficient, &exponent);
        node->coefficient = coefficient;
        node->exponent = exponent;

        cur->next = node;
        cur = node;
    }
    return dummyHead->next;
}

// Add 多项式相加
PtrNode Add(PtrNode polynomialLeft, PtrNode polynomialRight) {
    PtrNode shadowPolynomialLeft = Sort(polynomialLeft, NULL);
    PtrNode shadowPolynomialRight = Sort(polynomialRight, NULL);

    if (polynomialLeft == NULL) {
        return polynomialRight;
    }
    if (polynomialRight == NULL) {
        return polynomialLeft;
    }

    PtrNode dummyHead = (PtrNode)malloc(sizeof(Polynomial));
    PtrNode cur = dummyHead;

    while (shadowPolynomialLeft->exponent<shadowPolynomialRight->exponent)
    {
        cur->next = shadowPolynomialLeft;
        cur = cur->next;
        shadowPolynomialLeft = shadowPolynomialLeft->next;
    }
    while (shadowPolynomialLeft!=NULL && shadowPolynomialRight!=NULL)
    {
        if (shadowPolynomialLeft->exponent == shadowPolynomialRight->exponent) {
            PtrNode node = (PtrNode)malloc(sizeof(Polynomial));
            node->exponent = shadowPolynomialLeft->exponent;
            node->coefficient = shadowPolynomialLeft->coefficient+shadowPolynomialRight->coefficient;
            cur->next = node;
            shadowPolynomialRight = shadowPolynomialRight->next;
            shadowPolynomialLeft = shadowPolynomialLeft->next;
        } else if (shadowPolynomialLeft->exponent < shadowPolynomialRight->exponent) {
            cur->next = shadowPolynomialLeft;
            shadowPolynomialLeft = shadowPolynomialLeft->next;
        } else {
            cur->next = shadowPolynomialRight;
            shadowPolynomialRight = shadowPolynomialRight->next;
        }
        cur = cur->next;
    }
    if (shadowPolynomialLeft != NULL) {
        cur->next = shadowPolynomialLeft;
    }
    if (shadowPolynomialRight != NULL) {
        cur->next = shadowPolynomialRight;
    }
    return dummyHead->next;
}

// Multi 多项式相乘
PtrNode Multi(PtrNode polynomialLeft, PtrNode polynomialRight) {
    if (polynomialLeft == NULL || polynomialRight == NULL) {
        return NULL;
    }

    PtrNode dummyHead = (PtrNode)malloc(sizeof(Polynomial));
    dummyHead->next = NULL;

    PtrNode shadowPolynomialLeft = Sort(polynomialLeft, NULL);
    PtrNode shadowPolynomialRight = Sort(polynomialRight, NULL);
    while(shadowPolynomialLeft != NULL)
    {
        PtrNode result = (PtrNode)malloc(sizeof(Polynomial));
        PtrNode cur = result;
        PtrNode p = shadowPolynomialRight;
        while (p != NULL)
        {
            PtrNode node = (PtrNode)malloc(sizeof(Polynomial));
            // 系数相乘
            node->coefficient = shadowPolynomialLeft->coefficient * p->coefficient;
            // 指数相加
            node->exponent = shadowPolynomialLeft->exponent + p->exponent;
            cur->next = node;

            cur = cur->next;
            p = p->next;
        }
        cur->next = NULL;
        dummyHead->next = Add(dummyHead->next, result->next);
        shadowPolynomialLeft = shadowPolynomialLeft->next;
    }
    return dummyHead->next;
}

int main() {
    int numberOfTerm;
    printf("请输入多项式的项数:\n");
    scanf("%d", &numberOfTerm);
    PtrNode polynomialLeft = CreatePolynomial(numberOfTerm);
    Print(polynomialLeft);

    printf("请输入多项式的项数:\n");
    scanf("%d", &numberOfTerm);
    PtrNode polynomialRight = CreatePolynomial(numberOfTerm);
    Print(polynomialRight);

    printf("多项式相加\n");
    PtrNode result = Add(polynomialLeft, polynomialRight);
    Print(result);

    printf("多项式相乘\n");
    result = Multi(polynomialLeft, polynomialRight);
    Print(result);

    return 0;
}

基数排序

  • 以静态链表存储待排记录，并令表头指针指向第一个记录
  • “分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同
  • “收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表
  • 对每个关键字位均重复 2 和 3 两步
基数排序 
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
// 基数排序
#include<stdio.h>
#include<stdlib.h>

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

// ShowNode 打印链表
void ShowNode(Node* head) {
    Node* p = head;
    while(p != NULL)
    {
        printf("%d\t", p->value);
        p = p->next;
    }
}

// CreateNode 创建链表
Node* CreateNode() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* cur = head;
    int length = 0;
    printf("请输入待排序链表的长度:");
    while(length<=0) {
        scanf("%d", &length);
        if (length <= 0) {
            printf("请输入大于零的整数\n");
        }
    }
    printf("请输入%d个整数\n", length);
    for (int i=0; i<length; i++) {
        Node* node = (Node*)malloc(sizeof(Node));
        scanf("%d", &node->value);
        cur->next = node;
        cur = cur->next;
    }
    cur->next = NULL;

    return head->next;
}

// Length 返回链表长度
int Length(Node* head)
{
    int length = 0;
    Node* cur = head;
    while(cur!=NULL)
    {
        length++;
        cur = cur->next;
    }
    return length;
}

// GetNumInPos 返回整数num在pos位的数
int GetNumInPos(int num, int pos)
{
    int temp = 1;
    for (int i=1;i<pos;i++) {
        temp *= 10;
    }
    return (num/temp)%10;
}

// GetDigitOfNum 返回整数num有多少位
int GetDigitOfNum(int num)
{
    int n = 1, temp = 10;
    while (temp <= num) {
        n++;
        temp*=10;
    }
    return n;
}

// GetMaxDigit 返回链表中最大数有几位数
int GetMaxDigit(Node* head) {
    Node* cur = head;
    int n, max;
    while(cur!=NULL) {
        n = GetDigitOfNum(cur->value);
        if (n > max) {
            max = n;
        }
        cur = cur->next;
    }
    return max;
}

// RadixSort 基数排序
void RadixSort(Node* head) {
    int nodeLength = Length(head);
    int index[10][nodeLength]; // 二维数组分类, 从上到下0-9, 对应数字的每行可保存nodeLength个数
    int count[10]; // 用数组记录被分配基数个数
    int maxDigit = GetMaxDigit(head);

    for (int pos = 0; pos < maxDigit; pos++)
    {
        Node* p = head;
        for (int i = 0; i < 10; i++)
        {
            count[i] = 0;
        }
        while (p != NULL)
        {
            int n = GetNumInPos(p->value, pos+1);
            index[n][count[n]] = p->value;
            count[n]++;
            p = p->next;
        }

        Node* l = head;
        for (int i = 0; i < 10;i++)
        {
            for (int j=0; j < count[i]; j++)
            {
                l->value = index[i][j];
                l = l->next;
            }
        }
        printf("第%d次排序:\n", pos+1);
        ShowNode(head);
        printf("\n");
    }
}

int main()
{
    Node* head = CreateNode();
    printf("已经创建单链表:\n");
    ShowNode(head);
    printf("\n");
    RadixSort(head);
    printf("最终排序结果:\n");
    ShowNode(head);
    return 0;
}
上一页
#数据结构 #线性表
下一页