创建链表:页眉插入与页尾插入
最编程
2024-06-11 13:26:55
...
两种方法的区别无非是插入的位置: 头插法:新插入结点始终未当前的第一个结点 尾插法:新插入结点始终为当前的最后一个结点
头插法建表
实现代码:
//头插法建链表
void HeadCreateList(LinkList L,int n)
{
int i;
srand(time(0)); //初始化随机数种子
L = (LinkList)malloc(sizeof(LNode));
L ->next = NULL;
LinkList p;
//利用循环生成结点并添加到单链表中
for(i = 0;i < n;i++)
{
p = (LinkList)malloc(sizeof(LNode)); //生产新结点
p ->data = rand()%100 + 1; //生产两位随机数100
p ->next = L ->next;
L ->next = p; //插到表头
}
}
尾插法建表
实现代码:
void TailCreateList(LinkList L,int n)
{
LinkList p,tail;
int i;
srand(time(0)); //初始化随机数种子
L = (LinkList)malloc(sizeof(LNode));
tail = L;
for(i = 0;i < n;i++)
{
p = (LinkList)malloc(sizeof(LNode)); //生产新结点
p ->data = rand()%100 + 1; //生产两位随机数100
tail ->next = p; //将表尾终端结点的指针指向新结点
tail = p; //将当前的新结点定义为表尾的尾结点
}
tail->next = NULL; //当前链表结束
}
有趣的算法:查找单链表的中间结点
就是给你一个单链表,要你获得单链表中位置中间的结点?你会怎么做? 一般我们可能用一个指针,从头到尾撸一遍,同时记录单链表的长度,然后再除以2得出第几 项为中间结点,然后再撸length / 2获得中间节点,重复遍历很繁琐,有没有其他的方法呢? 有,肯定有,这里提供一个简单的方法: 用两个不同的指针,按照不同的移动顺序来移动,这里我们暂且把他们成为快慢指针! 每次循环, 快指针向后移动两个结点: p = p -> next -> next; 慢指针向后移动一个结点: q = q -> next; 当快指针到达尾部的时候,慢指针不就指向中间结点了,你说是吧~ 原理非常简单,下面我们写下代码实现:
Status GetMidLNode(LinkList *L,ElemType *e)
{
LinkList p,q;
p = q = *L;
while(p ->next ->next != NULL)
{
if(p ->next ->next != NULL)
{
p = p ->next ->next;
q = q ->next;
}else{
p = p ->next;
}
}
e = q ->data;
return OK;
}
12种基础基本操作代码实现
从本节开始就不像上一节一样一步步地讲解了,直接上代码,难点部分会写下注释!
1)构造空表
void InitList(LinkList L)
{
L = (LinkList)malloc(sizeof(LNode));
if(!L)exit(ERROR);
L ->next = NULL;
}
2)将链表置为空表
void ClearList(LinkList L)
{
LinkList p = L ->next;
L ->next = NULL;
//接着就是释放头结点以外的结点了
while(p)
{
p = L->next;
free(L); //释放首元结点
L = p; //移动到当前的首元结点
}
}
3)判断是否为空表
这里要区分两种情况:
有头结点:L -> next = NULL;此时表为空表! 无头结点:L = NULL;此时为空表!
Status ListEmpty(LinkList L)
{
//有头节点的情况,只需判断头结点的指针域是否为空即可
if(L ->next)return FALSE;
else return TRUE;
}
4)销毁单链表
void DestoryList(LinkList L)
{
LinkList q;
//删除头结点外的结点
while(L)
{
//指向首元结点,而不是头结点
q = L ->next;
free(L);
L = q; //删除后指向首元
}
}
5)获得表长度
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L ->next;
while(p)
{
i++;
p = p ->next;
}
return i;
}
6)获得表中第i个元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
int j = 1;
//指向首元,然后依次后移,假如到了结尾或者j的值大于i
//还没找个改元素说明i不合法
LinkList p = L ->next;
while(p && j < i)
{
j++;
p = p ->next;
}
if(!p || j> i)return ERROR;
e = p ->data;
return OK;
}
7)查找表中是否存在满足条件的元素
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
int i = 0;
LinkList p = L -> next;
while(p)
{
i++;
if(compare(p->data,e))return i;
p = p -> next;
}
return 0;
}
8)获得某个结点的直接前驱
Status BeforeElem(LinkList L,ElemType choose,ElemType *before)
{
LinkList q,p = L ->next;
while(p ->next)
{
q = p ->next;
//判断p的后继是否为choose,是的话返回OK,否则继续后移
if(q ->data == choose)
{
before = p ->data;
return OK;
}
p = q;
}
return ERROR;
}
9.获得某个结点的直接后继
Status NextElem(LinkList L,ElemType choose,ElemType *behind)
{
LinkList p = L ->next;
while(p ->next)
{
if(p ->data == choose)
{
behind = p ->next ->data;
return OK;
}
p = p ->next;
}
return ERROR;
}
10.往表中第i个位置插入元素
Status ListInsert(LinkList L,int i,ElemType e)
{
int j = 0;
LinkList p,q =L; //让q指向头结点
while(p && j < i - 1)
{
j++;
p = p ->next; //p指向下一个节点
}
if(!p || j > i - 1)return ERROR;
p = (LinkList)malloc(sizeof(LNode));
//要先让插入的结点的指针域指向插入位置的后继结点
//再让插入节点的前驱的指针域指向插入结点
//!!!顺序不能乱哦1
p ->data = e;
p ->next = q ->next;
q ->next = p;
return OK;
}
11.删除表中第i个元素
Status ListDelete(LinkList L,int i,ElemType *e)
{
int j = 0;
LinkList p,q = L;
while(q ->next && j < i -1)
{
j++;
q = q->next;
}
if(!q || j >i -1)return ERROR;
p = q ->next; //指向准备删除的结点
q ->next = p ->next; //删除结点的前驱的指针域指向删除结点的后继
e = p ->data;
free(p); //释放要删除的结点
return OK;
}
12.遍历单链表中的所有元素
void ListTraverser(LinkList L,void(*visit)(ElemType))
{
LinkList p = L ->next;
while(p)
{
visit(p ->data);
p = p ->next;
}
printf("\n");
}
参考:https://www.it610.com/article/1277924529858953216.htm
推荐阅读
-
创建链表:表头和表尾插入方法
-
创建链表 "表头插入 "和 "表尾插入 "方法详情
-
创建链表:页眉插入与页尾插入
-
单链表的表头插入与表尾插入,你真的明白吗?
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
数据结构与算法 - 链表(表头插入、表尾插入、循环链表)
-
创建链表(表头插入、表尾插入)
-
创建链表--表头插入、表尾插入--有无表头节点
-
链表操作(创建空链表、插入表头、插入表尾、反转链表、修改、删除链表元素、获取链表元素的位置)
-
插入页眉和页尾--最好通过查看代码在纸上模拟这一过程。