线性表的链式存储结构：定义、单链表存储结构、给链表头结点分配空间、初始化链表数据、输出链表、在某个位置上插入数据、头插法、尾插法、删除某个位置上的数据、删除某个数据、删除整个链表计算链表的长度

1、线性表链式存储结构定义 1.1特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 1.2为了表示每个数据ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们吧存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。 1.3链表中第一个结点的存储位置叫做头指针；线性表的最后一个结点指针为空（通常用符号NULL或“^”表示）。 1.4在单链表的第一个结点前附设一个结点，称为头结点。

2、头指针与头结点的异同 2.1头指针 （1）头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针； （2）头指针具有标识作用，所以常用头指针冠以链表的名字； （3）无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 2.2头结点 （1）头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可以存放链表的长度）； （2）有了头结点，对在第一个元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了； （3）头结点不一定是链表必须要素。

3、功能实现代码 （1）线性表的单链表存储结构

typedef struct Node {/*线性表的单链表存储结构*/ ElenType data; struct Node *next; }Node; typedef struct Node *LinkList;/*定义指针*/

（2）线性表的初始化：分配空间 L为二级指针，通过此操作来给头结点分配空间。

void Initialize(LinkList *L) {/*初始化链表指针：分配空间*/ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; }

（3）输出链表中的数据 A. P指向头结点之后的存储数据的结点p = L->next; B. 判断头结点的下一个结点是否为空，若为空则输出“链表为空！”的信息； C. 若不为空，则遍历输出数据，printf("%d ", p->data); p = p->next;直到结点为空时退出循环。

void Display(LinkList L) {/*输出链表中的数据*/ LinkList p = L->next; if (!p) printf("链表为空！\n"); else { while (p) { printf("%d ", p->data); p = p->next; } putchar('\n'); } }

（4）初始化链表：输入初始化的数据 A. P指向链表头结点L ，p = L; B. 输入需要创建的数据个数； C. 给结点q分配空间q = (LinkList)malloc(sizeof(Node)); D. 输入数据，然后结点p的指针指向结点q，结点p再更新指向结点q，p->next = q; p = p->next; E. 循环创建结点，直到j>i时退出循环； F. 将最后一个结点的指针置空p->next = NULL;

void create(LinkList L) {/*初始化链表：输入初始化的数据*/ int i,j=1; LinkList p, q; p = L; printf("请输入需要初始化的数据个数："); scanf_s("%d", &i); while (j <= i) { q = (LinkList)malloc(sizeof(Node)); printf("请输入第%d个数据：",j); scanf_s("%d", &q->data); p->next = q; p = p->next; j++; } p->next = NULL; }

（5）插入数据：在某个位置插入数据 A. 指针p指向链表头结点，p = L; B. 遍历寻找需要插入位置的前一个位置p = p->next;，当查找到该位置或者不存在该位置时退出循环； C. 如果插入位置之前的位置为空或者不存在该位置，则返回ERROR； D. 否则给结点q分配空间，输入数据，q = (LinkList)malloc(sizeof(Node)); q->data = e; E. 将结点q的指针置指向插入位置的那一个结点q->next = p->next;使得结点q取代这一个位置； F. 插入位置前一个结点的指针指向结点q，p->next = q;

int InsertionLocation(LinkList L, int i,ElenType e) {/*插入数据：在某个位置插入数据*/ int j=1; LinkList q, p; p = L; while (p&&j < i) {/*寻找需要插入的位置*/ p = p->next; ++j; } if (!p || j > i) return ERROR; q = (LinkList)malloc(sizeof(Node)); q->data = e; q->next = p->next; p->next = q; return OK; }

（6）插入数据：头插法 A. 指针p指向链表头结点L； B. 创建新的结点q = (LinkList)malloc(sizeof(Node)); C. 将插入数据赋予新的结点q->data = e; D. 新结点的指针指向头结点之后的第一个结点q->next = p->next; E. 头结点指向新的结点p->next = q;

void InsertionHead(LinkList L,ElenType e) {/*插入数据：头插法*/ LinkList p = L, q; q = (LinkList)malloc(sizeof(Node)); q->data = e; q->next = p->next; p->next = q; }

