【数据结构】——顺序表介绍（独家介绍，小白必看！！）

article/2025/8/22 5:15:50

重点和易错点都用彩笔标记出来了，放心食用！！

数据结构分为线性表和非线性表，今天我们要学习的顺序表就是线性表中的一个小类。那么，何为线性表，线性表是指n个具有相同性质的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列、字符串等等。注意，线性表的物理结构不一定是线性的，它在逻辑结构上一定是线性的（这个很好理解，等我们学完顺序表和单链表这对黄金搭档，就明白这句话的含义了）

今天我们重点讲解顺序表，顺序表是线性表，顺序表在逻辑结构和物理结构上都是线性的。

 1、概念及结构

顺序表（SeqList）：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构（连续存储数据，不能跳跃）。

一般我们用数组存储顺序表，在数组上完成数据的增删查改。

顺序表分为两种类型：

//静态顺序表
#define N 7
typedef int SLDateType;
typedef struct SeqList
{SLDateType array[N];  //定长数组size_t size;                  //有效数据长度，size_t是无符号整形
}SeqList;//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{SLDateType* array;  //指向动态开辟的数组size_t size;  //数据中存储的数据size_t capacity;   //数组的容量
}SeqList;

 我建议用动态顺序表，比起静态顺序表，动态的更加好调整顺序表的大小。接下来，我也会以动态顺序表为例，介绍如何实现动态顺序表的增删查改。

2、接口实现

2.1 功能要求

我们要实现以下功能

//顺序表初始化
void SeqListInit(SeqList* psl);  //psl  p指针，sl顺序表
//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl,SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos,SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x);

2.2 功能实现

2.2.1 打印顺序表

这里提一嘴，我建议在每写一个功能就测试一下，千万不要把大部分功能写完再统一测试，那样你的Bug可能会99+（别问我为什么知道）。

//打印顺序表
void SeqListPrint(SeqList* psl)
{assert(psl);for(int i=0;i<psl->size;i++){printf("%d ", psl->array[i]);}printf('\n');
}

2.2.2 顺序表初始化

链表初始化没什么好说的，我直接上代码了。

void SeqListInit(SeqList*psl)
{assert(psl);   //断言psl是不是空指针psl->array=NULL;psl->size=psl->capacity=0;
}

2.2.3 检查顺序表的空间，增容

思路讲解：

  1. 判断顺序表空间是否满了，也就是判断是否需要增容就是要看psl->size==psl->capacity?增容：不增容。
  2. 用条件运算符来确定增容后的新空间的大小，如果是仍未存储数据的新链表，则先让链表的容量为4（这个数值可以随便设置）；如果已经存储了数据，但容量不够了，我们就让链表的空间每次增加一倍，也就是变成原来的两倍（可能有人会疑惑，为什么是两倍，其实这个也是为了减少数据的浪费，变成2倍比较保守）。
  3. 在扩容时用realloc，当realloc的第一个参数为0时，其效果等同于malloc，用realloc可以完美实现最初开辟空间和增容的功能。
  4. 检查tmp是否为空，也就是检查是否成功开辟了新的空间，非空则把tmp赋值给psl->array，最后千万不要忘记更改capacity的值。
//检查容量，增容
void CheckCapacity(SeqList* psl)
{assert(psl);if (psl->size == psl->capacity){size_t newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);//这里用realloc非常好SLDateType* tmp = (SLDateType*)realloc(psl->array, psl->capacity * sizeof(SLDateType));if (tmp == NULL){perror("realloc：");return;}psl->array = tmp;psl->capacity = newcapacity;}
}

2.2.4 顺序表尾插

这里就需要注意在尾插前检查容量，并且不要忘记psl->size++。

//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x)
{assert(psl);CheckCapacity(psl);psl->array[psl->size] = x;//别忘记让psl->size+1psl->size++;
}

2.2.5 顺序表尾删

注意：不管是进行头删还是进行尾删，我们都要检查psl->size是否大于0，我也提供了两种检查的方式，选其一即可。

//顺序表尾删
void SeqListPopBack(SeqList* psl)
{assert(psl);//千万不要忘记检查psl->size是否大于0//检查方式一：温柔的检查/*if (psl->size == 0)return;*///检查方式二：暴力的检查assert(psl->size>0);psl->size--;
}

