数据结构之线性表(顺序表示)
程序员文章站
2024-03-20 14:28:40
...
定义
线性表是具有相同数据类型的个数据元素的有限序列。其中为表长,当时,线性表是一个空表。若用命名线性表,则一般表示如下:
其中,是唯一的第一个数据元素,又称为表头元素;是唯一的最后一个元素,又称为表尾元素。除第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外,每个元素有且仅有一个直接后继。
特点:
- 表中元素个数有限且具有逻辑上的有序性
- 表中元素数据类型相同
- 表中元素具有抽象性,仅讨论元素逻辑关系,不考虑元素内容
划分:
- 顺序存储: 顺序表
- 链式存储:
- 单链表 (指针实现)
- 双链表(指针实现)
- 循环链表(指针实现)
- 静态链表(借助数组实现)
注意:
- 线性表是逻辑结构,表示元素之间一对一的相邻关系
- 顺序表和链表是指存储结构
线性表的基本操作
-
InitList(&L)
:初始化表 -
Length(L)
:求表长 -
LocateElem(L,e)
:按值查找 -
GetElem(L,i)
:按位查找 -
ListInsert(&L,i,e)
:插入操作 -
ListDelete(&L,i,&e)
:删除操作 -
PrintList(L)
:输出 -
Empty(L)
:判空 -
DestroyList(&L)
:销毁
线性表的顺序存储
线性表的顺序存储又称顺序表,它是一组地址连续的存储单元,它的逻辑顺序和物理顺序相同。
注意:线性表中的位序是从1开始的,而数组中元素的下标是从0开始的。
假定线性表的元素类型为ElemType,那么线性表的顺序存储类型可以描述如下:
#define MaxSize 50 //定义线性表的最大长度
typedef struct{
ElemType data[MaxSize]; //顺序表的元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
一维数组可以是静态分配的(数据可能溢出),也可以是动态分布的。C的初始动态分配语句为:
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)
#define InitSize 100 //表长的初始定义
typedef struct{
ElemType *data; // 动态分布数组的指针
int MaxSize,length; // 数组的最大容量和当前个数
}SeqList;
-
插入操作
在顺序表L的第i个位置插入新的元素e
bool ListInsert(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1) //判断i范围是否有效
return false;
if(L.length>=MaxSize) //若当前空间已满,则不能插入
return false;
for(int j=L.length;j>=i;j--) //将第i个元素及后面的元素后移
L.data[j]=L.data[j-1]
L.data[i-1]=e; //插入元素e
L.length++; //表长加1
return true;
}
-
删除操作
删除表L中第i个位置的元素,删除的元素用变量e返回
bool ListDelete(SqList &L,int i,&e){
if(i<1||i>L.length) //判断i范围是否有效
return false;
e=L.data[i-1]; //将被删除的元素赋值给e
for(j=i;j<L.length;j++) //将第i个位置后的元素前移
L.data[j-1]=L.data[j]
L.length--; //表长减1
return true;
}
-
按值查找
在表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SqList &L, ElemType e){
int i;
for(i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}
总结:上述三种操作的时间复杂度均为O(n)。
顺序表的特点:
- 随机访问,通过首地址和元素序号可以在O(1)的时间内找到指定元素
- 存储密度高,每个节点只存储数据元素
- 逻辑相邻元素物理上也相邻,插入和删除需要移动大量元素
上一篇: 关于java数组的一点小技巧
下一篇: 会话Session和Cookie