线性表之《链表的表示及基本操作的实现》


线性表之《链表的表示及基本操作的实现》

目录
线性表之《链表的表示及基本操作的实现》一、单链表(一)单链表的描述(一)单链表的操作实现1、初始化2、查找3、插入4、删除5、单链表的建立(前插法)6、单链表的建立(后插法)

二、循环链表三、双向链表1、插入1、删除

一、单链表
(一)单链表的描述

typedef struct LNode {
ElemType data;//结点数据域
struct LNode* next;//结点指针域
}LNode ,*LinkList;

变量定义:
LNode* p, * q LinkList L;
p, q, L都是指针变量,* p, * q, * L都是结点变量

指针变量p : 表示结点地址
结点变量* p:表示一个结点

p->data;//表示数据域
p->next;//表示指针域

typedef struct LNode {
ElemType data;//结点数据域
struct LNode* next;//结点指针域
}LNode ,*LinkList;

LinkList p, s, L;//指针变量的定义
L = new LNode;//为指针变量L分配内存空间
p = L;//p指向头结点
s = L->next;//s指向首元结点

(一)单链表的操作实现
1、初始化

算法思想:
(1)、生成新结点作为头结点,用头指针L指向头结点
(2)、头结点的指针域置为空

/*初始化*/
Status InitList(LinkList& L)
{
L = new LNode;//生成新结点作为头结点,用头指针L指向头结点
L->next = NULL;//头结点的指针域置为空
return OK;
}

2、查找

线性表之《链表的表示及基本操作的实现》

算法思想:
(1)、初始化,p指向第一个结点,j为计数器
(2)、从链表头依次向后扫描,直到p为空或p指向第i个元素
(3)、更新p指向当前结点,计数器+1
(4)、i 值不合法(i<=0或者i>n)
(5)、取第i个结点的数据域

/*按序号查找*/
Status GetElem(LinkList L, int i, ElemType& e)
{
LinkList p;
int j;
p = L->next;j = 1;//初始化,p指向第一个结点,j为计数器
while (p && j < i)//从链表头依次向后扫描,直到p为空或p指向第i个元素
{
p = p->next;//更新p指向当前结点
++j;//计数器+1
}
if (!p || j > i) return ERROR;//i 值不合法(i<=0或者i>n)
e = p->data;//取第i个结点的数据域
return OK;
}

3、插入

线性表之《链表的表示及基本操作的实现》

算法思想:
(1)找到a i - 1的存储位置p
(2)生成一个新结点 * s
(3)将新结点 * s的数据域置为e
(4)新结点 * s的指针域指向a i
(5)结点p指针域指向结点s

/*插入*/
Status ListInsert(LinkList & L, int i, ElemType e)
{
p = L;
int j = 0;
while (p && j < i - 1)//寻找第i - 1个结点
{
p = p->next;//指向当前结点
++j;
}
if (!p || j > i - 1) return ERROR;//i值不合法
LinkList s;
s = new LNode;//生成新结点s
s->data = e;//新结点的数据域置为e
s->next = p->next;//新结点 * s的指针域指向a i
p->next = s;//结点*p指针域指向结点*s
return OK;
}

4、删除

线性表之《链表的表示及基本操作的实现》

算法思想:
(1)查找结点a i-1所在位置,并由指针p指向该结点
(2)临时保存待删除结点ai的地址在q中,以备释放
(3)将结点*p指向结点ai的直接后继结点
(4)释放结点ai的空间

Status LinkDelete(LinkList & L, int i)
{
p = L;
j = 0;
while (p->next && j < i - 1)//寻找第i-1个结点
{
p = p->next;
++j;
}
if (!(p->next) || j > i - 1) return ERROR;
q = p->next;//临时保存待删除结点ai的地址在q中,以备释放
p->next = q->next;//将结点*p指向结点ai的直接后继结点
delete q;//释放结点ai的空间
return OK;
}

