北京文都2023考研全年集训营

考试资讯

咨询热线8:00-24:00 400-0999-680

首页 考试资讯考研专业课 2023计算机考研408数据结构知识:线性表的链式表示

2023计算机考研408数据结构知识:线性表的链式表示

时间:2021-11-18 13:36:34 编辑:leichenchen

      计算机考研专业课,很多学校以408为主!接下来,小编为帮助备考2023计算机考研408的学子们,在头脑中有一个专业课思维框架,特意精心为大家整理出-计算机考研408数据结构知识:线性表的链式表示,供考生参考。

2023计算机考研408数据结构知识:线性表的链式表示

2023计算机考研408数据结构知识:线性表的链式表示

一、单链表的定义

特点: 浪费空间,非随机存取

头指针和头结点区别:不管带不带头结点,头指针始终指向链表的第一个结点;头结点是带头结点的链表中的第一个结点,通常不存储信息;在链表第一个位置上的操作和其他位置上的一致。

引入头结点的优点:无论链表是否为空,头指针都指向头结点的非空指针,空表和非空表处理一致

二、单链表上基本操作的实现

头插法建立链表;尾插法建立链表;按序号查找结点值;按值查找表结点;插入结点操作;删除结点操作;求表长操作

三、双链表

双链表中结点类型的描述;插入操作;删除操作

四、循环链表

循环单链表;循环双链表

五、静态链表

定义: 用数组描述链式存储结构,也有数据域和指针域.指针是结点的相对地址(数组下标),又称游标

结束标志: next==-1

注意:和顺序表一样,也要预先分配一块连续的内存空间;插入和删除只需要修改指针,不需要移动元素;在不支持指针的语言(Basic)中很巧妙

六、顺序表和链表的比较

1.存取方式

顺序表可顺序存取,可随机存取。链表只能从表头顺序存取

2.逻辑结构与物理结构

3.查找,插入和删除

按值查找:无序时,都为O(n);有序时,顺序表可以折半查找,O(log₂n)

按序号查找:顺序表为O(1),链表为O(n)

4.空间分配

5.怎样选取存储结构

基于存储的考虑:难以估计长度和存储规模时用链表,但链表的存储密度较低

基于运算的考虑:经常做按序号访问数据元素用顺序表

基于环境的考虑:顺序表容易实现,链表基于指针;较稳定选顺序表,动态性较强选链表

      综上是“2023计算机考研408数据结构知识:线性表的链式表示”,希望对计算机考研者们有所帮助!世界上唯一可以不劳而获的就是贫穷,唯一可以无中生有的是梦想。没有哪件事,不动手就可以实现。世界虽然残酷,但只要你愿意走,总会有路;看不到美好,是因为你没有坚持走下去。人生贵在行动,迟疑不决时,不妨先迈出小小一步。前进不必遗憾,若是美好,叫做精彩;若是糟糕,叫做经历!加油!

推荐阅读:

2023计算机考研408数据结构知识点总结

扫描二维码添加微信好友

获取更多考研干货资料以及专业备考指导

优先参加近期福利活动

我要提分

    • 文都考研课代表

    研友互动

    关注北京文都微信

    关注文都考研微博