数据结构复习(一)

时间:2021-03-29 10:34:35

---恢复内容开始---

 

数据结构四大基本结构:

  1.线性结构:数据元素之间存在一对一的关系,即除了第一个元素和最后一个元素之外,每一个元素都有一个直接前驱和直接后继,第一个元素没有直接前驱,最后一个元素没有直接后继。

  2.树形结构:数据元素存在一对多的关系。例如,老师T知道3个硕士研究生G1,G2,G3,每一个研究生Gi有分别指导3个本科生SI1,SI2,SI3,则数据元素之间呈现树形结构。

  3.图形结构(网状结构):数据元素存在多对多的关系。

  4.集合元素:元素之间没有任何关系。

算法的健壮性:当输入非法数据时,算法要能做出适当处理,而不至于产生莫名其妙的输出结果。

 

线性表:是一种线性结构的表,其特点是数据元素之间存在线性关系,即所有数据元素之间都是一个接一个顺序连接的。同一个线性表中各数据元素的类型必须相同。

线性表的基本操作:

 (1) Init_List(L)

   初始条件:表L不存在

   操作结果:构造一个空的线性表(PS:没有指定L的长度)

  (2)Length_List(L)

   初始条件:表L存在

   操作结构:返回线性表所含元素的个数

 (3)Get_List(L)

   初始条件:线性表L存在且1<=i<=Length_List(L)

   返回结果:返回线性表L中的第i个元素的值

  (4)Locate_List(L,x)x是给定的一个数据元素值

   初始条件:线性表L存在

   返回结果:在线性表中查找值为x的数据元素,其结果是返回在L中首次出现的值为x的那个元素的序号或者地址,表示查找成功;否则,在L中没有找打值为x的数据元素,返回一个特殊值,表示查获失败。

  (5)Insert_List(L,i,x)

   初始条件:线性表L存在,且插入位置正确。

   操作结果:在第i个位置插入x,插入之后表长+1

  (6)Delete_List(L,i)

  (7)PriorElem_List(L,cur,pre)

   操作结果:cur不是L中的第一个元素,则用pre返回它的直接前驱,否则操作失败,pre无定义

  (8)NextElem_List(L,cur,next)

   操作结果:cur不是最后一个元素,则用next返回它的直接后继,否则操作失败,next无定义。

 

顺序表的存储空间是连续的

   

   

---恢复内容结束---