单链表实现通讯录

之前我们完成了基于顺序表（动态）实现通讯录，现在我们链表学完了，可以尝试着使用链表来实现我们的通讯录。

首先我们要明白我们写的通讯录是由一个个节点组成的，每个节点里存储的就是我们的联系人信息。也就是说 我们需要先写一个单链表，完成单链表的插入，删除等功能。然后在单链表的基础上将单链表中的每个节点存储的数据改为一个联系人 由于这一部分我们之前写过，所以我在这里就不重复写了，大家可以看下我前面的博客。

一、通讯录的具体形式

二、实现通讯录

（1）、确定链表的类型

在我的双向链表这篇博客里我们了解了链表的分类，我们既写过不带头单向不循环链表，又写过带头双向循环链表。那么我们该如何选择呢？-在这里其实两种链表都可以，难度也是差不多的，因为双链表相较于单链表完善许多，那我们就用单链表来写。

（2）、完成通讯录的思路

首先，通讯录需要完成我们的 增、删联系人，修改联系人，查找联系人，打印通讯录。 这一部分就是我们需要完成的功能。

准备阶段：上面我们知道我们是由一个结构体来储存我们的联系人信息，我们就需要定义一个person联系人的结构体，然后我们之前写的链表里每个节点存储的数据的类型是int型，我们需要将其改为我们现在的person型。联系人的增删查改就是调用我们之前写的单链表的增删等函数，查改这两部分略有差异需要重新来写。

（3）、准备阶段：
contact.h

#define NAME_MAX 20
#define GENDER_MAX 10
#define ADDR_MAX 100
#define NUM_MAX 15
typedef struct person
{
	char name[NAME_MAX];//姓名
	char gender[GENDER_MAX];//性别
	int age;//年龄
	char addr[ADDR_MAX];//住址
	char num[NUM_MAX];//电话号码
}person;

。
void ConAdd(contact** ptr);//联系人添加
void ConPrint(contact** ptr);//联系人打印
void ConPop(contact** ptr);//删除联系人
void ConFind(contact** ptr);//查找联系人
void ConGai(contact** ptr);//修改联系人
void ConDesTroy(contact** ptr);//销毁通讯录

ListNode.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"单链表contact.h"
typedef person datatype;
typedef struct ListNode
{
	datatype data;
	struct ListNode* next;
}ListNode;
void SLprint(ListNode** ptr);//打印
void SLBackPush(ListNode** ptr,datatype x);//单链表的尾插
void SLProntPush(ListNode** ptr, datatype x);//单链表的头插
void SLBackPop(ListNode** ptr);//单链表的尾删
void SLProntPop(ListNode** ptr);//单链表的头删
ListNode* SLFind(ListNode** ptr,datatype x);//链表的查找
void SLPosPush(ListNode** ptr, ListNode* pos, datatype x);//在指定位置插入数据
void SLPosPop(ListNode** ptr,ListNode* pos);//删除指定节点
void SLDesTory(ListNode** ptr);//销毁链表

这里我们需要注意的是因为我们需要将每个结构体里的数据类型换为person那么我们就需要包含contact.h的头文件,但是我们知道我们使用通讯录时其实是调用的外层的单链表结构，所以我们需要将ListNode.h包含在contact.h里，现在就出现了一个尴尬的情况–互相包含。解决的办法就是前置申明，在contact.h中typedef struct ListNode contact;这一段代码不光前置声明了还将外层的链表给改个名。

（4）、增删查改的实现

1、增加联系人，上面我们说过增加联系人就是调用我们的单链表的插入函数，我们写单链表的时候写了单链表的头插与尾插，在这里都可以，但是为了更符合日常我在这里采用尾插。

void ConAdd(contact** ptr)
{
	assert(ptr);
	printf("请输入添加的联系人的姓名  性别  年龄  住址  电话\n");
	person pes;
	scanf("%s", pes.name);
	scanf("%s", pes.gender);
	scanf("%d", &pes.age);//age是整型所以需要&符号
	scanf("%s", pes.addr);
	scanf("%s", pes.num);
	SLBackPush(ptr, pes);
}

