1. 线性表的定义
线性表:零个或者多个数据元素的有限序列。
线性表元素的个数n(n≥0)定义为线性表的长度,当n=0时,称为空表。
对于一个非空的线性表或者线性结构,具有以下特点:
线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。
线性表顺序存储结构代码如下:
#define MAXSIZE 100
#define OK 1~~~~
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElemType类型根据实际情况而定,这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;
/*线性结构使用顺序表的方式存储*/
//顺序表结构设计
typedef struct {
ElemType *data; // 数组存储数据元素,最大值为MAXSIZE。
int length; // 线性表当前长度
}Sqlist;
//1.1 顺序表初始化
Status InitList(Sqlist *L){
//为顺序表分配一个大小为MAXSIZE 的数组空间
L->data = malloc(sizeof(ElemType) * MAXSIZE);
//存储分配失败退出
if(!L->data) exit(ERROR);
//空表长度为0
L->length = 0;
return OK;
}
代码实现如下:
/*
初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
*/
Status ListInsert(Sqlist *L,int i,ElemType e){
//i值不合法判断
if((i<1) || (i>L->length+1)) return ERROR;
//存储空间已满
if(L->length == MAXSIZE) return ERROR;
//插入数据不在表尾,则先移动出空余位置
if(i <= L->length){
for(int j = L->length-1; j>=i-1;j--){
//插入位置以及之后的位置后移动1位
L->data[j+1] = L->data[j];
}
}
//将新元素e 放入第i个位置上
L->data[i-1] = e;
//长度+1;
L->length++;
return OK;
}
代码实现如下:
/*
初始条件:顺序线性表L已存在,1≤i≤ListLength(L)
操作结果: 删除L的第i个数据元素,L的长度减1。
*/
Status ListDelete(Sqlist *L,int i){
//线性表为空
if(L->length == 0) return ERROR;
//i值不合法判断
if((i<1) || (i>L->length)) return ERROR;
for(int j = i; j < L->length; j++){
//被删除元素之后的元素向前移动
L->data[j-1] = L->data[j];
}
//表长度-1;
L->length--;
return OK;
}
//获取指定位置的元素
Status GetElem(Sqlist L,int i, ElemType *e){
//判断i值是否合理, 若不合理,返回ERROR
if(i<1 || i > L.length) return ERROR;
//data[i-1]单元存储第i个数据元素.
*e = L.data[i-1];
return OK;
}
// 初始条件:顺序线性表L已存在。操作结果:将L重置为空表
Status ClearList(Sqlist *L)
{
L->length=0;
return OK;
}
/* 初始条件:顺序线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
Status ListEmpty(Sqlist L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
//获取顺序表长度即元素个数 */
int ListLength(Sqlist L)
{
return L.length;
}
//顺序输出List
/* 初始条件:顺序线性表L已存在 */
/* 操作结果:依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
int i;
for(i=0;i<L.length;i++)
printf("%dn",L.data[i]);
printf("n");
return OK;
}