数据结构-单链表基本操作带图完整详解

2024-03-13 13:19:45

1.什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指 针链接次序实现的。

2.为什么要使用链表

在未学习链表时，我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快，但是它的弊端也很明显：

1.使用前需声明数组的长度，一旦声明长度就不能更改

2.插入和删除操作需要移动大量的数组元素，效率慢

3. 只能存储一种类型的数据

顺序表就是在计算机中内存以数组的形式保存的线性表，因此这些弊端同理

而链表则可以实现以上这些数组所不具备的功能，此时引入了结构体来实现创建链表的操作

  1.  n个节点离散分配
  2. 每一个节点之间通过指针相连
  3. 每一个节点有一个前驱节点和一个后继节点
  4. 首节点没有前驱节点，尾节点没有后继节点

数据结构-单链表基本操作带图完整详解 

创建单链表 

//带头结点单链表，逻辑相邻，物理不一定相邻，为了找到下一个结点，就必须增加下一个结点的地址
//尾结点；最后一个结点，在单链表中，尾结点的next为NULL，NULL是单链表的结尾标志
//头结点；其数据域不使用或者存放链表长度，其作用相当于标杆，简化整个操作

typedef int ElemType;
typedef struct Node
{
	ElemType data;//数据
	struct Node* next;//后继指针
}Node,*List;
//typedef Node* List;//List==Node *
//List本质是Node*,但含义不同,List表示一条链表,Node*表示一个节点的地址

首节点：存放第一个有效数据的节点

头节点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点（首节点）的地址。头结点的作用是使所有链表（包括空表）的头指针非空

头指针：指向头节点的指针

尾节点：存放最后一个有效数据的节点

尾指针：指向尾节点的指针

数据结构-单链表基本操作带图完整详解
 

 数据结构-单链表基本操作带图完整详解

 基本函数：

//初始化plist
void InitList(List plist);

//头插  往plist中头部插入数字val
bool Insert_head(List plist, ElemType val);

//尾插  往plist中尾部插入数字val
bool Insert_tail(List plist, ElemType val);

//删除plist中第一个val
bool DeleteVal(List plist, ElemType val);

//在plist中查找val值找到返回该结点地址，失败返回NULL
Node* Search(List plist, ElemType val);

//判断plist是否为空链表（没有数据结点）
bool IsEmpty(List plist);

//获取plist长度，数据结点的个数
int GetLength(List plist);

//获取plist链表的pos位置(下标)的值
bool GetElem(List plist, int pos, int* rtval);//输出参数rtval

//获取val前驱
Node* Prior(List plist, ElemType val);

//获取val后继
Node* Next(List plist, ElemType val);

//打印
void Show(List plist);

//清空数据
void Clear(List plist);
//销毁
void Destroy(List plist);

 3.基本操作

初始化单链表plist(带头结点):

//初始化plist
void InitList(List plist)
{
	assert(plist != NULL);
	//头结点的数据不使用plist->data,可以不处理
	plist->next = NULL;
}

//另一种写法(会出现二级指针不推荐)
void InitList(List* pplist)
{
	assert(pplist != NULL);
	*pplist = (Node*)malloc(sizeof(Node));//动态创建头结点
	assert(*pplist != NULL);
	if (*pplist == NULL)
		return;
	(*pplist)->next = NULL;
}

 插入操作:

1.头插

数据结构-单链表基本操作带图完整详解

 

//头插  往plist中头部插入数字val  //时间复杂度O(1)
bool Insert_head(List plist, ElemType val)
{
	//1.动态创建一个新结点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(p != NULL);
	if (p == NULL)
		return false;
	//2.把数据val存放到新结点
	p->data = val;
	//3.把新结点插入在头结点的后面
	p->next = plist->next;
	plist->next = p;
	return true;
}

2.尾插

数据结构-单链表基本操作带图完整详解

//尾插  往plist中尾部插入数字val
bool Insert_tail(List plist, ElemType val)//时间复杂度O(n)
{
	//1.动态创建新结点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(p != NULL);
	if (p == NULL)
		return false;
	//2.把值存放到新结点
	p->data = val;
	//3.找到链表尾巴
	Node* q;
	for (q = plist; q->next != NULL; q = q->next);
	//4.把新结点插在尾结点后面
	 p->next=q->next;//p->next=NULL
	 q->next = p;
	 return true;
}

 打印函数:

数据结构-单链表基本操作带图完整详解

 

