顺序表——“数据结构与算法”

news/2025/1/12 21:57:26/

各位CSDN的uu们你们好呀，今天小雅兰的内容是数据结构与算法里面的顺序表啦，在我看来，数据结构总体上是一个抽象的东西，关键还是要多写代码，下面，就让我们进入顺序表的世界吧

线性表

顺序表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表就是数组，但是在数组的基础上，它还要求数据是从头开始连续存储的，不能跳跃间隔 

顺序表一般可以分为：

 静态顺序表：使用定长数组存储元素。

#define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#include"SeqList.h"
typedef int SLDateType;
typedef struct SeqList
{SLDateType arr[N];//定长数组size_t size;//表示数组中存储了多少数据
}SL;

 动态顺序表：使用动态开辟的数组存储。

#define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#include"SeqList.h"
typedef int SLDateType;
typedef struct SeqList
{SLDateType* arr;//指向动态开辟的数组size_t size;//表示数组中存储了多少数据size_t capicity;//数组实际能存储数据的空间容量是多大
}SL;

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。  

在这里，所有函数命名风格都是跟着STL走的，方便小雅兰日后的学习！！！ 

顺序表的初始化：

void SeqListInit(SL* ps)//顺序表的初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

注意：在这里，不可以使用传值调用的方式，只能使用传址调用的方式

void SeqListInit(SL ps)//顺序表的初始化
{ps.arr = NULL;ps.size = ps.capacity = 0;
}

万万不能使用这样的方式初始化，因为：在函数传参的时候，形参是实参的一份临时拷贝，对形参的修改并不会影响实参

 顺序表的打印：

void SeqListPrint(SL* ps)//顺序表的打印
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

扩容：

void SeqListCheckCapacity(SL* ps)//检查空间，如果满了，进行扩容
{//如果没有空间或者空间不足，那么我们就扩容if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));if (tmp == NULL){printf("realloc fail!\n");exit(-1);}ps->arr = tmp;ps->capacity = newcapacity;}
}

顺序表销毁：

void SeqListDestroy(SL* ps)//顺序表销毁
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}

尾插：

void SeqListPushBack(SL* ps, SLDateType x)//尾插
{SeqListCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;
}

尾删：

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

 头插：

void SeqListPushFront(SL* ps, SLDateType x)//头插
{SeqListCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}

头删：

void SeqListPopFront(SL* ps)//头删
{assert(ps->size > 0);//挪动数据int begin = 0;while (begin < ps->size-1){ps->arr[begin] = ps->arr[begin+1];++begin;}ps->size--;
}
另一种写法： 
void SeqListPopFront(SL* ps)//头删
{assert(ps->size > 0);//挪动数据int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];++begin;}ps->size--;
}

 顺序表查找：

//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

 指定pos下标位置插入：

// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{温柔的写法//if (pos > ps->size || pos < 0)//{//	printf("pos invalid!\n");//}//粗暴的写法assert(pos <= ps->size || pos >= 0);SeqListCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;ps->size++;
}

 然后，写出了这个函数的功能之后，我们发现：可以对之前写的头插和尾插搞一些事情，下面，我们开始搞事情！！！

头插和尾插：

void SeqListPushBack(SL* ps, SLDateType x)//尾插
{SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{SeqListInsert(ps, 0, x);
}

 删除pos位置的数据：

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

写出这个函数的功能之后，我们又可以搞事情啦！！！

头删和尾删：

void SeqListPopBack(SL* ps)//尾删
{SeqListErase(ps, 0);
}
void SeqListPopFront(SL* ps)//头删
{SeqListErase(ps, ps->size - 1);
}

菜单：

void menu()
{printf("#############################################\n");printf("\n");printf("###################1.头插#####################\n");printf("\n");printf("###################2.头删#####################\n");printf("\n");printf("###################3.尾插######################\n");printf("\n");printf("###################4.尾删######################\n");printf("\n");printf("###################5.打印#####################\n");printf("\n");printf("###################0.exit#####################\n");printf("\n");printf("##############################################\n");
}

其实，最好不要一上来就写菜单，先写单元测试，菜单不方便调试

 测试菜单函数：

void MenuTest()
{SL s1;SeqListInit(&s1);int input = 0;int x;while (input != -1){menu();scanf("%d", &input);switch (input){case 1:printf("请输入你要头插的数据，以-1结束：");while (x != -1){SeqListPushFront(&s1, x);scanf("%d", &x);}break;case 2:SeqListPopFront(&s1);break;case 3:printf("请输入你要尾插的数据，以-1结束：");while (x != -1){SeqListPushBack(&s1, x);scanf("%d", &x);}break;case 4:SeqListPopBack(&s1);break;case 5:SeqListPrint(&s1);break;case 0:printf("退出程序\n");break;default:printf("输入错误，请重新输入\n");}}
}

源代码如下：

SeqList.h的内容：

#pragma once
#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<assert.h>
#define N 7
typedef int SLDateType;
//顺序表的动态存储
typedef struct SeqList
{SLDateType* arr;//指向动态开辟的数组size_t size;//表示数组中存储了多少数据size_t capacity;//数组实际能存储数据的空间容量是多大
}SL;
//基本增删查改接口
void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void SeqListCheckCapacity(SL* ps);//检查空间，如果满了，进行扩容
void SeqListDestroy(SL* ps);//顺序表销毁
void SeqListPushBack(SL* ps, SLDateType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDateType x);//头插
void SeqListPopFront(SL* ps);//头删
//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x);
//顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x);
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos);

