关键词:
1.顺序表概念
顺序表是用以一段物理地址连续的存储单眼依次存储数据元素的线性结构,一般情况采用数组存储。在数组上完成数据的增删查改。顺序表一般分为静态顺序表和动态顺序表,这里主要讲如何实现动态顺序表。
2.顺序表分类
顺序表一般可以分为:静态顺序表,动态顺序表
2.1静态顺序表
静态顺序表:通过定长的数组存储。
优点:实现方便,只需要会用数组就能够写出简单的静态顺序表。
缺点:不够灵活,开辟的数组如果过大荣以浪费大量的空间,而开辟的数组过小也容易导致数据不够存放,适用于能预先知道所需空间,而且不用对内容频繁改动的情况(但实际上从实现角度来看,其实动态通讯录也没有麻烦太多,所以一般都是使用动态顺序表)
2.2动态顺序表
动态顺序表:使用动态开辟的数组存储
优点:泛用性好,能够适用于各种不同的环境,并且能根据所需存储内容多少,动态的分配空间,更加的灵活,且不容易存在空间浪费的情况,一般都是需要多少空间就能那多少空间用。
缺点:相较于顺序表更难实现,有一定的使用门槛。
3.顺序表实现
3.1顺序表结构
3.1.1静态顺序表结构
由于静态顺序表不是本篇文章的主要内容所以只是稍微提及一下结构。
#typedef SLDataType int
#define N 10
typedef struct SeqList
SLDataType arr[N];
int size;
SeqList;
SeqList:顺序表的英文缩写,本文提到的所有SeqList均为顺序表的意思
SLData Type:顺序表中要存放的数据类型,只需要改动typedef int SLDataType后面的内容就能改变所需要存放的数据类型,这里假定我们需要存放的是int类型的数据
N:所开辟数组大小
arr[N]: 为顺序表开辟的数组空间
size:顺序表已经使用的空间长度
3.2动态顺序表结构
typedef int SLDataType
typedef struct SeqList
SLData Type* a;
int size;
int capacity;
SeqList;
SeqList:顺序表的英文缩写,本文提到的所有SeqList均为顺序表的意思
SLData Type:顺序表中要存放的数据类型,只需要改动 typedef int SLDataType 后面的内容就能改变所需要存放的数据类型,这里假定我们需要存放的是int类型的数据
size:已用空间的大小
capacity:剩余空间的大小
3.3动态顺序表功能实现
文件:"SeqList.c"
3.3.1顺序表初始化
void SeqListInit(SeqList* ps) //顺序表初始化
assert(ps);
ps->a = NULL;
//初始指针指空
ps->size = 0;
//初始已用容量为零
ps->capacity = 0;
//初始可用容量为零
3.3.2顺序表空间检查
void CheckSeqList(SeqList* ps)
assert(ps);
int new_capacity = ps->capacity;
SLDataType* new_a = NULL;
//开辟两个临时变量以防止开辟失败影响原空间内容
if (ps->size == ps->capacity)
//如果已用空间与可用空间相等就开辟空间
(new_capacity == 0) ? (new_capacity = 4) : (new_capacity = 2 * new_capacity);
//当首次开辟直接开辟四个空间,否则开辟原空间的两倍
new_a = (SLDataType*)realloc(ps->a, new_capacity * sizeof(SLDataType));
//开辟原来空间的两倍
if (new_a == NULL)
printf("开辟空间失败");
exit(-1);
//new_a是空指针表示开辟失败
else
ps->capacity = new_capacity;
ps->a = new_a;
//开辟成功将空间和空间长度给SeqList
3.3.3顺序表销毁
void SeqListDestory(SeqList* ps) //顺序表销毁
assert(ps);
free(ps->a);
//释放开辟的空间
ps->a = NULL;
//指针指空
ps->size = 0;
//已用空间置零
ps->capacity = 0;
//可用空间置零
3.3.4打印顺序表
void SeqListPrint(SeqList* ps) //顺序表打印
assert(ps);
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->a[i]);
printf("\\n");
//将顺序表的内容依次打印
3.3.5顺序表头部插入数据
void SeqListPushFront(SeqList* ps, SLDataType x) //顺序表头插
assert(ps);
CheckSeqList(ps);
//检查顺序表是否已满
for (int i = ps->size -1 ; i >=0 ; i--)
ps->a[i+1] = ps->a[i];
//从后到前一次往后放一位
ps->a[0] = x;
//第一位为插入内容
ps->size++;
//已用空间+1
3.3.6顺序表尾部插入数据
void SeqListPushBack(SeqList* ps, SLDataType x) //顺序表尾插
assert(ps);
CheckSeqList(ps);
//检查顺序表是否已满
ps->a[ps->size] = x;
//在顺序表最后放入x
ps->size++;
//顺序表已用空间+1
3.3.7顺序表头部删除数据
void SeqListPopFront(SeqList* ps) //顺序表头删
assert(ps);
for (int i = 0; i < ps->size -1; i++)
ps->a[i] = ps->a[i + 1];
//将顺序表依次往前移
ps->size--;
//顺序表可用空间-1
3.3.8顺序表尾部删除数据
void SeqListPopBack(SeqList* ps) //顺序表尾删
assert(ps);
ps->size--;
//顺序表可用空间-1
3.3.9顺序表按值查找
int SeqListFind(const SeqList* ps, SLDataType x) //顺序表按值查找
assert(ps);
for (int i = 0; i < ps->size; i++)
if (ps->a[i] == x)
return i;
//依次与x匹配,找到返回所在位置
return -1;
//找不到返回-1
3.3.10顺序表按位插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x) //顺序表位插
assert(ps);
CheckSeqList(ps);
//检查顺序表是否已满
if (pos > ps->size)
printf("超出可检测范围");
exit(-1);
//要插入位置是否为合格
for (int i = ps->size - 1; i >= pos - 1; i--)
ps->a[i + 1] = ps->a[i];
//从后到前依次往后移一位
ps->a[pos - 1] = x;
//第pos-1位为插入内容
ps->size++;
//已用空间+1
3.3.11顺序表按位删除
void SeqListErase(SeqList* ps, int pos) //顺序表位删
assert(ps);
if (pos > ps->size)
printf("超出可检测范围");
exit(-1);
//要删除位置是否为合格为止
for (int i = pos - 1; i < ps->size - 1; i++)
ps->a[i] = ps->a[i+1];
//从前向后依次往前移一位
ps->size--;
//已用空间-1
3.4顺序表头文件
文件:"SeqList.h"
#pragma once //防止重复定义
typedef int SLDataType;
#include<stdio.h>
#include<stdlib.h>
#include<assert.h> //头文件,其他文件只用包含该文件
typedef struct SeqList //顺序表结构
SLDataType *a;
int size;
int capacity;
SeqList;
void SeqListInit(SeqList* ps); //顺序表初始
void SeqListDestory(SeqList* ps); //顺序表销毁
void SeqListPrint(SeqList* ps); //顺序表打印
void SeqListPushFront(SeqList* ps, SLDataType x); //顺序表头插
void SeqListPushBack(SeqList* ps, SLDataType x); //顺序表尾插
void SeqListPopFront(SeqList* ps); //顺序表头删
void SeqListPopBack(SeqList* ps); //顺序表头删
void SeqListInsert(SeqList* ps, int pos, SLDataType x); //顺序表位插
void SeqListErase(SeqList* ps, int pos); //顺序表位删
void CheckSeqList(SeqList* ps); //检查表容量
int SeqListFind(const SeqList* ps, SLDataType x); //顺序表查找
3.5顺序表功能测试
文件:"test.c"
#include"SeqList.h"
int main()
SeqList seqlist;
SeqListInit(&seqlist); //初始化顺序表--通过
SeqListPushFront(&seqlist, 3);
SeqListPushFront(&seqlist, 2);
SeqListPushFront(&seqlist, 1);
SeqListPushFront(&seqlist, 0);
SeqListPrint(&seqlist); //头插测试--通过
SeqListPushBack(&seqlist, 4);
SeqListPushBack(&seqlist, 5);
SeqListPushBack(&seqlist, 6);
SeqListPushBack(&seqlist, 7);
SeqListPrint(&seqlist); //尾插测试--通过
SeqListPopFront(&seqlist);
SeqListPopFront(&seqlist);
SeqListPrint(&seqlist); //头删测试--通过
SeqListPopBack(&seqlist);
SeqListPopBack(&seqlist);
SeqListPrint(&seqlist); //尾插测试--通过
printf("%d ", SeqListFind(&seqlist, 1));
printf("%d \\n", SeqListFind(&seqlist, 4));
SeqListPrint(&seqlist); //查找测试--通过
SeqListInsert(&seqlist, 3, 0);
SeqListInsert(&seqlist, 5, 0);
SeqListPrint(&seqlist); //位插测试--通过
SeqListErase(&seqlist, 3);
SeqListErase(&seqlist, 4);
SeqListPrint(&seqlist); //位删测试--通过
SeqListDestory(&seqlist); //销毁顺序表--通过
return 0;
✨写在最后
⏱笔记时间:2021_09_25
🌐代码:Gitee:朱雯睿 (zhu-wenrui) - Gitee.com
Github:https://github.com/Zero0Tw0
数据结构学习笔记——顺序存储结构实现栈(代码片段)
目录一、栈的相关知识二、顺序栈的定义三、顺序栈的初始化四、判断顺序栈是否为空栈五、判断顺序栈是否为满栈六、进栈(插入操作)七、出栈(删除操作)八、读取顺序栈顶元素九、顺序栈的建立一个简单... 查看详情
数据结构与算法学习笔记串,数组和广义表(代码片段)
数据结构与算法学习笔记(6)串、数组和广义表截图、笔记来自:王卓数据结构与算法文章目录数据结构与算法学习笔记(6)串、数组和广义表一.串1.串的定义2.串的类型定义、存储结构及其运算串的类型定义串的存储串的顺序存储结... 查看详情
数据结构学习笔记二线性表---顺序表篇(画图详解+代码实现)(代码片段)
本篇文章及后面几篇文章将会详细介绍和学习数据结构线性表中的顺序表和链表,这两种数据结构将是学习其他数据结构的基础。文章内容结构如下:①理论基础②画图详细讲解③代码实现④常见oj题刷题文章目录线性表... 查看详情
b站学习数据结构笔记=====>稀疏数组(代码片段)
学习来源–>传送门–>尚硅谷Java数据结构与java算法(Java数据结构与算法)程序==数据结构+算法数据结构包括线性结构与非线性的结构线性结构:特点;数据元素之间存在着一对一的线性关系;但是;线性结构又... 查看详情
线性表学习笔记(代码片段)
一、顺序表线性表的顺序存储结构,以下通过数组实现。常用操作:•构建、析构、求长度、判空、遍历•按位查找:判断查找位置,返回•按值查找:判断是否能找到,返回•插入:在表的第i(1<... 查看详情
数据结构与算法学习笔记栈和队列ⅰ(代码片段)
数据结构与算法学习笔记(5)栈和队列文章目录数据结构与算法学习笔记(5)栈和队列一.栈和队列的定义和特点1.栈的定义和特点相关概念示意图栈与一般线性表的不同2.队列的定义和特点相关概念二.案例引入1.栈的典型案例进制转... 查看详情
数据结构学习笔记——顺序存储结构实现串(代码片段)
目录一、串的相关概念二、定长顺序存储和变长分配存储三、串的初始化四、判断串是否为空五、串的建立六、串的遍历输出七、求串的长度八、求串的子串九、插入子串十、删除子串十一、连接子串十二、比较子串十三、串的... 查看详情
数据结构学习笔记——顺序表的基本操作(超详细最终版+++)建议反复看看ヾ(≧▽≦*)o(代码片段)
目录前言一、顺序表的相关知识点二、顺序表的定义三、顺序表的初始化四、顺序表的建立五、顺序表的输出六、顺序表的逆序输出七、顺序表的插入操作八、顺序表的删除操作九、顺序表的按位和按值查找基本操作的完整代码... 查看详情
数据结构学习笔记(单链表单循环链表带头双向循环链表)的增删查改排序等)(代码片段)
数据结构学习笔记(单链表、单循环链表、带头双向循环链表)的增删查改排序等链表的概念及结构链表结构的分类链表的常用操作实现无头单链表单链表补充单循环链表带头双向循环链表链表的概念及结构概念:链... 查看详情
数据结构学习笔记(单链表单循环链表带头双向循环链表)的增删查改排序等)(代码片段)
数据结构学习笔记(单链表、单循环链表、带头双向循环链表)的增删查改排序等链表的概念及结构链表结构的分类链表的常用操作实现无头单链表单链表补充单循环链表带头双向循环链表链表的概念及结构概念:链... 查看详情
数据结构学习笔记(栈队列)整理与总结(代码片段)
数据结构学习笔记(栈、队列)整理与总结栈栈结构之顺序栈的基本介绍顺序栈的常用操作栈结构之链栈的基本介绍链栈的常用操作队列顺序队列(循环队列)链队列整体代码栈队列头文件和主函数栈栈的概念... 查看详情
学习笔记--hbase(代码片段)
HBase和HDFSHDFSHBaseHDFS是适于存储大容量文件的分布式文件系统。HBase是建立在HDFS之上的数据库。HDFS不支持快速单独记录查找。HBase提供在较大的表快速查找它提供了高延迟批量处理;没有批处理概念。它提供了数十亿条记录低延迟... 查看详情
数据结构与算法——学习笔记汇总(代码片段)
...号匹配问题》6.使用栈《解决逆波兰表达式求值问题》7.数据结构与算法-自定义二叉树API8.递归-反转单链表-图解鸡汤https://www.bloghut.cn/questionBank链接:面试题库视频推荐java版尚硅谷Java数据 查看详情
数据结构学习总结线性表之顺序表(代码片段)
通过前面的学习知道,具有“一对一”逻辑关系的数据,最佳的存储方式是使用线性表。那么,什么是线性表呢?线性表,全名为线性存储结构。使用线性表存储数据的方式可以这样理解,即“把所有数据用一... 查看详情
数据结构学习笔记——广义表以及树和二叉树的基本知识(代码片段)
目录一、广义表二、树和森林三、二叉树四、平衡二叉树五、二叉树的存储结构(一)二叉树的顺序存储结构(二)二叉树的链式存储结构六、二叉树的遍历七、二叉树的实现代码(链式存储)(一... 查看详情
数据结构学习笔记——广义表树和二叉树的基本知识(代码片段)
目录一、广义表二、树和森林三、二叉树(一)概念(二)性质1、二叉树的性质2、满二叉树的性质3、完全二叉树的性质四、平衡二叉树五、二叉树的存储结构(一)二叉树的顺序存储结构(二)... 查看详情
数据结构与算法学习笔记线性表ⅱ(代码片段)
数据结构与算法学习笔记(4)线性表Ⅱ文章目录数据结构与算法学习笔记(4)线性表Ⅱ一.线性表的链式表示和实现1.链式存储结构情境引入2.链式存储相关术语结点链表单链表、双链表、循环链表头指针、头结点和首元结点单链表的... 查看详情
数据结构与算法学习笔记查找(代码片段)
数据结构与算法学习笔记(9)查找文章目录数据结构与算法学习笔记(9)查找一.查找的基本概念二.线性表的查找1.顺序查找应用范围算法基本形式改进算法特点2.折半查找(二分查找)非递归算法递归算法算法分析判定树优缺点3.分块... 查看详情