线性表

线性表，全名为线性存储结构，存储 “一对一” 逻辑关系的数据。


顺序表

  • 插入元素
  • 删除元素
  • 查找元素
  • 修改元素

完整代码

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
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct {
    int *data;
    int len;
} List_s;

void NumCheck(int num) {
    if (num > MAXSIZE) {
        printf("超出最大存储值！\r\n");
        exit(0);
    } else if (num < 0) {
        printf("请设置正确的值！\r\n");
        exit(0);
    }
}

void InitList(List_s L) {
    L.data = (int *) malloc(MAXSIZE * sizeof(int));
    if (L.data == NULL) {
        printf("空间分配失败！\r\n");
        exit(0);
    }
    L.len = 0;
    printf("空间分配成功！\r\n");
}


void InputList(List_s *L, int addlen) {
    NumCheck(addlen);
    printf("请输入%d个值\r\n", addlen);
    for (int i = 0; i < addlen; i++) {
        scanf("%d", &L->data[i]);
    }
    L->len = addlen;
    printf("输入完毕！\r\n");
}

// 填入元素的下标位置！
void AddList(List_s *L, int pos, int addNum) {
    NumCheck(pos);
    if (pos > L->len || L->len == MAXSIZE) {
        printf("下标位置不正确或已达到最大长度，不能再插入！\r\n");
        exit(0);
    }
    for (int i = L->len; i >= pos; i--) {
        L->data[i + 1] = L->data[i];
    }
    L->data[pos] = addNum;
    L->len = L->len + 1;
    printf("插入完毕！(下标位置：%d)\r\n",pos);
}

void DelList(List_s *L, int pos) {
    NumCheck(pos);
    if (pos >= L->len || pos < 0) {
        printf("下标位置不正确，不能删除！\r\n");
        exit(0);
    }
    for (int i = pos; i <= L->len; i++) {
        L->data[i] = L->data[i + 1];
    }
    L->len = L->len - 1;
    printf("删除完毕！(下标位置：%d)\r\n",pos);
}

void UpdataList(List_s L, int pos, int addNum){
    NumCheck(pos);
    if (pos >= L.len || pos < 0) {
        printf("下标位置不正确，不能修改数据！\r\n");
        exit(0);
    }
    L.data[pos]=addNum;
    printf("修改完毕！(下标位置：%d)\r\n",pos);
}


void ShowList(List_s L) {
    printf("List:\t");
    for (int j = 0; j < L.len; j++) {
        printf("%d\t", L.data[j]);
    }
    printf("\r\n");
}

void QueryList(List_s L, int pos){
    NumCheck(pos);
    if (pos >= L.len || pos < 0) {
        printf("下标位置不正确，查询失败！\r\n");
        exit(0);
    }
    printf("查询结果 (下标位置：%d)：%d",pos,L.data[pos]);
}

int main(void) {

    List_s list;
    InitList(list);

    InputList(&list, 5);
    ShowList(list);
    AddList(&list, 3, 66);
    ShowList(list);
    DelList(&list, 0);
    ShowList(list);
    UpdataList(list, 4, 77);
    ShowList(list);
    QueryList(list,2);

    return 0;
}


静态链表

  • 结点

  • 插入元素

  • 删除元素

  • 查找元素

  • 修改元素


完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct {
    int data;   //数据域
    int next; //游标(cur)
} List_s[MAXSIZE];


int main(void) {
    List_s list;
    list[0].data=1;
    list[0].next=3;
    printf("list:%d",list[0].data);


    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
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
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int data;
    struct List_s *next;
} List_s;   //*List_ss

/***************************************************/

List_s *CreatList() {
    List_s *headNode = (List_s *) malloc(sizeof(List_s));
    headNode->next = NULL;
    return headNode;
}

List_s *CreatNode(int data) {
    List_s *node = (List_s *) malloc(sizeof(List_s));
    node->data = data;
    node->next = NULL;
    return node;
}

