1. AI技术聚合首页
  2. IT

【数据结构】顺序表详解

xiaoxingxing • • IT • 阅读 45

前言

接下来我们进入数据结构的学习~

要提前准备的C语言知识包括： 结构体 、 指针（一级指针，二级指针、指针传参、结构体指针）、 动态内存管理。

欢迎关注个人主页：逸狼

创造不易，可以点点赞吗~

如有错误，欢迎指出~

目录

前言

认识数据结构

线性表

顺序表

静态顺序表

动态顺序表

动态顺序表的初始化、打印

头文件Seqlist.h

实现接口Seqlist.c

 测试文件test.c

调试代码

动态顺序表的插入

尾插

头插

头文件Seqlist.h

实现接口Seqlist.c

 测试文件test.c

调试代码 尾插

运行结果  头插和尾插

顺序表删除

尾删

头删

​编辑

头文件Seqlist.h

实现接口Seqlist.c

 测试文件test.c

调试代码

顺序表指定位置插入

顺序表指定位置删除

头文件Seqlist.h

实现接口Seqlist.c

 测试文件test.c

调试代码

认识数据结构

数据结构是计算机存储、组织数据的方式

  • 能够存储数据（如顺序表、链表等结构）
  • 存储的数据能够⽅便查找

通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操 作。 最基础的数据结构：数组。

线性表

线性表是n个具有相同特性的数据元素的有限序列。常⻅的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构，但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

顺序表

底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

静态顺序表

给定的数组长度

缺点：

  • 若空间不够，会导致后续的数据保存失败（数据丢失是严重的技术事故！）
  • 若空间太大，会导致空间大大的浪费
#include<stdio.h>
//宏定义，让代码更加灵活，方便修改
#define N 100

//静态顺序表

typedef int SLDataType;//将int类型名称改为SLDataType，为了以后改为其他类型更方便

struct SeqList
{
	SLDataType a[N];
	SLDataType size;
};

动态顺序表

动态顺序表就可以避免静态顺序表的问题

如下的代码创建了一个动态顺序表

//动态顺序表
typedef int SLDataType;//将int类型名称改为SLDataType，为了以后改为其他类型更方便

typedef struct SeqList
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;   //记录顺序表的空间大小
	int size;       //记录顺序表当前有效的数据个数
}SL;//将struct SeqList类型改为SL,简洁易写
//typedef struct SeqList SL;这样修改也行

创建三个文件

动态顺序表的初始化、打印

头文件Seqlist.h


//顺序表的初始化
void SLInit(SL* ps);//因为SL未初始化，不能传值（传值：形参是实参的临时拷贝，这里实参没有初始化，就没有值），所以只能传地址


//打印顺序表
void SLPrint(SL* ps);

实现接口Seqlist.c

#include"SeqList.h"

//顺序表的初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//打印顺序表
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

 测试文件test.c

#include"SeqList.h"
void slTest01()
{
	SL sl;//创建一个结构体变量sl
	SLInit(&sl);//初始化sl
}


int main()
{
	slTest01();

	return 0;
}

调试代码

动态顺序表的插入

尾插

在顺序表的尾部插入

情况1：空间足够

直接插入

情况2：空间不足

先扩容，变成情况1

扩容原则：

  1. 一次扩1个空间（插入一个元素不会造成空间浪费）
  2. 一次扩固定个大小的空间（10，100……）
  3. 推荐：选择成倍数增加（1.5倍，2倍）

头插

在顺序表的头部插入

头文件Seqlist.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//尾插（在顺序表的尾部插入）
void SLPushBack(SL* ps, SLDataType x);//ps表示要插入的顺序表，x表示要插入的数据

//头插（在顺序表的头部插入）
void SLPushFront(SL* ps, SLDataType x);
实现接口Seqlist.c
//空间扩容2倍的函数
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//扩容2倍空间
		//capacity可能为0，要先判断，否则2*0 ，空间还是0
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//三目表达式 ps->capacity == 0 ? 4 : 2 ps->capacity判断原空间是否为0，为真，表达式等于4；为假，表达式等于2倍原空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");//报错，扩容失败
			exit(1);//扩容失败直接中断程序
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插（在顺序表的尾部插入）
void SLPushBack(SL* ps, SLDataType x)//ps表示要插入的顺序表，x表示要插入的数据
{
	//assert断言---粗暴的解决方式
	assert(ps);


	//if 判断---温柔的解决方式
	//if (ps == NULL)
	//{
	//	return;//如果顺序表为空，直接结束
	//}
	//空间不够，扩容
	SLCheckCapacity(ps);
	
	//空间足够，直接插入
	ps->arr[ps->size] = x;
	ps->size++;
}

