站点图标 AI技术聚合

数据结构：顺序表

乘风

目录

一.顺序表

1.1概念以及结构

顺序表（一般是用数组存储）是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。

顺序表一般可以分为：

  • 静态顺序表：使用定长数组存储元素
  • 动态顺序表：使用动态开辟（malloc）的数组存储。

静态顺序表：

#include<stdio.h>
#include<stdlib.h>

#define number 7
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[number];//定长数组
    size_t size;//有效数据个数
}SL;

动态顺序表：

#include<stdio.h>
#include<stdlib.h>

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据个数
	int capacity;//容量空间大小
}SL;

1.2动态顺序表实现

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

1.2.1文件创建：

  • 在seq.h文件中对顺序表结构和接口（增删查改等）函数进行声明
  • 在seq.c文件中对顺序表接口函数进行实现
  • 在test.c文件中一步步对顺序表及其接口进行测试

1.2.2接口实现

对于顺序表我们要实现以下几个功能：

  1. 顺序表打印（可视化每一步的成果）
  2. 顺序表初始化
  3. 顺序表尾插
  4. 顺序表头插
  5. 顺序表尾删
  6. 顺序表头删
  7. 顺序表在pos位置插入x
  8. 顺序表删除pos位置的值
  9. 顺序表销毁
1.顺序表打印
//存储整数的顺序表打印
void SLPrint(SL* psl)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
2.顺序表初始化
//顺序表初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;

}
3.顺序表尾插
// 顺序表尾插
void SLPushBack(SL* psl, SLDataType x)
{
	assert(psl);
	//尾插时 检查顺序表容量大小
	if (psl->size == psl->capacity)
	{
		//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//realloc开辟空间和扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fali:");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;

	}
	//尾插元素
	psl->a[psl->size] = x;
	psl->size++;
}

 写出函数后进行一次测试：

//顺序表尾插测试
void test1()
{

	//定义一个顺序表变量
	SL sl1;
	//初始化这个顺序表变量
	SLInit(&sl1);
	SLPushBack(&sl1, 1);
	SLPushBack(&sl1, 2);
	SLPushBack(&sl1, 3);
	SLPushBack(&sl1, 4);
	SLPushBack(&sl1, 5);

	SLPrint(&sl1);

}
int main()
{
	test1();

	return 0;
}

 

4.顺序表头插
// 顺序表头插
void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	//头插时 检查顺序表容量大小
	if (psl->size == psl->capacity)
	{
		//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//realloc开辟空间和扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fali:");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;

	}
	//与尾插不同的是在进行头插之前我们需要将所有元素先向后移动一位
	int odd_size_to_move = psl->size;
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		psl->a[odd_size_to_move] = psl->a[odd_size_to_move - 1];
		odd_size_to_move--;
	}

	//头插元素
	psl->a[0] = x;
	psl->size++;
}

  写出函数后进行一次测试：

//顺序表头插测试
void test2()
{
	//	定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//	先尾插
	SLPushBack(&sl2, 0);
	SLPushBack(&sl2, 0);
	SLPushBack(&sl2, 0);
	SLPushBack(&sl2, 0);
	//	再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);


	SLPrint(&sl2);
	SLDestory(&sl2);

}
int main()
{
	test2();
	return 0;
}

 

 5.顺序表尾删
// 顺序表尾删
void SLPopBack(SL* psl)
{
	//温柔检查
	//要保证顺序表空了就不再删除了，根除错误源头
	if (psl->size == 0)
	{
		return;
	}

	//暴力检查
	//assert(psl->size > 0);

	psl->size--;

}

 写出函数后进行一次测试：

//顺序表尾删测试
void test3()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	SLPrint(&sl2);

	//尾删
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	//上面只有九个元素，当我们再调用删除的时候将会报错或者直接退出该函数调用。
	SLPopBack(&sl2);
	//头插                       
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main()
{
	test3();
	return 0;
}

 

6.顺序表头删
// 顺序表头删
void SLPopFront(SL* psl)
{
	assert(psl);

	//挪动覆盖
	int i = (psl->size) - 1;
	int j = 0;
	while (i)
	{
		psl->a[j] = psl->a[j + 1];
		j++;
		i--;
	}
	psl->size--;
}

  写出函数后进行一次测试：

//顺序表头删测试
void test4()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	SLPrint(&sl2);

	//头删
	SLPopFront(&sl2);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main()
{
	test4();
	return 0;
}

 

 7.顺序表在pos位置插入x
// 顺序表在pos位置插入x
void SLInsert(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	//插入元素前先检查顺序表容量大小是否足够
	if (psl->size == psl->capacity)
	{
		//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//realloc开辟空间和扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fali:");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}

	int n = psl->size;
	while (n > pos)
	{
		psl->a[n] = psl->a[n - 1];
		n--;
	}

	psl->a[pos] = x;
	(psl->size)++;


}

   写出函数后进行一次测试：


//顺序表pos位置插入测试
void test5()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	//pos位置插入x
	SLInsert(&sl2, 3, 5000);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main
{
    test5();
    return 0;
}

 8.顺序表删除pos位置的值
// 顺序表删除pos位置的值
void SLErase(SL* psl, size_t pos)
{
	assert(psl);
	while (pos < ((psl->size) - 1))
	{
		psl->a[pos] = psl->a[pos + 1];
		pos++;
	}
	(psl->size)--;
}

   写出函数后进行一次测试：

//顺序表pos位置删除测试
void test6()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	//pos位置删除
	SLErase(&sl2, 3);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main()
{

	test6();
	return 0;
}

 9.顺序表销毁
//顺序表销毁
void SLDestory(SL* psl)
{
	assert(psl);
	//检查动态开辟的顺序表内存最后是否被释放，没有释放则释放psl->a并且将顺序表全部初始化为最初的形态
	if (psl->a != NULL)
	{
		free(psl->a);
		psl->a = NULL;
		psl->size = 0;
		psl->capacity = 0;
	}
}

二.顺序表问题

我们已经实现了顺序表，那我们能发现顺序表这种数据结构有什么优劣势么？

顺序表缺点：

  1. 头部或者中间插入删除效率低，要挪动数据，O(N)
  2. 空间不够需要扩容，扩容有一定消耗，且可能存在一定的空间消耗
  3. 只适合尾插尾删

顺序表优点：

        支持下标随机访问 O(1)

顺序表无法简要完成的事情我们可以通过学习下一个数据结构链表来完成，咱们下次再见

感谢您的支持！

文章出处登录后可见！

已经登录？立即刷新
退出移动版