【C/C++】数据结构与算法之顺序表

发布于：2022-11-28 ⋅ 阅读:(573) ⋅ 点赞:(0)

本系列文章主要讲述数据结构与算法。
温馨提示：本文代码主要使用C++编写，且不使用C++的高级特性，但只会c语言的读者最好先提前了解C++的引用符&和动态内存分配等内容。

首先先介绍什么是线性表：简而言之，一个线性表是n个数据元素的有限序列。

这个数据元素没有具体的形式，它可以是一个个整数，也可以是一段段信息。

//表中的某一个元素可以是一个整型变量
int data;
//也可以是一个结构体
struct Data {
	int width;
	int height;
};

线性表是一种逻辑结构，顺序表是一种存储结构。我们可以用顺序存储（顺序表）或链式存储（链表）来表示线性表。这两者的关系可以理解为（或许有些强行比喻）：线性表如果是一块CPU，而顺序结构可以是Inter公司的架构，链式结构可以是AMD公司的架构。两者架构不一样，但它们都是CPU，都具有CPU的功能，且可能在不同应用领域中有各自独特的性能优势。就像顺序表适合随机访问，链表适合增删。本文主要讨论线性表的顺序表示和实现。

定义顺序表相关结构：

//顺序表元素结构
typedef struct {
	int data;
} ElemType;

//顺序表结构
typedef struct {
	ElemType* pElem; //表元素基址
	int length; //表的当前长度
	int listSize; //表尺寸
} SqList;

#define LIST_INIT_SIZE 100 //表存储空间的初始分配量
#define LIST_ALLOC_INC 10 //表存储空间的分配增量

定义表初始化函数：

//表初始化c++版
bool InitList(SqList& list) {
	list.pElem = new ElemType[LIST_INIT_SIZE];
	if (nullptr == list.pElem) {
		return false; //分配失败
	} 

	list.length = 0;
	list.listSize = LIST_INIT_SIZE;
	return true;
}
//表初始化c语言版
//这里给出一次c语言版本，为节省篇幅，以后都只给出c++版本
_Bool InitList(SqList* pList) {
	pList->pElem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (!pList->pElem) {
		return 1; //分配失败
	} 

	pList->length = 0;
	pList->listSize = LIST_INIT_SIZE;
	return 0;
}

定义表销毁函数：

//销毁顺序表
bool DestoryList(SqList& list) {
	if (nullptr == list.pElem) {
		return false;
	}
	
	delete[] list.pElem; //释放表空间
	list.pElem = nullptr;
	return true;
}

定义插入元素函数：

//在顺序表list中第index个位置之前插入新元素e
bool ListInsert(SqList& list, int index, const ElemType& e) {
	//检查表元素指针有效性
	if (nullptr == list.pElem) {
		return false;
	}
	//检验index的合法性，是否越界
	if (index < 1 || index > list.length + 1) {
		return false;
	}
	//表满了，扩展LIST_ALLOC_INC个元素大小的空间
	if (list.length >= list.listSize) {
		list.listSize += LIST_ALLOC_INC;
		ElemType* pTmpElem = new ElemType[list.listSize];
		if (nullptr == pTmpElem) {
			return false;
		}
		
		for (int i = 0; i < list.length; ++i) {
			pTmpElem[i].data = list.pElem[i].data;
		}
		
		delete[] list.pElem;
		list.pElem = pTmpElem;
	}
	//第index个及之后的元素整体向后移一个单位
	/*如果需要扩展空间，插入操作也可与新空间拷贝原数据时一起完成以提高效率，但为了体现模块化和代码优雅感，这里牺牲了一点性能，没有这样做*/
	for (int i = list.length; i >= index; --i) {
		list.pElem[i].data = list.pElem[i - 1].data;
	}
	list.length++; //表目前长度加一
	list.pElem[index - 1].data = e.data; //待插入的元素成为新的第index个元素
	
	return true;
}

定义删除元素函数

//通过下标删除元素, 并以e返回其值
bool ListDelete(SqList& list, int index, ElemType& e) {
	//判断输入下标合法性
	if (index < 1 || index > list.length) {
		return false;
	}
	e = list.pElem[index - 1];
	//第index个及之后的元素整体向前移一个单位
	for (int i = index; i < list.length; ++i) {
		list.pElem[i - 1].data = list.pElem[i].data;
	}
	list.length--; //表目前长度减一
	
	return true;
}

定义打印表函数:

void PrintList(const SqList& list) {
	std::cout << "Length: " << list.length << std::endl;
	for (int i = 0; i < list.length; ++i) {
		std::cout << list.pElem[i].data << " ";
	}
	std::cout << std::endl;
}

