C++实现顺序表

顺序表,一种线性表,因此顺序表是线性的. 因为顺序表在物理结构与逻辑结构都是连续的.意味着在内存中是连续存储的,形如数组的内存存储方式,我将用数组实现顺序表. 实现顺序表的主要功能为:增删查改. 顺序表是一种简单的数据结构,原理与实现并不难 主要维护下标size,内存空间capacity的大小即可

Seqlist.h头文件声明

#pragma once
#include<iostream>
#include<cstdlib>
#include<cassert>
using namespace std;
// 顺序表结构定义
typedef int SLDataType;
class SeqList {
public:
	SLDataType* arr;
	int size;
	int capacity;
};
typedef SeqList SL;
//检查顺序表容量是否合理
void checkSLCaoacity(SL* ps);
//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);

//顺序表的插入操作
//头插尾插
void SLPushFront(SL* ps,SLDataType x);
void SLPushBack(SL* ps, SLDataType x);
//头删尾删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//选择插入
void SLInsert(SL* ps,int i, SLDataType x);
//选择删除
void SLDelete(SL* ps, SLDataType x);

//顺序表的查找操作
void SLFind(SL* ps, SLDataType x);
//顺序表的修改操作
void SLUpdate(SL* ps, int i, SLDataType x);

//输出所以元素
void SLPrint(SL* ps);

Seqlist.cpp原文件中存方法

#include"SeqList.h"

void SLInit(SL* ps) {
	ps->arr = NULL;
	ps->size=ps->capacity=0;
}

void SLDestroy(SL* ps) {
	if (ps->arr) {
		delete[] ps->arr;
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void checkSLCaoacity(SL* ps) {
	//先判断空间够不够
	if (ps->size == ps->capacity) {
		int newCapacity = (ps->capacity == 0) ? sizeof(SLDataType) : 2 * ps->capacity;
		SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (!temp) {
			perror("realloc failed");
			exit(1);
		}
		ps->arr = temp;
		//delete(temp);
		ps->capacity = newCapacity;
	}
}
	
//头插尾插
void SLPushFront(SL* ps, SLDataType x) {
	assert(ps);//传其他类型指针会导致崩溃，给爷爬
	checkSLCaoacity(ps);
	//插入
	for (int i = ps->size; i > 0; i--) {
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
void SLPushBack(SL* ps, SLDataType x) {
	assert(ps);
	checkSLCaoacity(ps);
	ps->arr[ps->size++] = x;
}
//头删尾删
void SLPopFront(SL* ps) {
	assert(ps);
	if (ps->size == 0) {
		return;
	}
	for (int i = 0; i < (ps->size--) - 1; i++) {
		ps->arr[i + 1] = ps->arr[i];
	}
}
void SLPopBack(SL* ps) {
	assert(ps);
	if (ps->size == 0) {
		return;
	}
	ps->size--;
}
//选择插入
void SLInsert(SL* ps, int i, SLDataType x) {
	assert(ps);
	checkSLCaoacity(ps);
	//1 2 3 4 5 size
	//0 1 2 3 4 
	for (int j = ps->size; j >i; j--) {
		ps->arr[j] = ps->arr[j - 1];
	}
	ps->arr[i] = x;
	ps->size++;
}
//选择删除
void SLDelete(SL* ps, SLDataType x) {
	assert(ps);
	if (ps->size == 0) { return; }
	for (int j = 0; j < ps->size; j++) {
		if (ps->arr[j] == x) {
			for (int k = j; k < ps->size - 1; k++) {
				ps->arr[k] = ps->arr[k + 1];
			}
			ps->size--;
			return;
		}
	}
	cout << "没有找到要删除的元素" << '\n';
}

//顺序表的查找操作
void SLFind(SL* ps, SLDataType x) {
	assert(ps);
	for (int i = 0; i <= ps->size - 1; i++) {
		if (ps->arr[i] == x) {
			cout << "找到了第" << i + 1 << "个元素\n";
			cout << "值为:" << ps->arr[i] << '\n';
			return;
		}
	}
	cout << "没有找到要查找的元素" << '\n';
}
//顺序表的修改操作
void SLUpdate(SL* ps, int i, SLDataType x) {
	assert(ps);
	checkSLCaoacity(ps);
	if (i <= 0 || i > ps->size - 1) {
		cout << "索引越界" << '\n';
		return;
	}
	ps->arr[i - 1] = x;
}

//输出所有元素
void SLPrint(SL* ps) {
	assert(ps);
	checkSLCaoacity(ps);
	for (int i = 0; i < ps->size; i++) {
		cout << ps->arr[i] << " ";
	}
	cout << '\n';
}

test.cpp源文件中用于测试实现的功能

#include"SeqList.h"

void test01() {
	SL s;
	SLInit(&s);//初始化
	//增删查改
	//使用for循环插入100个元素
	for (int i = 1; i <= 100; i++)
	{
		if(i&1)
			SLPushFront(&s, i);
		else
			SLPushBack(&s, i);
	}
	//输出所有元素
	SLPrint(&s);
	//查找元素
	SLFind(&s, 55);
	SLFind(&s, 999);
	//删除元素
	SLDelete(&s, 100);
	SLDelete(&s, 404);
	SLPrint(&s);
	//修改元素
	SLUpdate(&s, 55, 969696);
	SLPrint(&s);
	SLDestroy(&s);//销毁
}

int main()
{
	test01();
	return 0;
}