数据结构之单链表的表⽰和基本操作
【数据结构】单链表的基本操作
⼀、基本概念
1、结点的类型定义（数据元素的映像）
（1）结点：由数据域和指针域构成。
（2）结点在C语⾔中的结构定义
Typedef  ElemType  int ;            //或其他数据类型
typedef struct Node
{
ElemType data;                //结点的数据域
struct Node*next;            //结点的指针域，⽤结点类型指针定义结点指针域
}Node,*LinkList;
2、单链表
（1）什么是单链表
⽤⼀组任意的存储单元存放线性表的结点，每个结点的唯⼀后继依靠结点的指针维持逻辑上相邻的元素。
（2）特点：数据元素在逻辑上相邻，存储位置不⼀定相邻。
3、⾸元结点：链表中第⼀个元素所在的结点
4、头结点：链表中在⾸元结点之前的结点，可有可⽆，有头结点便于运算。 头结点的数据域不包括任何信息。
5、头指针：指向第⼀个结点。
6、头指针、头结点、⾸元结点之间的关系
（1）带头结点的链表中，头指针指向头结点的指针域（如、L->next），头结点的指针域指向⾸元结点。
（2）⽆头结点的指针域的链表中，头指针的指针域指向⾸元结点。
7、由头结点退带头结点的链表进⾏判空
（1）带头结点的空链表
L->NULL;//L==NULL，则为空链表
(2)、带头结点的⾮空链表
L->next;//L!=NULL，则链表不为空
8、头指针和头结点的区别
（1）头指针是⼀个指针，若有头结点，头指针指向头结点；若⽆头结点，头指针指向⾸元结点。
（2）头结点是⼀个实际存在的点，它包含数据域和指针域。
c语言listinsert函数（3）头指针只声明，⽽未分配存储空间，头指针进⾏了声明并分配了⼀个结点的实际物理空间。
⼆、单链表的基本操作
1、单链表的创建
单链表的创建有两种⽅式：头插法和尾插法
（1） 头插法创建单链表（⽣成的链表是逆序的）
原理： 从创建⼀个空表开始，重复读⼊数据，⽣成新的结点，将读⼊数据存放到新结点的数据域，然后将新的结点插⼊到当前链表的头结点之后。
基本操作：
1. 创建新结点，使⼀结点类型的指针指向该结点
2. 使头结点指向新结点（头结点指针域存储新节点位置信息）
3. 使新结点指向后⼀节点。
c语⾔实现：
Node *HeardCreateList（int length）
{
/*创建空链表*/
Nodet  *L=（Node*）malloc(sizeof(Node));//申请⼀个结点的空间
Node *s=L;
s->next=NULL;
/
*头插法创建链表*/
for(int i=1;i<=length;i++)
{
Node *temp=(Node*)mallo(sizeof(Node));//创建新结点
scanf("%d",&temp->data);
/*核⼼原理*/
temp->next=L->next;
L->next=temp;
}
return  L;
}
(2)尾插法创建单链表（⽣成的链表是正序的）
**原理：**从⼀个空链表开始，重复读⼊数据，⽣成新结点，将读⼊数据存放在新结点的数据与中，然后将新结点插⼊当前链表的表尾结点之后。
基本操作：
1. 创建新结点，使⼀结点类型指针指向该结点。
2. 使头结点指针指向新结点。
3. 使第i个结点指针，指向第i+1个结点。
在c语⾔中的表现：
Node *TailCreateList(int length)
{
//创建空链表
Node *L=(Node*)malloc(sizeof(Node));
Node *temp=L;
temp->next=NULL;
//创建单链表
for(int i=1;i<=length;i++)
{
Node *s=(Node*)malloc(sizeof(Node));
scanf("%d",&s->data);
/*核⼼原理*/
temp->next=s;
temp=s;
}
temp->next=NULL;
return(Node*)L;//创建完结点后，尾结点的指针域为空
}
2、单链表的取值（查询链表第i个结点的值）
与顺序表不同，单链表的存储结构是链式映像，不能同顺序映像的线性表⼀样对线性表进⾏随机访问。只能从链表的⾸元结点出法，顺着链域next逐个访问链表。
基本操作步骤：
1. ⽤指针p指向⾸元结点（p=L->next）
2. 从⾸元结点开始顺着链域逐个访问，当p不为空或者未到达该结点位置时执⾏下列循环：
指针盘的遍历，计数器j的⾃增。
3. 退出循环后，通过p和j来判断，第i个结点是否在链表中。（p为空或者j<i）
代码：
ElemType GetElem(LinkList L,int i, ElemType e)
{
LNode *p = L->next;
int j =1;
while(p&&j < i)//Walk through the list until P is empty or you find the ith node
{
p = p->next;
++j;
}
if(!p || j < i)//"i" is not on the list
printf("i is not on the list.\n");
e = p->data;
return e;
}
3、查
从⾸元结点出发，逐个对⽐结点的数据域的值是否等于特定值。
（1）查第⼀个值为特定值的结点。
LinkList LoateElem(LinkList L, ElemType e)
{
LNode *p = L->next;//Start with the first node
int i =1;
while(p && p->data == e)
{
p = p->next;
++i;
}
if(!p)
printf("There is no node with data e in the list.\n");
printf("The data at the '%d'th node is %d.\n",i,e);
return p;
}
（2）查所有数据域为特定值的结点
LinkList LoateElem(LinkList L, ElemType e)
{
LNode *p = L->next;//Start with the first node
int i =1;
while(p && p->data == e)
{
p = p->next;
++i;
}
if(!p)
printf("There is no node with data e in the list.\n");
printf("The data at the '%d'th node is %d.\n",i,e);
return p;
}
4、插⼊
基本步骤:
到插⼊位置的前驱。
创建新结点。
使新结点的指针域存储前驱指针域数据。
前驱指针域指向新结点指针。
Status ListInsert(LinkList L,int i, ElemType e)
{//Insert the node at the ith position of the list with lead node. LNode *p = L;
int j =0;
while(p &&(j < i -1))
{
p = p->next;
++j;
}
if(!p || j >(i -1))
return ERROR;
LNode *temp =(LNode*)malloc(sizeof(LNode));
temp->data = e;
temp->next = p->next;
p->next = temp;
return OK;
}
5、删除
基本步骤：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。