数据结构--02链表拓展

第二节、链表拓展

1.双链表

（1）双链表定义与结构

双链表能够解决单链表的单向性的缺点。双链表是指每个节点都有指向其前驱与后继的指针，可以实现双向的操作。

我们可以简单定义它的结构体为：

typedef struct Node
{
    Elemtype data;
    struct Node *prior,*next;
}

（2）双链表的基本操作的实现

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

//双向链表结构体

typedef struct Node
{
	char name[20];
	struct Node* prior,* next;
}*LNode;


//初始创建n个节点
LNode create(int n)
{
	LNode p, head, s;
	p = (LNode)malloc(sizeof(Node));
	p->name[0] = '\0';
	p->prior = NULL;
	p->next = NULL;
	head = p;
	for (int i = 0; i < n; i++)
	{
		s = (LNode)malloc(sizeof(Node));
		printf("请输入第%d个学生的姓名：", i + 1);
		scanf("%s", s->name);
		p->next = s;
		s->prior = p;
		s->next = NULL;
		p = s;
	}
	p->next = NULL;
	return head;
}


//search 函数，查找要删除的节点，若找到，返回该节点的地址。
LNode search(LNode head, char* x)
{
	LNode p;
	char* y;
	p = head;
	while (p)
	{
		y = p->name;
		if (!strcmp(x, y))
			return p;
		else
		{
			p = p->next;
		}
	}
	printf("未找到该数据。\n");
}


//del函数，实现删除链表中指定的节点。

void del(LNode p)
{
	p->next->prior = p->prior;
	p->prior->next = p->next;
	free(p);
}


//Print函数，打印所有的节点数据；

void Print(LNode head)
{
	LNode p = head;
	while (p)
	{
		printf("%s\t", p->name);
		p = p->next;
	}
}

//main函数
int main()
{
	LNode head;
	int n;
	printf("请输入你要初始化的节点数量：");
	scanf("%d", &n);
	printf("\n");
	head = create(n);
	Print(head);

}

2.循环单链表

（1）循环单链表的定义与结构体

​ 循环单链表，可以想象为如下一个环形的链表:

​ 其中，head是一个指向头结点的指针，A,B,C,D,E分别是一个节点。我们可以把它的结构题简单的定义为：

typedef struct Node
{
	int num;
	struct Node* next;
}*LinkList;

（2）用头插法实现

#include <stdio.h>
#include <stdlib.h>
#include <corecrt_malloc.h>


//循环单链表，即理解为节点围成了一个圆，首尾相连。

typedef struct Node
{
	int num;
	struct Node* next;
}*LinkList;


//创建一个循环链表的首个节点
LinkList create()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	if (head == NULL)
	{
		printf("内存分配错误\n");
		exit(1);
	}
	else
	{
		head->next = head;
		return head;
	}
}


//往链表中插入新的节点(前插法）；

void Insert(LinkList head, int x)
{
	LinkList p = head;
	LinkList s = (LinkList)malloc(sizeof(Node));
	s->num = x;
	s->next = p->next;
	p->next = s;
	
}


//Print 打印链表所有元素
void Print(LinkList head)
{
	LinkList p = head->next;
	while (p->next!= head)
	{
		printf("%d\t", p->num);
		p = p->next;
	}
	printf("%d \n", p->num);
}


//main 函数

int main()
{
	LinkList head = create();
	for (int i = 1; i < 5; i++)
	{
		Insert(head, i);

	}
	Print(head);

	return 0;
}