【数据结构】单链表基本操作：查找、插入、删除、创建_链表查找

链表的存储结构

 链表由结点组成，结点由数据域和指针域组成。其中，数据域存放的就是数据元素，指针域存放下一个结点的地址。数据元素可以只有一个，也可以有多个不同类型的数据元素，甚至是数组。下图和代码来自《C Primer Plus》，该链表每个节结点同时含char类型和int类型。

#define TSIZE 45
struct film{
   char title[TSIZE];
   int rating;
   struct film *next;//指针域
};
struct film head;//头指针

​​​​​​在上述表示中，头指针存储第一个结构的地址。头指针指向链表中的第一项。在上述的表示方式中，结构体的名字是struct film，每次使用该类型的指针，都要写全这个名字。

struct film *p=(struct film*)malloc(sizeof(struct film));//调用malloc,为新结构和新指针分配空间

事实上， 在以后的数据结构学习中，我们常用的是下面这种形式：

tyoedef int ElemType;
typedef struct LNode{
     ElemType data;
     struct LNode *next;
}LNode,*LinkList;
LNode L;
LinkList p=(LinkList)malloc(sizeof(LNode));

在这里，L是单链表的名字，p是一个同类型指针，但还未定义它指向谁。

虽然LNode和*LinkList是等价的，但还是常用上述表示方式。在某些编译器里，不这样表示可能会报错。

在后续学习中，头结点，头指针，第一个结点等概念也略有变化。以往，我们设L为LinkList型的变量，则L为单链表的头指针，它指向表中的第一个结点。若L为空，则所表示的线性表为空表，长度为0 。此后，在单链表的第一个结点前设一个结点，称之为头结点。头结点的指针域存储第一个结点的存储位置(即指向第一个结点的指针)。单链表的头指针指向头结点。若头结点的指针域为空，则单链表为空表。若单链表名为L，L就是头指针head，在不同参考资料中可能用L，也可能用head。下图是博主用ppt画的，上为空表，下为非空表。

单链表基本操作

遍历输出

在正式开始之前，我们不妨先熟悉一下单链表的遍历本身。

