郑州知名网站建设公司,蓝海基业做的网站好吗,网页特效大全,1688黄页大全1. 线性表
线性表(lina list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串......
线性表在逻辑上是线性结构#xff0c;也就是说连续的一条直线。但是在物理结构上并…1. 线性表
线性表(lina list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串......
线性表在逻辑上是线性结构也就是说连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 2. 顺序表实现
2.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为
1.静态顺序表使用定长数组存储。
2.动态顺序表使用动态开辟的数组存储。
#define N 100
// 静态顺序表
struct SeqList
{int arr[N];int size; // 有效数据个数
}; typedef int SLDataType;// 动态顺序表
typedef struct SeqList
{SLDataType* arr;int size; // 有效数据个数int capacity; // 空间大小
}SL; 注意静态顺序表只适用于确定知道需要多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态地分配空间大小所以下面我们实现动态顺序表。
2.2 顺序表初始化
// 顺序表初始化
void SLInit(SL* ps);
首先我们需要初始化数组数组首元素地址 ps-arr 置为NULL有效数字个数 size 和空间容量capacity 大小都置为0。
// 顺序表初始化
void SLInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;
}
2.3 顺序表销毁
// 顺序表销毁
void SLDestroy(SL* ps);
我们使用完顺序表之后都需要把顺序表进行销毁以免造成内存被占用和内存泄漏问题。
首先需要把开辟的空间 free 掉再将数组首元素地址 ps-arr 置为NULL有效数字个数 size 和空间容量 capacity 大小都置为0。
// 顺序表销毁
void SLDestroy(SL* ps)
{if (ps-arr){free(ps-arr);}ps-arr NULL;ps-size ps-capacity 0;
}
2.4 顺序表打印
// 顺序表打印
void SLPrint(SL s);
为了更好地对程序进行调试我们这里需要写一个打印程序以便我们测试每一个接口函数。
// 顺序表打印
void SLPrint(SL s)
{for (int i 0; i s.size; i){printf(%d , s.arr[i]);}printf(\n);
}
附我们完成这些前导工作接下来我们就可以正式编写顺序表的功能函数。
2.5 顺序表尾插
// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x);
我们得分两种情况 不过在尾插元素之前我们必须得确保数组空间大小是足够的也就是说得有空间插入元素。如果说空间容量不够的话我们就得扩容所以说在尾插之前我们得判断空间大小是否足够不够咱就扩容。我们这里得写一个内存容量检查函数。
这里我们还得注意一个点就是我们内存空间不够的情况下一般我们是以2倍或者3倍 capacity(容量) * 2 * sizeof(数据类型) 去开辟空间。
// 检查内存函数
void SLCheckCapacity(SL* ps)
{// 插入数据之前看空间够不够if (ps-capacity ps-size){// 申请空间// 申请之前要判断一下capacity是否为0int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;错误写法这里不要直接这样写要不然申请空间失败的话前面的数据会丢失//ps-arr (SLDataType*)realloc(ps-arr, newCapacity * 2 * sizeof(SLDataType));// 正确写法SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * 2 * sizeof(SLDataType));// 如果申请失败if (tmp NULL){perror(realloc fail!);exit(1); // 直接退出程序不再继续执行}// 空间申请成功ps-arr tmp;ps-capacity newCapacity;}
}
检查开辟完空间后我们就可以进行下一步顺序表尾插接口函数编写。
步骤
① 程序开始前我们要断言一下确保指针是有效的不是NULL
② 检查内存是否足够
③ 将我们需要的 x 尾插入下标 ps-size 的位置插完之后数组元素总个数 ps-size 得加1。
// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{温柔的解决方式//if (ps NULL)// return;assert(ps); // 等价于assert(ps ! NULL)// 检查内存SLCheckCapacity(ps);/*ps-arr[ps-size] x;ps-size;*/ps-arr[ps-size] x;
}
每次写完一个函数接下来我们都得测试一下尾插函数接口谨记
测试程序
void SLTest01()
{SL sl;// 顺序表初始化SLInit(sl);// 增删查改操作// 测试尾插SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPrint(sl);// 顺序表销毁SLDestroy(sl);
}int main()
{SLTest01();return 0;
}
运行结果依次尾插1234 2.6 顺序表头插
// 顺序表头插
void SLPushFront(SL* ps, SLDataType x);
我们也得分两种情况 不过我们在头插元素之前我们也得确保数组空间大小是足够的所以我们头插之前也得调用一下内存检查函数 SLCheckCapacity保证我们内存容量是足够的。
步骤
① 程序开始前我们要断言一下确保指针是有效的不是NULL
② 检查内存是否足够
③ 将我们需要的 x 头插入下标 0 的位置插完之后数组元素总个数 ps-size 得加1。 // 顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);// 检查内存SLCheckCapacity(ps);// 先让顺序表中已有的数据整体往后挪动一位for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1]; // arr[1] arr[0]}ps-arr[0] x;ps-size;
}
测试程序
void SLTest01()
{SL sl;// 顺序表初始化SLInit(sl);// 增删查改操作// 测试尾插SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPrint(sl);// 测试头插SLPushFront(sl, 5);SLPushFront(sl, 6);SLPrint(sl);// 顺序表销毁SLDestroy(sl);
}int main()
{SLTest01();return 0;
}
运行结果先尾插1234然后头插56最终结果是651234 2.7 顺序表尾删
// 顺序表尾删
void SLPopBack(SL* ps);
我们删除数据不是说要把这个数据从数组中去除而是说我们这个所谓的“删除的数据”不能被访问所以我们只需把数组中有效的元素个数 size - 1 即可并不需要把这个数据变成什么其他的数这是非常多余的(如果非要更改删除数据也不是不可)。 步骤
① 程序开始前我们要断言一下确保指针是有效的不是NULL
② 断言一下数据有效个数不能为0
③ 将数据有效个数 size - 1。
// 顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size); // 顺序表有效数字不能为0// 顺序表不能为空//ps-arr[ps-size - 1] -1; // 这行代码有点多余ps-size--;
}
测试程序
void SLTest01()
{SL sl;// 顺序表初始化SLInit(sl);// 增删查改操作// 测试尾插SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPrint(sl);// 测试头插SLPushFront(sl, 5);SLPushFront(sl, 6);SLPrint(sl);// 测试尾删SLPopBack(sl);SLPrint(sl);// 顺序表销毁SLDestroy(sl);
}int main()
{SLTest01();return 0;
}
运行结果先尾插1234然后头插56最后进行尾删最终得到的结果是65123 附尾删还是非常简单的
2.8 顺序表头删
// 顺序表头删
void SLPopFront(SL* ps);
头删数据之后我们还需要每个数据往前一位最后 size - 1。 步骤
① 程序开始前我们要断言一下确保指针是有效的不是NULL
② 断言一下数据有效个数不能为0
③ 然后将每个数据往前移动一位
③ 将数据有效个数 size - 1。
// 顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size); // 顺序表有效数字不能为0// 数据整体往前挪动一位for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1]; // 最后一次arr[size - 2] arr[size - 1]}ps-size--;
}
测试程序
void SLTest01()
{SL sl;// 顺序表初始化SLInit(sl);// 增删查改操作// 测试尾插SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPrint(sl);// 测试头插SLPushFront(sl, 5);SLPushFront(sl, 6);SLPrint(sl);// 测试尾删SLPopBack(sl);SLPrint(sl);// 测试头删SLPopFront(sl);SLPrint(sl);// 顺序表销毁SLDestroy(sl);
}int main()
{SLTest01();return 0;
}
运行结果先尾插1234然后头插56然后进行尾删再进行头删最终得到的结果是5123 顺序表续顺序表--续C语言详细版-CSDN博客
