数据结构笔记数据结构.doc

:信息的载体,能被计算机识别、存储和加工处理。:数据的基本单位,可由若干个数据项组成,数据项是具有独立含义的最小标识单位。:数据之间的相互关系,即数据的组织形式。它包括:1)数据的逻辑结构,从逻辑关系上描述数据,与数据存储无关,独立于计算机;2)数据的存储结构,是逻辑结构用计算机语言的实现,依赖于计算机语言。3)数据的运算,定义在逻辑结构上,每种逻辑结构都有一个运算集合。常用的运算:检索/插入/删除/更新/排序。。数据的存储结构是逻辑结构用计算机语言的实现。:一个值的集合及在值上定义的一组操作的总称。分为:原子类型和结构类型。:抽象数据的组织和与之相关的操作。优点:将数据和操作封装在一起实现了信息隐藏。:是在概念层上描述问题;类:是在实现层上描述问题;在应用层上操作对象(类的实例)解决问题。,简称为数据结构,有:(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。(2)非线性结构,一个结点可能有多个直接前趋和后继。:1)顺序存储,把逻辑相邻的结点存储在物理上相邻的存储单元内。2)链接存储,结点间的逻辑关系由附加指针字段表示。3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。4)散列存储,按结点的关键字直接计算出存储地址。:算法是正确的;执行算法所耗的时间;执行算法的存储空间(辅助存储空间);易于理解、编码、调试。(n):是该算法的时间耗费,是求解问题规模n的函数。记为O(n)。时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。(n):是该算法的空间耗费,是求解问题规模n的函数。:是用时间复杂度和空间复杂度来衡量的,它们合称算法的复杂度。,还与输入实例中各元素的取值相关。:是由n(n≥0)个数据元素组成的有限序列。:1)InitList(L),构造空表,即表的初始化;2)ListLength(L),求表的结点个数,即表长;3)GetNode(L,i),取表中第i个结点,要求1≤i≤ListLength(L);4)LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置,有多个x则返回首个,没有则返回特殊值表示查找失败。5)InsertList(L,x,i)在表的第i个位置插入值为x的新结点,要求1≤i≤ListLength(L)+1;6)DeleteList(L,i)删除表的第i个位置的结点,要求1≤i≤ListLength(L);:把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。:Loc(ai)=Loc(a1)+(i-1)*C;1≤i≤(1)插入voidinsertlist(seqlist*L,datatypex,inti){intj;if(i<1||i>L->length+1)error(“positionerror”);if(L->length>=listsize)error(“overflow”);for(j=L->length-1;j>=i-1;j--)L->data[j+1]=L->data[j];结点后移L->data[i-1]=x;L->length++;}在顺序表上插入要移动表的n/2结点,算法的平均时间复杂度为O(n)。(2)删除voiddelete(seqlist*L,inti){intj;if(i<1||i>L->length)error(“positionerror”);for(j=i;j<=L->length-1;j++)L->data[j-1]=L->data[j];结点前移L->length--;}在顺序表上删除要移动表的(n+1)/2结点,算法的平均时间复杂度为O(n)。:只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址,datanextdata是数据域,next是指针域。(1)建立单链表。时间复杂度为O(n)。加头结点的优点:1)链表第一个位置的操作无需特殊处理;2)将空表和非空表的处理统一。(2)查找运算。时间复杂度为O(n)。1)按序号查找。Listnode*getnode(linklisthead,int