当前位置：首页 > news >正文

顺序表的实现（2）

news 2026/9/1 0:10:25

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型
#define MAXSIZE 100 //顺序表可能达到的最大长度
typedef struct {
ElemType* elem; //存储空间的基地址
int length; //当前长度
} SqList;
Status InitList(SqList& L)
{
//构造一个空的顺序表L
L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if (!L.elem)
exit(OVERFLOW); //存储分配失败退出
L.length = 0; //空表长度为0
return OK;
}
void DestroyList(SqList& L)
{
if (L.elem)
delete[]L.elem; //释放存储空间
}
int ListLength(SqList L)
{
return L.length;
}
bool ListEmpty(SqList L)
{
if (L.length == 0)
return true;
else
return false;
}
Status GetElem(SqList L, int i, ElemType& e) //用e返回L中第i个数据元素的值
{
if (i<1 || i>L.length) //顺序表的位置在1~L.length，那么不符合条件的范围就是
//i<1||i>L.length
return ERROR;
e = L.elem[i - 1]; //数组的第i-1个位置放的就是线性表第i个位置的元素
return OK;
}
int LocateElem(SqList L, ElemType e) //返回L中第1个值与e相同的元素在L中的位置，不存在返回0
{
for (int i = 0; i < L.length; i++)
{
if (L.elem[i] == e)
return i + 1;
}
return 0;
}
Status ListInsert(SqList& L, int i, ElemType e) //在顺序表L中第i个位置插入新的元素e
{
if (i<1 || i>L.length + 1)
{
return ERROR;
}
if (L.length == MAXSIZE) {
return ERROR;
}
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 OK;
}
Status ListDelete(SqList& L, int i) //在顺序表L中删除第i个元素
{
if (i<1 || i>L.length)
return ERROR;
for (int j = i; j <= L.length - 1; j++)
{
L.elem[j - 1] = L.elem[j];
}
--L.length;
return OK;
}
void ListPrint(SqList L)
{
for (int i = 0; i < L.length; i++)
cout << L.elem[i] << ((i == L.length - 1) ? '\n' : ' ');
}
int main()
{
int i;
ElemType e;
SqList L;
string op;
InitList(L);
while (cin >> op) {
if (op == "Empty")
cout << (ListEmpty(L) ? "Empty" : "Not empty") << endl;
else if (op == "Insert") {
cin >> i >> e;
if (ListInsert(L, i, e) == ERROR)
cout << "Insert failed" << endl;
else
ListPrint(L);
}
else if (op == "Length") {
cout << "List length is " << ListLength(L) << endl;
}
else if (op == "GetElem") {
cin >> i;
if (GetElem(L, i, e) == ERROR)
cout << "Out of index" << endl;
else
cout << "The elem at position " << i << " is " << e << endl;
}
else if (op == "LocateElem") {
cin >> e;
i = LocateElem(L, e);
if (i == 0)
cout << e << " is not found in list" << endl;
else
cout << e << " is found at the position " << i << endl;
}
else if (op == "Delete") {
cin >> i;
if (ListDelete(L, i) == ERROR)
cout << "Delete failed" << endl;
else
ListPrint(L);
}
}
DestroyList(L);
return 0;
}