麻城网站建设公司,如何做网站给女朋友,wordpress添加字体,建筑模板生产设备目录 1.线性表2.顺序表2.1顺序表相关概念及结构2.2增删查改等接口的实现 3.数组相关例题 1.线性表 线性表#xff08;linear list#xff09;是n个具有相同特性#xff08;数据类型相同#xff09;的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff… 目录 1.线性表2.顺序表2.1顺序表相关概念及结构2.2增删查改等接口的实现 3.数组相关例题 1.线性表 线性表linear list是n个具有相同特性数据类型相同的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 在内存中的储存地址可能不是连续的但是我们可以按它的储存顺序从顺序表的开头依次找到结尾所以逻辑上是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2.顺序表
2.1顺序表相关概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。结构与数组相同在数组的基础上增加了对数据的增删查改。 顺序表一般可以分为 1.静态顺序表数组的长度是确定的不可改变。 2.动态顺序表使用动态开辟的数组存储数据数组大小是可变的。 2.2增删查改等接口的实现 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的数组大小N是确定的不能改变N如果定大了空间开多了浪费N定小了空间开少了不够用。所以现实中基本都是使用动态顺序表根据需要改变动态分配的空间大小可以更加灵活地储存数据所以下面我们实现动态顺序表。 test.c
#include SeqList.hvoid menu()//功能菜单
{printf(******************************************\n);printf(************** 请选择 **************\n);printf(****** 1.PushFront 2.PushBack *******\n);printf(****** 3.PopFront 4.PopBack *******\n);printf(****** 5.Insert 6.Del *******\n);printf(****** 7.Modify 8.FindSct *******\n);printf(****** 9.Print 0.Exit *******\n);printf(******************************************\n);
}int main()
{int input 0;int value 0;int pos 0;SeqList sl;Init_SeqList(sl);do{menu();scanf(%d, input);switch (input){case 1:printf(请输入要头插的值:);scanf(%d, value);Push_Front_SeqList(sl, value);break;case 2:printf(请输入要尾插的值:);scanf(%d, value);Push_Back_SeqList(sl, value);break;case 3:Pop_Front_SeqList(sl);break;case 4:Pop_Back_SeqList(sl);break;case 5:printf(请输入你要插入的位置和要插入的值:);scanf(%d %d, pos, value);Insert_SeqList(sl, pos, value);break;case 6:printf(请输入要删除的值:);scanf(%d, value);Del_SeqList(sl, value);break;case 7:printf(请输入你要修改的位置和修改的值:);scanf(%d %d, pos, value);Modify_SeqList(sl, pos, value);break;case 8:printf(请输入你要查找的值:);scanf(%d, value);int ret Find_Sct_SeqList(sl, value);if (ret -1)printf(找不到该值\n);elseprintf(该值的下标为%d\n, ret);break;case 9:Print_SeqList(sl);break;case 0:printf(退出成功\n);Destroy_SeqList(sl);}} while (input);return 0;
}SeqList.c
#include SeqList.h//初始化顺序表
void Init_SeqList(SeqList* ptr)
{assert(ptr);//防止ptr为空指针空指针不能解引用SLDataType* tmp (SLDataType*)malloc(3 * sizeof(SLDataType));//先开3个数据的大小不够再增if (tmp NULL)//有可能动态数组开辟不成功{perror(Init_SeqList);exit(1);}elseptr-arr tmp;ptr-size 0;ptr-capacity 3;
}//销毁顺序表
void Destroy_SeqList(SeqList* ptr)//动态申请的空间使用完之后要释放不然会造成内存泄漏
{free(ptr-arr);ptr-arr NULL;
}//检查数组大小
void Check_Capacity(SeqList* ptr)//数组大小不够则增容
{assert(ptr);//防止ptr为空指针空指针不能解引用if (ptr-size ptr-capacity){SLDataType* tmp (SLDataType*)realloc(ptr-arr, 2 * ptr-capacity * sizeof(SLDataType));//每次增容都开辟两倍的数组大小if (tmp NULL)//有可能动态数组开辟不成功{perror(Check_Capacity);exit(1);}elseptr-arr tmp;ptr-capacity * 2;//扩容后不要忘记把capacity修改}
}//寻找某个数据的下标
int Find_Sct_SeqList(SeqList* ptr, SLDataType val)
{assert(ptr);//防止ptr为空指针空指针不能解引用for (int i 0; i ptr-size; i){if (ptr-arr[i] val){return i;//找到val返回val的下标}}return -1;//找不到则返回-1因为-1不是下标方便区分找没找到
}//在数据dst的前面插入数据src
void Insert_SeqList(SeqList* ptr, SLDataType dst,SLDataType src)
{assert(ptr);//防止ptr为空指针空指针不能解引用Check_Capacity(ptr);//插入前要先检查空间够不够不够则增容int sct Find_Sct_SeqList(ptr, dst);if(sct -1)//有可能要插入的值的位置是不存在的{printf(找不到该值\n);return;}for (int i ptr-size - 1; i sct ; i--)//插入一个值后面的值都要往后移动{ptr-arr[i1] ptr-arr[i];}ptr-arr[sct] src;ptr-size;//插入后不要忘了给数组大小加1
}//头插一个数据
void Push_Front_SeqList(SeqList* ptr,SLDataType val)
{assert(ptr);//防止ptr为空指针空指针不能解引用Check_Capacity(ptr);插入前要先检查空间够不够不够则增容for (int i ptr-size - 1; i 0; i--){ptr-arr[i 1] ptr-arr[i];}ptr-arr[0] val;ptr-size;//插入后不要忘了给数组大小加1
}//尾插一个数据
void Push_Back_SeqList(SeqList* ptr,SLDataType val)
{assert(ptr);//防止ptr为空指针空指针不能解引用Check_Capacity(ptr);//插入前要先检查空间够不够不够则增容ptr-arr[ptr-size] val;ptr-size;//插入后不要忘了给数组大小加1
}//修改一个给定的数据
void Modify_SeqList(SeqList* ptr, SLDataType dst, SLDataType src)
{assert(ptr);//防止ptr为空指针空指针不能解引用int sct Find_Sct_SeqList(ptr, dst);if (sct -1)//有可能要修改的值是不存在的{printf(找不到该值\n);return;}ptr-arr[sct] src;
}//删除一个给定的数据
void Del_SeqList(SeqList* ptr, SLDataType val)
{assert(ptr);//防止ptr为空指针空指针不能解引用int sct Find_Sct_SeqList(ptr, val);if (sct -1)//有可能要删除的值是不存在的{printf(找不到该值\n);return;}for (int i sct 1; i ptr-size; i){ptr-arr[i - 1] ptr-arr[i];}ptr-size--;
}//头删一个数据
void Pop_Front_SeqList(SeqList* ptr)
{assert(ptr);//防止ptr为空指针空指针不能解引用if (ptr-size 0)//数组内元素个数为0时不能再删了否则会越界访问{return;}for (int i 1; i ptr-size; i){ptr-arr[i - 1] ptr-arr[i];}ptr-size--;
}//尾删一个数据
void Pop_Back_SeqList(SeqList* ptr)
{if (ptr-size 0)//数组内元素个数为0时不能再删了否则会越界访问{return;}assert(ptr);ptr-size--;//数组尾删就是不访问最后一个元素将数组大小减1就可以了
}//打印顺序表
void Print_SeqList(SeqList* ptr)
{assert(ptr);//防止ptr为空指针空指针不能解引用for (int i 0; i ptr-size; i){printf(%d ,ptr-arr[i]);}printf(\n);
}SeqList.h
#include stdio.h
#include assert.h
#include stdlib.h
#include errno.htypedef int SLDataType; //将数据类型重命名为SLDataType方便修改储存的数据类型typedef struct SeqList
{SLDataType* arr; //动态开辟的数组size_t size; //数组元素个数size_t capacity; //数组大小
}SeqList;void Init_SeqList(SeqList* ptr);void Insert_SeqList(SeqList* ptr, SLDataType dst, SLDataType src);void Push_Front_SeqList(SeqList* ptr, SLDataType val);void Push_Back_SeqList(SeqList* ptr, SLDataType val);void Modify_SeqList(SeqList* ptr, SLDataType dst, SLDataType src);void Del_SeqList(SeqList* ptr, SLDataType val);void Pop_Front_SeqList(SeqList* ptr);void Pop_Back_SeqList(SeqList* ptr);int Find_Sct_SeqList(SeqList* ptr, SLDataType val);void Print_SeqList(SeqList* ptr);void Destroy_SeqList(SeqList* ptr);3.数组相关例题
题目1
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(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]也会被视作正确答案。
参考解析
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}// 思路用两个存下标的front和behind都先放在0的位置front找不是val的值与behind交换
// 这样就相当于把等于val的值往后放不等于val的值往前放
// 最后数组的前n个数就是我们想要的删除所有val值之后的数组int removeElement(int* nums, int numsSize, int val)
{int front, behind;front behind 0;while (front numsSize){if (nums[front] val){front;}else{if (front ! behind)Swap(nums[front], nums[behind]);front;behind;}}return behind;//每找到一个不是val的值behind就一次所以behind的值就是新数组的长度
}程序执行过程图 题目2
给你两个按 非递减顺序 排列的整数数组 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] 其中斜体加粗标注的为 nums1 中的元素。
示例 2
输入nums1 [1], m 1, nums2 [], n 0 输出[1] 解释需要合并[1] 和[] 。 合并结果是[1] 。
参考解析
//解题思路:
//1. 从后往前遍历数组将nums1和nums2中的元素逐个比较
//将较大的元素往nums1末尾进行搬移
//2. 第一步结束后nums2中可能会有数据没有搬移完将nums2中剩余的元素逐个搬移到nums1
//
//时间复杂度O(m n)
//空间复杂度 : O(1)void Merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// end1、end2分别标记nums1 和 nums2最后一个有效元素位置// end标记nums1的末尾nums1和nums2中的元素从后往前往nums1中存放应从end开始往前放否则会存在数据覆盖int end1 m - 1;int end2 n - 1;int index m n - 1;// 从后往前遍历将num1或者nums2中较大的元素往num1中end位置搬移// 直到将num1或者num2中有效元素全部搬移完while (end1 0 end2 0){if (nums1[end1] nums2[end2]){nums1[index--] nums1[end1--];}else{nums1[index--] nums2[end2--];}}// num2中的元素可能没有搬移完将剩余的元素继续往nums1中搬移while (end2 0){nums1[index--] nums2[end2--];}// num1中剩余元素没有搬移完 ---不用管了因为num1中剩余的元素本来就在num1中
}程序执行过程图
