线性表抽象数据类型
1.定义:
线性表表示0个或者多个数据元素的有限序列
线性表的特性有:
除第一个元素外,每一个元素均有一个直接前驱
出最后一个元素外,每一个元素均有一个直接后继
2.线性表抽象数据类型
ADT List
Data
/*线性表的数据对象集合为｛a1,a2,...,an｝,每个元素的类型均为DataType.其中，除第一个元素a1外，
每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
数据元素直接是一对一的关系。*/
Operation
InitList(*L);//初始化操作，建立一个空的线性表
ListEmpty(L);//若线性表为空，返回true,否则返回false
ClearList(*L);//清空线性表
GetElem(L,i,*e);//查找线性表中的第i个位置的元素值，并赋值给e
LocateElem(L,e);//查找线性表L中与给定值e相等的元素，如果查找成功，则返回第一个相同的元素在L
//中的下标；否则，返回0表示失败
ListInsert(*L,i,e);//在线性表L的第i个位置插入元素e
ListDelete(*L,i,*e);//删除线性表L中第i个位置元素，并用e返回其值
ListLength();//返回线性表L的长度
end ADT
实现线性表La和线性表Lb的并集操作，结果保存在La中的伪代码如下所示：
[cpp]
//实现线性表La和线性表Lb的并集操作，结果保存在La中
void UnionList(*La,Lb)
{
//计算Lb长度
int lblength = ListLength(Lb);
//计算La长度
int laLength = ListLength(La);
int i ;
//便利Lb中所有元素，判断其是否在La中，若不在，则插入La中
for (i=0;i<length;i++)
{
ElemType temp = GetElem(Lb,i,*e);
if (LocateElem(La,temp)==0)
{
ListInsert(La,++laLength,temp);
}
}
}
//实现线性表La和线性表Lb的并集操作，结果保存在La中
void UnionList(*La,Lb)
{
//计算Lb长度
int lblength = ListLength(Lb);
//计算La长度
int laLength = ListLength(La);
int i ;
//便利Lb中所有元素，判断其是否在La中，若不在，则插入La中
for (i=0;i<length;i++)
{
ElemType temp = GetElem(Lb,i,*e);
if (LocateElem(La,temp)==0)
{
ListInsert(La,++laLength,temp);
}
}
}
3.顺序存储结构
3.1顺序存储结构的定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
3.2 数据结构
[cpp]
//线性表的顺序存储结构
#define MAXSIZE 20;//存储空间初始分配量为20
typedef int ElemType;//数据类型为int
type struct
{
ElemType data[MAXSIZE];//数组存储数据元素
intlength;//线性表长度
};
//线性表的顺序存储结构
#define MAXSIZE 20;//存储空间初始分配量为20
typedef int ElemType;//数据类型为int
type struct
{
ElemType data[MAXSIZE];//数组存储数据元素
intlength;//线性表长度
};
3.3 数组长度与线性表长度的区别
数组的长度是存放线性表的存储空间的长度，存储空间分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表的插入和删除，这个量是变化的。
3.4 地址计算方法
由于顺序存储结构是按照顺序存储的，所以每个数据元素的地址都可以根据第一个元素的地址推算出来。
LOC(ai) = LOC(a1)+ (i-1)*c
4.顺序存储结构的操作
4.1 获取元素操作
[cpp]
//////////////////////////////////////////////////////////////////////////
//获取顺序链表中第i个元素，并赋值给e
int GetElem(SqList L,int i, ElemType * e)
{
//线性表长度等于0或者获取元素位置错误返回0
if (L.Length == 0 || i < 0 || i > L.Length)
{
return 0;
}
返回第i个元素
*e = L.data[i-1];
return 1;
}
//////////////////////////////////////////////////////////////////////////
//获取顺序链表中第i个元素，并赋值给e
int GetElem(SqList L,int i, ElemType * e)
{
//线性表长度等于0或者获取元素位置错误返回0
if (L.Length == 0 || i < 0 || i > L.Length)
{
return 0;
}
返回第i个元素
*e = L.data[i-1];
return 1;
}
4.2插入操作
插入操作算法的思路是：
1.如果插入位置不合理，抛出异常.
2.如果线性表长度大于等于数组长度，则抛出异常或者增加数组长度
3.从最后一个元素开始像前便利到第i个位置，分别将它们像后移动一个位置
4.第i个元素位置插入e
5.表长度加1
[cpp]
//在线性表L的第i个位置插入元素e
int ListInsert(Sqlist *L, int i, ElemType e)
{
//插入位置错误，返回0
if (i < 0 || i > L.Length)
{
return 0;
}
//线性表的长度大于等于数组的最大长度，返回0
if (L.Length >= MAXSIZE)
{
return 0;
}
int j = L.Length -1;
//从第i个元素到最后一个元素，每个元素后移一位
while (j >= i)
{
L.data[j+1] = L.data[j];
j--;
}
//第i个元素的位置放入e
L.data[i] = e;
//线性表长度加1
L.Length ++;
}
//在线性表L的第i个位置插入元素e
int ListInsert(Sqlist *L, int i, ElemType e)
{
//插入位置错误，返回0
if (i < 0 || i > L.Length)
{
return 0;
}
//线性表的长度大于等于数组的最大长度，返回0
if (L.Length >= MAXSIZE)
{
return 0;
}
int j = L.Length -1;
//从第i
补充：软件开发 , C++ ,
