线性表的相关概念:
------线性表(Linear List)由有限个类型相同的数据元素组成,除了第一个元素和最后一个元素外,其他元素都有唯一的前驱元素和唯一的后继元素。
------表中元素个数成为线性表的长度。
------线性表没有元素时成为空表。
------表起始位置成为表头,结束位置成为表尾。
线性表的抽象数据类型描述:
数据对象集合:
{a1,a2,a3,... ,an},每个元素类型为DataType,除了a1和an外每个元素都只有一个前驱元素一个后继元素,数据元素之间的关系是一对一。
基本操作集合:
(1)void InitList(List *L):初始化一个空线性表表
(2)DataType FindByNum(int k, List L):查找线性表中第K位的元素,返回该元素
(3)int FindByElem(DataType e,List L):在线性表中查找元素X第一次出现的位置,返回该位置
(4)void Insert(List L, int i, DataType e):在线性表中第i个位置上插入元素e
(5)void Delete(List L, int i):删除线性表中第i个位置上的元素
(6)int Lengh(List L):返回线性表长度
(7)void PrintList(List L):打印线性表
线性表的实现:
一、顺序实现
#define MAXSIZE 20
typedef int DataType;
typedef struct
{
DataType data[MAXSIZE];
int len;
}SeqList;
(1)初始化空顺序表
//初始化(建立空的顺序表)
void InitList(SeqList *L)
{
L->len = 0;
}
(2)查找
//按位置查找(i非下标)
DataType FindByNum(int i, SeqList L)
{
for(int j = 0; j < i; j++)
return L.data[j];
}
//按元素查找(返回元素第一次出现的下标)
int FindByElem(DataType e, SeqList L)
{
int i = 0;
while(i < L.len && L.data[i] != e)
i++;
if(i >= L.len)
return -1;
return i;
}
(3)插入(注意移动时要从最后一个开始移动, i是元素位置,不是下标)
void Insert(DataType e, int i, SeqList *PtrL)
{
int j;
if(PtrL->len == MAXSIZE)
printf("The list is full.\n");
if(i < 1 || i > PtrL->len + 1)
printf("Wrong place.\n");
if(i <= PtrL->len)
{
for(j = PtrL->len - 1; j >= i - 1; j--)
{
PtrL->data[j + 1] = PtrL->data[j];
}
}
PtrL->data[i - 1] = e;
PtrL->len++;
}
(4)删除(注意移动要从i开始,i是元素的位置,不是下标)
void Delete(int i, SeqList *PtrL)
{
int j;
if(PtrL->len == 0)
printf("Empty.\n");
if(i < 1 || i > PtrL->len)
printf("Wrong place.\n");
for(j = i; j < PtrL->len; j++)
{
PtrL->data[j - 1] = PtrL->data[j];
}
PtrL->len--;
}
(5)打印
void PrintList(SeqList L)
{
for(int i = 0; i < L.len; i++)
printf("%d ", L.data[i]);
printf("\n");
}
(6)长度
int Length(SeqList L)
{
return L.len;
}