程序员经验分享-hwhale

数据结构初阶 ---- 顺序表的(C语言)实现

2023-11-15

目录

一.动态顺序表的结构体定义

二.动态顺序表的函数接口

1.顺序表的初始化

 2.顺序表的销毁

3.打印结构体数组内的内容

4.检查数组容量(容量不够时，扩容）

5.顺序表的尾插

6.顺序表的尾删

 7.顺序表的头插

 8.顺序表的头删

9.顺序表的查找 （找到了，就返回x的下标，没有找到的话，就返回 -1）

10.顺序表在pos位置插入指定的数字x

 11.顺序表删除pos位置的值

三.源代码

1.SeqList.h

2.SeqList.c

3.Test.c

一.动态顺序表的结构体定义

（顺序表可以动态存储也可以静态存储，但是一般采用的都是动态存储，可以减少空间的浪费）。

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;     //表示数组中存储了多少个有效的数据
	int capacity; //表示数组实际能存储的空间容量的大小
}SL;

这里把int 重定义(typedef)了一下,这样做的目的也是为了方便以后如果想更改这个顺序表中数组的数据类型时会很方便。

二.动态顺序表的函数接口

//接口函数
void SeqListInit(SL* ps);//初始化
void SeqListDestory(SL* ps);//销毁函数
void SeqListPrint(SL* ps);//打印结构体数组内的内容
void SeqListCheckCapacity(SL* ps);//检查容量的函数
void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删

//找到了，就返回x的下标，没有找到的话，就返回 -1
int SeqListFind(SL* ps, SLDataType x);//寻找某个值的位置的函数
//在pos下标位置进行插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的数据
void SeqListErase(SL* ps, int pos);

1.顺序表的初始化

顺序表的初始化：就是对它的指针，数据个数，和容量进行了初始化

