数据结构与算法—顺序表

03-03 9632阅读 0评论

目录

一、线性表

二、顺序表概念

 三、实现顺序表

1、声明结构体

2、初始化

3、打印数据 

4、销毁 

5、尾插&头插

尾插

判断是否扩容 

 头插

6、尾删&头删

尾删

头删

7、 指定位置插入元素

8、 删除指定位置元素

9、 查找指定元素位置

10、修改指定位置元素

完整版附上：

Seqlist.h

Seqlist.c

 text.c

一、线性表

  • 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
  • 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
  • 线性表在物理上存储时，通常以数组和链式结构的形式存储。 数据结构与算法—顺序表 第1张

    二、顺序表概念

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为： 1. 静态顺序表：使用定长数组存储元素。数据结构与算法—顺序表 第2张

    2. 动态顺序表：使用动态开辟的数组存储。  

    数据结构与算法—顺序表 第3张

     三、实现顺序表

    静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用 动态顺序表 ，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

     我们创建三个文件：

    1. Seqlist.h用于存放头文件、结构体和函数的声明
    2. text.c作为主程序进行运行和测试
    3. Seqlist.c存放函数主体

    1、声明结构体

    #include 
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SL;
    • 在头文件中声明结构体struct SeqList，由于名字太长，我们用typedef自定义结构体名称的别名为SL。
    • 将顺序表的数据类型用SLDatatype这个别名代替int，以后程序中使用到元素数据类型时都替换成SLDatatype，方便日后修改顺序表数据类型。
    • 定义size存储当前元素个数，capacity存储顺序表容量。

      2、初始化

      void SLInit(SL* psl)
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL) {
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;
}
      • 需要改变结构体变量，则将其地址传入函数。
      • assert检测传参顺序表指针是否合法，如果传入参数为空则报错（具体哪行出错）。
      • 然后为结构体成员a分配4个成员类型空间，顺便检查是否分配成功。
      • 对成员size和capacity分别复制为0（当前元素个数）和4（顺序表容量）。

        3、打印数据 

        void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i size; i++) {
		printf("%d ", psl->a[i]);
	}
}

        • assert检测传参顺序表指针是否合法，然后循环遍历输出。

          4、销毁 

          void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

          • assert检测传参顺序表指针是否合法。

          • 释放动态开辟a的空间，同时赋值为空，不置空可能会造成野指针的访问。

          • size和capacity分别赋值为0。

            5、尾插&头插

            尾插

            void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);
    SLCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

            • assert检测传参顺序表指针是否合法。

            • 判断数组是否已经装满，如果装满则进行扩容，这些操作我们在函数SLCheckCapacity内进行。

            • 将 x 赋值给 psl->a 数组中下一个可用的位置，即 psl->size 索引处。

            • 递增 psl->size，以便记录新元素的加入。

               接下来我们来讲解函数SLCheckCapacity：

              判断是否扩容 

              void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity) {
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}

              •  判断当前元素个数size与顺序表容量capacity是否相等，相等则对结构体成员指针a进行扩容。

              • 通过realloc函数对a的内存进行扩容，每次增加一倍容量，并将reallocd的返回值新空间的起始地址赋值给SLDatatype类型指针 tmp，这样避免直接对a开辟空间时发生错误丢失数据。

              • 检测是否成功扩容。

              • 最后将存放新空间地址的tmp赋值给a。

              • 顺序表的容量也随之扩大为原来的两倍。

                我们还可以优化一下尾插函数，具体如下： 

                void SLPushBack(SL* psl, SLDatatype x)//尾插
{
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;
}

                 头插

                void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

                • assert检测传参顺序表指针是否合法。

                • 判断数组是否已经装满，如果装满则进行扩容，这些操作在函数SLCheckCapacity内进行。

                • 定义end表示当前顺序表中最后一个元素的下标。

                • while循环用于从后向前将顺序表中的元素依次向后移动一个位置，为新元素 x 腾出空间

                • 将新元素 x 插入到顺序表的开头

                • 顺序表元素个数 size 增加1

                  6、尾删&头删

                  尾删

                  void SLPopBack(SL* psl)
{
	assert(psl);
	//暴力判断
	assert(psl->size == 0);
	//常规判断
	//if (psl->size == 0)
	//	return;
	psl->a[psl->size - 1] = 0;
	psl->size--;
}

                  • 第一个assert检测传参顺序表指针是否合法。

                  • 第二个assert检测顺序表是否为空，为空没有元素则不需要删除，程序报错。

                  • 我们还可以通过顺序表元素个数判断，if语句判断size为0时，函数停止运行。

                  • 顺序表大小不为空，则对最后一个元素进行删除，赋值为0。

                  • 顺序表大小size减1.

                    头删

                    void SLPopFront(SL* psl)
{
	assert(psl);
	assert(psl->size > 0);
	int start = 0;
	while (start size) {
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	psl->size--;
}

                    • 第一个assert检测传参顺序表指针是否合法。

                    • 第二个assert检测顺序表是否为空，为空没有元素则不需要删除，程序报错。

                    • 定义变量start为首元素下标.

                    • 头删不用赋值为0，直接从第一个元素开始后项赋值给前项。

                      7、指定位置插入元素

                      void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(0 size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->size++;
	psl->a[pos] = x;
}

                      • 参数pos为要在第几个元素后插入。

                      • 第一个assert检测传参顺序表指针是否合法。

                      • 第二个assert检测传参pos的位置是否合法。

                      • 判断数组是否已经装满，如果装满则进行扩容，这些操作在函数SLCheckCapacity内进行。

                      • 定义end表示当前顺序表中最后一个元素的下标。

                      • while循环用于从后向前将顺序表中的元素依次向后移动一个位置，为新元素 x 腾出空间

                      • 顺序表元素个数 size 增加1。

                      • 将新元素 x 插入到顺序表指定元素位置之后。

                         SLInsert这个函数可以代替头插尾插函数进行顺序表元素的增加。

                        8、删除指定位置元素

                        void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(0 size) {
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}

                        • 第一个assert检测传参顺序表指针是否合法。

                        • 第二个assert检测传参pos的位置是否合法。

                        • 定义变量start存储pos位置后一项的下标。

                        • 将删除元素后一项位置的值开始从pos+1向后依次前移一位，顶替pos位置。

                        • 顺序表元素个数减一。

                          这个函数就可以完全代替头删尾删了。

                          9、查找指定元素位置

                          int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i size; i++) {
		if (psl->a[i] == x)
			return i+1;
	}
	return -1;
}

                          •  assert检测传参顺序表指针是否合法。

                          • 循环遍历顺序表找出于x相等的元素，返回其下标。

                          • 找不到返回-1。

                            10、修改指定位置元素

                            void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(0 a[pos] = x;
}

                            • 第一个assert检测传参顺序表指针是否合法。

                            • 第二个assert检测传参pos的位置是否合法。

                            • 将pos位置的值修改为x。

                              完整版附上：

                              Seqlist.h

                              #include 
