【数据结构】顺序表

YoungMLet

发布于 2024-03-01 10:25:22

870

发布于 2024-03-01 10:25:22

文章被收录于专栏：C++/Linux

顺序表和链表

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

下面我们实现动态顺序表：

1. 函数声明部分

下面是顺序表结构体的定义和一些增删查改函数的声明；

		#pragma once
		#include <stdio.h>
		#include <stdlib.h>
		#include <assert.h>
		
		//将顺序表中的指针类型起别名
		typedef int SLDataType;
		
		//创建一个结构体顺序表，存放顺序表的头指针，顺序表的长度，顺序表的容量
		typedef struct SeqList
		{
			SLDataType *a;
			int size;
			int capacity;
		}SL;
		
		//初始化
		void SLInit(SL* psl);
		
		//尾插和头插
		void SLPushBack(SL* psl, SLDataType x);
		void SLPushFront(SL* psl, SLDataType x);
		
		//尾删和头删
		void SLPopBack(SL* psl);
		void SLPopFront(SL* psl);
		
		//在pos位置插入x
		void SLInsert(SL* psl, size_t pos, SLDataType x);
		
		//删除pos位置的元素
		void SLErase(SL* psl, size_t pos);
		
		//修改数据
		void SLModify(SL* psl, size_t pos ,SLDataType x);
		
		//查找，找到返回下标，找不到返回-1
		int SLFind(SL* psl, SLDataType x);
		
		//打印
		void SLPrint(SL* psl);
		
		//归还空间
		void SLDestroy(SL* psl);

2. 函数的实现部分

由于一些头插，尾插等函数需要判断容量的大小，所以我们将检查容量的函数放到外面；若当前长度等于容量，即满了，用realloc开辟成原来两倍的空间；

		//检查容量是否已满
		void CheakCapacity(SL* psl)
		{
			assert(psl);
		
			if (psl->size == psl->capacity)
			{
				SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * psl->capacity * 2);
				assert(tmp);
		
				psl->a = tmp;
				psl->capacity *= 2;
			}
		}

（1）初始化

先为顺序表开辟4个大小的空间，当前容量为4，当前长度为0；

		void SLInit(SL* psl)
		{
			assert(psl);
		
			psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
			assert(psl->a);
		
			psl->capacity = 4;
			psl->size = 0;
		}

（2）尾插

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

（3）头插

		void SLPushFront(SL* psl, SLDataType x)
		{
			assert(psl);
		
			CheakCapacity(psl);
		
			int i = psl->size - 1;
			for (i = psl->size - 1; i >= 0; i--)
			{
				psl->a[i + 1] = psl->a[i];
			}
		
			psl->a[i+1] = x;
			psl->size++;
		}

（4）尾删

		void SLPopBack(SL* psl)
		{
			assert(psl);
		
			assert(psl->size > 0);
		
			psl->size--;
		}

（5）头删

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

（6）在pos位置插入x

		void SLInsert(SL* psl, size_t pos, SLDataType x)
		{
			assert(psl);
			assert(pos >= 0 && pos <= psl->size);
			CheakCapacity(psl);
		
			SLDataType right = psl->size - 1;
			SLDataType left = pos;
		
			while (left <= right)
			{
				psl->a[right + 1] = psl->a[right];
				right--;
			}
			psl->a[left] = x;
			psl->size++;
		}

（7）删除pos位置的元素

		void SLErase(SL* psl, size_t pos)
		{
			assert(psl);
			assert(pos >= 0 && pos < psl->size);
		
			while (pos < psl->size - 1)
			{
				psl->a[pos] = psl->a[pos + 1];
				pos++;
			}
			psl->size--;
		}

（8）修改数据

		void SLModify(SL* psl, size_t pos, SLDataType x)
		{
			assert(psl);
		
			psl->a[pos] = x;
		}

（9）查找

找到返回下标，找不到返回-1

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

（10）打印

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

（11）归还空间

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

3. 测试部分

		int main()
		{
			SL s;
			
			SLInit(&s);
		
			SLPushBack(&s, 1);
			SLPushBack(&s, 2);
			SLPushBack(&s, 3);
		
			SLPushFront(&s, 10);
		
			SLPopFront(&s);
		
			SLPopBack(&s);
		
		
			SLInsert(&s, 1, 10);
		
		
			SLErase(&s, 1);
		
			SLModify(&s, 1, 100);
		
			SLPrint(&s);
		
			printf("\n");
			int ret = SLFind(&s, 100);
			if (ret != -1)
			{
				printf("找到了，下标为：%d\n", ret);
			}
			else
			{
				printf("找不到\n");
			}
			
			SLDestroy(&s);
			return 0;
		}

以上代码的结果：