2.2.6 顺序表头插

这个也没什么好说的，直接上代码。

void SeqListPushFront(SeqList*psl, SLDateType x)
{assert(psl);CheckCapacity(psl);for (int i = psl->size;i>0; i++){psl->array[i] = psl->array[i - 1];}psl->array[0] = x;psl->size++;
}

2.2.7 顺序表头删

删除数据不要忘记暴力检查psl->size。

//顺序表头删
void SeqListPopFront(SeqList*psl)
{assert(psl);//暴力检查assert(psl->size);for (int i = 0; i < psl->size - 1; i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}

2.2.8 顺序表查找

找到了，返回值为数组下标；未找到，返回值为-1。

//顺序表查找(返回下标,找不到就返回-1)
int SeqListFind(SeqList* psl, SLDateType x)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->array[i] == x){return i;}}return -1;
}

2.2.9 在pos位置插入值

这个功能在实现的过程中一不小心就出问题，注意注意！！！！

//顺序表在pos位置插入x（pos为下标值）
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{assert(psl);assert(pos<=psl->size);//注意：pos是可以等于psl->size，此时就相当于尾插CheckCapacity(psl);//写法一：for (int i = psl->size-1; i >= pos; i--){psl->array[i + 1] = psl->array[i];}//写法二：size_t end=psl->size-1;while(end){psl->array[end+1]=psl->array[end];end--;}psl->array[pos] = x;psl->size++;
}

当在下标为0的位置上插入一个数据时，i从psl->size-1到0，i进行i--操作，此时i=-1，再执行i>=pos操作，此时会停止循环吗？答案是不会，大家可以去调试，确实不会让循环停下。

那为什么呢？因为pos为size_t的类型，size_t为无符号整形-，当int（有符号整形）和size_t（无符号整形）比较大小时，int型的数据会发生算数转换，转换成unsigned int型，此时为负数的i就变成了很大的数字，自然而然比0大，因此会进入死循环。

那怎么解决呢？

针对写法一的解决办法：

for (int i = psl->size; i > pos; i--)
{psl->array[i] = psl->array[i-1];
}

此时，避免了i==0的情况，保证i始终大于0，这样i--就不会出现问题了。

针对写法二的解决方法：

size_t end=psl->size;
while(end)
{psl->array[end]=psl->array[end-1];end--;
}

有人肯定会不理解，为什么非让pos为size_t类型，如果让pos变成int型，只需要保证pos大于等于0就可以了，size_t显得好像更麻烦一些。其实，我们把pos写成size_t是因为库也是这样写的，我们严格根据库的声明来实现，以后当我们涉及到的问题更加复杂时，用size_t做接口肯定比int更好。

2.2.10 顺序表删除pos的位置

这里注意好循环时i的上下限就可以了。

