数据结构之单链表—

数据结构之单链表——考研笔记

文章目录

一.单链表定义
- 1.什么是单链表
- 2.代码实现
- 3.不带头结点的单链表
- 4.带头结点的单链表
二.单链表插入删除
- 1.按位序插入（带头结点）
- 2.插入时不带头节点
- 3.指定节点的后插操作
- 4.指定节点的前插操作
- 5.按位序删除（带头结点）
- 6.删除指定节点p
三.单链表查找
- 1.按位查找
- 2.按值查找
- 3.求表长
四.单链表建立
- 1.尾插法建立单链表
- 2.头插法建立单链表

在这里插入图片描述

一.单链表定义

1.什么是单链表

在这里插入图片描述
单链表一个节点需要存放数据元素和指向下一个节点的指针，由于每个节点只包含一个指针，所以叫单链表。
单链表：改变容量方便，但不可随机存取

2.代码实现

struct LNode//LNode:结点
{
	ElemType data;//数据域，每个节点存放一个数据元素
	struct LNode *next;//指针域，指针指向下一个节点
};
//用malloc函数增加新的节点
struct LNode *p=(struct LNode*)malloc(sizeof(struct LNode));

书写麻烦，因此可以用typedef 给关键字重命名

typedef <数据类型> <别名>

typedef int zhengshu;
zhengshu x=1;

typedef int *zhengshuzhizhen;
zhengshuzhizhen p;

tyepedef struct LNode LNode;
LNode *p=(LNode*)malloc(sizeof(LNode));

//综上：

typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//struct LNode重命名为LNode，linklist:指向struct LNode的指针

表示一个单链表时，只需声明一个头指针L，指向单链表的第一个节点
在这里插入图片描述

LNode* L：强调返回的是一个节点
等价于
LinkList L：强调是一个单链表
都是声明一个指向单链表节点的指针

3.不带头结点的单链表

//初始化一个空的单链表
bool InitList(LinkList &L)
{
	L=NULL;//空表，暂时没有任何节点
	return true;
}
bool Empty(LinkList L)
{
	return(L==NULL);
}
void test()
{



	LinkList L;//声明一个指向单链表的指针
	InitList(L);
}

4.带头结点的单链表

bool InitList(LinkList &L)
{
	L=(LNode*)malloc(sizeof(LNode));//分配一个头节点
	if(L==NULL)//内存不足分配失败
	{	
		return false;
	}
	L->next=NULL;//头节点之后暂时还没有节点
	return true;
}

在这里插入图片描述
头节点不存放数据，只有这个头结点之后的下一个数据才存放数据

二.单链表插入删除

单链表的插入删除只需要移动指针

在这里插入图片描述

上一个节点的指针域存放着下一个节点的地址，现在s节点要插进来，所以应该把b所在节点的地址放在s节点的指针域里，而b所在节点的地址在哪呢？在没插前b所在节点的地址在p节点的指针域里，所以咱把s-next=p-next(把p节点的指针域赋值给s节点的指针域)，这样s节点的指针域就有b所在节点的地址了。然后咱再让p-next=s(把s节点的地址信息赋值给p节点的指针域)，这样一个单链表插入节点的操作就完成了
在这里插入图片描述

1.按位序插入（带头结点）

InsertList(&L,i,e);
//找到第i-1个节点，将新节点插入其后
i=2
在这里插入图片描述
头节点可以看成第0个节点，所以当i=1时也适用
分析：

i=1时（插在表头）
插在表中
插在表尾
i>length

//在第i个位置插入元素e
ListInsert(LinkList &L,int i,int e)
{
	if(i<1)
		return false;
	LNode *p;//p指向当前扫到的节点
	int j=0;//当前p指向的是第几个节点，头节点是第0个节点
	p=L;//L指向头节点，头节点是第0个节点（不存数据）
	if(p!=NULL && j<i-1)//循环找到第i-1个节点
	{
		p=p->next;
		j++;
	}
	if(p==NULL)//p值不合法
		return false；
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;//s节点连在p后
	return true;
}		
	//else
	//	e.next=L.i;
	//	L.i-1->next=L.e;

2.插入时不带头节点

在这里插入图片描述

bool InsertList(LinkList &L,int i,int e)
{
	if(i<1)
		return false;
	if(i==1)
		LNode *s=(LNode*)malloc(sizeof(LNode));
		s->data=e;
		s->next=L;
		L=s;//头指针指向新节点
		return true;
	}
	LNode*p;//指针p指向当前扫到的节点
	int j=1;//当前p指向的是第几个节点
	p=L://p指向第1个节点（不是头节点）
	while(p!=NULL&&p<i-1)	
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

在这里插入图片描述

3.指定节点的后插操作

在这里插入图片描述

//在p指针后插入元素e
bool InsertList(LNode *p,ElemType e)
{
	if(p==NULL)
		return false;//**注意p为空的情况
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;//**生成内存空间失败
	//p后节点已知
	s->data=e;//**用节点s保存数据e
	s->next=p->next;
	p->next=s;//将s结点连在p后
	return true;
	
}

