数据结构——线性表

这次介绍的是线性表，线性表（List），零个或多个数据元素的有限序列。

线性表基本操作

InitList(L): 初始化操作，建立一个空的线性表L。
ListEmpty(L): 判断线性表是否为空表，若线性表为空，返回true，否则返回false。
ClearList(L): 将线性表清空。 GetElem(L,i,e): 将线性表L中的第i个位置元素值返回给e。
LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
ListInsert(L,i,e): 在线性表L中第i个位置插入新元素e。
ListDelete(L,i,e): 删除线性表L中第i个位置元素，并用e返回其值。
ListLength(L): 返回线性表L的元素个数。

 

线性表按照物理存储结构可分为顺序存储和链式存储

1. 顺序存储：用一段地址连续的存储单元依次存储线性表的数据元素

 

优点：可以快速存取，无需为元素间逻辑占用存储空间

缺点：插入和删除需移动元素，长度不确定难以确定存储空间容量，容易找出存储空间“碎片”

 

1. 链式存储：用一组任意的存储单元存储线性表的数据元素，存储单元可以连续，也可以不连续

 

对比顺序存储，链式的有以下优势，频繁的增加 删除操作，不需要提前分配存储大小空间。但链式的也牺牲了查询的操作。

 

链式存储的其他形式

静态链表：为了给没有指针的高级语言设计的一种实现单链表能力方式

 

循环链表：将单链表终端节点的指针由空指针改为指向头节点（合并两个循环链表方便）

 

双向链表：方便对节点前后进行操作（牺牲了一些空间）