//顺序表删除pos的位置
void SeqListErase(SeqList*psl, size_t pos)
{assert(psl);assert(pos < psl->size);for (int i = pos;i<psl->size-1;i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}

2.2.11 修改pos位置的值

//修改顺序表的值
void SeqListModify(SeqList*psl, size_t pos,SLDateType x)
{assert(psl);assert(pos < psl->size);psl->array[pos] = x;
}

2.2.12 销毁顺序表

//销毁顺序表
void SeqListDestory(SeqList*psl)
{assert(psl);free(psl->array);psl->array = NULL;psl->size = psl->capacity = 0;
}

3、总代码

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
静态版本
//#define N 7
//typedef struct SeqList
//{
//	SLDateType array[N];   //静态数组
//	size_t size;   //有效数据个数
//}SeqList;
//动态版本
typedef struct SeqList
{SLDateType* array;   //指向动态开辟的数组size_t size;   //有效数据个数size_t capacity;  //容量空间的大小
}SeqList;//基本增删查改接口
//顺序表初始化
void SeqListInit(SeqList* psl);  //psl  p指针，sl顺序表
//检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl,SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos,SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x);

SeqList.c

#include"SeqList.h"
//打印顺序表
void PrintSL(const SeqList* psl)
{assert(psl);for (int i = 0; i < psl->size; i++){printf("%d ", psl->array[i]);}printf("\n");
}
//初始化顺序表
void SeqListInit(SeqList* psl)
{assert(psl);psl->array = NULL;psl->size = psl->capacity = 0;
}
//检查容量，增容
void CheckCapacity(SeqList* psl)
{assert(psl);if (psl->size == psl->capacity){size_t newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);//这里用realloc非常好，当realloc的第一个参数为0时，其效果等同于malloc//用realloc可以完美实现最初开辟空间和增容的功能//一定要注意：是newcapacity，而不是psl->capacitySLDateType* tmp = (SLDateType*)realloc(psl->array, newcapacity * sizeof(SLDateType));if (tmp == NULL){perror("realloc：");return;}psl->array = tmp;psl->capacity = newcapacity;}
}
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x)
{assert(psl);CheckCapacity(psl);psl->array[psl->size] = x;//也可以用SeqListInsert（psl，psl->size,x),但经常用上面的方法，可读性更强//可别忘了让psl->size加1psl->size++;
}//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x)
{assert(psl);CheckCapacity(psl);for (int i = psl->size; i > 0; i--){psl->array[i] = psl->array[i - 1];}psl->array[0] = x;//也可以用SeqListInsert（psl，0,x),但经常用上面的方法，可读性更强psl->size++;
}//顺序表尾删
void SeqListPopBack(SeqList* psl)
{assert(psl);//千万不要忘记检查size是否大于0//温柔地检查SL中的size是否大于0/*if (psl->size == 0){return;}*///暴力的检查assert(psl->size > 0);psl->size--;
}//顺序表头删
void SeqListPopFront(SeqList* psl)
{assert(psl);assert(psl->size > 0);for (int i = 0; i < (psl->size - 1); i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->array[i] == x){return i;}}return -1;
}//顺序表在pos位置插入x（pos指的是下标）
void SeqListInsert(SeqList* psl,size_t pos,SLDateType x)
{assert(psl);CheckCapacity(psl);assert(pos <= psl->size);//size_t是无符号整形，所以不需要担心pos小于0//而pos等于psl->size，此时就不是插在中间了，而是尾插了。//易错：pos=0for (int i = psl->size; i >pos; i--){psl->array[i] = psl->array[i - 1];}psl->array[pos] = x;psl->size++;
}//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl);assert(pos<psl->size);for (int i = pos; i < psl->size; i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}
//顺序表销毁
void SeqListDestory(SeqList* psl)
{assert(psl);free(psl->array);psl->array = NULL;psl->capacity = psl->size = 0;
}
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x)
{assert(psl);assert(psl < psl->size);psl->array[pos] = x;
}

test.c

test.c可以自己写，记得引用头文件就可以。

#include"SeqList.h"
int main()
{SeqList SL;SeqListInit(&SL);SeqListPushBack(&SL, 5);SeqListPushBack(&SL, 2);SeqListPushFront(&SL, 0);PrintSL(&SL);SeqListInsert(&SL, 2, 3);PrintSL(&SL);SeqListInsert(&SL, 2, 3);PrintSL(&SL);return 0;
}

这是数据结构第二篇文章了，数据结构有些小难♂，但别担心，快关注我跟我一起坚持学习吧！(*^▽^*)

如果喜欢我的文章就给我点个赞再走吧！下次见！拜拜 ┏(＾0＾)┛


http://chatgpt.dhexx.cn/article/7e8hm0FO.shtml

相关文章

顺序表详解

顺序表详解

目录 一、线性表的概念 二、顺序表 1、顺序表的概念 1&#xff09;. 静态顺序表&#xff1a;使用定长数组存储元素。 2&#xff09;. 动态顺序表&#xff1a;使用动态开辟的数组存储。 三、接口实现 1、创建 2、初始化 3、扩容 4、尾插 5、打印 6、销毁 7、尾删 越界&…
阅读更多...
php的strstr是什么意思,php strstr函数怎么用

php的strstr是什么意思,php strstr函数怎么用

