海口建设厅网站,网站数据库网络错误,重庆网站建设合肥公司,wordpress 插件有木马目录
1. 概念与结构
1.1 静态顺序表
1.2 动态顺序表
2. 动态顺序表实现
2.1 SeqList.h
2.2 SeqList.c
2.3 Test_SeqList.c
3. 顺序表性能分析 线性表是n个具有相同特性的数据元素的有限序列。
常见的线性表有#xff1a;顺序表、链表、栈、队列、字符串等#xff1b…目录
1. 概念与结构
1.1 静态顺序表
1.2 动态顺序表
2. 动态顺序表实现
2.1 SeqList.h
2.2 SeqList.c
2.3 Test_SeqList.c
3. 顺序表性能分析 线性表是n个具有相同特性的数据元素的有限序列。
常见的线性表有顺序表、链表、栈、队列、字符串等
线性表在逻辑上是连续的线性结构在物理结构上并不一定是连续的。
线性表在物理上存储时通常以数组和链式结构的形式存储分别称之为顺序表和链表。
本文介绍顺序表。
1. 概念与结构
顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构一般情况下采取数组存储在数组上完成数据的增删查改
要求数据必须从第一个位置开始连续存放
顺序表在逻辑上是连续的在物理上也是连续的
1.1 静态顺序表
#define N 100
typedef int SLDataType;
// 静态顺序表
typedef struct SeqList{SLDataType arr[N]; // 定长数组size_t size; // 有效数据个数
}SeqList;
在定义时使用定长数组会造成数组大小若太小则导致不够用数组若太大则导致空间浪费
1.2 动态顺序表
#define N 100
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList {SLDataType* arr;size_t size; // 有效数据个数size_t capacity; // 空间大小
}SeqList;
在定义时仅给定数组首元素地址并且基于size和capacity实现动态增容相较而言更灵活。
注1、通常会将顺序表的结构体命名为struct SeqList即Sequence List
2、建议目录结构注意自定义头文件的包含
.h头文件顺序表结构、声明顺序表的方法
.c/.cpp源文件实现顺序表的方法测试 3、为便于修改程序通常会将顺序表结构体中的数据类型进行重命名可命名为SLDataType 为便于编写程序通常也会对顺序表结构体进行重命名可重命名为SeqList或SL
2. 动态顺序表实现
2.1 SeqList.h
#includestdio.h
#includestdlib.h
#includeassert.h
#define N 100
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;int size; // 有效数据个数int capacity; // 空间大小
}SL;
// 空间检查
void SLCheckCapacity(SL* psl);
// 打印
void SLPrint(SL* psl);
// 初始化
void SLInit(SL* psl);
// 销毁
void SLDestory(SL* psl);
// 尾插
void SLPushBack(SL* psl, SLDataType x);
// 头插
void SLPushFront(SL* psl, SLDataType x);
// 尾删
void SLPopBack(SL* psl);
// 头删
void SLPopFront(SL* psl);
// 指定位置插入
void SLInsert(SL* psl,int pos, SLDataType x);
// 指定位置删除
void SLErase(SL* psl,int pos);
// 查找
int SLFind(SL* psl, SLDataType x);
// 修改
void SLModify(SL* psl, int pos, SLDataType x);2.2 SeqList.c
#include SeqList.h
// 初始化
void SLInit(SL* psl) {psl-arr NULL;psl-size psl-capacity 0;
}
// 销毁
void SLDestory(SL* psl) {if (psl-arr) {free(psl-arr);}psl-arr NULL;psl-size psl-capacity 0;
}
// 打印
void SLPrint(SL* psl) {assert(psl);for (int i 0; i psl-size; i) {printf(%d , psl-arr[i]);}printf(\n);
}
// 空间检查
void SLCheckCapacity(SL* psl) {if (psl-capacity psl-size) {// 常以2倍增容int newCapacity psl-capacity 0 ? 4 : psl-capacity * 2;SLDataType* tmp (SLDataType*)realloc(psl-arr, newCapacity*sizeof(SLDataType));if (tmp NULL) {perror(realloc fail\n);exit(1);}psl-arr tmp;psl-capacity newCapacity;}
}
// 尾插
void SLPushBack(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);// 写法1/*psl-arr[psl-size] x;psl-size;*/// 写法2psl-arr[psl-size] x;
}
// 头插
void SLPushFront(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);int count psl-size;// 写法一while (count) {psl-arr[count] psl-arr[count-1];count--;}// 写法二//for (int i psl-size; i 0; i--) {// psl-arr[i] psl-arr[i - 1];//}psl-arr[0] x;psl-size;
}
// 尾删
void SLPopBack(SL* psl) {assert(psl);assert(psl-size);psl-size--;
}
// 头删
void SLPopFront(SL* psl) {assert(psl);assert(psl-size);for (int i 0; i psl-size - 1; i) {psl-arr[i] psl-arr[i1];}psl-size--;
}
// 指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos0 pospsl-size);SLCheckCapacity(psl);for (int i psl-size; i psl-size - pos;i--) {psl-arr[i] psl-arr[i-1];}psl-arr[pos] x;psl-size;
}
// 指定位置删除
void SLErase(SL* psl, int pos) {assert(psl);assert(pos 0 pos psl-size);for (int i pos; i psl-size - 1; i) {psl-arr[i] psl-arr[i 1];}psl-size--;
}
// 查找
int SLFind(SL* psl, SLDataType x) {assert(psl);for (int i 0; i psl-size; i) {if (psl-arr[i] x)return i;}return -1;
}
// 修改
void SLModify(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos 0 pos psl-size);psl-arr[pos] x;
}
2.3 Test_SeqList.c
#includeSeqList.h
int main() {SL sl1;SLInit(sl1);printf(Test SLPushBack:PushBack5~10\n);SLPushBack(sl1, 5);SLPushBack(sl1, 6);SLPushBack(sl1, 7);SLPushBack(sl1, 8);SLPushBack(sl1, 9);SLPushBack(sl1, 10);SLPrint(sl1);printf(TestPushFront:PushFront 4~2\n);SLPushFront(sl1, 4);SLPushFront(sl1, 3);SLPushFront(sl1, 2);SLPrint(sl1);printf(TestPopBack:PopBack 10\n);SLPopBack(sl1);SLPrint(sl1);printf(TestPopFront:PopFront 2\n);SLPopFront(sl1);SLPrint(sl1);printf(TestInsert:Insert arr[4]99\n);SLInsert(sl1, 4, 99);SLPrint(sl1);printf(TestErase:Erase arr[3]\n);SLErase(sl1, 3);SLPrint(sl1);printf(TestFind: Find 99\n);int retIndex SLFind(sl1, 99);printf(The index of 99 is: %d\n, retIndex);printf(TestModify:Modify 99 to 100\n);SLModify(sl1, 3, 100);SLPrint(sl1);SLDestory(sl1);
}
测试用例运行结果 注1、关于初始化与扩容问题方法多样逻辑完整即可
上文示例为SLInit使得psl-capacity初值为0从而在SLCheckCapacity中对于0容量的扩容不能采取一概而论的二倍扩容法上例使用三目操作符:?使得capacity被赋值为4。
也可在SLInit中就对capacity赋予一个初值但对应的psl-arr就不可再赋值为NUL了也需对应malloc相应大小的空间
2、注意指定位置插入SLInsert与指定位置删除SLErase对pos参数的判定区别
对于SLInsertpos可取值size即实现尾插效果
对于SLErasepos不可取值sizearr[psl-size]实际是数组arr最后一个有效数据的下一个位置
3. 顺序表性能分析
优点物理空间连续便于利用下标随机访问
缺点1空间不够需扩容。
① 需要申请新的空间拷贝数据释放旧空间有一定性能消耗
② 一般增容呈2倍增长存在空间浪费
2头部或者中间位置的插入删除时涉及数据的移动时间复杂度为O(N)效率低下
注越界是不一定报错的系统对于越界的检查是设岗抽查以VS为例 int a[10];a[10] 1;a[11] 1;
当我们运行如上代码系统会报错 再运行下文代码 int a[10];a[12] 1;a[13] 1;
系统不会报错。说明系统只重点检查部分位置的越界情况。
