政务网站建设管理的论文,网站所有权包括,沈阳唐朝网站建设,凯叔讲故事网站谁做的文章目录1 线性表2 顺序表2.1 概念及结构2.2 接口实现2.3 数组相关面试题2.4 顺序表的问题与思考1 线性表 线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序…
文章目录1 线性表2 顺序表2.1 概念及结构2.2 接口实现2.3 数组相关面试题2.4 顺序表的问题与思考1 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就是说是连续的一条直线。但是在物理结构上不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 2 顺序表 那么今天我们首先来学习顺序表然后再学习链表有一个循序渐进的效果 2.1 概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为 静态顺序表使用定长数组存储元素。 这种顺序表空间固定那么存储到一定数量时就不能存储不太方便 动态顺序表使用动态开辟的数组存储 动态开辟就很好解决了空间不够的问题。 2.2 接口实现 静态顺序表只适用于确定知道需要存多少数据的场景。 静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。 所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。 //那么我们先来实现接口函数#includestdio.h
#includestdlib.h
#includeassert.h
#includestring.h
typedef int SLDataType;
#define INIT_CAPACITY 4typedef struct SeqList//顺序表的创建
{SLDataType* s;//作为动态数组来初始化int size;//元素个数应该为正数int capacity;//初始容量大小
}SL;
//写接口函数时要想我们对顺序表有什么操作void SLInit(SL* ps);//顺序表的初始化
void SLDestroy(SL* ps);//顺序表的销毁
void SLPrint(SL* ps);//打印顺序表
void SLCheckCapacity(SL* ps);//检查容量是否充足
void SLPushBack(SL* ps, SLDataType x);//在尾部插入数据
void SLPopBack(SL* ps);//在尾部删除数据
void SLPushFront(SL* ps, SLDataType x);//在首部插入数据
void SLPopFront(SL* ps);//在首部删除数据
void SLInsert(SL* ps, int pos, SLDataType x);//在中间插入某个数据
void SLErase(SL* ps, int pos);//删除中间某个数据
int SLSearch(SL* ps, SLDataType x);//寻找某个元素并且返回下标写完接口函数时就要实现函数了 注意在写代码时最好写完一个接口函数就要进行调试这样找错误就很方便。 //首先是对顺序表的初始化
void SLInit(SL* ps)
{assert(ps);//进行断言ps指向的对象不为空ps-s (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//malloc开辟空间时后面要考虑开辟失败的情况要进行检查if (ps-s NULL){perror(malloc fail);return;}ps-size 0;//初始化没有元素ps-capacity INIT_CAPACITY;//进行初始化
}//打印顺序表
void SLPrint(SL* ps)
{assert(ps);//如果是空的顺序表就不能打印int i 0;for (i 0; i ps-size; i){printf(%d , ps-s[i]);}printf(\n);//打印完换行
}//进行容量检查
void SLCheckCapacity(SL* ps)
{assert(ps);//判断为不为空顺序表if (ps-size ps-capacity)//在进行尾部插入数据时要先判断空间够不够不够要进行扩容{SLDataType* ptr (SLDataType*)realloc(ps-s, sizeof(SLDataType) * ps-capacity * 2);//这里使用新的指针是因为如果开辟失败返回空指针就不会影响到原来开辟的内存空间if (ptr NULL){perror(realloc fail);return;}ps-s ptr;//开辟成功将新开辟空间的指针赋给原来的指针ps-capacity * 2;//因为空间扩大了两倍那么容量也要扩大两倍}
}//进行尾部插入数据
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//断言可以找到问题SLCheckCapacity(ps);//尾部插入要判断最后一个元素有没有空间没有则开辟ps-s[ps-size] x;//将数据赋给最后一个元素ps-size;//同时将元素个数加一//SLInsert(ps, ps-size, x);//这个函数先不用管后面会讲
}//进行头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断为不为空SLCheckCapacity(ps);//判断容量够不够for (int i ps-size - 1; i 0; i--){ps-s[i 1] ps-s[i];//将所有的数往后移一位}ps-size;//元素要加一ps-s[0] x;//进行赋值//SLInsert(ps, 0, x);//后面会讲
}//进行尾部删除
void SLPopBack(SL* ps)
{assert(ps);//判断不为空assert(ps-size 0);//判断顺序表中有没有元素ps-size--;//直接删除一个元素
}//进行头部删除
void SLPopFront(SL* ps)
{assert(ps);//判读为不为空assert(ps-size 0);//当这个数组是空的size就为负数了//那么头部删除就可以进行覆盖可以用memmove函数也可以进行一个一个覆盖int begin 0;for (begin 1; begin ps-size - 1; begin){ps-s[begin - 1] ps-s[begin];//后一个将前一个进行覆盖}ps-size--;//让元素减一
}//进行插入数据
void SLInsert(SL* ps, int pos, SLDataType x)//这个插入包括了头插和尾插所以可以进行复用
{assert(ps);//判断为不为空assert(pos 0 pos ps-size);//判断指定下标要合法等于0就是要头插等于ps-size就是要尾插SLCheckCapacity(ps);//检查容量是否充足int end ps-size - 1;while (end pos){ps-s[end 1] ps-s[end];end--;//往后一个一个赋值}ps-s[pos] x;//最后在pos位置赋值为xps-size;//元素个数加一
}//进行删除元素
void SLErase(SL* ps, int pos)
{assert(ps);//判断为不为空assert(pos 0 pos ps-size);//判断位置要合法int begin pos 1;while (begin ps-size){ps-s[begin - 1] ps-s[begin];begin;//一个一个往前覆盖}ps-size--;//元素要减一
}//进行元素的查找找到了则返回下标没找到则返回-1
int SLSearch(SL* ps, SLDataType x)//返回元素下标要有返回值
{assert(ps);//判断为不为空for (int i 0; i ps-size; i){if (ps-s[i] x)return i;//进行循环查找找到了就返回下标}return -1;//循环结束代表没找到返回-1表示没找到
}
//最后进行顺序的销毁
void SLDestroy(SL* ps)//销毁顺序表时要释放内存并且将指针设为空
{assert(ps);//判断为不为空free(ps-s);//释放指针所指向的内存空间ps-s NULL;//同时将指针置为空ps-size ps-capacity 0;//元素和容量置为0
}注意在进行传参数时如果要改变所指向的内容就要传地址过去不要传值过去切记 2.3 数组相关面试题 顺序表的内容完成后那么接下来就要写写题目来巩固能力了 原地移除数组中所有的元素val要求时间复杂度为O(N),空间复杂度O(1)。 https://leetcode.cn/problems/remove-element/ //首先我们可以将元素覆盖的方式去写。
int removeElement(int* nums, int numsSize, int val) {int src 0;//作为遍历数组的元素int dst 0;//作为返回数组的新长度while (src numsSize){if (nums[src] ! val){nums[dst] nums[src];//如果不等于元素不相等那么将dst加一src也加一}src;//如果相等只有src加一dst不加一等下个元素进行覆盖}return dst;//最后返回数组的新长度
}//也可以这样写
int removeElement(int* nums, int numsSize, int val) {int src 0;int dst 0;while (src numsSize){if (nums[src] ! val){nums[dst] nums[src];//上面的方式更加简洁因为src哪种情况都要加一}else{src;}}return dst;
}
// 删除排序数组中的重复项。 https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ //这道题目和上一个思路差不多每个数字之只能出现一次返回数组的新长度
//我们使用快慢指针
int removeDuplicates(int* nums, int numsSize){int src 1;//让src为1int dst 0;while (src numsSize){if (nums[dst] nums[src]){src;//两个数相等就src加1}else{nums[dst] nums[src];//不相等就进行赋值}}return dst 1;//最后返回dst1
}//结合图片进行理解
// 合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array/ //这里的非递减是可能递增也可能相等
//这里我们可以从头一个一个比较小的放前面大的放后面但这样比较实在麻烦。换个角度如果从后面开始放就会方便很多。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 m - 1;//作为最后一个元素比较int end2 n - 1;int dst m n - 1;while (end1 0 end2 0){if (nums2[end2] nums1[end1]){nums1[dst--] nums2[end2--];//如果大那么num2放元素}else{nums1[dst--] nums1[end1--];//如果小那么num1放元素}}while (end2 0)//这里判断end2如果还有元素依次放上去//不判断end1的原因是num1的元素就在num1中不用进行移植{nums1[dst--] nums2[end2--];}
}
//结合动态理解!(https://img-blog.csdnimg.cn/7a9667b48f7d40e48155cfb77ec0dd45.gif#pic_center) 以上题目希望可以加深和理解顺序表 2.4 顺序表的问题与思考 问题 中间/头部的插入删除时间复杂度为O(n)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们在再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 如何解决以上问题呢那就要使用链表了 这次我们学习了顺序表下次学习链表希望各位学习永无止境o_O 晚风庭院落梅初。淡云来往越疏疏。–李清照