//打印
void Show(List plist)
{
	for (Node* p = plist->next; p != NULL; p = p->next) //遍历所有的数据结点
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

上面三个函数测试用例：

int main()
{
	Node head;//创建头结点
	InitList(&head);
	//for (int i = 0; i < 10; i++) //....4 3 2 1 0头插
	//{
	//	Insert_head(&head, i); 
	//}
	for (int i = 0; i < 10; i++) //0 1 2 3 4....尾插
	{
		Insert_tail(&head, i);
	}
	Show(&head);
}

数据结构-单链表基本操作带图完整详解

 查找函数(在plist中查找val值,找到返回该结点地址，失败返回NULL):

数据结构-单链表基本操作带图完整详解

 

//在plist中查找val值,找到返回该结点地址，失败返回NULL
Node* Search(List plist, ElemType val)
{
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data ==val)//找到了
			return p;
	}
	return NULL;//没找到
}

获取任意值val的前期:

//获取val前驱
Node* Prior(List plist, ElemType val)
{
	for (Node* p = plist->next; p ->next!= NULL; p = p->next)
	{
		if (p->next->data == val)
			return p; //找到了
	}
	return NULL;//失败了
}

获取任意值val的后继:

//获取val后继
Node* Next(List plist, ElemType val)
{
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data == val)
			return p->next;
	}
	return NULL;
}

删除操作(删除plist中第一个val值):

数据结构-单链表基本操作带图完整详解

 

//删除plist中第一个val
bool DeleteVal(List plist, ElemType val)
{
	//1.找到需要删除的结点前驱
	Node* p= Prior(plist,val);//指向前驱结点 调用找前驱函数
	if (p == NULL)//没有val
		return false;

	Node* q = p->next;//标记需要删除的结点
	p->next = q->next;//将q从链表中剔除
	free(q);  //释放结点
	return true;
}

判空操作:

数据结构-单链表基本操作带图完整详解

//判断plist是否为空链表（没有数据结点）
bool IsEmpty(List plist)
{
	return plist->next == NULL;
	//等同于
	/*if (plist->next == NULL)
		return true;
	else
		return false;*/
		
}

 获取长度(获取plist长度，数据结点的个数):

数据结构-单链表基本操作带图完整详解

 

//获取plist长度，数据结点的个数
int GetLength(List plist)
{
	int count = 0;
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		count++;
	}
	return count;
}

获取链表下标位置的值(获取plist链表的pos位置(下标)的值)：

//获取plist链表的pos位置(下标)的值
bool GetElem(List plist, int pos, int* rtval)//输出参数rtval
{
	if (pos < 0 || pos >= GetLength(plist))//下标不存在
		return false;

	Node* p=plist->next;
	for (int i=0;i < pos; p = p->next, i++)
	{
		;
	}
	*rtval= p->data;
	return true;	
}

销毁操作:

数据结构-单链表基本操作带图完整详解

//销毁
void Destroy(List plist)
{

  /*第一种写法
	if (plist == NULL || plist->next == NULL)
		return;
	Node* p = plist->next;
	Node* q;
	plist->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
	*/
    //第二种写法
	Node* p;//指向第一个数据结点
	while (plist->next != NULL)//还有数据结点
	{
		p = plist->next;
		plist->next = p->next;//剔除p
		free(p);
	}

}

 清空数据:


//清空数据 把所有的数据删除
void Clear(List plist)
{
	Destroy(plist);
}

完整代码:

#pragma once

typedef int ElemType;
typedef struct Node
{
	ElemType data;//数据
	struct Node* next;//后继指针
}Node,*List;
//typedef Node* List;//List==Node *
//List本质是Node*,但含义不同,List表示一条链表,Node*表示一个节点的地址

//初始化plist
void InitList(List plist);
//头插  往plist中头部插入数字val
bool Insert_head(List plist, ElemType val);
//尾插  往plist中尾部插入数字val
bool Insert_tail(List plist, ElemType val);
//删除plist中第一个val
bool DeleteVal(List plist, ElemType val);

//在plist中查找val值找到返回该结点地址，失败返回NULL
Node* Search(List plist, ElemType val);
//判断plist是否为空链表（没有数据结点）
bool IsEmpty(List plist);
//获取plist长度，数据结点的个数
int GetLength(List plist);
//获取plist链表的pos位置(下标)的值
bool GetElem(List plist, int pos, int* rtval);//输出参数rtval

//获取val前驱
Node* Prior(List plist, ElemType val);
//获取val后继
Node* Next(List plist, ElemType val);

