《C++》解密--顺序表
郭小宝耶 2024-09-15 13:05:31 阅读 78
一、线性表
线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈......
线性表在【逻辑上】是线性结构，也就是连续的一条直线； 但在【物理结构】上不一定是连续的，线性表在物理上储存时，通常是数组、链式结构等形式。
二、顺序表
1、概念
顺序表是线性表的一种。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。
【顺序表在逻辑结构、物理结构上都是线性的】
2、顺序表和数组区别
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口。
三、分类
1、静态顺序表
2、动态顺序表
四、动态顺序表的实现
1、创立文件
2、顺序表的初始化和销毁
【SeqList.h】
<code>#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义动态顺序表结构
typedef int SLDatatype;
struct SeqList
{
SLDatatype* arr;
int capacity; //空间大小
int size; //有效数据个数
};
typedef struct SeqList SL; //给结构体SeqList改个名字SL
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestory(SL* ps);
【SeqList.c】
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include"SeqList.h"
//顺序表的初始化
void SLInit(SL* ps)
{
ps->;arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestory(SL* ps)
{
if (ps->arr) //相当于ps->arr != NULL
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
【test.c】
#include"SeqList.h"
void SLtest01()
{
SL s;
SLInit(&s);
SLDestory(&s);
}
int main()
{
SLtest01();
return 0;
}
3、打印
【SeqList.c】
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
【test.c】
#include"SeqList.h"
void SLtest01()
{
SL s;
SLInit(&s);
SLPrint(&s);
SLDestory(&s);
}
int main()
{
SLtest01();
return 0;
}
4、判断空间是否足够
【SeqList.c】
//判断空间是否充足
void SLCheckCapacity(SL* ps)
{
//判断空间是否充足
if (ps->size == ps->capacity)
{
//增容 //0*2=0
//若capacity为0，给个默认值，否则x2倍
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity *= newCapacity;
}
}
5、头插
【SeqList.h】
//头插
void SLPushFront(SL* ps,SLDatatype x);
【SeqList.c】
//头插
void SLPushFront(SL* ps, SLDatatype x)
{
assert(ps);
//判断空间是否足够
SLCheckCapacity(ps);
//插入操作
//数据整体后移一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//下标为0的位置空出来了
ps->arr[0] = x;
ps->size++;
}
【test.c】
#include"SeqList.h"
void SLtest01()
{
SL s;
SLInit(&s);
//头插
SLPushFront(&s, 1);
SLPushFront(&s, 2);
SLPushFront(&s, 3);
SLPushFront(&s, 4);
SLPrint(&s); //4 3 2 1
SLDestory(&s);
}
int main()
{
SLtest01();
return 0;
}
6、尾插
【SeqList.h】
//尾插
void SLPushBack(SL* ps,SLDatatype x);
【SeqList.c】
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
//方式1
if (ps == NULL)
{
return;
}
//方式2 粗暴--断言
//assert(ps); //等价于assert(ps != NULL)
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
【test.c】
//尾插
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s); //1 2 3 4
7、头删
【SeqList.h】
//头删
void SLPopFront(SL* ps);
【SeqList.c】
//头删（将第一个以后的数据整体向前挪动一位）
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1]; //i = size-2
}
ps->size--;
}
【test.c】
//头删
SLPopFront(&s);
SLPrint(&s); //2 3 4
8、尾删
【SeqList.h】
//尾删
void SLPopBack(SL* ps);
【SeqList.c】
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
//ps->arr[ps->size-1] = -1 //多余了
ps->size--;
}
【test.c】
//尾删
SLPopBack(&s);
SLPrint(&s); //1 2 3
10、在指定位置之前插入数据
【SeqList.h】
//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos);
【SeqList.c】
//在指定位置之前插入数据
//空间足够才可以直接插入
void SLInsert(SL* ps, SLDatatype x, int pos)
{
assert(ps);
// 头插 尾插
assert(pos >= 0 && pos <= ps->size);
//检查空间是否足够，是否可以直接插入
SLCheckCapacity(ps);
//pos及之后的数据整体向后移动一位
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1]; //pos <-- pos+1
}
ps->arr[pos] = x;
ps->size++;
}
【test.c】
//SLInsert(&s, 11, 0); //头插11
//SLPrint(&s); //11 1 2 3 4
//SLInsert(&s, 22, s.size); //尾插22
//SLPrint(&s); //1 2 3 4 22
SLInsert(&s, 33, 2); //指定位置后插入（2后面插入33）
SLPrint(&s); //1 2 33 3 4
11、删除指定位置的数据
【SeqList.h】
//删除指定位置的数据
void SLErase(SL* ps, int pos);
【SeqList.c】
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
//还有很多限制：如顺序表不可以为空...
//pos之后的数据整体向前挪动一位（一个一个挪）
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1]; //size-1 --> size-2
}
ps->size--;
}
【test.c】
//指定位置删除
//SLErase(&s, 0); //删除下标为0的那个数据
//SLPrint(&s); //2 3 4
SLErase(&s, s.size-1); //删除最后一个有效数据
SLPrint(&s); //1 2 3
12、查找
【SeqList.h】
//查找数据
int SLFind(SL* ps, SLDatatype x);
【SeqList.c】
//查找数据
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return 1;
}
}
//没有找到，就返回一个无效下标
return -1;
}
【test.c】
//查找数据
int find = SLFind(&s, 21);
if (find < 0)
{
printf("顺序表中不存在它！\n");
}
else
{
printf("find it!\n");
}
13、整体代码
【SeqList.h】
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义动态顺序表结构
typedef int SLDatatype;
struct SeqList
{
SLDatatype* arr;
int capacity; //空间大小
int size; //有效数据个数
};
typedef struct SeqList SL; //给结构体SeqList改个名字SL
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestory(SL* ps);
//头插
void SLPushFront(SL* ps,SLDatatype x);
//尾插
void SLPushBack(SL* ps,SLDatatype x);
//头删
void SLPopFront(SL* ps);
//尾删
void SLPopBack(SL* ps);
//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//查找数据
int SLFind(SL* ps, SLDatatype x);
【SeqList.c】
#include<stdio.h>
#include"SeqList.h"
//顺序表的初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestory(SL* ps)
{
if (ps->arr) //相当于ps->arr != NULL
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//判断空间是否充足
void SLCheckCapacity(SL* ps)
{
//判断空间是否充足
if (ps->size == ps->capacity)
{
//增容 //0*2=0
//若capacity为0，给个默认值，否则x2倍
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity *= newCapacity;
}
}
//头插
void SLPushFront(SL* ps, SLDatatype x)
{
assert(ps);
//判断空间是否足够
SLCheckCapacity(ps);
//插入操作
//数据整体后移一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//下标为0的位置空出来了
ps->arr[0] = x;
ps->size++;
}
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
//方式1
if (ps == NULL)
{
return;
}
//方式2 粗暴--断言
//assert(ps); //等价于assert(ps != NULL)
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
//头删（将第一个以后的数据整体向前挪动一位）
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1]; //i = size-2
}
ps->size--;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
//ps->arr[ps->size-1] = -1 //多余了
ps->size--;
}
//在指定位置之前插入数据
//空间足够才可以直接插入
void SLInsert(SL* ps, SLDatatype x, int pos)
{
assert(ps);
// 头插 尾插
assert(pos >= 0 && pos <= ps->size);
//检查空间是否足够，是否可以直接插入
SLCheckCapacity(ps);
//pos及之后的数据整体向后移动一位
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1]; //pos <-- pos+1
}
ps->arr[pos] = x;
ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
//还有很多限制：如顺序表不可以为空...
//pos之后的数据整体向前挪动一位（一个一个挪）
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1]; //size-1 --> size-2
}
ps->size--;
}
//查找数据
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return 1;
}
}
//没有找到，就返回一个无效下标
return -1;
}
【test.c】
#include"SeqList.h"
void SLtest01()
{
SL s;
SLInit(&s);
//头插
/*SLPushFront(&s, 1);
SLPushFront(&s, 2);
SLPushFront(&s, 3);
SLPushFront(&s, 4);
SLPrint(&s); */ //4 3 2 1
//尾插
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s); //1 2 3 4
//头删
/*SLPopFront(&s);
SLPrint(&s);*/ //2 3 4
尾删
//SLPopBack(&s);
//SLPrint(&s); //1 2 3
//指定位置之后插入
//SLInsert(&s, 11, 0); //头插11
//SLPrint(&s); //11 1 2 3 4
//SLInsert(&s, 22, s.size); //尾插22
//SLPrint(&s); //1 2 3 4 22
//SLInsert(&s, 33, 2); //指定位置后插入（2后面插入33）
//SLPrint(&s); //1 2 33 3 4
//指定位置删除
//SLErase(&s, 0); //删除下标为0的那个数据
//SLPrint(&s); //2 3 4
//SLErase(&s, s.size-1); //删除最后一个有效数据
//SLPrint(&s); //1 2 3
//查找数据
int find = SLFind(&s, 21);
if (find < 0)
{
printf("顺序表中不存在它！\n");
}
else
{
printf("find it!\n");
}
SLDestory(&s);
}
int main()
{
SLtest01();
return 0;
}
五、顺序表算法题
【示例1】
<code>int removeElement(int* nums, int numsSize, int val) {
int src = 0;
int dst = 0;
while(src < numsSize)
{
if(nums[src] == val)
{
src++;
}
else
{
nums[dst] = nums[src];
dst++;
src++;
}
}
//此时dst指向的位置就是要返回的有效个数
return dst;
}
【示例2】
<code>int removeDuplicates(int* nums, int numsSize) {
int dst = 0;
int src = dst + 1;
while(src <numsSize)
{
//nums[dst] nums[src]
//相同（重复）src++
//不相同，dst++,赋值，src++
if(nums[dst] != nums[src])
{
dst++;
nums[dst] = nums[src];
}
src++;
}
return dst+1;
}
【示例3】
<code>void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int l1 = m-1;
int l2 = n-1;
int l3 = m+n-1;
while(l1 >= 0 && l2 >= 0)
{
if(nums1[l1]>nums2[l2])
{
nums1[l3] = nums1[l1];
l3--;
l1--;
}
else
{
//l1==l2要么l2>l1
nums1[l3] = nums2[l2];
l3--;
l2--;
}
}
//跳出while循环有两种情况
//要么l1<0 ; 要么l2<0
while(l2>=0)
{
nums1[l3] = nums2[l2];
l3--;
l2--;
}
}
【思考】
感谢观看，未完待续...
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。