C语言基础系列（三）——链表

C语言基础系列（三）——链表

1.链表的定义

链表是一些包含数据的独立结构体（被称为节点）的集合。

1.1 单链表

在单链表中，每个节点包含一个指向链表下一节点的指针，示意图如下：

定义的节点结构体声明如下：

typedef struct NODE {
    int 	val;
    struct NODE *next;
} Node;

1.链表的初始化

链表初始化过程：

• 申请一个头节点
• 将其他的节点一直添加至next

//create link_list, return header pointer
//该函数返回了头节点
Node *init_Link(void)
{
    Node *p = (Node *)malloc(sizeof(Node));
    Node *temp = p;

    int i = 0;
    for (i = 0; i< 5; i++)
    {
		Node *a = (Node *)malloc(sizeof(Node));
		a->val = i;
		a->next = NULL;
	
		temp->next = a;
		temp = temp->next;
    }

    return p;
}

2.链表的插入

插入链表的步骤：
1.将新结点的 next 指针指向插入位置后的结点；
2.将插入位置前结点的 next 指针指向插入结点；

/*
 * args: p: header pointer, val: insert number, add: the place want to insert
 * 该函数实现将新结点插入到自己所设定的地方
 */
Node *insert_val(Node *p, int val, int place)
{
    Node *temp = p;
    //judge the place is legal or not
    int i = 0;
    for (i = 1; i < place; i++)
    {
		if (temp == NULL)
		{
		    printf("illegal place insert!\n");
		    return p;
		}
		temp = temp->next;
    }

    Node *c = (Node *)malloc(sizeof(Node));
    c->val = val;

    c->next = temp->next;
    temp->next = c;

    return p;
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>


typedef struct NODE {
    int 	val;
    struct NODE *next;
} Node;

//create link_list, return header pointer
Node *init_Link(void)
{
    Node *p = (Node *)malloc(sizeof(Node));
    Node *temp = p;

    int i = 0;
    for (i = 0; i< 5; i++)
    {
	Node *a = (Node *)malloc(sizeof(Node));
	a->val = i;
	a->next = NULL;

	temp->next = a;
	temp = temp->next;
    }

    return p;
}

//arg: the header pointer
void display(Node *p)
{
    Node *temp = p->next;

    while(temp->next != NULL)
    {
	printf("%d ", temp->val);
	temp = temp->next;
    }
    printf("\n");
}

/*
 * args: p: header pointer, val: insert number, add: the place want to insert
 *
 */
Node *insert_val(Node *p, int val, int place)
{
    Node *temp = p;
    //judge the place is legal or not
    int i = 0;
    for (i = 1; i < place; i++)
    {
	if (temp == NULL)
	{
	    printf("illegal place insert!\n");
	    return p;
	}
	temp = temp->next;
    }

    Node *c = (Node *)malloc(sizeof(Node));
    c->val = val;

    c->next = temp->next;
    temp->next = c;

    return p;
}

int main(void)
{
    Node *p = NULL;
    p = init_Link();
    display(p);

    insert_val(p, 6, 1);
    display(p);
    return 0;
}

参考资料

1.2 双链表

双向链表，简称双链表。从名字上理解双向链表，即链表是 “双向” 的
结构体的定义如下：

typedef struct NODE {
    struct NODE *prior;   //前一个节点
    int 	val;
    struct NODE *next;    //后一个节点
} Node;

#include <stdio.h>
#include <stdlib.h>
//节点结构
typedef struct line {
    struct line * prior;
    int data;
    struct line * next;
}line;
//双链表的创建函数
line* initLine(line * head);
//输出双链表的函数
void display(line * head);

int main() {
    //创建一个头指针
    line * head = NULL;
    //调用链表创建函数
    head = initLine(head);
    //输出创建好的链表
    display(head);
    //显示双链表的优点
    printf("链表中第 4 个节点的直接前驱是：%d", head->next->next->next->prior->data);
    return 0;
}
line* initLine(line * head) {
    int i = 0;
    line * list = NULL;
    //创建一个首元节点，链表的头指针为head
    head = (line*)malloc(sizeof(line));
    //对节点进行初始化
    head->prior = NULL;
    head->next = NULL;
    head->data = 1;
    //声明一个指向首元节点的指针，方便后期向链表中添加新创建的节点
    list = head;
    for (i = 2; i <= 5; i++) {
        //创建新的节点并初始化
        line * body = (line*)malloc(sizeof(line));
        body->prior = NULL;
        body->next = NULL;
        body->data = i;

        //新节点与链表最后一个节点建立关系
        list->next = body;
        body->prior = list;
        //list永远指向链表中最后一个节点
        list = list->next;
    }
    //返回新创建的链表
    return head;
}
void display(line * head) {
    line * temp = head;
    while (temp) {
        //如果该节点无后继节点，说明此节点是链表的最后一个节点
        if (temp->next == NULL) {
            printf("%d\n", temp->data);
        }
        else {
            printf("%d <-> ", temp->data);
        }
        temp = temp->next;
    }
}