C语言顺序表

不是风动233 2022-06-03 我要评论

顺序表是什么

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

总的来说，顺序表类似于数组，下标对应的是相应的元素（如图所示）

顺序表的结构体

typedef struct
{
	SLDataType *a;
	int size;//表示数组中存储了多少个数据
	int capacity;//数组实际存储数据的空间容量是多大
}SL;

其中的SLDataType*a的意思是可以动态开辟空间--相当于数组，因为数组表示的是首元素的地址，这里是直接换成了指针，也指的是地址和数组的意思一样！

typedef int SLDataType;//重命名，到时候方便更改类型

顺序表的接口函数

void menu();//菜单
void SeqListInit(SL*ps);//初始化
void SeqListPushBack(SL*ps, SLDataType x);//往后加元素
void SeqListPush(SL*ps, SLDataType n);//在顺序表中添加元素
void SeqListPopBack(SL*ps);//删除最后一个元素
void SeqListPushFront(SL*ps, SLDataType x);//往前面加元素
void SeqListPopFront(SL*ps);//删除第一个元素
void SepListdisplay(SL*ps);//陈列
void SeqListPushMid(SL*ps, SLDataType x,SLDataType z);//往中间加元素
void SeqListPopMid(SL*ps,SLDataType x);//删除中间某一个元素

这里只是先对一些函数进行声名，还没有进行创建函数！

顺序表相关操作的菜单

void menu()
{
	cout << "\t\t\t******************************************************************" << endl;
	cout << "\t\t\t****************   注意！每次都要先进行初始化  *******************" << endl;
	cout << "\t\t\t****************    1.输入-1  退出程序         *******************" << endl;
	cout << "\t\t\t****************    2.输入1   初始化           *******************" << endl;
	cout << "\t\t\t****************    3.输入2   添加元素         *******************" << endl;
	cout << "\t\t\t****************    4.输入3   陈列元素         *******************" << endl;
	cout << "\t\t\t****************    5.输入4   往最后加元素     *******************" << endl;
	cout << "\t\t\t****************    6.输入5   往前面加元素     *******************" << endl;
	cout << "\t\t\t****************    7.输入6   任意位置加元素   *******************" << endl;
	cout << "\t\t\t****************    8.输入7   删除最后元素     *******************" << endl;
	cout << "\t\t\t****************    8.输入8   删除前面元素     *******************" << endl;
	cout << "\t\t\t****************    8.输入9   删除任意元素     *******************" << endl;
	cout << "\t\t\t******************************************************************" << endl;
}

可以在控制台输入相关的数字进行相关的操作

顺序表的初始化

void SeqListInit(SL*ps)//初始化
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
	cout << "初始化完成" << endl;
}

顺序表初始化，首先使顺序表的指针置为空，先让顺序表的长度和容量都先置为空

添加元素

void SeqListPush(SL*ps, SLDataType n)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;
		SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//SLDataType类型（强制类型转换）的有newcapacity大小的空间
		if (tmp == NULL)
		{
			cout << "分配失败" << endl;
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	int k = 0;
	cout << "请进行赋值" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> k;
		ps->a[i] = k;
		ps->size++;
	}
	cout << "赋值完成" << endl;
}

此时先进行判断，如果没有空间或者空间不足，就要把把一个新的容量赋值为原来容量的二倍，如果是0就赋值为100 。relloc是扩容函数，是在ps->a后面扩容一个SLDataType类型（强制类型转换）的有newcapacity大小的空间，申请成功的话，就让指针a的地址存放新的地址tmp,此时新的地址tmp里面有扩容后的空间，再让capacity为新的容量，让ps的第一个位置放传进来函数的x，最后再让它的大小++。

陈列元素

void SepListdisplay(SL*ps)//陈列
{
	cout << "下面是您赋值的元素" << endl;
	for (int i = 0; i < ps->size; i++)
	{
		cout << ps->a[i] << " ";
	}
	cout << endl;
}

陈列元素这块很简单，直接可以通过它的下标找到它所代表的值，跟数组一样

往最后加元素

void SeqListPushBack(SL*ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;
		SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//如果分配失败
		{
			cout << "分配失败" << endl;
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->size] = x;
	ps->size++;//再让它的大小++
	cout << "添加完成" << endl;
}

此时还是要先进行判断顺序表的空间够不够，要是空间不够的话，再运用realloc函数进行重新分配空间，再直接让最后一个位置里面放上传过来的元素就可以了。

往前面加元素

