数据结构初级——顺序表_请给出顺序表的存储结构的定义

今天我们就是进入数据结构初阶的学习。我们采用C语言实现数据结构，以多文件形式写代码

目录

<一>顺序表的定义

<二>顺序表的结构体定义

<三>顺序表创建

<四>给顺序表尾插一个数据

<五>顺序表头部删除

<六>顺序表的尾部删除

<七>顺序表的头部删除

<八>顺序表的指定位置插入

<九>指定位置删除

---

<一>顺序表的定义

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

<二>顺序表的结构体定义

顺序表是一段连续的空间也就是我们常说的数组，而在c语言中数组的长度是不可以改变的，所以这里我们采用可变长的数组来实现顺序表 .

typedef int seldata;//为了使顺序表可以存储任何类型的数据，在这里使用给类型起别名的方式来方便数据类型的改变
typedef struct seqlit
{
	seldata* pldata;
	int cursize;
	int maxsize;
}Sel,*PLsel;

<三>顺序表创建

用动态内存申请给顺序表初始化

PLsel creatseqlist(int maxsize)
{
	PLsel seqlist = (PLsel)malloc(sizeof(Sel));
	assert(seqlist);
	seqlist->pldata = (seldata*)malloc(sizeof(seldata)*maxsize);
	assert(seqlist->pldata);
	seqlist->cursize = 0;
	seqlist->maxsize = maxsize;
	return seqlist;
}

<四>给顺序表尾插一个数据

顺序表实际和数组是一样的，要给顺序表尾部插入一个数据，其实就是给顺序表中的当前元素个数的下标存入一个新的数据。那么首先，就先来创建一个顺序表，

#include"seqlist.h"//采用多文件的形式进行书写代码，函数的声明在这个文件中，定义就在对应的.c文件中
int main()
{
	PLsel seqlist = creatseqlist(7);
	return 0;
}

此时，我们的顺序表中已经有储存7个数据的空间了，接下来就来插入数据

void PushByBack(PLsel seqlist, seldata data)
{
		seqlist->pldata[seqlist->cursize] = data;
		seqlist->cursize++;	
}

这样数据插入在了我们准备好的顺序表中。当然为了能方便观展数据，我们需要来实现一个接口把顺序表中的元素打印出来。

打印顺序表是非常简单的，和打印数组中的元素是一样的。这里直接上代码。

void printsql(PLsel seqlist)
{
	for (int i = 0; i < seqlist->cursize; i++)
	{
		printf("%d ", seqlist->pldata[i]);
       
	}
}

程序运行效果图

 顺序表逻辑图如图：

此时顺序表中已经有数据了。但是，此时的顺序表中只能存储7个数据，那么我们的，但我们在存入数据时就会导致程序崩掉。

例如：

#include"seqlist.h"
int main()
{
	PLsel seqlist = creatseqlist(7);
	for (int i = 0; i < 7; i++)
	{
		PushByBack(seqlist, i);
	}
	PushByBack(seqlist, 100);//顺序表满了，再插入
	printsql(seqlist);
	return 0;
}

 

就会导致程序崩掉。

所以，就要对插入函数进行优化。当顺序表中的元素个数等于或者大于顺序表中的最大储存数量的时候就给数组扩容。优化后插入函数如下：

void PushByBack(PLsel seqlist, seldata data)
{
	if (seqlist->cursize >= seqlist->maxsize)
	{
		seqlist->pldata = (seldata*)realloc(seqlist->pldata, sizeof(seldata) * ((seqlist->maxsize) * 2));//通过realloc函数给数组的容量扩充为原来的两倍
		assert(seqlist->pldata);
		seqlist->pldata[seqlist->cursize++] = data;
		seqlist->maxsize *= 2;
	}
 
	else
	{
		seqlist->pldata[seqlist->cursize] = data;
		seqlist->cursize++;
 
	}
}

此时再进行插入，就可以看到代码可以正常的运行起来

#include"seqlist.h"
int main()
{
	PLsel seqlist = creatseqlist(7);
	for (int i = 0; i < 7; i++)
	{
		PushByBack(seqlist, i);
    }
	printsql(seqlist);
    printf("\n");
	PushByBack(seqlist, 100);
	printsql(seqlist);
	return 0;
}

<五>顺序表头部删除

头部的删除要比较麻烦一些，因为顺序表的数据储存的物理地址是连续的。这样我们就需要将顺序表中的数据以此向后移动，然后将数据插入到顺序表的开头。

 就这样一直移动最后头部位置为空，将新的数据插入.

当然，同上面的尾部插入一样，为了可以更多的存储数据，当顺序表的容量不够时，进行扩容。

代码如下：

void PushByHead(PLsel seqlist, seldata data)
{
	if (seqlist->cursize >= seqlist->maxsize)
	{
		seqlist->pldata = (seldata*)realloc(seqlist->pldata, sizeof(seldata) * ((seqlist->maxsize) * 2));
		assert(seqlist->pldata);
		for (int i = seqlist->cursize; i >0; i--)
		{
			seqlist->pldata[i - 1] = seqlist->pldata[i];
		}
		seqlist->pldata[0] = data;
		seqlist->cursize++;
		seqlist->maxsize *= 2;
	}
	else
	{
		for (int i = seqlist->cursize; i > 0; i--)
		{
			seqlist->pldata[i] = seqlist->pldata[i-1];
		}
		seqlist->pldata[0] = data;
		seqlist->cursize++;
	}
}

 执行代码：

