跨境派

跨境派

跨境派,专注跨境行业新闻资讯、跨境电商知识分享!

当前位置:首页 > 工具系统 > 数据分析 > 顺序表(详解)

顺序表(详解)

时间:2024-04-15 17:55:24 来源:网络cs 作者:欧阳逸 栏目:数据分析 阅读:

标签: 顺序 

1.什么是数据结构

所谓数据结构也就是数据在内存中的储存结构,它有 线性表,队列,栈结构,树结构,图结构等等,顺序表是线性表的一种。

2.物理结构与逻辑结构

物理结构是指一个数据在内存实际的储存空间,逻辑结构是来抽象的描述数据之间有某种联系。 举个例子:

比如我说:我们是好朋友是一个整体不能分开,但我们真的是一个整体吗?事实上我们是单个的人,相互独立。而这里说成我们是一个整体只是因为我们存在着某种关系,整体是来描述这种关系的一种说法,实际我们是相互独立的。

我们是一个整体 相当于逻辑结构的描述

我们是独立的个体 相当于物理结构的描述

3.什么是线性表

线性表是指在逻辑结构上是线性的,线性表有静态顺序表,动态顺序表,单链表,双链表等。

而顺序表就相当于数组,它的储存结构和数组相同,在逻辑结构和物理结构上都是线性的。静态顺序表就是一个数组,它的大小是在定义的时候就决定好的,不可在程序运行后改变,具有局限性。动态顺序表的内存是需要动态开辟的需要用到动态开辟函数,而通过realloc函数可以对它的内存根据需要调节,比较灵活,现在我们主要来学习一下动态顺序表。

静态顺序表定义:

typedef int SLDataType;typedef struct SeqList{SLDataType arr[100];int size;//记录arr数组中已储存元素的个数}SL;

动态顺序表定义:

typedef int SLDataType;typedef struct SeqList{SLDataType* arr;int size;//记录arr中已储存元素的个数int capacity;//记录arr申请的空间的大小}SL;

 4.动态顺序表

4.1.头文件(SeqLish.h)声明:

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<string.h>#include<errno.h>#define N 3typedef int SLDataType;//方便根据需要一次性替换为其他类型typedef struct SeqList{SLDataType* arr;int size;//记录arr中已储存元素的个数int capacity;//记录arr申请的空间的大小}SL;void CSH(SL* ps);//初始化void PrintSL(SL ps);//输出顺序表void FreeSL(SL* ps);//顺序表释放内存void CapSL(SL* ps);//根据需要判断是否增容void EndPush(SL* ps, SLDataType x);//尾插void HeadPush(SL* ps, SLDataType x);//头插void LocPush(SL* ps, int loc, SLDataType x);//指定位置插入void EndDelete(SL* ps);//尾删void HeadDelete(SL* ps);//头删void LocDelete(SL* ps, int loc);//指定位置删除int FindSL(SL* ps, SLDataType x);//数据查找

接下来我们依次来实现以上操作:

每一步为什么这么写都在注释中解释

4.2.初始化:

#include"SeqList.h"void CSH(SL* ps){ps->arr = NULL;//把它置为NULL防止野指针的出现ps->capacity = ps->size = 0;//或memset(ps, 0, sizeof(*ps));}

4.3.顺序表输出:

void PrintSL(SL* ps){assert(ps);//作用: 如果ps是空指针就报出警告并停止运行for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);//有效数据是储存在ps->arr的前p->size个中}}

4.4.顺序表内存释放:

void FreeSL(SL* ps){assert(ps);free(ps->arr);//动态申请的内存需要释放,否则会发生内存泄漏ps->arr = NULL;//释放内存后ps->arr依旧指向原空间,需要置空ps->size = ps->capacity = 0;}

4.5.判断扩容:

void CapSL(SL* ps){assert(ps);if (ps->size == ps->capacity)//若已储存元素的个数等于空间大小,说明内存不足{int Cap = ps->capacity == 0 ? N : ps->capacity * 2;//增容一般增两倍//但是当容量为0时,0乘2仍然等于0,所以分两种情况,N在头文件已定义。SLDataType* Sk = (SLDataType*)realloc(ps->arr, Cap * sizeof(SLDataType));//因为realloc函数在申请内存失败的时候会返回NULL(即会丢失原的数据)//所以用一个Sk来接受,再判断Sk是否为NULL,不为的话就可以赋给ps->arrif (Sk == NULL){perror("ralloc No");//这个函数可以用来打印错误信息,需要包含头文件<errno.h>exit(-1);//该函数用于结束程序的运行}ps->arr = Sk;ps->capacity = Cap;//更新空间大小}}

4.6.尾插:

void EndPush(SL* ps, SLDataType x){CapSL(ps);//只要是插入操作一定要判断是否扩容,后面就不在赘述ps->arr[ps->size] = x;ps->size++;}

4.7.头插:

void HeadPush(SL* ps, SLDataType x){CapSL(ps);for (int i = ps->size; i > 0; i--){    //把数据整体向后移,给头的位置留出空位ps->arr[i] = ps->arr[i - 1];}//或memmove(ps->arr+1, ps->arr, sizeof(SLDataType) * ps->size);ps->arr[0] = x;ps->size++;}

4.8.指定位置插入:

void LocPush(SL* ps, int loc, SLDataType x){CapSL(ps);for (int i = ps->size; i > loc; i--){ps->arr[i] = ps->arr[i - 1];}//或memmove(ps->arr + loc + 1, ps->arr + loc, sizeof(SLDataType) * (ps->size - loc+1));ps->arr[loc] = x;ps->size++;}

4.9.尾删:

void EndDelete(SL* ps){assert(ps);if (ps->size == 0){    //如果顺序表中没有元素就不能再删直接返回return;}ps->size--;}

4.10.头删:

void HeadDelete(SL* ps){assert(ps);for (int i = 0; i < ps->size - 1; i++){    //把后面的数据整体向前移将首元素覆盖ps->arr[i] = ps->arr[i + 1];}//或memmove(ps->arr, ps->arr + 1, sizeof(SLDataType) * (ps->size - 1));ps->size--;}

4.11.指定位置删除:

void LocDelete(SL* ps, int loc){assert(ps);assert(loc >= 0 && loc <= ps->size - 1);//不能超过数据范围for (int i = loc; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}//或memmove(ps->arr + loc, ps->arr + loc + 1, sizeof(SLDataType) * (ps->size - 1 - loc));ps->size--;}

4.12.数据查找:

int FindSL(SL* ps, SLDataType x){assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->arr[i]){return i;//找到返回它的下标}}return -1;//找不到返回-1}

5.原码:

SeqList.h文件

#define _CRT_SECURE_NO_WARNINGS 1#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<string.h>#include<errno.h>#define N 3typedef int SLDataType;typedef struct SeqList{SLDataType* arr;int size;//记录arr中已储存元素的个数int capacity;//记录arr申请的空间的大小}SL;void CSH(SL* ps);//初始化void PrintSL(SL* ps);//输出顺序表void FreeSL(SL* ps);//顺序表释放内存void CapSL(SL* ps);//根据需要判断是否增容void EndPush(SL* ps, SLDataType x);//尾插void HeadPush(SL* ps, SLDataType x);//头插void LocPush(SL* ps, int loc, SLDataType x);//指定位置插入void EndDelete(SL* ps);//尾删void HeadDelete(SL* ps);//头删void LocPush(SL* ps, int loc);//指定位置删除int FindSL(SL* ps, SLDataType x);//数据查找

SeqList.c 文件

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"void CSH(SL* ps){ps->arr = NULL;//把它置为NULL防止野指针的出现ps->capacity = ps->size = 0;//或memset(ps, 0, sizeof(*ps));}void PrintSL(SL* ps){assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}}void FreeSL(SL* ps){assert(ps);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;}void CapSL(SL* ps){assert(ps);if (ps->size == ps->capacity)//若已储存元素的个数等于空间大小,说明内存不足{int Cap = ps->capacity == 0 ? N : ps->capacity * 2;//增容一般增两被//但是当容量为0时0乘任何数都等于0,所以分两种情况,N在头文件已定义。SLDataType* Sk = (SLDataType*)realloc(ps->arr, Cap * sizeof(SLDataType));//因为realloc函数在申请内存失败的时候会返回NULL(即会丢失原的数据)//所以用一个Sk来接受,再判断Sk是否为NULL,不为的话就可以赋给ps->arrif (Sk == NULL){perror("ralloc No");//这个函数可以用来打印错误信息,需要包含头文件<errno.h>exit(-1);//该函数用于结束程序的运行}ps->arr = Sk;ps->capacity = Cap;//更新空间大小}}void EndPush(SL* ps, SLDataType x){CapSL(ps);//只要是插入操作一定要判断是否扩容后面就不在赘述ps->arr[ps->size] = x;ps->size++;}void HeadPush(SL* ps, SLDataType x){CapSL(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//或memmove(ps->arr+1, ps->arr, sizeof(SLDataType) * ps->size);ps->arr[0] = x;ps->size++;}void LocPush(SL* ps, int loc, SLDataType x){CapSL(ps);assert(loc >= 0 && loc < ps->size);for (int i = ps->size; i > loc; i--){ps->arr[i] = ps->arr[i - 1];}//或memmove(ps->arr + loc + 1, ps->arr + loc, sizeof(SLDataType) * (ps->size - loc));ps->arr[loc] = x;ps->size++;}void EndDelete(SL* ps){assert(ps);if (ps->size == 0){return;}ps->size--;}void HeadDelete(SL* ps){assert(ps);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}//或memmove(ps->arr, ps->arr + 1, sizeof(SLDataType) * (ps->size - 1));ps->size--;}void LocDelete(SL* ps, int loc){assert(ps);assert(loc >= 0 && loc < ps->size );for (int i = loc; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}//或memmove(ps->arr + loc, ps->arr + loc + 1, sizeof(SLDataType) * (ps->size - 1 - loc));ps->size--;}int FindSL(SL* ps, SLDataType x){assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->arr[i]){return i;}}return -1;}

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"int main(){SL sk;CSH(&sk);//HeadPush(&sk, 1);HeadPush(&sk, 2);HeadPush(&sk, 3);HeadPush(&sk, 4);//EndPush(&sk, 4);EndPush(&sk, 5);//HeadDelete(&sk);EndDelete(&sk);//LocPush(&sk, 1, 90);LocPush(&sk, 3, 10);//    LocDelete(&sk,2);    //PrintSL(&sk);int ret = FindSL(&sk, 90);printf("\n%d", ret);FreeSL(&sk);return 0;}

本文链接:https://www.kjpai.cn/news/2024-04-15/159111.html,文章来源:网络cs,作者:欧阳逸,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。

文章评论