（7）插入数据：尾插法 A. 指针p指向链表头结点L； B. 遍历结点p的下一个结点是否为空p = p->next;当为空时退出循环； C. 创建新的结点q = (LinkList)malloc(sizeof(Node)); D. 将插入数据赋予新的结点q->data = e; E. 将q的指针置空q->next = NULL; F. 最后一个结点的指针指向新节点q，p->next = q;

void InsertionTail(LinkList L, ElenType e) {/*插入数据：尾插法*/ LinkList p=L, q; while (p->next) p = p->next; q = (LinkList)malloc(sizeof(Node)); q->data = e; q->next = NULL; p->next = q; }

（8）删除数据：删除某个位置上的数据 A. 指针p指向链表头结点L； B. 遍历寻找需要删除的结点之前的那个结点p = p->next;直到找到该结点或者不存在这个结点时退出循环； C. 如果不存在删除节点则返回ERROR； D. 否则，结点q指向待删除的结点q = p->next; E. 待删除结点前面的结点的指针指向待删除结点后面的那一个结点p->next = q->next; F. 释放待删除结点的空间free(q);

int DeleteLocation(LinkList *L, int i) {/*删除某个位置上的数据*/ LinkList q, p = *L; int j = 1; while (j++ < i && p) p = p->next; if (j > i + 1 || !p) return ERROR; q = p->next; p->next = q->next; free(q); return OK; }

（9）删除数据：删除某个数据——方式一

int DeleteDataOne(LinkList L, ElenType e) {/*删除某个数据*/ LinkList p=L , q; while (p->next) {/*结点不为空则运行*/ if (p->next->data == e) {/*判断下一个结点是否符合要求*/ q = p->next;/*q继承下一个符合要求的结点*/ p->next = q->next;/*p指向下下个结点*/ free(q);/*释放q的空间*/ return OK; } p = p->next;/*若没有查找到符合要求结点，则结点后移*/ } printf("不存在该数据！\n"); return ERROR; }

（9）删除数据：删除某个数据——方式二

int DeleteDataTwo(LinkList L, ElenType e) {/*删除某个数据*/ LinkList p = L, q = L->next; while (q) { if (q->data == e) { p->next = q->next; free(q); return OK; } p = q; q = q->next; } printf("不存在该数据！\n"); return ERROR; }

（10）删除整个链表

int ClearList(LinkList *L) {/*删除整个链表*/ LinkList p, q; p = (*L)->next; while (p) { q = p->next; free(p); p = q; } (*L)->next = NULL; return OK; }

（11）计算链表的长度

int Length(LinkList L) {/*计算链表的长度*/ LinkList p = L; int length = 0;; while (p->next) { length++; p = p->next; } return length; }

（12）完整测试代码（编译环境Visual Studio 2017）