strstr()函数是PHP中的一个内置函数&#xff0c;语法为strstr(string,search,before_search) &#xff0c;用于搜索字符串在另一字符串中是否存在&#xff0c;如果是&#xff0c;返回该字符串及剩余部分&#xff0c;否则返回 FALSE。此函数区分大小写。 php strstr()函数怎么用…
阅读更多...
【数据结构】--- kmp算法和strstr函数

【数据结构】--- kmp算法和strstr函数

kmp算法和strstr函数 引言一、概念分析分析原理分析 KMP算法原理基本操作图解KMP原理 三、复杂度分析四、KMP算法代码 引言 现实生活中&#xff0c;字符串匹配在很多的应用场景里都有着极其重要的作用&#xff0c;包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网…
阅读更多...
实现strstr函数

实现strstr函数

strstr函数的作用是寻找子字符串在目标字符串中第一次出现的位置。 #include <stdio.h> #include<stdlib.h> #include<assert.h> const char * Strstr(const char * str1, const char * str2) {assert(str1 ! NULL);assert(str2 ! NULL);char* cur str1;ch…
阅读更多...
字符串函数剖析（3）---strstr函数

字符串函数剖析（3）---strstr函数

1.strstr函数的巧妙 – 查找子字符串 1.1模拟实现strstr函数 strstr函数&#xff1a;在一个字符串中查找子串 学习新函数时&#xff0c;先去c库查找该函数的相关资料&#xff0c;更加助于你的学习 const char * strstr ( const char * str1, const char * str2 );先看函数…
阅读更多...
C语言strstr()函数用法-字符串查找

C语言strstr()函数用法-字符串查找

1.函数定义 strstr()函数是一个参数为两个字符指针类型&#xff0c;返回值是char*类型的函数。 用于找到子串&#xff08;str2&#xff09;在一个字符串&#xff08;str1&#xff09;中第一次出现的位置&#xff08;不包括str2的串结束符&#xff09;&#xff0c;并返回该位置…
阅读更多...
ConcurrentHashMap 实现原理

ConcurrentHashMap 实现原理

一. ConcurrentHashMap 是什么 在并发编程中&#xff0c;ConcurrentHashMap 是一个经常被使用的数据结构&#xff0c;相比于 Hashtable 以及Collections.synchronizedMap() 来说&#xff0c;ConcurrentHashMap 在线程安全的基础上提供了更好的写并发能力&#xff0c;同时还降低…
阅读更多...
ConcurrentHashMap 详解

ConcurrentHashMap 详解

前言 ConcurrentHashMap。 以下的技术点都基于JDK1.8~ 基础回顾 我们都知道&#xff0c;从JDK1.8起&#xff0c;ConcurrentHashMap底层的数据结构就已经从原来的Segment分段锁变为了数组 链表 红黑树的形态。 它是一款并发容器&#xff0c;一款装数据的容器在并发环境下铁…
阅读更多...
ConcurrentHashMap介绍

ConcurrentHashMap介绍

引言 学习ConcurrentHashMap&#xff0c;合理的问题顺序应该如下&#xff1a; ConcurrentHashMap是什么&#xff08;WHAT&#xff09;为什么要有ConcurrentHashMap&#xff08;WHY&#xff09;ConcurrentHashMap的实现原理&#xff08;HOW&#xff09;ConcurrentHashMap如何使…
阅读更多...
一文彻底弄懂ConcurrentHashMap

一文彻底弄懂ConcurrentHashMap

一文彻底弄懂ConcurrentHashMap 导读前言锁synchronizedvolatile&#xff08;非锁&#xff09;自旋锁分段锁ReentrantLockCAS ConcurrentHashMap 实现原理JDK1.7 中的 ConcurrentHashMapSegmentConcurrentHashMap 并发读写的几种情况get 方法put 方法 JDK1.8 中的 ConcurrentHa…
阅读更多...
ConcurrentHashMap杂谈

ConcurrentHashMap杂谈

为什么使用ConcurrentHashMap 在并发编程中使用HashMap可能导致程序死循环&#xff0c;而使用线程安全的HashTable效率又非常低下 线程不安全的HashMap 在多线程环境下&#xff0c;使用HashMap进行put操作会引起死循环&#xff0c;导致CPU利用率接近100% 死循环案例&#xf…
阅读更多...
图解ConcurrentHashMap

