网网站建设与制作,ipad wordpress 应用,后台更改公司网站背景图片,任务发布网站建设一、顺序表的概念和结构 1、顺序表的概念#xff1a; 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构#xff0c;一般情况下采用数组存储。在数组上完成数据的增删查改。 2、顺序表的结构#xff1a;
#xff08;1#xff09;静态顺序表#xff1a;使…一、顺序表的概念和结构 1、顺序表的概念 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 2、顺序表的结构
1静态顺序表使用定长数组存储元素
缺点只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了空间开多了浪费开少了不够用。
// 顺序表的静态存储
#define N 10
typedef int SLDataType;typedef struct SeqList
{SLDataType array[N];// 定长数组size_t size;// 有效数据个数
}SeqList;2动态顺序表使用动态开辟的数组存储元素
优点动态顺序表可以根据需要动态的分配空间大小。
// 顺序表的动态存储
typedef int SLDataType; //类型重命名后续要存储其它类型时方便更改typedef struct SeqList
{SLDataType* a;// 指向动态开辟的数组size_t size;// 有效数据个数当前顺序表中已存放的数据个数size_t capacity;// 容量大小顺序表总共能够存放的数据个数
}SeqList;注size_t 数据类型表示 C 中任何对象所能达到的最大长度它是无符号整数。 二、动态顺序表的接口实现
1、创建文件 test.c主函数、测试顺序表各个接口功能SeqList.c动态顺序表接口函数的实现SeqList.h动态顺序表的类型定义、接口函数声明、引用的头文件 2、SeqList.h 头文件代码
// SeqList.h
#pragma once // 防止头文件被二次引用#includestdio.h
#includeassert.h // assert
#includestdlib.h // realloctypedef int SLDataType; // 后续要存储其它类型时方便直接更改// 顺序表的动态存储
typedef struct SeqList
{SLDataType* a; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小
}SeqList;// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 查看顺序表中的有效数据个数
size_t SeqListSize(const SeqList* psl);
// 修改指定下标位置的数据
void SeqListAt(SeqList* psl, size_t pos, SLDataType x); 三、在 SeqList.c 中实现各个接口函数
1、初始化顺序表
// 初始化顺序表
void SeqListInit(SeqList* psl)
{assert(psl); // 断言 -- 防止传进来的指针为空psl-a NULL; // 初始化顺序表为空psl-size 0; // 初始数据个数为0psl-capacity 0; // 初始空间容量为0
} 2、顺序表销毁
// 销毁顺序表
void SeqListDestroy(SeqList* psl)
{assert(psl); // 断言 -- 防止传进来的指针为空free(psl-a); // 释放动态开辟的空间psl-a NULL; // 置空psl-size 0; // 数据个数置为0psl-capacity 0; // 空间容量大小置为0
} 3、检查空间如果满了进行增容
// 检查顺序表容量是否满了好进行增容
void CheckCapity(SeqList* psl)
{if (psl-size psl-capacity) // 检查容量满了则增容{// 原来容量为0扩容为4不为0扩容为原来的2倍size_t newcapacity psl-capacity 0 ? 4 : 2 * (psl-capacity);psl-a (SeqList*)realloc(psl-a, sizeof(SLDateType) * newcapacity); // 扩容psl-capacity newcapacity; // 更新容量}
} 为什么不采取插一个数据增容一个空间的方式呢 因为这样做很麻烦代价也很大。一般情况下为了避免频繁的增容当空间满了之后我们不会选择一个一个的去增而是一次增容 2 倍当然也不会一次增容太大比如 3 倍 4 倍这样空间可能会造成浪费所以 2 倍是一个折中的选择。 注realloc 在开辟动态内存空间时如果传给它的是一个空指针那么他就会开辟一个新的内存空间用法类似malloc。 4、顺序表尾插
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x) // O(1)
{// 不需要断言 空指针也符合条件// 第一种写法/* CheckCapacity(psl); // 检查顺序表容量是否已满psl-a[psl-size] x; // 尾插数据psl-size; // 有效数据个数1 */// 第二种写法SeqListInsert(psl, psl-size, x);
} 5、顺序表尾删
// 顺序表尾删
void SeqListPopBack(SeqList* psl) // O(1)
{assert(psl); // 断言// 第一种写法/* assert(psl-size 0); // 尾删 -- 顺序表不能为空//psl-a[psl-size - 1] 0; // 不知道SLDataType是什么类型的数据不能冒然的直接赋值为0psl-size--; // 有效数据个数-1 */// 第二种写法SeqListErase(psl, psl-size - 1);
} 关于在程序中检查错误的方式 1温柔检查法 如果出现错误程序就不再继续执行。因为一般情况下程序运行成功就返回0则运行失败就返回-1。 2暴力检查法推荐如果发生错误程序会报警告可以直接知道出错位置。 // 温柔处理方式if (psl-size 0){psl-a[ps-size - 1] 0;psl-size--;}// 暴力处理方式assert(psl-size 0);psl-size--; 注不知道 SLDataType 是什么类型的数据不能冒然的将顺序表最后一个数据赋值为 0我们只需将有效数据个数 size 减 1 即可达到尾删的目的。 6、顺序表头插
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x) // O(n)
{// 头插不需要断言 空指针也符合条件/* CheckCapacity(psl); // 检查顺序表容量是否已满for (int i psl-size - 1; i 0; i--) // 顺序表中[0,size-1]的元素依次向后挪动一位{psl-a[i 1] psl-a[i];}psl-a[0] x; // 头插数据psl-size; // 有效数据个数1 */SeqListInsert(psl, 0, x);
} 7、顺序表头删
// 顺序表头删
void SeqListPopFront(SeqList* psl) // O(n)
{assert(psl); // 断言// 方法一/* assert(psl-size 0); //顺序表不能为空for (int i 1; i psl-size; i) // 顺序表中[1,size-1]的元素依次向前挪动一位{psl-a[i - 1] psl-a[i];}psl-size--; // 有效数据个数-1 */// 方法二SeqListErase(psl, 0);
} 8、顺序表打印
// 打印顺序表
void SeqListPrint(SeqList* ps)
{assert(ps); // 断言if (psl-size 0) // 顺序表为空{printf(顺序表为空\n);return;}// 顺序表不为空for (size_t i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
} 9、顺序表查找指定值
// 顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{assert(psl); // 断言for (int i 0; i psl-size; i){if (psl-a[i] x){return i; //查找到返回该值在数组中的下标}}return -1; // 没查找到
} 10、顺序表在pos位置插入x
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{assert(psl); // 断言assert(pos 0 pos (psl-size)); // 检查pos下标的合法性CheckCapity(psl);// 第一种写法/* size_t end psl-size;while (end pos){psl-a[end] psl-a[end - 1];end--;} *///第二种写法size_t i 0;for (i psl-size; i pos; i--) // 将pos位置后面的数据依次向后挪动一位{psl-a[i] psl-a[i - 1];}psl-a[pos] x; // 插入数据psl-size; // 有效数据个数1
} 注原先下面这种写法当顺序表为空 size 0 时会导致 i -1执行 i pos 时i 被算术转换成无符号数而无符号数的 -1 是一个值很大的正数远远大于 pos满足条件进入循环会造成越界访问。 int i 0;
for (i psl-size - 1; i pos; i--)psl-a[i 1] psl-a[i]; 注转换并不会改变 i 本身的值而是在执行 i pos 时生成一个临时值与 pos 进行比较。如果在顺序表头部pos 0插入数据i 最终也会减成 -1被算术转换后变成一个很大的数。 总结避免负数给到无符号数或者避免有符号数变成负数后被算术转换或整型提升后变成一个很大的数。按照第二种写法就可以避免 i 变成负数-1了。 实现了此接口顺序表头插和尾插相当于在下标为 0 和 psl - size-1 位置处插入数据。 11、顺序表删除pos位置的值
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl); // 断言assert(psl-size 0); // 顺序表不能为空assert(pos 0 pos psl-size); // 检查pos下标的合法性// 第一种写法/* size_t start pos;while (start psl-size-1){psl-a[start] psl-a[start 1];start;} *///第二种写法size_t i 0;for (i pos 1; i psl-size; i) // 将pos位置后面的数据依次向前挪动一位{psl-a[i - 1] psl-a[i];}psl-size--; // 有效数据个数-1
} 实现了此接口顺序表头删和尾删相当于删除下标为 0 和 psl - size-1 位置处的数据。 12、查看顺序表中的有效数据个数
// 查看顺序表中的有效数据个数
size_t SeqListSize(const SeqList* psl)
{assert(psl); // 断言return psl-size;
} 为什么不选择在主函数里面直接通过定义的结构体变量直接访问还要弄一个相关函数呢 在数据结构中如果要访问或者修改数据结构中的数据不要直接访问而是应该去调用它的函数来访问和修改这样会更加规范和安全也更方便检查出是否出现了越界等错误情况。 数组越界是不一定报错的系统对越界的检查是设岗检查。 越界读读了不属于自己的数据一般是检查不出来的往往并不会造成内存奔溃。 越界写缓冲区溢出如果是修改到标志位才会被检查出来会造成数据破坏严重会造成内存奔溃。 系统在数组末尾后设的有标志位越界写时恰好修改到标志位了就会被检查出来 13、修改指定下标位置的数据
// 修改指定下标位置的数据
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{assert(psl); // 断言assert(psl-size 0); // 顺序表不能为空assert(pos 0 pos psl-size); // 检查pos下标的合法性psl-a[pos] x; // 修改pos下标处对应的数据
} 四、代码整合
// SeqList.c
#include SeqList.h// 初始化顺序表
void SeqListInit(SeqList* psl)
{assert(psl); // 断言 -- 防止传进来的指针为空psl-a NULL; // 初始化顺序表为空psl-size 0; // 初始数据个数为0psl-capacity 0; // 初始空间容量为0
}// 销毁顺序表
void SeqListDestroy(SeqList* psl)
{assert(psl); // 断言 -- 防止传进来的指针为空free(psl-a); // 释放动态开辟的空间psl-a NULL; // 置空psl-size 0; // 数据个数置为0psl-capacity 0; // 空间容量大小置为0
}// 检查顺序表容量是否满了好进行增容
void CheckCapity(SeqList* psl)
{if (psl-size psl-capacity) // 检查容量满了则增容{// 原来容量为0扩容为4不为0扩容为原来的2倍size_t newcapacity psl-capacity 0 ? 4 : 2 * (psl-capacity);psl-a (SeqList*)realloc(psl-a, sizeof(SLDateType) * newcapacity); // 扩容psl-capacity newcapacity; // 更新容量}
}// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x) // O(1)
{SeqListInsert(psl, psl-size, x);
}// 顺序表尾删
void SeqListPopBack(SeqList* psl) // O(1)
{assert(psl); // 断言SeqListErase(psl, psl-size - 1);
}// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x) // O(n)
{SeqListInsert(psl, 0, x);
}// 顺序表头删
void SeqListPopFront(SeqList* psl) // O(n)
{assert(psl); // 断言SeqListErase(psl, 0);
}// 打印顺序表
void SeqListPrint(SeqList* ps)
{assert(ps); // 断言if (psl-size 0) // 顺序表为空{printf(顺序表为空\n);return;}// 顺序表不为空for (size_t i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}// 顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{assert(psl); // 断言for (int i 0; i psl-size; i){if (psl-a[i] x){return i; //查找到返回该值在数组中的下标}}return -1; // 没查找到
}// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{assert(psl); // 断言assert(pos 0 pos (psl-size)); // 检查pos下标的合法性CheckCapity(psl);size_t i 0;for (i psl-size; i pos; i--) // 将pos位置后面的数据依次向后挪动一位{psl-a[i] psl-a[i - 1];}psl-a[pos] x; // 插入数据psl-size; // 有效数据个数1
}// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl); // 断言assert(psl-size 0); // 顺序表不能为空assert(pos 0 pos psl-size); // 检查pos下标的合法性size_t i 0;for (i pos 1; i psl-size; i) // 将pos位置后面的数据依次向前挪动一位{psl-a[i - 1] psl-a[i];}psl-size--; // 有效数据个数-1
}// 查看顺序表中的有效数据个数
size_t SeqListSize(const SeqList* psl)
{assert(psl); // 断言return psl-size;
}// 修改指定下标位置的数据
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{assert(psl); // 断言assert(psl-size 0); // 顺序表不能为空assert(pos 0 pos psl-size); // 检查pos下标的合法性psl-a[pos] x; // 修改pos下标处对应的数据
}
