数据结构-线性表-单链表02

线性表-单链表探究

2.3.1 单链表定义

dc7d4713cc2eff99fc5b308c557c8a30

1
2

单链表分为带头结点和不带头结点两种类型。在许多情况下，带头结点的单链表能够简化运算的实现过程。
因此这里讨论的单链表除特别指出外均指带头结点的单链表

单链表结构

typedef struct node
{  ElemType data;		//数据域
   struct node *next;		//指针域
} SLinkNode;			//单链表结点类型

尾节点next探究- 1.指向null 2.指向头节点-循环单链表

2.3.2线性表基本运算在单链表上的

数据结构

8d42879b92325190541fb4481ce40e7f

1.初始化线性表运算算法

创建一个空的单链表，它只有一个头结点，由L指向它。该结点的next域为空，data域未设定任何值。对应的算法如下：
void InitList(SLinkNode *&L)　　　//L为引用型参数
{  L=(SLinkNode *)malloc(sizeof(SLinkNode)); //创建头结点L
   L->next=NULL;
}

2.销毁线性表运算算法

1	`一个单链表中的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间。循环next delete吗`

void  DestroyList(SLinkNode *&L)
{
SLinkNode *pre=L,*p=pre->next;
   while (p!=NULL)
   {  free(pre);
      pre=p; p=p->next;	//pre、p同步后移
   }
   free(pre);

}

3.求线性表的长度运算算法

设置一个整型变量i作为计数器，i初值为0，p初始时指向第一个数据结点。然后沿next域逐个往后查找，每移动一次，i值增1。当p所指结点为空时，结束这个过程，i之值即为表长。

int GetLength(SLinkNode *L)
{  
       int=0;
       SLinkNode *p_next=L->next;
       while(p!=null)
       {
       i++;
       L=p_next;
}
return i;
}

4.求线性表中第i个元素运算算法

用p从头开始遍历单链表L中的结点，用计数器j累计遍历过的结点，其初值为0。
在遍历时j等于i时，若p不为空，则p所指结点即为要找的结点，查找成功，算法返回1。
否则算法返回0表示未找到这样的结点。

int GetElem(SLinkNode *L,int i,ElemType &e)
{  int j=0;
SLinkNode *P=L;
if(i<=0 )
{
return 0;
}
while(p!=null &&j<I)
{
j++;
p=p->next;
}
j-节点数量 -第i个元素
j=i;
if(p==null)
{
return 0;
}else
{
e=p->data;
return 1;
}


}

5.按值查找运算算法

1	`在单链表L中从第一个数据结点开始查找第一个值域与e相等的结点，若存在这样的结点，则返回其逻辑序号；否则返回0。`

int Locate(SLinkNode *L,ElemType e)	
{  
SLinkNode *p=L->next;
int j=1;
while(p!=null &&p->data!=e)
{
p=p.next;
j++;

}
if(p==null)
{
rerturn -1;
}
return j;
}

6.插入元素运算算法

在单链表L中插入第i个值为x的结点。
先在单链表L中查找第i-1个结点，若未找到返回0；
找到后由p指向该结点，创建一个以x为值的新结点s，将其插入到p指结点之后。

439df81a0b8ea9dfe5d48ad618bad001

头插

尾插

中间插

int InsElem(SLinkNode *&L,ElemType x,int i)	
{  int j=0;
   SLinkNode *p=L,*s;
   if (i<=0) return 0;	  //参数i错误返回0
   while (p!=NULL && j<i-1)	  //查找第i-1个结点p
   {	j++;
	p=p->next;
   }
   //找到替换位置指针
   if (p==NULL)
      return 0;		  //未找到第i-1个结点时返回0
   else				  //找到第i-1个结点p
   {	s=(SLinkNode *)malloc(sizeof(SLinkNode));
	s->data=x;		  //创建存放元素x的新结点s
	s->next=p->next;	  //将s结点插入到p结点之后
	p->next=s;
	return 1;		  //插入运算成功,返回1
   }
}

7.删除操作

中间删

d483479c3492507a1d6036710c6ec846

int DelElem(SLinkNode *&L,int i)
{  int j=0;
   SLinkNode *p=L,*q;
   if (i<=0) return 0;	  //参数i错误返回0
   while (p!=NULL && j<i-1)	  //查找第i-1个结点
   {	j++;
	p=p->next;
   }
   if (p==NULL) return 0;	  //未找到第i-1个结点时返回0
   else				  //找到第i-1个结点p
   {	q=p->next;		  //q指向被删结点
	if (q==NULL) return 0;  //没有第i个结点时返回0
	else
	{   p->next=q->next;	  //从单链表中删除q结点
	　　free(q);		  //释放其空间
	　　return 1;
	}
   }
}