这里需要注意的是我们是将整个person结构体定义的变量插入到链表，所以我们需要定义一个联系人的变量，先将联系人赋值，然后再将这整个变量作为我们的数据插入。

2、删除联系人

void ConPop(contact** ptr)
{
	assert(ptr && *ptr);
	char NAME[NAME_MAX];//定义一个数组
	printf("请输入你要删除的联系人的姓名：\n");
	scanf("%s", NAME);//输入我们要删除的联系人的姓名
	contact* pcur = *ptr;
	while (pcur)
	{
		if (strcmp(pcur->data.name,NAME)==0)//比较输入的字符串和链表中的联系人姓名，名字相同时删除该联系人
		{
			if (pcur==*ptr)//当删除的联系人为第一个节点
			{
				pcur = pcur->next;
				free(*ptr);
				*ptr = pcur;
				break;
			}
			else//删除的联系人不在第一个节点
			{
				contact* prev = *ptr;
				while (prev->next != pcur)//找需要删除的联系人的前一个节点
				{
					prev = prev->next;
				}
				prev->next = pcur->next;
				free(pcur);
				pcur = NULL;
				break;
			}
		}
		pcur = pcur->next;
	}
}

删除联系人稍微比较麻烦，首先我们要确定以什么为标准来删除联系人，如果以电话号码来删除，就需要比较两个电话号码的字符串，名字同理，为了符合常理我这里使用名字，确定了以什么为标准以后我们还要考虑需要删除的联系人是否为第一个节点。

如果不为第一个节点，就需要遍历整个链表，找到需要删除的联系人的前一个节点，然后将前一个节点与后一个节点连接，最后释放掉需要删除的节点即可。

如果需要删除的联系人就是第一个节点的话，我们就不需要找前一个节点，直接让指向头结点的指针向后移，然后释放掉原来的头结点。

以上就是删除时的三种情况，第三种只有一个联系人的情况是可以通过第二种方式的代码解决。

3、查找联系人

同样查找联系人也需要我们以一个标准来选，我这里依然用名字来比较。

void ConFind(contact** ptr)
{
	assert(ptr && *ptr);
	char NAME[NAME_MAX];
	printf("请输入你要查找的联系人的姓名：\n");
	scanf("%s", NAME);
	contact* pcur = *ptr;
	while (pcur)
	{
		if (strcmp(pcur->data.name, NAME) == 0)
		{
			printf("姓名  性别  年龄  住址  电话\n");
			printf("%s  %s  %d  %s  %s\n", pcur->data.name,
				pcur->data.gender,
				pcur->data.age,
				pcur->data.addr,
				pcur->data.num);
		}
		pcur = pcur->next;
	}
}

这一部分简单许多，直接遍历链表，找到名字相同的节点，然后将该节点存储的联系人信息打印出来即可。

4、修改联系人

同样我这里用名字作为找联系人的标准。

void ConGai(contact** ptr)
{
	assert(ptr && *ptr);
	char NAME[NAME_MAX];
	printf("请输入你要修改的联系人的姓名：\n");
	scanf("%s", NAME);
	contact* pcur = *ptr;
	while (pcur)
	{
		if (strcmp(pcur->data.name, NAME) == 0)
		{
			printf("请输入修改后的联系人的姓名  性别  年龄  住址  电话\n");
			scanf("%s %s %d %s %s",
				pcur->data.name,
				pcur->data.gender,
				&pcur->data.age,
				pcur->data.addr,
				pcur->data.num);
		}
		pcur = pcur->next;
	}
}

这里跟上面的找联系人相似，找到后直接输入修改后的联系人的信息，覆盖掉原联系人的信息即可。

（5）、通讯录的销毁

