顺序表的学习与通讯录的模拟实现

前面几篇文章，我们已经大概的学习了c语言的整体基础知识。那么，学会了前面那些知识，我们当如何应用？接下来，我们就讲一个数据结构的基础应用：顺序表。

顺序表是什么呢？我们平时存储一串数据的时候，一般使用的是数组，但是数组有个缺点，那就是数组的大小是固定的，无法调整的，当你用[]时，那个数组的大小就已经确定了。但有时我们需要对数组中的元素进行增删查改，那要怎么办呢？此时，顺序表就可以完成这份工作

typedef struct seqlist
{
	TypeSort* arr;
	int size;
	int capcity;

}SL;

假设，这是一份名为seqlist的结构体，我将他重定义名字为SL。这个结构体中存放了一个指针(arr)，一个数字（size），和另一个数字（capcity），指针的类型是TypeSort,可以用#define来定义不同的类型以灵活调用，size描述的是当前数组已经包含的数据的数量，capcity表示的是当前数组的总大小。这样的一个结构体变量，就构成了一个顺序表。那么，我们要如何添删查改呢？这就是本篇文章的重点内容啦

顺序表

初始化结构体

我们在使用结构体的时候，是需要对内部的三个变量进行初始化的，否则会造成一些错误。比如，如不初始化结构体中的arr的话，会导致这个arr是个野指针。因此，我们在最开始写一个这样的函数。

void Init_seqlist(SL* sl)
{
	sl->size = 0;
	sl->capcity = 0;
	sl->arr = NULL;
}

增添数据

 在初始化以后，我们可以向数组中添加数据，若空间足够大的话，我们可以直接进行赋值，将某个数据直接写入这个参数之中。但空间不够大呢？那我们就需要对空间进行扩容。

空间扩容

首先，我们需要先知道空间够不够大，才知道需不需要扩容，因此我们需要在函数中先写一个if语句，判断size和capcity是否相等。若相等，则进入扩容函数。在扩容函数中，我们先定义一个局部变量new_capcity，然后先判断capcity是否为0，如果为0，那我们就让capcity=Init_capcity, Init_capcity是我们利用define定义的一个数据，在此代码中，他就是4.如果capcity不为0，那就让他扩大两倍并用new_capcity来接受，接着用realloc创建一个空间，并用一个局部指针来接收，然后断言ptr是否为空指针，若不是空指针，那就让原数组的地址调整为ptr，接着把结构体中的capcity改成new_capcity.

void Longer_sl(SL*sl)
{
	int  new_capcity = 0;
	if (sl->capcity == 0)
	{
		new_capcity = Init_capcity;
	}
	else
		new_capcity = 2 * sl->capcity;
		TypeSort* ptr = (TypeSort*)realloc(sl->arr,sizeof(TypeSort)* new_capcity);
		assert(ptr);
		sl->arr = ptr;
		sl->capcity = new_capcity;
}

尾部插入

在掌握了扩容以后，尾部插入便显得及其简单了。我们直接将数据赋值给arr指向的地址的size位置。然后size++就可以了

void AddSL_Back(SL* example,TypeSort data)
{
	assert(example);
	if (example->size == example->capcity)
	{
		Longer_sl(example);
	}
	example->arr[example->size] = data;
	example->size++;//也可以放在里面++

}

头部插入

头部插入和尾部插入略有不同。为了将数据插入到头部，那原先所有的数据都需要往后面移一位。所以在尾插的基础上，我们需要将原先的所有数据往后面移动一位。为了更加高效的移动，我们从后面开始移动。最后实现的代码如图所示。

void AddSL_Head(SL* example, TypeSort data)
{
	assert(example);
	if (example->size == example->capcity)
	{
		Longer_sl(example);
	}
	for (int i = example->size; i >= 0; i--)
	{
		example->arr[i + 1] = example->arr[i];//arr[1] = arr[0]
	}

	example->arr[0] = data;
	example->size++;//也可以放在里面++

}

随意插入

随意插入和头部插入又很相似，只不过这次又多了一个参数dire，这个参数就是决定在哪里插入。接着将dire地址往后的数据都往后面移动一个位置。

void AddSL_ALL(SL* example, TypeSort data, int dire)//4
{
	assert(example);
	if (example->size == example->capcity)
	{
		Longer_sl(example);
	}
	for (int i = example->size; i >=dire ; i--)
	{
		example->arr[i + 1] = example->arr[i];
	}
	example->arr[dire] = data;
	example->size++;//也可以放在里面++
}

删除数据

数据的删除便不需要空间的扩容了，数据的删除相比较于数据的增加较为简单。因此，我便一次性将所有删除的方法全部列出来了

void DelateSL_back(SL* example)
{
	assert(example);
	assert(example->size);
	example->size--;
}
void DelateSL_Head(SL* example)
{
	assert(example);
	assert(example->size);
	for (int i = 0; i < example->size; i--)
	{
		example->arr[i] = example->arr[i+1];
	}
	example->size--;
}
void DelateSL_ALL(SL* example,int dire)
{
	assert(example);
	assert(example->size&&dire<example->size);
	for (int i = dire; i < example->size-1; i--)
	{
		example->arr[i] = example->arr[i + 1];
	}
	example->size--;
	
}

