数据结构学习笔记之线性表
1. 线性表
线性表是指：零个或多个数据元素的有限序列。
线性表的特点是：第一个元素无前驱，最后一个元素无后继。其他每个元素有且只有一个直接的前驱和后继。
线性表的长度是指包含数据元素的个数。
2. 线性表的抽象数据类型
线性表的的数据模型在定义中已经说明了，而线性表所包括的一组操作定义如下：
- 初始化InitList(*L)
- 查询是否为空ListEmpty(L)
- 清空ClearList(*L)
- 获取线性表的第i个元素GetElem(L,I,*e)
- 确定某个元素在线性表中的位置LocateElem(L,e)
- 插入ListInsert(*L,i,e)
- 删除ListDelete(*L,i,*e)
- 返回线性表的长度ListLength(L)
在实际的应用中，线性表的基本操作是不同的，可能是上面操作的一个子集。复杂的线性表操作可以由以上基本操作组合来实现。由之前的讨论可知，任何一种数据结构，有存储方式上，有顺序存储结构和链式存储结构。我们先从顺序存储结构讲起。
3. 线性表的物理存储结构
- 顺序存储结构
线性表的顺序存储结构是指用一段连续地址空间依次存储线性表的数据元素。在C语言中符合这种存储结构的数据类型是：数组。对，利用数组就可以存储线性表了。为了更好地抽象线性表，我们利用结构体的概念，将线性表的长度的属性也包括在这一结构体中。因此顺序存储结构的代码如下：
# define MAXSIZE 20
# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;
}SqList;
/*顺序存储结构包括3个关键因素：数组大小、链表长度以及数组起始地址*/
接下来给出三个线性表相关操作的函数。代码实现如下：
- 获取线性表的第i个元素GetElem(SqList L, int i, ElemType *e)
Status GetElem(SqList L, int i, ElemType *e)
{
if (L.length == 0 || i<1 || i>L.length)
return ERROR;
*e = L.data[i-1];
return OK; }-
插入操作ListInsert(SqList *L, int i, ElemType e)
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if (L->length == MAXSIZE)
return ERROR;
if (i<1 || i>L->length+1)
return ERROR;
if (i<L->length)
{
for (k=L->length;k>i-1;k--)
{
L->data[k+1] = L->data[k];
}
}
L->data[i-1] = e;
L->length ++;
return OK; }-
删除操作ListDelete(SqList *L, int i, ElemType *e)
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;
if (L->length == 0)
return ERROR;
if (i<1 || i>L->length)
return ERROR;
*e = L->data[i-1];
if (i<L->length)
{
for (k=i;k<L->length;k++)
L->data[k-1] = L->data[k];
}
L->length--;
return OK; } 顺序存储结构的优缺点如下：-
优点：存储空间的利用率高，不用存储元素之间的逻辑关系。此外还能快速存取任意位置的元素，时间复杂度为O(1). -
缺点：插入和删除操作需要移动大量元素，时间复杂度为O(1).容易造成存储空间“碎片”。
-
链式存储结构
鉴于顺序存储结构存在的缺点，链式存储结构采用了结点的方式来组织数据元素。结点包括数据域和指针域。其中数据域用来存储数据元素，指针域用来存储下一个结点的指针。这样就可以最大限度的利用存储空间，此外链式存储结构可以避免插入删除操作时的数据移动。 链表中的第一个结点的存储位置称为头指针。为了更方便的对链表进行操作，单链表的第一个结点前加一个结点，称为头结点。每一个链表都存在头指针，不一定存在头结点。头结点的数据域可以为空，也可以是链表长度信息，指针域为指向第一个结点。 下面简单介绍下链式存储结构的数据结构。其代码实现如下所示typedef struct Node
{
ElemType data;
struct Node *node;
}Node
typedef struct Node *LinkList; /*定义LinkList*/ 链式存储结构的单链表操作原理比较简单。主要是涉及到链表指针域的调整。
4. 单链表顺序结构与链式结构的优缺点比较
4. 单链表顺序结构与链式结构的优缺点比较 最后来来总结下顺序存储结构与链式结构。-
若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
譬如，用于游戏账户的注册，可以考虑采用顺序存储结构，因为注册基本只需要一次插入操作，而需要较多的登录查询操作。-
当线性链表中的元素个数变化较大或者不确定有多大时，最好采用单链表结构。
文章评论（1条评论）
登录后参与讨论
相关推荐阅读
-
用户449796 2013-09-20 11:39
- 基于Matlab的数字图像处理——滤波原理——非线性空间滤波
- 概述 我们已经知道，线性空间滤波即为掩膜矩阵和图像矩阵的卷积/相关运算。本质上来说，是像素点值与像素点邻域像素点值之间的一种特殊运算关系，因为其运算规则为邻域像素点与对应掩膜系数相乘后相加的线...
-
- 数据结构学习之数据结构相关定义
- 数据结构学习笔记之数据结构相关定义 1. 数据相关定义 何为数据结构？ 答：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 ...
-
- 数据结构学习笔记--数据结构相关定义
- 数据结构学习笔记之数据结构相关定义 1. 数据相关定义 何为数据结构？ 答：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 ...
-
- verilog中两个常用的选择器if和case
- 看过一些资料，是研究if和case的好处和坏处，在什么时候该用if，在什么时候该用case等等的。但是看完这些分析后，并没有很明确地体会到这两者的优缺点，也没有体会这两个选择器该什么时候...
-
- [博客大赛]详解如何搭建S5PV210的Eclipse集成开发环境(一)
- 一、详解如何搭建S5PV210的eclipse集成开发环境 1. S5PV210处理器简介 S5PV210处理器是Samsung公司2009年推出的一款Cortex...
EE直播间
更多
-
提升毫米波信号测试精度 直播时间： 12月18日 14:00 -
EE Talk主题专访系列直播-对话：释放 Wi-Fi 7 在高带宽应用中的技术潜力 直播时间： 12月19日 10:00
关闭
站长推荐
/2 
/2
-
返回顶部
-
daydayup_yao_738579509 2013-9-15 13:01