河南省两学一做网站,网站开发交接协议书,软件开发工资多少,华为公司网站建设方案目录
1. 顺序表介绍
2. 顺序表工程
2.1 顺序表定义
2.1.1 静态顺序表
2.1.2 动态顺序表
2.2顺序表接口
2.2.1 顺序表初始化
2.2.2 顺序表打印
2.2.3 顺序表销毁
2.2.4 顺序表数据插入
2.2.4.1 容量检查
2.2.4.2 顺序表尾插
2.2.4.3 顺序表头插
2.2.4.4 顺序表随机… 目录
1. 顺序表介绍
2. 顺序表工程
2.1 顺序表定义
2.1.1 静态顺序表
2.1.2 动态顺序表
2.2顺序表接口
2.2.1 顺序表初始化
2.2.2 顺序表打印
2.2.3 顺序表销毁
2.2.4 顺序表数据插入
2.2.4.1 容量检查
2.2.4.2 顺序表尾插
2.2.4.3 顺序表头插
2.2.4.4 顺序表随机插入
2.2.5 顺序表数据删除
2.2.5.1 顺序表尾删
2.2.5.2 顺序表头删
2.2.5.3 顺序表随机删除 2.2.6 顺序表查找
3. 顺序表总结反思 1. 顺序表介绍 顺序表顾名思义就是顺序储存数据的数据管理方式。在物理层面来看顺序表将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 因为顺序表采用的是一段物理地址连续的储存单元一次存储数据元素所以我们一般会采用数组的方式来存储。涉及到数组的存储我们便会有两种方式一种是静态的顺序表即使用定长的数组来存储元素而我们今天介绍的是另一种动态的顺序表即采用动态开辟的数组进行数据的存储。
2. 顺序表工程 对于一个顺序表工程我们一般模式需要分为三部分。 SeqList.h 为头文件其中包含库函数头文件的包含顺序表结构体的定义与声明接口函数的声明。 SeqList.c 包含接口函数的定义。 Test.c 是我们的测试源文件从这里进入main函数。 2.1 顺序表定义 在描述一个顺序表时我们需要多个顺序表的信息才能方便我们对其进行管理所以我们可以定义一个结构体其中包含顺序表的存储数组与元素个数等信息。
2.1.1 静态顺序表 我们前面提到静态顺序表采用的数据存储方式为定长数组所以在静态顺序表的结构体内需要包含数据存储的数组与已经存储的数据个数。
//静态顺序表
#define N 10typedef int SLDataType;typedef struct SeqList
{SLDataType data[N];//定长数组size_t size;//存储数据个数
}SeqList; 由于静态顺序表的数组大小已经给定所以很容易产生空间不够或者浪费过大的情况所以我们会更倾向于寻求动态开辟空间的方法来管理顺序表以此来灵活管理空间。
2.1.2 动态顺序表 想要管理好一个动态顺序表我们创建的结构体中不仅要有存储数据的数组与有效数据个数还应该有数组容量大小的说明以便于我们及时对顺序表的空间做出调整。
//动态顺序表typedef int SLDataType;typedef struct SeqList
{int size;//有效数据个数int capacity;//顺序表容量SLDataType* data;//顺序表动态开辟数组地址
}SL;
2.2顺序表接口 我们在使用顺序表时需要一些函数接口来帮助我们实现数据的插入与删除等功能所以最关键的部分也就是增删查改功能接口函数的实现。
2.2.1 顺序表初始化 当我们新建一个顺序表我们需要对其进行参数预置也就是初始化。
void SeqListInit(SL* ps)
{assert(ps);ps-size 0;ps-capacity 0;ps-data NULL;
}
2.2.2 顺序表打印 我们想要在屏幕上看到顺序表存储的数据内容即可调用打印函数将顺序表数据依次打印在屏幕上。
void SeqListPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-data[i]);}printf(\n);
}
2.2.3 顺序表销毁 当顺序表不再被使用时我们应该调用销毁函数即使销毁顺序表释放空间。
void SeqListDestroy(SL* ps)
{assert(ps);if (ps-data ! NULL){ps-size 0;ps-capacity 0;free(ps-data);ps-data NULL;}
}
2.2.4 顺序表数据插入 在管理顺序表数据时常常涉及到数据插入常见的插入数据的方式有头插即在顺序表地址最小头部的位置插入新的数据尾插即在顺序表地址最大尾部的位置插入新的数据随机插入即在指定下标位置插入新的数据。
2.2.4.1 容量检查 在插入数据的时候需要注意到容量的问题再每一次插入数据时我们都需要关注空间是否充足所以我们需要对容量进行检查。当容量不够时采用realloc函数来重新设置空间大小一般采取空间扩大为原先的二倍的方式。需要注意的是由于我们初始化容量为0所以扩容时要防止在0的基础上扩大二倍的情况。
void CheckCapacity(SL* ps)
{if (ps-size ps-capacity){return;}else{int newcapacity ps-capacity 0 ? 4 : 2 * (ps-capacity);SLDataType* tmp (SLDataType*)realloc(ps-data, sizeof(SLDataType) * newcapacity);if (tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capacity newcapacity;}
} 将容量检查打包成为一个函数在之后的插入过程中只需要调用该函数即可解决容量的问题。
2.2.4.2 顺序表尾插 尾插很容易只需要在数据最后一个元素size-1的后一个位置size存入新数据并令有效数据个数加一即可。
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);CheckCapacity(ps);ps-data[ps-size] x;ps-size;
}2.2.4.3 顺序表头插 头插时涉及到数据的移位即整体数据向后移动一个位置才能在头部有空间插入新的数据而不干扰原数据。我们可以采用循环来解决。
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);CheckCapacity(ps);int tmp ps-size;while (tmp){ps-data[tmp] ps-data[tmp - 1];tmp--;}ps-data[0] x;ps-size;
}
2.2.4.4 顺序表随机插入 随机插入时涉及到另一个参数即下标参数只需要采用头插的思想将指定下标后的数据向后移动一位即可。
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);CheckCapacity(ps);int tmp ps-size;while (tmp pos){ps-data[tmp] ps-data[tmp - 1];tmp--;}ps-data[pos] x;ps-size;
}
2.2.5 顺序表数据删除 与顺序表的插入类似顺序表的删除也有多种方式常见的删除数据的方式有头删即删除在顺序表地址最小头部的位置的数据尾删即删除在顺序表地址最大尾部的数据随机删除即删除在指定下标位置的数据。 删除不许要考虑容量但是需要关心有效数据个数是否为0使用assert断言即可。
2.2.5.1 顺序表尾删 尾删很简单只需要将有效数据个数减一即可至于原来的最后一个数据是多少不需要关心因为有效数据个数限制我们不会去考虑它。
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size 0);ps-size--;
}
2.2.5.2 顺序表头删 顺序表头删也涉及到数据覆盖的问题设计循环将每一位的后一位向前移动覆盖即可。
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size 0);int tmp 0;while (tmp ps-size - 1){ps-data[tmp] ps-data[tmp 1];tmp;}ps-size--;
}
2.2.5.3 顺序表随机删除 随机删除是删除指定下标的数据只需要将其后的数据参照头删的方式向前移动覆盖即可。
void SLErase(SL* ps, int pos)
{assert(ps);assert(ps-size 0);int tmp pos;while (tmp ps-size - 1){ps-data[tmp] ps-data[tmp 1];tmp;}ps-size--;
} 2.2.6 顺序表查找 查找要求查找指定数据若找到返回其下标否则返回-1。因此只需要遍历顺序表一一比较即可。
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-data[i] x){return i;}}return -1;
}
3. 顺序表总结反思 顺序表以其物理空间连续为最大的“卖点”同时由于其存储物理空间连续也延伸出了优劣势。 其优势在与因为物理空间连续所以访问数据很方便快捷。其劣势也是由于物理空间连续导致在头插和头删等操作时我们需要移动所有的数据来保持其物理空间连续的特性改变数据开销就会变得很大。