void printList(List_s *headnode) {
    List_s *p = (List_s *) headnode->next;
    printf("List:\t");
    while (p) {
        printf("%d\t", p->data);
        p = (List_s *) p->next;
    }
    printf("\r\n");
}

void AddNodeInFir(List_s *headnode, int data) {
    List_s *newnode = CreatNode(data);
    newnode->next = headnode->next;
    headnode->next = (struct List_s *) newnode;
}

void AddNodeInEnd(List_s *headnode, int data, List_s *endnode) {
    if (endnode == NULL) {
        List_s *pos = (List_s *) headnode;
        while (pos->next) {
            pos = (List_s *) pos->next;
        }
        endnode = pos;
    }
    List_s *newnode = CreatNode(data);
    endnode->next = (struct List_s *) newnode;
    endnode = newnode;
}


void DelNode(List_s *headnode, int pos) {
    if (headnode->next == NULL) {
        printf("链表为空！\r\n");
        return;
    }
    List_s *fornnode = (List_s *) headnode;
    List_s *posnode = (List_s *) headnode->next;

    for (int i = 1; i < pos; i++) {
        fornnode = posnode;
        posnode = (List_s *) posnode->next;
        if (!posnode) {
            printf("没有找到该位置，删除失败！\r\n");
            return;
        }
    }
    fornnode->next = posnode->next;
    free(posnode);
    printf("删除结点成功！-----%d\r\n", pos);
}

void UpdataNode(List_s *headnode, int pos, int newnum) {
    if (headnode->next == NULL) {
        printf("链表为空！\r\n");
        return;
    }
    List_s *posnode = (List_s *) headnode->next;
    for (int i = 1; i < pos; i++) {
        posnode = (List_s *) posnode->next;
        if (!posnode) {
            printf("没有找到该位置，修改失败！\r\n");
            return;
        }
    }
    posnode->data = newnum;
    printf("修改结点成功！-----%d\r\n", pos);
}

void QueryNode(List_s *headnode, int pos) {
    if (headnode->next == NULL) {
        printf("链表为空！\r\n");
        return;
    }
    List_s *posnode = (List_s *) headnode->next;
    for (int i = 1; i < pos; i++) {
        posnode = (List_s *) posnode->next;
        if (!posnode) {
            printf("没有找到该位置，查找失败！\r\n");
            return;
        }
    }
    printf("查找成功！-----pos:%d,data:%d\r\n", pos, posnode->data);
}

List_s *CopyList(List_s *L) {
    List_s *p = L;
    List_s *newlist = CreatList();

    List_s *endnode = NULL;
    while (p->next) {
        p = (List_s *) p->next;
        AddNodeInEnd(newlist, p->data, endnode);
    }
    free(endnode);
    return newlist;
}

/* 并集 union，带头结点; L2 接 L1 后*/
List_s *UnionList(List_s *L1, List_s *L2) {
    List_s *newlist = CopyList(L1);
    List_s *L1endnode = newlist;
    List_s *L2Node = CopyList(L2);

    if (newlist->next == NULL) {
        return newlist;
    } else if (L2Node->next == NULL) {
        return L2Node;
    }

    while (L1endnode->next) {
        L1endnode = (List_s *) L1endnode->next;
    }

    L1endnode->next = L2Node->next;

//    free(L1endnode);
//    free(L2Node);
    return newlist;
}

int main(void) {
    int num; //用于存储输入的数据

    /* 创建一个新单链表，并创建多个结点 */
    List_s *headnode = CreatList();
    printf("输入 List 1：\r\n");
    /* 使用尾部插入法，需要endnode记录尾部 */
    List_s *endnode = NULL;
    for (int i = 0; i < 3; i++) {
        scanf("%d", &num);
        AddNodeInEnd(headnode, num, endnode);
//        AddNodeInFir(headnode,num);
    }
    free(endnode); // 释放内存

    printList(headnode);
    DelNode(headnode, 4);       // 删除第四个值，即删除第5个结点（包含头结点）
    printList(headnode);
    UpdataNode(headnode, 4, 66);    // 修改结点的值
    printList(headnode);
    QueryNode(headnode, 5); // 查询结点的值

    /****************************/

    /* 再创建一个单链表 */
    printf("\r\n输入 List 2：\r\n");
    List_s *headnode2 =CreatList();
    List_s *endnode2 = NULL;
    for (int i = 0; i < 3; i++) {
        scanf("%d", &num);
        AddNodeInEnd(headnode2, num, endnode2);
//        AddNodeInFir(headnode,num);
    }
    free(endnode2);
    printList(headnode2);

    /* 合并两个单链表 */
    List_s *uilist = UnionList(headnode,headnode2);
    printf("\r\n合并结果：\t\r\n");

    printList(headnode);
    printList(headnode2);
    printList(uilist);

    return 0;
}

