男女在床上做孔网站,wordpress 维护页面,专业建站公司建站系统,建站售后服务从本文正式进入对数据结构的讲解#xff0c;开始前友友们要有C语言的基础#xff0c;熟练掌握动态内存管理、结构体、指针等章节#xff0c;方便后续的学习。 顺序表#xff08;Sequence List#xff09; 线性表的概念#xff1a;线性表#xff08;linear list#xff… 从本文正式进入对数据结构的讲解开始前友友们要有C语言的基础熟练掌握动态内存管理、结构体、指针等章节方便后续的学习。 顺序表Sequence List 线性表的概念线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 线性表是对存储具有某种共同点的数据集合的统称顺序表和数组就是线性表的一种。顺序表的底层逻辑是利用数组实现的但是相较于数组顺序表的功能更齐全、丰富顺序表新增了增、删、查、改等功能。
顺序表的分类 根据定义格式的不同顺序表又可分为静态顺序表和动态顺序表。
静态顺序表
#include stdio.hstruct SeqList//定义顺序表
{int arr[10];//定长数组int size;//顺序表中有序的元素个数
};
静态顺序表的缺陷空间给少了不够⽤给多了造成空间浪费。静态顺序表的定义方式已经基本被淘汰现在大多采用动态顺序表的定义方式。
动态顺序表 动态顺序表不同于静态顺序表它很好的解决了空间浪费的问题动态顺序在定义时不直接指明内存空间的大小在初始化时有一定的空间而是根据需求通过动态内存分配的方式开辟内存等到存储空间不够时再扩容。
#include stdio.htypedef 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);
} 示例 int main()
{SL p;SLinit(p);printf(这是尾插:);//尾插1 2 3 4 5SLpopBack(p, 1);SLpopBack(p, 2);SLpopBack(p, 3);SLpopBack(p, 4);SLpopBack(p, 5);SLprint(p);printf(这是头插:);//头插6 7 8SLpopFront(p, 8);SLpopFront(p, 7);SLpopFront(p, 6);SLprint(p);printf(这是头删:);//头删6 7 8SLpushFront(p);SLpushFront(p);SLpushFront(p);SLprint(p);printf(这是尾删:);//尾删3 4 5SLpushBack(p);SLpushBack(p);SLpushBack(p);SLprint(p);SLdestory(p);return 0;
} 运行结果