5、单链表的建立(前插法)

线性表之《链表的表示及基本操作的实现》

描述:前插法是通过将新结点逐个插入链表的头部(头结点之后)来创建链表,每次申请一个新结点,读入相应的数据元素值,然后将新结点插入到头结点之后。

算法思想
(1)创建一个只有头结点的空链表。
(2)根据待创建链表包括的元素个数n,循环n次执行以下操作:
1、生成一个新结点p;
2、输入元素值赋值给新结点
p的数据域;
3、将新结点*p插入到头结点之后。

/*单链表的建立(前插法)*/
void CreateList(LinkList& L, int n)
{
L = new LNode;//建立一个带头结点的空链表
L->next = NULL;

for (i = n;i > 0;--i)//循环插入新结点
{
p = new LNode;//生成新结点*p
scanf_s("%d", &p->data);//输入元素赋值给p->data
p->next = L->next;//将新结点*p插入到头结点后
L->next = p;
}
}

6、单链表的建立(后插法)

线性表之《链表的表示及基本操作的实现》

描述:后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样,每次申请一个新结点,读入相应数据元素值。不同的是,为了使新结点能够插入到表尾,需要增加一个尾指针r指向链表的尾结点。

算法思想:
(1)创建一个只有头结点的空链表
(2)尾指针r初始化,指向头结点
(3)根据创建链表包括的元素个数n,循环n次执行以下操作:
1、生成一个新结点p;
2、输入元素值赋给新结点
p的数据域
3、将新结点p插入到尾结点r之后;
4、尾指针r指向新的尾结点*p.

/*单链表的建立(后插法)*/
void CreateList(LinkList& L, int n)
{
L = new LNode;//建立带头结点的空链表
L->next = NULL;
r = L;//尾指针指向头结点

for (i = 0;i < n;i++)
{
p = new LNode;//生成新结点p
scanf_s("%d", &p->data);//输入数据域
p->next = NULL;
r->next = p;//插入到尾表
r = p;//r指向新的尾结点
}
}

二、循环链表

特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
线性表之《链表的表示及基本操作的实现》
从循环链表中的任何一个结点的位置都可以找到其他所有的结点,而单链表做不到,循环链表中没有明显的尾端。

线性表之《链表的表示及基本操作的实现》
实现

p->next = B->next;
B->next = A->next;
A->next = p->next;
delete p;
A = B;

三、双向链表

有两个指针域的链表,称为双链表

/*双向链表的存储结构*/
typedef struct DuLNode {
ElemType data;//数据域
struct DuLNode *prior;//前指针域
struct DuLNode* next;//后指针域
}DuLNode,*DuLinkLst;

线性表之《链表的表示及基本操作的实现》

1、插入

线性表之《链表的表示及基本操作的实现》

/*双向链表的插入*/
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e)
{
if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
retrun ERROR;//p为NULL时,第i个元素不存在
s = new DuLNode;//生成一个新结点s
s->data = e;//将数据e存入到结点s的数据域data中
s->prior = p->prior;//将结点s的前指针指向前一个结点
p->prior->next = s;//将前一个结点的后指针指向新结点s
s->next = p;//新结点s的后指针指向p
p->prior = s;//p的前指针指向新结点
return OK;
}

1、删除

线性表之《链表的表示及基本操作的实现》

/*双向链表的删除*/
Status ListDelete_DuL(DuLinkList& L, int i, ElemType &e)
{
if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
retrun ERROR;//p为NULL时,第i个元素不存在
e = p->data;//保存被删除结点的数据域
p->prior->next = p->next;//修改被删除结点的前驱结点的后继指针
p->next->prior = p->prior;//修改被删除结点的后继结点的前驱指针
delete p;//释放被删除结点的空间
return OK;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

线性表之《链表的表示及基本操作的实现》

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 线性表之《链表的表示及基本操作的实现》
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