JZTXT

10.顺序表

发布时间 2023-06-13 13:17:53作者: CodeMagicianT

1.顺序表的定义

  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
  • 顺序表：可动态增长的数组，要求数据是连续存储的
typedef struct _SqList SqList;

struct _SqList
{
	int* elems;//顺序表的基地址
	int length;//顺序表的长度
	int size;//顺序表总的空间大小
};

typedef struct
{
	int* elems;//顺序表的基地址
	int length;//顺序表的长度
	int size;//顺序表总的空间大小
}SqList;

2.顺序表的初始化

bool initList(SqList& L)//构造一个空的顺序表L
{
	L.elems = new int[MAX_SIZE];//为顺序表分配MAX_SIZE个int元素的空间
	if (!L.elems) return false;

	L.length = 0;
	L.size = MAX_SIZE;
	return true;
}

3.顺序表的打印

void listPrint(SqList& L)
{
	cout << "顺序表的存储空间size:" << L.size << "，已保存的元素个数length：" << L.length << endl;
	for (int i = 0; i <= L.length - 1; i++)
	{
		cout << L.elems[i] << " ";
	}
	cout << endl;
}

4.表尾添加元素

bool listAppend(SqList& L, int e)
{
	if (L.length == L.size)  return false;//存储空间已满

	L.elems[L.length] = e;
	L.length++;//表长增加1
	return true;
}

//2.添加元素
int count = 0;
cout << "请输入要添加的元素个数：" << endl;
cin >> count;

for (int i = 0; i < count; i++)
{
    cout << "\n请输入要添加的元素e：";
    cin >> e;
    if (listAppend(list, e))
    {
        cout << "添加成功！" << endl;
    }
    else
    {
        cout << "添加失败！" << endl;
    }
}
listPrint(list);

5.表中任意位置插入元素

bool listInsert(SqList &L, int i, int e)
{
	if (i < 0 || i >= L.length) return false;//i值不合法
	if (L.length == L.size) return false;//存储空间已满

	for (int j = L.length - 1; j >= i; j--)
	{
		L.elems[j + 1] = L.elems[j];//从最后一个元素开始后移，直到下标为i的元素后移
	}

	L.elems[i] = e;//将新元素e放入第i的位置
	L.length++;//表长加1

	return true;
}

//3.插入元素
cout << "请输入要插入元素的个数,（先输入插入位置，后输入元素个数）：" << endl;
cin >> i >> e;

if (listInsert(list, i, e))
{
    cout << "插入成功！" << endl;
}
else
{
    cout << "插入失败！" << endl;
}
listPrint(list);

6.表中任意位置删除元素

bool listDelete(SqList& L, int i)
{
	if (i < 0 || i >= L.length) return false;//删除位置无效

	if (i == L.length - 1)//删除最后一个元素
	{
		L.length--;
		return true; 
	}

	for (int j = i; j < L.length - 1; j++)
	{
		L.elems[j] = L.elems[j + 1];//删除位置的后续元素依次往前移
	}
	L.length--;
	return true;
}

//4.删除元素
cout << "请输入要删除元素的位置：";
cin >> i;
if (listDelete(list, i))
{
    cout << "删除成功！" << endl;
}
else
{
    cout << "删除失败!" << endl;
}
listPrint(list);

7.链表销毁

void destroyList(SqList& L)
{
	if (L.elems) delete[]L.elems;//释放存储空间
	L.length = 0;
	L.size = 0;
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
using namespace std;

#define MAX_SIZE 100

//typedef struct _SqList SqList;
//
//struct _SqList
//{
//	int* elems;//顺序表的基地址
//	int length;//顺序表的长度
//	int size;//顺序表总的空间大小
//};

typedef struct
{
	int* elems;//顺序表的基地址
	int length;//顺序表的长度
	int size;//顺序表总的空间大小
}SqList;

bool initList(SqList& L)//构造一个空的顺序表L
{
	L.elems = new int[MAX_SIZE];//为顺序表分配MAX_SIZE个int元素的空间
	if (!L.elems) return false;

	L.length = 0;
	L.size = MAX_SIZE;
	return true;
}

void listPrint(SqList& L)
{
	cout << "顺序表的存储空间size:" << L.size << "，已保存的元素个数length：" << L.length << endl;
	for (int i = 0; i <= L.length - 1; i++)
	{
		cout << L.elems[i] << " ";
	}
	cout << endl;
}

bool listAppend(SqList& L, int e)
{
	if (L.length == L.size)  return false;//存储空间已满

	L.elems[L.length] = e;
	L.length++;//表长增加1
	return true;
}

bool listInsert(SqList &L, int i, int e)
{
	if (i < 0 || i >= L.length) return false;//i值不合法
	if (L.length == L.size) return false;//存储空间已满

	for (int j = L.length - 1; j >= i; j--)
	{
		L.elems[j + 1] = L.elems[j];//从最后一个元素开始后移，直到下标为i的元素后移
	}

	L.elems[i] = e;//将新元素e放入第i的位置
	L.length++;//表长加1

	return true;
}

bool listDelete(SqList& L, int i)
{
	if (i < 0 || i >= L.length) return false;//删除位置无效

	if (i == L.length - 1)//删除最后一个元素
	{
		L.length--;
		return true; 
	}

	for (int j = i; j < L.length - 1; j++)
	{
		L.elems[j] = L.elems[j + 1];//删除位置的后续元素依次往前移
	}
	L.length--;
	return true;
}

void destroyList(SqList& L)
{
	if (L.elems) delete[]L.elems;//释放存储空间
	L.length = 0;
	L.size = 0;
}

int main()
{
	SqList list;
	int i, e;
	cout << "顺序表的初始化：" << endl;
	//1.初始化
	if (initList(list))
	{
		cout << "顺序表初始化成功！" << endl;
	}

	listPrint(list);

	//2.添加元素
	int count = 0;
	cout << "请输入要添加的元素个数：" << endl;
	cin >> count;

	for (int i = 0; i < count; i++)
	{
		cout << "\n请输入要添加的元素：";
		cin >> e;
		if (listAppend(list, e))
		{
			cout << "添加成功！" << endl;
		}
		else
		{
			cout << "添加失败！" << endl;
		}
	}
	listPrint(list);

	//3.插入元素
	cout << "请输入要插入元素的个数,（先输入插入位置，后输入所插入的元素）：" << endl;
	cin >> i >> e;

	if (listInsert(list, i, e))
	{
		cout << "插入成功！" << endl;
	}
	else
	{
		cout << "插入失败！" << endl;
	}
	listPrint(list);

	//4.删除元素
	cout << "请输入要删除元素的位置：";
	cin >> i;
	if (listDelete(list, i))
	{
		cout << "删除成功！" << endl;
	}
	else
	{
		cout << "删除失败!" << endl;
	}
	listPrint(list);

	//5.销毁链表
	destroyList(list);

	system("pause");
	return EXIT_SUCCESS;
}

参考资料来源：

奇牛学院