链表

---

• 2021-07-14 09:54:08

  来填坑了。 链表是如何实现的呢？如下。

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 //创建一个结构体用来表示链表的结点类型
   5 struct node {
   6     int data;
   7     struct node *next;
   8 };
   9 
  10 int main() {
  11     struct node *head, *p, *q, *t;
  12     int n, a;
  13     scanf("%d", &n);
  14     head = NULL; //头指针初始为空
  15     for (int i = 1; i <= n; i++) { //循环读入n个数
  16         scanf("%d", &a);
  17         //动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
  18         p = (struct node *)malloc(sizeof(struct node));
  19         p->data = a; //将数据存储到当前结点的data域中
  20         p->next = NULL; //设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
  21         if (head == NULL)
  22             head = p; //如果这是第一个创建的结点，则将头指针指向这个结点
  23         else
  24             q->next = p; //如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
  25 
  26         q = p; //指针q也指向当前结点
  27     }
  28 
  29     //输出链表中的所有数
  30     t = head;
  31     while (t != NULL) {
  32         printf("%d ", t->data);
  33         t = t->next; //继续下一个结点
  34     }
  35 
  36     return 0;
  37 }

　！！注意：上面这段代码没有释放动态申请的空间，虽然没有错误，但是很不安全。我以后再来了解一下free命令。

• 接下来，我们再往一个升序链表中插入一个数。

  请看第29至第40行。

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 // 这里创建一个结构体用来表示链表的结点类型
   5 struct node {
   6     int data;
   7     struct node *next;
   8 };
   9 
  10 int main() {
  11     struct node *head, *p, *q, *t;
  12     int n, a;
  13     scanf("%d", &n);
  14     head = NULL; // 头指针初始为空
  15     for (int i = 1; i <= n; i++) { // 循环读入n个数
  16         scanf("%d", &a);
  17         // 动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
  18         p = (struct node *)malloc(sizeof(struct node));
  19         p->data = a; // 将数据存储到当前结点的data域中
  20         p->next = NULL; // 设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
  21         if (head == NULL)
  22             head = p; // 如果这是第一个创建的结点，则将头指针指向这个结点
  23         else
  24             q->next = p; // 如果不是第一个创建的结点，则将上一个结点的后继指针指向这个结点
  25 
  26         q = p; // 指针q也指向当前结点
  27     }
  28 
  29     scanf("%d", &a); // 读入待插入的数
  30     t = head; // 从链表头部开始遍历
  31     while (t != NULL) { // 当没有到达链表尾部时，循环
  32         if (t->next->data > a) { // 如果当前结点的下一个结点的值大于待插入数，将数插入到中间
  33             p = (struct node *)malloc(sizeof(struct node)); // 动态申请一个空间，用来存放新增结点
  34             p->data = a;
  35             p->next = t->next; // 新增结点的后继指针指向当前结点的后继指针所指向的结点
  36             t->next = p; // 当前结点的后继指针指向新增结点
  37             break; // 插入完毕退出循环
  38         }
  39         t = t->next; // 继续下一个结点
  40     }
  41 
  42     // 输出链表中的所有数
  43     t = head;
  44     while (t != NULL) {
  45         printf("%d ", t->data);
  46         t = t->next; // 继续下一个结点
  47     }
  48 
  49     return 0;
  50 }

---

• 模拟链表 - 不使用指针实现

   1 //在升序的排列中插入一个数
   2 
   3 #include <stdio.h>
   4 
   5 int main() {
   6     int data[101], right[101];
   7     int n, t, len;
   8     //读入已有的数
   9     scanf("%d", &n);
  10     for (int i = 1; i <= n; i++)
  11         scanf("%d", &data[i]);
  12     len = n;
  13 
  14     //初始化数组right
  15     for (int i = 1; i <= n; i++) {
  16         if (i != n)
  17             right[i] = i+1;
  18         else
  19             right[i] = 0;
  20     }
  21 
  22     //直接在数组data的末尾增加一个数
  23     len++;
  24     scanf("%d", &data[len]);
  25 
  26     //从链表的头部开始遍历
  27     t = 1;
  28     while (t != 0) {
  29         if (data[right[t] > data[len]) { //如果当前结点下一个结点的值大于待插入数，将数插入到中间
  30             right[len] = right[t]; //新插入数的下一个结点编号等于当前结点的下一个结点编号
  31             right[t] = len; //当前结点的下一个结点编号就是新插入数的编号
  32             break; //插入完成跳出循环
  33         }
  34         t = right[t];
  35     }
  36 
  37     //输出链表中所有的数
  38     t = 1;
  39     while (t != 0) {
  40         printf("%d ", data[t]);
  41         t = right[t];
  42     }
  43     return 0;
  44 }