数据结构---顺序表

概念

1.概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构

1. 静态顺序表
   数组大小定死,太小会不够用,太大会浪费
   工程中不会采用
2. 动态顺序表
   可以动态变动数组,如果数组大小较小,可以进行扩容

2.接口实现(c++实现)

SeqList.h

#pragma once
#include <stdlib.h>
#include <iostream>
using namespace std;
//把int类型起名为Element,方便后面修改顺序表内的元素
typedef int Element;

class SeqList
{
public:
	//构造函数初始化对象
	//并且使用缺省参数来代替无参数传入时的初始化
	SeqList(int size = 0, int capacity = 0);
	
	//尾插法,传入数据
	void PushBack(Element val);

	//头插法
	void PushFront(Element val);

	//尾删法
	void PopBack();

	//头删法
	void PopFront();

	//任意位置插入
	void Insert(int pos, Element val);

	//任意位置删除
	void Erase(int pos);
	//打印数据
	void Print();

	//检查容量够不够,不够扩容
	void CheckCapacity();
	//查找
	int Find(Element x);
	//修改
	void Modify(int pos, Element x);
	//建立析构函数用于在类的生命周期结束时
	//一般要对其内存空间进行清理
	~SeqList();

private:
	Element* _a;
	int _size;//数组中现存的数据个数
	int _capacity;//数组容量
};

SeqList.cpp

#include "SeqList.h"

SeqList::SeqList(int size, int capacity)
{
	//初始化类的对象
	_size = size;
	_capacity = capacity;
	//申请空间,创建动态数组
	_a = (Element*)malloc(sizeof(Element) * _capacity);
}

void SeqList::PushBack(Element val)
{
	//检查数据个数和容量的关系,容量小进行扩容
	CheckCapacity();
	_a[_size++] = val;
}
void SeqList::PushFront(Element val)
{
	CheckCapacity();
	int end = _size;
	//从后向前覆盖
	while (end - 1 >= 0)
	{
		_a[end] = _a[end - 1];
		end--;
	}
	_size++;
	_a[0] = val;//第一个数据进行赋值为输入的数据
}

void SeqList::PopBack()
{
	if (_size == 0)return; 
	_size--;
}
void SeqList::PopFront()
{
	int begin = 0;
	while (begin < _size - 1)
	{ 
		_a[begin] = _a[begin + 1];
		begin++;
	}
	_size--;
}
void SeqList::Insert(int pos, Element val)
{
	if (pos < 0 || pos > _size) return;
	int end = _size;  
	while (end - 1 >= pos)
	{
		_a[end] = _a[end - 1];
		end--;
	}
	_a[pos] = val;
	_size++;
}
void SeqList::Erase(int pos)
{
	if (pos < 0 || pos >= _size) return;
	int begin = pos;
	while (begin + 1 <= _size - 1)
	{
		_a[begin] = _a[begin + 1];
		begin++;
	}
	_size--;
}
//打印数据
void SeqList::Print()
{
	for (int i = 0; i < _size; i++)
	{
		cout << _a[i] << " ";
	}
	cout << endl;
}


void SeqList::CheckCapacity()
{
	//_size已指向外界,申请空间
	if (_size == _capacity)
	{
		Element* tem = (Element*)realloc(_a, sizeof(Element) * _capacity * 2);
		_a = tem;
		_capacity *= 2;
	}
}

int SeqList::Find(Element x)
{
	for (int i = 0; i < _size; i++)
	{
		if (_a[i] == x)
			return i;
	}
	return -1; 
}

void SeqList::Modify(int pos, Element x)
{
	if (pos < 0 && pos >= _size) return;
	_a[pos] = x;
}

SeqList::~SeqList()
{
	free(_a);//释放内存
	_a = nullptr;//置空
	_size = 0;
	_capacity = 0;
}

main.cpp(用于测试)

#include "SeqList.h"

int main()
{
	SeqList a(0, 4);

	a.PushBack(1);
	a.PushBack(2);
	a.PushBack(3);
	a.PushBack(4);  
	a.PushBack(5);
	a.PushBack(6);
	//a.PushFront(6); 
	//a.Insert(2, 111);
	//a.Insert(2, 111);
	//a.Insert(2, 111);
	//a.Erase(0);
	//a.Erase(0);
	//a.Erase(0);
	int pos = a.Find(6);
	if (pos != -1)
		a.Erase(pos);
	/*a.PopFront();
	a.PopFront();
	a.PopFront();*/
	//a.PopBack();
	//a.PopBack();
	//a.PopBack();
	//a.PopBack();


	a.Print();
	return 0;
}