双向链表

  • 前驱节点（指针域 prior）
  • 数据域
  • 后继结点（指针域 next）
  • 添加结点（表头、表间、表尾）
  • 删除结点
  • 查找结点
  • 修改结点

完整代码

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
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    struct List_s *prior;
    int data;
    struct List_s *next;
} List_s;

List_s *CreatList() {
    List_s *headNode = (List_s *) malloc(sizeof(List_s));
    headNode->prior = NULL;
    headNode->next = NULL;
    return headNode;
}

List_s *CreatNode(int data) {
    List_s *node = (List_s *) malloc(sizeof(List_s));
    node->prior = NULL;
    node->data = data;
    node->next = NULL;
    return node;
}

void printList(List_s *headnode) {
    List_s *p = (List_s *) headnode->next;
    printf("List:\t");
    while (p) {
        printf("%d\t", p->data);
        p = (List_s *) p->next;
    }
    printf("\r\n");
}

/* 结点后方插入 */
void AddNode(List_s *L, int pos, int data) {
    if (pos == 0) {
        printf("至少为1！\r\n");
    }
    List_s *posnode = L;
    for (int i = 1; i < pos; i++) {
        if (!posnode) {
            printf("没有找到该位置，插入失败！\r\n");
            return;
        }
        posnode = (List_s *) posnode->next;
    }

    List_s *newnode = CreatNode(data);
    newnode->next = posnode->next;
    newnode->prior = (struct List_s *) posnode;
    posnode->next = (struct List_s *) newnode;
}

void DelNode(List_s *headnode, int pos) {
    if (headnode->next == NULL) {
        printf("链表为空！\r\n");
        return;
    }
    List_s *posnode = (List_s *) headnode->next;
    for (int i = 1; i < pos; i++) {
        posnode = (List_s *) posnode->next;
        if (!posnode) {
            printf("没有找到该位置，删除失败！\r\n");
            return;
        }
    }
    List_s *priornode = (List_s *) posnode->prior;
    List_s *nextnode = (List_s *) posnode->next;
    priornode->next = posnode->next;
    nextnode->prior = (struct List_s *) priornode;
    free(posnode);
    printf("删除结点成功！-----%d\r\n", pos);
}

void UpdataNode(List_s *headnode, int pos, int newnum) {
    if (headnode->next == NULL) {
        printf("链表为空！\r\n");
        return;
    }
    List_s *posnode = (List_s *) headnode->next;
    for (int i = 1; i < pos; i++) {
        posnode = (List_s *) posnode->next;
        if (!posnode) {
            printf("没有找到该位置，修改失败！\r\n");
            return;
        }
    }
    posnode->data = newnum;
    printf("修改结点成功！-----%d\r\n", pos);
}

void QueryNode(List_s *headnode, int pos) {
    if (headnode->next == NULL) {
        printf("链表为空！\r\n");
        return;
    }
    List_s *posnode = (List_s *) headnode->next;
    for (int i = 1; i < pos; i++) {
        posnode = (List_s *) posnode->next;
        if (!posnode) {
            printf("没有找到该位置，查找失败！\r\n");
            return;
        }
    }
    printf("查找成功！-----pos:%d , data:%d\r\n", pos, posnode->data);

}