在顺序表中插入或删除一个数据元素，平均约移动表中一半元素。若表长为n，则插入与删除算法的时间复杂度为O(n)。
顺序表还有如查找、合并等算法，实现起来并不困难，读者可自行尝试。

在main函数进行测试的所有代码：

#include <iostream>

//顺序表元素结构
typedef struct {
	int data;
} ElemType;

//顺序表结构
typedef struct {
	ElemType* pElem; //表元素基址
	int length; //表的当前长度
	int listSize; //表尺寸
} SqList;

#define LIST_INIT_SIZE 100 //表存储空间的初始分配量
#define LIST_ALLOC_INC 10 //表存储空间的分配增量

//初始化表
bool InitList(SqList& list);
//销毁表
bool DestoryList(SqList& list);
//在表中第index个位置之前插入新元素e
bool ListInsert(SqList& list, int index, const ElemType& e);
//删除表中第index个元素，并返回其值给e
bool ListDelete(SqList& list, int index, ElemType& e);
//打印表
void PrintList(const SqList& list);

int main() {
	SqList mySqList;
	InitList(mySqList);

	ElemType e1 = { 10 }, e2 = { 20 }, e3 = { 30 };
	//在第一个元素之前插入el并打印表
	ListInsert(mySqList, 1, e1);
	PrintList(mySqList);
	//在第一个元素之前插入e2并打印表
	ListInsert(mySqList, 1, e2);
	PrintList(mySqList);
	//在第一个元素之前插入e3并打印表
	ListInsert(mySqList, 1, e3);
	PrintList(mySqList);

	ElemType ret;
	//删除第二个元素
	ListDelete(mySqList, 2, ret);
	PrintList(mySqList);
	//删除第一个元素
	ListDelete(mySqList, 1, ret);
	PrintList(mySqList);

	DestoryList(mySqList);

	return 0;
} 

bool InitList(SqList& list) {
	list.pElem = new ElemType[LIST_INIT_SIZE];
	if (nullptr == list.pElem) {
		return false; //分配失败
	} 

	list.length = 0;
	list.listSize = LIST_INIT_SIZE;
	return true;
}

bool DestoryList(SqList& list) {
	if (nullptr == list.pElem) {
		return false;
	}
	
	delete[] list.pElem; //释放表空间
	list.pElem = nullptr;
	return true;
}

bool ListInsert(SqList& list, int index, const ElemType& e) {
	//检查表元素指针有效性
	if (nullptr == list.pElem) {
		return false;
	}
	//检验index的合法性，是否越界
	if (index < 1 || index > list.length + 1) {
		return false;
	}
	//表满了，扩展LIST_ALLOC_INC个元素大小的空间
	if (list.length >= list.listSize) {
		list.listSize += LIST_ALLOC_INC;
		ElemType* pTmpElem = new ElemType[list.listSize];
		if (nullptr == pTmpElem) {
			return false;
		}
		
		for (int i = 0; i < list.length; ++i) {
			pTmpElem[i].data = list.pElem[i].data;
		}
		
		delete[] list.pElem;
		list.pElem = pTmpElem;
	}
	//第index个及之后的元素整体向后移一个单位
	/*如果需要扩展空间，插入操作也可与新空间拷贝原数据时一起完成以提高效率，但为了体现模块化和代码优雅感，这里牺牲了一点性能，没有这样做*/
	for (int i = list.length; i >= index; --i) {
		list.pElem[i].data = list.pElem[i - 1].data;
	}
	list.length++; //表目前长度加一
	list.pElem[index - 1].data = e.data; //待插入的元素成为新的第index个元素
	
	return true;
}

bool ListDelete(SqList& list, int index, ElemType& e) {
	//判断输入下标合法性
	if (index < 1 || index > list.length) {
		return false;
	}
	e = list.pElem[index - 1];
	//第index个及之后的元素整体向前移一个单位
	for (int i = index; i < list.length; ++i) {
		list.pElem[i - 1].data = list.pElem[i].data;
	}
	list.length--; //表目前长度减一
	
	return true;
}

void PrintList(const SqList& list) {
	std::cout << "Length: " << list.length << std::endl;
	for (int i = 0; i < list.length; ++i) {
		std::cout << list.pElem[i].data << " ";
	}
	std::cout << std::endl;
}

运行结果如下图：

在这里插入图片描述

参考文献：《数据结构》(c语言版) ——严蔚敏、吴伟明著
文章持续更新中！
求点赞、收藏！欢迎在评论区留言，有问必答！
作者水平有限，如果有误，欢迎指正！
编译环境：Visual Studio 2019

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布