![](https://www.jinchutou.com/images/s.gif)
数据结构知识点总结
11页1、数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。数据结构的定义:逻辑结构:从逻辑结构上描述数据,独立于计算机。线性结构:一对一关系。线性结构:多对多关系。存储结构:是逻辑结构用计算机语言的实现。顺序存储结构:如数组。链式存储结构:如链表。索引存储结构:稠密索引:每个结点都有索引项。稀疏索引:每组结点都有索引项。散列存储结构:如散列表。数据运算。对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。常用的有:检索、插入、删除、更新、排序。数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。结构类型:由用户借助于描述机制定义,是导出类型。抽象数据类型ADT: 是抽象数据的组织和与之的操作。相当于在概念层上描述问题。优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。评价算法的好坏的因素:算法是正确的;执行算法
2、的时间;执行算法的存储空间(主要是辅助存储空间);算法易于理解、编码、调试。时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为:常数阶0(1)、对数阶O(log2n)、线性阶O (n)、线性对数阶O (nlog2n)、平方阶O (M2)、立方阶O (M3 )、 k次方阶O (nAk)指数阶O (2An)o空间复杂度:是某个算法的空间耗费,它是该算法所求解问题规模n的函数。算法的时间复杂度和空间复杂度合称算法复杂度。第二章线性表线性表是由nN0个数据元素组成的有限序列。n=0是空表;非空表,只能有一个开始结点,有且只能有一个终端结点。线性表上定义的基本运算:构造空表:Initlist (L)求表长:Listlength (L)取结点:GetNode (L,i)查找:LocateNode (L, x)插入:InsertList (L, x, i)
3、册J除:Delete (L,i)顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算:LOCa (i) =LOCa (1) + (i-1) *d;(首地址为1) 在顺序表中实现的基本运算:插入:平均移动结点次数为n/2;平均时间复杂度均为O (n)。删除:平均移动结点次数为(n-1) /2;平均时间复杂度均为O (n)。线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同,为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还存储了其后继 结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。单链表运算:建立单链表头插法:s-next=head; head=s;生成的顺序与输入顺序相反。平均时间复杂度均为O (n)。尾插法:head=rear=null; if (head=null) head=s ; else r-next=s; r=s; 平均时间复杂度均为 O (n)加头结点的算法:对开始结点的操作无需特殊处理,统一了空表和非空表。查找按序号:与
4、查找位置有关,平均时间复杂度均为O (n)。按值:与输入实例有关,平均时间复杂度均为O (n)。插入运算:p=GetNode (L, i-1); s-next=p-next; p-next=s;平均时间复杂度均为 O (n)删除运算:p=GetNode (L, i-1); r=p-next; p-next=r-next; free (r);平均时间复杂度均为 O (n)单循环链表是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O (1),不用遍历整个链表。双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方 向的链。由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链表。双链表上的插入和删除时间复杂度均为O (1)。顺序表和链表的比较:基于空间:顺序表的存储空间是静态分配,存储密度为1;适于线性表事先确定其大小时采用。链表的存储空间是动态分配,存储密度1;适于线性表长度变化大时采用。基于
《数据结构知识点总结》由会员鲁**分享,可在线阅读,更多相关《数据结构知识点总结》请在金锄头文库上搜索。
![2023年办公室下半年工作计划.docx](https://union.152files.goldhoe.com/2022-11/30/30a592a0-1a8d-4014-bf8b-37841c51f610/pic1.jpg)
2023年办公室下半年工作计划.docx
![工商联深入学习科学发展观的总结.docx](https://union.152files.goldhoe.com/2024-1/1/a1f592a5-902b-43d8-9700-4a8cbabee4b5/pic1.jpg)
工商联深入学习科学发展观的总结.docx
![学农心得体会(多篇).docx](https://union.152files.goldhoe.com/2023-8/31/9cc70efc-a158-4b0d-a466-b1734190177e/pic1.jpg)
学农心得体会(多篇).docx
![鲁迅《好故事》教学教案](https://union.152files.goldhoe.com/2023-4/19/52f04ee8-9820-41b4-aa96-6943b9d23753/pic1.jpg)
鲁迅《好故事》教学教案
![物业管理公司投标书范本(1)(天选打工人).docx](https://union.152files.goldhoe.com/2023-4/26/883690b1-8186-464a-a418-049f5afa8728/pic1.jpg)
物业管理公司投标书范本(1)(天选打工人).docx
![安防系统质量管理制度.doc](https://union.152files.goldhoe.com/2023-2/4/2031aab8-4c32-4fde-b7db-26148fa643cf/pic1.jpg)
安防系统质量管理制度.doc
![电脑族如何保护眼睛.doc](https://union.152files.goldhoe.com/2023-1/3/22ecf296-de4e-4b27-885d-bfb39dbd348e/pic1.jpg)
电脑族如何保护眼睛.doc
![成语故事作文汇总十篇](https://union.152files.goldhoe.com/2022-11/2/c40e847b-6bd4-411e-928d-6d1f16752c4a/pic1.jpg)
成语故事作文汇总十篇
![普通话三分钟命题说话范文.doc](https://union.152files.goldhoe.com/2023-7/23/944ec02c-e7cc-4e83-9d21-0727bccbf0b4/pic1.jpg)
普通话三分钟命题说话范文.doc
![42生产管理制度发文.doc](https://union.152files.goldhoe.com/2022-8/28/7babe79b-5eba-4520-8fb9-50b372a151e2/pic1.jpg)
42生产管理制度发文.doc
![个人房屋租赁合同书简单版(8篇).doc](https://union.152files.goldhoe.com/2023-10/24/57611a4a-e98a-4607-9f21-9866811e5457/pic1.jpg)
个人房屋租赁合同书简单版(8篇).doc
![2022种植合同模板六篇](https://union.152files.goldhoe.com/2022-9/3/4db2b20b-bff9-4a47-9d6c-fadeb5980c90/pic1.jpg)
2022种植合同模板六篇
![客服员工年度工作总结(二篇).doc](https://union.152files.goldhoe.com/2023-12/9/0093edee-3176-4c01-b249-1a04bede0695/pic1.jpg)
客服员工年度工作总结(二篇).doc
![2013年高考语文一轮专题复习-词语](https://union.152files.goldhoe.com/2023-1/23/e074f8e7-8bf9-420a-8b5b-51b2a4eb461e/pic1.jpg)
2013年高考语文一轮专题复习-词语
![卫生间装修注意这17个“神细节”能让家务省一半力!](https://union.152files.goldhoe.com/2022-9/14/5eab7232-3707-4ce9-9f19-6fa81d39d92c/pic1.jpg)
卫生间装修注意这17个“神细节”能让家务省一半力!
![保安班长个人年终工作总结8篇.doc](https://union.152files.goldhoe.com/2023-3/13/c088fac3-090c-4c2e-b079-a3814918bbdb/pic1.jpg)
保安班长个人年终工作总结8篇.doc
![2023年中学数学教师工作总结.docx](https://union.152files.goldhoe.com/2023-9/4/8fa66791-08e9-4cdf-be29-22fe25c3b3f1/pic1.jpg)
2023年中学数学教师工作总结.docx
![餐费补贴管理办法-(天选打工人).docx](https://union.152files.goldhoe.com/2023-6/21/8fe5b401-37a2-4c0f-8196-aebdb7bb1cbe/pic1.jpg)
餐费补贴管理办法-(天选打工人).docx
![三亚邮轮市场调研综合报告](https://union.152files.goldhoe.com/2023-9/15/4fae37c5-3610-437d-ba39-2a2792040537/pic1.jpg)
三亚邮轮市场调研综合报告
![教师考勤制度.docx](https://union.152files.goldhoe.com/2022-10/24/c2ebb8b1-ac03-4096-8084-2c36f712530c/pic1.jpg)
教师考勤制度.docx
![主从RS触发器资料](/Images/s.gif)
2023-09-27 20页
![关键环节食品加工操作规程](/Images/s.gif)
2024-01-31 8页
![信息处理技术员](/Images/s.gif)
2022-10-21 6页
![GPS导航的应用](/Images/s.gif)
2022-08-26 2页
![财政与金融题库](/Images/s.gif)
2024-02-10 32页
![新教师培训自我评价五篇](/Images/s.gif)
2022-08-09 12页
![计提折旧年数总和法详解及例题](/Images/s.gif)
2024-03-09 3页
![彼得林奇寻找快速成长股](/Images/s.gif)
2022-08-13 4页
![路面路基工程](/Images/s.gif)
2022-09-05 2页
![一体化生活净水处理系统操作维护说明书](/Images/s.gif)
2023-02-18 13页