链表——删除元素或插入元素（头插法及尾插法）

目录

链表的结点由一个结构体构成

判断链表是否为空

键盘输入链表中的数据

输出链表中的数据

返回链表的元素个数

清空链表

 返回指定位置的元素值

查找数据所在位置

删除链表的元素

插入元素

建立无头结点的单链表

建立有头结点的单链表（头插法）

建立有头节点的单链表（尾插法）

总代码如下：

---

链表：

是一种在存储单元上非连续，非顺序的存储结构，由一系列结点组成，结点可以在运行的过程中动态生成，每个结点包括两部分：存储数据的数据域；存储下一节点地址的指针域。

对指针的理解：

将某个变量（例如 int a）赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

链表的结点由一个结构体构成

struct node
{int data;//数据域struct node *next;//指针域
};

判断链表是否为空

如果链表头结点的指针域不为空，如果定义链表头结点是 struct node *L，也就是 L->next !=NULL.

(因为在有头结点的链表中，头结点数据域中不存储数据，它的指针域存放的是链表第一个元素的地址）

//判断链表是否为空
bool isEmptyList(struct node* L)
{//判断头结点指向的下一指针域不为空，说明该链表不为空if (L->next != NULL)return true;//不为空elsereturn false;//为空
}

建立头结点：

创建头结点，为头结点分配内存（用到 malloc 函数，使用头文件），令链表的头指针为空指针（有头节点的链表）。

键盘输入链表中的数据

//输入n个元素
void putList(struct node *L, int n)
{struct node* p, * q;L->next = (struct node*)malloc(sizeof(struct node));q = L->next;printf("输入%d个元素放入链表：",n);for (int i = 0; i < n; i++){int x;scanf("%d", &x);p = (struct node*)malloc(sizeof(struct node));p->data = x;p->next = NULL;q->next = p;q = p;}
}

输出链表中的数据

//输出链表中的数据
void printList(struct node* L)
{struct node* p;p = L->next;printf("当前链表元素：");while (p->next != NULL){p = p->next;//工作指针后移printf("%d ", p->data);//输出当前结点的数据}printf("\n");
}

返回链表的元素个数

因为链表是动态分配内存，所以没有记录结点个数，此时可以从头结点开始，通过指针后移找到后面的结点，当指针域为空时，就结束循环，循环的次数就是结点个数。

//返回链表元素个数
int numList(struct node* L)
{int sum = 0;//计数器struct node* p;//定义一个工作指针，因为如果直接用L指针后移的话，这个链表就找不到了p = L->next;//将头指针指针域指向的地址赋给p，也就是链表的第一个元素（头指针中不存放数据）while (p->next != NULL){p=p->next;sum++;}return sum;
}

清空链表

对于清空链表，是要把链表中每一个结点的空间都释放，而不是只释放头结点的空间。而且在释放空间之前，要记录它的指针域。

//清空链表
void clearList(struct node** L)
{struct node* p, * q;p = (*L)->next;//工作指针while (p!=NULL){//记录将要被释放空间的结点的指针域，如果不记录，那么链表后面的结点就找不到了q = p->next;free(p);p = q;}(*L)->next = NULL;
}

 返回指定位置的元素值

用一个工作指针后移找结点，循环时计数器自增，找到指定位置，然后返回。

//返回链表的指定位置的元素
int elementList(struct node* L, int x)//x为指定位置
{int i = 0;//计数器struct node* p;p = L->next;//找到指定位置的前面那个位置，因为当刚好i==x-1时，此时进入循环，p=p->next,刚好到达结点为x的位置while (p != NULL&&i<x){p = p->next;i++;}if (p)return p->data;elsereturn 0;
}

查找数据所在位置

用一个工作指针后移找结点，循环中计数器自增，如果找到一个结点的数据与目标值相等就返回该位置，直到循环结束，若是没有返回，就说明链表里面没有 x 元素。

//查找数据所在位置
int findList(struct node* L, int x)
{int i = 0;struct node* p;p = L->next;while (p != NULL){if (p->data == x)//找到了直接输出该节点的序号return i;i++;p = p->next;}return 0;//代表没有找到数据为x的结点
}

也有更好的方法，比如说如果有多个结点的元素与 x 相等，上面这个代码就解决不了了，此时可以用一个数组记录找到的位置，结束时返回该数组的地址。

删除链表的元素

先搞清有头结点的链表和无头结点的链表之间的区别：

http://t.csdn.cn/3Nghn

对于有头结点的链表就相对来说方便一些，不用考虑删除头指针的情况。

将要删除的结点赋给q，然后将 p->next 赋给 p->next.

//删除元素
bool deleteList(struct node* L, int x,int *e)//x是删除元素的结点序号，传入的地址e是用来记录删除结点的数据的
{struct node* p,* q;p = L->next;int i = 0;while (i < x-1&&p->next != NULL)//这里循环到i<x-1，因为找到当前的结点后，是删除它后面那个元素{p = p->next;i++;}if (p->next == NULL)return false;//删除失败q = p->next;*e = q->data;p->next = q->next;return true;//删除成功
}

插入元素

首先插入键盘输入的数字作为插入的数据：

先开辟一块空间，再将值放入 p 的数据域，将其指针域赋为 NULL，每次循环都进行此操作（到了最后一个结点的时候，它的指针域就是 NULL），也可以在输入完数据后将最后一个结点的指针域赋为 NULL。

每次循环将 p 结点赋给 q 结点，下一轮循环时就将 q->next=p.

//插入元素（输入）
void PutList(struct node* L,int x,int y)
{struct node* q,* p,* s;int i=1;p = L;while (i < x && p != NULL)//找到要插入元素的位置{p = p->next;i++;}s = (struct node*)malloc(sizeof(struct node));s->data = y;//赋值//这两步不能反s->next = p->next;p->next = s;
}

也可以生成随机数据作为插入的数据：此时用到 rand 函数和 srand 函数（用到 #include<stdlib.h> 函数和 #include<time.h> 头文件）

//插入元素（随机）
void PutRandList(struct node** L,int x)
{struct node* p, * q;q = NULL;int i = 1;p = (*L);while (i < x && p != NULL){p = p->next;i++;}srand(time(0));int s = rand()%100;q = (struct node*)malloc(sizeof(struct node));q->data = s;q->next = p->next;p->next = q;
}

建立无头结点的单链表

链表的每一个结点都有数据域，说明首元结点前没有头结点。

//创建链表(无头结点）
void creatList(struct node** L, int n)
{printf("输入%d个元素：",n);struct node* p, * q;*L = NULL;for (int i = 0; i < n; i++){int x;scanf("%d", &x);p = (struct node*)malloc(sizeof(struct node));p->data = x;p->next = NULL;if (*L == NULL)//如果头结点是空的就将第一个结点赋值给头结点（因为这是无头结点）*L = p;elseq->next = p;q = p;}
}

建立有头结点的单链表（头插法）

建立一个带头结点的链表，为结点 p 开辟一块空间，然后将生成的随机数赋值给 p 的数据域，将 p 插入到表头，循环执行。

//建立有头结点的单链表（头插法）
void CreateListHead(struct node* L, int n)//n为元素个数
{srand(time(0));struct node* p;for(int i=0;i<n;i++){p = (struct node*)malloc(sizeof(struct node));int s = rand() % 100;//随机数p->data = s;p->next = L->next;L->next = p;}
}

建立有头节点的单链表（尾插法）

与头插法不同的是：尾插法需要另外一个指向尾部的结点 r ，在链表中插入元素时，只需要将 r 的指针指向 p 即可，然后将 p 赋值给 r ，这样可以使 r 始终在链表尾部，并且将要插入的元素置于 r 的后方，也就是链表的尾部。插入结束后，将链表尾部的元素的指针指向NULL。

//建立有头结点的单链表（尾插法）
void CreateListTail(struct node* L, int n)
{srand(time(0));struct node* p, * q;q = L;for (int i = 0; i < n; i++){p = (struct node*)malloc(sizeof(struct node));int s = rand() % 100;p->data = s;q->next = p;q = p;}q->next = NULL;
}

总代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{int data;struct node *next;
};
//清空链表
void clearList(struct node** L)
{struct node* p, * q;p = (*L)->next;//工作指针while (p!=NULL){//记录将要被释放空间的结点的指针域，如果不记录，那么链表后面的结点就找不到了q = p->next;free(p);p = q;}(*L)->next = NULL;
}
//输入n个元素
void putList(struct node *L, int n)
{struct node* p, * q;L->next = (struct node*)malloc(sizeof(struct node));q = L;printf("输入%d个元素放入链表：",n);for (int i = 0; i < n; i++){int x;scanf("%d", &x);p = (struct node*)malloc(sizeof(struct node));p->data = x;p->next = NULL;q->next = p;q = p;}
}
//输出链表中的数据
void printList(struct node* L)
{struct node* p;p = L->next;printf("当前链表元素：");while (p != NULL){printf("%d ", p->data);//输出当前结点的数据p = p->next;//工作指针后移}printf("\n");
}
//返回链表元素个数
int numList(struct node* L)
{int sum = 0;//计数器struct node* p;//定义一个工作指针，因为如果直接用L指针后移的话，这个链表就找不到了p = L->next;//将头指针指针域指向的地址赋给p，也就是链表的第一个元素（头指针中不存放数据）while (p->next != NULL){p=p->next;sum++;}return sum;
}
//判断链表是否为空
bool isEmptyList(struct node* L)
{//判断头结点指向的下一指针域不为空，说明该链表不为空if (L->next != NULL)return true;//不为空elsereturn false;//为空
}
//初始化
void InitList(struct node** L)
{*L = (struct node *)malloc(sizeof(struct node));(*L)->next = NULL;
}
//返回链表的指定位置的元素
int elementList(struct node* L, int x)//x为指定位置
{int i = 0;//计数器struct node* p;p = L->next;//找到指定位置的前面那个位置，因为当刚好i==x-1时，此时进入循环，p=p->next,刚好到达结点为x的位置while (p != NULL&&i<x){p = p->next;i++;}if (p)return p->data;elsereturn 0;
}
//查找数据所在位置
int findList(struct node* L, int x)
{int i = 0;struct node* p;p = L->next;while (p != NULL){if (p->data == x)//找到了直接输出该节点的序号return i;i++;p = p->next;}return 0;//代表没有找到数据为x的结点
}
//删除元素
bool deleteList(struct node *L, int x,int *e)//x是删除元素的结点序号，传入的地址e是用来记录删除结点的数据的
{struct node* p,* q;p = L->next;int i = 0;while (i < x-1&&p->next != NULL)//这里循环到i<x-1，因为找到当前的结点后，是删除它后面那个元素{p = p->next;i++;}if (p->next == NULL)return false;//删除失败q = p->next;*e = q->data;p->next = q->next;return true;//删除成功
}
//插入元素（输入）
void PutList(struct node* L,int x,int y)
{struct node* q,* p,* s;int i=1;p = L;while (i < x && p != NULL)//找到要插入元素的位置{p = p->next;i++;}s = (struct node*)malloc(sizeof(struct node));s->data = y;//赋值//这两步不能反s->next = p->next;p->next = s;
}
//插入元素（随机）
void PutRandList(struct node** L,int x)
{struct node* p, * q;q = NULL;int i = 1;p = (*L);while (i < x && p != NULL){p = p->next;i++;}srand(time(0));int s = rand()%100;q = (struct node*)malloc(sizeof(struct node));q->data = s;q->next = p->next;p->next = q;
}
//创建链表(无头结点）
void creatList(struct node** L, int n)
{printf("输入%d个元素：",n);struct node* p, * q;*L = NULL;for (int i = 0; i < n; i++){int x;scanf("%d", &x);p = (struct node*)malloc(sizeof(struct node));p->data = x;p->next = NULL;if (*L == NULL)//如果头结点是空的就将第一个结点赋值给头结点（因为这是无头结点）*L = p;elseq->next = p;q = p;}
}
//建立有头结点的单链表（头插法）
void CreateListHead(struct node* L, int n)//n为元素个数
{srand(time(0));struct node* p;for(int i=0;i<n;i++){p = (struct node*)malloc(sizeof(struct node));int s = rand() % 100;//随机数p->data = s;p->next = L->next;L->next = p;}
}
//建立有头结点的单链表（尾插法）
void CreateListTail(struct node* L, int n)
{srand(time(0));struct node* p, * q;q = L;for (int i = 0; i < n; i++){p = (struct node*)malloc(sizeof(struct node));int s = rand() % 100;p->data = s;q->next = p;q = p;}//这个地方不能省，因为输出的时候是以最后一个结点的指针域为NULL判断结束的q->next = NULL;
}int main()
{int n, x;struct node* L;//初始化后判断链表是否为空InitList(&L);//初始化链表if (isEmptyList(L))printf("当前链表不为空\n");elseprintf("当前链表为空\n");//输入n个元素存入链表printf("输入元素个数：");scanf("%d", &n);//输入元素个数putList(L, n);//键盘输入n个元素进入链表printList(L);if (isEmptyList(L))printf("当前链表不为空\n");elseprintf("当前链表为空\n");//统计链表中元素个数printf("链表中元素个数：%d\n",numList(L));//输入链表的结点位置，找对应位置的元素printf("输入要查找的地址：");scanf("%d", &x);printf("%d位置上的元素是：%d\n", x,  elementList(L,x));//输入元素，找链表中对应的位置printf("输入要查找的数据：");scanf("%d", &x);printf("%d在链表的第%d个\n", x,findList(L, x));//输入要删除的位置，删除对应的元素printf("输入要删除的位置：");scanf("%d", &x);int y;//记录删除的那个元素是什么if (deleteList(L, x, &y)){printList(L);//打印出链表printf("删除的元素是：%d\n", y);}else printf("删除失败\n");//插入元素printf("输入插入的元素的位置和元素：");scanf("%d%d", &x, &y);PutList(L, x, y);printList(L);//打印出链表//插入元素（随机生成数）printf("输入要插入随机数字的位置：");scanf("%d", &x);PutRandList(&L, x);printList(L);//打印出链表clearList(&L);//清空链表if (isEmptyList(L))//判断链表是否为空printf("当前链表不为空\n");elseprintf("当前链表为空\n");//建立无头结点的链表printf("建立无头结点的单链表，输入结点个数：");scanf("%d", &x);creatList(&L, x);//建立无头结点的单链表struct node *t = L;while (t != NULL)//打印无头结点单链表（打印时不能用上面的printList函数，因为这个是无头结点的链表）{printf("%d ", t->data);t = t->next;}printf("\n");clearList(&L);//清空//建立有头结点的单链表printf("输入头插法的要插入的元素个数：");scanf("%d", &x);CreateListHead(L,x);printList(L);clearList(&L);//清空//建立有头结点的单链表（随机生成数）printf("输入尾插法的要插入的元素个数：");scanf("%d", &x);CreateListTail(L, x);printList(L);clearList(&L);//清空
}