void SeqListPushFront(SL*ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;
		SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			cout << "分配失败" << endl;
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->size++;
	int i = 0;
	int j = ps->size;
	for (i = j; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	cout << "添加完成" << endl;
}

往前面加元素的话，首先还是需要进行判断空间够不够，要是不够还是要运用realloc函数重新分配空间，此时要是想要在最前面添加元素的话，就需要先让它的大小++，再让从下标为0的第一个元素开始，把每一个元素都往后移动一个位置。移动完成之后，再让新的元素加入的顺序表的表头就可以了。

任意位置加元素

void SeqListPushMid(SL*ps, SLDataType x,SLDataType z)
{
	ps->size++;
	int i = 0;
	int j = ps->size - 1;
	for (i=j; i >= x; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[x] = z;
	cout << "添加完成" << endl;
}

要是想在任意位置加元素的话，我们首先应该知道我们需要进行加元素的下标，以及我们需要添加的元素，此时刚好我们的函数里面已经接收到了这两个元素，此时我们就从这个下标开始，让下标对应的元素以及下标之后的元素都往后加一个位置，此时就可以为新的元素腾出一个位置，等全部移动完成后，我们就可以把元素加进来就可以了。

删除最后元素

void SeqListPopBack(SL*ps)//删除最后一个元素
{
	if (ps->size > 0)
	{
		ps->size--;
	}
	cout << "删除完毕" << endl;
}

这一块是最简单的了，直接让顺序表的大小--就可以了。

删除前面元素

void SeqListPopFront(SL*ps)//删除第一个元素
{
	int i = 0;
	int j = ps->size;
	for (i = 1; i < j ; i++)
	{
		ps->a[i-1] = ps->a[i];
	}
	ps->size--;
	cout << "删除完毕" << endl;
}

我们这里可以直接让从下标为1以及后面的元素的位置往前面加一个位置，把第一个元素覆盖住就可以了。

删除任意元素

void SeqListPopMid(SL*ps, SLDataType x)//删除中间某一元素
{
	int i = 0, j = 0;
	for (i = x; i < ps->size ; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
	cout << "删除完毕" << endl;
}

这里的话我们已经知道我们需要删除元素的下标了，于是我们就可以从这个下标开始不包括这个下标对应的元素，把它们的位置往前推一个，把该元素覆盖住就可以了，最后再让大小减一。

整体代码(fun.h部分)

#pragma once
#define N 10000
typedef int SLDataType;
typedef struct
{
	SLDataType *a;
	int size;
	int capacity;
}SL;
//接口函数
void menu();//菜单
void SeqListInit(SL*ps);//初始化
void SeqListPushBack(SL*ps, SLDataType x);//往后加元素
void SeqListPush(SL*ps, SLDataType n);//在顺序表中添加元素
void SeqListPopBack(SL*ps);//删除最后一个元素
void SeqListPushFront(SL*ps, SLDataType x);//往前面加元素
void SeqListPopFront(SL*ps);//删除第一个元素
void SepListdisplay(SL*ps);//陈列
void SeqListPushMid(SL*ps, SLDataType x,SLDataType z);//往中间加元素
void SeqListPopMid(SL*ps,SLDataType x);//删除中间某一个元素

整体代码(fun.cpp部分)

#include<iostream>//顺序表的实现
#include<stdlib.h>
#include"fun.h"
using namespace std;
void menu()
{
	cout << "\t\t\t******************************************************************" << endl;
	cout << "\t\t\t****************   注意！每次都要先进行初始化  *******************" << endl;
	cout << "\t\t\t****************    1.输入-1  退出程序         *******************" << endl;
	cout << "\t\t\t****************    2.输入1   初始化           *******************" << endl;
	cout << "\t\t\t****************    3.输入2   添加元素         *******************" << endl;
	cout << "\t\t\t****************    4.输入3   陈列元素         *******************" << endl;
	cout << "\t\t\t****************    5.输入4   往最后加元素     *******************" << endl;
	cout << "\t\t\t****************    6.输入5   往前面加元素     *******************" << endl;
	cout << "\t\t\t****************    7.输入6   任意位置加元素   *******************" << endl;
	cout << "\t\t\t****************    8.输入7   删除最后元素     *******************" << endl;
	cout << "\t\t\t****************    8.输入8   删除前面元素     *******************" << endl;
	cout << "\t\t\t****************    8.输入9   删除任意元素     *******************" << endl;
	cout << "\t\t\t******************************************************************" << endl;
}
void SeqListInit(SL*ps)//初始化
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
	cout << "初始化完成" << endl;
}
void SeqListPush(SL*ps, SLDataType n)//在顺序表中加元素
{
	if (ps->size == ps->capacity)//如果没有空间或者空间不足
	{
		int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;//把一个新的容量赋值为原来容量的二倍，如果是0就赋值为100
		SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//relloc是扩容函数，是在ps->a后面扩容一个
		//SLDataType类型（强制类型转换）的有newcapacity大小的空间
		if (tmp == NULL)//如果分配失败
		{
			cout << "分配失败" << endl;
			exit(-1);
		}
		ps->a = tmp;//申请成功的话，就让指针a的地址存放新的地址tmp,此时新的地址tmp里面有扩容后的空间
		ps->capacity = newcapacity;//再让capacity为新的容量
	}
	int k = 0;
	cout << "请进行赋值" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> k;
		ps->a[i] = k;
		ps->size++;
	}
	cout << "赋值完成" << endl;
}
void SeqListPushBack(SL*ps, SLDataType x)//往后加元素,或者也可以叫做为顺序表赋值
{
	if (ps->size == ps->capacity)//如果没有空间或者空间不足
	{
		int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;//把一个新的容量赋值为原来容量的二倍，如果是0就赋值为100
		SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));//relloc是扩容函数，是在ps->a后面扩容一个
		//SLDataType类型（强制类型转换）的有newcapacity大小的空间
		if (tmp == NULL)//如果分配失败
		{
			cout << "分配失败" << endl;
			exit(-1);
		}
		ps->a = tmp;//申请成功的话，就让指针a的地址存放新的地址tmp,此时新的地址tmp里面有扩容后的空间
		ps->capacity = newcapacity;//再让capacity为新的容量
	}
	ps->a[ps->size] = x;//让ps的第一个位置放传进来函数的x
	ps->size++;//再让它的大小++
	cout << "添加完成" << endl;
}
void SeqListPopBack(SL*ps)//删除最后一个元素
{
	if (ps->size > 0)
	{
		ps->size--;
	}
	cout << "删除完毕" << endl;
}
void SeqListPushFront(SL*ps, SLDataType x)//往前面加元素
{
	//进来先判断一下里面的空间满没有
	if (ps->size == ps->capacity)//如果没有空间或者空间不足
	{
		int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;//把一个新的容量赋值为原来容量的二倍，如果是0就赋值为100
		SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//relloc是扩容函数，是在ps->a后面扩容一个
		//SLDataType类型的有newcapacity大小的空间
		if (tmp == NULL)//如果分配失败
		{
			cout << "分配失败" << endl;
			exit(-1);
		}
		ps->a = tmp;//申请成功的话，就让指针a的地址存放新的地址tmp,此时新的地址tmp里面有扩容后的空间
		ps->capacity = newcapacity;//再让capacity为新的容量
	}
	ps->size++;
	int i = 0;
	int j = ps->size;
	for (i = j; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	cout << "添加完成" << endl;
}
void SeqListPopFront(SL*ps)//删除第一个元素
{
	int i = 0;
	int j = ps->size;
	for (i = 1; i < j ; i++)
	{
		ps->a[i-1] = ps->a[i];
	}
	ps->size--;
	cout << "删除完毕" << endl;
}
void SepListdisplay(SL*ps)//陈列
{
	cout << "下面是您赋值的元素" << endl;
	for (int i = 0; i < ps->size; i++)
	{
		cout << ps->a[i] << " ";
	}
	cout << endl;
}
void SeqListPushMid(SL*ps, SLDataType x,SLDataType z)//往中间加元素
{
	ps->size++;
	int i = 0;
	int j = ps->size - 1;
	for (i=j; i >= x; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[x] = z;
	cout << "添加完成" << endl;
}
void SeqListPopMid(SL*ps, SLDataType x)//删除中间某一元素
{
	int i = 0, j = 0;
	for (i = x; i < ps->size ; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
	cout << "删除完毕" << endl;
}

整体代码(主函数部分)

#include<iostream>//顺序表的实现
#include<stdlib.h>
#include"fun.h"
using namespace std;
int main()
{
	SL ps;
	int n = 0, m = 0;
	int x = 0;
	menu();
	while (cin >> x)
	{
		if (x < 0)
		{
			break;
		}
		switch (x)
		{
		case 1:
			SeqListInit(&ps);
			break;
		case 2:
			cout << "请输入您要添加几个元素" << endl;
			cin >> n;
			SeqListPush(&ps, n);
			break;
		case 3:
			SepListdisplay(&ps);
			break;
		case 4:
			cout << "请输入您要在最后添加什么元素" << endl;
			cin >> n;
			SeqListPushBack(&ps, n);
			break;
		case 5:
			cout << "请输入您要在最前面添加什么元素" << endl;
			cin >> n;
			SeqListPushFront(&ps, n);
			break;
		case 6:
			cout << "请输入您要添加位置的下标以及添加的元素" << endl;
			cin >> n >> m;
			SeqListPushMid(&ps, 1, 6);
			break;
		case 7:
			SeqListPopBack(&ps);
			break;
		case 8:
			SeqListPopFront(&ps);
			break;
		case 9:
			cout << "请输入您要进行删除元素的下标" << endl;
			cin >> n;
			SeqListPopMid(&ps, n);
		default:
			cout << "您的输入有误，请重新输入" << endl;
		}
	}
	return 0;
}