4.指定节点的前插操作

在这里插入图片描述

//在结点p之前插入e
bool InsertPriorList(LinkList L,LNode *p,ElemType e)//**传入一个头指针
{
	if(p==NULL)
		return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)//空间满了
		return false;
	s->data=e;
	int j=0;
	j=L;
	L.i=p;
	while(j<i-1)
	{
		j=L->next;
		j++;
		
	}
	
	s->next=p;
	j->next=s;
	return true;

另一种实现方式
在这里插入图片描述

//用新节点覆盖旧结点，再将旧节点放入新结点中
bool InsertPriorList(LNode *p,ElemType e)
{
	if(p==NULL)
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->next=p->next;
	p->next=s;//新节点连在p后
	s->data=p->data;//p中元素复制到s中
	p->data=e;//p中元素覆盖到e
	return true;

时间复杂度O（1）

5.按位序删除（带头结点）

ListDelete(&i,i,&e):删除表L中第i个位置的元素，并用e返回删除元素的值
找到第i-1个节点并指向i+1节点最后将第i个位置的节点释放掉

bool ListDelete(LinkList &L,int i,ElemType &e)
{
	if(i<1)//**节点从1开始
		return false;
	LNode *p;//**声明指针p扫到当前指向的节点
	int j=0;//p扫到的是第几个结点
	p=L;//p指向L头节点，头节点是第0个结点
	 
	while(p!=NULL&&j<i-1)//**指针p不能为空
	{
		p=p->next;//**p一个个向后扫
		j++;
	}
	if(p==NULL)//**i值不合法
		return false;
	if(p->next=NULL)//**第i-1结点后再无其他结点
		return false;
	LNode *q=p->next;//**q指向被删除节点
	e=q->data;//**用e返回被删元素的值
	p->next=q->next;//将q结点从中断开
	free(q);
	return true;
}

最坏时间复杂度：O（n）

6.删除指定节点p

bool DeleteList(LNode *p)
在这里插入图片描述

bool DeleList(LNode *p)
{
	if(p==NULL)
		return false;
	LNode*q=p->next;
	p->data=p->next->data;//**和后继节点数据域交换data
	p->next=q->next;
	free(q);//释放后继结点的存储空间
	return true;
}

在这里插入图片描述
如果p指向最后一个节点，则上述结点有BUG

单链表局限性：只能单向检索，不能逆向检索

!](https://i-blog.csdnimg.cn/direct/4f4772a7ec84437e850b2775299340dd.png)

三.单链表查找

基于带头结点的单链表

按位查找
按值查找

1.按位查找

GetElem(L,i):获取表中第i个位置元素的值
LocateElem(L,e):按值查找

//按位查找，找到单链表中第i个位置的结点
LNode *GetElem(LinkList L,int i)
{
	if(i<0)
		 return NULL;
	LNode *p;//指针p指向当前扫描到的节点
	p=L;//p指向头节点
	int j=0;
	while(p!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	return p;
}

2.按值查找

//按值查找
LNode *LocateElem(LinkList L,ElemType e)
{
	LNode *p;
	p=L->next;//从第1个节点开始查找数据域为e的节点
	while(p!=NULL && p->data!=e)
		p=p->next;
	return p;//找到后返回该节点的指针，否则返回NULL
}

在这里插入图片描述

3.求表长

int length(LinkList L)
{
	int i=0;
	LNode *p=L->next;
	while(p!=NULL)
	{
		p=p->next;
		i++;
	}
	return i;
}

四.单链表建立

尾插法
头插法

Step1.初始化一个单链表
Step2.每次去一个数据元素，插到表尾/头

typedef struct
{
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一结点
}LNode,*LinkList;
//初始化一个单链表，带头结点
bool InitList(LinkList &L)
{
	L=(LNode*)malloc(sizeof(LNode));
	if(L==NULL)//内存不足，分配失败
		return false;
	L->next=NULL;//头节点之后暂时还没有节点
	return true;
}
void test()
{
	LinkList L;
	InitList(L);
}

1.尾插法建立单链表

void TailList(LinkList &L)
{
	L=(LNode*)malloc(sizeof(LNode));//建立头节点
	int x;//把ElemType设为整型
	int *s,*r=L;//r为表尾指针
	scanf(%d",&x);
	while(e!=99999)
	{
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;//在r后插入元素x
		r=s;//r指向新的表尾结点
		scanf("%d",&x);
	}
	r->next=NULL;//尾结点指针置空
	return L;
}

在这里插入图片描述

2.头插法建立单链表

bool NextNode(LNode *p,ElemType e)
{
	if(p==NULL)
		return false;
	LNode *s =(LNode*) malloc(sizeof(LNode));
	if(s==NULL)//内存分配失败
		return false;
	s->data=e;//用节点s保存数据元素e
	s->next=p->next;
	p->next=s;//将结点s连在p之后
	return true;
}