数据结构之顺序表（C语言版本）

发布于：2025-06-28 ⋅ 阅读:(18) ⋅ 点赞:(0)

欢迎拜访：雾里看山-CSDN博客
本篇主题：数据结构之顺序表（C语言版本）
发布时间：2025.6.27
隶属专栏：数据结构

在这里插入图片描述

目录

顺序表的概念

顺序表（Sequence List）是线性表的顺序存储结构，它用一段连续的存储单元依次存储线性表中的数据元素。在C语言中，顺序表通常通过数组来实现。

核心特点：

  • 连续存储：数据元素在内存中连续存放
  • 随机访问：可以通过下标直接访问任意元素
  • 固定容量：需要预先分配存储空间
  • 长度可变：通过记录当前元素数量实现动态使用

顺序表的优缺点分析

优点：

  • 随机访问：通过下标直接访问元素，时间复杂度O(1)
  • 存储密度高：只存储数据元素，无额外空间开销
  • 尾插高效：在表尾插入元素的时间复杂度O(1)
  • 缓存友好：连续存储有利于CPU缓存命中

缺点：

  • 插入/删除慢：平均需要移动n/2个元素，时间复杂度O(n)
  • 容量固定：静态分配需要预先确定大小，可能浪费空间或不足
  • 扩容代价高：动态分配扩容需要复制所有元素，时间复杂度O(n)
  • 内存要求：需要连续的大块内存空间

顺序表的使用场景

  • 元素数量相对固定的应用
  • 查询操作远多于插入删除的场景
  • 需要快速随机访问元素的情况
  • 对内存占用敏感的嵌入式系统
  • 元素规模较小的数据集合

具体实现（以动态为例）

创建结构体

顺序表一般可分为：

  1. 静态顺序表：使用定长数组存储元素。
  2. 动态顺序表：使用动态开辟的数组存储。

静态顺序表

// 静态顺序表
#define N 1000 // 顺序表的最大容量

typedef int SLDataType; //顺序表存储的数据类型

struct SeqList
{
	SLDataType a[N]; //存储元素的数组
	int size;		 //当前元素个数
};

动态顺序表

typedef int SLDataType;//顺序表存储的数据类型

typedef struct SeqList
{
	SLDataType* a;   // 动态分配数组的指针
	int size;        // 存储有效数据的个数
	int capacity;    // 数组的空间大小
}SL;

基本功能 接口实现

初始化

初始化阶段先开辟少量的空间，便于后续操作

void SLInit(SL* ps)
{
	assert(ps); //断言避免传参是空指针

	ps->a = (SLDataType *)malloc(sizeof(SLDataType) * 4);// 预先开辟出来一定的空间
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	ps->size = 0;
	ps->capacity = 4;
}

销毁

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

打印

void SLPrint(SL* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
		printf("\n");
	}
}

扩容检查 接口实现

当size和capacity相同时，就要准备进行扩容操作了。此处的实现是将空间二倍扩容。

void SLCheckCapacity(SL* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		SLDataType * tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-2);
		}
		ps->a = tmp;
		ps->capacity = ps->capacity * 2;
	}
}

增删查改 接口实现

增

头插

头插要考虑好是否需要扩容，而且要将所有数据进行移动。

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	SLCheckCapacity(ps);

	for (int i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;

}
尾插

尾插不需要移动数据，只需要考虑是否扩容即可

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);

	SLCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}
指定位置插入

这里要考虑数据插入的位置是否合理，数组是否需要扩容和数组中的元素移动的问题

// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	if (ps->size <= pos || pos < 0)
		return;	

	SLCheckCapacity(ps);

	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}

删

头删

头删要考虑数组中是否存在数据和后面数据的移动问题。

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

}
尾删

只需要判断是否存在数据即可。

void SLPopBack(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
		return;
	ps->a[ps->size-1] = 0;
	ps->size--;
}
指定位置删除

要考虑删除的位置是否合理，后续数据的移动问题

// 删除pos位置的值
void SLErase(SL* ps, int pos)
{
	assert(ps);

	if (ps->size <= pos || pos < 0)
		return ;

	for (int i = pos; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

查

遍历数组，返回元素下标，如果元素不存在，返回-1

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}

改

需要判断元素位置是否合理

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);

	if (ps->size <= pos || pos < 0)
		return;
	ps->a[pos] = x;
}

整体代码展示

整体的代码包括三个文件：SeqList.h、 SeqList.c和 main.c

SeqList.h

#pragma once

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>


// 静态顺序表
//#define N 1000 // 顺序表的最大容量
//
//typedef int SLDataType; //顺序表存储的数据类型
//
//struct SeqList
//{
//	SLDataType a[N]; //存储元素的数组
//	int size;		 //当前元素个数
//};

// 动态顺序表
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int size;      // 存储有效数据的个数
	int capacity;  // 顺序表空间大小
}SL;


