顺序表：采用顺序存储方式，即逻辑上相邻，物理上也相邻；元素存储时连续的，中间不允许有空的位置；根据分配空间方法不同，分为静态分配和动态分配两种，本程序采用动态分配！！！
一、Seqlist.h
1、引用的库函数
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
2、枚举选择项
enum Option//枚举选择项
{
EXIT,
push_back,
push_front,
show_list,
pop_back,
pop_front,
insert_pos,
find,
length,
delete_pos,
delete_val,
sort,
resver,
clear,
destroy
};
3、用结构体构造顺序表
定义base用于存放数据；
定义capacity与size是为了判断顺序表是否已满，若capacity==size说明顺序表开辟的空间已被元素占满
typedef struct SEQLIST
{
ElemType* base;
int capacity;//表的容量（总长度）
int size;//当前表的长度
}Seqlist;
4、函数声明
bool Inc(Seqlist* list);
void InitSeqlist(Seqlist* list);
void PushBackList(Seqlist* list, ElemType x);
void PushFrontList(Seqlist* list, ElemType x);
void ShowList(const Seqlist* list);
void PopBackList(Seqlist* list);
void PopFrontList(Seqlist* list);
void InsertPosList(Seqlist* list,int pos, ElemType x);
int Find(const Seqlist* list, ElemType key);
void LengthList(const Seqlist* list);
void DelPosList(Seqlist* list,int pos);
void DelValList(Seqlist* list, ElemType val);
void Sort(const Seqlist* list);
void Resevr(Seqlist* list);
void Clear(Seqlist* list);
void Destroy(Seqlist* list);
void Exit(Seqlist* list);
5、其他
本程序采用整型数据，为方便以后更改，将int型使用重定义!
#define SEQLIST_INIT_SIZE 8//顺序表的初始大小
#define INC_SIZE 3//每一次的增量空间
typedef int ElemType;//当前定义的为int型顺序表，方便更改为其他类型，使用类型重定义
二、Main_seqlist.c
1、定义顺序表
Seqlist mylist;//定义顺序表
2、主函数
int main()
{
InitSeqlist(&mylist);//初始化顺序表
slect();
return 0;
}
3、选择系统
本程序将实现以下15大功能！！
void menu()
{
puts("*******************************************************");
puts("*** 1、尾插 2、头插 3、打印 4、尾删 ***");
puts("*** 5、头删 6、按位插入 7、查找 8、求长度***");
puts("*** 9、按位删除 10、按值删除 11、排序 12、逆置 ***");
puts("*** 13、清除 0、退出 ***");
puts("*******************************************************");
printf("请选择:> ");
}
void slect()
{
int input = 0;
ElemType Item = 0;
int pos = 0;
while (1)
{
fflush(stdout);//清空输出缓冲区的数据
system("cls");//清屏
menu();
scanf("%d", &input);
switch (input)
{
case push_back:
printf("请输入要插入的数据(-1结束):> ");
while (scanf("%d", &Item),Item!=-1)
{
PushBackList(&mylist, Item);
}
puts("尾插完毕，结果如下：");
ShowList(&mylist);
break;
case push_front:
printf("请输入要插入的数据(-1结束):> ");
while (scanf("%d", &Item), Item != -1)
{
PushFrontList(&mylist, Item);
}
puts("头插完毕，结果如下：");
ShowList(&mylist);
break;
case show_list:ShowList(&mylist);
break;
case pop_back:PopBackList(&mylist);
break;
case pop_front:PopFrontList(&mylist);
break;
case insert_pos:
printf("请输入要插入的数据:> ");
scanf("%d", &Item);
printf("请输入要插入的位置:> ");
scanf("%d", &pos);
InsertPosList(&mylist,pos,Item);
break;
case find:
printf("请输入要查找的数据:> ");
scanf("%d", &Item);
pos = Find(&mylist,Item);
if (pos == -1)
{
printf("所要查找的数据:%d不存在！\n",Item);
system("pause");
}
else
{
printf("查找的数据：%d在顺序表中的下标为：%d\n", Item, pos);
system("pause");
}
break;
case length:LengthList(&mylist);
break;
case delete_pos:
printf("请输入你要删除的数据的位置;> ");
scanf("%d", &pos);
DelPosList(&mylist,pos);
break;
case delete_val:
printf("请输入你要删除的数据;> ");
scanf("%d", &Item);
DelValList(&mylist,Item);
break;
case sort:Sort(&mylist);
break;
case resver:Resevr(&mylist);
break;
case clear:Clear(&mylist);
break;
case EXIT:Exit();
break;
default:puts("选择有误，请重试！");
system("pause");
break;
}
}
}
三、Fun_seqlist.c
1、初始化
初始化是指为顺序表分配一段预定义大小的连续空间，用base记录这段空间的基地址，当前空间是没有任何元素的。
a、为base开辟空间用于存放数据；
b、将初始容量赋值给capacity，因未存入数据所以初始顺序表长度size为0
void InitSeqlist(Seqlist* list)
{
list->base = (ElemType*)malloc(SEQLIST_INIT_SIZE * sizeof(ElemType));
assert(list->base != NULL);//断言——若list->base为NULL则开辟不成功
list->capacity = SEQLIST_INIT_SIZE;
list->size = 0;
puts("初始化完毕！\n");
system("pause");
return;
}
2、尾插函数
a、判断顺序表是否已满，若满则无法存储，需增加空间，直到内存已满（即：无法再开辟内存）为止
b、若没满，则size所指向的空间就是尾部，直接赋值插入即可
void PushBackList(Seqlist* list, ElemType x)
{
if (list->size >= list->capacity && !Inc(list))
{
puts("顺序表空间已满，无法在尾部插入数据！");
system("pause");
return;
}
list->base[list->size] = x;
list->size++;
}
3、头插函数
a、判断顺序表是否已满，若满则无法存储，需增加空间，直到内存已满（即：无法再开辟内存）为止；
b、将元素依次往后移，把第一个位置留出来，再赋值
void PushFrontList(Seqlist* list, ElemType x)
{
int i = 0;
if (list->size >= list->capacity && !Inc(list))
{
puts("顺序表空间已满，无法在头部插入数据！");
system("pause");
return;
}
for (i = list->size; i > 0; i--) {
list->base[i] = list->base[i - 1];
}
list->base[0] = x;
list->size++;
}
4、显示打印函数
void ShowList(const Seqlist* list)
{
int i = 0;
if (list->size == 0)
{
puts("顺序表中无数据存在！");
system("pause");
return;
}
for (i = 0; i < list->size; i++)
{
printf("%d ", list->base[i]);
}
printf("\n");
puts("显示完毕！");
system("pause");
}
5、尾删函数
a、判断顺序表是否为空；
b、尾删只需要将size–即可（即：虽然表中数据没变，但可用的有效数据是少了一个的），没必要非得把最后一个具体元素删除
void PopBackList(Seqlist* list)
{
if (list->size == 0)
{
puts("顺序表为空，无法进行尾删！");
system("pause");
return;
}
list->size--;
puts("尾删完毕，结果如下：");
ShowList(list);
}
6、头删函数
a、判断顺序表是否为空；
b、把第一个元素之后的元素依次往前移动
void PopFrontList(Seqlist* list)
{
int i = 0;
if (list->size == 0)
{
puts("顺序表为空，无法进行头删！");
system("pause");
return;
}
for (i = 0; i < list->size - 1; i++)
{
list->base[i] = list->base[i + 1];
}
list->size--;
puts("头删完毕，结果如下：");
ShowList(list);
}
7、按位置插入函数
a、判断插入位置的合法性，若pos<0或者pos大于了顺序表的当前长度（即：不能构成顺序表）；
b、判断顺序表空间是否已满；
c、将要插入的位置及其之后的元素依次往后移动一位，再把插入的值赋值给位置处
void InsertPosList(Seqlist* list,int pos, ElemType x)
{
int i = 0;
if (pos<0 || pos>list->size)
{
puts("插入位置非法，无法插入！");
system("pause");
return;
}
if (list->size >= list->capacity && !Inc(list))
{
puts("顺序表空间已满，无法按位置插入数据！");
system("pause");
return;
}
for (i = list->size; i > pos; i--)
{
list->base[i] = list->base[i - 1];
}
list->base[pos] = x;
list->size++;
puts("插入完毕，结果如下：");
ShowList(list);
}
8、查找函数
a、我们默认顺序表中的数据不重复！
b、遍历顺序表，一一进行比较，若存在，则返回其下标，否则返回-1
int Find(const Seqlist* list, ElemType key)
{
assert(list != NULL);
int i = 0;
for (i = 0; i < list->size; i++)
{
if (list->base[i] == key)
{
return i;
}
}
return -1;
}
9、求顺序表长度函数
当前顺序表的长度，即为所存入的数据个数，打印size的值即可！
void LengthList(const Seqlist* list)
{
assert(list != NULL);
printf("该顺序表长度为：%d\n", list->size);
system("pause");
return;
}
10、按所在位置进行删除函数
a、判断位置pos的合法性，若pos小于0或者大于了顺序表当前长度，均不合法；
b、将pos所指后面的数据依次前移；
c、注意：最后一个元素就没必要移动，因而pos只需小于size-1即可
void DelPosList(Seqlist* list,int pos)
{
int i = 0;
if (pos<0 || pos>=list->size)
{
puts("删除位置非法，无法删除！");
system("pause");
return;
}
for (i = pos; i < list->size-1; i++)
{
list->base[i] = list->base[i+1];
}
list->size--;
puts("删除完成，结果如下：");
ShowList(list);
}
11、按值进行删除函数
a、利用查找函数Find，找出需要删除的值得位置下标；
b、再调用位置删除函数DelPosList，进行删除即可
void DelValList(Seqlist* list, ElemType val)
{
int i = 0;
int pos = Find(list, val);
if (pos == -1)
{
printf("所在顺序表中，不存在数据：%d\n", val);
system("pause");
return;
}
DelPosList(list, pos);
}
12、排序函数
采用冒泡排序法！！
void Sort(const Seqlist* list)
{
int i = 0;
int j = 0;
ElemType temp;
for (i = 0; i < list->size-1; i++)
{
for (j = 0; j < list->size - i-1; j++)
{
if (list->base[j] > list->base[j + 1])
{
temp = list->base[j];
list->base[j] = list->base[j + 1];
list->base[j + 1] = temp;
}
}
}
puts("排序完毕，其结果如下：");
ShowList(list);
}
13、数据逆置函数
a、判断顺序表的元素必须大于2，才能进行逆置；
b、定义两个变量low、high分别指向顺序表的两头，再交换后同时减减即可
void Resevr(Seqlist* list)
{
if (list->size == 0 || list->size == 1)
{
return;
}
int low = 0;
int high = list->size - 1;//内存中序号是以0开始，最后一位为size-1
ElemType temp;
while (low < high)
{
temp = list->base[low];
list->base[low] = list->base[high];
list->base[high] = temp;
low++;
high--;
}
puts("逆置完毕，其结果如下：");
ShowList(list);
}
14、清除数据函数
清除只是让顺序表的有效数据访问为0！
void Clear(Seqlist* list)
{
list->size = 0;
puts("清除数据完毕！");
system("pause");
}
15、销毁函数
销毁则需将顺序表的动态存储空间释放掉！
此方法，应为退出时自动操作！
void Destroy(Seqlist* list)
{
free(list->base);
list->base = NULL;
list->capacity = 0;
list->size = 0;
puts("数据销毁成功！");
system("pause");
}
16、退出函数
void Exit(Seqlist* list)
{
puts("即将退出系统，欢迎下次使用！");
system("pause");
Destroy(list);
exit(0);
}
17、动态增加空间函数
bool Inc(Seqlist* list)
{
ElemType* newbase = (ElemType*)realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));
if (newbase == NULL)
{
puts("增加空间失败，内存不足！");
return false;
}
list->base = newbase;
list->capacity += INC_SIZE;
return true;
}
四、力扣OJ练习
1、原地移除元素
法一：暴力对比——用数组 nums 中的每个值与 val 对比，若一样，则将数组中的后续元素依次前移，覆盖掉一样的元素
此法，时间复杂度为O(n*n)
法二：新建一个数组（以时间换空间）——将数组 nums 中与 val 不一样的元素，存放到新数组中
此法时间复杂度为O(n)，空间复杂度也为O(n)
法三：双指针玩法——src位置不是val就放到dst位置，然后src++,dst++；src位置是val，src++
此法时间复杂度为O(n),空间复杂度O(1)
//方法三符合要求，实现如下：
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++];
}
else
{
src++;
}
}
return dst;
}
2、合并两个有序数组
void merge(int* nums1, int m, int* nums2, int n) {
int end1 = m - 1;
int end2 = n - 1;
int end = m + n - 1;
while (end1 >= 0 && end2 >= 0)
{
if (nums1[end1] > nums2[end2])
{
nums1[end--] = nums1[end1--];
}
else
{
nums1[end--] = nums2[end2--];
}
}
//如果是 end1 没完，不需要处理；若 end2 没完，则需拷贝过去
while (end2 >= 0)
{
nums1[end--] = nums2[end2--];
}
}
本文含有隐藏内容，请 开通VIP 后查看