【数据结构】顺序表解析及实战运用
目录
线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表
概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表就是数组,但是再数组的基础上,它还要求数据是从头开始连续存储的,不能跳跃间隔。
静态顺序表
#pragma once
#define N 1000
typedef int SLDataType;
//静态顺序表
typedef struct SeqList
{
SLDataType a[N];
int size;//表示数组中存储了多少个数据
}SL;
//接口函数
void SeqListInit(SL* ps, SLDataType x);
//静态特点：如果满了就不让插入 缺点：给多少的合适呢？这个很难确定
//N给小了不够用，N给大了浪费
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListpushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps, SLDataType x);动态顺序表
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* a;
int size;//表示数组中存储了多少个数据（有效数据个数）
int capacity;//数组实际能存数据的空间容量是多大（能存储的数据个数）
}SL;
//接口函数
void SeqListInit(SL* ps);//初始化
void SeqListCheckCapacity(SL* ps);//检查容量（扩容）
void SeqListDestroy(SL* ps);
//销毁顺序表，释放空间
void SeqListPushBack(SL* ps, SLDataType x);
//尾插
void SeqListPopBack(SL* ps);
//尾删
void SeqListpushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);
//头删
void SeqListPrint(SL* ps);//打印顺序表
//找到了返回x位置下标，没有找到返回-1
int SeqListFind(SL* ps, SLDataType x);
//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos);
接口实现
初始化与销毁顺序表
void SeqListInit(SL* ps)//初始化
{
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListDestroy(SL* ps)//顺序表不用了，销毁，释放空间
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}检查容量（扩容函数）
void SeqListCheckCapacity(SL* ps)//检查容量，扩容
{
//如果没有空间或者空间不足，我们就扩容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果为0，则给4，如果不是0，则扩大二倍
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)//扩容失败
{
printf("realloc fail\n");
exit(-1);//系统函数，退出程序，正常退出是返回0，这里是退出程序并返回-1，说明是异常退出
}
//扩容成功
ps->a = tmp;
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, SLDataType x)//尾插，从尾部插入
{
SeqListCheckCapacity(ps);
//从尾部插入
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPopBack(SL* ps)//尾部删除
{
assert(ps->size > 0); //防止多次调用导致size小于0出现非法访问的情况
//ps->a[ps->size - 1] = 0; //可加可不加
ps->size--;
}头部插入与头部删除
void SeqListpushFront(SL* ps, SLDataType 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 SeqListPopFront(SL* ps)//头删
{
assert(ps->size > 0);
int begin = 1;//从数组第二个位置开始依次往前移动覆盖
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}查找数据
//查找
int SeqListFind(SL* ps, SLDataType x)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (x == ps->a[i])
return i;
}
return -1;
}指定下标位置插入
//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(pos >= 0 && pos <= ps->size);//防止pos插入位置非法
SeqListCheckCapacity(ps);
int end = ps->size - 1;
//挪动数据
while (pos <= end)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}删除指定下标位置的数据
//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}顺序表优缺点
优点
支持随机访问。
缺点
1.空间不够了需要增容，而增容是需要付出代价的。
2.为了避免频繁扩容，我们满了基本都是扩大2倍，可能会导致一定的空间浪费。
3.顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入删除数据就需要挪动数据，效率不高。
（针对顺序表的缺陷，就设计出了链表）
顺序表实战运用
删除有序数组中的重复项
解题思路：
定义三个指针，dst，i，j。使j++、向后移动，判断i和j指向的数据是否相等测定重复数据的范围，j++直到i和j指向的数据不相等，就让nums[dst] = nums[i]，然后i = j，将i移动到j的位置上，dst+1指向下一个需要改变的位置，然后j++继续向后移动测定重复数据的范围。这样dst就可以一个一个将去重后的数据放到数组中。（需要注意j++越界）
代码如下：
//去重
int removeDuplicates(int* nums, int numsSize)//返回数据个数
{
if (numsSize == 0)//防止空数组
return 0;
int i = 0, j = 0;
int dst = 0;
while (j < numsSize)
{
if (nums[i] != nums[j])
{
nums[dst] = nums[i];
i = j;
j++;
}
else
{
j++;
}
}
//当j++越界后会导致直接跳出循环，最后一个去重后的数据还需要录入
nums[dst] = nums[i];
dst++;
return dst;
}合并两个有序数组
思路：
两个指针将两个数组从最后一个开始进行相互比较，大的放进左边大数组的最后一个位置，然后将该已经放入数组的指针向前移动一个位置，然后再进行比较。
大的放进数组中，再将指针前移。
依次向前就可以把两个数组合并。如果是左侧大数组的指针先向左走到头，那么只需要将右侧数组中剩余的元素拷贝到左侧未放入新数据的位置就可以了。
代码实现：
void merge(int* nums1, int muns1Size, int m, int* nums2, int nums2Size, int n)
{
int left = m - 1, right = n - 1;
int end = m + n - 1;
while (right >= 0 && left >= 0)
{
if (nums1[left] > nums2[right])
{
nums1[end] = nums1[left];
end--;
left--;
}
else
{
nums1[end] = nums2[right];
end--;
right--;
}
}
if (left < 0)
{
while (right >= 0)
{
nums1[end] = nums2[right];
end--;
right--;
}
}
}（全文完）
原文地址：https://blog.csdn.net/leilei050213/article/details/143790223
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！