8.输出线性表运算算法

1	`从第一个数据结点开始，沿next域逐个往下遍历，输出每个遍历到结点的data域，直到尾结点为止。`

void DispList(SLinkNode *L)
{  SLinkNode *p=L->next;
   while (p!=NULL)
   {	printf("%d ",p->data);
	p=p->next;
   }
   printf("\n");
}

整体创建单链表的算法

可以通过调用基本运算算法来创建单链表，其过程是先初始化一个单链表，然后向其中一个一个地插入元素。
这里介绍是快速创建整个单链表的算法，也称为整体建表。
假设给定一个含有n个元素的数组a，由它来创建单链表，这种建立单链表的常用方法有两种。

1.头插

从一个空单链表（含有一个L指向的头结点）开始。
读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到新结点的数据域中。
将新结点s插入到当前链表的表头上。
再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到单链表L中，直到数组a中所有元素读完为止。

void CreateListF(SLinkNode *&L,ElemType a[],int n)
{  SLinkNode *s;  int i;
   L=(SLinkNode *)malloc(sizeof(SLinkNode));//创建头结点
   L->next=NULL;	//头结点的next域置空，表示一个空单链表
   for (i=0;i<n;i++)		//遍历a数组所有元素
   {	s=(SLinkNode *)malloc(sizeof(SLinkNode));
	s->data=a[i];		//创建存放a[i]元素的新结点s
	s->next=L->next;	//将s插在头结点之后
	L->next=s;
   }
}

86120495f4b2c71b0d16a605c858d0cf

2.尾插

从一个空单链表（含有一个L指向的头结点）开始。
读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到新结点的数据域中。
将新结点s插入到当前链表的表尾上。
再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到单链表L中，直到数组a中所有元素读完为止。
由于尾插法算法每次将新结点插到当前链表的表尾上，为此增加一个尾指针tc，使其始终指向当前链表的尾结点。

void CreateListR(SLinkNode *&L,ElemType a[],int n)
{  SLinkNode *s,*tc;  int i;
   L=(SLinkNode *)malloc(sizeof(SLinkNode));  //创建头结点
   tc=L;		//tc始终指向尾结点,初始时指向头结点
   for (i=0;i<n;i++)
   {	s=(SLinkNode *)malloc(sizeof(SLinkNode));
	s->data=a[i];	//创建存放a[i]元素的新结点s
	tc->next=s;	//将s插入tc之后
	tc=s;
   }
   tc->next=NULL;	//尾结点next域置为NULL
}

单链表算法示例

1. 基于单链表基本操作的算法设计

2.11

2.13

2. 基于整体建表的算法设计

1
2
3

这类算法设计中需要根据条件产生新的结果单链表。
而创建结果单链表的方法有头插法和尾插法。

2.14

3. 有序单链表的二路归并算法

1
2
3

有序单链表是有序表的单链表存储结构，同样可以利用有序表元素的有序性提高相关算法的效率。
当数据采用单链表存储时，对应的二路归并就是单链表二路归并算法。

2.16

4. 单链表的排序

2.18

循环单链表

2.3.4.1 循环单链表定义

4253efe9dd66b03ed40ea343337ca5fd

2.3.1.2 算法定义

1.初始化线性表运算算法

1	`创建一个空的循环单链表，它只有头结点，由L指向它。该结点的next域指向该头结点，data域未设定任何值。`

void InitList(SLinkNode *&L)　　//L为引用型参数
{  L=(SLinkNode *)malloc(sizeof(SLinkNode));
   L->next=L;
}

2.销毁线性表运算算法

1	`一个循环单链表中的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间。`

void DestroyList(SLinkNode *&L)
{  SLinkNode *pre=L,*p=pre->next;
   while (p!=L)
   {	free(pre);
	pre=p; p=p->next;	//pre、p同步后移
   }
   free(pre);
}

3.求线性表的长度运算算法

设置一个整型变量i作为计数器，i初值为0，p初始时指向第一个结点。然后沿next域逐个往下移动，每移动一次，i值增1。当p所指结点为头结点时这一过程结束，i之值即为表长。

int GetLength(SLinkNode *L)
{  int i=0;
   SLinkNode *p=L->next;
   while (p!=L)
   {	i++;
	p=p->next;
   }
   return i;
}