数据查询

要查找到该顺序表中是否有目标顺序，我们同样需要用到for循环。我们需要从0位置一直往后面进行查询，一直到最后。如果在这个过程中就找到了该数据，那就返回该数据指向的下标。若没找到，那就返回打印没找到。因为我这里后续是在通讯录中利用名字来进行查询，因此该代码不具有普遍性。

int FindName_SL(SL* example, char *data)
{
	assert(example);
	for (int i = 0; i < example->size; i++)
	{
		if (0 == strcmp(example->arr[i].name ,data))
		{
			printf("找到了，在%d下标处\n", i);
			return i;
		}
	}
	return -1;
}

摧毁结构体

当我们使用完顺序表以后，我们需要及时的将他所占的内存释放，否则会占用我们的内存空间，释放的过程如下图所示。

void Init_seqlist(SL* sl)
{
	sl->size = 0;
	sl->capcity = 0;
	sl->arr = NULL;
}

通讯录

在我们学会了顺序表以后，那我们要如何使用呢？接下来，我们就来举例使用顺序表实现通讯录的功能。

首先，通讯录的本质和上面的顺序表是一样的，都是一个数组，一个size表示当前数据的数量，一个capcity表示当前数组的最大值。但是现在数组内储存的不再是int 或者char类型了，它所储存的是一个结构体类型，这个结构体的定义如下：

typedef struct man
{
	char name[NAME_MAX];
	char HomeAddr[ADDR_MAX];
	char  Tele[TELE_MAX];
	char gender[TELE_MAX];
	int age;
}x;

如图，我将结构体赋予了5个属性，分别是名字家庭住址，电话，性别以及年龄。现在，我们可以开始针对通讯录这个结构体进行操作了。

初始化与摧毁

因为通讯录的本质是一个顺序表，只不过数组里面存的是指向另一个结构体的指针，所以通讯录的初始化与摧毁和原先的顺序表相同。

void init_contact(SL* con)
{
	void Init_seqlist(SL*con);//获得了一个顺序表
}

void Des_contact(SL* con)
{
	seqlist_Destory(con);
}

添加数据

在这个环节，我们就开始给通讯录添加数据了，在这里我们统一使用尾插的方法进行添加。我们首先定义一个x类型的数据，接着通过scanf由用户往里面输入数据，然后再讲被填好的x类型数据传给顺序表的尾插函数，这样子，一个x类型数据就传入到通讯录中了。

void Add_man(SL* con)
{
	x infor;
	printf("请输入用户名字\n");
	scanf("%s", infor.name);
	printf("请输入用户年龄\n");
	scanf("%d", &infor.age);
	printf("请输入用户性别\n");
	scanf("%s", infor.gender);
	printf("请输入用户电话\n");
	scanf("%s", infor.Tele);
	printf("请输入用户家庭住址\n");
	scanf("%s", infor.HomeAddr);
	AddSL_Back(con, infor);
}

删除数据

删除数据，我们需要先找一下该数据是否存在于该通讯录中，我们定义将要删除的人的名字放入我们前面写的顺序表顺序查询函数，然后用一个int类型的数据来接受这个返回值。如果函数返回的是的-1也就是小于0，那么就是数据不存在，那么就告诉用户数据不存在并直接返回。若函数返回了相对应下标，那就是数据存在，接着就调用顺序表的尾删函数，并打印删除成功。

void Delate_man(SL* con)
{
	char Name[NAME_MAX];
	printf("请输入你要删除的人的名字\n");
	scanf("%s", Name);
	int find = FindName_SL(con, Name);
	if (find < 0)
	{
		printf("你要删的不存在！");
		return;
	}
	else
	{
		DelateSL_ALL(con,find);
		printf("删除成功");

	}
}

改变数据

前面部分与删除数据类似，当find的值小于0的时候直接返回，当大于零的时候，我们就让用户输入新的数据。

void Change_man(SL* con)
{
	char Name[NAME_MAX];
	printf("请输入你要改变的人的名字\n");
	scanf("%s", Name);
	int find = FindName_SL(con, Name);
	if (find < 0)
	{
		printf("你要改的人不存在！");
		return;
	}
	else
	{
		printf("请输入新的姓名：\n");
		scanf("%s", con->arr[find].name);

		printf("请输入新的性别：\n");
		scanf("%s", con->arr[find].gender);

		printf("请输入新的年龄：\n");
		scanf("%d", &con->arr[find].age);

		printf("请输入新的电话：\n");
		scanf("%s", con->arr[find].Tele);

		printf("请输入新的住址：\n");
		scanf("%s", con->arr[find].HomeAddr);
		printf("改变成功！");
	}
}

查找并显示数据

在该环节，前列的代码并不两样，主要的区别在后面部分。当我们确定该数据存在的时候，直接将数据打印出来（我这个格式打印出来的好像不是很好看，各位可自行调格式）

