文章目录
一、顺序表增删查改
静态顺序表和动态顺序表的主要区别为：动态顺序表使用动态内存分配和销毁，而静态顺序表则是用定长数组存储。
1、静态顺序表
1.1、SeqList.h
头文件、函数声明、结构体
#pragmaonce#include<stdio.h>#include<string.h>#defineMAX_SIZE5typedefint SQDataType;typedefstructSeqList{
SQDataType data[MAX_SIZE];int size;//size控制元素个数（即打印个数），而不是空间的大小}SL;//初始化voidSeqListInit(SL* ps);//打印voidSeqListPrint(SL* ps);//插入删除//尾插voidSeqListPushBack(SL* ps, SQDataType x);//头插voidSeqListPushFront(SL* ps, SQDataType x);//指定位置插入voidSeqListInsert(SL* ps,int pos, SQDataType x);//指定位置删除voidSeqListErase(SL* ps,int pos);//尾删voidSeqListPopBack(SL* ps);//头删voidSeqListPopFront(SL* ps);//查找修改//查找voidSeqListFind(SL* ps, SQDataType x);//修改voidSeqListModify(SL* ps,int pos, SQDataType x);
1.2、Test.c
main函数，SeqListTest函数，menu函数
#define_CRT_SECURE_NO_WARNINGS#include"SeqList.h"voidmenu(){printf("***********************************\n");printf("**** 1.PushBack 2.PopBack ****\n");printf("****---------------------------****\n");printf("**** 3.PushFront 4.PopFront ****\n");printf("****---------------------------****\n");printf("**** 5.Insert 6.Erase ****\n");printf("****---------------------------****\n");printf("**** 7.Find 8.Modify ****\n");printf("****---------------------------****\n");printf("**** 9.Print 0.exit ****\n");printf("***********************************\n");}voidSeqListTest(){
SL s;int input =0;SeqListInit(&s);SeqListPrint(&s);do{menu();printf("请输入你的选择:>\n");scanf("%d",&input);switch(input){case1:{printf("请输入你要尾插的数，以-1结束\n");int num =0;while(num !=-1){scanf("%d",&num);if(num ==-1){break;}SeqListPushBack(&s, num);}printf("尾插完成！\n");break;}case2:{printf("请输入你要尾删的个数\n");int count =0;scanf("%d",&count);while(count){SeqListPopBack(&s);
count--;}printf("尾删完成！\n");break;}case3:{printf("请输入你要头插的数，以-1结束\n");int num =0;while(num !=-1){scanf("%d",&num);if(num ==-1){break;}SeqListPushFront(&s, num);}printf("头删完成！\n");break;}case4:{printf("请输入你要头删的个数\n");int count =0;scanf("%d",&count);while(count){SeqListPopFront(&s);
count--;}printf("头删完成！\n");break;}case5:{printf("请输入指定位置插入的个数:>\n");int count =0;int index =0;int num =0;scanf("%d",&count);while(count){printf("请输入插入位置和插入的数:>\n");scanf("%d %d",&index,&num);while(index <0|| index >= s.size){printf("位置超出范围，请重新输入:>\n");scanf("%d %d",&index,&num);}SeqListInsert(&s, index, num);SeqListPrint(&s);
count--;}printf("指定位置插入完成！\n");break;}case6:{printf("请输入指定位置删除的个数:>\n");int count =0;int index =0;scanf("%d",&count);while(count){printf("请输入删除位置:>\n");scanf("%d",&index);while(index <0|| index >= s.size){printf("位置超出范围，请重新输入:>\n");scanf("%d",&index);}SeqListErase(&s, index);SeqListPrint(&s);
count--;}printf("指定位置删除完成！\n");break;}case7:{printf("请输入你要查找的数:>\n");int findnum =0;scanf("%d",&findnum);SeqListFind(&s, findnum);break;}case8:{printf("请输入你要修改的位置和该位置修改成的数:>\n");int index =0;int num =0;scanf("%d %d",&index,&num);while(index <0|| index >= s.size){printf("位置超出范围，请重新输入:>\n");scanf("%d %d",&index,&num);}SeqListModify(&s, index,num);SeqListPrint(&s);break;}case9:SeqListPrint(&s);break;case0:break;default:break;}}while(input);}intmain(){SeqListTest();return0;}
1.3、SeqList.c
增删查改函数实现
#define_CRT_SECURE_NO_WARNINGS#include"SeqList.h"//初始化voidSeqListInit(SL* ps){memset(ps->data,0, MAX_SIZE *sizeof(SQDataType));
ps->size =0;}//打印voidSeqListPrint(SL* ps){for(int i =0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");}//不用void PushBack(SL* ps)，是因为在这里循环输入插入的数时用到%d，插入的数的类型不好维护//因为，如果改变类型，每一个函数都需要改变，所以循环最好放函数外。调用一次插入函数只执行一个数插入//尾插voidSeqListPushBack(SL* ps, SQDataType x){if(ps->size >= MAX_SIZE){printf("SeqList is full\n");return;}
ps->data[ps->size]= x;
ps->size++;}//头插：从后往前向后移动voidSeqListPushFront(SL* ps, SQDataType x){if(ps->size >= MAX_SIZE){printf("SeqList is full\n");return;}int end = ps->size-1;while(end >=0){
ps->data[end+1]= ps->data[end];
end--;}
ps->data[0]= x;
ps->size++;}//尾删voidSeqListPopBack(SL* ps){
ps->size--;}//头删:从前往后向前移动voidSeqListPopFront(SL* ps){int start =0;while(start < ps->size-1){
ps->data[start]= ps->data[start +1];
start++;}
ps->size--;}//指定位置插入voidSeqListInsert(SL* ps,int pos, SQDataType x)//pos的值为0,1，2，3...{if(pos > ps->size)//这个范围包含了头插和尾插{printf("此位置超出范围！");return;}if(ps->size >= MAX_SIZE){printf("SeqList is full\n");return;}int end = ps->size-1;while(end >= pos){
ps->data[end+1]= ps->data[end];
end--;}
ps->data[pos]= x;
ps->size++;}//指定位置删除voidSeqListErase(SL* ps,int pos){if(pos > ps->size)//这个范围包含了头插和尾插{printf("此位置超出范围！\n");return;}int start = pos;while(start < ps->size-1){
ps->data[start]= ps->data[start +1];
start++;}
ps->size--;}//查找下标intSeqListFindIndex(SL* ps, SQDataType x){for(int i =0; i < ps->size; i++){if(ps->data[i]== x){return i;}}return-1;}//查找元素voidSeqListFind(SL* ps, SQDataType x){int ret =SeqListFindIndex(ps, x);if(ret ==-1){printf("没有%d这个值！\n",x);}else{printf("值为：%d 位置为：%d\n", ps->data[ret],ret);}}//修改voidSeqListModify(SL* ps,int pos, SQDataType x){if(pos>=ps->size || pos<0){printf("超出范围！\n");}else{
ps->data[pos]= x;printf("修改成功！\n");}}
2、动态顺序表
2.1、SeqList.h
#pragmaonce#include<stdio.h>#include<string.h>#include<stdlib.h>#include<assert.h>typedefint SQDataType;typedefstructSeqList{
SQDataType* data;int size;// 有效数据的个数int capacity;//容量大小}SL;//初始化voidSeqListInit(SL* ps);//打印voidSeqListPrint(SL* ps);//插入删除//尾插voidSeqListPushBack(SL* ps, SQDataType x);//头插voidSeqListPushFront(SL* ps, SQDataType x);//指定位置插入voidSeqListInsert(SL* ps,int pos, SQDataType x);//指定位置删除voidSeqListErase(SL* ps,int pos);//尾删voidSeqListPopBack(SL* ps);//头删voidSeqListPopFront(SL* ps);//查找修改//查找intSeqListFind(SL* ps, SQDataType x);//修改voidSeqListModify(SL* ps,int pos, SQDataType x);//销毁voidSeqListDistory(SL* ps);
2.2、Test.c
#define_CRT_SECURE_NO_WARNINGS#include"SeqList.h"voidmenu(){printf("***********************************\n");printf("**** 1.PushBack 2.PopBack ****\n");printf("****---------------------------****\n");printf("**** 3.PushFront 4.PopFront ****\n");printf("****---------------------------****\n");printf("**** 5.Insert 6.Erase ****\n");printf("****---------------------------****\n");printf("**** 7.Find 8.Modify ****\n");printf("****---------------------------****\n");printf("**** 9.Print 0.exit ****\n");printf("***********************************\n");}voidSeqListTest(){
SL s;int input =0;SeqListInit(&s);SeqListPrint(&s);do{menu();printf("请输入你的选择:>\n");scanf("%d",&input);switch(input){case1:{printf("请输入你要尾插的数，以-1结束\n");int num =0;while(num !=-1){scanf("%d",&num);if(num ==-1){break;}SeqListPushBack(&s, num);}printf("尾插完成！\n");break;}case2:{printf("请输入你要尾删的个数\n");int count =0;scanf("%d",&count);while(count){SeqListPopBack(&s);
count--;}printf("尾删完成！\n");break;}case3:{printf("请输入你要头插的数，以-1结束\n");int num =0;while(num !=-1){scanf("%d",&num);if(num ==-1){break;}SeqListPushFront(&s, num);}printf("头插完成！\n");break;}case4:{printf("请输入你要头删的个数\n");int count =0;scanf("%d",&count);while(count){SeqListPopFront(&s);
count--;}printf("头删完成！\n");break;}case5:{printf("请输入指定位置插入的个数:>\n");int count =0;int index =0;int num =0;scanf("%d",&count);while(count){printf("请输入插入位置和插入的数:>\n");scanf("%d %d",&index,&num);while(index <0|| index >= s.size){printf("位置超出范围，请重新输入:>\n");scanf("%d %d",&index,&num);}SeqListInsert(&s, index, num);SeqListPrint(&s);
count--;}printf("指定位置插入完成！\n");break;}case6:{printf("请输入指定位置删除的个数:>\n");int count =0;int index =0;scanf("%d",&count);while(count){printf("请输入删除位置:>\n");scanf("%d",&index);while(index <0|| index >= s.size){printf("位置超出范围，请重新输入:>\n");scanf("%d",&index);}SeqListErase(&s, index);SeqListPrint(&s);
count--;}printf("指定位置删除完成！\n");break;}case7:{printf("请输入你要查找的数:>\n");int findnum =0;scanf("%d",&findnum);int ret =SeqListFind(&s, findnum);if(ret ==-1){printf("没有该元素！\n");}else{printf("该元素为:%d 下标为:%d\n", findnum, ret);}break;}case8:{printf("请输入你要修改的位置和该位置修改成的数:>\n");int index =0;int num =0;scanf("%d %d",&index,&num);while(index <0|| index >= s.size){printf("位置超出范围，请重新输入:>\n");scanf("%d %d",&index,&num);}SeqListModify(&s, index, num);printf("修改完成！\n");break;}case9:SeqListPrint(&s);break;case0:SeqListDistory(&s);//退出程序前销毁break;default:printf("输入错误，请重新输入:>");break;}}while(input);}intmain(){SeqListTest();return0;}
2.3、SeqList.c
#define_CRT_SECURE_NO_WARNINGS#include"SeqList.h"//初始化voidSeqListInit(SL* ps){
ps->data =NULL;//可以先置为NULL，需要空间了再开辟
ps->size =0;
ps->capacity =0;}//销毁voidSeqListDistory(SL* ps){free(ps->data);
ps->data =NULL;
ps->size = ps->capacity =0;}//打印voidSeqListPrint(SL* ps){for(int i =0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");}//检查容量voidSeqListCheckCapacity(SL* ps){if(ps->size == ps->capacity){int newcapacity = ps->capacity ==0?4: ps->capacity *2;
SQDataType* ptr =(SQDataType*)realloc(ps->data, newcapacity *sizeof(SQDataType));if(ptr ==NULL){printf("CheckFullSeqList::%S\n",strerror(errno));exit(-1);}else{
ps->data = ptr;
ps->capacity = newcapacity;}}}//不用void PushBack(SL* ps)，是因为在这里循环输入插入的数时用到%d，插入的数的类型不好维护//因为，如果改变类型，每一个函数都需要改变，所以循环最好放函数外。//调用一次插入函数只执行一个数插入//尾插voidSeqListPushBack(SL* ps, SQDataType x){SeqListCheckCapacity(ps);
ps->data[ps->size]= x;
ps->size++;}//头插：从后往前向后移动voidSeqListPushFront(SL* ps, SQDataType x){SeqListCheckCapacity(ps);int end = ps->size -1;while(end >=0){
ps->data[end +1]= ps->data[end];
end--;}
ps->data[0]= x;
ps->size++;}//尾删voidSeqListPopBack(SL* ps){assert(ps->size >0);
ps->size--;}//头删:从前往后向前移动voidSeqListPopFront(SL* ps){assert(ps->size >0);int start =1;while(start < ps->size){
ps->data[start-1]= ps->data[start];
start++;}
ps->size--;}//指定位置插入(不包括尾插)voidSeqListInsert(SL* ps,int pos, SQDataType x)//pos的值为0,1，2，3...{//插入时需要判断空间是否足够，删除时需要判断size是否为0assert(pos >=0&& pos < ps->size);//不包括尾插SeqListCheckCapacity(ps);//非尾插,都是从后往前向后移动,再把插入的值放进去, --用end--//非尾删,都是从前往后向前移动,再size-- , --用start++//end和start最开始是将要移动的那个位置int end = ps->size -1;while(end >= pos){
ps->data[end +1]= ps->data[end];
end--;}
ps->data[pos]= x;
ps->size++;}//指定位置删除voidSeqListErase(SL* ps,int pos){assert(ps->size >0);assert(pos >=0&& pos <ps->size);//头删，尾删，任意位置删均可int start = pos +1;while(start < ps->size){
ps->data[start-1]= ps->data[start];
start++;}
ps->size--;}//查找(返回下标)intSeqListFind(SL* ps, SQDataType x){for(int i =0; i < ps->size; i++){if(ps->data[i]== x){return i;}}return-1;}//修改voidSeqListModify(SL* ps,int pos, SQDataType x){assert(pos >=0&& pos < ps->size);
ps->data[pos]= x;printf("修改成功！\n");}
3、静态和动态区别
3.1、不同点
1、静态顺序表用定长数组存储。动态顺序表则使用动态内存分配和销毁。
2、在Init，PushBack，PushFront，Insert中，静态顺序表不能超过定长，而动态顺序表capacity==size时：用realloc开辟更大的空间。
3、动态比静态多出CheckCapacity和Distory两个函数。
3.2、相同点
1、在接口函数中尽量不要有输入，因为typedef下的数据类型一旦改变，有一些有输入的函数需要改（如%d），所以循环最好放函数外，在函数内就没有不符合范围重新输入的情况。
2、插入和删除：插入考虑空间是否足够用CheckCapacity检查容量并扩容，删除考虑size>0是否成立可以用assert断言。
尾插和尾删和比较简单
3、非尾插：包括头插和指定下标插，用end记录当前位置最后一个数（size-1这个位置），操作完一次end- -，依次从后往前向后移动，最后把插入的数放在开头（头插）或指定位置（随机插）。
4、非尾删：包括头删和指定下标删，用start记录0+1或当前位置+1的位置，该位置就是要移动的第一个数，操作完一次start++，依次从前往后向前移动就完成了。
5、指定插入、指定删除，和修改都要考虑下标可能<0或>=size的情况，可以用assert断言
二、OJ题
1、题一
链接：
LeetCode27.移除元素
intremoveElement(int* nums,int numsSize,int val){int i=0;int j=0;while(i < numsSize){//不等时//1、就用i在后面访问的值覆盖j记录的删除的下标//2、如果前面的值都是不等于val，那就是nums自己赋值给自己。if(nums[i]!=val)//相等的时候j不变，即j记录等于val值的下标{
nums[j++]=nums[i++];}else{
i++;}}return j;//j从0开始,最后一个数下标是j-1,元素个数是j个}
1.1、法一
双指针法，就是上面那种 时间复杂度:O(N),空间复杂度O(1)
思路：
nums[i]与val不相等时，把i位置的数给j位置的数。
相等时，i++，j不变，但j在上一步中已经++，所以j记录了当前相等时候的下标。
1.2、法二
以空间换时间的思想：重新写一个数组，把不等的数放进新数组。
缺陷：空间复杂度为O(N)
1.2、法三
一个一个找，如果相等，就把后面的数从前往后依次向前挪
缺陷：时间复杂度O(N^2)
2、题二
链接：
LeetCode88.合并两个有序数组
2.1、法一
方法：双指针从后往前找大，找到依次从nums1末尾往前放
1、原版
voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){int cnt=m+n-1;int i=m;int j=n;//nums1中数全为0，nums2个数不为0if(i==0&& j!=0){//判断个数
j-=1;//找下标while(j>=0){
nums1[cnt--]=nums2[j--];}}elseif(i!=0&& j!=0){//else if之后的语句，else不用再写，因为它表示nums2个数为0，不用再移动
i-=1;
j-=1;//当nums1最小的数比nums2最小的数还小时，这一段结束，排序就完成！while(i>=0&& j>=0){if(nums1[i]>nums2[j]){
nums1[cnt--]=nums1[i--];}else{
nums1[cnt--]=nums2[j--];}}//当nums1最小的数比nums2中的数大时，就执行此操作，把nums2的剩下的值拷贝到nums1while(i<0&& j>=0){
nums1[cnt--]=nums2[j--];}}}
2、简洁版
voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){int cnt=m+n-1;int end1=m-1;int end2=n-1;//nums1和nums2个数都大于0while(end1>=0&& end2>=0){if(nums1[end1]>nums2[end2]){
nums1[cnt--]=nums1[end1--];}else{
nums1[cnt--]=nums2[end2--];}}//1、nums1结束，nums2还没结束。//2、nums1中数全为0，nums2个数不为0while(end2>=0){
nums1[cnt--]=nums2[end2--];}}
2.2、法二
思路：创建新数组，双指针从前往后找小。小的放进新数组，直到两个数组都遍历完，最后把值还给nums1
缺点：空间复杂度为O(N)
voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){//法二 以空间换时间//思路：双指针从前往后，小的放进新数组，直到两个数组都遍历完，最后把值还给nums1//缺点：空间复杂度为O(N)int i =0;int j =0;//创建新数组并初始化int copy[m+n];while(i<m+n){
copy[i++]=0;}int cnt=0;
i=0;//在i<m,j<n的范围内一个一个比较，把小的给copywhile(i<m && j<n){if(nums1[i]<=nums2[j]){
copy[cnt++]=nums1[i++];}else{
copy[cnt++]=nums2[j++];}}//nums1走完，nums2还没完while(i==m && j<n){
copy[cnt++]=nums2[j++];}//nums2走完，nums1还没完while(j==n && i<m){
copy[cnt++]=nums1[i++];}//把结果赋值给nums1
i=0;while(i<nums1Size){
nums1[i]=copy[i];
i++;}}
2.3、法三
方法：从前往后找大。找nums2大于等于nums1的值，记录nums1的位置，将它之后的从后往前向后移动，然后插入nums1，循环完成。
缺点：时间复杂度为O(N^2)，且逻辑较为复杂。
本文转载自: https://blog.csdn.net/m0_63979882/article/details/126540767
版权归原作者 学Java的冬瓜 所有， 如有侵权，请联系我们删除。
版权归原作者 学Java的冬瓜 所有， 如有侵权，请联系我们删除。