目录一、线性表的定义二、顺序表的定义三、顺序表的定义及初始化四、顺序表的插入五、顺序表的删除六、顺序表的修改七、顺序表的查找八、顺序表的显示九、测试主程序一、线性表的定义线性表是一种基本的数据结构它是由n个数据元素a[1]、a[2]、...、a[n]组成的有限序列。 线性表中的数据元素之间呈现出一对一的顺序关系每个元素都有一个前驱和后继元素除了第一个元素没有前驱最后一个元素没有后继它可以用顺序存储结构和链式存储结构来实现。 举一个例子一个班级的学生名单可以看作是一个线性表其中每一个学生都是一个数据元素学生名单中的数据元素之间存在一定的顺序关系每个学生都有一个前一个和后一个学生除了第一个学生没有前一个学生最后一个学生没有后一个学生。如果使用顺序存储结构来实现学生名单那么每个学生的信息将被存储在一个数组中如果使用链式存储结构可以将每个学生的信息存储在一个链表的节点中。无论是使用数组还是链表都可以对学生名单进行插入、删除、查找和遍历等常见的操作这些操作都是线性表的基本操作。 线性表作为一种基本的数据结构类型在计算机存储器中的表示一般有两种形式一种是顺序存储一种是链式存储。二、顺序表的定义线性表的顺序存储又叫顺序表。线性表的顺序存储是指将数据元素按照其逻辑顺序依次存储在一组连续的物理位置上通过数组来实现。顺序存储结构以连续的存储单元顺序存放线性表的元素可以直接访问元素查找和遍历较快但插入和删除操作需要移动大量元素效率较低。 线性表的顺序存储可以用一维数组来实现。数组的下标从0开始表示元素在数组中的位置。 具体实现步骤如下 1. 定义一个数组用来存储线性表中的元素数组大小为线性表的长度 2. 将线性表中的元素按照逻辑顺序存储在数组中即将第i个元素存储在数组中下标为i-1的位置上 3. 可以通过下标访问具体的元素数组下标从0开始第i个元素的下标为i-1 4. 可以通过数组下标修改或者查询元素的值 5. 插入元素时需要将插入点之后的元素依次后移然后在插入点处插入新元素 6. 删除元素时需要将删除点之后的元素依次前移然后删除最后一个元素。 顺序表具有随机存取的优点可以直接按照下标访问任意位置的元素。但是因为删除或插入操作时需要移动大量元素所以其插入和删除操作效率较低。三、顺序表的定义及初始化//顺序表的定义 #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; // 存储顺序表的数组 int length; // 顺序表长度 } sqlist_t; //顺序表的初始化 sqlist_t *sqlist_init(void) { sqlist_t *list (sqlist_t *)malloc(sizeof(sqlist_t)); list-length 0; // 顺序表的长度初始化为0 memset(list-data, 0, sizeof(list-data)); // 清空数组的值 return list; }四、顺序表的插入插入元素时需要将插入点之后的元素依次后移然后在插入点处插入新元素 例如在 {1,2,3,4,5} 的第 3 个位置上插入元素 6实现过程如下1. 遍历至顺序表存储第 3 个数据元素的位置如图所示2. 将元素 3 以及后续元素 4 和 5 整体向后移动一个位置如图所示3.将新元素 6 放入腾出的位置如图所示// 顺序表的插入 int sqlist_insert(sqlist_t *list, int index, int val) { // index 1 , index 是从1 开始的 // index list-length 1 大于顺序表的长度是 list-length if (index 1 || index list-length 1 || list-length MAXSIZE) { return -1; // 失败 -1 } // 最后一个元素开始往后移动 // 倒数第二个元素 移动到倒数第一个元素的位置 一直移动到index 的位置 // index 指向的元素也要往后移动 for (int i list-length - 1; i index - 1; i--) { // 4 3 2 list-data[i 1] list-data[i]; // 往后移动1个元素 } list-data[index - 1] val; // 插入元素 list-length; // 顺序表的长度增加1 return 0; }五、顺序表的删除删除元素时需要将删除点之后的元素依次前移然后删除最后一个元素。例如从 {1,2,3,4,5} 中删除元素 3 的过程如图所示// 顺序表的删除 int sqlist_delete(sqlist_t *list, int index, int *pval) { // index 1 , index 是从1 开始的 // index list-length 1 大于顺序表的长度是 list-length if (index 1 || index list-length 1) { return -1; // 失败 -1 } *pval list-data[index - 1]; // 先将删除的元素赋值给pval // 把后面的元素往前移动 for (int i index - 1; i list-length - 1; i) { list-data[i] list-data[i 1]; // 往前移动1个元素 } list-length--; // 顺序表的长度减少1 return 0; }六、顺序表的修改// 顺序表的修改 int sqlist_modify(sqlist_t *list, int index, int newval) { // index 1 , index 是从1 开始的 // index list-length 1 大于顺序表的长度是 list-length if (index 1 || index list-length 1) { return -1; // 失败 -1 } list-data[index - 1] newval; // 把newval 的值更新到数组内 return 0; }七、顺序表的查找// 顺序表的查找 int sqlist_search(sqlist_t *list, int val) { for (int i 0; i list-length; i) { if (val list-data[i]) // 查找元素 { return i 1; // 找到返回元素的位置 } } return 0; // 没有找到返回0 }八、顺序表的显示// 顺序表的显示 int sqlist_print(sqlist_t *list) { for (int i 0; i list-length; i) { printf(%d , list-data[i]); } printf(\n); return 0; }九、测试主程序//测试主程序 int main(int argc, char const *argv[]) { sqlist_t *L sqlist_init(); for (int i 0; i 5; i) { sqlist_insert(L, i 1, i 1); } sqlist_print(L); sqlist_insert(L, 3, 6); sqlist_print(L); int value; sqlist_delete(L, 3, value); printf(删除的元素是%d\n, value); sqlist_print(L); sqlist_delete(L, 3, value); printf(删除的元素是%d\n, value); sqlist_print(L); sqlist_modify(L, 3, 40); sqlist_print(L); int pos sqlist_search(L, 4); if (pos 0) // 查找元素 { printf(%d 查找的元素在第%d个位置\n, 4, pos); } else { printf(%d 查找的元素不存在\n, 4); } pos sqlist_search(L, 40); if (pos 0) // 查找元素 { printf(%d 查找的元素在第%d个位置\n, 40, pos); } else { printf(%d 查找的元素不存在\n, 40); } return 0; }
