跳至正文
View Categories

1 min read

主要内容 #

  1. 链表的创建
  2. 链表的使用

1. 链表的创建 #

创建一个链表，实现步骤如下：

  1. 定义一个头指针；
  2. 创建一个头结点或者首元结点，让头指针指向它；
  3. 每创建一个结点，都令其直接前驱结点的指针指向它。

例如，创建一个存储 {1,2,3,4} 且无头节点的链表，C 语言实现代码为：

Link* initLink() {
    int i;
    //1、创建头指针
    Link* p = NULL;
    //2、创建首元结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 1;
    temp->next = NULL;
    //头指针指向首元结点
    p = temp;
    //3、每创建一个结点，都令其直接前驱结点的指针指向它
    for (i = 2; i < 5; i++) {
        //创建一个结点
        Link* a = (Link*)malloc(sizeof(Link));
        a->elem = i;
        a->next = NULL;
        //每次 temp 指向的结点就是 a 的直接前驱结点
        temp->next = a;
        //temp指向下一个结点（也就是a),为下次添加结点做准备
        temp = temp->next;
    }
    return p;
}

再比如，创建一个存储 {1,2,3,4} 且含头节点的链表，则 C 语言实现代码为：

Link* initLink() {
    int i;
    //1、创建头指针
    Link* p = NULL;
    //2、创建头结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 0;
    temp->next = NULL;
    //头指针指向头结点
    p = temp;
    //3、每创建一个结点，都令其直接前驱结点的指针指向它
    for (i = 1; i < 5; i++) {
        //创建一个结点
        Link* a = (Link*)malloc(sizeof(Link));
        a->elem = i;
        a->next = NULL;
        //每次 temp 指向的结点就是 a 的直接前驱结点
        temp->next = a;
        //temp指向下一个结点（也就是a),为下次添加结点做准备
        temp = temp->next;
    }
    return p;
}

2. 链表的使用 #

对于创建好的链表，我们可以依次获取链表中存储的数据，例如：

#include <stdio.h>
#include <stdlib.h>
//链表中节点的结构
typedef struct link {
    int  elem;
    struct link* next;
}Link;
Link* initLink() {
    int i;
    //1、创建头指针
    Link* p = NULL;
    //2、创建头结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 0;
    temp->next = NULL;
    //头指针指向头结点
    p = temp;
    //3、每创建一个结点，都令其直接前驱结点的指针指向它
    for (i = 1; i < 5; i++) {
        //创建一个结点
        Link* a = (Link*)malloc(sizeof(Link));
        a->elem = i;
        a->next = NULL;
        //每次 temp 指向的结点就是 a 的直接前驱结点
        temp->next = a;
        //temp指向下一个结点（也就是a),为下次添加结点做准备
        temp = temp->next;
    }
    return p;
}
void display(Link* p) {
    Link* temp = p;//temp指针用来遍历链表
    //只要temp指向结点的next值不是NULL，就执行输出语句。
    while (temp) {
        Link* f = temp;//准备释放链表中的结点
        printf("%d ", temp->elem);
        temp = temp->next;
        free(f);
    }
    printf("\n");
}
int main() {
    Link* p = NULL;
    printf("初始化链表为：\n");
    //创建链表{1,2,3,4}
    p = initLink();
    //输出链表中的数据
    display(p);
    return 0;
}

程序中创建的是带头结点的链表，头结点的数据域存储的是元素 0，因此最终的输出结果为：
0 1 2 3 4
如果不想输出头结点的值，可以将 p->next 作为实参传递给 display() 函数。
如果程序中创建的是不带头结点的链表，最终的输出结果应该是：
1 2 3 4

What are your Feelings