数据结构__顺序表

概念及结构       

         顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改

需要用到数组：数组的绝对优势：下标的随机访问（因为物理空间连续）

a[i]等价于*(a+i)

顺序表的两种类型

顺序表一般可以分为：

1. 静态顺序表：

使用定长数组存储元素。

缺点：空间给小了不够用，给多了浪费

//静态顺序表
//缺点：空间给小了不够用，给多了浪费
#define N 10
typedef int SLDatatype;
struct SeqList
{
	SLDatatype a[N];
	int size;
};

2. 动态顺序表：

        接口实现
        静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。

使用动态开辟的数组存储。

SList.h

包括顺序表的初始化、删除、尾部插入删除、头部插入删除

还有最后打印出结果

头部插入需要挪动整体的位置，必须从后面开始挪。先挪前面的会覆盖之前的位置导致数据丢失

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
//动态顺序表
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;	//存储的有效数据个数
	int capacity;//容量
}SL;
//需要把结构体的地址传过来
//初始化
void SLInit(SL* sl);
//销毁/删除
void SLDestroy(SL* sl);
//尾插
void SLPushBack(SL* psl,SLDatatype x);
//头插
void SLPushFront(SL* psl, SLDatatype x);
//头部删除
void SLPopFront(SL* psl);
//尾部删除
void SLPopBack(SL* psl);
//打印
void SLPrint(SL* psl);

SList.cpp

#define _CRT_SECURE_NO_WARNINGS  1
#include"SeqList.h"
//void SLInit(SL* psl)
//{
// 开始不开辟空间
//	psl->a = NULL;
//	psl->capacity = 0;
//	psl->size = 0;
//}
void SLPrint(SL* psl)
{
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d", psl->a[i]);
	}
	printf("\n");
}
void SLInit(SL* psl)
{
	//开始先开辟一小块空间
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);
	if (psl->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->capacity = 0;
	psl->size = 0;
}
void SLDestroy(SL* psl)
{
	//必须置空否则外面会访问到野指针
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
//检查容量
void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)
	{
		//扩容
		//realloc是空间的新的大小
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}
//尾插
void SLPushBack(SL* psl, SLDatatype x)
{
	//防止越界要检查容量
	SLCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
	//或者psl->a[psl->size++]=x;
}
//头插
void SLPushFront(SL* psl, SLDatatype x)
{
	SLCheckCapacity(psl);
	//挪动数据(最后一个数据往后挪)
	int end = psl->size - 1;
	//挪动数据(最后空的地方往前移)
	//int end=psl->size;
	//如果还有空间  
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0]=x;
	//长度+1
	psl->size++;
}
//头部删除
void SLPopFront(SL* psl)
{
	//暴力检查
	assert(psl->size>0);
 
	int start = 0;
	//重点
	while (start < psl->size-1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}
 
	//int start = 1;
	重点
	//while (start < psl->size)
	//{
	//	psl->a[start] = psl->a[start + 1];
	//	start++;
	//}
	psl->size - 1;
}
//尾部删除
void SLPopBack(SL* psl)
{
	//断言，暴力检查
	assert(psl->size>0);
	//温柔检查
	/*if (psl->size == 0)
		printf("表已经空了，别删了");
		return;*/
	
	psl->size--;
}

test.cpp

#include"SeqList.h"
int main()
{
	SL s;
	SLInit(&s);
	SLDestroy(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);
	SLDestroy(&s);
	return 0;
}

柔性数组和动态数组的区别

柔性数组是让结构体的成员和后面的数组空间在一块空间上

动态数组在两块空间上

接口的实现