哈喽,everybody!感谢各位同胞的阅览,希望大家在评论区多多发表意见!
本篇代码都是基于VS所写,在其他编译器运行可将#define _CRT_SECURE_NO_WARNINGS该行注释,某些语句或许在某些低版本的GCC编译器上不能运行。
顺序表
1.顺序表的概念及结构
1.1 线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,
线性表在物理上存储时,通常以数组和链式结构的形式存储。
案例:蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合
顺序表的底层是数组,故顺序表的物理结构是连续的。
顺序表是线性表的一种,逻辑结构是连续的。
2.顺序表分类
•2.1顺序表和数组的区别
◦ 顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口
• 2.2顺序表分类
◦ 静态顺序表
概念:使用定长数组存储元素
静态顺序表缺陷:空间给少了不够用,给多了造成空间浪费.
struct SeqList{//sequence 顺序的
int arr[100];//定长数组
int size;//顺序表当前有效的数据个数
}SL;
◦ 动态顺序表
struct SeqList{
int *arr;
int size;//有效的数据个数
int capacity;//空间大小
}SL;
可增容
3.动态顺序表的实现
#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);
以上为提纲
下面顺序表的实现采用项目格式
项目设计: 1.头文件 .h 顺序表结构 声明顺序表的方法 2 .c文件 实现顺序表的方法
4.顺序表具体实现(主要为动态)
4.1头文件
#pragma once
//顺序表的创建
//静态
/*
struct seqList{
int arr[100];定长数组
int size; 数量
}
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int datatype;//方便以后改数据类型
//动态顺序表--按需申请空间
typedef struct seqList {
datatype* arr;
int size;
int capacity;//容量
}SL;
//初始化和销毁,数据打印
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL s);
//扩容
void CheckCapacity(SL* ps);
//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL* ps, datatype x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, datatype x);
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据/数据查询
void SLInsert(SL* ps, int pos, datatype x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, datatype x);
4.2相关函数实现
#define _CRT_SECURE_NO_WARNINGS
#include"seqList.h"
//初始化
void SLInit(SL* ps) {
ps->arr = NULL;
ps->size = ps->capacity = 0;//初始化也可赋值,但是后续操作会改变,思路都是一样的。
}
//销毁
void SLDestroy(SL* ps) {
if (ps->arr) {//等价于if(ps->arr!=NULL)
free(ps->arr);
ps->arr = NULL;
}
ps->size = ps->capacity = 0;
}
//空间检查
void CheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
int newcapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
//创建临时数组,判断是否创建为空导致数据丢失
datatype* tem = (datatype*)realloc(ps->arr, newcapacity * sizeof(datatype));
if (tem == NULL) {
perror("realloc fail!");
exit(1);//直接退出
}
ps->arr = tem;
ps->capacity = newcapacity;
}
}
//尾插
void SLPushBack(SL* ps, datatype x) {
//ps->arr[ps->size] = x;
//++ps->size;
//判断空间是否足够
assert(ps);
CheckCapacity(ps);
ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, datatype x) {
assert(ps);
CheckCapacity(ps);
//让顺序表中已有的数据整体往后挪一位
for (int i = ps->size; i > 0; i--) {
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
//输出
void SLPrint(SL s) {
for (int i = 0; i < s.size; i++) {
printf("%d ", s.arr[i]);
}
printf("\n");
}
//尾删
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
--ps->size;
}
//头删
void SLPopFront(SL* ps) {
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++) {
ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
}
ps->size--;
}
//指定位置前插入数据
void SLInsert(SL* ps, int pos, datatype x) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
for (int i = ps->size; i > pos; i--) {
ps->arr[i] = ps->arr[i - 1];//arr[size]=arr[size-1]
}
ps->arr[pos] = x;
ps->size++;
}
//指定位置删除
void SLErase(SL* ps, int pos) {
assert(ps);
assert(ps->size);
for (int i = pos; i < ps->size - 1; i++) {
ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
}
ps->size--;
}
//找寻数据
int SLFind(SL* ps, datatype x) {
assert(ps);
for (int i = 0; i < ps->size; i++) {
if (ps->arr[i] == x) {
return i;
}
}
return -1;
}
4.3代码测试文章来源:https://www.toymoban.com/news/detail-860886.html
#define _CRT_SECURE_NO_WARNINGS
#include"seqList.h"
void test1() {
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(sl);//12345
SLInsert(&sl, 0, 99);
SLInsert(&sl, sl.size, 66);
//SLErase(&sl, 3);
//SLErase(&sl, 0);
//SLErase(&sl, 4);
SLPrint(sl);
SLPushFront(&sl, 6);
SLPushFront(&sl, 6);
SLPrint(sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPopFront(&sl);
//SLPopFront(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(sl);
int find= SLFind(&sl,4);
if (find < 0) {
printf("没有找到!");
}
else
printf("找到了,数组下标为%d.,第%d个元素.", find,find+1);
SLDestroy(&sl);
}
int main() {
test1();
return 0;
}
可根据自己要求进行数据检测处理!文章来源地址https://www.toymoban.com/news/detail-860886.html
到了这里,关于数据结构-顺序表详解(看这篇就足够了,哈哈哈)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!