考研/计算机二级数据结构刷题之顺序表

目录

第一题 顺序表的初始化，销毁，头插，尾插，头删，尾删，指定位置插入，指定删除以及打印

第二题 移除元素

题目链接： OJ链接

题目详解：移除元素 

第三题：删除有序数组中的重复项

题目链接：OJ链接 

---

第一题 顺序表的初始化，销毁，头插，尾插，头删，尾删，指定位置插入，指定删除以及打印

//SL.h
#pragma oncetypedef int SLDataType;typedef struct SeqList
{SLDataType* a;int size;int capacity;
}SL;//初始化
void SLInit(SL* psl);
//销毁
void SLDestory(SL* psl);
//打印函数
void SLPrint(SL* psl);
//扩容函数
void SLCheckCapacity(SL* psl);
//尾插
void SLPushBack(SL* psl, SLDataType x);
//头插
void SLPushFront(SL* psl, SLDataType x);
//尾删
void SLPopBack(SL* psl);
//头删
void SLPopFront(SL* psl);
//指定位置出入
void SLInsert(SL* psl, int pos,SLDataType x);
//制定位置删除
void SLErase(SL* psl, int pos);
//查找
int SLFind(SL* psl, SLDataType x);//SL.c
#define _CRT_SECURE_NO_WARNINGS
#include"SL.h"
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<assert.h>//初始化
void SLInit(SL* psl)
{psl->a = NULL;psl->size = 0;psl->capacity = 0;
}
//销毁
void SLDestory(SL* psl)
{assert(psl->a);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}
//打印函数
void SLPrint(SL* psl)
{assert(psl);for(int i=0;i<psl->size;i++){printf("%d ", psl->a[i]);}printf("\n");
}
//扩容函数
void SLCheckCapacity(SL* psl)
{assert(psl);if(psl->size==psl->capacity)		//当最后一个元素的下一个位置等于容量，即满了时要扩容{int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;	//	如果容量为0的话先赋初值为4，否则扩2倍SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newcapacity); //用指针指向新地址,//realloc(a,b);第一个参数a是扩容前的原地址，b是扩容大小。扩容的容量大小是Int型用sizeof（SLDataType）求得数据类型所占字节子在成容量，是开辟新空间所占的字节数if(tmp==NULL){perror("realloc fail");return 0;}psl->a = tmp;//将新空间赋给原地址，如果不引用tmp，如果扩容失败会导致原地址也消失psl->capacity = newcapacity;}}
//尾插
void SLPushBack(SL* psl, SLDataType x)
{assert(psl);			//指针不能为空NULLSLCheckCapacity(psl);psl->a[psl->size] = x;//顺序表是在size插入数据psl->size++;
}
//头插
void SLPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheckCapacity(psl);int end = psl->size - 1;while(end>=0){psl->a[end + 1] = psl->a[end];end--;}psl->a[0] = x;psl->size++;
}
//尾删
void SLPopBack(SL* psl)
{assert(psl);assert(psl->size > 0);psl->size--;			//size--,直接覆盖前一个，不用free（）
}
//头删
void SLPopFront(SL* psl)
{assert(psl);assert(psl->size > 0);int begin = 0;while (begin < psl->size)	//	向前覆盖{psl->a[begin] = psl->a[begin + 1];begin++;}psl->size--;			//size--
}
//指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos >=0 && pos <=psl->size );SLCheckCapacity(psl);int end = psl->size - 1;while(end>=pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = x;psl->size++;}
//指定位置删除
void SLErase(SL* psl, int pos)
{assert(psl);assert(pos >= 0 && pos <= psl->size);while(pos<=psl->size-1){psl->a[pos] = psl->a[pos + 1];pos++;}psl->size--;
}
//查找
int SLFind(SL* psl, SLDataType x)
{assert(psl);assert(psl->size > 0);for(int i=0;i<psl->size-1;i++){if(psl->a[i]==x){return i;}}
}//test.c
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include"SL.h"
void text1()
{SL sl; //SL 结构体类型,sl是结构体变量SLInit(&sl);		//初始化SLPushBack(&sl,1);	//将变量sl指向的空间传递给形参，这样形参可以改变实参SLPushBack(&sl,2);SLPushBack(&sl,3);SLPushBack(&sl,4);SLPushBack(&sl,5);SLPrint(&sl);SLPushFront(&sl, 0);SLPushFront(&sl, -1);SLPushFront(&sl, -2);SLPushFront(&sl, -3);SLPrint(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPrint(&sl);SLInsert(&sl, 2, 3);SLPrint(&sl);SLErase(&sl, 2);SLPrint(&sl);int t= SLFind(&sl, -1);SLErase(&sl, t);SLPrint(&sl);SLDestory(&sl);SLPrint(&sl);
}
int main()
{text1();/*printf("%d", sizeof(int));*/return 0;
}

第二题 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

int removeElement(int* nums, int numsSize, int val){int left = 0;int right = 0;while(right<numsSize){if(nums[right]!=val){nums[left]=nums[right];left++;right++;}else{right++;}}return left;
}

题目链接： OJ链接

题目详解：移除元素 

第三题：删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

题目链接：OJ链接 

非严格递增的含义：

后面都大于等于前者，不会小于前者

如 123345，是非严格递增，123342不是非严格递增

思路双指针：

int removeDuplicates(int* nums, int numsSize) {int slow=0;int fast=1;while(fast<numsSize){if(nums[fast]!=nums[slow]){slow++;nums[slow]=nums[fast];fast++;}else{fast++;}}return slow+1;
}