图解ConcurrentHashMap

曾经研究过jkd1.5新特性&#xff0c;其中ConcurrentHashMap就是其中之一&#xff0c;其特点&#xff1a;效率比Hashtable高&#xff0c;并发性比hashmap好。结合了两者的特点。 集合是编程中最常用的数据结构。而谈到并发&#xff0c;几乎总是离不开集合这类高级数据结构的支…
阅读更多...
Java集合：ConcurrentHashMap

Java集合：ConcurrentHashMap

本篇内容包括&#xff1a;ConcurrentHashMap 概述、ConcurrentHashMap 底层数据结构、ConcurrentHashMap 的使用以及相关知识点。 一、ConcurrentHashMap 概述 ConcurrentHashMap 是 HashMap 的线程安全版本&#xff0c;其内部和 HashMap 一样&#xff0c;也是采用了数组 链表…
阅读更多...
Hashtable与ConcurrentHashMap区别

Hashtable与ConcurrentHashMap区别

ConcurrentHashMap融合了hashtable和hashmap二者的优势。 hashtable是做了同步的&#xff0c;hashmap未考虑同步。所以hashmap在单线程情况下效率较高。hashtable在的多线程情况下&#xff0c;同步操作能保证程序执行的正确性。 但是hashtable每次同步执行的时候都要锁住整个结…
阅读更多...
ConcurrentHashMap 面试题

ConcurrentHashMap 面试题

作者&#xff1a;程序员库森 链接&#xff1a;https://www.nowcoder.com/discuss/591527?source_idprofile_create_nctrack&channel-1 来源&#xff1a;牛客网 本文汇总了常考的 ConcurrentHashMap 面试题&#xff0c;面试 ConcurrentHashMap&#xff0c;看这一篇就够了…
阅读更多...
Hashmap和ConcurrentHashmap的区别

Hashmap和ConcurrentHashmap的区别

HashTable &#xff08;1&#xff09;底层数组链表实现&#xff0c;无论key还是value都不能为null&#xff0c;线程安全&#xff0c;实现线程安全的方式是在修改数据时锁住整个HashTable&#xff0c;效率低&#xff0c;ConcurrentHashMap做了相关优化 &#xff08;2&#xff0…
阅读更多...
ConcurrentHashMap的作用与用法

ConcurrentHashMap的作用与用法

ConcurrentHashMap的作用与用法 一.ConcurrentHashMap简介 ConcurrentHashMap是属于JUC工具包中的并发容器之一&#xff0c;在多线程开发中很经常会使用到这个类&#xff0c;它与HashMap的区别是HashMap是线程不安全的&#xff0c;在高并发的情况下&#xff0c;使用HashMap进行…
阅读更多...
Java并发包concurrent——ConcurrentHashMap

Java并发包concurrent——ConcurrentHashMap

目录 1. ConcurrentHashMap的实现——JDK7版本 1.1 分段锁机制 1.2 ConcurrentHashMap的数据结构 1.3 ConcurrentHashMap的初始化 1.3.1 初始化ConcurrentHashMap 1.3.2 初始化Segment分段 1.4 定位Segment 1.5 ConcurrentHashMap的操作 1.5.1 get 1.5.2 put 1.5.3 …
阅读更多...
Java8 ConcurrentHashMap详解

Java8 ConcurrentHashMap详解

点个赞&#xff0c;看一看&#xff0c;好习惯&#xff01;本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录&#xff0c;这是我花了 3 个月总结的一线大厂 Java 面试总结&#xff0c;本人已拿大厂 offer。 另外&#xff0c;原创文章首发在我的个人博客&#x…
阅读更多...
HashMap与ConcurrentHashMap的区别

HashMap与ConcurrentHashMap的区别

从JDK1.2起&#xff0c;就有了HashMap&#xff0c;正如前一篇文章所说&#xff0c;HashMap不是线程安全的&#xff0c;因此多线程操作时需要格外小心。 在JDK1.5中&#xff0c;伟大的Doug Lea给我们带来了concurrent包&#xff0c;从此Map也有安全的了。 ConcurrentHashMap具体…
阅读更多...
推荐文章

Copyright @ 2022~2023