数据结构——线性表

线性表:顺序表、单链表。

线性表的变形:双向链表、循环链表。

多项式及其运算。

线性表的性质:除第一个元素外,其他每一个元素有一个且仅有一个直接前驱;除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。

线性表基本操作:查找、插入、删除……(其实插入与删除都是基于查找的,所以最基本的还是查找。)

线性表的存储方式:基于数组(顺序表);基于链表(链表);基于散列(散列表)……

顺序表

顺序表的优点:无需保存与逻辑相关的信息;给定下标时,存取速度快。

顺序表的缺点:插入删除操作移动开销大(对于排序不利);需要固定的存储空间(连续的存储空间);

作者笔记:线性表用来保存一小量数据,或是存储一些采集到的数据信息什么的还是很方便的。

单链表

结点:数据+链接(data+link)

单链表的结构:

first->[a1, link]->[a2, link]->……->[ak, link]->……->[an, null]

单链表也头具有头结头与没有头结点两种。

头指针 指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。

图1 线性链表的逻辑状态

有时在单链表的第一个结点之前附设一个结点,称之为头结点 头结点的数据域可以不存储任何信息,也可以存储如线性表长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。如图2(a)所示,此时,单链表的头指针指向头结点。若线性表为空,则头结点的指针域为“空”,如图2(b)所示。

图2 带头结点的单链表   (a)非空表;(b)空表

加入头结点的目的就是要使空表、表头、中部、尾部的插入操作变得一致,都可以变成后插入操作。此外,空表和非空表的表示统一。

缺点就是浪费了一个并没节点的空间。但对于节点数很多的链表而言,这一点浪费是可以忽略不计的。

插入要考虑非空表头部或是空表、非空表中部或是尾部。

删除要考虑头部删除、中部或尾部删除、空链表删除。

未经允许不得转载:TacuLee » 数据结构——线性表

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址