【数据结构初阶】顺序表SeqList

news/2024/11/30 0:33:17/

描述

顺序表我们可以把它想象成在一个表格里面填数据，并对数据做调整；

那我们的第一个问题是：怎么样在创建出足够的空间呢？

我们可以去堆上申请，用一个指针指向一块空间，如果申请的空间不够，我们可以再realloc申请出来。

我们的第二个问题是：怎么样标记我们用了多少空间呢？

这时我们就需要一个变量来记录我们当前的用到第几个“格子”（即用了多少空间），我们这里用size来表示：

我们的第三个问题是：怎么样知道我们有空间呢？

这时我们就需要一个变量来记录我们“格子”总数（即拥有多少空间），我们这里用capacity来表示：

所以（在.h文件中）我们线性表的结构体描述为：

typedef int SLDataType;typedef struct SeList
{SLDataType* a;int size;int capacity;
}SL;

组织

  1. 初始化
  2. 释放
  3. 尾插
  4. 尾删
  5. 头插
  6. 头删
  7. 指定位置删除
  8. 指定位置插入
  9. 查找指定元素

1.初始化

把我们描述出来的顺序表结构体里的变量初始化

在.h文件中：

因为要对创建出来的结构体里的内容进行修改，所以函数要进行传址调用；

在.c文件中:

我们用malloc来开辟空间,同时注意检查malloc；

因为我们刚刚开辟空间，并没有往顺序表里增删查改 所以此时size为0；

而我们的capacity就是在malloc开辟的空间大小。

void SLInit(SL* ps)
{assert(ps->a);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

2.释放

将描述出来的顺序表结构体里的变量逐个进行释放；

在.h 文件中：

在.c文件中：

首先是指针a，需要使用free函数将其释放，还需要注意的是free后，需要将a置空，避免出现野指针；

因为size和capacity是临时变量储存在栈上，函数调用结束后会自动释放，我们这里把它改为0就可以了。

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

3.尾插

向顺序表的尾部插入数据；

在.h 文件中：

在.c文件中：

尾插数据时，首先，需要判断capacity（空间）是否足够，如果不够需要扩容，这里我们写个扩容函数：

扩容我们用realloc函数，最后要返回ps至尾插函数判断是否为空；

接着，才能将数据尾插；

最后别忘了调整size的位置；

SL* SLExpand(SL* ps)
{assert(ps->a);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)* ps->capacity*2);if (tmp == NULL){perror("realloc fail");return NULL;}ps->capacity *=2;ps->a = tmp;}return ps;
}void SLPushBack(SL* ps,SLDataType x)
{assert(ps->a);//扩容if (ps->size == ps->capacity){SL* ret = SLExpand(ps);if (ret == NULL){return;}}ps->a[ps->size] = x;ps->size++;}

4.尾删

将顺序表的尾部删除；

在.h 文件中：

在.c 文件中：

因为顺序表是从开始连续存储size个数据，不能单独释放那一块区域，所以我们直接将size--就可以了，如果往后插入的话，就直接把数据覆盖；

assert（）如果当capacity为空的时候还尾删时会报错,并且终止程序；

void SLPopBack(SL* ps)
{assert(ps->a);ps->size--;
}

5.头插

向顺序表的头部插入数据；

在.h 文件中：

在.c 文件中：

首先，我们得先判断空间是否足够，如果不够就扩容；

第二步：把数据往后移一位，数据从最后一位开始向后移动；

第三步：进行数据头插，别忘了把size的大小改改；

void SLPushFront(SL* ps, SLDataType x)
{assert(ps->a);//扩容if (ps->size == ps->capacity){SL* ret = SLExpand(ps);if (ret == NULL){return;}}//移动数据for (int i = ps->size; i >0 ; i--){ps->a[i] = ps->a[i - 1];}//头插ps->a[0] = x;ps->size++;}

6.头删

将顺序表的头部数据删除；

在.h 文件中：

在.c 文件中：

我们只需要将从第二位数据开始往前移动，把前一位的数据覆盖就可以达到头删的效果；

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

7.指定位置删除

将顺序表的指定位置数据删除；

在.h 文件中：

在.c 文件中：

首先，要先用assert检查一下空间和size的值是否合理；

如果删除的数据是最后一个就直接尾删；

如果如果删除的数据不是最后一个就需要移动数据覆盖，类似于头删；

void SLErase(SL* ps, int pos)
{assert(ps->a);assert(pos >= 0&&pos<ps->size);//如果pos是最后一个数据，尾删if (pos == ps->size - 1){SLPopBack(ps);}else{for (int i = pos; i < ps->size; i++){ps->a[i] = ps->a[i + 1];}ps->size--;}}

8.指定位置插入

将顺序表的指定位置数据插入；

在.h 文件中：

在.c 文件中：

首先，要先用assert检查一下空间和size的值是否合理；

如果删除的数据是最后一个就直接尾插；

如果如果删除的数据不是最后一个就需要移动数据，再插入数据，类似于头插；

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps->a);assert(pos >= 0 && pos <= ps->size);//判断容量if (ps->size == ps->capacity){SL* ret = SLExpand(ps);if (ret == NULL){return;}}//尾插if (pos == ps->size - 1){SLPushBack(ps,x);}else{for (int i = ps->size; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->size++;ps->a[pos] = x;}
}

9.查找指定元素

在顺序表中查找指定数据，并输出其下表，和在该表中的个数；

在.h 文件中：

在.c 文件中：

for循环遍历一下顺序表，如果遍历过程中找到了直接打印其下标，并用一个变量记录它出现的此数。

出循环后打印其和在该表中出现的个数。

void SLFindPoint(SL* ps, SLDataType x)
{assert(ps->a);int cnt = 0;for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){cnt++;printf("找到了第%d个，下标为:%d\n",cnt, i);}}if (cnt == 0){printf("抱歉，无该数据\n");}else{printf("共找到%d个数据\n", cnt);}
}