void ContactFind(SL* con)
{
	//11
	char name[NAME_MAX];
	printf("请输入要查找的联系人姓名\n");
	scanf("%s", name);
	int find = FindName_SL(con, name);
	if (find < 0)
	{
		printf("要查找的联系人数据不存在！\n");
		return;
	}
	// 姓名 性别 年龄 电话  地址
	// 11   11   11   11   11
	printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "地址");
	printf("%3s %3s %3d %3s %3s\n", //手动调整一下格式
		con->arr[find].name,
		con->arr[find].gender,
		con->arr[find].age,
		con->arr[find].Tele,
		con->arr[find].HomeAddr
	);
}

最后的整合

当我们把这些代码写完以后，我们需要把他们串在一起，并在main函数中使用。首先是各个c文件的头文件，两个头文件对自己的函数进行声明，并包含了所需要的库函数。并且为了后续数据以及类型的方便转换，我们还使用了#define对数据进行了定义。因为struct seqlist 与struct man在c文件的重命名无法直接在头文件里面使用，因此我们需要在头文件中重新进行一次命名。

#pragma once
#include "stdio.h"
#include "assert.h"
#include "stdlib.h"
#include "contact.h"
#define Init_capcity 4
typedef x TypeSort;
typedef struct seqlist
{
	TypeSort* arr;
	int size;
	int capcity;

}SL;

void Init_seqlist(SL* sl);
void seqlist_Destory(SL* sl);
void Longer_sl(SL* sl);
void AddSL_Back(SL* example, TypeSort data);
void AddSL_Head(SL* example, TypeSort data);
void AddSL_ALL(SL* example, TypeSort data, int dire);//4
void DelateSL_back(SL* example);
void DelateSL_Head(SL* example);
void DelateSL_ALL(SL* example, int dire);
int FindName_SL(SL* example, char* data);

#pragma once
#include "stdio.h"
#include "stdlib.h"

#define ADDR_MAX 100
#define NAME_MAX 20
#define TELE_MAX 20

typedef struct man
{
	char name[NAME_MAX];
	char HomeAddr[ADDR_MAX];
	char  Tele[TELE_MAX];
	char gender[TELE_MAX];
	int age;
}x;
typedef struct seqlist SL;
void init_contact(SL* con);
void Des_contact(SL* con);
void Add_man(SL* con);
void Delate_man(SL* con);
void Change_man(SL* con);
void ContactFind(SL* con);

到最后的main文件处，为了显示的美观与清楚，我们提前写了一个简单的菜单文件。在main函数中，我们首先创建一个SL 型的数据叫做con，接着对这个顺序表进行了初始化，接着让用户根据菜单选择操作，利用do-while和switch语句可以实现对应的功能。当用户最后退出通讯录以后，将这个通讯录以txt文件形式输出并摧毁这个通讯录，接着结束函数。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"
#include "contact.h"

FILE* Data;

void menu()
{
	printf("******************\n");
	printf("*****1.添加联系人   2.删除联系人*********\n");
	printf("*****3.改变联系人   4.查找联系人*********\n");
	printf("*************0.退出通讯录****************\n");
}

void Txt_Write(SL* contact)
{
	SL person = *contact;
	Data = fopen("tonguxnlu.txt", "w");
	TypeSort* First = person.arr;
	for (int i = 0; i < person.size; i++)
	{
		fprintf(Data,"%s    ", person.arr->name);
		person.arr++;
	}
	fprintf(Data, "\n");
	person.arr= First;
	for (int i = 0; i < person.size; i++)
	{
		fprintf(Data,"%d    ", person.arr->age);
		person.arr++;
	}
	fprintf(Data, "\n");
	person.arr = First;
	for (int i = 0; i < person.size; i++)
	{
		fprintf(Data,"%s    ", person.arr->Tele);
		person.arr++;
	}
	fprintf(Data, "\n");
	person.arr = First;
	for (int i = 0; i < person.size; i++)
	{
		fprintf(Data,"%s    ", person.arr->HomeAddr);
		person.arr++;
	}
	fprintf(Data, "\n");
	person.arr = First;
	for (int i = 0; i < person.size; i++)
	{
		fprintf(Data,"%s    ", person.arr->gender);
		person.arr++;
	}
	fprintf(Data, "\n");
	person.arr = First;
	fclose(Data);

}

int main()
{
	SL con;
	Init_seqlist(&con);
	int opt = 0;
	do
	{
		menu();
		printf ("请输入你的选择\n");
		scanf("%d", &opt);	
		switch (opt)
		{
		case 1:
			Add_man(&con);
			break;
		case 2:
			Delate_man(&con);
			break;
		case 3:
			Change_man(&con);
			break;
		case 4:
			ContactFind(&con);
			break;
		case 0:
			printf("退出通讯录！");
			Txt_Write(&con);
			break;
		default:
			printf("输入错误！请重新输入！");
			break;
		}
	} while (opt!=0);
	Des_contact(&con);
	return 0;
}

谢谢翻阅！