链表与模拟链表

刺骨的言语ヽ痛彻心扉 2022-09-11 15:20 231阅读 0赞

## 链表中的每一个结点应该如何存储？ ##

*  每个节点都由两个部分组成。左边的部分用来存放具体的数值，那么用一个整型变量就可以；右边的部分需要存储下一个节点的地址，可以用指针来实现（也称为后继指针）。
 *  这里我们定义一个结构体类型来存储这个节点。

struct node{ 
        int data;
        struct node *next;
    };

上面的代码中，我们定义了一个叫做 node 的结构体类型，这个结构体类型有两个成员。

*  第一个成员是整型 data ，用来存储具体的数值；
 *  第二个成员是一个指针，用来存储下一个节点的地址。
 *  因为下一个结点的类型也是 struct node ，所以这个指针的类型也必须是 struct node \* 类型的指针。

--------------------

## 如何建立链表呢？ ##

首先，我们需要一个头指针 head 指向链表的最开始。  
当链表还没有建立的时候头指针 head 为空（也可以理解为指向头结点）。

struct node *head;
    head = NULL;
    //头指针初始为空

现在我们来创建第一个结点，并用临时指针 p 指向这个结点。

struct node *p;
    p = (struct node *)malloc(sizeof(struct node));

接下来分别设置新创建的这个结点的左半部分和右半部分。

scanf("%d", &a);
       p->data = a;
       p->next = NULL;

上面的代码中我们发现了一个很奇怪的符号 “->” 。-> 叫做结构体指针运算符，也是用来访问结构体内部成员的。`因为此处 p 是一个指针，所以不能使用 . 号访问内部成员，而要用 ->`。  
下面来设置头指针并设置新创建的结点的 \* next 指向空。头指针的作用是方便以后从头遍历整个链表。

if(head=NULL)
           head = p;
           //如果这是第一个创建的结点，则将头指针指向这个结点
           else
               q->next = p;
               //如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点

最后要将指针 q 也指向当前结点，因为待会儿临时指针 p 将会指向新创建的结点。

q = p;  // 指针q也指向当前结点

完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    struct node{ 
        int data;
        struct node *next;
    };
    
    int main(){ 
        struct node *head,*p,*q,*t;
        int i, n, a;
        scanf("%d", &n);
        head = NULL;
        for (i = 1; i <= n;i++){ 
            scanf("%d", &a);
            p = (struct node *)malloc(sizeof(struct node));
            p->data = a;
            p->next = NULL;
            if(head==NULL)
                head = p;
                else
                    q->next = p;
                q = p;
        }
        t = head;
        while(t!=NULL){ 
            printf("%d", t->data);
            t = t->next;
        }
        getchar();
        getchar();
        return 0;
    }

发现这样的定义不是很简洁！  
对比下面的代码！

*  容易发现，这里 `struct` 前多了 `typedef` ，这是为了方便定义附加的！  
    需要说明的一点是：上面的这段代码没有释放动态申请的空间，虽然这样会很不安全，有兴趣的朋友可以去用 free 命令。

## 接下来需要往链表中插入a。 ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node{ 
        int data;
        struct node *next;
    } Lnode ,*Linklist;
    
    int main(){ 
        Linklist head, q, p, t;
        int i, n, a;
        scanf("%d", &n);
        head = NULL;
        for (i = 1; i <= n;i++){ 
            scanf("%d", &a);
            p = (Linklist)malloc(sizeof(Lnode));
            p->data = a;
            p->next = NULL;
            if(head==NULL)
                head = p;
                else
                    q->next = p;
                q = p;
        }
        t = head;
        scanf("%d", &a);
        while(t!=NULL){ 
            if(t->next->data>a){ 
                p = (Linklist)malloc(sizeof(Lnode));
                p->data = a;
                p->next = t->next;
                t->next = p;
                break;
            }
            t = t->next;
        }
        t = head;
        while(t!=NULL){ 
            printf("%d", t->data);
            t = t->next;
        }
        getchar();
        getchar();
        return 0;
    }

--------------------

## 动态存储方法 ##

malloc 函数的作用是从内存中申请分配指定字节大小的内存空间。

*  需要注意，malloc 函数的返回类型是 void \* 类型。
 *  void \* 表示未确定类型的指针。
 *  注意当在程序中使用 malloc 函数时需要用到 stdlib.h 头文件。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    int main(){ 
    	int *p;
    	p = (int *)malloc(sizeof(int));
    	*p = 10;
    	printf("%d", *p);
    	getchar();
    	getchar();
    	return 0;
    }

运行结果是：

> 10

--------------------

## 模拟链表 ##

*  用整型数组 data 存放序列中具体数字
 *  用另外一个整型数组 right 存放当前序列中每一个元素右边的元素在数组 data 中的位置。

完整代码如下：

#include <stdio.h>
    int main(){ 
        int data[101], right[101];
        int i, n, t, len;
        scanf("%d", &n);
        for (i = 1; i <= n;i++)
            scanf("%d", &data[i]);
        len = n;
        for (i = 1; i <= n;i++){ 
            if(i!=n)
                right[i] = i + 1;
                else
                    right[i] = 0;
        }
        len++;
        scanf("%d", &data[len]);
        t = 1;
        while(t!=0){ 
            if(data[right[t]]>data[len]){ 
                //如果当前结点下一个结点的值大于待插入数，将数插入到中间
                right[len] = right[t];
                //新插入数的下一个结点标号等于当前结点的下一个结点编号
                right[t] = len;
                //当前结点的下一个结点编号就是新插入数的编号
                break;
                //插入完成跳出循环
            }
            t = right[t];
        }
        t = 1;
        while(t!=0){ 
            printf("%d", data[t]);
            t = right[t];
        }
        getchar();
        getchar();
        return 0;
    }

--------------------