0、节点结构体定义
typedef struct LNode{
int data;
struct LNode *next;
} Lnode, *LinkList;
1、初始化
bool InitList(LinkList &L) //初始化
{
L = new LNode;
if(!L){
return false;
}
L->next = NULL;
return true;
}
2、创建
(1)头插法
void CreateList_H(LinkList &L, int n) //头插法创建
{
LinkList s;
while(n--){ //--n不行!!
s = new LNode;
cin>> s->data;
s->next = L->next; //链表的i++
L->next =s;
}
}
//反复利用链表头L和新节点s添加(就是插入...)
(2)尾插法
void CreateList_R(LinkList &L, int n) //尾插法创建
{
LinkList s, r = L;
while(--n){
s = new LNode;
cin>> s->data;
r->next = s; //链表的i++
s->next = NULL;
r = s;
}
}
//利用r存储当前节点信息,便利于新节点s的添加
3、查找
(1)查找具体元素
bool Finde(LinkList &L, int e) //查找具体元素
{
LinkList p = L->next;
while(p != NULL && p->data != e){
p = p->next;
}
if(!p){
return false;
}
return true;
}
(2)查找第 i 个元素
bool GetElemi(LinkList &L, int i, int &e) //查找第i个元素
{
int j = 1; //记不住就初始化为 j = 1、p = L
LinkList p = L->next; //因为后面都是这样(保对),而且也没增加什么时间
while(p && j<i){
p = p->next;
++j;
}
if(!p || j>i){ //i值不合法:i>n || i<0
return false;
}
e = p->data; //用e记录元素i
return true;
}
4、插入
bool ListInsert(LinkList &L, int i, int e) //在第i个元素后插入元素
{
int j = 0;
LinkList p = L; //保证能在第一个元素前插入
while(p && j<i){
p = p->next;
++j;
}
if(!p || j>i){
return false;
}
//上面就是查找操作...
LinkList s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
5、删除
bool ListDelete(LinkList &L, int i) //删除第i个元素
{
int j = 0;
LinkList p = L; //保证能删除第 1个元素
while(p && j<i-1){
p = p->next;
++j;
}
if(!p ||j>i-1){
return false;
}
//上面还是查找操作...(找第元素i-1)
LinkList q = p->next; //使用临时变量更安全!(p->next->next = p->next; delete p->next;
p->next = q->next; //当n=2时会出错!因为要删除的p->next已经变成NULL了!)
delete q;
return true;
}
6、释放内存
bool ListRelese(LinkList &L)
{
LinkList p;
while(L){
p = L; //暂存当前节点
L = L->next; //更新为下一节点
delete p; //删除当前节点
/*这样也ok:
**p = L->next;// 暂存下一个节点
**delete L;// 删除当前节点
**L = p;// 更新当前节点为下一个节点
*/
}
return true;
}
7、其他操作
(1)查找中间元素
LinkList FindMid(LinkList L) //查找中间的节点
{ //不会修改L就不用传引用!
LinkList p = L, q = L;
while(p){
q = q->next;
p = p->next->next;
}
return q;
}
(2)查找倒数第 k 个节点
LinkList Findk(LinkList L, int k) //查找倒数第k个节点
{
LinkList p, q;
p=L->next;
q=L->next;
while(p->next!=NULL)
{
if(--k<=0) //k减到0时,慢指针开始走
q=q->next;
p=p->next; //p为快指针,先走k-1步
}
if(k>0)
return NULL;
else
return q;
}
(3)合并有序链表文章来源:https://www.toymoban.com/news/detail-667115.html
/合并有序链表:将两个有序(非递减)单链表La和Lb合并为一个新的有序(非递减)单链表Lc
LinkList ListMerge(LinkList LA, LinkList LB)
{
LinkList p = LA->next ,q = LB->next;
LinkList LC = LA, r = LC;
while(p && q){
if(p->data > q->data){
r->next = q;
r = q;
q = q->next;
}else{
r->next = p;
r = p;
p = p->next;
}
}
r->next = p? p:q;
delete LB;
return LC;
}
(4)逆转链表文章来源地址https://www.toymoban.com/news/detail-667115.html
void ListReverse(LinkList &L) //逆转单链表
{
LinkList p = L->next, q;
L->next = NULL;
while(p){
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
到了这里,关于单链表Single-LinkList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!