线性表

线性表是由n（n≥0）个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每个元素都有唯一的直接前驱，除了最后一个元素外，每个元素都有唯一的直接后继。

前驱和后继

image-20200809182535992

顺序表

顺序表是顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，所以插入、删除时需要移动大量元素。

image-20200809182618326

链表

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻

单链表

image-20200809182952179

image-20200809183002675

添加操作

头插法

image-20200810154434529

尾插法

image-20200810154453060

中间添加

image-20200810155112050

删除操作

image-20200810155135267

数组实现

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

#define MAXSIZE 100

typedef struct LinkList {
  // 保存数据
  int data[MAXSIZE];
  // 保存数组长度
  int size;
} LinkList;

void printList(LinkList *L) {
  /* printf("size: %d ", L->size); */
  for (int i = 0; i < L->size; i ++) {
    printf("%d ", L->data[i]);
  }
  printf("\n");
}

// 头插 移动数组
void insertLinkListInHead(LinkList *L, int val) {
  // 所有数往后移动一位
  if(L->size > 0) {
    for(int i = L->size; i > 0; i --) {
      L->data[i] = L->data[i-1];
    }
  }
  // 第一位重新赋值
  L->data[0] = val;
  L->size++;
}

// 尾插
void insertLinkListInEnd(LinkList *L, int val) {
  L->data[L->size] = val;
  L->size ++;
}

// 在第i个位置插入
void insertLinkListInI(LinkList *L, int i, int val) {
  // 所有数往后移动一位
  if(i <= 0 || i > L->size) {
    printf("超出范围\n");
    return;
  }
  for(int j = L->size; j > i-1; j --) {
    L->data[j] = L->data[j-1];
  }
  // 第i个位置重新赋值
  L->data[i-1] = val;
  L->size ++;
}

// 删除第i个元素
void deleteListListInI(LinkList *L, int i) {
  // 直接进行覆盖
  if(i <= 0 || L->size == 0 || i > L->size) {
    printf("超出范围\n");
    return;
  }
  // 删除操作
  for(int j = i-1; j < L->size-1; j ++) {
    L->data[j] = L->data[j+1];
  }
  L->size --;
}