void SeqListInit(SL* ps)//初始化
{
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

 2.顺序表的销毁

顺序表的销毁：就是把它的指针释放销毁掉，然后置空；把它的数据个数和容量也都置为0

void SeqListDestory(SL* ps)//销毁函数
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

3.打印结构体数组内的内容

void SeqListPrint(SL* ps)//打印结构体数组内的内容
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

4.检查数组容量(容量不够时，扩容）

在进行扩容的时候，是有2种情况的，一种是这个数组还是一个空的数组的时候，我们需要给它开辟空间；另一种情况就是如果这个数组不是空的，而是容量满了需要扩容的话，我们就可以给它扩容，扩2倍。(这里为什么是扩2倍呢？主要就是为了不必频繁扩容）

void SeqListCheckCapacity(SL* ps)//检查容量的函数
{
	if (ps->size == ps->capacity)
	{
        // 这里用到了三目操作符
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

5.顺序表的尾插

只要是插入操作就要考虑空间是否够用，是否需要增容的问题，所以在插入之前要先检查一下空间容量。

尾插在检查好空间容量以后，就直接插入就可以了。

void SeqListCheckCapacity(SL* ps)//检查容量的函数
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
	SeqListCheckCapacity(ps);//检查容量的函数
	ps->a[ps->size] = x;
	ps->size++;
}

6.顺序表的尾删

删除操作，要考虑数组内是否还有元素，如果没有了就不能再进行删除操作了。

这里使用assert来进行断言，所以当数组内没有元素以后，程序就不会再继续向下执行删除操作了。

void SeqListPopBack(SL* ps)//尾删
{
	assert(ps->size > 0);
	ps->size--;
}

 7.顺序表的头插

只要是插入操作就要考虑空间是否够用，是否需要增容的问题，所以在插入之前要先检查一下空间容量。

头插，需要把数组内原有的所有元素 从后往前 依次向后挪动一位，然后再进行头插，把要插入的值放到数组下标为0的位置（数组的头）。

void SeqListCheckCapacity(SL* ps)//检查容量的函数
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

void SeqListPushFront(SL* ps, SLDataType x)//头插
{
	SeqListCheckCapacity(ps);//检查容量的函数
	int i = 0;
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}

 8.顺序表的头删

删除操作，要考虑数组内是否还有元素，如果没有了就不能再进行删除操作了。

头删的操作，就是从正数第2个元素（下标为1的位置）开始，从前向后 依次向前挪动一位。

void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size > 0);//不为空才能继续往下走，去进行删除的操作
	int i = 1;
	for (i = 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}
	ps->size--;
}

9.顺序表的查找 （找到了，就返回x的下标，没有找到的话，就返回 -1）

//找到了，就返回x的下标，没有找到的话，就返回 -1
int SeqListFind(SL* ps, SLDataType x)//寻找某个值的位置的函数
{
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}

10.顺序表在pos位置插入指定的数字x

插入操作都是要先判断容量是否够用，是否需要扩容；然后再继续插入的操作。

//在pos下标位置进行插入
//pos是下标
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SeqListCheckCapacity(ps);//检查容量的函数 
	int end = ps->size;
	while (end != pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
找到了就插入，没找到就不插入，这里的pos是数组下标的意思。

 11.顺序表删除pos位置的值

删除操作，要先判断数组是否为空，为空的话就不必执行删除操作了；不为空的话再继续执行删除操作。（这里的pos也是数组下标的意思）

//删除pos位置的数据
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos;
	while (begin < ps->size - 1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

三.源代码

1.SeqList.h

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

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;     //表示数组中存储了多少个有效的数据
	int capacity; //表示数组实际能存储的空间容量的大小
}SL;

//接口函数
void SeqListInit(SL* ps);//初始化
void SeqListDestory(SL* ps);//销毁函数
void SeqListPrint(SL* ps);//打印结构体数组内的内容
void SeqListCheckCapacity(SL* ps);//检查容量的函数
void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删

//找到了，就返回x的下标，没有找到的话，就返回 -1
int SeqListFind(SL* ps, SLDataType x);//寻找某个值的位置的函数
//在pos下标位置进行插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的数据
void SeqListErase(SL* ps, int pos);

2.SeqList.c

#include"SeqList.h"


//接口函数
void SeqListInit(SL* ps)//初始化
{
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SeqListDestory(SL* ps)//销毁函数
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SeqListPrint(SL* ps)//打印结构体数组内的内容
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SeqListCheckCapacity(SL* ps)//检查容量的函数
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
	SeqListCheckCapacity(ps);//检查容量的函数
	ps->a[ps->size] = x;
	ps->size++;
}

void SeqListPopBack(SL* ps)//尾删
{
	assert(ps->size > 0);
	ps->size--;
}

void SeqListPushFront(SL* ps, SLDataType x)//头插
{
	SeqListCheckCapacity(ps);//检查容量的函数
	int i = 0;
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size > 0);//不为空才能继续往下走，去进行删除的操作
	int i = 1;
	for (i = 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}
	ps->size--;
}



//找到了，就返回x的下标，没有找到的话，就返回 -1
int SeqListFind(SL* ps, SLDataType x)//寻找某个值的位置的函数
{
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}

//在pos下标位置进行插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SeqListCheckCapacity(ps);//检查容量的函数
	int end = ps->size;
	while (end != pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

//删除pos位置的数据
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos;
	while (begin < ps->size - 1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

3.Test.c

#include"SeqList.h"
void TestSeqList1()
{
	SL s1;
	SeqListInit(&s1);//初始化
	SeqListPushBack(&s1, 1);//尾插
	SeqListPushBack(&s1, 2);//尾插
	SeqListPushBack(&s1, 3);//尾插
	SeqListPushBack(&s1, 4);//尾插
	SeqListPushBack(&s1, 5);//尾插
	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListPopBack(&s1);//尾删
	SeqListPopBack(&s1);//尾删
	SeqListPopBack(&s1);//尾删
	SeqListPopBack(&s1);//尾删
	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListDestory(&s1);//销毁函数
}

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);//初始化
	SeqListPushBack(&s1, 1);//尾插
	SeqListPushBack(&s1, 2);//尾插
	SeqListPushBack(&s1, 3);//尾插
	SeqListPushBack(&s1, 4);//尾插
	SeqListPushBack(&s1, 5);//尾插
	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListPushFront(&s1, 10);//头插
	SeqListPushFront(&s1, 20);//头插
	SeqListPushFront(&s1, 30);//头插
	SeqListPushFront(&s1, 40);//头插
	SeqListPushFront(&s1, 50);//头插
	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListPopFront(&s1);//头删
	SeqListPopFront(&s1);//头删
	SeqListPopFront(&s1);//头删
	SeqListPrint(&s1);//打印结构体数组内的内容
	SeqListDestory(&s1);//销毁函数
}

void TestSeqList3()
{
	SL s1;
	SeqListInit(&s1);//初始化
	SeqListPushBack(&s1, 1);//尾插
	SeqListPushBack(&s1, 2);//尾插
	SeqListPushBack(&s1, 3);//尾插
	SeqListPushBack(&s1, 4);//尾插
	SeqListPushBack(&s1, 5);//尾插

	SeqListPushFront(&s1, 10);//头插
	SeqListPushFront(&s1, 20);//头插
	SeqListPushFront(&s1, 30);//头插
	SeqListPushFront(&s1, 40);//头插
	SeqListPushFront(&s1, 50);//头插
	SeqListPrint(&s1);//打印结构体数组内的内容

	int a = SeqListFind(&s1, 100);//寻找某个值的位置的函数
	int b = SeqListFind(&s1, 40);//寻找某个值的位置的函数
	printf("%d %d\n", a, b);

	SeqListInsert(&s1, 10, 60);//在pos下标位置进行插入
	SeqListPrint(&s1);//打印结构体数组内的内容
	SeqListInsert(&s1, 0, 60);//在pos下标位置进行插入
	SeqListPrint(&s1);//打印结构体数组内的内容
	SeqListInsert(&s1, 3, 60);//在pos下标位置进行插入
	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListDestory(&s1);//销毁函数
}

void TestSeqList4()
{
	SL s1;
	SeqListInit(&s1);//初始化
	SeqListPushBack(&s1, 1);//尾插
	SeqListPushBack(&s1, 2);//尾插
	SeqListPushBack(&s1, 3);//尾插
	SeqListPushBack(&s1, 4);//尾插
	SeqListPushBack(&s1, 5);//尾插

	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListErase(&s1, 0);//删除pos位置的数据
	SeqListPrint(&s1);//打印结构体数组内的内容
	SeqListErase(&s1, 2);//删除pos位置的数据
	SeqListPrint(&s1);//打印结构体数组内的内容
	SeqListErase(&s1, 2);//删除pos位置的数据
	SeqListPrint(&s1);//打印结构体数组内的内容

	int pos = SeqListFind(&s1, 3);
	if (pos != -1)
	{
		SeqListErase(&s1, pos);
	}
	SeqListPrint(&s1);//打印结构体数组内的内容

	SeqListDestory(&s1);//销毁函数
}

int main()
{
	//TestSeqList1();
	//TestSeqList2();
	//TestSeqList3();
	//TestSeqList4();
	return 0;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

c语言

算法

数据结构初阶 ---- 顺序表的(C语言)实现 的相关文章

随机推荐

  • SimpleDateFormat案例

    package Java project 1 import java text ParseException import java text SimpleDateFormat import java util Date public cl

  • 使用VS创建的C#winfrom窗体窗体设计界面突然不见了解决方法

    使用VS创建的C winfrom窗体窗体设计界面突然不见了解决方法 原因 在主窗体的类前面添加了一个新类 这样会导致原来的窗体设计界面无法显示 正常可以显示的情况下如下图所示 但是如果在主窗体类的前面再添加一个类之后 窗体设计界面就会无法显

  • Java-面向对象2-向下转型

    多态的补充 有了对象的多态性以后 内存中实际上是加载了子类特有的属性和方法的 但是由于变量声明为父类类型 导致编译时 只能调用父类中声明的属性和方法 子类特有的属性和方法不能调用 如何才能调用子类特有的属性和方法 向下转型 使用强制类型转换

  • 将现有MySQL数据库改为大小写不敏感

    摘要 用过MySQL的应该都会注意到 默认情况下 Linux下安装的MySQL是大小写敏感的 也就是说Table1和table1可以同时存在 而Windows下的MySQL却是大小写不敏感的 所有表名和数据库名都会变成小写 用过MySQL的

  • Java中try catch的原则

    一 使用try catch的场合 如果不使用这种try结构时 代码报错退出就无bai法继续执行 有的代码出错就应该退出 有的出错尚可以补救 就不应该退出 对于这种出错不应该退出的就需要使用这种结构 在catch中进行补救 二 使用try c

  • 项目作品展示

    本人本科所读专业 机械设计专业 对于结构设计有一定的经验 读研期间的主要方向为机器视觉 以及以目标检测为代表的深度学习在日常生活中以及工业上的应用 1 基于机器视觉的测量系统 2 基于机器视觉的玻璃缺陷检测系统 3 基于机器视觉的油墨测量

  • day02

    springboot注解 ApiOperation 接口文档注解功能 PathVariable 获取requestMapping中的参数值 转载于 https www cnblogs com lik99999 p 11460401 html

  • MGRE GRE PPP协议综合运用

    题目 题目要求 思路 1 拿到拓扑图 我们先看第一个要求 r5是isp isp是网络服务运营商 不能被通告进路由协议 所以在配置时 要写一条静态缺省 指向isp 2 从拓扑图我们可以看出 在实验前需要先加2SA板卡 连接成串线 3 在完成前

  • B-tree/B+tree/B*tree

    B 树 1 前言 动态查找树主要有 二叉查找树 Binary Search Tree 平衡二叉查找树 Balanced Binary Search Tree 红黑树 Red Black Tree B tree B tree B tree B

  • EAN13条形码绘制（Delphi版）

    单元声明 unit UnitEAN https wenku baidu com view d61eec0dc4da50e2524de518964bcf84b9d52d0d html 共有95 18 113条数据模块 1表示黑 0表示白 左侧

  • Python版SSH远程服务器使用Paramiko和scp库

    作为开发人员 配置或调试VPS通常是无法解决的 而且并不是特别有意义 充其量 您的应用程序可能最终将以与本地环境相同的方式运行 我们如何才能使这一不可避免的工作变得更好 好吧 我们可以使其自动化 设置SSH密钥 要验证SSH连接 我们需要设

  • 图像处理算法大全（基于libyuv或IPP）----NV12转成I420,RGB24,ARGB集合

    周星星教你学ffmpeg 技巧 libyuv源码 static void NV12ToI420 BYTE pNV12 Y BYTE pNV12 UV BYTE pYV12 int width int height libyuv NV12To

  • 在Nginx中让所有HTTP请求转发到HTTPS

    title 在Nginx中让所有HTTP请求转发到HTTPS date 2017 10 23 20 50 24 tags nginx http https categories 运维 背景 在启用HTTPS协议的网站上 通常会让用户始终以

  • Sklearn常用API以及代码

    1 ensemble 集成 VotingClassifier 投票分类器 由若干异质分类器组成 例如LR RF朴素贝叶斯 GNB import numpy as np from sklearn import datasets from sk

  • 2022年业绩逆势增长，“要强”蒙牛再创蒙牛

    2022年是蒙牛 再造一个新蒙牛 五年计划的第二年 也是乳企赛道疫情以来最为艰难的一年 这一年里 不仅有疫情多点散发所带来的线下渠道不畅 也有原材料价格飙涨所导致的成本高企 在这种形势下 蒙牛尽管遭遇多重困难 但仍拿出了一份亮眼的成绩单 其

  • Eclipse 连接 SQL Server 2008数据库，运行JAVA代码时出现：‘sa’用户登录失败

    前几天用Eclipse 连接 SQL Server 2008数据库 运行JAVA代码时总是出现 sa 用户登录失败 我的连接方法都是按照网上找的 一直在寻找错误的原因 网上说 1 sql server的密码是否正确 2 sql server

  • 西瓜书《机器学习》课后答案——chapter7

    7 1 试使用极大似然法估计西瓜数据集3 0中前3个属性的类条件概率 解答 假设类别C为随机变量 则它总共有两种取值 好瓜和坏瓜 前3个属性分别为色泽 根蒂和敲声 分别用随机变量R S T表示 并且可取值分别为 青绿 乌黑 浅白 38738

  • Array K-Coloring【Codeforces Round #531 (Div. 3)B】【构造】

    题目链接 题意 给你N长度的数组 以及K种颜色 要求的是我们能否使用全部K种颜色来填充每个数组元素 其中数组中的每个相同值元素的染色是不能相同的 并且 要用完所有K个颜色 能达到以上要求 则是YES并输出染色 否则 只有NO 我WA在了第6

  • 一个或多个筛选器或者Listeners启动失败

    今天使用tomcat直接部署项目 之前一直都是在idea直接部署 但是在启动tomcat的过程中一直报一个或多个筛选器或者Listeners启动失败的错误 之前在idea部署的时候也出现过这个错误 然后就根据网上的答案说 lib 下可能没有

  • 数据结构初阶 ---- 顺序表的(C语言)实现

    目录 一 动态顺序表的结构体定义 二 动态顺序表的函数接口 1 顺序表的初始化 2 顺序表的销毁 3 打印结构体数组内的内容 4 检查数组容量 容量不够时 扩容 5 顺序表的尾插 6 顺序表的尾删 7 顺序表的头插 8 顺序表的头删 9 顺

热门标签