C++ 顺序表 完整代码模版 数据结构入门 可直接复制运行
·
顺序表(概念+代码)
一、顺序表的概念
1. 顺序表的初始化
二、顺序表的元素插入
1.元素插入的概念
2.元素插入的步骤
3.伪代码实现
三、顺序表的元素删除
1.元素删除的概念
2.元素删除的步骤
3.伪代码实现
四、顺序表的元素查找
1.元素查找的概念
2.元素查找的步骤
3.伪代码实现
五、顺序表的元素索引
1.元素索引的概念
2.元素索引的步骤
3.伪代码实现
六、顺序表的元素修改
1.元素修改的概念
2.元素修改的步骤
3.伪代码实现
七、顺序表中的辅助函数
1.销毁,遍历,判空,大小获取
八、简单介绍C++顺序表中的 vector
九、顺序表完整可运行源码
1.SequentialList.h
2. SequtialistList.cpp
3. main.cpp
一、顺序表的概念
顺序表是一种线性的数据结构，其中数据元素按照特定的顺序存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引（或者叫下标）相关联，索引从0开始递增。
1. 顺序表的初始化
typedef int eleType;
typedef struct SequentialList {
eleType* elements; // 动态数组指针
int size; // 表中实际存储元素个数
int capacity; // 表的最大容量
}SL;
// 初始化顺序表 (给数组分配内存 + 重置参数)
void initializeList(SequentialList* list, int capacity)
{
list->elements = new eleType[capacity];
list->size = 0;
list->capacity = capacity;
}
二、顺序表的元素插入
1.元素插入的概念
顺序表的元素插入,就是值给定一个索引和一个元素,将这个元素插入到对应的索引位置上,这个位置以后的所有元素都要往后移动一个位置。
2.元素插入的步骤
第1步：判断插入位置是否合法，合法区间 [0,size] ，如果不合法则抛出异常。
第2步：判断顺序表是否已满，满了就需要扩容，而扩容一般是在顺序表原有的容量上进行倍增。
第3步：将要插入位置后面的元素向后移动1位，为新元素腾出空间。
第4步：将新元素插入到指定位置。
第5步：更新顺序表的大小（size++）。
3.伪代码实现
// 插入
void insert(SequentialList* list, int index, eleType element)
{
if (index < 0 || index > list->size) {
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
// 判断表满,如果满了,就扩容.
if (list->size == list->capacity) {
int newCapacity = list->capacity * 2;
eleType* newElements = new eleType[newCapacity];
for (int i = 0; i < list->size; ++i) {
newElements[i] = list->elements[i];
}
delete[] list->elements;
list->elements = newElements;
list->capacity = newCapacity;
}
// 注意 i > index 就可以将index极其后面的元素后移
for (int i = list->size; i > index; --i) {
list->elements[i] = list->elements[i - 1];
}
list->elements[index] = element;
list->size++;
}
三、顺序表的元素删除
1.元素删除的概念
顺序表的元素删除,就是指给定一个索引,将这个索引上的元素删除,并且把这个索引位置以后得所有元素都往前移动一个位置。
2.元素删除的步骤
第1步：判断删除位置是否合法,合法区间 [0,size-1] ，如果不喝法则抛出异常。
第2步：如果删除位置为最后一个元素，直接将顺序表的大小减 1。
第3步：如果删除位置不是最后一个元素，将要删除位置之后的元素向前移动，覆盖掉要删除的元素，其实删除本质就是覆盖。
第4步：更新顺序表的大小（size–）。
3.伪代码实现
// 删除(通过指定下标)
void deleteElement(SequentialList* list, int index)
{
if (index < 0 || index >= list->size) {
// 非法下标：抛出异常，程序报错并停止
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
// 注意 终止条件为i < list.size - 1,而不是i < list.size,因为下面数组下标到 i+1
for (int i = index; i < list->size - 1; i++) {
list->elements[i] = list->elements[i + 1];
}
list->size--;
}
四、顺序表的元素查找
1.元素查找的概念
顺序表的元素查找,是指在顺序表中查找指定元素是否存在,如果存在则返回该元素的索引,否则返回 -1,由于需要遍历整个顺序表进行元素对比,所以查找的时间复杂度为O(n)。
2.元素查找的步骤
第1步：遍历整个顺序表，对顺序表中的每个元素和指定元素进行比较如果相等则返回当前的索引；
第2步：如果遍历完所有的顺序表元素，都没有找到相等的元素，则返回 -1；
3.伪代码实现
// 查找(按值查找,返回数组下标)
int findElement(SequentialList* list, eleType element)
{
for (int i = 0; i < list->size; i++) {
if (list->elements[i] == element) {
return i;
}
}
return -1;
}
五、顺序表的元素索引
1.元素索引的概念
顺序表的索引，是指给定一个索引值，通过下标访问，直接在顺序表中获取元素的值，时间复杂度为 O(1)。
2.元素索引的步骤
第1步：先判断索引下标是否合法，合法区间 [0，size - 1]
第2步：直接通过索引访问即可获得对应的元素。
3.伪代码实现
// 索引(给定索引值,返回对应元素值)
eleType getElement(SequentialList* list, int index)
{
if (index < 0 || index >= list->size) {
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
return list->elements[index];
}
六、顺序表的元素修改
1.元素修改的概念
顺序表的元素修改，是指将顺序表中指定位置的元素更新为新的值。
2.元素修改的步骤
第1步：先判断索引下标是否合法，合法区间 [0，size - 1]
第2步：通过索引访问即可获得对应元素，修改成指定的值。
3.伪代码实现
// 修改
void updateElement(SequentialList* list, int index, eleType value)
{
if (index < 0 || index >= list->size) {
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
list->elements[index] = value;
}
七、顺序表中的辅助函数
// 销毁
void destroyList(SequentialList* list)
{
delete[] list->elements;
}
// 求长
int size(SequentialList* list)
{
return list->size;
}
// 判空
bool isEmpty(SequentialList* list)
{
return list->size == 0;
}
// 遍历
void printfList(SL* list)
{
for (int i = 0; i < list->size; i++) {
cout << list->elements[i] << " ";
}
cout << endl;
}
八、简单介绍C++顺序表中的 vector
#include <iostream>
#include <vector> // 导入C++ <vector> 头文件
using namespace std;
int main()
{
// 初始化
vector<int>ret;
// 获取大小
cout << ret.size() << endl; // 开始默认为0
// 插入元素(尾插)
ret.push_back(520);
// 索引
cout << ret[0] << endl;
vector<float>ret1 = { 1.1 , 2.2 , 3.3 , 4.4 ,5.5 };
ret1.push_back(1314);
cout << ret1[5] << endl;
// 遍历输出
for (int i = 0; i < ret1.size(); i++) {
cout << ret1[i] << " ";
}
cout << endl;
return 0;
}
九、顺序表完整可运行源码
1.SequentialList.h
#ifndef SEQUENTIALLIST_H
#define SEQUENTIALLIST_H
#include<iostream>
using namespace std;
#define eleType int
typedef struct SequentialList {
eleType* elements;
int size; // 表中实际存储的大小
int capacity; // 表中可存储的大小
}SL;
void initializeList(SequentialList* list, int capacity);
void destroyList(SequentialList* list);
int size(SequentialList* list);
bool isEmpty(SequentialList* list);
void printfList(SL* list);
void insert(SequentialList* list, int index, eleType element);
void deleteElement(SequentialList* list, int index);
int findElement(SequentialList* list, eleType element);
eleType getElement(SequentialList* list, int index);
void updateElement(SequentialList* list, int index, eleType value);
#endif
2. SequtialistList.cpp
#include "SequentialList.h"
// 初始化
void initializeList(SequentialList* list, int capacity)
{
list->elements = new eleType[capacity];
list->size = 0;
list->capacity = capacity;
}
// 销毁
void destroyList(SequentialList* list)
{
delete[] list->elements;
}
// 求长
int size(SequentialList* list)
{
return list->size;
}
// 判空
bool isEmpty(SequentialList* list)
{
return list->size == 0;
}
// 遍历
void printfList(SL* list)
{
for (int i = 0; i < list->size; i++) {
cout << list->elements[i] << " ";
}
cout << endl;
}
// 插入
void insert(SequentialList* list, int index, eleType element)
{
if (index < 0 || index > list->size) {
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
// 判断表满,如果满了,就扩容.
if (list->size == list->capacity) {
int newCapacity = list->capacity * 2;
eleType* newElements = new eleType[newCapacity];
for (int i = 0; i < list->size; ++i) {
newElements[i] = list->elements[i];
}
delete[] list->elements;
list->elements = newElements;
list->capacity = newCapacity;
}
// 注意 i > index 就可以将index极其后面的元素后移
for (int i = list->size; i > index; --i) {
list->elements[i] = list->elements[i - 1];
}
list->elements[index] = element;
list->size++;
}
// 删除
void deleteElement(SequentialList* list, int index)
{
if (index < 0 || index >= list->size) {
// 非法下标：抛出异常，程序报错并停止
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
// 注意 终止条件为i < list.size - 1,而不是i < list.size,因为下面数组下标到 i+1
for (int i = index; i < list->size - 1; i++) {
list->elements[i] = list->elements[i + 1];
}
list->size--;
}
// 查找
int findElement(SequentialList* list, eleType element)
{
for (int i = 0; i < list->size; i++) {
if (list->elements[i] == element) {
return i;
}
}
return -1;
}
// 元素索引 : 获取第index个元素
eleType getElement(SequentialList* list, int index)
{
if (index < 0 || index >= list->size) {
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
return list->elements[index];
}
// 修改元素
void updateElement(SequentialList* list, int index, eleType value)
{
if (index < 0 || index >= list->size) {
throw std::invalid_argument("Invalid index"); // 报错+强制停止
}
list->elements[index] = value;
}
3. main.cpp
#include "SequentialList.h"
int main()
{
SL list; // 定义结构体变量
initializeList(&list, 10); // 改成传指针：&list
cout << "1. 插入10个元素:";
for (int i = 0; i < 10; i++) {
insert(&list, i, i * 10);
}
printfList(&list);
cout << endl << "2.删除数组下标为5的元素:";
deleteElement(&list,5);
printfList(&list);
cout << endl << "3. 查找元素30:";
int idx = findElement(&list, 30);
printfList(&list);
cout << endl << "4. 查找索引下标为1的元素:";
cout << getElement(&list, 1);
cout << endl << endl << "5. 修改数组下标为0的元素为520: ";
updateElement(&list, 0, 520);
printfList(&list);
destroyList(&list);
return 0;
}
更多推荐
20
0- 0
已为社区贡献5条内容
所有评论(0)