#include 
#include 
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SL;
void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int pos);
int SLFind(SL* psl, SLDatatype x);
void SLModify(SL* psl, int pos, SLDatatype x);

                              Seqlist.c

                              #define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"
void SLInit(SL* psl)//初始化
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL) {
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;//每次开辟的容量为四个
}
void SLPrint(SL* psl)//打印数据
{
	assert(psl);
	for (int i = 0; i size; i++) {
		printf("%d ", psl->a[i]);
	}
}
void SLDestroy(SL* psl)//结束使用需要销毁
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity) {
		//增加一倍容量
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
	
}
void SLPushBack(SL* psl, SLDatatype x)//尾插
{
	assert(psl);
	//psl->a[psl->size] = x;
	//psl->size++;
	//插入需要判断a是否已满，已满需要扩容
	SLCheckCapacity(psl);
	//或者写成一句
	psl->a[psl->size++] = x;//后置自增
}
void SLPushFront(SL* psl, SLDatatype x)//头插
{
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}
void SLPopBack(SL* psl)
{
	assert(psl);//尾删
	//暴力判断
	//assert(psl->size == 0);
	//常规判断
	if (psl->size == 0)
		return;
	psl->a[psl->size - 1] = 0;
	psl->size--;
}
void SLPopFront(SL* psl)//头删
{
	assert(psl);
	assert(psl->size > 0);
	int start = 0;
	while (start size) {
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	psl->size--;
}
void SLInsert(SL* psl, int pos, SLDatatype x)//指定位置插入元素,可代替头插尾插
{
	assert(psl);
	assert(0 size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->size++;
	psl->a[pos] = x;
}
void SLErase(SL* psl, int pos)//删除指定位置元素，代替头删尾删
{
	assert(psl);
	assert(0 size) {
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}
int SLFind(SL* psl, SLDatatype x)//查找指定元素位置
{
	assert(psl);
	for (int i = 0; i size; i++) {
		if (psl->a[i] == x)
			return i+1;
	}
	return -1;//找不到返回-1
}
void SLModify(SL* psl, int pos, SLDatatype x)//修改指定位置元素
{
	assert(psl);
	assert(0 a[pos] = x;
}

                               text.c

                              这里大家可以自行发挥！

                              #define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"
void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 5);
	SLPushBack(&s, 9);
	SLPushBack(&s, 50);
	SLPushFront(&s, 1);
	SLPushFront(&s, 15);
	SLPushFront(&s, 0);
	SLPopBack(&s, 50);
	SLPopFront(&s, 0);
	SLInsert(&s, 2, 555);
	SLErase(&s, 4);
	SLPrint(&s);
	int a=SLFind(&s, 15);
	printf("\n%d\n", a);
	if (a != -1)
		SLErase(&s, a);
	SLPrint(&s);
	SLDestroy(&s);
}
int main()
{
	test1();
	return 0;
}

相关阅读：

1、Axios使用

2、【NodeMcu-ESP8266】引脚使用参考指南——推荐收藏

3、【JavaEE多线程】Java 文件操作

4、【数据结构】图论（图的储存方式，图的遍历算法DFS和BFS、图的遍历算法的应用、图的连通性问题）

5、使用FastDDS编译IDL文件

免责声明
1、本网站属于个人的非赢利性网站，转载的文章遵循原作者的版权声明。
2、本网站转载文章仅为传播更多信息之目的，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所
提供信息的准确性及可靠性，但不保证信息的正确性和完整性，且不对因信息的不正确或遗漏导致的任何
损失或损害承担责任。
3、任何透过本网站网页而链接及得到的资讯、产品及服务，本网站概不负责，亦不负任何法律责任。
4、本网站所刊发、转载的文章，其版权均归原作者所有，如其他媒体、网站或个人从本网下载使用，请在
转载有关文章时务必尊重该文章的著作权，保留本网注明的“稿件来源”，并白负版权等法律责任。

手机扫描二维码访问

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

发表评论

快捷回复： 表情：
评论列表 （暂无评论，9632人围观）

还没有评论，来说两句吧...

目录[+]