#include"seqlist.h"
int main()
{
	PLsel seqlist = creatseqlist(7);
	for (int i = 0; i < 7; i++)
	{
		PushByBack(seqlist, i);
	}
	printsql(seqlist);
	printf("\n");
	PushByBack(seqlist, 100);
	printsql(seqlist);
	printf("\n");
	PushByHead(seqlist, 99);
	printsql(seqlist);
	return 0;
}

效果如下:

 

<六>顺序表的尾部删除

这个就非常的简单了，只要让我们的cursize--就可以了。

代码如下：

void PopByBack(PLsel seqlist)
{
	if (seqlist->cursize == 0)
	{
		printf("顺序表为空无法删除\n");
		return;
	}
	else
	{
		seqlist->cursize--;
	}
}

执行代码：

#include"seqlist.h"
int main()
{
	PLsel seqlist = creatseqlist(10);
	for (int i = 0; i < 10; i++)
	{
		PushByBack(seqlist, i);
	}
	
 
	printsql(seqlist);
	printf("\n");
	PushByBack(seqlist, 100);
	printsql(seqlist);
	printf("\n");
	PushByHead(seqlist, 99);
	printsql(seqlist);
	printf("\n");
	PopByBack(seqlist);
	printsql(seqlist);
	return 0;
}

 

 

<七>顺序表的头部删除

顺序表的头部删除同样有一定的麻烦，和头部插入一样，我们要将后面的元素移动，覆盖头部元素

代码如下：

void PopByHead(PLsel seqlist)
{
	if (seqlist->cursize == 0)
	{
		printf("顺序表为空无法删除\n");
		return;
	}
	for (int i = 0; i +1< seqlist->cursize; i++)
	{
		seqlist->pldata[i] = seqlist->pldata[i + 1];
	}
	seqlist->cursize--;
}

 执行代码：

 

<八>顺序表的指定位置插入

指定位置的插入，首先需要找到指定的位置，然后将指定位置及之后的数据以此先后移动，然后将新的数据插在指定位置。当然，我们同样考虑数组扩容问题

 代码如下：

void PushByPos(PLsel seqlist, int pos, seldata data)
{
	if (pos < 0)//当pos小于0时候，就无法进行插入
	{
		return;
	}
	if (seqlist->cursize >= seqlist->maxsize)
	{
		seqlist->pldata = (seldata*)realloc(seqlist->pldata, sizeof(seldata) * ((seqlist->maxsize) * 2));
		assert(seqlist->pldata);
		seqlist->maxsize *= 2;
		
		for (int i = seqlist->cursize; i >pos ; i--)
		{
			seqlist->pldata[i] = seqlist->pldata[i - 1];
		}
		seqlist->pldata[pos] = data;
		seqlist->cursize++;
	}
	else
	{
		for (int i = seqlist->cursize; i > pos; i--)
		{
			seqlist->pldata[i] = seqlist->pldata[i - 1];
		}
		seqlist->pldata[pos] = data;
		seqlist->cursize++;
	}
}

执行代码：

#include"seqlist.h"
int main()
{
	PLsel seqlist = creatseqlist(10);
	for (int i = 0; i < 10; i++)
	{
		PushByBack(seqlist, i);
    }
	printsql(seqlist);
	printf("\n");
	PushByBack(seqlist, 100);
	printsql(seqlist);
	printf("\n");
	PushByHead(seqlist, 99);
	printsql(seqlist);
	printf("\n");
	PopByBack(seqlist);
	printsql(seqlist);
	printf("\n");
	PopByHead(seqlist);
	printsql(seqlist);
	PushByPos(seqlist, 3, 300);
	printf("\n");
	printsql(seqlist);
	return 0;
}

<九>指定位置删除

指定位置的删除就是，找到指定位置，然后把指定位置后的元素向前移动。

 代码如下：

void PopByPos(PLsel seqlist, int pos)
{
	if (pos < 0||seqlist->cursize==0)
	{
		return;
	}
	else
	{
		for (int i = pos; i-+1 < seqlist->cursize; i++)
		{
			seqlist->pldata[i] = seqlist->pldata[i + 1];
		}
		seqlist->cursize--;
	}
}

执行代码：

#include"seqlist.h"
int main()
{
	PLsel seqlist = creatseqlist(10);
	for (int i = 0; i < 10; i++)
	{
		PushByBack(seqlist, i);
	}
	
 
	printsql(seqlist);
	printf("\n");
	PushByBack(seqlist, 100);
	printsql(seqlist);
	printf("\n");
	PushByHead(seqlist, 99);
	printsql(seqlist);
	printf("\n");
	PopByBack(seqlist);
	printsql(seqlist);
	printf("\n");
	PopByHead(seqlist);
	printsql(seqlist);
	PushByPos(seqlist, 3, 300);
	printf("\n");
	printsql(seqlist);
	PopByPos(seqlist,2);
	printf("\n");
	printsql(seqlist);
 
	return 0;
}