互联网服务平台登录,安阳网站制作优化,酒泉市建设局网站招标办,黑龙江网站建设工作室文章目录 一、线性表二、顺序表顺序表和数组的区别顺序表的分类1.静态顺序表2.动态顺序表 三、动态顺序表的实现1.动态顺序表头文件2.动态顺序表源文件3.测试源文件 一、线性表 线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。线性表是⼀种… 文章目录 一、线性表二、顺序表顺序表和数组的区别顺序表的分类1.静态顺序表2.动态顺序表 三、动态顺序表的实现1.动态顺序表头文件2.动态顺序表源文件3.测试源文件 一、线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使 ⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储
二、顺序表
顺序表和数组的区别 顺序表的底层结构是数组对数组的封装实现了常⽤的增删改查等接口
顺序表的分类
1.静态顺序表
概念使⽤ 定⻓数组 存储元素 静态顺序表缺陷空间给少了不够⽤给多了造成空间浪费
2.动态顺序表 动态顺序表就是动态分配内存可以根据需求调节数组大小 三、动态顺序表的实现 实现的主要思想 1.初始化顺序表先初始化arr为NULLsize为0capacity为0 2.销毁顺序表顺序表使用完成之后把arr动态分配的内存释放掉 3.扩容顺序表在每次插入数据之前必须先检查是否空间充足不足则开辟更大的空间 4.增删查改顺序表围绕数组去做即可比较简单。增头插尾插指定位置插入删包括头删尾删指定位置删除查找数据。
1.动态顺序表头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
// 动态顺序表
// 按需申请
typedef int SLDateType;typedef struct SeqList
{SLDateType* arr;int size;//有效数据个数int capacity;//空间大小
}SL;void SLInit(SL* ps);//顺序表的初始化
void SLDestroy(SL* ps);//顺序表的销毁
void SLPrint(SL* ps);//顺序表的打印void SLCheckCapacity(SL* ps);//扩容//头部插入删除 / 尾部插入删除
void SLPushFront(SL* ps, SLDateType x);
void SLPushBack(SL* ps, SLDateType x);void SLPopFront(SL* ps);
void SLPopBack(SL* ps);//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDateType x);
void SLErase(SL* ps, int pos);//查找数据
int SLFind(SL* ps, SLDateType x);2.动态顺序表源文件
#include Seqlist.h
//初始化
void SLInit(SL* ps)
{ps-arr NULL;ps- size 0;ps-capacity 0;
}
//销毁
void SLDestroy(SL* ps)
{if (ps-arr){free(ps-arr);}ps-arr NULL;ps-size 0;ps-capacity 0;
}//打印
void SLPrint(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}//扩容
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){//申请空间int NewCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;SLDateType* tmp (SLDateType*)realloc(ps-arr, NewCapacity * sizeof(SLDateType));if (tmp NULL){perror(realloc fail!);exit(1);//直接退出程序}ps-arr tmp;ps-capacity NewCapacity;}
}//头部插入
void SLPushFront(SL* ps, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size-1;i 0;i--){ps-arr[i 1] ps-arr[i];}ps-arr[0] x;ps-size;
}//尾部插入
void SLPushBack(SL* ps, SLDateType x)
{assert(ps);SLCheckCapacity(ps);ps-arr[ps-size] x;
}//头部删除
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];}ps-size--;
}//尾部删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size);ps-size--;
}//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);for (int i ps-size-1;i pos;i--){ps-arr[i1] ps-arr[i];}ps-arr[pos] x;ps-size;
}//指定位置之前删除数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);for (int i pos;i ps-size-1;i){ps-arr[i] ps-arr[i 1];}ps-size--;
}//查找数据
int SLFind(SL* ps, SLDateType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x){return i;}}return -1;
}3.测试源文件
最后可以在创建一个测试源文件去测试顺序表的正确性
#include Seqlist.hvoid test()
{SL s1;//测试初始化SLInit(s1);//测试尾部插入SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushBack(s1, 5);//测试打印SLPrint(s1);//测试头部插入/*SLPushFront(s1, 9);SLPushFront(s1, 8);SLPushFront(s1, 7);SLPushFront(s1, 6);SLPushFront(s1, 66);*///测试头删/*SLPopFront(s1);SLPrint(s1);SLPopFront(s1);SLPrint(s1);SLPopFront(s1);SLPrint(s1);SLPopFront(s1);SLPrint(s1);SLPopFront(s1);SLPrint(s1);SLPopFront(s1);SLPrint(s1);*///测试尾删/*SLPopBack(s1);SLPrint(s1);SLPopBack(s1);SLPrint(s1);SLPopBack(s1);SLPrint(s1);SLPopBack(s1);SLPrint(s1);SLPopBack(s1);SLPrint(s1);SLPopBack(s1);SLPrint(s1);*///测试在指定位置之前插入数据/*SLInsert(s1, 3, 8);SLPrint(s1);*///测试在指定位置之前删除数据/*SLErase(s1, 1);SLPrint(s1);*///测试查找int find SLFind(s1, 3);if (find ! -1){printf(找到了下标为%d\n, find);}else{printf(没有找到\n);}//测试销毁SLDestroy(s1);
}int main()
{test();return 0;
}