整个程序

.h文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>typedef int SLDataType;
#define INIT_CAPACITY 4typedef struct SeList
{SLDataType* a;int size;int capacity;
}SL;void SLPrint(SL* ps);void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLErase(SL* ps,int pos);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLFindPoint(SL* ps, SLDataType x);

.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"void SLPrint(SL* ps)
{assert(ps->a);for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}void SLInit(SL* ps)
{assert(ps->a);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLDestroy(SL* ps)
{assert(ps->a);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}SL* SLExpand(SL* ps)
{assert(ps->a);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)* ps->capacity*2);if (tmp == NULL){perror("realloc fail");return NULL;}ps->capacity *=2;ps->a = tmp;}return ps;
}void SLPushBack(SL* ps,SLDataType x)
{assert(ps->a);//扩容if (ps->size == ps->capacity){SL* ret = SLExpand(ps);if (ret == NULL){return;}}ps->a[ps->size] = x;ps->size++;}void SLPopBack(SL* ps)
{assert(ps->a);ps->size--;
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps->a);//扩容if (ps->size == ps->capacity){SL* ret = SLExpand(ps);if (ret == NULL){return;}}//移动数据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->a);assert(ps->size > 0);for (int i = 0; i < ps->size; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}void SLErase(SL* ps, int pos)
{assert(ps->a);assert(pos >= 0&&pos<ps->size);//如果pos是最后一个数据，尾删if (pos == ps->size - 1){SLPopBack(ps);}else{for (int i = pos; i < ps->size; i++){ps->a[i] = ps->a[i + 1];}ps->size--;}}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps->a);assert(pos >= 0 && pos <= ps->size);//判断容量if (ps->size == ps->capacity){SL* ret = SLExpand(ps);if (ret == NULL){return;}}//尾插if (pos == ps->size - 1){SLPushBack(ps,x);}else{for (int i = ps->size; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->size++;ps->a[pos] = x;}
}void SLFindPoint(SL* ps, SLDataType x)
{assert(ps->a);int cnt = 0;for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){cnt++;printf("找到了第%d个，下标为:%d\n",cnt, i);}}if (cnt == 0){printf("抱歉，无该数据\n");}else{printf("共找到%d个数据\n", cnt);}
}


