数据结构与算法基础——第02周-线性表的顺序表示和实现(2.4.3)

一 概述

• 线性表的顺序存储表示
• 顺序表示意图
• 顺序表基本操作的实现——线性表的基本操作

二 线性表的顺序存储表示

2.1 顺序表(Sequence List)

注意：逻辑位序和物理位序相差1

2.2 代码表示

顺序表类型定义(静态)

#define MAXSIZE 100
typedef struct
{
	ElemType elem[MAXSIZE];
	int length;
}SqList;

顺序表类型定义(动态)

typedef struct
{
	ElemType *elem;
	int length;
}SqList; //顺序表类型

L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);

三 顺序表示意图

四 顺序表基本操作的实现——线性表的基本操作

4.1 线性表的基本操作

InitList(&L);         //初始化操作，建立一个空的线性表L
DestroyList(&L);      //销毁已存在的线性表L
ClearList(&L);        //将线性表清空
ListInsert(&L,i,e);   //在线性表L中第i个位置插入新元素e
ListDelete(&L,i,&e);  //删除线性表L中第i个位置元素，用e返回
IsEmpty(L);           //若线性表为空，返回true，否则false
ListLength(L);        //返回线性表L的元素个数
LocateElem(L,e);      //L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
GetElem(L,i,&e);      //将线性表L中第i个位置元素返回给e

4.2 操作算法中用到的预定义常量和类型

//函数结果状态代码
#define TRUE        1
#define FALSE       0
#define Ok          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW    -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

4.3 线性表的基本操作-1

线性表L的初始化(参数用引用)

Status InitList_Sq(SqList &L)    //构造一个空的顺序表
{
	L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间
	if(!L.elem)exit(OVERFLOW);    //存储分配失败
	L.length=0;                   //空表长度为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 IsEmpty(SqList L)
{
	if(L.length==0)return 1;
	else return 0;
}

4.4 线性表的基本操作-2(顺序表的取值-根据位置i获取响应位置数据元素的内容)

int GetElem(SqList L,int i, ElemType &e)
{
	if(i<1||i>L.length)return ERROR; //判断i值是否合理，若不合理，返回Error
	e=L.elem[i-1];//第i-1的单元存储着第i个数据
	return OK;
}