4.求线性表中第i个元素运算算法

用p从头开始遍历循环单链表L中的结点（初值指向第一个数据结点），用计数器j累计遍历过的结点，其初值为1。
当p不为L且j<i时循环，p后移一个结点，j增1。
当循环结束时，若p指向头结点则表示查找失败返回0，否则p所指结点即为要找的结点，查找成功，算法返回1。

int GetElem(SLinkNode *L,int i,ElemType &e)
{  int j=1;
   SLinkNode *p=L->next;   	//p指向首结点，计数器j置为1
   if (i<=0) return 0;	//参数i错误返回0
   while (p!=L && j<i)	//找第i个结点p
   {	j++;
	p=p->next;
   }
   if (p==L) return 0;	//未找到返回0
   else
   {	e=p->data;
	return 1;		//找到后返回1
   }
}

5.按值查找运算算法

1
2
3

用i累计查找数据结点的个数，从第一个数据结点开始，由前往后依次比较单链表中各结点数据域的值。
若某结点数据域的值等于给定值x，则返回i；否则继续向后比较。
若整个单链表中没有这样的结点，则返回0。

int Locate(SLinkNode *L,ElemType x)	
{  int i=1;
   SLinkNode *p=L->next;
   while (p!=L && p->data!=x)	
                 //从第1个数据结点开始查找data域为x的结点
   {	p=p->next;
	i++;
   }
   if (p==L) return 0;   //未找到值为x的结点返回0
   else return i;	   //找到第一个值为x的结点返回其序号
}

6.插入元素运算算法

在循环单链表L中查找第i个结点p及其前驱结点pre。
若没有这样的结点p返回0。
否则创建一个以x为值的新结点s，将结点s插入在pre结点之后，返回1。

int InsElem(SLinkNode *&L,ElemType x,int i)	//插入结点算法
{  int j=1;
   SLinkNode *pre=L,*p=pre->next,*s;
   if (i<=0) return 0;	//参数i错误返回0
   while (p!=L && j<i)	//查找第i个结点p和其前驱结点pre
   {	j++;
	pre=p; p=p->next;	//pre、p同步后移一个结点
   }
   if (p==L && i>j+1) return 0;//参数i>n+1时错误返回0
   else				//成功查找到第i个结点的前驱结点pre
   {	s=(SLinkNode *)malloc(sizeof(SLinkNode));
	s->data=x;		//创建新结点用于存放元素x
	s->next=pre->next;	//将s结点插入到pre结点之后
	pre->next=s;
	return 1;		//插入运算成功,返回1
   }
}

1
2
3

在循环链表中，用p指针扫描所有结点时，方式有两种：
以p!=L作为循环条件，当p==L时循环结束，此时p回过来指向头结点，所以p应该初始化指向第一个数据结点而不是头结点，否则循环内的语句不会执行。
扫描指针p的初始化为p=L，循环的条件应该为p->next!=L，当p->next==L时循环结束，此时p指向尾结点

7.删除元素运算算法

1
2

在循环单链表L中查找第i-1个结点，若不存在这样的结点返回0。
否则让p指第i-1个结点，q指向后继结点，当q为NULL时返回0，否则将q所指结点删除并释放其空间，返回1

int DelElem(SLinkNode *&L,int i)
{  int j=0;
   SLinkNode *p=L,*q;
   if (i<=0) return 0;		//参数i错误返回0
   while (p->next!=L && j<i-1)	//查找第i-1个结点p
   {	j++;
	p=p->next;
   }
   if (p->next==L) return 0;		//未找到这样的结点返回0
   else
   {	q=p->next;			//q指向被删结点
	if (q==L) return 0;		//没有第i个结点时返回0
	else
	{   p->next=q->next;		//从单链表中删除q结点
	　　free(q);			//释放其空间
	　　return 1;			//成功删除返回1
	}
   }
}

8.输出线性表运算算法

1	`从第一个数据结点开始，沿next域逐个往下遍历，输出每个遍历到结点的data域，直到头结点为止。`

void DispList(SLinkNode *L)
{  SLinkNode *p=L->next;
   while (p!=L)
   {	printf("%d ",p->data);
	p=p->next;
   }
   printf("\n");
}

2.3.5 循环单链表算法

2.19

2.20

2.21

数据结构

数据结构-线性表-单链表02

http://example.com/2024/09/19/数据结构线性表-链表/

作者

John Doe

发布于

2024年9月19日

许可协议

微服务Spring Cloude 上一篇

数据结构-线性表-顺序表01 下一篇