[数据结构与算法]数据结构之顺序表！（C语言实现，代码充实）！！！

整体思路：

要知道我们实现数据结构，是要理解他是有什么用处的。

顺序表就是连续存储数据，它可以实现增删查改，让我们的数据变得灵活可变，让我们能够灵活的使用数据。

顺序表有两个类型：一个是静态的顺序表，一个是动态的顺序表。他们都有各自的优点和缺点，我们这次是采取工程文件的形式。

静态版本：就是顺序表的大小是确定的，不管你的数据是多少，容量是固定的，在定义的是时候是这样的：

#define MAX 1000//设置最大容量为100.
//为什么要宏呢？
//因为我们后面会多次用到容量为1000,我们就直接都用MAX代替
//以防我们需要修改容量大小时候所以的1000都要修改。
//进行宏替换只需要修改宏中的数字就可。

tpyedef int STDataType;//重命名，后面要用到其他数据类型就可以在这里直接改变。

typedef struct SeqList
{
	STDataType data[MAX];//顺序表存储的位置
	int size;//记录已经存储的个数
}SL;

我这次主要介绍的是动态的版本，应为大部分的数据都是多变的，所以动态版本是更好的。

tpyedef int STDataType;//重命名，后面要用到其他数据类型就可以在这里直接改变。

typedef struct SeqList
{
	STDataType* a;//这里用动态申请空间
	int size;//数据个数
	int capacity//动态顺序表的容量，用来判断是否需要增容。
}SL;

动态顺序表的增删查改等：

这些函数的定义是要放在头文件里面的，实现是放在一个.c文件中的：

（1）初始化：

一开始顺序表是什么都没有的，为空

//实现：
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
} 

(2) 尾插

尾插就是在顺序表的最后面进行数据的插入，每当我们插入的时候都需要进行判断顺序表是否需要增容，以及后面的头插和在任何位置插入，都需要进行判断是否需要增容，所以为了防止代码的重复，我们直接封装一个增容函数。

增容

