目录
一、顺序表的定义
由n (n≥0) 个数据特性相同的元素构成的有限序列称为线性表，当 n=0 时被称为空表。
而顺序表是线性表的其中一种： 用一组连续地址的存储单元一次存储线性表的数据元素（可类比数组）
注意：线性表的位序是从1开始的，而数组中元素的下标是从0开始的。
基本操作：建立、存取、插入、删除、检索、分解、排序等。
二、顺序表的实现
1. 构建顺序表类以及准备内置函数
//构建顺序表类
class SqList
{
public:
ElemType* elem;
int length;
public:
//析构函数初始化顺序表
SqList()
{
elem = new ElemType[MAXSIZE];
if(!elem)
exit(OVERFLOW);
length = 0;
}
public:
//顺序表的取值
Status GetElem(SqList L, int i, ElemType& e);
//顺序表的查找
int LocateElem(SqList L, ElemType e);
//顺序表的插入
Status ListInsert(SqList& L, int i, ElemType e);
//顺序表的删除
Status ListDelete(SqList& L, int i);
};2. 顺序表的取值
//顺序表的取值
Status SqList::GetElem(SqList L, int i, ElemType& e)
{
if (i<1 || i>L.length)
return false;
e = L.elem[i - 1];
return true;
}3. 顺序表的查找
//顺序表的查找
int SqList::LocateElem(SqList L, ElemType e)
{
for (int i = 0; i < L.length; i++)
if (L.elem[i] == e)
return i + 1;
return 0;
}
4. 顺序表的插入
//顺序表的插入
Status SqList::ListInsert(SqList& L, int i, ElemType e)
{
if ((i < 1) || (i > L.length + 1))
return false;
if (L.length == MAXSIZE)
return false;
for (int j = L.length - 1; j >= i - 1; j--)
L.elem[j + 1] = L.elem[j];
L.elem[i - 1] = e;
L.length++;
return true;
}5. 顺序表的删除
Status SqList::ListDelete(SqList& L, int i)
{
if ((i < 1) || (i > L.length))
return false;
for (int j = i; j <= L.length - 1; j++)
L.elem[j - 1] = L.elem[j];
L.length--;
return false;
}三、整合起来
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define ElemType int
typedef bool Status;
//构建顺序表类
class SqList
{
public:
ElemType* elem;
int length;
public:
//析构函数初始化顺序表
SqList()
{
elem = new ElemType[MAXSIZE];
if(!elem)
exit(OVERFLOW);
length = 0;
}
public:
//顺序表的取值
Status GetElem(SqList L, int i, ElemType& e);
//顺序表的查找
int LocateElem(SqList L, ElemType e);
//顺序表的插入
Status ListInsert(SqList& L, int i, ElemType e);
//顺序表的删除
Status ListDelete(SqList& L, int i);
};
//顺序表的取值
Status SqList::GetElem(SqList L, int i, ElemType& e)
{
if (i<1 || i>L.length)
return false;
e = L.elem[i - 1];
return true;
}
//顺序表的查找
int SqList::LocateElem(SqList L, ElemType e)
{
for (int i = 0; i < L.length; i++)
if (L.elem[i] == e)
return i + 1;
return 0;
}
//顺序表的插入
Status SqList::ListInsert(SqList& L, int i, ElemType e)
{
if ((i < 1) || (i > L.length + 1))
return false;
if (L.length == MAXSIZE)
return false;
for (int j = L.length - 1; j >= i - 1; j--)
L.elem[j + 1] = L.elem[j];
L.elem[i - 1] = e;
L.length++;
return true;
}
//顺序表的删除
Status SqList::ListDelete(SqList& L, int i)
{
if ((i < 1) || (i > L.length))
return false;
for (int j = i; j <= L.length - 1; j++)
L.elem[j - 1] = L.elem[j];
L.length--;
return false;
}