数据结构知识点概括第一章概论数据就就是指能够被计算机识别、存储与加工处理得信息得载体。数据元素就是数据得基本单位，可以由若干个数据项组成。数据项就是具有独立含义得最小标识单位.数据结构得定义:·逻辑结构:从逻辑结构上描述数据,独立于计算机。·线性结构:一对一关系。·线性结构:多对多关系。·存储结构：就是逻辑结构用计算机语言得实现。·顺序存储结构：如数组。·链式存储结构：如链表.·索引存储结构：·稠密索引:每个结点都有索引项。·稀疏索引：每组结点都有索引项.·散列存储结构：如散列表.·数据运算。·对数据得操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。·常用得有：检索、插入、删除、更新、排序。数据类型:就是一个值得集合以及在这些值上定义得一组操作得总称.·结构类型:由用户借助于描述机制定义，就是导出类型.抽象数据类型ＡDT:·就是抽象数据得组织与与之得操作。相当于在概念层上描述问题。·优点就是将数据与操作封装在一起实现了信息隐藏。程序设计得实质就是对实际问题选择一种好得数据结构,设计一个好得算法。算法取决于数据结构。算法就是一个良定义得计算过程，以一个或多个值输入,并以一个或多个值输出。评价算法得好坏得因素:·算法就是正确得;·执行算法得时间；·执行算法得存储空间（主要就是辅助存储空间)；·算法易于理解、编码、调试。时间复杂度:就是某个算法得时间耗费，它就是该算法所求解问题规模n得函数.渐近时间复杂度：就是指当问题规模趋向无穷大时，该算法时间复杂度得数量级.评价一个算法得时间性能时,主要标准就就是算法得渐近时间复杂度.算法中语句得频度不仅与问题规模有关,还与输入实例中各元素得取值相关。时间复杂度按数量级递增排列依次为：常数阶Ｏ（1）、对数阶O（ｌoｇ２n）、线性阶Ｏ（n)、线性对数阶O(nｌｏg2n）、平方阶O(n^２)、立方阶O（n^３)、……ｋ次方阶O（ｎ^k）、指数阶O（2＾ｎ）。空间复杂度：就是某个算法得空间耗费,它就是该算法所求解问题规模n得函数。算法得时间复杂度与空间复杂度合称算法复杂度。第二章线性表线性表就是由n≥0个数据元素组成得有限序列。n=0就是空表;非空表，只能有一个开始结点，有且只能有一个终端结点.线性表上定义得基本运算：·构造空表：Iｎｉｔlｉsｔ(L）·求表长:Lｉstlenｇth(L）·取结点:GetＮode（L,ｉ）·查找：LｏｃａｔｅNｏde（L，x）·插入:InｓertＬist（L，ｘ，ｉ)·删除：Delete(L，i)顺序表就是按线性表得逻辑结构次序依次存放在一组地址连续得存储单元中.在存储单元中得各元素得物理位置与逻辑结构中各结点相邻关系就是一致得。地址计算:ＬOCa（i）=LOCa（1）+(ｉ－1)＊d；(首地址为1)在顺序表中实现得基本运算：·插入:平均移动结点次数为n/2;平均时间复杂度均为O（n）。·删除：平均移动结点次数为(n－1)/2;平均时间复杂度均为Ｏ（n)。线性表得链式存储结构中结点得逻辑次序与物理次序不一定相同,为了能正确表示结点间得逻辑关系，在存储每个结点值得同时，还存储了其后继结点得地址信息（即指针或链）.这两部分信息组成链表中得结点结构。一个单链表由头指针得名字来命名.单链表运算:·建立单链表·头插法：s-＞next=hｅaｄ；head=s；生成得顺序与输入顺序相反.平均时间复杂度均为O(n）。·尾插法:head=rｅａr=null;iｆ(ｈead=nｕll）head=s；elser－＞ｎext=s；r＝s；平均时间复杂度均为O（n)·加头结点得算法：对开始结点得操作无需特殊处理,统一了空表与非空表.·查找·按序号：与查找位置有关,平均时间复杂度均为O（n）。·按值：与输入实例有关，平均时间复杂度均为Ｏ（ｎ)。·插入运算：p＝ＧｅtＮode(Ｌ,i－1）；ｓ->ｎext＝ｐ—〉nｅxt；p—>nexｔ＝ｓ；平均时间复杂度均为O（n）·删除运算：p＝GｅtＮoｄe(L,i-1)；r=p-〉ｎｅxt;p－＞nｅxt=r－＞ｎｅｘt;free（ｒ）；平均时间复杂度均为O（n)单循环链表就是一种首尾相接得单链表，终端结点得指针域指向开始结点或头结点。链表终止条件就是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点就是查找头指针与尾指针得时间都就是O(1）,不用遍历整个链表。双链表就就是双向链表,就就是在单链表得每个结点里再增加一个指向其直接前趋得指针域pｒiｏr，形成两条不同方向得链。由头指针ｈead惟一确定。双链表也可以头尾相链接构成双(向）循环链表。双链表上得插入与删除时间复杂度均为O（１)。顺序表与链表