int main(int argc, char *argv[])
{
  LinkList list;
  list.size = 0;
  insertLinkListInHead(&list, 1);
  insertLinkListInHead(&list, 2);
  insertLinkListInHead(&list, 3);
  insertLinkListInHead(&list, 4);
  printList(&list);
  insertLinkListInEnd(&list, 1);
  insertLinkListInEnd(&list, 2);
  insertLinkListInEnd(&list, 3);
  insertLinkListInEnd(&list, 4);
  printList(&list);
  insertLinkListInI(&list, 2, 10);
  insertLinkListInI(&list, 3, 13);
  printList(&list);
  deleteListListInI(&list, 1);
  deleteListListInI(&list, 1);
  deleteListListInI(&list, 5);
  printList(&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
#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
  int val;
  struct LNode *next;
} LNode, *LinkList;

LinkList initialList() {
  LinkList L = (LinkList) malloc(sizeof(LinkList));
  if(!L) return NULL;
  L->next = NULL;
  return L;
}

// 头部插入元素
void insertListInHead(LinkList L, int val) {
  LinkList elem = (LinkList) malloc(sizeof(LinkList));
  elem->val = val;
  elem->next = L->next;
  L->next = elem;
}

// 尾部插入
void insertListInEnd(LinkList L, int val) {
  LinkList p = L;
  while(p->next) {
    p = p->next;
  }
  LinkList elem = (LinkList) malloc(sizeof(LinkList));
  elem->val = val;
  p->next = elem;
}

// 在i处增加
void insertListInI(LinkList L, int i, int val) {
  int j = 0;
  LinkList p = L;
  while(p && j < i-1) {
    p = p->next;
    j ++;
  }
  if(!p || j > i-1) {
    printf("超出范围\n");
    return;
  }
  LinkList elem = (LinkList) malloc(sizeof(LinkList));
  elem->val = val;
  elem->next = p->next;
  p->next = elem;
}

// 删除第i个
void deleteListInI(LinkList L, int i) {
  LinkList p = L;
  int j = 0;
  while(p && j < i-1) {
    p = p->next;
    j ++;
  }
  // p->next 为要删除的
  if(!p->next || j > i-1) {
    printf("超出范围\n");
  }
  LinkList q = p->next;
  p->next = q->next;
  free(q);
}

// 打印链表
void printList(LinkList L) {
  // 头节点没有数据
  LinkList p = L->next;
  while(p) {
    printf("%d \t", p->val);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  LinkList L = initialList();
  insertListInHead(L, 1);
  insertListInHead(L, 2);
  insertListInHead(L, 3);
  insertListInHead(L, 4);
  printList(L);
  insertListInEnd(L, 1);
  insertListInEnd(L, 2);
  insertListInEnd(L, 3);
  insertListInEnd(L, 4);
  printList(L);
  insertListInI(L, 2, 10);
  printList(L);
  deleteListInI(L, 1);
  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
#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
  int val;
  struct LNode *next;
} LNode, *LinkList;

LinkList initialList() {
  LinkList L = (LinkList) malloc(sizeof(LinkList));
  if(!L) return NULL;
  L->next = NULL;
  return L;
}

// 尾部插入
void insertListInEnd(LinkList L, int val) {
  LinkList p = L;
  while(p->next) {
    p = p->next;
  }
  LinkList elem = (LinkList) malloc(sizeof(LinkList));
  elem->val = val;
  p->next = elem;
}

//合并链表
LinkList mergeList(LinkList L1, LinkList L2) {
  LinkList p = L1->next;
  LinkList q = L2->next;
  // 结果
  LinkList r = L1;
  LinkList res = r;

  while(p && q) {
    if(p->val < q->val) {
      res->next = p;
      res = p;
      p = p->next;
    } else {
      res->next = q;
      res = q;
      q = q->next;
    }
  }
  res->next = q?q:p;
  free(L2);
  return r;
}

// 打印链表
void printList(LinkList L) {
  // 头节点没有数据
  LinkList p = L->next;
  while(p) {
    printf("%d \t", p->val);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  LinkList L1 = initialList();
  insertListInEnd(L1, 1);
  insertListInEnd(L1, 3);
  insertListInEnd(L1, 7);
  insertListInEnd(L1, 9);
  printList(L1);
  LinkList L2 = initialList();
  insertListInEnd(L2, 0);
  insertListInEnd(L2, 1);
  insertListInEnd(L2, 2);
  insertListInEnd(L2, 4);
  insertListInEnd(L2, 10);
  insertListInEnd(L2, 11);
  printList(L2);
  LinkList L3 = mergeList(L1, L2);
  printList(L3);
  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
#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
  int val;
  struct LNode *next;
} LNode, *LinkList;

LinkList initialList() {
  LinkList L = (LinkList) malloc(sizeof(LinkList));
  if(!L) return NULL;
  L->next = NULL;
  return L;
}

// 尾部插入
void insertListInEnd(LinkList L, int val) {
  LinkList p = L;
  while(p->next) {
    p = p->next;
  }
  LinkList elem = (LinkList) malloc(sizeof(LinkList));
  elem->val = val;
  p->next = elem;
}

// 找出中间元素 快慢指针
LinkList findMiddle(LinkList L) {
  LinkList p = L;
  LinkList q = L;
  while(p && p->next) {
    p = p->next->next;
    q = q->next;
  }
  return q;
}

// 打印链表
void printList(LinkList L) {
  // 头节点没有数据
  LinkList p = L->next;
  while(p) {
    printf("%d \t", p->val);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  LinkList L = initialList();
  insertListInEnd(L, 1);
  insertListInEnd(L, 2);
  insertListInEnd(L, 3);
  insertListInEnd(L, 4);
  insertListInEnd(L, 5);
  printList(L);
  LinkList el = findMiddle(L);
  printf("middle element is %d\n", el->val);
  return 0;
}

双链表

image-20200810154824675

添加操作

image-20200810154914081

删除操作

image-20200810154929003