临沂做网站首选,做网站的公司周年活动,德山经济开发区建设局网站,公司局域网设计方案数据结构#xff1a;顺序表详解 一、 线性表二、 顺序表概念及结构1. 静态顺序表#xff1a;使用定长数组存储元素。2. 动态顺序表#xff1a;使用动态开辟的数组存储。三、接口实现1. 创建2. 初始化3. 扩容4. 打印5. 销毁6. 尾插7. 尾删8. 头插9. 头删10. 插入任意位置数据… 数据结构顺序表详解 一、 线性表二、 顺序表概念及结构1. 静态顺序表使用定长数组存储元素。2. 动态顺序表使用动态开辟的数组存储。三、接口实现1. 创建2. 初始化3. 扩容4. 打印5. 销毁6. 尾插7. 尾删8. 头插9. 头删10. 插入任意位置数据11. 删除任意位置数据12. 查找13. 修改 四所有代码 一、 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的。 线性表在物理上存储时通常以数组和链式结构的形式. 二、 顺序表概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为:
1. 静态顺序表使用定长数组存储元素。 2. 动态顺序表使用动态开辟的数组存储。 三、接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。
基本增删查改接口
//对数据管理 --- 增删查改
void SLInit(SL* ps); //初始化
void SLDestory(SL* ps); //释放
void SLPrint(SL* ps); //打印
void SLCheakCapacity(SL* ps); //检查容量 -- 扩容//头插头删 尾插尾删
void SLPushBack(SL* ps, SLDateType x); //尾插
void SLPopBack(SL* ps); //尾删
void SLPushFront(SL* ps, SLDateType x);//头插
void SLPopFront(SL* ps); //头删//返回下标没找到返回-1
int SLFind(SL* ps, SLDateType); //查找元素返回下标//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x); //任意位置插入
//在pos位置删除x
void SLErase(SL* ps, int pos); //任意位置删除void SLModify(SL* ps, int pos, SLDateType x);//修改 1. 创建
由于在实际工程中项目的实现都是采用模块化进行实现的。所以在此处博主也采用了模块化的方式进行实现。
#pragma once#include stdio.h
#include assert.h
#include stdlib.h//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;//指向动态开辟的数组int size; //有效数据的个数int capacity;//容量空间的大小
}SL; 为了后续好修改类型数据在此采用typedef将结构体类型struct SeqList 重新命名为SL。 在实际开发过程中为了开发人员更好的输入数据一般我们会将输入数据的数据类型重命名为SLDateType。在本篇博客中采用typedef将其数据类型int重命名为SLDateType 2. 初始化 初始化时理论上我们只需要开辟一个空间并置为空指针并将结构体中的数据全部初始化为0即可。 但在实际开发过程中我们一般会开辟一定大小的空间本篇博客开4个空间但具体开多少各位可自行选择。 代码实现
void SLInit(SL* ps)
{assert(ps);ps-a (SLDateType*)malloc(4 * sizeof(SLDateType));//开辟4个空间if (ps-a NULL){perror(malloc);exit(-1);}//开辟成功ps-capacity 4;//开辟多少空间容量变为多少ps-size 0;
}3. 扩容 在后续我们插入数据时已开辟容量可能已经无法满足需求了。这是就需要扩容。 那一次扩到多少呢 在实际开发过程中我们一般是扩到原有空间的两倍。当然你也可以开1000倍只要后台空间足够大 代码实现
void SLCheakCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){//开辟空间X2SLDateType* tmp (SLDateType*)realloc(ps-a, ps-capacity * sizeof(SLDateType) * 2);if (tmp NULL){perror(realloc);exit(-1);}//开辟成功ps-a tmp;ps-capacity * 2;}
}4. 打印 上述函数定义完成后我们通常需要测试打印以下相关数据来判断相关函数定义是否成功. 代码实现
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}5. 销毁 由于上述空间是动态开辟的。所以当我们使用完时要及时销毁释放空间。 代码实现
void SLDestory(SL* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}6. 尾插
尾插在尾部插入一个数据。 但是在数据的尾部插入一个数据时我们需要考虑一个问题原有空间是否可以容纳新的数据是否需要扩容。 所以我们在插入数据时要先调用 SLCheakCapacity函数来检查是否需要扩容。 代码实现
void SLPushBack(SL* ps, SLDateType x)
{assert(ps);SLCheakCapacity(ps);//检查是否需要扩容ps-a[ps-size] x;ps-size;
}7. 尾删
尾删删除尾部最后的一个元素。 但尾删同样也要考虑一个问题空间中是否还有数据给我们删除。 所以在进行尾删时我们可以采用assert函数断言空间中还有数据。 代码实现
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size 0);//断言空间中还有元素ps-size--;//下标减1
}在删除数据时我们不用将原有数据删除。只需要下标减1即可。 原因在于我们时根据下标来使用数据的当下标减1后尾部最后一个数据便无法进行访问。 Tips: 越界是不一定报错的系统对越界的检查是一种设岗抽查。以VS2022为例微软公司在数据的开始前和结尾后的一小段空间设有一些特殊值。当程序结束或内存空间释放时编译器就会检查这些值是否发生改变, 从而触发程序的保护机制。但如果这些值没有发生改变即使发生越界访问程序也不会报错。就像如果你酒驾交警只在二环设关卡但只要你不去二环你就没事不会被发现。每个编译器略有差异 8. 头插
头插在数据最开始地方插入数据。 同样头插也要调用 SLCheakCapacity函数来检查空间是否足够是否需要扩容。 代码实现
void SLPushFront(SL* ps, SLDateType x)
{assert(ps);SLCheakCapacity(ps);//检查是否需要扩容//移动数据int i ps-size-1;while (i 0){ps-a[i 1] ps-a[i];i--;}//移动数据完成插入元素。同时有效个数加1ps-a[0] x;ps-size;
} 9. 头删
头删删除数据最开始的元素。 思路和头插类似只要下标从1开始所有数据依次向前移动1位再把有限个数减1即可。 同时头删也需要使用assert函数断言原有空间中还有数据可以删除。 代码实现
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size 0);//空间中还有数据可以删除//移动数据for (int begin 1; begin ps-size; begin){ps-a[begin - 1] ps-a[begin];}ps-size--;//有效个数减1
}10. 插入任意位置数据
由于顺序表要求数据是连续存放的,所以我们只需要找到输入位置的下标pos即可。 【代码思路】首先我们要检查输入下标是否合法是有效下标并检查是否有足够空间来容纳新数据是否需要扩容。之后从输入的数据下标开始所有元素向后移动一位并把新数据插入到下标为pos处即可。 代码实现
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);//检查下标是否合法SLCheakCapacity(ps); //检查空间是否足够//移动数据int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
}11. 删除任意位置数据 【代码思路】和插入任何位置数据思想类似。首先我们要检查输入下标pos是否合法。之后从输入下标开始后一个元素拷贝到前一个元素空间。 代码实现
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);//下标是否合法//移动数据int begin pos1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
} 12. 查找 【代码思路】要查找某个元素。由于这里只是最简单的查找我们直接暴力查找遍历整个数组返回下标即可。更为复杂的数据查找会有更高阶的数据结构来实现。 代码实现
int SLFind(SL* ps, SLDateType x)
{assert(ps);for (int i 0; i ps-size; i){if (x ps-a[i])return i;}return -1;
}13. 修改 【代码思路】 要实现修改数据我们只需要先判断输入下标是否合法。在将对应下标数据进行修改即可。 代码实现
void SLModify(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);ps-a[pos] x;
}四所有代码
SeqList.h源文件
#include assert.h
#include stdlib.h//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SL;//对数据管理 --- 增删查改
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);
void SLCheakCapacity(SL* ps);//头插头删 尾插尾删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);//返回下标没找到返回-1
int SLFind(SL* ps, SLDateType);//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x);
//在pos位置删除x
void SLErase(SL* ps, int pos);void SLModify(SL* ps, int pos, SLDateType x);
SeqList.c头文件
#define _CRT_SECURE_NO_WARNINGS#include SeqList.hvoid SLInit(SL* ps)
{assert(ps);ps-a (SLDateType*)malloc(4 * sizeof(SLDateType));if (ps-a NULL){perror(malloc);exit(-1);}//开辟成功ps-capacity 4;ps-size 0;
}void SLDestory(SL* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}void SLCheakCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){SLDateType* tmp (SLDateType*)realloc(ps-a, ps-capacity * sizeof(SLDateType) * 2);if (tmp NULL){perror(realloc);exit(-1);}ps-a tmp;ps-capacity * 2;}
}void SLPushBack(SL* ps, SLDateType x)
{assert(ps);/*SLCheakCapacity(ps);ps-a[ps-size] x;ps-size;*/SLInsert(ps, ps-size, x);
}void SLPopBack(SL* ps)
{assert(ps);assert(ps-size 0);/*ps-size--;*/SLErase(ps, 0);
}void SLPushFront(SL* ps, SLDateType x)
{assert(ps);SLCheakCapacity(ps);//移动数据/*int i ps-size-1;while (i 0){ps-a[i 1] ps-a[i];i--;}ps-a[0] x;ps-size;*/SLInsert(ps, 0, x);
}void SLPopFront(SL* ps)
{assert(ps);assert(ps-size 0);/*for (int begin 1; begin ps-size; begin){ps-a[begin - 1] ps-a[begin];}ps-size--;*/SLErase(ps, 0);
}int SLFind(SL* ps, SLDateType x)
{assert(ps);for (int i 0; i ps-size; i){if (x ps-a[i])return i;}return -1;
}void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheakCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int begin pos1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}void SLModify(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);ps-a[pos] x;
}
