郴州买房网站,wordpress网站图片,昆山网站公司,品牌网站建设十小蝌蚪文中代码源文件已上传#xff1a;数据结构源码 -上一篇 NULL | 初级数据结构#xff08;二#xff09;——链表 下一篇-
1、顺序表的特点
1.1、数组 现实中数据记录一般都记录在表格中#xff0c;如进货单、菜单等#xff0c;它们的最大特点就是… 文中代码源文件已上传数据结构源码 -上一篇 NULL | 初级数据结构二——链表 下一篇-
1、顺序表的特点
1.1、数组 现实中数据记录一般都记录在表格中如进货单、菜单等它们的最大特点就是有序。表述中可以用第一项、第二项、第 n 项来描述表格中某个数据或者某串数据。在 C 语言中数组的特点恰好匹配此功能。 由于数组在内存中的储存方式就如同列表依序排布对数组可以用 arr[n] 或者 *(arrn) 来迅速获得第 n-1 项数据。再加上而且数组是 C 语言的原生类型创建数组极其便利作为有序数据的载体着实是不二之选。
1.2、结构 顺序表为了方便使用除了用数组作为数据载体外一般还包含记录数组空间大小和开辟空间大小的两个变量。常以结构体将这三个变量作为成员变量进行囊括。主要有两种创建方式 柔性数组顺序表 Sequence table with flexible array #include stdlib.h//重定义数据类型
typedef int DATA;//创建并重定义结构体类型
typedef struct SeqTab
{int size; //数据长度int capacity; //数据空间大小DATA arr[]; //数据载体柔性数组
}SeqTab;int main()
{//开辟结构体空间SeqTab* sqList (SeqTab*)malloc(sizeof(SeqTab) sizeof(DATA)*4);//初始化数据长度及空间大小sqList-size 0;sqList-capacity 4;return 0;
} 数组指针顺序表 Sequence table with array pointer #include stdlib.h//重定义数据类型
typedef int DATA;//创建并重定义结构体类型
typedef struct SeqTab
{int size; //数据长度int capacity; //数据空间大小DATA* arr; //数据载体数组指针
}SeqTab;int main()
{//创建结构体变量SeqTab sqList;//开辟数据载体数组空间sqList.arr (DATA*)malloc(sizeof(DATA)*4);//初始化数据长度及空间大小sqList.size 0;sqList.capacity 4;return 0;
}
2、顺序表创建 接下来以数组指针顺序表为例进行演示。
2.1、文件结构 seqTab.h 用于创建结构体类型及声明函数 sqFunction.c 用于创建顺序表初始化及增删改查的函数 main.c 仅创建 main 函数用作测试。
2.2、前期工作 在 seqTab.h 中先写入以下内容
#include stdio.h
#include stdlib.h
#include assert.h//用于初始化顺序表时开辟空间
#define INIT_SIZE 4//顺序表数据类型方便顺序表储存数据类型修改
typedef int DATATYPE;//创建顺序表结构体类型
typedef struct SeqTab
{DATATYPE* data;int size;int capacity;
}SeqTab;//---------------------函数声明---------------------
//初始化顺序表
extern void DataInit(SeqTab*);//销毁顺序表
extern void DataDestory(SeqTab*);//打印顺序表
extern void DataPrint(const SeqTab*); 在 sqFunction.c 中包含 seqTab.h 并分别创建一个初始化顺序表和销毁顺序表的函数
#include seqTab.h//初始化顺序表
void DataInit(SeqTab* sq)
{//断言确保结构体指针不为空assert(sq);//为顺序表开辟空间sq-data (DATATYPE*)malloc(INIT_SIZE * sizeof(DATATYPE));//加入判断防止空间开辟失败if (sq-data NULL){perror(Malloc Fail);return;}//初始化记录数据长度及开辟空间长度的变量sq-size 0;sq-capacity INIT_SIZE;
}//销毁顺序表
void DataDestory(SeqTab* sq)
{//断言确保结构体指针不为空assert(sq);//释放顺序表数据空间free(sq-data);//数组指针置空sq-data NULL;//数组长度及空间尺寸全部置0sq-size 0;sq-capacity 0;
}//打印顺序表
void DataPrint(const SeqTab* sq)
{//断言确保结构体指针不为空assert(sq);//遍历顺序表并逐个数据打印for (int i 0; i sq-size; i){printf(%d , sq-data[i]);}printf(\n);
} 最后在 main.c 中包含 seqTab.h并创建一个顺序表及初始化
#include seqTab.hint main()
{//创建顺序表SeqTab sqList;//初始化顺序表DataInit(sqList);return 0;
} 至此前期工作准备完毕之后便是对顺序表的数据进行增删改查。
3、顺序表操作
3.1、增 插入数据一般为头部插入数据、尾部插入数据及指定位置插入数据。插入数据时除了写入数据到数组中还需时刻判断开辟的空间尺寸是否足以容纳已有数据。 先将以下三个函数声明添加到 seqTab.h 中
//指定位置插入数据
extern void DataInsert(SeqTab*, int, DATATYPE);
//头部插入数据
extern void DataPushHead(SeqTab*, DATATYPE);
//尾部插入数据
extern void DataPushTail(SeqTab*, DATATYPE); 然后便是 DataInsert 函数。如图 据此可以轻松写出其代码。以下写入 sqFunction.c 中
void DataInsert(SeqTab* sq, int pos, DATATYPE data)
{//数据有效性判断assert(sq);if (pos 0 || pos sq-size){printf(Illegal Position : %d\n, pos);return;}//空间不足则创建空间if (sq-size 1 sq-capacity){//申请新空间DATATYPE* ptr_newSqData (DATATYPE*)realloc(sq-data, sizeof(DATATYPE) * (sq-capacity * 2));//空间申请结果判断if (ptr_newSqData NULL){perror(Realloc Fail);return;}//赋予新空间地址sq-data ptr_newSqData;//空间大小记录翻倍sq-capacity * 2;}//数据后移直至腾出 pos 位置的空间for (int i sq-size; i pos; i--){sq-data[i] sq-data[i - 1];}//写入数据*(sq-data pos) data;//数据长度1sq-size;
} 至于头插尾插数据只不过是上述函数 pos 位置的区别。因此
//pos 0 便是头插
void DataPushHead(SeqTab* sq, DATATYPE data)
{DataInsert(sq, 0, data);
}
//pos 数据尺寸便是尾插
void DataPushTail(SeqTab* sq, DATATYPE data)
{DataInsert(sq, sq-size, data);
} 在 main 函数里写入下列代码验证一下 DataInsert(sqList, 10, 32); //报错DataPushTail(sqList, 10);DataPrint(sqList); //打印 10DataPushHead(sqList, 20);DataPrint(sqList); //打印 20 10DataPushHead(sqList, 3);DataPushTail(sqList, 6);DataPushHead(sqList, 8);DataPushHead(sqList, 7);DataPushHead(sqList, 2);DataPushTail(sqList, 100);DataPushTail(sqList, 432);DataPrint(sqList); //打印 2 7 8 3 20 10 6 10 432 结果与预期无误。至此插入功能便已完成。
3.2、删 正如插入数据分为头插、尾插及指定插删除也分头删及任意位删。与插入相反删除数据需要在数据删除结束后关注数据长度与开辟的数据空间当空间分配过大时对多余空间进行回收。 同样先将以下三个函数声明添加到 seqTab.h 中
//指定位置删除数据
extern void DataRemove(SeqTab*, int);
//删除头部数据
extern void DataPopHead(SeqTab*);
//删除尾部数据
extern void DataPopTail(SeqTab*); DataRemove 函数流程图如下 根据图中逻辑在 sqFunction.c 中写入以下
void DataRemove(SeqTab* sq, int pos)
{//数据有效性判断assert(sq);if (pos 0 || pos sq-size - 1){printf(Illegal Position : %d\n, pos);return;}//列表不为空则执行if (sq-size - 1 0){//由 pos 位开始之后所有数据前移 1 位for (int i pos; i sq-size - 1; i){sq-data[i] sq-data[i 1];}//数据长度-1sq-size--;}//开辟空间过大则执行if (sq-size sq-capacity / 2){//申请新空间DATATYPE* ptr_newSqData (DATATYPE*)realloc(sq-data, sizeof(DATATYPE) * (sq-capacity / 2));//空间申请结果判断if (ptr_newSqData NULL){perror(Realloc Fail);return;}//赋予新空间地址sq-data ptr_newSqData;//空间大小记录减半sq-capacity / 2;}
} 至于头删尾删数据也同样是上述函数 pos 位置的区别
//头删 pos 0
void DataPopHead(SeqTab* sq)
{DataRemove(sq, 0);
}
//尾删 pos 数据长度-1
void DataPopTail(SeqTab* sq)
{DataRemove(sq, sq-size - 1);
} 之后同样是验证将以下代码写到之前测试代码之后 DataRemove(sqList, 100); //报错DataRemove(sqList, 3);DataPrint(sqList); //打印 2 7 8 20 10 6 100 432DataPopHead(sqList);DataPrint(sqList); //打印 7 8 20 10 6 100 432DataPopTail(sqList);DataPrint(sqList); //打印 7 8 20 10 6 100DataPopTail(sqList);DataPopTail(sqList);DataPopTail(sqList);DataPopTail(sqList);DataPopTail(sqList);DataPrint(sqList); //打印 7DataPopTail(sqList);DataPopTail(sqList);DataPrint(sqList); //因为 size 0 pos -1 报错 删除数据功能完毕。
3.3、改 改数据的功能实现起来逻辑上毫无难度可言。以下函数声明添加到 seqTab.h 中
//修改指定位置数据
extern void DataModify(SeqTab*, int, DATATYPE); 在 sqFunction.c 中写入
void DataModify(SeqTab* sq, int pos, DATATYPE data)
{//数据有效性判断assert(sq);if (pos 0 || pos sq-size - 1){printf(Illegal Position : %d\n, pos);return;}//修改数据sq-data[pos] data;
} 在 main 函数中追加以下代码验证 for (int i 0; i 10; i){DataPushTail(sqList, i);}DataPrint(sqList); //打印 0 1 2 3 4 5 6 7 8 9DataModify(sqList, 100, 30); //报错DataModify(sqList, 3, 30);DataPrint(sqList); //打印 0 1 2 30 4 5 6 7 8 9 完毕。
3.4、查 查到数据返回该数据的位置查不到返回 -1 。同样很简单。 seqTab.h 中写入声明
//在表中查找数据
extern int DataSearch(SeqTab*, DATATYPE); 然后是 sqFunction.c 中写入
int DataSearch(SeqTab* sq, DATATYPE data)
{//数据有效性判断assert(sq);//遍历数组for (int i 0; i sq-size; i){//如果找到数据则返回下标if (sq-data[i] data){return i;}}//遍历完毕仍找不到数据返回 -1return -1;
} main 函数中验证 int num 1200;int pos DataSearch(sqList, num);if (pos -1){printf(The number \%d\ is not exist!\n, num);}else{printf(The position of number \%d\ is %d\n, num, pos);}//打印不存在num 9;pos DataSearch(sqList, num);if (pos -1){printf(The number \%d\ is not exist!\n, num);}else{printf(The position of number \%d\ is %d\n, num, pos);}//打印 9DataModify(sqList, DataSearch(sqList, 8), 11001);DataPrint(sqList); //打印 0 1 2 30 4 5 6 7 11001 9 至此增删改查功能实现均已完毕。除此之外还有排序、截断等其他一系列可以自定的操作。总之操作顺序表就是操作数组实现起来难度几乎为 0 。
