坪山网站建设,wordpress主题4mudi,哈尔滨酒店网站建设,注册公司需要什么材料目录
一、线性表的定义和特点
二、线性表的顺序表示和实现
2.1 - 线性表的顺序存储表示
2.2 - 顺序表中基本操作的实现
三、练习
3.1 - 移除元素
3.2 - 删除有序数组中的重复项
3.3 - BC100 有序序列合并
3.4 - 88.合并两个有序数组
四、顺序表的问题及思考 线性表、…目录
一、线性表的定义和特点
二、线性表的顺序表示和实现
2.1 - 线性表的顺序存储表示
2.2 - 顺序表中基本操作的实现
三、练习
3.1 - 移除元素
3.2 - 删除有序数组中的重复项
3.3 - BC100 有序序列合并
3.4 - 88.合并两个有序数组
四、顺序表的问题及思考 线性表、栈、队列、串和数组都属于线性结构。线性结构的基本特点是除了第一个元素无直接前驱最后一个元素无直接后继之外其他每个数据元素都有一个前驱和后继。线性表是最基本且最常用的一种线性结构同时也是其他数据结构的基础尤其单链表是贯穿整个数据结构课程的基本技术。 一、线性表的定义和特点
由 nn 0个数据特性相同的元素构成的有限序列称为线性表Linear List。
线性表中元素的个数 nn 0定义为线性表的长度n 0 时称为空表。
对于非空的线性表或线性结构其特点是 存在唯一的一个被称作第一个的数据元素 存在唯一的一个被称作最后一个的数据元素 除第一个外结构中的每个数据元素均只有一个前驱 除最后一个外结构中的每个数据元素均只有一个后继。 二、线性表的顺序表示和实现
2.1 - 线性表的顺序存储表示
线性表的顺序表示指的是用一组地址连续的存储单元依次存放线性表的数据元素这种表示也称作线性表的顺序存储结构或顺序映像。
顺序存储结构的线性表又称为顺序表Sequential List。其特点是逻辑上相邻的数据元素其物理次序也是相邻的。
线性表的顺序存储结构是一种随机存取的存储结构即只要确定了线性表的起始位置基地址线性表中任一数据元素都可以在 O(1) 时间内存取。
由于高级程序设计语言中的数组类型也有随机存取的特性因此可以用数组来描述数据结构中的顺序存储结构。
顺序表的静态存储
#define MAXSIZE 100 // 静态顺序表可能达到的最大长度
typedef struct SeqList
{SLDataType elem[MAXSIZE];int count;
}SeqList; 元素类型定义中的 SLDataType 数据类型是为了描述统一而自定义的在实际应用中用户可根据实际需要具体定义表中数据元素的数据类型例如 typedef int SLDataType;。 count 不仅能表示顺序表中当前数据元素的个数还能表示第一个未存放数据元素的数组下标。 不过静态顺序表的缺点也是很明显的其只适用于确定知道需要存储多少数据元素的场景因为静态顺序表的定长数组如果开大了可能导致浪费但如果开小了又可能不够用。所以现实中基本都是使用动态顺序表根据需要动态分配空间大小。顺序表的动态存储
typedef struct SeqList
{SLDataType* elem;int count;int capacity; // 动态顺序表的最大容量
}SeqList; 2.2 - 顺序表中基本操作的实现
SeqList.h
#pragma once// 动态顺序表
typedef int SLDataType;#define DEFAULT_CAPACITY 5 // 容量的默认大小typedef struct SeqList
{SLDataType* elem;int count;int capacity;
}SeqList;// 基本操作
typedef int Status;#define OK 1
#define ERROR 0void SeqListInit(SeqList* psl); // 初始化Status CheckCapacity(SeqList* psl); // 检查当前数据元素个数考虑是否需要扩容void SeqListPushBack(SeqList* psl, SLDataType e); // 尾插void SeqListPopBack(SeqList* psl); // 尾删void SeqListPushFront(SeqList* psl, SLDataType e); // 头插void SeqListPopFront(SeqList* psl); // 头删void SeqListInsert(SeqList* psl, int pos, SLDataType e); // 在 pos 位置插入 evoid SeqListErase(SeqList* psl, int pos); // 删除 pos 位置的元素int SeqListFind(SeqList* psl, SLDataType e); // 查找void SeqListPrint(SeqList* psl); // 打印 void SeqListDestroy(SeqList* psl); // 销毁
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1#include SeqList.h
#include stdio.h
#include stdlib.h
#include assert.h// 初始化
void SeqListInit(SeqList* psl)
{assert(psl);psl-elem (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_CAPACITY);if (NULL psl-elem){perror(malloc failed!);exit(1);}psl-count 0;psl-capacity DEFAULT_CAPACITY;
}// 检查当前数据元素个数考虑是否需要扩容
Status CheckCapacity(SeqList* psl)
{assert(psl);if (psl-count psl-capacity){SLDataType* tmp (SLDataType*)realloc(psl-elem, sizeof(SLDataType) * 2 * psl-capacity);if (NULL tmp){perror(realloc failed!);return ERROR;}psl-elem tmp;psl-capacity * 2;}return OK;
}// 尾插
void SeqListPushBack(SeqList* psl, SLDataType e)
{assert(psl);// 考虑是否需要扩容if (CheckCapacity(psl) ERROR){return;}// 尾插psl-elem[psl-count] e;
}// 尾删
void SeqListPopBack(SeqList* psl)
{assert(psl);// 判断是否为空表if (psl-count 0){return;}// 尾删--psl-count;
}// 头插
void SeqListPushFront(SeqList* psl, SLDataType e)
{assert(psl);// 考虑是否需要扩容if (CheckCapacity(psl) ERROR) // 扩容失败{return;}// 头插for (int end psl-count - 1; end 0; --end){psl-elem[end 1] psl-elem[end];}psl-elem[0] e;psl-count;
}// 头删
void SeqListPopFront(SeqList* psl)
{assert(psl);// 判断是否为空表if (psl-count 0){return;}// 头删for (int begin 1; begin psl-count; begin){psl-elem[begin - 1] psl-elem[begin];}--psl-count;
}// 在 pos 位置插入 e
void SeqListInsert(SeqList* psl, int pos, SLDataType e)
{assert(psl);// 当 pos 0 时即相当于头插当 pos psl-count即相当于尾插if (pos 0 || pos psl-count){return;}// 考虑是否需要扩容if (CheckCapacity(psl) ERROR) // 扩容失败{return;}// 插入for (int end psl-count - 1; end pos; --end){psl-elem[end 1] psl-elem[end];}psl-elem[pos] e;psl-count;
}// 删除 pos 位置的元素
void SeqListErase(SeqList* psl, int pos)
{assert(psl);// 当 pos 0 时即相当于头删当 pos psl-count - 1 时即相当于尾删if (pos 0 || pos psl-count){return;}// 删除for (int begin pos 1; begin psl-count; begin){psl-elem[begin - 1] psl-elem[begin];}--psl-count;
}// 查找
int SeqListFind(SeqList* psl, SLDataType e)
{for (int i 0; i psl-count; i){if (psl-elem[i] e){return i;}}return -1;
}// 打印不通用
void SeqListPrint(SeqList* psl)
{assert(psl);for (int i 0; i psl-count; i){printf(%d , psl-elem[i]);}printf(\n);
}// 销毁
void SeqListDestroy(SeqList* psl)
{free(psl-elem);psl-elem NULL;psl-count 0;psl-capacity DEFAULT_CAPACITY;
} 断言assert是一种除错机制用于验证代码是否符合编码人员的预期。编码人员在开发期间应该对函数的参数、代码中间执行结果合理地使用断言机制确保程序地缺陷尽量在测试阶段被发现即 assert 只在 debug 版本中有效在 release 版本中无效。 在 SeqListInsert 函数中当 pos psl-count 时该函数就相当于尾插当 pos 0 时该函数就相当于头插因此可以分别对 SeqListPushBack 和 SeqListPushFront 函数做如下修改
void SeqListPushBack(SeqList* psl, SLDataType e)
{SeqListInsert(psl, psl-count, e);
}void SeqListPushFront(SeqList* psl, SLDataType e)
{SeqListInsert(psl, 0, e);
}
在 SeqListErase 函数中当 pos psl-count - 1 时该函数就相当于尾删当 pos 0 时该函数就相当于头删因此可以分别对 SeqListPopBack 和 SeqListPopFront 函数做如下修改
void SeqListPopBack(SeqList* psl)
{SeqListErase(psl, psl-count - 1);
}void SeqListPopFront(SeqList* psl)
{SeqListErase(psl, 0);
} 三、练习
3.1 - 移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1 输入nums [3,2,2,3], val 3 输出2, nums [2,2] 解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。 示例 2 输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3] 解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 提示 0 nums.length 100 0 nums[i] 50 0 val 100
代码实现一暴力求解
int removeElement(int* nums, int numsSize, int val)
{for (int i 0; i numsSize; i){if (nums[i] val){for (int j i 1; j numsSize; j){nums[j - 1] nums[j]; }--numsSize;--i;}}return numsSize;
} 该算法最坏的时间复杂度为 O(n^2)空间复杂度为 O(1)。 代码实现二快慢双指针
int removeElement(int* nums, int numsSize, int val)
{int slow 0; // slow 始终是第一个未存放数据元素的数组下标for (int fast 0; fast numsSize; fast){if (nums[fast] ! val){nums[slow] nums[fast];}}return slow;
} 该算法的时间复杂度是 O(n)空间复杂度是 O(1)。 3.2 - 删除有序数组中的重复项
给你一个 升序排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度所以必须将结果放在数组 nums 的第一部分。更规范地说如果在删除重复项之后有 k 个元素那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1 输入nums [1,1,2] 输出2, nums [1,2,_] 解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2 输入nums [0,0,1,1,1,2,2,3,3,4] 输出5, nums [0,1,2,3,4] 解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。 提示 1 nums.length 3 * 10^4 -10^4 nums[i] 10^4 nums 已按 升序 排列
代码实现快慢双指针
int removeDuplicates(int* nums, int numsSize)
{int slow 0; // slow 始终是最后一个已存放数据元素的数组下标for (int fast 1; fast numsSize; fast){if (nums[fast] ! nums[slow]){nums[slow] nums[fast];}}return slow 1;
} 该算法的时间复杂度是 O(n)空间复杂度是 O(1)。 3.3 - BC100 有序序列合并
描述
输入两个升序排列的序列将两个序列合并为一个有序序列并输出。
数据范围1 n, m 1000序列中的值满足 0 val 30000
输入描述
输入包含三行
第一行包含两个正整数 n, m用空格分隔。n 表示第二行第一个升序序列中数字的个数m 表示第三行第二个升序序列中数字的个数。
第二行包含 n 个整数用空格分隔。
第三行包含 m 个整数用空格分隔。
输出描述
输出为一行输出长度为 n m 的升序序列即长度为 n 的升序序列和长度为 m 的升序序列中的元素重新进行升序序列排列合并。
示例 1 输入 5 6 1 3 7 9 22 2 8 10 17 33 44 输出 1 2 3 7 8 9 10 17 22 33 44 代码实现
#include stdio.h
int main()
{int arr1[1000] { 0 };int arr2[1000] { 0 };int arr[2000] { 0 };int n 0, m 0;// 一、输入scanf(%d %d, n, m);int i 0;for (i 0; i n; i){scanf(%d, arr1[i]);}for (i 0; i m; i){scanf(%d, arr2[i]);}// 二、合并有序序列i 0; // i 始终是 arr1 中未被合并的最小元素的下标int j 0; // j 始终是 arr2 中未被合并的最小元素的下标int k 0; // k 始终是 arr 中第一个未存放数据元素的下标while (i n j m){if (arr1[i] arr2[j])arr[k] arr1[i];elsearr[k] arr2[j];}while (i n){arr[k] arr1[i];}while (j m){arr[k] arr2[j];}// 三、输出for (i 0; i n m; i){printf(%d , arr[i]);}printf(\n);return 0;
} 3.4 - 88.合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例 1 输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6] 解释需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6]。 示例 2 输入nums1 [1], m 1, nums2 [], n 0 输出[1] 解释需要合并 [1] 和 [] 。 合并结果是 [1] 。 示例 3 输入nums1 [0], m 0, nums2 [1], n 1 输出[1] 解释需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 提示 nums1.length m n nums2.length n 0 m, n 200 1 m n 200 -10^9 nums1[i], nums2[j] 10^9
代码实现双指针
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1 m - 1; // end1 始终是 nums1 中未被合并的最大元素的下标int end2 n - 1; // end2 始终是 nums2 中未被合并的最大元素的下标int end m n - 1; // end 始终是 nums1 中最后一个未存放数据元素的下标while (end1 0 end2 0){if (nums1[end1] nums2[end2])nums1[end--] nums1[end1--];elsenums1[end--] nums2[end2--];}while (end2 0){nums1[end--] nums2[end2--];}// 当 nums2 中的元素都被合并到 nums1 中nums1 数组就已经有序了
} 该算法的时间复杂度是 O(m n)空间复杂度是 O(1)。 四、顺序表的问题及思考
问题 在中间/头部做插入或删除操作时需要移动大量元素。 增容一般是呈 2 倍的增长势必会有一定的空间浪费。
思考
以上问题都可以通过线性表的另一种表示方法即链式存储结构来解决。 欲知后事如何且听下回分解~
