没有合适的资源？快使用搜索试试~ 我知道了~

文库首页前端Node.js《数据结构与算法》讲义.docx

《数据结构与算法》讲义.docx

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

0 下载量 95 浏览量 2022-07-12 18:21:04 上传评论收藏 1018KB DOCX 举报

温馨提示

试读

31页

《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx《数据结构与算法》讲义.docx

资源详情

资源评论

资源推荐

《数据结构》

实验课讲义

实验一线性表基本操作的实现

1.1 单链表的运算

1、建立单链表

假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符''

为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：

（1）头插法建表

① 算法思路

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后

将新结点插入到当前链表的表头上,直到读入结束标志为止。

注意：该方法生成的链表的结点次序与输入顺序相反。

② 具体算法实现

LinkList CreatListF(void)

{//返回单链表的头指针

char ch;

LinkList head;//头指针

ListNode *s; //工作指针

head=NULL;

//链表开始为空

ch=getchar(); //读入第 1 个字符

while(ch!='\n'){

s=(ListNode *)malloc(sizeof(ListNode));//生成新结点

s->data=ch; //将读入的数据放入新结点的数据域中

s->next=head;

head=s;

ch=getchar(); //读入下一字符

}

return head;

}

（2）尾插法建表

① 算法思路

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后

将新结点插入到当前链表的表尾上,直到读入结束标志为止。

② 具体算法实现

LinkList CreatListR(void)

{//返回单链表的头指针

char ch;

LinkList head;//头指针

ListNode *s,*r; //工作指针

head=NULL;

//链表开始为空

r=NULL;//尾指针初值为空

ch=getchar(); //读入第 1 个字符

while(ch!='\n'){

s=(ListNode *)malloc(sizeof(ListNode));//生成新结点

s->data=ch; //将读入的数据放入新结点的数据域中

if (head!=NULL)

head=s;//新结点插入空表

else

r->next=s;//将新结点插到*r 之后

r=s;//尾指针指向新表尾

ch=getchar(); //读入下一字符

}//endwhile

if (r!=NULL)

r->next=NULL;//对于非空表，将尾结点指针域置空 head=s;

return head;

}

2.插入运算

（1）思想方法

插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之

间。

具体步骤：

（1）找到 ai-1 存储位置 p

（2）生成一个数据域为 x 的新结点*s

（3）令结点*p 的指针域指向新结点

（4）新结点的指针域指向结点 ai。

（2）具体算法实现

void InsertList(LinkList head,DataType x,int i)

{//将值为 x 的新结点插入到带头结点的单链表 head 的第 i 个结点的位置上

ListNode *p;

p=GetNode(head,i-1);//寻找第 i-1 个结点

if (p==NULL)//i<1 或 i>n+1 时插入位置 i 有错

Error("position error")；

s=(ListNode *)malloc(sizeof(ListNode));

s->data=x;s->next=p->next;p->next=s;

}

（3）算法分析

算法的时间主要耗费在查找操作 GetNode 上，故时间复杂度亦为 O(n)。

3.删除运算

（1）思想方法

删除运算是将表的第 i 个结点删去。

具体步骤：

（1）找到ai-1 的存储位置 p（因为在单链表中结点 ai 的存储地址是在其直接前趋结点

ai-1 的指针域 next 中）

（2）令 p-＞next 指向 ai 的直接后继结点（即把 ai 从链上摘下）

（3）释放结点 ai 的空间，将其归还给"存储池"。

（2）具体算法实现

void DeleteList(LinkList head,int i)

{//删除带头结点的单链表 head 上的第 i 个结点

ListNode *p,*r;

p=GetNode(head,i-1);//找到第 i-1 个结点

if (p==NULL||p->next==NULL)//i<1或 i>n 时，删除位置错

Error("position error");//退出程序运行

r=p->next;//使 r 指向被删除的结点 ai

p->next=r->next;//将 ai 从链上摘下

free(r);//释放结点 ai 的空间给存储池

}

2.3.3 循环链表（Circular Linked List）

循环链表是一种首尾相接的链表。

1、循环链表

（1）单循环链表——在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开

始结点即可。

（2）多重链的循环链表——将表中结点链在多个环上。

2、带头结点的单循环链表

注意：判断空链表的条件是 head==head->next;

3、仅设尾指针的单循环链表

用尾指针 rear 表示的单循环链表对开始结点 a1 和终端结点 an 查找时间都是 O(1)。而

表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾

指针的单循环链表可见下图。

剩余30页未读，继续阅读

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

xxpr_ybgg

粉丝: 6449
资源: 3万+

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

《数据结构与算法》讲义.docx

评论0

最新资源

《数据结构与算法》讲义.docx

评论0

数据结构与算法图解.docx

Python数据结构与算法分析.docx

新闻流实时话题挖掘框架与算法研究 .docx

《数据结构》实验讲义.docx

数据结构经典算法试题.docx

《数据结构实验》讲义.docx

数据结构与算法串.docx

前端面试数据结构与算法类.docx

第九章-数据结构与算法基础.docx

面试题集，包含Android、Java、数据结构、算法等.docx

Python中级-数据结构与算法分析.docx

数据结构模拟试卷.docx

基于微信小程序的数据结构学习平台设计.docx

MySQL索引背后的数据结构及算法原理.docx

学习笔记5：数据预处理与数据挖掘十大经典算法.docx

人工智能小型专家系统的设计与实现解读上课讲义.docx

武汉理工大学数据结构与算法综合实验图与景区信息管理系统.docx

《数据结构与算法.docx

武汉理工大学数据结构及算法综合实验连连看.docx

KepOPC DA2UA实现从OPCDA到OPCUA的转换及读写互操作

Midjourney-关键词大全

“未来工厂”建设导则.pdf

2024年Java基础面试题，附带详细解析答案

腾讯QQ秀立项调研PPT

5G介绍PPT.pptx

各省互联网普及率（1997-2020）

2024年最新最全面的Java后端面试资料

海盗派测试分析.pdf

CHATGPT训练指令模板.docx

最新资源