顺序表的操作

顺序表的操作

这里先定义个顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

#define MAXSIZE 100

typedef struct{
int *elems;
int length;
int size;
}Sqlist;

Sqlist list;

顺序表初始化

  • 定义bool类型函数 initList() ,初始化成功为true,失败为false
1
2
3
4
5
6
7
8
9
10
11
//初始化顺序表,创建一个空表
bool initList(Sqlist &L) //L本身要改变所以为引用型
{
L.elems = new int[MAXSIZE]; //为顺序表分配内存空间
if(!L.elems) return false; //存储分配失败返回false

//分配成功则初始化
L.length = 0;
L.size = MAXSIZE;
return true; //成功并返回true
}
  • 定义函数 outputInfoList() 用于输出顺序表信息
1
2
3
4
5
6
7
8
9
//输出数据表信息
void outputInfoList(Sqlist &L)
{
cout << "顺序表储存空间" << L.size << ",已经保存元素个数" << L.length << endl;
for(int i = 0; i <= L.length - 1;i++){
cout << L.elems[i] << " ";
}
cout << endl;
}

找查元素

  • 定义函数 findElem() 在顺序表中找查一个等于e的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 用于找查顺序表中的元素
* 参数e为要找查的元素
* 若找到则返回元素下标
* 若没找到则返回-1
*/
int findElem(Sqlist L, int e) //这里我们不改变L,所以不用引用类型
{
for(int i = 0; i < L.length; i++){
if(e == L.elems[i])
return i; //若找到则返回元素下标
}
return -1; //若没找到则返回-1
}

插入元素

尾部添加元素

在尾部添加元素要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 故定义函数 listAppend()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 在顺序表尾部插入元素
* 参数e为要插入到尾部的元素
* 若成功则返回true,失败(顺序表已经满了)则返回false
*/
bool listAppend(Sqlist &L, int e)
{
if(L.length == L.size)
//顺序表满了
return false;
//没满则尾部插入元素并返回true
L.elems[L.length] = e;
L.length++;
return true;
}

在特定位置插入元素

在特定位置插入要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 要移动后面的元素而不能移动前面的元素,否则后面的元素会被前面的覆盖

定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//在顺序表p位置(0 <= p <= length)上插入元素e
bool insertElem(Sqlist &L, int p, int e)
{
if(p < 0 || p > L.length || L.length == MAXSIZE)
/*
* 如果位置错误
* 或者表长已经达到最大允许值
* 此时插入不成功并返回false
*/
return false;
for(int i = L.length - 1; i >= p; --i)
//从后往前将元素相后方移动一个位置
L.elems[i+1] = L.elems[i];
L.elems[p] = e; //插入元素e到p位置
L.length++;

return true; //成功返回true
}

删除元素

删除元素要考虑以下几点

  • 顺序表位置是否正确
  • 成功后长度要减去1
  • 后方元素向前移动一个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除p位置的元素
bool delElem(Sqlist &L, int p, int &e)
{
//位置错误返回false
if(p < 0 || p > L.length - 1) return false;
e = L.elems[p]; //将被删除的元素赋值给e
for(int i = p; i < L.length - 1; i++)
{
//从p开始后方元素向前移动一个位置
L.elems[i] = L.elems[i+1];
}

L.length--; //长度减去1
return true; //成功返回true

}

顺序表的销毁

  • 在初始化函数中,用了new来分配内存,所以在销毁时要释放内存
1
2
3
4
5
6
7
void destroy(Sqlist &L)
{
//内存存在则释放内存
if(L.elems) delete []L.elems;
L.length = 0;
L.size = 0;
}
作者

CairBin

发布于

2021-08-09

更新于

2021-08-09

许可协议

评论