int main(void) {


    List_s *headnode = CreatList();
    int addcount = 6;
    int num;
    printf("请输入%d个数：\r\n", addcount);
    for (int i = 0; i < addcount; i++) {
        scanf("%d", &num);
        AddNode(headnode, i + 1, num);
    }
    printList(headnode);
    DelNode(headnode, 4);
    printList(headnode);
    UpdataNode(headnode, 4, 233);
    printList(headnode);
    QueryNode(headnode, 4);

    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
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5

typedef struct {
    int *base;
    int *top;
    int size;
} stack_s;

/*
 * 初始化
 * 进栈
 * 出栈
 * 取栈顶
 * 判断栈空与栈满
 * ------
 * 括号匹配
 * 数值转换
 */

stack_s *CreatStack() {

    stack_s *s = (stack_s *) malloc(sizeof(stack_s));
    s->base = (int *) malloc(MAXSIZE * sizeof(int));
    s->top =  s->base;
    s->size = MAXSIZE;
    return s;
}

void push(stack_s *s, int data) {
    if(s->top - s->base == s->size){
        printf("栈满了，入栈失败\r\n");
        return;
    }
    *(s->top++) = data;
    printf("入栈:%d\r\n", *(s->top-1));
}

void pop(stack_s *s, int *data) {
    if(s->top == s->base ){
        printf("栈低了，没有数据可出栈\r\n");
        return;
    }
    *data = *(--s->top);
    printf("出栈:%d\r\n", *data);
}

int getStackTop(stack_s *s){
    if(s->top != s->base){
        return *(s->top-1);
    }
}

int main() {
    stack_s *s = CreatStack();
    int *getdata = malloc(sizeof(int));

    push(s, 6);
    push(s, 5);
    push(s, 4);
    printf("取栈顶：%d\r\n",getStackTop(s));
    push(s, 3);
    push(s, 2);
    printf("取栈顶：%d\r\n",getStackTop(s));
    push(s, 1);
    pop(s, getdata);
    pop(s, getdata);
    pop(s, getdata);
    printf("取栈顶：%d\r\n",getStackTop(s));
    pop(s, getdata);
    pop(s, getdata);
    pop(s, getdata);

    /* 遍历栈，栈顶开始 */
    int *p = s->top-1;
    printf("-----\t\r\n");
    if(p == s->base-1){
        printf("没有数据哦！\r\n");
    }
    while(p != s->base-1){
        printf("栈：%d\t\r\n", *p);
        p--;
    }
    printf("-----\t\r\n");



    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
#include <stdio.h>
#include <stdlib.h>

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

stack_s *CreatStack() {
    stack_s *s = (stack_s *) malloc(sizeof(stack_s));
    s->data = -1;
    s->next = NULL;
    return s;
}

void push(stack_s **s, int data) {
    stack_s *node = (stack_s *) malloc(sizeof(stack_s));
    node->data = data;
    node->next = (struct stack_s *) *s;
    *s = node;
    printf("push:%d\r\n", (*s)->data);
}

int pop(stack_s **s) {
    if ((*s)->next == NULL) {
        return -1;
    }
    int data = (*s)->data;

    stack_s *tmp = *s;
    *s = (stack_s *) (*s)->next;
    free(tmp);

    printf("出栈:%d\r\n", data);
    return data;
}

int getStackTop(stack_s *s) {
    if (s != NULL) {
        return s->data;
    }
    return -1;
}

int main() {
    stack_s *s = CreatStack();
    push(&s, 8);
    push(&s, 7);
    push(&s, 6);
    push(&s, 5);
    push(&s, 4);
    push(&s, 3);
    push(&s, 2);
    push(&s, 1);
    printf("取栈顶：%d\r\n", getStackTop(s));
    pop(&s);
    printf("取栈顶：%d\r\n", getStackTop(s));
    pop(&s);
    printf("取栈顶：%d\r\n", getStackTop(s));

    /* 遍历栈，栈顶开始 */
    stack_s *p = s;
    printf("-----\t\r\n");

    if(p->next==NULL){
        printf("没有数据哦！\r\n");
    }
    while(p->next!=NULL){
        printf("栈：%d\t\r\n", p->data);
        p= (stack_s *) p->next;
    }

    printf("-----\t\r\n");
    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
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5

typedef struct {
    int *base;
    int front;  // 队头下标
    int rear;   // 队尾下标
    int flag;  // 进队&出队标识位，用于判断队空还是队满。进队后置1，出队后置0。
} queue_s;

queue_s *CreatQueue() {
    queue_s *q = (queue_s *) malloc(sizeof(queue_s));
    q->base = (int *) malloc(MAXSIZE * sizeof(int));
    q->front = q->rear =q->flag = 0;
    return q;
}

void InQueue(queue_s *q, int data) {
    if (q->flag == 1 && q->rear == q->front) {
        printf("队满\r\n");
        return;
    }
    q->base[q->rear] = data;
    printf("进队：%d\r\n", q->base[q->rear] );

    q->rear = (q->rear + 1) % MAXSIZE;
    q->flag = 1;
}

void OutQueue(queue_s *q) {
    if (q->flag == 0 && q->front == q->rear) {
        printf("队空\r\n");
        return;
    }
    printf("chu队：%d\r\n", q->base[q->front]);

    q->front = (q->front + 1) % MAXSIZE;
    q->flag = 0;
}

void GetQueueFront(queue_s *q) {
    if ((q->flag == 0) && (q->front == q->rear)) {
        printf("--队空\r\n");
        return;
    }
    printf("--头值：%d\r\n", q->base[q->front]);
}

void GetQueueRear(queue_s *q) {
    if ((q->flag == 0) && (q->front == q->rear)) {
        printf("--队空\r\n");
        return;
    }
    if(q->rear == 0){
        printf("--尾值：%d\r\n",q->base[MAXSIZE-1]);
    }else {
        printf("--尾值：%d\r\n", q->base[q->rear-1]);
    }

}


int main() {
    queue_s *q = CreatQueue();
    InQueue(q, 3);
    InQueue(q, 6);
    GetQueueFront(q);
    InQueue(q, 9);
    InQueue(q, 12);
    OutQueue(q);
    InQueue(q, 2);
    GetQueueRear(q);
    InQueue(q, 4);
    InQueue(q, 5);

    OutQueue(q);
    OutQueue(q);
    OutQueue(q);
    GetQueueFront(q);
    GetQueueRear(q);
    OutQueue(q);
    OutQueue(q);
    OutQueue(q);
//
//    GetQueueFront(q);
//    GetQueueRear(q);
}



链式队列

完整代码

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
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    struct node_s *front;   // 队头
    struct node_s *rear;    // 队尾
} queue_s;  // 队列

typedef struct {
    int data;
    struct queue_s *next;
} node_s;

queue_s *CreatQueue() {
    queue_s *q = (queue_s *) malloc(sizeof(queue_s));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void push(queue_s *q, int data) {
    node_s *rear = (node_s *) q->rear;
    node_s *node = (node_s *) malloc(sizeof(node_s));
    node->data = data;
    node->next = NULL;
    if (q->front == NULL) {
        q->rear = (struct node_s *) node;
        q->front = (struct node_s *) node;
    } else {
        rear->next = (struct queue_s *) node;
        q->rear = (struct node_s *) node;
    }
    printf("push:%d\r\n", node->data);
}

void pop(queue_s *q) {

    if (q->front == NULL) {
        printf("栈空\r\n");
        return;
    }

    node_s *node = (node_s *) q->front;
    printf("出栈:%d\r\n", node->data);

    if (node->next == NULL) {
        q->front = NULL;
        q->rear = NULL;
    } else {
        q->front = (struct node_s *) node->next;
    }

    free(node);
}

int main() {
    queue_s *q = CreatQueue();
    push(q, 5);
    push(q, 6);
    push(q, 7);

    pop(q);
    pop(q);
    pop(q);
    pop(q);

    push(q, 7);
    push(q, 6);
    push(q, 5);

    pop(q);
    pop(q);
    pop(q);
    pop(q);
}