数据结构 - 链表

线性表的链式存储结构

概念

将线性表 L = (a₀, a₁, … , a_n-1)中各元素分布在存储器的不同存储块，成为结点，通过地址或指针建立元素之间的联系。

结点的 data 域存放数据元素 a_i ，而 next 域是一个指针，指向 a_i 的直接后继 a_i+1 所在的结点。

• 下图中的首元结点（头结点） A 的 data 不重要，next 域指向链表的真正的第一个结点，头结点的作用也是为了指明哪个结点是链表的第一个结点。

• 最后一个结点的 next 域，也就是下图中最后一个结点的那个 ^ 代表的是 NULL。

结点类型描述

typedef struct node
{data_t data; //结点的数据域struct node *next; //结点的后继指针域
}listnode, *linklist;

则有：

listnode A;
linklist p = &A;

结点声明

设 P 指向链表中结点 a_i

获取 a_i，写作：p->data
获取 a_i+1，写作：p->next->data

若指针 p 的值为 NULL，则它不指向任何结点，此时 p->data 或 p->next 是非法操作。

可调用 C 语言中 malloc() 函数向系统申请结点的存储空间：

linklist p;
p = (linklist)malloc(sizeof(listnode));

则创建一个类型为 linklist 的结点，且该结点的地址已存入指针变量 p 中。

建立单链表

• 目标：建立单链表
• 思路：
  1、给头结点分配空间然后判空
  2、初始化头结点（H->data，H->next）
  3、返回头结点
• 代码：

linklist list_create()
{linklist H; //头结点//分配空间并判空if ((H = (linklist)malloc(sizeof(listnode))) == NULL){printf("malloc H failed!\n");return NULL;}//初始化头结点H->data = 0;H->next = NULL;//返回头结点return H;
}

链表尾部插入节点

• 目标：向单链表的尾部插入新的节点
• 思路：
  1、建立新节点，给新节点分配空间并初始化
  2、定义指针指示插入节点的位置，这个位置的 next 为空，这样才能在 next 插入新节点，才能保证在链表的结尾插入节点 （从 H 开始，通过 q=q->next 遍历链表直到链表尾部）
  3、在指针的 next 插入新节点
• 代码：

int list_insert_tail(linklist H, data_t value)
{linklist p; //要插入的新节点 linklist q; //确定插入位置的指针//如果头结点为空那么以后的操作也没办法进行if (H == NULL){printf("H is NULL!\n");return -1;}//给新节点分配空间并判空if ((p = (linklist)malloc(sizeof(listnode))) == NULL){printf("malloc p failed!\n");return -1;}//初始化新节点p->data = 0;p->next = value;q = H;//确定插入节点的位置while (q->next){q = q->next;}//在链表尾部插入节点q->next = p;return 0;
}

根据下标查找节点

• 目标：根据位置获取链表中的节点
• 思路：
  1、判头结点是否为空，判下标是否合法；
  2、定义遍历链表的指针和 i 遍历链表直到找到指定位置（注意遍历完链表也没有找到指定节点的情况）；
  3、返回要查找的节点或空节点（未找到的情况）
• 代码：

linklist list_get(linklist H, int pos)
{linklist p; //遍历用指针int i; //遍历用标记if (H == NULL){printf("H is NULL!\n");return NULL;}if (pos < 0){printf("pos is invalid\n");return NULL;}p = H;i = -1;while (i < pos){p = p->next; //指针p向下移动//已经遍历完链表但没找到这个位置则breakif (p == NULL){break;}i++; //i迭代}return p;
}

在链表指定位置插入新节点

• 目标：给定链表、位置和新节点的值将这个新节点插入到链表的指定位置
• 思路：
  1、判头节点是否为空，位置是否合法（初步）
  2、通过指针和 i 遍历链表找到这个要插入节点的前一个节点的位置，让指针指向这个节点
  3、通过改变指针指向插入这个新节点
• 代码：

int list_insert_between(linklist H, data_t value, int pos)
{linklist p; //遍历用指针linklist q; //新节点int i;//如果头结点为空那么以后的操作也没办法进行if (H == NULL){printf("H is NULL!\n");return -1;}//这种位置无效if (pos < -1){printf("H is invalid!\n");return -1;}//给新节点分配空间并判空if ((q = (linklist)malloc(sizeof(listnode))) == NULL){printf("malloc p failed!\n");return -1;}//初始化新节点q->next = NULL;q->data = value;//p从头结点开始遍历p = H;while (i < pos - 1) //注意这里是 pos - 1,一定要在循环结束时让指针指向指定位置的前一个节点{p = p->next;//i还没到pos指针指向节点就空了，证明给定的位置无效if (p == NULL){printf("the pos not found!\n");return -1;}i++;}//此时指针指向指定位置的前一个节点,通过改变指针指向插入新节点q->next = p->next;p->next = q;return 0;
}	

打印链表

• 目标：打印链表节点
• 思路：通过指针遍历链表并打印
• 代码：

int list_show(linklist H) {linklist p;if (H == NULL) {printf("H is NULL\n");return -1;}p = H;while (p->next != NULL) {printf("%d ", p->next->data);p = p->next;}puts("");return 0;
}