// 管理数据 -- 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);

// 扩容检查机制
void SLCheckCapacity(SL* ps);

// 头插头删 尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

// 返回下标，没有找打返回-1
int SLFind(SL* ps, SLDataType x);

// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);

// 删除pos位置的值
void SLErase(SL* ps, int pos);

//修改pos位置的值
void SLModify(SL* ps, int pos, SLDataType x);

SeqList.c

#include "SeqList.h"


// 管理数据 -- 增删查改
void SLInit(SL* ps)
{
	assert(ps);

	ps->a = (SLDataType *)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

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

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

	if (ps->size == ps->capacity)
	{
		SLDataType * tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-2);
		}
		ps->a = tmp;
		ps->capacity = ps->capacity * 2;
	}
}

// 头插头删 尾插尾删
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);

	SLCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}
void SLPopBack(SL* ps)
{
	assert(ps);
	if (ps->size == 0)
		return;
	ps->a[ps->size-1] = 0;
	ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	SLCheckCapacity(ps);

	for (int i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;

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

// 返回下标，没有找打返回-1
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}

// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	if (ps->size <= pos || pos < 0)
		return;	

	SLCheckCapacity(ps);

	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}
// 删除pos位置的值
void SLErase(SL* ps, int pos)
{
	assert(ps);

	if (ps->size <= pos || pos < 0)
		return ;

	for (int i = pos; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);

	if (ps->size <= pos || pos < 0)
		return;
	ps->a[pos] = x;
}

main.c

#include<stdio.h>
#include"SeqList.h"



void TestSeqList1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 0);
	SLPushBack(&sl, 0);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	/*SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);*/
	SLPrint(&sl);

	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSeqList2()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLPushFront(&sl, 10);
	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSeqList3()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPopFront(&sl);
	//SLPopFront(&sl);
	SLPrint(&sl);

	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSeqList4()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushFront(&sl, -1);
	SLPushFront(&sl, -2);
	SLPrint(&sl);

	SLInsert(&sl, 3, 40);
	SLPrint(&sl);

	int x;
	scanf("%d", &x);
	int pos = SLFind(&sl, x);
	if (pos != -1)
	{
		SLInsert(&sl, pos, x * 10);
	}
	SLPrint(&sl);

	SLDestroy(&sl);

}

void TestSeqList5()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLErase(&sl, 2);
	SLPrint(&sl);

	int x;
	scanf("%d", &x);
	int pos = SLFind(&sl, x);
	if (pos != -1)
	{
		SLErase(&sl, pos);
	}
	SLPrint(&sl);

	SLDestroy(&sl);

}

void TestSeqList6()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLModify(&sl, 2, 20);
	sl.a[2] = 20;

	SLPrint(&sl);

	/*int x;
	scanf("%d", &x);
	int pos = SLFind(&sl, x);
	if (pos != -1)
	{
		SLModify(&sl, pos, x*10);
	}
	SLPrint(&sl);*/

	int pos, x;
	scanf("%d%d", &pos, &x);
	//sl.a[pos] = x;
	SLModify(&sl, pos, x);

	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSeqList7()
{
	/*SL* sl = NULL;
	SLInit(sl);
	SLPushBack(sl, 1);
	SLPushBack(sl, 2);
	SLPushBack(sl, 3);
	SLPushBack(sl, 4);
	SLPushBack(sl, 5);
	SLPrint(sl);*/

	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLPopFront(&sl);

	SLDestroy(&sl);
}

//int main()
//{
//	TestSeqList6();
//
//	return 0;
//}



void menu()
{
	printf("****************************************\n");
	printf("1、尾插  2、头插\n");
	printf("3、头删  4、尾删\n");
	// ...
	printf("7、打印 -1、退出\n");

	printf("****************************************\n");
}


int main()
{
	SL sl;
	SLInit(&sl);
	int option = 0;
	do
	{
		menu();
		scanf("%d", &option);

		if (option == 1)
		{
			//printf("请依次输入输入你要插入的数据，以-1结束\n");
			printf("请依次输入你要插入数据个数和数据\n");
			int n = 0;
			scanf("%d", &n);

			int x = 0;
			for (int i = 0; i < n; i++)
			{
				scanf("%d", &x);
				SLPushBack(&sl, x);
			}
		}
		else if (option == 2)
		{
			printf("请依次输入你要插入数据个数和数据\n");
			int n = 0;
			scanf("%d", &n);

			int x = 0;
			for (int i = 0; i < n; i++)
			{
				scanf("%d", &x);
				SLPushFront(&sl, x);
			}
		}
		else if (option == 3)
		{
			SLPopFront(&sl);
		}
		else if (option == 4)
		{
			SLPopBack(&sl);
		}
		else if (option == 7)
		{
			SLPrint(&sl);
		}
	} while (option != -1);

	SLDestroy(&sl);

	return 0;
}

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布