线性表的定义和特点
定义:
有n(n≥0)个数据特性相同的元素构成的有序序列称为线性表。
当个数n(n≥0)定于为线性表的长度,n=0时成为空表。
特点:
只有一个首结点和尾结点;
除首尾结点外,其他结点只有一个直接前驱和一个直接后继。
分析26个英文字母组成的英文表(A,B,C,D,…..,Z)数据元素都是字母,元素间关系是线性
抽象数据类型的定义为:
ADT List
{
数据对象:D={ai|ai∈ElemSet,i1,2,3...n,n≥0}
数据关系:R={<ai-1,ai|ai-1,ai∈D,i=2,...,n}
线性表的基本操作
1.初始化线性表 L
2.销毁线性表L
3.清空线性表L
4.求线性表L的长度
5.判断线性表L是否为空
6.获取线性表L中的某个数据元素内容
7.检索值为e的数据元素
8.在线性表L中插入一个数据元素
9.删除线性表L中第i个数据元素
}ADT List
线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。(逻辑上相邻,物理上也相邻)
顺序存储方法:用一组地址连续的存储单元依次存储线性表的元素,可通过数组V[n]来实现。
顺序表的类型定义
#define MAXSIZE 100//最大长度
typedef struct{
ElemType *elem;//指向顺序表的基地址
int length;//顺序表的当前长度
}SqList;//顺序表的类型定义
如果你的C和C++基础不够扎实,建议看下我这篇博客
C、C++函数传参疑难解析
初始化线性表L(参数用引用)
Status InitList_Sq(SqList &L)
{ //构造一个空的顺序表L
L.elem=new ElemTyPe[MAXSIZE];
//为顺序表分配空间
//存储分配失败
if(!L.elem)exit(OVERFLOW);
//空表长度为0
L.length=0;
return OK;
}
初始化线性表L(参数用指针)
"Status InitList_Sq(SqList *L)
{
L->elem=new ElemType[MAXSIZE];
if(!L->elem)exit(OVERFLOW);
L->length=0;
return OK;
}
销毁线性表L
void DestroyList(Sqlist &L)
{
if(L.elem)
delete[]L.elem;//释放存储空间
}
清空线性表L
void ClearList(SqList &L)
{
L.length=0;//将线性表的长度置为0
}
求线性表L的长度
int GetLength(SqList L)
{
return(L.length);
}
判断线性表L是否为空
int