//头插（在顺序表的头部插入）
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	//判断是否扩容
	SLCheckCapacity(ps);

	//每个旧数据都往后挪动一位
	for (int i = ps->size; i >0 ; i--)//从最后一位数据开始移动，直到i==1
	{
		ps->arr[i] = ps->arr[i - 1];//直到ps->arr[0]=ps->arr[1];
	}
	ps->arr[0] = x;//将x赋值给第一个位置
	ps->size++;//数组arr个数+1
}
 测试文件test.c
#include"SeqList.h"
void slTest01()
{
	SL sl;//创建一个结构体变量sl
	SLInit(&sl);//初始化sl


	//测试尾插
	SLPushBack(&sl, 1);//在顺序表sl插入1
	SLPushBack(&sl, 2);//插入2
	SLPushBack(&sl, 3);//插入3
	SLPushBack(&sl, 4);//插入4
	//1 2 3 4 

	//头插
	SLPushFront(&sl, 5);//插入5
	SLPushFront(&sl, 6);//插入6
	SLPushFront(&sl, 7);//插入7
	//7 6 5 1 2 3 4

	//打印
	SLPrint(&sl);

}


int main()
{
	slTest01();

	return 0;
}
调试代码 尾插

运行结果  头插和尾插

顺序表删除

尾删

  1. 顺序表为空，不能删除
  2. 顺序表不为空，删除最后一个数据，size-1

头删

  1. 顺序表为空，不能删除
  2. 顺序表不为空，删除最后一个数据，将数据向前移动一位，size-1
头文件Seqlist.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//尾删
void SLPopBack(SL* ps);

//头删
void SLPopFront(SL* ps);
实现接口Seqlist.c
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);

	//顺序表为空，不能删除
	assert(ps -> size);

	//顺序表不为空，删除最后一个数据，size-1
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	//顺序表为空
	assert(ps->size);
	//顺序表不为空
	for (int i = 0; i < ps->size - 1; i++)//i最大等于size-2
	{
		ps->arr[i] = ps->arr[i + 1];//最后一位ps->arr[size-2]=ps->arr[size-1]
	}
	ps->size--;
}
 测试文件test.c
#include"SeqList.h"
void slTest01()
{
	SL sl;//创建一个结构体变量sl
	SLInit(&sl);//初始化sl


	//测试尾插
	SLPushBack(&sl, 1);//在顺序表sl插入1
	SLPushBack(&sl, 2);//插入2
	SLPushBack(&sl, 3);//插入3
	SLPushBack(&sl, 4);//插入4
	//1 2 3 4 

	//头插
	SLPushFront(&sl, 5);//插入5
	SLPushFront(&sl, 6);//插入6
	SLPushFront(&sl, 7);//插入7
	//7 6 5 1 2 3 4

	//测试尾删
	SLPopBack(&sl);//删除4
	SLPopBack(&sl);//删除3
	SLPopBack(&sl);//删除2
	//7 6 5 1

	//头删
	SLPopFront(&sl);//删除7
	SLPopFront(&sl);//删除6
	//5 1

	//打印
	SLPrint(&sl);

}

int main()
{
	slTest01();

	return 0;
}
调试代码

顺序表指定位置插入

顺序表指定位置删除

头文件Seqlist.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);

//指定位置删除数据
void SLErase(SL* ps, int pos);
实现接口Seqlist.c
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//限定pos的范围
	assert(pos >= 0 && pos < ps->size);
	//先检查是否要扩容
	SLCheckCapacity(ps);

	for (int i=ps->size ;i>pos;i--)
	{
		ps->arr[i] = ps->arr[i - 1];//pos之后的数据向后移动一位
	}
	ps->arr[pos] = x;//pos的位置放入x
	ps->size++;//size+1

}

//指定位置删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//限定pos的范围
	assert(pos >= 0 && pos < ps->size);

	//pos以后的数据向前移动一位
	for (int i =pos ;i<ps->size-1;i++ )
	{
		ps->arr[i] = ps->arr[i+1];
	}
	ps->size--;
}
 测试文件test.c
#include"SeqList.h"
void slTest01()
{
	SL sl;//创建一个结构体变量sl
	SLInit(&sl);//初始化sl


	//测试尾插
	SLPushBack(&sl, 1);//在顺序表sl插入1
	SLPushBack(&sl, 2);//插入2
	SLPushBack(&sl, 3);//插入3
	SLPushBack(&sl, 4);//插入4
	//1 2 3 4 

	//测试指定位置插入
	SLInsert(&sl, 2, 100);//下标2的位置插入100
	SLInsert(&sl, 0, 200);//下标0的位置插入200
	//200 1 2 100 3 4

	//测试指定位置删除
	SLErase(&sl, 2);//下标2的位置删除
	//200 1 100 3 4
	SLErase(&sl, 4);//下标0的位置
	//200 1 100 3

	//打印
	SLPrint(&sl);

}

int main()
{
	slTest01();

	return 0;
}
调试代码

版权声明：本文为博主作者：逸狼原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/2301_80898480/article/details/136502469

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2024年4月1日
下一篇 2024年4月1日

相关推荐