目录
前言:
1.源代码如下
2.数据结构——顺序表
2.1.顺序表的特点
2.2顺序表的分类
2.2.1.动态分配内存的顺序表
2.2.2.静态分配内存的顺序表
2.3.定义一个顺序表
3.顺序表的基本操作
3.1初始化顺序表
不用将顺序表中可能存在的原有元素初始化吗?
原因
3.2求元素个数
3.3插入元素*
基本步骤与思路
各步骤目的
3.4删除元素*
基本步骤与思路
各步骤目的
3.5获取元素
结束语
前言:
顺序表是数据结构中最为基础,也是最为简单的结构。后面的栈,队列,串等结构和顺序表有密切关系,要学好数据结构,顺序表必定要掌握!!👍
1.源代码如下
#代码很长,展示了顺序表全部基本操作,不用细看,由我接下来细细分开讲解。
#define MaxSize 100 //静态内存
#include<stdio.h>
typedef int score;//将datatype设置为了成绩score(便于简单理解)
typedef struct
{
score list[MaxSize];
int size;
}SeqList;//顺序表定义(此处为成绩列表)
//顺序表的操作:
//一、初始化
void ListInitiate(SeqList* L)//传入顺序表地址
{
L->size = 0;//初始长度为0,无元素
}//有地址有长度---》》》创建顺序表完成
//二、求当前元素个数(将长度返回)
int ListLength1(SeqList* L)//传入地址找size
{
return L->size;
}
int ListLength2(SeqList L)//传入整个表找size
{
return L.size;
}
//三、插入元素
//#默认i的合法范围为i∈[0,size)#
/*接受int返回值1或0,判断插入成败(后面同理)*/
int ListInsert(SeqList* L, int i, score x)//i为插入位置,x为插入的元素
{
//1.先判断能否插入:
if (L->size == MaxSize)
{
printf("无法插入,内存不足!");
return 0;//直接退出(下同)
}
//2.再判断传入的i是否合法(即未超出范围):
else if (i < 0 || i > L->size)
{
printf("i的输入不合法,无法插入!");
return 0;//直接退出
}
//3.开始插入:
else
{
for (int j = L->size; j > i; j--) L->list[j] = L->list[j - 1];//将插入位置后面的元素整体后移
L->list[i] = x;//覆盖i处原元素
L->size++;//长度加1
return 1;
}
}
//四、删除元素
int ListDelete(SeqList* L, int i, score* x)//i为删除元素的位置,x保存删除的元素等待另外处置
{
//先判断i是否合法(同上)
if (i < 0 || i > L->size)
{
printf("i的输入不合法,无法删除");
return 0;
}
//再判断能否再删
else if (L->size == 0)
{
printf("已无元素可删!");
return 0;
}
//开始删除
else
{
*x = L->list[i];//先保存
for (int j = i; j < L->size; j++)//再往前覆盖
{
L->list[j] = L->list[j+1];
}
L->size--;//长度减1
return 1;
}
}
//五、获取元素
int ListGet(SeqList* L, int i, score* x)//x接受获取到的元素
{
//判断i输入合法性(下同)
if (i < 0 || i > L->size)
{
printf("i的输入不合法,无法获取!");
return 0;
}
else
{
*x = L->list[i];
return 1;
}
}
//尝试建立顺序表并使用基本操作
int main()
{
SeqList L;
//初始化
ListInitiate(&L);
//插入若干元素
for (int i = 0; i < 10; i++)
{
score z=i+1;
ListInsert(&L, i, z);
}
//删除一个元素
score x;//(接受删除元素)
ListDelete(&L, 6, &x);
//求顺序表长度
int length1 = ListLength1(&L);
int length2 = ListLength2(L);
printf("%d,%d\n", length1, length2);
//获取元素并输出
for (int i = 0; i < length1; i++)
{
score y;
ListGet(&L, i, &y);
printf("%d ", y);
}
return 0;
}
这段代码的基本情境是用顺序表存储学生成绩score。
2.数据结构——顺序表
#我们先来了解顺序表的基本知识
2.1.顺序表的特点
顾名思义,顺序表的存储结构是有顺序的,每一个元素的存储在逻辑上和物理上都是连续的。它实质上就是一个数组。(“逻辑”是对于代码逻辑而言的;“物理”是对于实际存储的地址而言的)
arr | 元素1 | 元素2 | 元素3 |
元素4 | …… | 元素n | …… | 空(可能) |
arr的索引 | 0 | 1 | 2 | 3 | …… | n | …… | n+m |
arr元素的地址 (假设) |
0x1000 | 0x1004 | 0x1008 | 0x100c | …… | …… | …… | …… |
逻辑上:在对任一元素访问和存储时,都能依靠索引来进行。索引从0开始依次增加1,元素也按照次序存放在数组里。
物理上:当我们在VS2022上调试代码时,我们能够发现,数组中存放的每一个元素的地址也是按顺序排列的,随着索引值大小的递增而递增,差值为元素类型的字节数。
这个连续的特点和链表对比就很好理解。链表在逻辑上是连续的,因为每一个元素结点都有指针相连接,形成一个有序的数据结构。但是在物理上不是连续的,因为每个结点的地址是随机创建的的,之间没有关联。(我的主页里有关于链表的博客哦!Elnaij-CSDN博客)
2.2顺序表的分类
#本文中的顺序表默认使用静态分配内存的顺序表,关于动态分配,动态数组的创建,我会在有关串的数据结构文章中讲到!敬请期待~🖖
2.2.1.动态分配内存的顺序表
它的大小长度可以按需要创建。
2.2.2.静态分配内存的顺序表
他的大小长度由一个常量确定。
2.3.定义一个顺序表
#define Maxsize 100
typedef struct
{
score list[MaxSize];
int size;
}SeqList;//顺序表定义(此处为成绩列表)
用结构体来定义,里面包含要存储score成绩数据的list数组,数组大小为宏常量Maxsize(100),还有表示元素个数的size。
#既然顺序表本质上是一个数组,可为什么还要用结构体来定义呢?就为了多存一个size元素个数的信息?有必要吗?(往下看就知道啦!)
3.顺序表的基本操作
我在源代码中使用了
typedef int score;
score是元素的数据名称,这样写目的是为了便于理解数据的实际内容,表示顺序表存储的是学生的成绩score,也就是很多教科书里面写到的DataType,这里把教材的概念具体化了。
3.1初始化顺序表
void ListInitiate(SeqList* L)//传入顺序表地址
{
L->size = 0;//初始长度为0,无元素
}//有地址有长度---》》》创建顺序表完成
十分简单的操作。将顺序表里的元素个数size赋值为0即可。
Q:不用将顺序表中可能存在的原有元素初始化吗?
A:初始化一个已有数据的顺序表,不必要对原有元素进行改变。
原因
i.顺序表的内存空间已经创建好,所以不管对里面的元素怎么修改,甚至空置为NULL,都不会影响其内存大小。
ii.size的值可以作为能否进行其他操作的判断标准。当size=0时,就不让删除操作进行。或者让插入操作不可以将新元素插入超过数组索引为size+1的位置。这样即使在插入时有原有元素的存在,原有元素也会被新元素覆盖掉。(不懂的话,让下看删除和插入操作就能有所体会了)
3.2求元素个数
//二、求当前元素个数(将长度返回)
int ListLength1(SeqList* L)//传入地址找size
{
return L->size;
}
int ListLength2(SeqList L)//传入整个表找size
{
return L.size;
}
这里有两种求元素个数的操作,实际上是一样的。
传入的是指针就用"->"访问到顺序表的size并返回;
传入的是整个顺序表就用"."访问到顺序表的size并返回。
因为这个操作不会也不需要对顺序表进行修改,所以可以不传入顺序表的指针,而是直接传入整个顺序表。
3.3插入元素*
!!重要!!
//三、插入元素
//#默认pos的合法范围为pos∈[0,size)#
/*接受int返回值1或0,判断插入成败(后面同理)*/
int ListInsert(SeqList* L, int pos, score x)//i为插入位置,x为插入的元素
{
//1.先判断能否插入:
if (L->size == MaxSize)
{
printf("无法插入,内存不足!");
return 0;//直接退出(下同)
}
//2.再判断传入的i是否合法(即未超出范围):
else if (pos < 0 || pos > L->size)
{
printf("pos的输入不合法,无法插入!");
return 0;//直接退出
}
//3.开始插入:
else
{
for (int j = L->size; j > pos; j--) L->list[j] = L->list[j - 1];//将插入位置后面的元素整体后移
L->list[pos] = x;//覆盖i处原元素
L->size++;//长度加1
return 1;
}
}
#先来分析插入元素的思路。
基本步骤与思路
i.传入插入的位置pos和要插入的元素。
ii.判断内存是否足够插入新元素。
iii.判断pos这一插入位置是否合法(有没有超出范围0~size)。
iiii.将在位置pos以及之后的所有元素从最后一个元素开始都依次后移一个位置。
iiiii.将新元素赋值到pos位置
iiiiii.size=size+1
各步骤目的
i步是传参,ii和iii是判断插入是否可行,iiii步是在腾出位置,这时pos位置还有一个原有元素,但是没关系,iiiii步把新元素覆盖pos处原有元素,完成插入。最后让元素个数size+1.
比如说我要在pos为2处插入元素999:
索引 | 0 | 1 | 2 | 3 | 4 | …… | n-1 | |
arr元素 | 1 | 2 | 3 | 4 | 5 | …… | n | |
↘ | ↘ | ↘ | ↘ | ↘ | ||||
arr插入前 |
1 | 2 | 3 | 3 | 4 | 5 | …… | n |
索引 | 0 | 1 | 2 | 3 | 4 | 5 | …… | n-1 |
arr插入后 | 1 | 2 | 999 | 3 | 4 | 5 | …… | n |
索引 | 0 | 1 | 2 | 3 | 4 | 5 | …… | n-1 |
size的作用:插入操作这里就能看到size的作用了——size的值可以作为能否进行其他操作的判断标准。ii和iii步可离不开size。
3.4删除元素*
!!重要!!
//四、删除元素
int ListDelete(SeqList* L, int i, score* x)//i为删除元素的位置,x保存删除的元素等待另外处置
{
//先判断i是否合法(同上)
if (i < 0 || i > L->size)
{
printf("i的输入不合法,无法删除");
return 0;
}
//再判断能否再删
else if (L->size == 0)
{
printf("已无元素可删!");
return 0;
}
//开始删除
else
{
*x = L->list[i];//先保存
for (int j = i; j < L->size; j++)//再往前覆盖
{
L->list[j] = L->list[j+1];
}
L->size--;//长度减1
return 1;
}
}
基本步骤与思路
i.传入删除的位置pos和一个类型与顺序表中元素相同的变量x。
ii.判断顺序表中是否还有元素可以删除。
iii.判断pos这一删除位置是否合法(有没有超出0~size)。
iiii.用变量x接受删除的元素。
iiiii.将在位置pos之后的所有元素从最前面的元素开始都依次前移一个位置。
iiiiii.size=size-1
各步骤目的
比如我要删除pos为2处的元素 ,size为n,Maxsize为n+1
size=n | ||||||||
索引 | 0 | 1 | 2 | 3 | 4 | …… | n-1 | n |
arr元素 | 1 | 2 | 3 | 4 | 5 | …… | n | NULL |
size=n | ↓ 存入x |
↓ ↙ |
↓ ↙ |
↓ ↙ |
↓ ↙ |
|||
arr删除后 |
1 | 2 | 4 | 5 | …… | n | n | NULL |
索引 | 0 | 1 | 2 | 3 | …… | n-2 | n-1 | n |
size=n-1 |
i~iii步骤同上(插入操作部分)。不同的是,iiii步要将删除的元素另外存起来,存起来的好处是可以后续对其进行进一步处置。最后一步,是要通过覆盖前面元素的值以达到删除的功能。最后让元素个数size -1.
size的作用:删除操作这里也能看到size的作用——size的值可以作为能否进行其他操作的判断标准。
我们可以看到,进行删除操作之后,顺序表里的数组里面最后一个元素和倒数第二个元素是一样的,但是没有关系,因为size已经-1,最后一个元素已经被size限制,保证它下次不会被进行删除操作。索引>=size的位置也只会在之后的插入操作时被覆盖。
3.5获取元素
十分简单!
//五、获取元素
int ListGet(SeqList* L, int i, score* x)//x接受获取到的元素
{
//判断i输入合法性(下同)
if (i < 0 || i > L->size)
{
printf("i的输入不合法,无法获取!");
return 0;
}
else
{
*x = L->list[i];
return 1;
}
}
首先判断要获取的元素的位置是否合法,合法就存到score变量x里,完成获取。同求元素个数操作,因为这个操作不会也不需要对顺序表进行修改,所以可以不传入顺序表的指针,而是直接传入整个顺序表。
size在这又对操作合法性进行了限制!
到这里,你应该知道为什么size很重要了吧!
结束语
顺序表和链表统称为线性表,它们是所有数据结构的基础,学到后面,我们会发现很多的数据结构类型都从他们两个变化来。总之很重要啦!三连三连!!!❤
我的主页也有关于链表知识的博客哦!↓点击跳转,继续学习!😍基于C语言的数据结构之单链表——带你熟练掌握单链表!!超级详细!!-CSDN博客文章来源:https://www.toymoban.com/news/detail-858359.html
Elnaij-CSDN博客文章来源地址https://www.toymoban.com/news/detail-858359.html
到了这里,关于基于C语言的数据结构之顺序表——带你熟练掌握顺序表基本操作!!超级详细!!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!