void DisplayLink(LinkList L)
{
LinkList p;
p=L;//链表名L，L也是头指针的名字，指向头结点。头结点的指针域指向第一个结点(即p->next)
while(p!=NULL)//注意一下代码的简洁易懂。p!=NULL比!(p=NULL)常用
{
printf(%d\n",&p->data);
p=p->next;//不能用p++，因为链表不是连续存储的
}
}

注意，遍历本身是不需要分配空间的，不需要调用malloc函数。LinkList类型的指针p本身就是用来指向LinkList类型结构体的。p指向需要插入链表中的新结点时，需要给p分配空间。

按位序查找

顺序表按位序查找比较简单，直接引用L.elem[i]即可。但链表查找必须从头开始

Status ListLocate(LinkList L,int i,ElemType &e)
{
 int j;
 LinkList p;//同理遍历，不要给p分配动态存储空间
 p=L->next;//p存储第一个结点的地址
 j=1;//(j=0)
 while(p&&j<i)//(j<i-1)
 {
   p=p->next;//循环结束时，p存储第i个结点的地址
   j++;
 }
 if(!p||j>i) return ERROR;//i>表长||空表
 e=p->data;
 printf("第%d位是元素%d\n", i, e);
 return OK;
}

在本节学习中，Status型函数比较常用，因为可以对操作失败做出返回值。你也可以用bool代替。

按值查找

Status QueryNode(LinkList L,ElemType x)
{
LinkList p;int i=0;
p=L->next;
while(p!=NULL)
{
if(p->data=x)
{
i++;
printf("元素%d在链表第%d位\n",x,i);
return OK;
}
p=p->next;
}
return ERROR;
}

删除

链表的删除和插入原理相同，重点都在于不要丢失结点地址

Status DeletList(LinkList &L,int i,ElemType &e)//删除第i个结点
{
 LinkList p,q;//q指向第i个结点。循环结束时，p指向第i-1个结点
 p=L;//p存储头结点的地址
 int j=0;
 while(p->next&&j<i-1)
 {
  p=p->next;
  i++;
 }
 if(!p->next||j>i-1) return ERROR;
//*****************************
 q=p->next;
 p->next=q->next;//第i-1个结点的指针域指向第i+1个结点
//*****************************
 e=q->data;//用e存放q的数据域
 free(q);//释放第i个结点
 return OK; 
}

插入

Status ListInsert(LinkList &L,int i,ELemType e)//在第i个结点前插入新结点
{
 LinkList p=L;
 LinkList q;
 int j=0;
 while(p&&j<i-1)
 {
  p=p->next;
  j++;//循环结束时，p指向第i-1个结点
 }
 if(!p||j>i) return ERROR;
 else
 {
  q=(LinkList)malloc(sizeof(LNode));
  q->next=p->next;
  p->next=q;
  p->data=e;
 }
 return OK;
}

注意在第i位后插入元素的while循环条件不是while(p->next&&j<i-1)，而是while(p&&j<i-1)，因为尾结点之后也可以插入新结点，操作和其他结点是一样的。如一个长度为12的链表，可在其第13位前插入。

创建

头插法

每个新结点都是头结点的新直接后继。

由图知，头插法的输入顺序为倒序

关键步骤：1.初始化一个空表 2.for循环逐个插入结点

//关键步骤
p->next=L->next;
L->next=p;

void CreatList(LinkList &L,int n)//L为链表名,n为表长
{
  L=(LinkList)malloc(sizeof(LNode));//定义指向L的头指针
  L->next=NULL;//初始化L为空表
  for(int i=n;i>0;--i)
  {
    LinkList p=(LinkList)malloc(sizeof(LNode));//随用随分配
    scanf("%d",&p->data);
    p->next=L->next;
    L->next=p;
  }
}

for(i=n;i>0;i--)和for(i=n;i>0;--i)都表示递减循环，即从n开始，每次递减1，直到i小于等于0为止。

区别在于循环体中对i的更新位置不同。在for(i=n;i>0;i--)中，i表示先使用i的当前值进行循环体操作，然后再将i减1；而在for(i=n;i>0;--i)中，--i表示先将i减1，然后再使用新值进行循环体操作。

尾插法

每个新结点都是尾结点的新直接前驱

它的思路是遍历链表，将新的结点插入到链表的尾部，即在原有链表的最后一个结点之后插入新的结点。这种方法可以保持原链表的相对顺序不变。

具体步骤如下：

1. 创建一个新的结点q，将待插入的值赋给q的data域。
2. 如果链表为空，即头结点为NULL，将q赋给头结点的next域，即头结点指向q。
3. 否则，遍历链表，找到链表的最后一个结点。
4. 将q插入到最后一个结点的后面，即将最后一个结点的next指针指向q。
5. 更新链表的最后一个结点为q，即将q赋给最后一个结点。

这样，每次插入新的结点时，都会保持链表的相对顺序不变，并且新的结点都会插入到链表的尾部。

void CreateList(LinkList& L, int n) {//尾插法
// 正序输入 n 个数据元素，建立带头结点的单链表
LinkList p, q; int i;
L = (LinkList)malloc(sizeof(LNode));
q = L; // 先建立一个带头结点和尾指针的单链表
for (i = 0; i < n; ++i) {
p = (LinkList)malloc(sizeof(LNode));
scanf_s("%d", &p->data); // 输入元素值
q->next = p;
q = p;
} //
q->next = NULL; //修改尾指针
}

一道题目

题干

不妨用下面这道题串联上述操作，顺便练习C语言菜单的建立。

主函数中实现下列操作(蓝色部分用函数实现)

1. 头插法创建n个随机元素的单链表
2. 输出单链表
3. 输入要查找的位序i,调用函数，按位序查找单链表，输出位序为i的元素值
4. 输入要插入的元素f和要插入的位置，调用插入函数，并输出更新后的链表
5. 输入要删除的元素位置，调用按位序删除函数，先输出删除的元素值，再输出更新后的链表

菜单

C语言菜单是一种通过控制台界面为用户提供选择功能的方式。通常使用switch语句和循环来实现菜单的选择和功能执行的过程。通过用户输入的选择执行对应的功能函数。在每个功能函数内部，你可以编写你想要执行的具体功能代码。若当用户输入某个特定值时，返回上一级菜单，则实现了多级菜单。

本题用到的菜单比较简单，博主采用了最基本的if...else if...语句。

源代码

源代码如下。编译器vs20

一点细节：博主认为输出查找结果的printf语句放在主函数里比放在查找函数里方便。

#include <stdio.h>
#include <stdlib.h>
constexpr auto ERROR = 0;
constexpr auto OK = 1;
typedef int ElemType;
typedef int Status;
typedef struct node {
	ElemType data;
	struct node* next;
}LNode, * LinkList;
void DisplayLink(LinkList L)//输出链表
{
	LinkList p;
	p = L->next;//链表名L，L也是头指针的名字，指向头结点。头结点的指针域指向第一个结点(即p->next)
	while (p!=NULL)
	{
		printf("%d\n", p->data);
		p = p->next;//不能用p++，因为链表不是连续存储的
	}
}
Status ListLocate(LinkList L,  int i,ElemType& e)//按位序查找
{
	LinkList p;
	p = L->next;
	int j = 1;
	while (p!=NULL&&j<i)
	{
		p = p->next;
		j++;
	}
	if (!p||j>i) return ERROR;
	e = p->data;
	return OK;
}
Status DeletList(LinkList& L, int i, ElemType& e)//删除第i个结点
{
	LinkList p, q; int j;
	p = L; j = 0;
	while (p->next&&j<i-1)//循环结束时,p指向第i-1个结点
	{
		p = p->next;
		j++;
	}
	if (!(p->next )|| j > i - 1) return ERROR;
	q = p->next;
	p->next = q->next;
	e = q->data;
	free(q);
	return OK;
}
Status ListInsert(LinkList &L, ElemType e, int i)//在第i个结点前插入
{
	LinkList p, q;
	int j = 0;
	p = L;
	while (p&&j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) return ERROR;
	q = (LinkList)malloc(sizeof(LNode));
	q->data = e;
	q->next = p->next;
	p->next = q;
	return OK;
}
void ListCreate(LinkList& L, int n)//头插法：输入顺序为倒序
{
	LinkList p;
	L = (LinkList)malloc(sizeof(LNode));
	L->next= NULL;
	printf("输入元素:\n");
	for(int i=0;i<n;i++)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf_s("%d",&p->data);
		p->next = L->next;
		L->next = p;
	}
}
int select(void)//菜单选择函数
{
	int s;
	printf("查找请按1\n");
	printf("删除请按2\n");
	printf("插入请按3\n");
	scanf_s("%d", &s);
	return s;
}
int main(void)
{
	LinkList A;
	int a; printf("请输入链表长度:\n"); scanf_s("%d", &a);
	ListCreate(A, a);
	printf("您已创建链表如下:\n");
	DisplayLink(A);
	printf("查找请按1\n删除请按2\n插入请按3\n退出请按0\n");
 
	int x;//由用户输入，控制小while循环
	int b;//要查找、删除第几位
	int c;//返回第几位的值
 
	x = 6;
	while (x)//x的初始值为除1、2、3之外的非0数
	{
		scanf_s("%d", &x);
		if (x == 1)
		{
			printf("要查找第几位\n"); scanf_s("%d", &b);
			ListLocate(A, b, c);
			printf("第%d位是数字%d\n", b, c);
			printf("查找请按1\n删除请按2\n插入请按3\n退出请按0\n");
		}
		else if (x == 2)
		{
			printf("要删除第几位\n"); scanf_s("%d", &b);
			DeletList(A, b, c);
			printf("您已删除第%d位的值%d\n", b, c);//如果删除失败，输出的还是原表
			DisplayLink(A);
			printf("查找请按1\n删除请按2\n插入请按3\n退出请按0\n");
		}
		else if (x == 3)
		{
			printf("在第几个结点前插入\n");
			scanf_s("%d", &b);
			printf("插入元素:\n");
			scanf_s("%d", &c);
			ListInsert(A, c,b);
			printf("您已在%d位前插入%d\n", b, c);//如果插入失败，输出的还是原表
			DisplayLink(A);
			printf("查找请按1\n删除请按2\n插入请按3\n退出请按0\n");
		}
		else printf("重新输入\n");
	}
	printf("退出循环，操作结束\n");
	return 0;
}

运行结果

其一

其二