[数据结构与算法]创建双向链表

问题描述

创建一个双向链表，并将这个链表中的数据输出在窗体上，输入要查找的学生姓名，将查找的姓名

从链表中删除，并显示删除后的链表。

算法分析

引用头文件

#include <stdio.h>
#include <malloc.h>
#include <string.h>

声明结构体类型

?typedef struct MyStruct
{
?? ?char name[20];
?? ?struct MyStruct *prior,*next;
}stud;

自定义creat(),实现创建一个双向链表，将此函数定义为指针类型，使其返回值为指针值，返回值指向一个struct? Mystruct类型数据，实际上返回链表的头指针。代码如下：

stud *create(int n)
{
	stud *p, *h, *s;
	int i;
	h = (stud*)malloc(sizeof(stud));
	h->name[0] = '\0';
	h->prior = NULL;
	h->next = NULL;
	p = h;
	for (i = 0; i < n; i++)
	{
		s = (stud*)malloc(sizeof(stud));
		p->next = s;
		printf("输入第%d个学后的姓名：",i + 1);
		scanf_s("%s", s->name,20);
		s->prior = p;
		s->next = NULL;
		p = s;
	}
	p->next = NULL;
	return h;
}

自定义函数search(),实现查找删除的节点，如果找到则返回这个节点的地址，代码如下：

stud *search(stud *h, char *x)
{
	stud *p;
	char *y;
	p = h->next;
	while (p)
	{
		y = p->name;
		if (strcmp(y, x) == 0) {
			return p;
		}
		else
		   p = p->next;
	}
	
	printf("没有找到数据！\n");
	return NULL;
}

自定义函数del(),实现删除链表中指定的节点，代码如下：

void del(stud *p) {
?? ?if (p->next == NULL) {
?? ??? ?p->prior->next = NULL;
?? ??? ?free(p);
?? ?}
?? ?else
?? ?{
?? ??? ?p->next->prior = p->prior;
?? ??? ?p->prior->next = p->next;
?? ??? ?free(p);
?? ?}
?? ?
}?

技术要点

双向链表的节点有两个指针域，一个指向其直接后继，另一个指向其直接前驱。其结构如图所示：

?

可以看出双向链表的关系

下面实现代码如下：?

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct MyStruct
{
	char name[20];
	struct MyStruct *prior,*next;
}stud;

stud *create(int n)
{
	stud *p, *h, *s;
	int i;
	h = (stud*)malloc(sizeof(stud));
	h->name[0] = '\0';
	h->prior = NULL;
	h->next = NULL;
	p = h;
	for (i = 0; i < n; i++)
	{
		s = (stud*)malloc(sizeof(stud));
		p->next = s;
		printf("输入第%d个学后的姓名：",i + 1);
		scanf_s("%s", s->name,20);
		s->prior = p;
		s->next = NULL;
		p = s;
	}
	p->next = NULL;
	return h;
}

stud *search(stud *h, char *x)
{
	stud *p;
	char *y;
	p = h->next;
	while (p)
	{
		y = p->name;
		if (strcmp(y, x) == 0) {
			return p;
		}
		else
		   p = p->next;
	}
	
	printf("没有找到数据！\n");
	return NULL;
}

void del(stud *p) {
	if (p->next == NULL) {
		p->prior->next = NULL;
		free(p);
	}
	else
	{
		p->next->prior = p->prior;
		p->prior->next = p->next;
		free(p);
	}
	
}

int main(void) {
	int number;
	char sname[20];
	stud *head, *sp;
	puts("请输入链表的大小：");
	scanf_s("%d", &number);
	head = create(number);
	sp = head->next;
	printf("\n现在这个双向链表是：\n");
	while (sp)
	{
		printf("%s ", &*(sp->name));//%s是字符串解析，所以要解引后的取地址
		sp = sp->next;
	}

	printf("\n请输入你想查找的姓名：\n");
	scanf_s("%s", sname,20);
	sp = search(head, sname);
	printf("你想查找的姓名是：%s\n", sp->name);
	del(sp);
	sp = head->next;
	printf("现在这个双链表是：\n");
	while (sp)
	{
		printf("%s ", &*(sp->name));//%s是字符串解析，所以要解引后的取地址
		sp = sp->next;
	}
	printf("\n");
	puts("\n按任意键退出...");

	return 0;
}

其输出结果如下

请输入链表的大小：
5
输入第1个学后的姓名：jiajia
输入第2个学后的姓名：duoduo
输入第3个学后的姓名：xiaoxiao
输入第4个学后的姓名：mingming
输入第5个学后的姓名：huanhuan

现在这个双向链表是：
jiajia duoduo xiaoxiao mingming huanhuan
请输入你想查找的姓名：
duoduo
你想查找的姓名是：duoduo
现在这个双链表是：
jiajia xiaoxiao mingming huanhuan

按任意键退出...

?