SeqList.c的内容：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SL* ps)//顺序表的初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SeqListPrint(SL* ps)//顺序表的打印
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
void SeqListCheckCapacity(SL* ps)//检查空间，如果满了，进行扩容
{//如果没有空间或者空间不足，那么我们就扩容if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));if (tmp == NULL){printf("realloc fail!\n");exit(-1);}ps->arr = tmp;ps->capacity = newcapacity;}
}
void SeqListDestroy(SL* ps)//顺序表销毁
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}
void SeqListPushBack(SL* ps, SLDateType x)//尾插
{SeqListCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;
}
void SeqListPopBack(SL* ps)//尾删
{assert(ps->size > 0);ps->size--;
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{SeqListCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}
void SeqListPopFront(SL* ps)//头删
{assert(ps->size > 0);//挪动数据int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];++begin;}ps->size--;
}
//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}
// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{温柔的写法//if (pos > ps->size || pos < 0)//{//	printf("pos invalid!\n");//}//粗暴的写法assert(pos <= ps->size || pos >= 0);SeqListCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;ps->size++;
}
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{assert(pos < ps->size || pos >= 0);int begin = pos + 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];++begin;}ps->size--;
}

好啦，小雅兰今天的内容就到这里啦，数据结构的的确确是一个麻烦的东西，还要加油呀！！！

 


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

相关文章

看看CabloyJS是如何异步加载并执行go wasm模块的

看看CabloyJS是如何异步加载并执行go wasm模块的

介绍 CabloyJS提供了一个内置模块a-wasmgo&#xff0c;将go wasm模块的异步加载运行机制进行了封装&#xff0c;使我们可以非常方便的在CabloyJS项目中引入go wasm&#xff0c;从而支持更多的业务场景开发 下面&#xff0c;我们以测试模块test-party为例&#xff0c;演示引入…
阅读更多...
合并两个有序链表（精美图示详解哦）

合并两个有序链表（精美图示详解哦）

全文目录引言合并两个有序链表题目描述方法一&#xff1a;将第二个链表合并到第一个思路实现方法二&#xff1a;尾插到哨兵位的头节点思路实现总结引言 在前面两篇文章中&#xff0c;我们介绍了几道链表的习题&#xff1a;反转链表、链表的中间结点、链表的倒数第k个结点&…
阅读更多...
基于Vue+Vue-cli+webpack搭建渐进式高可维护性前端实战项目

基于Vue+Vue-cli+webpack搭建渐进式高可维护性前端实战项目

本文是专栏《手把手带你做一套毕业设计毕业设计》的实战第一篇&#xff0c;将从Vue脚手架安装开始&#xff0c;逐步带你搭建起一套管理系统所需的架构。当然&#xff0c;在默认安装完成之后&#xff0c;会对文件目录进行初步的细化拆分&#xff0c;以便后续功能迭代和维护所用。…
阅读更多...
【C++】类与对象（二）

【C++】类与对象（二）

文章目录1、类的6个默认成员函数2、构造函数3、析构函数4、拷贝构造5、赋值运算符重载运算符重载赋值运算符重载1、类的6个默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&#…
阅读更多...
【Java基础】HashMap的底层数据结构是怎样的？

【Java基础】HashMap的底层数据结构是怎样的？

HashMap就是以Key-Value的方式进行数据存储的一种数据结构。 HashMap在jdk1.7之前和jdk1.8之后的底层数据结构是不一样的。 在jdk1.7之前是数组链表的形式&#xff0c;并通过entry节点保存key和value值&#xff1b;当Hash冲突比较严重的时候&#xff0c;在数组上形成的链表就会…
阅读更多...
MySQL——插入加锁/唯一索引插入死锁/批量插入效率

MySQL——插入加锁/唯一索引插入死锁/批量插入效率

本篇主要介绍MySQL跟加锁相关的一些概念、MySQL执行插入Insert时的加锁过程、唯一索引下批量插入可能导致的死锁情况&#xff0c;以及分别从业务角度和MySQL配置角度介绍提升批量插入的效率的方法&#xff1b;MySQL跟加锁相关的一些概念在介绍MySQL执行插入的加锁过程之前&…
阅读更多...
Leetcode. 21 合并两个有序列表

Leetcode. 21 合并两个有序列表

尾插 核心思路&#xff1a;依次比较 &#xff0c;取经过比较后较小值进行尾插 cur1 指向list1 ,cur 2指向list2 ,当cur1走完list1 或者cur2 走完list2 后停止 如果cur1走完list1 ,可以将cur2 整个拿下来尾插 如果cur2走完list2 ,可以将cur1 整个拿下来尾插 特殊情况 &#xff1…
阅读更多...
SAP 更改物料基本计量单位

SAP 更改物料基本计量单位

前言部分 在SAP中物料创建后&#xff0c;一旦发生业务&#xff0c;其基本计量单位便很难修改。由于单位无法满足业务要求&#xff0c;往往会要求新建一个物料替代旧物料。这时候除了要将旧物料上所有的未清业务删除外&#xff0c;还需要替换工艺与BOM中的旧物料。特别是当出现旧…
阅读更多...
最新文章

Copyright @ 2022~2023