当我们使用完通讯录，我们就需要将这个通讯录的空间给释放掉，那之前我们说有销毁就有初始化，为什么通讯录没有初始化呢？那是因为我们使用这个链表时，使用的是指向这个链表的指针，当我们不进行增删查改等操作时，该指针就为空，不需要进行初始化。

void ConDesTroy(contact** ptr)
{
	assert(ptr && *ptr);
	contact* pcur = *ptr;
	while (pcur)
	{
		contact* del = pcur->next;
		free(pcur);
		pcur = del;
	}
	pcur = NULL;
}

销毁链表也比较简单，直接遍历整个链表，遍历一个释放一个。

上面我们完成了通讯录的功能，那么我们就可以将功能组装起来成为我们的通讯录。

#include"ListNode.h"
#include"单链表contact.h"
void menu()
{
	printf("***************************************\n");
	printf("*************单链表通讯录**************\n");
	printf("*******1、添加联系人  2、删除联系人****\n");
	printf("*******3、查找联系人  4、修改联系人****\n");
	printf("*******5、打印联系人  0、退出通讯录****\n");
	printf("***************************************\n");
}

int main()
{
	contact* phead=NULL;
	int input = 0;
	do
	{
		menu();
		printf("请输入你的选项：\n");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			ConAdd(&phead);
			break;
		case 2:
			ConPop(&phead);
			break;
		case 3:
			ConFind(&phead);
			break;
		case 4:
			ConGai(&phead);
			break;
		case 5:
			ConPrint(&phead);
			break;
		case 0:
			ConDesTroy(&phead);
			printf("退出成功");
			break;
		default:
			printf("选项错误，请重新输入：");
			break;
		}
	} while (input);
	return 0;
}

像这样我们就可以通过输入的数字来进行我们的通讯录操作。

上面我已经给出了contact.h ListNode.h test.c的代码，下面是其他部分的代码：
ListNode.c

#include"ListNode.h"

ListNode* buynode(datatype x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = NULL;
	return node;
}

void SLBackPush(ListNode** ptr,datatype x)
{
	assert(ptr);
	ListNode* node = buynode(x);
	if (*ptr == NULL)
	{
		*ptr = node;
	}
	else
	{
		ListNode* ptail = *ptr;
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}
		ptail->next = node;
	}
}

//void SLprint(ListNode** ptr)
//{
//	assert(ptr);
//	ListNode* pcur = *ptr;
//	while (pcur)
//	{
//		printf("%d ", pcur->data);
//		pcur = pcur->next;
//	}
//	printf("\n");
//}

void SLProntPush(ListNode** ptr, datatype x)
{
	assert(ptr);
	ListNode* node = buynode(x);
	if (*ptr == NULL)
	{
		*ptr = node;
	}
	else
	{
		node->next = *ptr;
		*ptr = node;
	}
}

void SLBackPop(ListNode** ptr)
{
	assert(ptr);
	if ((*ptr)->next==NULL)
	{
		free(*ptr);
		*ptr = NULL;
	}
	else
	{
		ListNode* pcur = *ptr;
		while (pcur->next->next)
		{
			pcur = pcur->next;
		}
		ListNode* del = pcur->next;
		free(del);
		pcur->next = NULL;
		del = NULL;
	}
}

void SLProntPop(ListNode** ptr)
{
	assert(ptr && *ptr);
	ListNode* del = *ptr;
	*ptr = (*ptr)->next;
	free(del);
	del = NULL;
}

//ListNode* SLFind(ListNode** ptr, datatype x)
//{
//	assert(ptr && *ptr);
//	ListNode* pcur = *ptr;
//	while (pcur)
//	{
//		if (pcur->data == x)
//		{
//			return pcur;
//		}
//		pcur = pcur->next;
//	}
//	return NULL;
//}

void SLPosPush(ListNode** ptr, ListNode* pos, datatype x)
{
	assert(ptr && *ptr && pos);
	if (pos == *ptr)
	{
		SLProntPush(ptr, x);
	}
	else
	{
		ListNode* node = buynode(x);
		ListNode* pcur = *ptr;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		node->next = pos;
		pcur->next = node;
	}
}

