- 1、 顺序表实现
- 1.1 概念及结构
- 1.2 接口实现
- 2、测试模块
- 3、顺序表OJ题
- ① LeetCode：移除元素
- ② 牛客：序列中删除指定数字
- ③ LeetCode：合并两个有序数组
- ④ 牛客：有序序列合并
1、 顺序表实现 1.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
-
静态顺序表：使用定长数组存储。
-
动态顺序表：使用动态开辟的数组存储。
- ☀️SeqList.h
#pragma once //防止头文件重复包含 #include#include #include #include #define MAX_SIZE 5 typedef int SQDataType; //静态顺序表 //typedef struct SeqList //{ // SQDataType a[MAX_SIZE]; // int size;// //}SL; // //动态顺序表 typedef struct SeqList { SQDataType*a; int size;// int capacity; }SL; //增删改查 void SeqListInit(SL *ps);//初始化 void SeqListPrint(SL* ps);//打印 void SeqListDestroy(SL* ps);//销毁 void SeqListCheckCapacity(SL* ps);//检查容量 void SeqListPushBack(SL *ps,SQDataType x);//尾插 void SeqListPushFront(SL *ps,SQDataType x);//头插 void SeqListPopBack(SL* ps);//尾删 void SeqListPopFront(SL* ps);//头删 void SeqListInsert(SL* ps, int pos, SQDataType x);//指定位置插入 void SeqListErase(SL* ps, int pos);//指定位置删 int SeqListFind(SL* ps,SQDataType x);//查找 void SeqListModify(SL* ps,int pos,SQDataType x);//修改
- ☀️SeqList.c
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
//void SeqListInit(SL *ps)//静态顺序表初始化
//{
// memset(ps->a, 0, sizeof(SQDataType)*MAX_SIZE);
// ps->size = 0;
//}
//初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
//void SeqListPushBack(SL* ps, SQDataType x)//静态顺序表的尾插
//{
// if (ps->size >= MAX_SIZE)
// {
// printf("Seqlist is Fulln");
// return;
// }
// ps->a[ps->size] = x;
// ps->size++;
//}
//销毁
void SeqListDestroy(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
//检查容量够不够
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SQDataType* tem = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
if (tem == NULL)
{
perror("realloc fail");
}
else
{
ps->a = tem;
ps->capacity = newcapacity;
}
}
}
//打印
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("n");
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
//满了就要扩容
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SeqListPushFront(SL* ps, SQDataType x)
{
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];//往后挪
end--;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}
//头删
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
int start = 1;
while (start < ps->size)
{
ps->a[start - 1] = ps->a[start];
start++;
}
ps->size--;
}
//指定位置插入
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
assert(pos < ps->size);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//指定位置删除
void SeqListErase(SL* ps, int pos)
{
assert(pos < ps->size);//删的位置要有值
int start = pos + 1;
while (start < ps->size)
{
ps->a[start - 1] = ps->a[start];
start++;
}
ps->size--;
}
//查找
int SeqListFind(SL* ps,SQDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SeqListModify(SL* ps, int pos, SQDataType x)
{
assert(pos < ps->size);
ps->a[pos] = x;
}
2、测试模块
- test.c
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
void TestSeqList()
{
//实现一个接口就进行测试
SL s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPushBack(&s, 5);
SeqListPushBack(&s, 6);
SeqListPushFront(&s, 7);
SeqListPrint(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPrint(&s);
SeqListPopFront(&s);
SeqListPrint(&s);
SeqListInsert(&s, 0, 20);
SeqListPrint(&s);
SeqListErase(&s, 0);
SeqListPrint(&s);
SeqListDestroy(&s);
}
void menu()
{
printf("**********************************************n");
printf("1. 尾插数据 2. 头插数据n");
printf("3. 尾删数据 4. 头删数据n");
printf("5. 打印数据 0. 退出n");
printf("**********************************************n");
printf("请输入你的操作选项：");
}
int main()
{
//TestSeqList();
SL s;
SeqListInit(&s);
int option = 0;
int x = 0;
do
{
menu();
scanf("%d", &option);
switch (option)
{
case 0:
printf("退出成功n");
break;
case 1:
printf("输入你要插入的数据，以-1结束n");
do
{
scanf("%d", &x);
if (x != -1)
{
SeqListPushBack(&s, x);
}
} while (x != -1);
break;
case 2:
printf("输入你要插入的数据，以-1结束n");
do
{
scanf("%d", &x);
if (x != -1)
{
SeqListPushFront(&s, x);
}
} while (x != -1);
break;
case 3:
SeqListPopBack(&s);
printf("删除成功n");
break;
case 4:
SeqListPopFront(&s);
printf("删除成功n");
break;
case 5:
SeqListPrint(&s);
break;
default:
printf("选择错误n");
break;
}
} while (option);
SeqListDestroy(&s);
return 0;
}
3、顺序表OJ题
① LeetCode：移除元素
- leetcode：移除元素
AC示例：
int removeElement(int* nums, int numsSize, int val){
int src = 0;
int dest = 0;
while (src < numsSize)
{
if (val == nums[src])
{
src++;
}
else
{
nums[dest++] = nums[src++];
}
}
return dest;
}
② 牛客：序列中删除指定数字
- 牛客：序列中删除指定数字
AC代码示例：
#include③ LeetCode：合并两个有序数组#include void Delete(int* arr,int *arrLen,int target) { int src = 0;//快指针 int dest = 0;//慢指针 while (src < *arrLen) { if (arr[src] == target) { src++; } else { arr[dest++] = arr[src++]; } } *arrLen = dest; } void Print(int* arr, int arrLen) { for (int i = 0; i < arrLen; ++i) { printf("%d ", arr[i]); } } void Init(int* arr, int arrLen) { for (int i = 0; i < arrLen; ++i) { scanf("%d", &arr[i]); } } int main() { int n = 0; int target = 0; scanf("%d", &n); int* arr = (int*)malloc(n * sizeof(int)); if (NULL == arr) { return 0; } Init(arr, n); scanf("%d", &target); Delete(arr, &n, target); Print(arr, n); free(arr); arr = NULL; return 0; }
- leetcode：合并两个有序数组
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int end1 = m-1;
int end2 = n-1;
int end = m+n-1;
//从后往前拷贝，大的拷贝到nums1
while (end1 >= 0 && end2 >= 0)//有一个数组走完就不进入循环
{
if (nums1[end1] > nums2[end2])
{
nums1[end--] = nums1[end1--];
}
else
{
nums1[end--] = nums2[end2--];
}
}
//情况1：nums1没走完，nums2走完，不需要处理
//情况2：nums1走完，nums2没走完，把nums2继续拷贝
while (end2 >= 0)
{
nums1[end--] = nums2[end2--];
}
}
④ 牛客：有序序列合并
- 牛客：有序序列合并
#include#include void Init(int *arr,int arrLen) { for (int i = 0;i < arrLen;++i) { scanf("%d ",&arr[i]); } } void Merge(int *arr1,int n,int *arr2,int m) { int end1 = n-1; int end2 = m-1; int end = m+n-1; while (end1 >= 0 && end2 >= 0) { if (arr1[end1] < arr2[end2]) { arr1[end--] = arr2[end2--]; } else { arr1[end--] = arr1[end1--]; } } while (end2 >= 0) { arr1[end--] = arr2[end2--]; } } void Print(int *arr,int arrLen) { for (int i = 0;i < arrLen;++i) { printf("%d ",arr[i]); } } int main() { int n = 0,m = 0; scanf("%d%d",&n,&m); int *arr1 = (int*)malloc((n+m)*sizeof(int)); int *arr2 = (int*)malloc(m*sizeof(int)); if (NULL == arr1 || NULL == arr2) { return 0; } Init(arr1,n); for (int i = n;i < m+n;++i) { arr1[i] = 0; } Init(arr2,m); Merge(arr1,n,arr2,m); Print(arr1,n+m); free(arr1); arr1 = NULL; free(arr2); arr2 = NULL; return 0; }
本文到此就结束了，如果有错误，请指正。