#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 typedef int ElenType;/*线性表中存储的数据类型*/ typedef struct Node {/*线性表的单链表存储结构*/ ElenType data; struct Node *next; }Node; typedef struct Node *LinkList;/*定义指针*/ void Initialize(LinkList *L) {/*初始化链表指针：分配空间*/ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; } void Display(LinkList L) {/*输出链表中的数据*/ LinkList p = L->next; if (!p) printf("链表为空！\n"); else { while (p) { printf("%d ", p->data); p = p->next; } putchar('\n'); } } void create(LinkList L) {/*初始化链表：输入初始化的数据*/ int i,j=1; LinkList p, q; p = L; printf("请输入需要初始化的数据个数："); scanf_s("%d", &i); while (j <= i) { q = (LinkList)malloc(sizeof(Node)); printf("请输入第%d个数据：",j); scanf_s("%d", &q->data); p->next = q; p = p->next; j++; } p->next = NULL; } int InsertionLocation(LinkList L, int i,ElenType e) {/*插入数据：在某个位置插入数据*/ int j=1; LinkList q, p; p = L; while (p&&j < i) {/*寻找需要插入的位置*/ p = p->next; ++j; } if (!p || j > i) return ERROR; q = (LinkList)malloc(sizeof(Node)); q->data = e; q->next = p->next; p->next = q; return OK; } void InsertionHead(LinkList L,ElenType e) {/*插入数据：头插法*/ LinkList p = L, q; q = (LinkList)malloc(sizeof(Node)); q->data = e; q->next = p->next; p->next = q; } void InsertionTail(LinkList L, ElenType e) {/*插入数据：尾插法*/ LinkList p=L, q; while (p->next) p = p->next; q = (LinkList)malloc(sizeof(Node)); q->data = e; q->next = NULL; p->next = q; } void InsertionMenu(LinkList L) {/*插入数据菜单*/ int i, j,e; printf("请选择插入数据的方式：1、在某个位置插入数据\t2、头插法\t3：尾插法\n请选择："); scanf_s("%d", &i); switch (i) { case 1: printf("请输入插入的位置："); scanf_s("%d", &j); printf("请输入插入的数据："); scanf_s("%d", &e); InsertionLocation(L, j, e); break; case 2: printf("请输入插入的数据："); scanf_s("%d", &e); InsertionHead(L, e); break; case 3: printf("请输入插入的数据："); scanf_s("%d", &e); InsertionTail(L, e); break; default: printf("不存在该功能选项！\n"); break; } printf("插入数据后的链表中的数据为："); Display(L); } int DeleteLocation(LinkList *L, int i) {/*删除某个位置上的数据*/ LinkList q, p = *L; int j = 1; while (j++ < i && p) p = p->next; if (j > i + 1 || !p) return ERROR; q = p->next; p->next = q->next; free(q); return OK; } int DeleteDataOne(LinkList L, ElenType e) {/*删除某个数据*/ LinkList p=L , q; while (p->next) {/*结点不为空则运行*/ if (p->next->data == e) {/*判断下一个结点是否符合要求*/ q = p->next;/*q继承下一个符合要求的结点*/ p->next = q->next;/*p指向下下个结点*/ free(q);/*释放q的空间*/ return OK; } p = p->next;/*若没有查找到符合要求结点，则结点后移*/ } printf("不存在该数据！\n"); return ERROR; } int DeleteDataTwo(LinkList L, ElenType e) {/*删除某个数据*/ LinkList p = L, q = L->next; while (q) { if (q->data == e) { p->next = q->next; free(q); return OK; } p = q; q = q->next; } printf("不存在该数据！\n"); return ERROR; } void DeleteMenu(LinkList L) {/*删除结点菜单*/ int i,j; printf("请选择删除结点的方式：1、删除某个位置上的数据\t2：删除某个数据—方式一\t3：删除某个数据—方式二\n请选择："); scanf_s("%d", &i); switch (i) { case 1: printf("请输入删除的位置："); scanf_s("%d", &j); DeleteLocation(&L, j); break; case 2: printf("请输入删除的数据："); scanf_s("%d", &j); DeleteDataOne(L, j); break; case 3: printf("请输入删除的数据："); scanf_s("%d", &j); DeleteDataTwo(L, j); break; default: printf("不存在该功能选项！\n"); break; } printf("删除数据后的链表中的数据为："); Display(L); } int ClearList(LinkList *L) {/*删除整个链表*/ LinkList p, q; p = (*L)->next; while (p) { q = p->next; free(p); p = q; } (*L)->next = NULL; return OK; } int Length(LinkList L) {/*计算链表的长度*/ LinkList p = L; int length = 0;; while (p->next) { length++; p = p->next; } return length; } void menu() {/*程序菜单*/ printf("程序的功能菜单：\n0：菜单\n1：创建链表\n2：插入数据\n3：删除结点\n4：单链表的整表删除\n5：计算链表的长度\n6：退出程序\n"); } int main(void) { int i = 0; LinkList L; while (i != 6) { switch (i) { case 0: menu(); break; case 1: Initialize(&L); create(L); printf("链表中的数据为："); Display(L); break; case 2: InsertionMenu(L); break; case 3: DeleteMenu(L); break; case 4: ClearList(&L); Display(L); break; case 5: printf("链表的长度为：%d\n", Length(L)); break; default: printf("不存在该功能选项！\n"); break; } printf("请输入需要执行的选项："); scanf_s("%d", &i); } printf("感谢您的使用！\n"); return 0; }

运行结果图：