数据结构——顺序表（三）

数据结构

一、什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
我们知道数组里的数据是0，1，2，3，不可能出现0，1，2，4，没有3就没有4

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。
   像通讯录第一次实现时定义了1000个。
2. 动态顺序表：使用动态开辟的数组存储。
   动态的通讯录

二、顺序表的创建

地址、容量、长度
定义一个结构体变量

1.静态顺序表

静态顺序表是使用定长数组存储元素。空间小了，不够用，空间大了又太浪费，所以说静态顺序表不实用。

struct SeqListInit
{
int *data；//地址
int length;//容量
};

#define N 100
typedef int SeqListDataType;//定义为SeqListDataType方便使用
typedef struct SeqList
{
	SeqListDataType a[N];//存储数据的数组
	int size;//顺序表中当前有效数据的个数
}SeqList;

2.动态数据表

typedef int SeqListDataType;
typedef struct SeqList
{
	SeqListDataType  *a;//存储数据的数组（动态开辟）
	int size;//顺序表中当前有效数据的个数
	int capacity;//顺序表中最大存储的个数
}SeqList;

三、顺序表的初始化、销毁

点（.）是用于结构体变量访问成员，箭头（->）是用于结构体指针访问成员。

//初始化
void SeqListInit(SeqList *p)
{
	assert(p);//用assert来防止传入空指针使程序崩掉
	p->a = NULL;//将指向动态开辟的数组置为NULL。
	p->size = 0;
	p->capacity = 0;
}

//销毁
void SeqListDestroy(SeqList *p)
{
	assert(p != NULL);
	free(p->a);//释放动态开辟的空间
	p->a = NULL;
	p->size = 0;
	p->capacity = 0;
}

四、顺序表的插入

在插入之前要先进行判断

//判断线性表是否已满
void CheckCapacity(SeqList* p)
{
	if (p->size == p->capacity)
	{
		int newcapacity = (p->capacity == 0) ? 4 : (p->capacity * 2);
		//如果容量为0（第一次插入数据），默认开辟4个SeqListDataType的空间
		//如果是在插入数据过程中顺序表已满，则将空间变为2倍（将空间变为2倍也可能会出现空间浪费的情况）
		//这里扩容的倍数需要具体情况具体分析，此处以2倍为例
		SeqListDataType* newA = (SeqListDataType*)realloc(p->a, sizeof(SeqListDataType)*newcapacity);
		if (newA == NULL)//开辟失败
		{
			printf("newcapacity fail\n");
			return;
		}
		p->a = newA;
		p->capacity = newcapacity;
	}
}

1.尾插

//尾插
void SeqListPushBack(SeqList* p, SeqListDataType x)
{
	assert(p);
	CheckCapacity(p);//当尾部空间不够时，就会自动扩容。
	p->a[p->size] = x;
	//p->size表示当前顺序表中有效的数据个数
	//a[p->size]访问当前最后一个数据的下一个位置
	p->size++;//注意此处要让有效数据的个数+1
}

2.头插

在头部插入数据前，需要将所有数据向后挪一位，腾出第一个数据的位置来插入新数据。
注意:必须从后向前依次挪动数据，否则前面一位的数据会覆盖后面一位的数据，导致数据的丢失。

void SeqListPushFront(SeqList* p, SeqListDataType x)
{
	assert(p);
	CheckCapacity(p);
	int end = p->size;
	for (; end > 0; end--)
	{
		p->a[end] = p->a[end - 1];//从后向前挪动数据
	}
	p->a[0] = x;
	p->size++;//注意此处要让有效数据的个数+1
}

3.任意插入

//中间插入数据
void SeqListInsert(SeqList* p, int pos, SeqListDataType x)
{
	assert(p);
	assert(pos >= 0 && pos <= p->size);
	CheckCapacity(p);

	int i = p->size;
	for (; i > pos; i--)
		p->a[i] = p->a[i - 1];//向后挪动数据
	p->a[i] = x;
	p->size++;
}

总结

我用DEV进行了简单的编写，规范的操作是编写源文件和.h文件

代码如下

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 10
typedef int SeqListDataType;
typedef struct SeqList
{
	SeqListDataType  *a;//存储数据的数组（动态开辟）
	int size;//顺序表中当前有效数据的个数
	int capacity;//顺序表中最大存储的个数
}SeqList;

int SeqListInit(SeqList *p)
{
	assert(p);//用assert来防止传入空指针使程序崩掉
	p->a = (int *)malloc(sizeof(int) * N);//将指向动态开辟的数组置为NULL。
	p->size = 0;
	p->capacity = 0;
	return 1;
}
void SeqListDestroy(SeqList *p)
{
	assert(p != NULL);
	free(p->a);//释放动态开辟的空间
	p->a = NULL;
	p->size = 0;
	p->capacity = 0;
}
void CheckCapacity(SeqList* p)
{
	if (p->size == p->capacity)
	{
		int newcapacity = (p->capacity == 0) ? 4 : (p->capacity * 2);
		//如果容量为0（第一次插入数据），默认开辟4个SeqListDataType的空间
		//如果是在插入数据过程中顺序表已满，则将空间变为2倍（将空间变为2倍也可能会出现空间浪费的情况）
		//这里扩容的倍数需要具体情况具体分析，此处以2倍为例
		SeqListDataType* newA = (SeqListDataType*)realloc(p->a, sizeof(SeqListDataType)*newcapacity);
		if (newA == NULL)//开辟失败
		{
			printf("newcapacity fail\n");
			return;
		}
		p->a = newA;
		p->capacity = newcapacity;
	}
}
void SeqListPushBack(SeqList* p, SeqListDataType x)
{
	assert(p);
	CheckCapacity(p);//当尾部空间不够时，就会自动扩容。
	p->a[p->size] = x;
	//p->size表示当前顺序表中有效的数据个数
	//a[p->size]访问当前最后一个数据的下一个位置
	p->size++;//注意此处要让有效数据的个数+1
}
void SeqListPushFront(SeqList* p, SeqListDataType x)
{
	assert(p);
	CheckCapacity(p);
	int end = p->size;
	for (; end > 0; end--)
	{
		p->a[end] = p->a[end - 1];//从后向前挪动数据
	}
	p->a[0] = x;
	p->size++;//注意此处要让有效数据的个数+1
}
void SeqListInsert(SeqList* p, int pos, SeqListDataType x)
{
	assert(p);
	assert(pos >= 0 && pos <= p->size);
	CheckCapacity(p);

	int i = p->size;
	for (; i > pos; i--)
		p->a[i] = p->a[i - 1];//向后挪动数据
	p->a[i] = x;
	p->size++;
}
void SeqListprintf(SeqList* p)
{
	assert(p);
	int i=0;
	for(i=0;i<p->size;i++)
	printf("%d\n",p->a[i]);
}
int main()
{
	SeqList sl;
	int ret;
    ret=SeqListInit(&sl);
	if(1==ret)
	printf("顺序表创建成功\n");
	SeqListPushBack(&sl,1);
	SeqListPushBack(&sl,2);
	SeqListPushBack(&sl,3);
	SeqListPushBack(&sl,4);
	printf("尾插4321成功\n"); 
	SeqListprintf(&sl);
	SeqListPushFront(&sl,5);
	printf("头插5成功\n");
	SeqListprintf(&sl);
	SeqListInsert(&sl,2,99); 
	printf("第三个位置插入99成功\n");
	SeqListprintf(&sl);
	SeqListDestroy(&sl);
	printf("销毁\n");
	SeqListprintf(&sl);
	printf("销毁成功");
}