[数据结构与算法]2021.9.23 C语言学习记录(双向链表)

双向链表

用结构体指针定义变量制作一个可以查增删改的双向链表存储信息

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef struct info_list
{
	int ID;
	char name[16];
	struct info_list* prev;//指向上一位的链表地址
	struct info_list* next;//指向下一位的链表地址
}INFO, * PINFO;


PINFO init_list(void);
PINFO make_list(void);
bool insert_list(PINFO p_node, PINFO node, PINFO n_node);
void show_list(PINFO phead);
void find_list(PINFO phead, char* name);
PINFO delete_list(PINFO phead, char* name);
PINFO change_list(PINFO phead, char* name);


int main(void)
{
	int num;

	//创建一个新的只带有空头的双向链表
	PINFO head = init_list();
	if (head == NULL)
		return -1;

	while (true)
	{
		printf("1.添加节点\t 2.遍历节点\t 3.排序节点\t 4.查询节点\t 5.删除节点\t 6.更改节点\t 0.退出\n");
		scanf("%d", &num);

		switch (num)
		{
		case 0:
			printf("退出程序！\n");
			exit(0);
		case 1:
		{
			printf("添加节点\n");
			PINFO pnew = make_list();
			if (pnew == NULL)
				return -1;

			//  insert_list(head,pnew, head->next ); // 头插
			insert_list(head->prev, pnew, head); // 尾插

			break;
		}
		case 2:
		{
			printf("遍历查询\n");
			show_list(head);
			break;
		}

		case 4:
		{
			//查找 ,按要求输入字符串，在已有的链表节点中找到它的完整信息，并显示出来
			char name[16];

			printf("please enter a Name : \n--");
			scanf("%s", name);

			find_list(head, name);

			break;
		}

		case 5:
		{
			//删除 ,按要求输入字符串，在已有的链表节点中找到后删除
			char name[16];

			printf("please enter a Name to delete : \n--");
			scanf("%s", name);

			delete_list(head, name);

			break;
		}
		case 6:
		{
			//更改节点信息 ,按要求输入字符串，在已有的链表节点中找到它的完整信息并更改
			char name[16];

			printf("please enter a Name to change : \n--");
			scanf("%s", name);

			change_list(head, name);

			break;
		}

		default:
			printf("非法字符,请重新输入\n");
			continue;
		}
	}

}

//初始化双向循环链表--头节点自循环
PINFO init_list(void)
{
	//给头节点申请新空间
	PINFO phead = (PINFO)malloc(sizeof(INFO));
	if (phead == NULL)
		return NULL;

	//头节点前后均指向自己 即头节点自循环
	phead->ID = 0;
	strcpy(phead->name, "");
	phead->next = phead;
	phead->prev = phead;

	return phead;

}

//申请节点并赋值 [创建新节点 存放在pnew中]
PINFO make_list(void)
{
	int ID;
	char Name[8];

	printf("请输入学号和姓名:");
	scanf("%d %s", &ID, Name);

	//给新节点申请新空间
	PINFO pnew = (PINFO)malloc(sizeof(INFO));
	if (pnew == NULL)
	{
		printf("创建新节点失败\n");
		return NULL;
	}

	//给新节点赋值 
	pnew->ID = ID;
	strcpy(pnew->name, Name);
	pnew->prev = pnew->next = pnew;

	return pnew;

}

//插入节点 形成新的关系: p<---->node<---->n_node
bool insert_list(PINFO p_node, PINFO node, PINFO n_node)
{
	if (p_node == NULL || node == NULL || n_node == NULL)
	{
		printf("插入节点失败!\n");
		return false;
	}

	//进行插入 告诉node的上家和下家是谁
	p_node->next = node;//先告诉上家 下家更改为node
	node->next = n_node;
	node->prev = p_node;
	n_node->prev = node;//最后再告诉下家 上家更改为node

	return true;
}

//遍历输出节点数据
void show_list(PINFO phead)
{
	PINFO p = phead->next;
	while (p != phead)
	{
		printf("ID:%d, name:%s\n", p->ID, p->name);
		p = p->next;
	}
}

//查询节点数据(函数代码相差不大)
void find_list(PINFO phead, char* name)
{
	PINFO p = phead->next;

	//遍历节点数据
	while (p != phead)
	{
		//把链表里的数据跟name配对
		if (strcmp(p->name, name) == 0)
		{
			printf("找到该名字\n");
			printf("ID=%d \t Name=%s \n", p->ID, p->name);
			return;
		}

		//如果双向链表遍历完一遍后没有配对成功
		if (p->next == phead)
		{
			printf("没有找到该名字\n");
			return;
		}
		p = p->next;
	}

}

//删除节点数据(函数代码相差不大)
PINFO delete_list(PINFO phead, char* name)
{
	PINFO p = phead->next;

	//遍历节点数据
	while (p != phead)
	{
		//把链表里的数据跟name配对
		if (strcmp(p->name, name) == 0)
		{
			将上一个的prev指向next再指向自己的next
			//p->prev->next = p->next;
			将自己的next指向自己的prev
			//p->next = p->prev;
			//同理
			PINFO x = p->prev;
			PINFO y = p->next;
			x->next = y;
			y->prev = x;


			free(p);

			return p;
		}

		//如果双向链表遍历完一遍后没有配对成功
		if (p->next == phead)
		{
			printf("没有找到该名字\n");
			return NULL;
		}
		p = p->next;
	}
}


//更改节点数据(函数代码相差不大)
PINFO change_list(PINFO phead, char* name)
{
	PINFO p = phead->next;

	//遍历链表
	while (p != phead)
	{
		//与name进行匹配
		if (strcmp((p->name), name) == 0)
		{
			int ID;
			char Name[8];
			printf("请输入要修改的数据:学号 姓名");
			scanf("%d %s",&ID,Name);

			//修改节点的参数
			p->ID = ID;
			strcpy((p->name),Name);

			return p;
		}

		if (p->next == phead)
		{
			printf("没有找到该名字");
			return NULL;
		}

		p->next;
	}
}