数据结构学习笔记——线性表（一）顺序表

目录

前言

线性表

顺序表

---

前言

我class="superseo">学习数据结构是通过在网上观看教学视频进行学习，但是大多数据结构教程都是使用c语言，而我也是刚从c语言过渡到c++，所以数据结构笔记都会将视频教程上的c语言代码转化为c++代码，代码或有错误，如发现请指正。

在我学习的数据结构教程中还含有时间复杂度和空间复杂度的内容，但由于这一部分比较简单，于是该笔记中将这一部分省去。

在介绍相关内容的时候，太官方的定义过于枯燥乏味，所以只做简单介绍。好，正文开始

线性表

简单来说就是数据在逻辑上呈现出一条线性来储存的。常见的线性表：顺序表，链表，栈，队列...

顺序表

顺序表其实就是数组，只是在数组的基础上，它还要求数据是从头开始连续存储的，不能有跳跃间隔。

比如数组可以这样存：

1

2

3

但是顺序表就要求只能这样存：

1

2

3

顺序表又分为动态顺序表和静态顺序表

静态顺序表特点：如果满了就不允许插入，所以就有了它的缺点：到底给多少空间合适？这很难确定，给小了不够用，给大了又浪费。

而这里则采用动态顺序表，具体代码如下：

#include
#include
#include
using namespace std;
struct Seqlist 
{
	vectorv;
	int size;
	int capacity;
};
void Seqlist_print(Seqlist *ps)
{
	for (auto p = ps->v.begin(); p != ps->v.end(); p++)
	{
		cout << *p << " ";
	}
	cout << endl;
}
void Seqlist_init(Seqlist* ps)
{
	ps->v.resize(0);
	ps->size = ps->capacity = 0;
}
void Seqlist_pushback(Seqlist* ps , int x)//尾插
{
	ps->v.push_back(x);
	ps->size=ps->v.size();
	ps->capacity = ps->v.capacity();
}
void Seqlist_popback(Seqlist* ps)//尾删
{
	ps->v.pop_back();
	ps->size = ps->v.size();
	ps->capacity = ps->v.capacity();
}
void Seqlist_pushfront(Seqlist* ps, int x)//头插
{
	ps->v.insert(ps->v.begin(), x);
	ps->size = ps->v.size();
	ps->capacity = ps->v.capacity();
}
void Seqlist_popfront(Seqlist*ps)//头删
{
	ps->v.erase(ps->v.begin());
	ps->size = ps->v.size();
	ps->capacity = ps->v.capacity();
}
void Seqlist_insert(Seqlist* ps,int pos,int x)//任意位置插入元素
{
	if (pos<0 || pos>ps->size)
	{
		cout << "pos invaild" << endl;
		return;
	}
	ps->v.insert(ps->v.begin() + pos, x);
	ps->size = ps->v.size();
	ps->capacity = ps->v.capacity();
}
void Seqlist_erase(Seqlist* ps, int pos)//任意位置删除元素
{
	if (pos<0 || pos>=ps->size)
	{
		cout << "pos invaild" << endl;
		return;
	}
	ps->v.erase(ps->v.begin() + pos);
	ps->size = ps->v.size();
	ps->capacity = ps->v.capacity();
}
void Seqlist_find(Seqlist* ps, int x)//查找元素
{
	vector::iterator iter = find(ps->v.begin(), ps->v.end(), x); 
	if (iter == ps->v.end())
	{
		cout << "没找到" << endl;
	}
	else
	{
		cout << "下标为:"<v.begin() << endl;
	}
}
void Test_Seqlist()
{
	Seqlist v1;
	Seqlist_init(&v1);
	for (int i = 0; i < 10; i++)
	{
		Seqlist_pushback(&v1,i);
	}
	cout << "尾插:" << endl;
	Seqlist_print(&v1);
	cout << "尾删:" << endl;
	Seqlist_popback(&v1);
	Seqlist_print(&v1);
	cout << "头插:" << endl;
	Seqlist_pushfront(&v1, 10);
	Seqlist_print(&v1);
	cout << "头删:" << endl;
	Seqlist_popfront(&v1);
	Seqlist_print(&v1);
	cout << "在下标为2的位置插入10:" << endl;
	Seqlist_insert(&v1, 2, 10);
	Seqlist_print(&v1);
	cout << "删除下标为2的元素:" << endl;
	Seqlist_erase(&v1,2);
	Seqlist_print(&v1);
	cout << "查找元素1:" << endl;
	Seqlist_find(&v1,1);
}
int main()
{
	Test_Seqlist();
	return 0;
}

结果：