void SeqListCheckCapacity(SL* ps)//判断是否需要增容
{
	if (ps->size == ps->capacity)
	{
		//判断ps->capacity是否为0.
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		//进行增容，realloc中第一个人参数如果为NULL,则效果相当于malloc，第二个参数是字节数。
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("Realloc Failed");
			exit(-1);//异常退出，终止程序。
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

这样我们就可以尾插了：

void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
	//1.判断是否要增容
	SeqListCheckCapacity(ps);

	//2.空间足够，进行尾插
	ps->a[ps->size] = x;
	ps->size++;
}

(3) 尾删

每当删除的时候都要判断顺序表中是否还有数据，如果有数据才能删除，没有数据是不能删除的。

void SeqListPopBack(SL* ps)//尾删
{
	if (ps->size != 0)//没有数据可以删了就进不去
	{
		ps->size--;
	}
}

（4）头插

头插的时候，因为数据是连续的，所以我们必须要把所以的数据从后往前一次向后挪动一个位置，所以时间复杂度是O(n)，这也是顺序表的一个缺陷。

void SeqListPushFront(SL* ps, SLDataType x)//头插
{
	//1.判断是否要增容
	SeqListCheckCapacity(ps);

	//2.进行头插
	int end = ps->size - 1;
	//挪数据
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

（5）头删

头删也是跟头插类似，要把除了第一个数据以为从第二个数据开始依次覆盖数据：

void SeqListPopFornt(SL* ps)//头删
{
	if (ps->size > 0)
	{
		int begin = 0;
		for (begin; begin < ps->size - 1; begin++)
		{
			ps->a[begin] = ps->a[begin + 1];
		}
		ps->size--;
	}	
}

（6）查找

查找就是输入一个数据，如果找到这个数据就返回数据的下标，找不到就返回-1，从而告诉我们没有这个数据。

int SeqListFind(const SL* ps, SLDataType x)
//查找,找到返回下标，找不到返回-1
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

（7）在pos下标后进行插入

void SeqListInsert(SL* ps, int pos, SLDataType x)//在pos下标后进行插入
{
	//1.判断pos是否小于ps->size或者小于0
	if (pos < ps->size && pos >= 0)
	{
		//（1）.判断是否需要增容
		SeqListCheckCapacity(ps);

		//（2）.插入
		int end = ps->size ;
		while (end > pos)
		{
			ps->a[end] = ps->a[end - 1];
			end--;
		}
		ps->a[pos + 1] = x;
		ps->size++;
	}

	//用错了返回
	else
	{
		//给定的下标不合法我们就直接断言报错
		assert(pos >= 0 && pos < ps->size);
	}
}

（7）在pos下标后进行删除

void SeqListErase(SL* ps, int pos)//删除下标为pos的值
{
	if (pos >= 0 && pos < ps->size)
	{
		int begin = pos;
		while (begin < ps->size - 1)
		{
			ps->a[begin] = ps->a[begin + 1];
			begin++;
		}
		ps->size--;
	}
}

整体代码

1.SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//#define N 100
//typedef int SLDataType;
//
静态顺序表 
//typedef struct SeqList
//{
//	SLDataType a[N];
//	int size;//表示顺序表存储元素的个数
//}SL;
//
接口函数
//void SeqListInit(SL* ps);//初始化
//
//void SeqListPushBack(SL* ps, SLDataType x);//尾插
//void SeqListPopBack(SL* ps);//尾删
//void SeqListPushFront(SL* ps, SLDataType x);//头插
//void SeqListPopFornt(SL* ps, SLDataType x);//头删



typedef int SLDataType;

//动态顺序表 
typedef struct SeqList
{
	SLDataType* a;
	int size;//表示顺序表存储元素的个数
	int capacity; //数组实际能存储空间的容量的个数。
}SL;

//接口函数（增删查改）
void SeqListInit(SL* ps);//初始化
void SeqListDestroy(SL* ps);//销毁

void SeqListCheckCapacity(SL* ps);//判断是否需要增容

void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删

void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFornt(SL* ps);//头删

void SeqListPrint(const SL* ps);//打印

int SeqListFind(const SL* ps, SLDataType x);//查找,找到返回下标，找不到返回-1

void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos下标后进行插入

void SeqListErase(SL* ps, int pos);//删除下标为pos的值

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void SeqListCheckCapacity(SL* ps)//判断是否需要增容
{
	if (ps->size == ps->capacity)
	{
		//判断ps->capacity是否为0.
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		//进行增容，realloc中第一个人参数如果为NULL,则效果相当于malloc，第二个参数是字节数。
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("Realloc Failed");
			exit(-1);//异常退出，终止程序。
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

void SeqListPrint(const SL* ps)//打印
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SeqListInit(SL* ps)//初始化
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void SeqListDestroy(SL* ps)//销毁
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
	//1.判断是否要增容
	SeqListCheckCapacity(ps);

	//2.空间足够，进行尾插
	ps->a[ps->size] = x;
	ps->size++;
}

void SeqListPopBack(SL* ps)//尾删
{
	if (ps->size != 0)//没有数据可以删了就进不去
	{
		ps->size--;
	}
}

void SeqListPushFront(SL* ps, SLDataType x)//头插
{
	//1.判断是否要增容
	SeqListCheckCapacity(ps);

	//2.进行头插
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPopFornt(SL* ps)//头删
{
	if (ps->size > 0)
	{
		int begin = 0;
		for (begin; begin < ps->size - 1; begin++)
		{
			ps->a[begin] = ps->a[begin + 1];
		}
		ps->size--;
	}	
}

int SeqListFind(const SL* ps, SLDataType x)//查找,找到返回下标，找不到返回-1
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}


void SeqListInsert(SL* ps, int pos, SLDataType x)//在pos下标后进行插入
{
	//1.判断pos是否小于ps->size或者小于0
	if (pos < ps->size && pos >= 0)
	{
		//（1）.判断是否需要增容
		SeqListCheckCapacity(ps);

		//（2）.插入
		int end = ps->size ;
		while (end > pos)
		{
			ps->a[end] = ps->a[end - 1];
			end--;
		}
		ps->a[pos + 1] = x;
		ps->size++;
	}

	//用错了返回
	else
	{
		assert(pos >= 0 && pos < ps->size);
	}
}

void SeqListErase(SL* ps, int pos)//删除下标为pos的值
{
	if (pos >= 0 && pos < ps->size)
	{
		int begin = pos;
		while (begin < ps->size - 1)
		{
			ps->a[begin] = ps->a[begin + 1];
			begin++;
		}
		ps->size--;
	}
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void TestSeqList1()
{
	SL	 s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(&s1);

	SeqListDestroy(&s1);
}

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPrint(&s1);
	SeqListPushFront(&s1, 0);
	SeqListPushFront(&s1, -1);
	SeqListPushFront(&s1, -2);
	SeqListPushFront(&s1, -3);
	SeqListPopFornt(&s1);
	SeqListPrint(&s1);
	SeqListDestroy(&s1);
}

void TestSeqList3()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListInsert(&s1, 1, 10);
	SeqListInsert(&s1, 1, 20);
	SeqListInsert(&s1, 1, 30);

	SeqListPrint(&s1);
	
	SeqListErase(&s1, 5);
	SeqListPrint(&s1);

	SeqListDestroy(&s1);

}

void menu()
{
	printf("********************************************\n");
	printf("************        请选择       ***********\n");
	printf("****          1.头插      2.尾插        ****\n");
	printf("****          3.头删      4.尾删        ****\n");
	printf("****          5.打印      -1.退出        ****\n");
	printf("********************************************\n");
	printf("********************************************\n");
}

void Test()
{
	int input;
	int x;
	SL s1;
	SeqListInit(&s1);
	printf("please Select\n");
	do
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		
		case 1:
			printf("Please enter the contents of the header to end with-1\n");
			scanf("%d", &x);
			while (x != -1)
			{
				SeqListPushFront(&s1, x);
				scanf("%d", &x);
			}
			break;
		case 2:
			printf("Please enter the contents of the tail insert ending in-1\n");
			scanf("%d", &x);
			while (x != -1)
			{
				SeqListPushBack(&s1, x);
				scanf("%d", &x);
			}
			break;
		case 3:
			SeqListPopFornt(&s1);
			printf("Pop successful\n");
			break;
		case 4:
			SeqListPopBack(&s1);
			printf("Pop successful\n");
			break;
		case 5:
			SeqListPrint(&s1);
			break;
		case -1:
			exit(0);
			break;

		default:
			printf("Selected error!\n");
			break;

		}
	} while (input != -1);
	SeqListDestroy(&s1);
}


int main()

{
	//menu()	;
	//TestSeqList1();
	//TestSeqList2();
	//TestSeqList3();
	Test();
	return 0;
}