数据结构(初阶)第一节:数据结构概论-CSDN博客
从本文正式进入对数据结构的讲解,开始前友友们要有C语言的基础,熟练掌握动态内存管理、结构体、指针等章节,方便后续的学习。
目录
顺序表(Sequence List)
顺序表的分类
静态顺序表
动态顺序表
顺序表的功能
初始化
扩容
头插
尾插
头删
尾删
销毁
打印顺序表
指定下标插入
指定下标删除
查找
示例
顺序表(Sequence List)
线性表的概念:线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构,常⻅的线性表:顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的, 线性表在物理上存储时,通常以数组和链式结构的形式存储。
线性表是对存储具有某种共同点的数据集合的统称,顺序表和数组就是线性表的一种。顺序表的底层逻辑是利用数组实现的,但是相较于数组,顺序表的功能更齐全、丰富,顺序表新增了增、删、查、改等功能。
顺序表的分类
根据定义格式的不同,顺序表又可分为静态顺序表和动态顺序表。
静态顺序表
#include <stdio.h>
struct SeqList//定义顺序表
{
int arr[10];//定长数组
int size;//顺序表中有序的元素个数
};
静态顺序表的缺陷:空间给少了不够⽤,给多了造成空间浪费。静态顺序表的定义方式已经基本被淘汰,现在大多采用动态顺序表的定义方式。
动态顺序表
动态顺序表不同于静态顺序表,它很好的解决了空间浪费的问题,动态顺序在定义时不直接指明内存空间的大小(在初始化时有一定的空间),而是根据需求通过动态内存分配的方式开辟内存,等到存储空间不够时再扩容。
#include <stdio.h>
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;//动态数组
int size;//有效元素个数
int capacity;//已经开辟的空间大小
}SL;
在一开始定义时,使用typedef关键字对数据类型和结构体重命名,方便后续修改,比如说将存储int的数组改为存储char的数组,只需要将typedef int SLDateType中的int改为char即可,可以提高开发效率。
顺序表的功能
初始化
在初始化时,我们选择malloc函数为数组分配内存,初始的内存空间一般定义为4个字节的大小。
注意:在对初始化函数传参时一定要传地址值,也就是参数一定是指针变量,不能直接将非指针变量传递过去,因为形参和实参不在同一块内存空间中,直接传参的话会导致初始化失败,程序报错。
void SLinit(SL* ps) { ps->a = malloc((sizeof(SLDateType)) * 4);//初始内存4个字节 if (ps->a == NULL)//分配内存失败 { perror("malloc fail"); return; } ps->capacity = 4; ps->size = 0; }
扩容
在对顺序表进行扩容时应该首先判断该情况下是否需要扩容,即ps->capacity == ps->size,判断之后使用realloc函数进行扩容,每次扩容应为上一次的两倍。
void SLcheckCapcity(SL* ps) { if (ps->capacity == ps->size)//判断是否需要扩容 { SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);//一般每次扩容到上一次的2倍 if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } }
头插
在顺序表的头部插入一个元素,其余元素按顺序向后移动。
void SLpopFront(SL* ps, SLDateType x) { assert(ps); SLcheckCapcity(ps); for (int i = ps->size; i >= 1; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; ps->size++; }
尾插
顺序表尾部插入元素,在尾部插入时就一定要进行数组扩容。通过调用SLpopBack函数在尾部插入元素,ps->size最开始指向0索引,每次插入元素时size总在最后一个有效元素的下一位。
void SLpopBack(SL* ps, SLDateType x) { assert(ps); SLcheckCapcity(ps); ps->a[ps->size++] = x; }
头删
从顺序表头部删除元素,将元素按顺序前移,覆盖要删除的元素。
void SLpushFront(SL* ps) { assert(ps && ps->size);//当顺序表为空时不用删除元素 for (int i = 1; i < ps->size; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; }
尾删
void SLpushBack(SL* ps) { assert(ps && ps->size); ps->size--; }
销毁
void SLdestory(SL* ps) { free(ps); ps->a = NULL; ps->capacity = 0; ps->size = 0; }
打印顺序表
void SLprint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]); printf("\n"); }
指定下标插入
void SLinsert(SL* p1, int pos, SLDataType x) { //要注意p1->size指向的是最后一个有效数据的下一位 //pos是指定的插入位置的下标(如果为0则是头插,如果为ps->size-1则为尾插) //x是待插入的数据 assert(p1 && pos >= 0 && pos < p1->size); SLcheckCapcity(p1); for (int i = p1->size; i > pos; i--) { p1->a[i] = p1->a[i - 1]; } p1->a[pos] = x; p1->size++; }
指定下标删除
void SLerase(SL* p1, int pos) { assert(p1 && pos >= 0 && pos < p1->size); for (int i = pos; i < p1->size - 1; i++) { p1->a[i] = p1->a[i + 1]; } p1->size--; }
查找
int SLfind(SL* p1, SLDataType x) { assert(p1); for (int i = 0; i < p1->size; i++) { if (p1->a[i] == x) { return i;//找到后返回下标 } } return -1;//没有找到返回-1 }
示例
int main() { SL p; SLinit(&p); printf("这是尾插:");//尾插1 2 3 4 5 SLpopBack(&p, 1); SLpopBack(&p, 2); SLpopBack(&p, 3); SLpopBack(&p, 4); SLpopBack(&p, 5); SLprint(&p); printf("这是头插:");//头插6 7 8 SLpopFront(&p, 8); SLpopFront(&p, 7); SLpopFront(&p, 6); SLprint(&p); printf("这是头删:");//头删6 7 8 SLpushFront(&p); SLpushFront(&p); SLpushFront(&p); SLprint(&p); printf("这是尾删:");//尾删3 4 5 SLpushBack(&p); SLpushBack(&p); SLpushBack(&p); SLprint(&p); SLdestory(&p); return 0; }
运行结果:文章来源:https://www.toymoban.com/news/detail-848359.html
文章来源地址https://www.toymoban.com/news/detail-848359.html
到了这里,关于数据结构(初阶)第二节:顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!