http://www.ppmy.cn/news/1212361.html

相关文章

制作麒麟V10-server-sp2镜像

制作麒麟V10-server-sp2镜像

1.挂载iso 文件到目录 mount -o loop /xxx.iso /mnt 这样mnt 目录下会有iso 解压相关的文件 2.修改源文件内容 vim /etc/yum.repos.d/ kylin_x86_64.repo 将里面的所有的源enabled 都改成 0 并添加一个新的源 [ks10-local] name Kylin Linux Advanced Server 10 - Local base…
阅读更多...
Python与ArcGIS系列（四）在地图文档中加入图层

Python与ArcGIS系列（四）在地图文档中加入图层

目录 0 简述1 将图层添加到地图文档中2 将图层插入到地图文档0 简述 本篇介绍如何利用arcpy实现将图层添加到地图文档中，以及将图层插入到地图文档指定的位置。 1 将图层添加到地图文档中 arcpy的mapping模块提供的AddLayer()函数可以实现将图层添加到地图文档中。功能本质上…
阅读更多...
C++11特性

C++11特性

1.统一的列表初始化 C11扩大了用大括号括起的列表(初始化列表)的使用范围&#xff0c;使其可用于所有的内置类型和用户自 定义的类型&#xff0c;使用初始化列表时&#xff0c;可添加等号()&#xff0c;也可不添加。 struct Point {int _x;int _y; }; int main() {int x1 1;…
阅读更多...
链表经典OJ题（链表回文结构，链表带环，链表的深拷贝）

链表经典OJ题（链表回文结构，链表带环，链表的深拷贝）

目录 前言 1.反转一个单链表。 2. 给定一个带有头结点 head 的非空单链表&#xff0c;返回链表的中间结点。 3.链表的回文结构。 4.链表带环问题&#xff08;*****&#xff09; 4.1是否带环 4.2 入环的节点 5.随机链表的复制&#xff08;链表的深拷贝&#xff09; 前言…
阅读更多...
人工智能基础_机器学习023_理解套索回归_认识L1正则---人工智能工作笔记0063

人工智能基础_机器学习023_理解套索回归_认识L1正则---人工智能工作笔记0063

然后上一节我们说了L1,L2正则是为了提高,模型的泛化能力, 提高泛化能力,实际上就是把模型的公式的w,权重值,变小对吧. 然后我们这里首先看第一个L1正则,是怎么做到把w权重变小的 可以看到最上面是线性回归的损失函数,然后 L1可以看到,这个正则,就是在损失函数的基础上给损失…
阅读更多...
Java必刷入门递归题×5（内附详细递归解析图）

Java必刷入门递归题×5（内附详细递归解析图）

目录 1.求N的阶乘 2.求12...N的和 3.顺序打印数字的每一位 4.求数字的每一位之和 5.求斐波拉契数列 1.求N的阶乘 &#xff08;1&#xff09;解析题目意思 比如求5的阶乘&#xff0c;符号表示就是5&#xff01;&#xff1b;所以5&#xff01;5*4*3*2*1我们下面使用简单的…
阅读更多...
Matplotlib绘图一网打尽【持续更新ing】

Matplotlib绘图一网打尽【持续更新ing】

2 绘制扇形图 绘制一个展示男女乘客比例的扇形图 得出男女的具体数字 sex_per df["Sex"].value_counts() sex_per # 把画图的包导入进来 import matplotlib.pyplot as plt# 这种绘图方式主要用于有多个子图以及复杂的图形布局的时候。fig,ax plt.subplots()# pl…
阅读更多...
Android发热监控实践

Android发热监控实践

一、背景 相信移动端高度普及的现在&#xff0c;大家或多或少都会存在电量焦虑&#xff0c;拥有过手机发热发烫的糟糕体验。而发热问题是一个长时间、多场景的指标存在&#xff0c;且涉及到端侧应用层、手机 ROM 厂商系统、外界环境等多方面的影响。如何有效衡量发热场景、定位…
阅读更多...
最新文章

Copyright @ 2022~2023