王道数据结构—单链表的建立
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
int data;
struct LNode* next;
}LNode,*LinkList;
//带头结点 尾插法建立单链表
LinkList List_TailInsert(LinkList& L)
{
//初始化链表
L = (LNode*)malloc(sizeof(LNode));
//输入插入的数据
int x;
scanf("%d", &x);
//s:一个辅助指针用于插入数据
//r:一个指针用于指向最后一个结点
LNode* s, * r = L;
while (x != 9999) {//截止循环的条件
s = (LNode*)malloc(sizeof(LNode));//指向一个结点的空间
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return L;
}
//不带头结点 尾插法建立单链表
LinkList List_TailInsert(LinkList& L)
{
//初始化链表
L = NULL;
//输入插入的数
int x;
scanf("%d", &x);
//s:一个辅助指针用于插入数据
//r:一个指针用于指向最后一个结点
LNode* s, * r = NULL;//(注意:此时r初始化为NULL)
while (x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
if (L == NULL)
L = s;//更新头指针
else
r->next = s;
r = s;//更新r的值,r仍指向链表尾部
scanf("%d", &x);
}
r->next = NULL;
return L;
}
//对比头插法和尾插法,为什么尾插法不需要显式地写 L->next = NULL;
//隐含的初始化:
//在第一次插入节点时,r->next = s; 实际上已经将 L->next 设置为 s,这意味着 L->next 被初始化为链表的第一个实际数据节点。因此,即使没有显式地写 L->next = NULL; ,L->next 也会在第一次插入节点时被正确初始化。
//带头结点 头插法建立单链表
LinkList List_HeadInsert(LinkList& L)
{
//初始化单链表
L = (LNode*)malloc(sizeof(LNode));
L->next = NULL;
//输入插入的数据
int x;
scanf("%d", &x);
//s:一个辅助指针用于插入数据
LNode* s;
while (x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
//不带头结点 头插法建立单链表
LinkList List_HeadInsert(LinkList& L)
{
//初始化单链表
L = NULL;
//输入插入的数据
int x;
scanf("%d", &x);
//s:一个辅助指针用于插入数据
LNode* s,*r;
while (x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L;
L = s;
scanf("%d", &x);
}
return L;
}
//链表的逆置(反转)
//方法1:头插法
//带头结点
LinkList List_Reserve(LinkList& L)
{
//判断链表是否为空
if (L == NULL || L->next == NULL)
return L;
//p:一个辅助指针指向当前结点
//q:一个辅助指针指向当前结点的后继结点,防止链断
LNode* p;
LNode* q;
//初始化
p = L->next;//指向第一个结点
L->next = NULL;//断开与后面结点的联系
//依次将结点摘下重新头插
while (p != NULL){
q = p->next;//暂存p的后继
//头插
p->next = L->next;
L->next = p;
p = q;//更新p结点
}
return L;
}
//方法二:原地逆置:不借助额外的内存空间O(1)的空间复杂度
LinkList List_Resreve(LinkList& L)
{
//判断链表是否为空
if (L == NULL || L->next == NULL)
return L;
//beg:一个辅助指针指向当前结点
//end:一个辅助指针指向当前结点的后继结点,防止链断
LNode* beg;
LNode* end;
//初始化
beg = L->next// beg 指向链表的第一个实际数据节点
end = L->next->next;// end 指向 beg 的后继节点
//依次将结点原地逆置
while (end != NULL) {
beg->next = end->next;// 保存 end 的后继节点
end->next = L->next;// 将 end 插入到头节点之后
L->next = end;// 更新头节点的 next 指针
end = beg->next; // 更新 end 指针,指向下一个待处理的节点
}
return L;
}
标签:插法,结点,带头,LNode,next,LinkList,end,NULL
From: https://blog.csdn.net/2301_79912259/article/details/142851247