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

这篇具有很好参考价值的文章主要介绍了【数据结构】单链表基本操作:查找、插入、删除、创建。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链表的存储结构

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

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

链表查询csdn,数据结构,visualstudio,c++

​​​​​​在上述表示中,头指针存储第一个结构的地址。头指针指向链表中的第一项。在上述的表示方式中,结构体的名字是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画的,上为空表,下为非空表。

链表查询csdn,数据结构,visualstudio,c++

单链表基本操作

遍历输出

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

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位前插入。

创建

头插法

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

链表查询csdn,数据结构,visualstudio,c++

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

关键步骤: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;
}

运行结果

其一

链表查询csdn,数据结构,visualstudio,c++

链表查询csdn,数据结构,visualstudio,c++

链表查询csdn,数据结构,visualstudio,c++

其二

链表查询csdn,数据结构,visualstudio,c++

链表查询csdn,数据结构,visualstudio,c++

链表查询csdn,数据结构,visualstudio,c++文章来源地址https://www.toymoban.com/news/detail-786499.html

到了这里,关于【数据结构】单链表基本操作:查找、插入、删除、创建的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包