线性表的顺序存储
- 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表在逻辑结构上相邻的元素存储在连续的物理存储单元中，即：通过数据元素物理存储的连续性来反应元素之间逻辑上的相邻关系。采用顺序存储结构存储的线性表通常简称为顺序表。
顺序存储的线性表的特点：
- 线性表的逻辑顺序与物理顺序一致;
- 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
- 顺序存储支持随机访问，可通过下标进行访问
- 顺序表头插头删效率低，时间复杂度为O(N)
顺序表在内存中的存储
顺序表源码
公共头文件common.h
#define _CRT_SECURE_NO_WARNINGS
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
#endif //__SEQLIST_H__
顺序表头文件SeqList .h相关接口介绍
#include"common.h"
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t _size; // 有效数据个数
size_t _capicity; // 容量空间的大小
}SeqList;
基本增删查改接口
void SeqListInit(SeqList* psl, size_t capacity);//顺序表的初始化
void SeqListDestory(SeqList* psl);//销毁顺序表
//
void CheckCapacity(SeqList* psl);//增容
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾删
void SeqListPushFront(SeqList* psl, SLDataType x);//头插
void SeqListPopFront(SeqList* psl);//头删
//
int SeqListFind(SeqList* psl, SLDataType x);//查找顺序表中的某个元素
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置处插入一个元素
void SeqListErase(SeqList* psl, size_t pos);//删除pos处的元素
void SeqListRemove(SeqList* psl, SLDataType x);//删除值为x的元素
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);//将pos处的元素的值修改为x
void SeqListPrint(SeqList* psl);//打印顺序表中的元素
void SeqListBubbleSort(SeqList* psl);//通过冒泡排序对顺序表的元素进行排序
int SeqListBinaryFind(SeqList* psl, SLDataType x);//二分查找一个元素的位置
void SeqListRmoveAll(SeqList* psl,SLDataType x);//清空顺序表
//
void SeqListtest1();//测试顺序表的相关接口
顺序表接口实现文件SeqList.c
#include"SeqList.h"
//顺序表的初始化
void SeqListInit(SeqList* psl, size_t capacity)
{
assert(psl != NULL);
//给顺序表分配初始空间
psl->array = (SLDataType*)malloc(capacity*sizeof(SLDataType));
psl->_size = 0;
psl->_capicity = capacity;
}
//销毁一个顺序表
void SeqListDestory(SeqList* psl)
{
assert(psl != NULL);
if (psl->array)//判断是否有为顺序表开辟空间，有则释放
{
free(psl->array);
psl->array = NULL;
psl->_size = 0;
psl->_capicity = 0;
}
}
//打印一个顺序表
void SeqListPrint(SeqList* psl)
{
assert(psl);
if (psl->array != NULL)
{//打印顺序表的元素,通过下标访问
for (size_t i = 0; i < psl->_size; i++)
{
printf("%d ", psl->array[i]);
}
}
printf("\n");
}
// 检查是否需要增容
void CheckCapacity(SeqList* psl)
{
assert(psl != NULL);
if (psl->_size == psl->_capicity)//若是实际插入的数据个数与容量相等时，说明需要增容
{
psl->_capicity *= 2;//顺序表的容量以两倍的速度增长
//为顺序表重新申请空间
psl->array = (SLDataType*)realloc(psl->array, psl->_capicity*sizeof(SLDataType));
assert(psl->array);//判断重新申请空间是否成功
}
}
//在顺序表的尾插入一个元素，时间复杂度为O(1)
void SeqListPushBack(SeqList* psl, SLDataType x)
{
//在顺序表尾上插入数据
assert(psl);
CheckCapacity(psl);
psl->array[psl->_size] = x;
psl->_size++;
}
//顺序表尾部删除一个元素，时间复杂度为O(1)
void SeqListPopBack(SeqList* psl)
{
assert(psl);
psl->array[psl->_size] = 0;//将最后一个元素的值置0，再将_size--即可
psl->_size--;
}
//在顺序表头部插入一个元素，时间复杂度为O(N)
void SeqListPushFront(SeqList* psl, SLDataType x)
{//在顺序表头部插入数据
assert(psl);
int end = psl->_size-1;
while (end>=0)
{
psl->array[end + 1] = psl->array[end];//将元素整体向后移动
end--;
}
psl->array[0] = x;//再将元素插入头部
psl->_size++;
}
//删除顺序表头部的元素，时间复杂度为O(N)
void SeqListPopFront(SeqList* psl)
{
assert(psl);
//将第二个数据依次向前移动
for (size_t i = 0; i < psl->_size - 1; i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->_size--;
}
//在顺序表中查找一个值为x的元素，找到返回该元素下标，找不到返回-1
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (size_t i = 0; i < psl->_size - 1; i++)
{
if (psl->array[i] == x)//遍历顺序表，查找是否有值与x相等的元素
return i;
}
return -1;
}
//在顺序表指定位置插入一个值为x的元素，时间复杂度接近O(N)
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl&&pos <= psl->_size);
CheckCapacity(psl);//插入元素之前都得判断是否需要增容
int end = psl->_size - 1;
while (end >= (int)pos)
{
psl->array[end + 1] = psl->array[end];//将pos及pos之后的数向后移动，再将值插入pos处
end--;
}
psl->array[pos] = x;
psl->_size++;
}
//删除顺序表指定位置的元素，时间复杂度接近O(N)
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl&&pos<psl->_size);
while (pos<psl->_size)
{
psl->array[pos] = psl->array[pos + 1];
pos++;
}
psl->_size--;
}
//删除顺序表中值为x的元素
void SeqListRemove(SeqList* psl, SLDataType x)
{
assert(psl);
int pos = SeqListFind(psl, x);//通过find找到元素的位置，再进行删除即可
if (pos != -1)
{
while (pos < (int)psl->_size)
{
psl->array[pos] = psl->array[pos + 1];
pos++;
}
psl->_size--;
}
else
printf("删除的数不存在！\n");
}
//修改顺序表中元素
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl && pos < psl->_size);
psl->array[pos] = x;
}
//对顺序表中的元素进行冒泡排序，使其有序
void SeqListBubbleSort(SeqList* psl)
{
assert(psl);
size_t finish = psl->_size;
while (finish>0)
{
for (size_t i = 0; i < finish; i++)
{
if (psl->array[i - 1]>psl->array[i])
{
SLDataType temp = psl->array[i];
psl->array[i] = psl->array[i - 1];
psl->array[i - 1] = temp;
}
}
finish--;
}
}
//通过二分查找顺序中值为x的元素
int SeqListBinaryFind(SeqList* psl, SLDataType x)
{
assert(psl);
int mid;
int begin = 0;
int end = psl->_size-1;
while (begin <= end)
{
mid = begin + (end - begin) / 2;
if (psl->array[mid] > x)
{
end = mid - 1;
}
else if (psl->array[mid] < x)
{
begin = mid + 1;
}
else
return mid;
}
if (begin>end)
return -1;
else
return mid;
}
//移除顺序表中所有的元素，即清空顺序表
void SeqListRmoveAll(SeqList* psl, SLDataType x)
{
assert(psl);
size_t cur = 0;
size_t dst = 0;
while (cur < psl->_size-1)
{
if (psl->array[cur] != x)
{
psl->array[dst] = psl->array[cur];
++dst;
}
++cur;
}
psl->_size = dst;
}
void SeqListtest1()
{
SeqList s;
SeqListInit(&s, 2);
SeqListPushBack(&s, 5);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 6);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPushBack(&s, 3);
//SeqListPrint(&s);
//SeqListPopBack(&s);
//SeqListPushFront(&s, 3);
//SeqListPopFront(&s);
//SeqListInsert(&s, 2, 3);
//SeqListErase(&s, 2);
//SeqListRemove(&s, 5);
//SeqListModify(&s, 2, 1);
//SeqListBubbleSort(&s);
/*int ret = SeqListBinaryFind(&s, 2);
if (ret = -1)
{
printf("找不到\n");
}
else
printf("所找的数的下标为：", ret);*/
SeqListRmoveAll(&s, 3);
SeqListPrint(&s);
}
![D. Ehab the Xorcist(构造+思维)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)