数据结构-顺序表详解(看这篇就足够了,哈哈哈)

简介: 数据结构-顺序表详解(看这篇就足够了,哈哈哈)
本篇代码都是基于VS所写,在其他编译器运行可将#define _CRT_SECURE_NO_WARNINGS该行注释,某些语句或许在某些低版本的GCC编译器上不能运行。

哈喽,everybody!感谢各位同胞的阅览,希望大家在评论区多多发表意见!

顺序表

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代码测试

#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;
 }

可根据自己要求进行数据检测处理!

结束语

这是小编的第一篇博客,写的不是很好,望各位友友多多包涵,小编会努力学习,不断进步!!!

最后还是感谢各位友友的支持!!!

目录
相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
65 3
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
35 6
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
26 3
|
2月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
32 2
|
2月前
|
存储
数据结构(顺序表)
数据结构(顺序表)
27 0
|
2月前
|
存储 算法
【数据结构】新篇章 -- 顺序表
【数据结构】新篇章 -- 顺序表
16 0
|
2月前
|
存储 测试技术
探索数据结构:顺序表的实现与应用
探索数据结构:顺序表的实现与应用
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
134 9