void SLPosPop(ListNode** ptr, ListNode* pos)
{
	assert(ptr&&*ptr&&pos);
	if (pos == *ptr)
	{
		SLProntPop(ptr);
	}
	else
	{
		ListNode* pcur = *ptr;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLDesTory(ListNode** ptr)
{
	assert(ptr);
	ListNode* pcur = *ptr;
	while (pcur)
	{
		ListNode* del = pcur->next;
		pcur = pcur->next;
		free(pcur);
		pcur = del;
	}
	pcur = NULL;
	*ptr = NULL;
}

contact.c

#include"单链表contact.h"
#include"ListNode.h"

void ConAdd(contact** ptr)
{
	assert(ptr);
	printf("请输入添加的联系人的姓名  性别  年龄  住址  电话\n");
	person pes;
	scanf("%s", pes.name);
	scanf("%s", pes.gender);
	scanf("%d", &pes.age);
	scanf("%s", pes.addr);
	scanf("%s", pes.num);
	SLBackPush(ptr, pes);
}

void ConPrint(contact** ptr)
{
	assert(ptr);
	printf("姓名  性别  年龄  住址  电话\n");
	contact* pcur = *ptr;
	while (pcur)
	{
		printf("%s    %s     %d    %s    %s\n", pcur->data.name,
			pcur->data.gender,
			pcur->data.age,
			pcur->data.addr,
			pcur->data.num);
		pcur = pcur->next;
	}
}

void ConPop(contact** ptr)
{
	assert(ptr && *ptr);
	char NAME[NAME_MAX];
	printf("请输入你要删除的联系人的姓名：\n");
	scanf("%s", NAME);
	contact* pcur = *ptr;
	while (pcur)
	{
		if (strcmp(pcur->data.name,NAME)==0)
		{
			if (pcur==*ptr)
			{
				pcur = pcur->next;
				free(*ptr);
				*ptr = pcur;
				break;
			}
			else
			{
				contact* prev = *ptr;
				while (prev->next != pcur)
				{
					prev = prev->next;
				}
				prev->next = pcur->next;
				free(pcur);
				pcur = NULL;
				break;
			}
		}
		pcur = pcur->next;
	}
}

void ConFind(contact** ptr)
{
	assert(ptr && *ptr);
	char NAME[NAME_MAX];
	printf("请输入你要查找的联系人的姓名：\n");
	scanf("%s", NAME);
	contact* pcur = *ptr;
	while (pcur)
	{
		if (strcmp(pcur->data.name, NAME) == 0)
		{
			printf("姓名  性别  年龄  住址  电话\n");
			printf("%s  %s  %d  %s  %s\n", pcur->data.name,
				pcur->data.gender,
				pcur->data.age,
				pcur->data.addr,
				pcur->data.num);
		}
		pcur = pcur->next;
	}
}

void ConGai(contact** ptr)
{
	assert(ptr && *ptr);
	char NAME[NAME_MAX];
	printf("请输入你要修改的联系人的姓名：\n");
	scanf("%s", NAME);
	contact* pcur = *ptr;
	while (pcur)
	{
		if (strcmp(pcur->data.name, NAME) == 0)
		{
			printf("请输入修改后的联系人的姓名  性别  年龄  住址  电话\n");
			scanf("%s %s %d %s %s",
				pcur->data.name,
				pcur->data.gender,
				&pcur->data.age,
				pcur->data.addr,
				pcur->data.num);
		}
		pcur = pcur->next;
	}
}

void ConDesTroy(contact** ptr)
{
	assert(ptr && *ptr);
	contact* pcur = *ptr;
	while (pcur)
	{
		contact* del = pcur->next;
		free(pcur);
		pcur = del;
	}
	pcur = NULL;
}

最终实现的形式如下