//打印
void Show(List plist);
//清空数据
void Clear(List plist);
//销毁
void Destroy(List plist);
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"list.h"
//初始化plist
void InitList(List plist)
{
	assert(plist != NULL);

	//头结点的数据不使用plist->data,可以不处理
	plist->next = NULL;
}
//书上的写法
void InitList(List* pplist)
{
	assert(pplist != NULL);
	*pplist = (Node*)malloc(sizeof(Node));//动态创建头结点
	assert(*pplist != NULL);
	if (*pplist == NULL)
		return;
	(*pplist)->next = NULL;
}
//头插  往plist中头部插入数字val// O(1)
bool Insert_head(List plist, ElemType val)
{
	//1.动态创建一个新结点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(p != NULL);
	if (p == NULL)
		return false;
	//2.把数据val存放到新结点
	p->data = val;
	//3.把新结点插入在头结点的后面
	p->next = plist->next;
	plist->next = p;
	return true;
}
//尾插  往plist中尾部插入数字val
bool Insert_tail(List plist, ElemType val)//O(n)
{
	//1.动态创建新结点
	Node* p = (Node*)malloc(sizeof(Node));
	assert(p != NULL);
	if (p == NULL)
		return false;
	//2.把值存放到新结点
	p->data = val;
	//3.找到链表尾巴
	Node* q;
	for (q = plist; q->next != NULL; q = q->next);
	//4.把新结点插在尾结点后面
	 p->next=q->next;//p->next=NULL
	 q->next = p;
	 return true;
}

//在plist中查找val值,找到返回该结点地址，失败返回NULL
Node* Search(List plist, ElemType val)
{
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data ==val)//找到了
			return p;
	}
	return NULL;//没找到
}
//删除plist中第一个val
bool DeleteVal(List plist, ElemType val)
{
	//1.找到需要删除的结点前驱
	Node* p= Prior(plist,val);//指向前驱结点
	if (p == NULL)//没有val
		return false;

	Node* q = p->next;//标记需要删除的结点
	p->next = q->next;//将q从链表中剔除
	free(q);  //释放结点
	return true;
}

//判断plist是否为空链表（没有数据结点）
bool IsEmpty(List plist)
{
	return plist->next == NULL;
	//等同于
	/*if (plist->next == NULL)
		return true;
	else
		return false;*/
		
}

//获取plist长度，数据结点的个数
int GetLength(List plist)
{
	int count = 0;
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		count++;
	}
	return count;
}

//获取plist链表的pos位置(下标)的值
bool GetElem(List plist, int pos, int* rtval)//输出参数rtval
{
	if (pos < 0 || pos >= GetLength(plist))//下标不存在
		return false;

	Node* p=plist->next;
	for (int i=0;i < pos; p = p->next, i++)
	{
		;
	}
	*rtval= p->data;
	return true;
		
}


//获取val前驱
Node* Prior(List plist, ElemType val)
{
	for (Node* p = plist->next; p ->next!= NULL; p = p->next)
	{
		if (p->next->data == val)
			return p; //找到了
	}
	return NULL;//失败了
}
//获取val后继
Node* Next(List plist, ElemType val)
{
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data == val)
			return p->next;
	}
	return NULL;
}


//打印
void Show(List plist)
{
	for (Node* p = plist->next; p != NULL; p = p->next) //遍历所有的数据结点
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

//清空数据 把所有的数据删除
void Clear(List plist)
{
	Destroy(plist);
}
//销毁
void Destroy(List plist)
{/*
	if (plist == NULL || plist->next == NULL)
		return;
	Node* p = plist->next;
	Node* q;
	plist->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
	*/
	Node* p;//指向第一个数据结点
	while (plist->next != NULL)//还有数据结点
	{
		p = plist->next;
		plist->next = p->next;//剔除p
		free(p);
	}

}

//测试用例
int main()
{
	Node head;//创建头结点
	InitList(&head);
	//for (int i = 0; i < 10; i++) //....4 3 2 1 0头插
	//{
	//	Insert_head(&head, i); 
	//}
	for (int i = 0; i < 10; i++) //0 1 2 3 4....尾插
	{
		Insert_tail(&head, i);
	}
	Show(&head);
	DeleteVal(&head, 3);
	Show(&head);
	printf("长度为:%d\n", GetLength(&head));

	int rtval;
	for (int i = 0; i < 10; i++)
	{
		if (GetElem(&head, i, &rtval))
			printf("%d %d\n", i, rtval);
	}
	
	for (int i = -1; i < 10; i++)
	{
		Node* p = Next(&head, i);//没有后继
		if (p == NULL)
			printf("%d没有后继\n", i);
		else
			printf("%d的后继数据为%d\n", i, p->data);
	}


	if (IsEmpty(&head))
		printf("空");
	else
		printf("不空");
	return 0;
}

看到这里了不妨点个赞!创作不易

 

上一篇：数据结构（C语言）约瑟夫环


下一篇：2021-09-08