底层架构 WEB视频自适应 Hibernate Gradle ios npm silverlight vuejs2 虚拟机 joomla devise 前端vue框架 jq获取元素 hadoop入门书籍 清空input文本框的值 js原生点击事件 pythonsocket编程 python安装mysql pythonfor循环 python中time python模块下载 java开发 java学习基础 java终止线程 java匿名函数 java中获取当前时间 java遍历list集合 javastringbuilder php语言入门 广告代码 心理学与生活下载 shutil kms神龙 java语言程序设计 什么模拟器最好 小洛快跑 电脑cmd命令大全 微信临时链接多久失效 暴力猴插件 免费ftp空间
当前位置: 首页 > 学习教程  > 编程语言

线性表的链式存储-双向循环链表,认识的无限性

2021/1/28 23:38:12 文章标签:

一.一字一句的血汗代码 1.Tools.h #define VerticalGap 1 //操作菜单的行间距 #define SPAN 50 //操作菜单的横向距离void outputOperatingMenu(char** menu, int length); void duplicate(char* token, int amount); void inputData(char* hint, char* type, void* data)…

一.一字一句的血汗代码


1.Tools.h

#define VerticalGap 1		//操作菜单的行间距
#define SPAN 50				//操作菜单的横向距离

void outputOperatingMenu(char** menu, int length);
void duplicate(char* token, int amount);
void inputData(char* hint, char* type, void* data);

2.Tools.c

#include"Tools.h"

void outputOperatingMenu(char** menu, int length)
{
	duplicate("-", SPAN);
	duplicate("\n", 1);
	int gap;
	for (int i = 0; i < length; i++)
	{
		printf("-");
		gap = SPAN - strlen(*(menu + i)) - 2;
		if (gap % 2 == 0)
			duplicate(" ", gap / 2);
		else
			duplicate(" ", gap / 2 + 1);
		printf("%s", menu[i]);
		duplicate(" ", gap / 2);
		printf("-");
		duplicate("\n", VerticalGap);
	}
	duplicate("-", SPAN);
	printf("\n");
}

void duplicate(char* token, int amount)
{
	for (int i = 0; i < amount; i++)
	{
		printf("%s", token);
	}
}

void inputData(char* hint, char* type, void* data)
{
	printf("%s", hint);
	scanf(type, data);
	printf("\n");
}



3.CircularDoubleLinkedList.h

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define status int
#define YES 1
#define NO -1
#define ListIsEmpty 0
#define InvalidPosition -2
#define InvalidData -3
#define NullPointer -5
#define DataLength 15

typedef struct doubleNode
{
	struct doubleNode* prior;
	struct doubleNode* next;
	void* data;
}* DoubleNodePointer,DoubleNode;

DoubleNodePointer initializeCircularDoubleLinkedList();
DoubleNodePointer createCircularDoubleLinkedList(DoubleNodePointer rearPointer,int length);
int getLength(DoubleNodePointer rearPointer);
void setLength(DoubleNodePointer rearPoiner, int length);
status isEmpty(DoubleNodePointer rearPointer);
void manifestForwardsForCircularDoubleLinkedList(DoubleNodePointer rearPointer);
void manifestBackwardsCircularDoubleLinkedList(DoubleNodePointer rearPointer);
status appendNodeForCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer,void* data);
DoubleNodePointer getNodeViaPosition(DoubleNodePointer rearPointer, int position);
int locateNodeForCircularDoubleLinkedList(DoubleNodePointer rearPointer, void* data);
void clearCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer);
status insertForCircularDoubleLinkedList(DoubleNodePointer rearPointer, int position, void* data);
status deleteForCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer, int position);
status modifyForCircularDoubleLinkedList(DoubleNodePointer rearPointer, int position, void* data);
status inverseForCircularDoubleLinkedList(DoubleNodePointer rearPointer);
status sortForCircularDoubleLinkedList(DoubleNodePointer rearPointer);
void conclude(int state);

4.CircularDoubleLinkedList.c

#include"CircularDoubleLinkedList.h"

DoubleNodePointer initializeCircularDoubleLinkedList()
{
	DoubleNodePointer originalPointer = (DoubleNodePointer)malloc(sizeof(DoubleNode));
	if (originalPointer == NULL)
	{
		printf("The Original Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	originalPointer->data = malloc(sizeof(int));
	if (originalPointer->data == NULL)
	{
		printf("The Data Scope Of Original Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	*(int*)(originalPointer->data)=0;
	originalPointer->prior = originalPointer;
	originalPointer->next = originalPointer;
	return originalPointer;
}

DoubleNodePointer createCircularDoubleLinkedList(DoubleNodePointer originalPointer, int length)
{
	DoubleNodePointer rearPointer = originalPointer;
	DoubleNodePointer newbornPointer = NULL;
	for (int i = 0; i < length; i++)
	{
		newbornPointer = (DoubleNodePointer)malloc(sizeof(DoubleNode));
		if (newbornPointer == NULL)
		{
			printf("The Newborn Node Failed To Allocate Memory !\n");
			exit(-1);
		}
		newbornPointer->data =malloc(sizeof(char)*DataLength);
		if (newbornPointer->data == NULL)
		{
			printf("The Data Scope Of Newborn Node Failed To Allocate Memory !\n");
			exit(-1);
		}
		printf("The Data Of Node %d:\t", i + 1);
		scanf("%s",(char*)newbornPointer->data);
		newbornPointer->prior = rearPointer;
		newbornPointer->next = NULL;
		rearPointer->next = newbornPointer;
		rearPointer = newbornPointer;
	}
	originalPointer->prior = rearPointer;
	rearPointer->next = originalPointer;
	setLength(rearPointer, length);
	return rearPointer;
}

int getLength(DoubleNodePointer rearPointer)
{
	return *(int*)rearPointer->next->data;
}

void setLength(DoubleNodePointer rearPoiner, int length)
{
	DoubleNodePointer originalPointer = rearPoiner->next;
	*(int*)originalPointer->data = length;
}

void manifestForwardsForCircularDoubleLinkedList(DoubleNodePointer rearPointer)
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return;
	}
	DoubleNodePointer originalPointer = rearPointer->next;
	DoubleNodePointer frontPointer = rearPointer->next->next;
	printf("[");
	while (frontPointer!= originalPointer)
	{
		if (frontPointer->next != originalPointer)
			printf("  %s,",(char*)frontPointer->data);
		else
			printf("  %s  ", (char*)frontPointer->data);
		frontPointer = frontPointer->next;
	}
	printf("]\n");
}

void manifestBackwardsCircularDoubleLinkedList(DoubleNodePointer rearPointer)
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return;
	}
	DoubleNodePointer originalPointer = rearPointer->next;
	printf("[");
	for (;rearPointer!=originalPointer;rearPointer=rearPointer->prior)
	{
		if (rearPointer->prior != originalPointer)
			printf("  %s,", (char*)(rearPointer->data));
		else
			printf("  %s  ", (char*)(rearPointer->data));
	}
	printf("]\n");
}

status appendNodeForCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer,void* data)
{
	if (*rearPointerPointer == NULL)
	{
		conclude(NullPointer);
		return NO;
	}
	DoubleNodePointer newbornPointer = (DoubleNodePointer)malloc(sizeof(DoubleNode));
	if (newbornPointer == NULL)
	{
		printf("The Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	newbornPointer->data =malloc(sizeof(char)*DataLength);
	if (newbornPointer->data == NULL)
	{
		printf("The Data Scope Of Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	strcpy((char*)(newbornPointer->data),(char*)data);
	DoubleNodePointer originalPointer = (*rearPointerPointer)->next;
	newbornPointer->prior = *rearPointerPointer;
	newbornPointer->next = originalPointer;
	originalPointer->prior =newbornPointer;
	(*rearPointerPointer)->next = newbornPointer;
	*rearPointerPointer = newbornPointer;
	setLength(*rearPointerPointer,getLength(*rearPointerPointer)+1);
	return YES;
}

DoubleNodePointer getNodeViaPosition(DoubleNodePointer rearPointer, int position)
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return NULL;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return NULL;
	}	
	int end = getLength(rearPointer);
	DoubleNodePointer originalPointer = rearPointer->next;
	for (; end > position && rearPointer!= originalPointer; end--, rearPointer = rearPointer->prior);
	if (end < position || rearPointer==originalPointer)
	{
		conclude(InvalidPosition);
		return NULL;
	}
	return rearPointer;
}

int locateNodeForCircularDoubleLinkedList(DoubleNodePointer rearPointer, void* data)
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return -1;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return -1;
	}

	int begin = 1;
	int end = getLength(rearPointer);
	DoubleNodePointer frontPointer = rearPointer->next->next;
	while (begin <= end)
	{
		if (strcmp((char*)frontPointer->data, (char*)data) == 0)
		{
			return begin;
		}
		if (strcmp((char*)rearPointer->data, (char*)data) == 0)
		{
			return end;
		}

		frontPointer = frontPointer->next;
		++begin;
		rearPointer = rearPointer->prior;
		--end;
	}
	conclude(InvalidData);
	return -1;
}

status isEmpty(DoubleNodePointer rearPointer)
{
	if (rearPointer->prior==rearPointer && rearPointer->next==rearPointer)
		return YES;
	return NO;
}

void clearCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer)
{
	if ((*rearPointerPointer) == NULL)
	{
		conclude(NullPointer);
		return;
	}
	if (isEmpty((*rearPointerPointer)) == YES)
	{
		conclude(ListIsEmpty);
		free((*rearPointerPointer)->next);
		printf("The Original Node has been released completely !\n");
		*rearPointerPointer = NULL;
		return;
	}
	DoubleNodePointer originalPointer = (*rearPointerPointer)->next;
	DoubleNodePointer temporaryPointer = NULL;
	char data[DataLength]="\0";
	int originalData;
	while((*rearPointerPointer)!=originalPointer)
	{
		temporaryPointer = (*rearPointerPointer);
		strcpy(data, (*rearPointerPointer)->data);
		(*rearPointerPointer) = (*rearPointerPointer)->prior;
		free(temporaryPointer->data);
		free(temporaryPointer);
		printf("The Node\t%s\t has been released completely !\n", (char*)data);
	}
	originalData =*(int*)originalPointer->data;
	free(originalPointer->data);
	free(originalPointer);
	printf("The Original Node\t%d\thas been released completely !\n",originalData);
	*rearPointerPointer = NULL;
}

status insertForCircularDoubleLinkedList(DoubleNodePointer rearPointer, int position, void* data)
{
	DoubleNodePointer aimPointer = getNodeViaPosition(rearPointer,position);
	if (aimPointer == NULL)
		return NO;

	DoubleNodePointer newbornPointer =(DoubleNodePointer)malloc(sizeof(DoubleNode));
	if (newbornPointer == NULL)
	{
		printf("The Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	newbornPointer->data = malloc(sizeof(char) * DataLength);
	if (newbornPointer->data == NULL)
	{
		printf("The Data Scope Of Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	strcpy((char*)newbornPointer->data, (char*)data);
	newbornPointer->prior = aimPointer->prior;
	newbornPointer->next = aimPointer;
	aimPointer->prior->next = newbornPointer;
	aimPointer->prior = newbornPointer;
	setLength(rearPointer, getLength(rearPointer) + 1);
	return YES;
}

status deleteForCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer, int position)
{
	DoubleNodePointer destinationPointer = getNodeViaPosition((*rearPointerPointer), position);
	if (destinationPointer == NULL)
		return NO;
	
	destinationPointer->prior->next= destinationPointer->next;
	destinationPointer->next->prior = destinationPointer->prior;
	if (destinationPointer == (*rearPointerPointer))
		*rearPointerPointer = destinationPointer->prior;
	free(destinationPointer);
	setLength(*rearPointerPointer, getLength(*rearPointerPointer) - 1);
	return YES;
}

status modifyForCircularDoubleLinkedList(DoubleNodePointer rearPointer, int position, void* data)
{
	DoubleNodePointer purposePointer = getNodeViaPosition(rearPointer, position);
	if (purposePointer == NULL)
		return NO;
	strcpy((char*)purposePointer->data, (char*)data);
	return YES;
}

status inverseForCircularDoubleLinkedList(DoubleNodePointer rearPointer)
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return NO;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return NO;
	}
		
	DoubleNodePointer originalPointer = rearPointer->next;
	DoubleNodePointer frontPointer = rearPointer->next->next;
	int begin = 1;
	int end = getLength(rearPointer);
	void* data=NULL;
	while (begin <= end)
	{
		data = rearPointer->data;
		rearPointer->data = frontPointer->data;
		frontPointer->data = data;
		frontPointer = frontPointer->next;
		++begin;
		rearPointer = rearPointer->prior;
		--end;
	}
	return YES;
}

status sortForCircularDoubleLinkedList(DoubleNodePointer rearPointer)//插入排序
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return NO;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return NO;
	}

	DoubleNodePointer originalPointer = rearPointer->next;//起源结点
	DoubleNodePointer currentPointer = rearPointer->next->next->next;//第二个有效结点
	DoubleNodePointer frontPointer=NULL;
	char* data;
	for (; currentPointer!= originalPointer; currentPointer = currentPointer->next)
	{
		data =(char*)currentPointer->data;
		frontPointer = currentPointer->prior;
		if (strcmp(data,(char*)frontPointer->data) > 0)
			continue;
		for (frontPointer = currentPointer->prior; strcmp(data,(char*)frontPointer->data) < 0; frontPointer = frontPointer->prior)
		{
			frontPointer->next->data = frontPointer->data;
		}
		frontPointer->next->data = data;
	}
	return YES;
}

void conclude(int state)
{
	if (state ==ListIsEmpty)
	{
		printf("The CircularDoubleLinkedList Is Empty !\n");
	}else if(state==InvalidPosition)
	{ 
		printf("INVALID POSITION !\n");
	}else if (state == NullPointer)
	{
		printf("Null Pointer !\n\nThe CircularDoubleLinkedList may not be constructed !\n ");
	}
	else if (state == InvalidData)
	{
		printf("Invalid Data !\n");
	}
}

5.main.c

#include"CircularDoubleLinkedList.h"
#include"Tools.h"
void main()
{
	char* operatingMenu[] =
	{
		"CircularDoubleLinkedList",
		"1.Create",
		"2.Clear",
		"3.Sort",
		"4.Inverse",
		"5.Manifest Backwards",
		"6.Append Node",
		"7.Insert Node",
		"8.Delete Node",
		"9.Modify Node",
		"10.Get Node",
		"11.Locate Node",
		"12.Exit"
	};
	int position=0, state=0,digit=0,length=0;
	char data[15]="\0";
	DoubleNodePointer rearPointer = NULL,aimPointer=NULL;

	while (1)
	{
		system("cls");
		state = 0;
		outputOperatingMenu(operatingMenu, sizeof(operatingMenu) / sizeof(char*));
		if (rearPointer != NULL && isEmpty(rearPointer) == NO)
		{
			printf("Length:\t%d\n\n", getLength(rearPointer));
			printf("Data:\t");
			manifestForwardsForCircularDoubleLinkedList(rearPointer);
		}
		if (rearPointer != NULL && isEmpty(rearPointer) == YES)
		{
			printf("The Circular Linked List Is Empty !\n");
		}
		printf("\n");
		inputData("Type in digit:\t", "%d", &digit);
		switch (digit)
		{
		case 1:
			if (rearPointer != NULL && isEmpty(rearPointer) == NO)
			{
				clearCircularDoubleLinkedList(&rearPointer);
			}
			inputData("Length of CircularDoubleLinkedList:\t", "%d", &length);
			if (length <= 0)
			{
				printf("Invalid Length !\n");
				continue;
			}
			rearPointer = createCircularDoubleLinkedList(initializeCircularDoubleLinkedList(), length);
			printf("The CircularDoubleLinkedList has been constructed completely !\n");
			break;
		case 2:
			clearCircularDoubleLinkedList(&rearPointer);
			break;
		case 3:
			state = sortForCircularDoubleLinkedList(rearPointer);
			break;
		case 4:
			state = inverseForCircularDoubleLinkedList(rearPointer);
			break;
		case 5:
			manifestBackwardsCircularDoubleLinkedList(rearPointer);
			break;
		case 6:
			inputData("Data:\t", "%s", data);
			state=appendNodeForCircularDoubleLinkedList(&rearPointer,data);	
			break;
		case 7:
			inputData("Position:\t", "%d", &position);
			inputData("Data:\t", "%s", data);
			state = insertForCircularDoubleLinkedList(rearPointer, position, data);
			break;
		case 8:
			inputData("Position:\t", "%d", &position);
			state = deleteForCircularDoubleLinkedList(&rearPointer, position);
			break;
		case 9:
			inputData("Position:\t", "%d", &position);
			inputData("Data:\t", "%s", data);
			state = modifyForCircularDoubleLinkedList(rearPointer, position, data);
			break;
		case 10:
			inputData("Position:\t", "%d", &position);
			aimPointer = getNodeViaPosition(rearPointer, position);
			if (aimPointer != NULL)
				printf("Data:\t%s\n", (char*)aimPointer->data);
			break;
		case 11:
			inputData("Data:\t", "%s", data);
			position = locateNodeForCircularDoubleLinkedList(rearPointer, data);
			if (position != -1)
			{
				printf("Position:\t%d\n", position);
			}
			break;
		case 12:
			if(rearPointer!=NULL)
			{
				clearCircularDoubleLinkedList(&rearPointer);
			}
			printf("You have already exited !\n\n");
			system("pause");
			exit(-1);
			break;
		}
		if (state==YES)
		{
			printf("Data manipulation have been completed !\n\n");
			manifestForwardsForCircularDoubleLinkedList(rearPointer);
		}
		printf("\n");
		system("pause");
	}
	
}


二、注解关键代码

CircularDoubleLinkedList.c


#include"CircularDoubleLinkedList.h"

DoubleNodePointer initializeCircularDoubleLinkedList()//初始化双向循环链表,生成其起源结点
{
	DoubleNodePointer originalPointer = (DoubleNodePointer)malloc(sizeof(DoubleNode));//创建起源结点
	if (originalPointer == NULL)
	{
		printf("The Original Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	originalPointer->data = malloc(sizeof(int));//创建起源结点的数据域,用来存储双向循环链表的长度
	if (originalPointer->data == NULL)
	{
		printf("The Data Scope Of Original Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	*(int*)(originalPointer->data)=0;			//初始化起源结点的成员变量
	originalPointer->prior = originalPointer;
	originalPointer->next = originalPointer;
	return originalPointer;						//返回起源结点指针
}

DoubleNodePointer createCircularDoubleLinkedList(DoubleNodePointer originalPointer, int length)//创建双向循环链表
{
	DoubleNodePointer rearPointer = originalPointer;//将传入的起源结点作为尾结点进行处理
	DoubleNodePointer newbornPointer = NULL;
	for (int i = 0; i < length; i++)
	{
		newbornPointer = (DoubleNodePointer)malloc(sizeof(DoubleNode));//创建后续的新结点
		if (newbornPointer == NULL)
		{
			printf("The Newborn Node Failed To Allocate Memory !\n");
			exit(-1);
		}
		newbornPointer->data =malloc(sizeof(char)*DataLength);//创建新结点的数据域
		if (newbornPointer->data == NULL)
		{
			printf("The Data Scope Of Newborn Node Failed To Allocate Memory !\n");
			exit(-1);
		}
		printf("The Data Of Node %d:\t", i + 1);
		scanf("%s",(char*)newbornPointer->data);//为新结点的数据域录入数据
		newbornPointer->prior = rearPointer;//新结点的前指针域指向尾结点
		newbornPointer->next = NULL;//新结点的后指针为空
		rearPointer->next = newbornPointer;//尾结点的后指针指向新结点
		rearPointer = newbornPointer;//双向循环链表的尾结点变成新结点
	}
	originalPointer->prior = rearPointer;//起源结点的前指针域指向尾结点
	rearPointer->next = originalPointer;//尾结点的后指针指向起源结点
	setLength(rearPointer, length);//设置双向循环链表的长度
	return rearPointer;//返回尾指针
}

int getLength(DoubleNodePointer rearPointer)//获取双向循环链表的有效结点长度
{
	return *(int*)rearPointer->next->data;//由尾结点到起源结点,从起源结点的数据域中取出双向循环链表的长度
}

void setLength(DoubleNodePointer rearPoiner, int length)//设置双向循环链表的有效长度
{
	DoubleNodePointer originalPointer = rearPoiner->next;//由尾结点到起源结点
	*(int*)originalPointer->data = length;//给起源结点的数据域赋值
}

void manifestForwardsForCircularDoubleLinkedList(DoubleNodePointer rearPointer)//正向遍历双向循环链表
{
	if (rearPointer == NULL)//若传入的尾指针为空,则报出空指针的异常信息
	{
		conclude(NullPointer);
		return;
	}
	if (isEmpty(rearPointer) == YES)//若双向循环链表为空,则报出表为空的异常信息
	{
		conclude(ListIsEmpty);
		return;
	}
	DoubleNodePointer originalPointer = rearPointer->next;//由尾结点到起源结点
	DoubleNodePointer frontPointer = rearPointer->next->next;//由尾结点到首结点
	printf("[");
	while (frontPointer!= originalPointer)//从首结点向后运动,若回到起源结点,结束循环
	{
		if (frontPointer->next != originalPointer)//当前结点是否到达尾结点,判断依据为"尾结点的后继结点就是起源结点"
			printf("  %s,",(char*)frontPointer->data);
		else
			printf("  %s  ", (char*)frontPointer->data);
		frontPointer = frontPointer->next;//结点向后运动
	}
	printf("]\n");
}

void manifestBackwardsCircularDoubleLinkedList(DoubleNodePointer rearPointer)//反向遍历双向循环链表
{
	if (rearPointer == NULL)//若传入的尾指针为空,则报出空指针的异常信息
	{
		conclude(NullPointer);
		return;
	}
	if (isEmpty(rearPointer) == YES)//若双向循环链表为空,则报出表为空的异常信息
	{
		conclude(ListIsEmpty);
		return;
	}
	DoubleNodePointer originalPointer = rearPointer->next;//由尾结点到起源结点
	printf("[");
	for (;rearPointer!=originalPointer;rearPointer=rearPointer->prior)//从尾结点向起源结点运动,若到达起源结点,结束循环
	{
		if (rearPointer->prior != originalPointer)//当前结点是否到达首结点,判断依据为"首结点的前驱结点就是起源结点"
			printf("  %s,", (char*)(rearPointer->data));
		else
			printf("  %s  ", (char*)(rearPointer->data));
	}
	printf("]\n");
}

status appendNodeForCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer,void* data)//追加结点
{
	if (*rearPointerPointer == NULL)//若传入的尾指针为空,则报出空指针的异常信息
	{
		conclude(NullPointer);
		return NO;//返回状态值NO
	}
	DoubleNodePointer newbornPointer = (DoubleNodePointer)malloc(sizeof(DoubleNode));//创建新结点
	if (newbornPointer == NULL)
	{
		printf("The Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	newbornPointer->data =malloc(sizeof(char)*DataLength);//为新结点创建数据域,用于存储字符串
	if (newbornPointer->data == NULL)
	{
		printf("The Data Scope Of Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	strcpy((char*)(newbornPointer->data),(char*)data);//为新结点的数据域赋值
	DoubleNodePointer originalPointer = (*rearPointerPointer)->next;//从尾结点到起源结点
	newbornPointer->prior = *rearPointerPointer;//新结点的前指针域指向尾结点
	newbornPointer->next = originalPointer;//新结点的后指针指向起源结点
	originalPointer->prior =newbornPointer;//起源结点的前指针域指向新结点
	(*rearPointerPointer)->next = newbornPointer;//尾结点的后指针指向新结点
	*rearPointerPointer = newbornPointer;//此时的新结点已成为尾结点,变更方法外的尾指针变量
	setLength(*rearPointerPointer,getLength(*rearPointerPointer)+1);//双向循环链表的长度加1
	return YES;//返回状态值YES
}

DoubleNodePointer getNodeViaPosition(DoubleNodePointer rearPointer, int position)//按下标获取对应结点
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return NULL;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return NULL;
	}	
	int end = getLength(rearPointer);//读取双向循环链表的有效长度
	DoubleNodePointer originalPointer = rearPointer->next;//从尾结点到起源结点
	for (; end > position && rearPointer!= originalPointer; end--, rearPointer = rearPointer->prior);
	/*该循环颇为烧脑,一番深入钻研,掌握其中道理,自信也会随之而来
	 尾结点由其前指针向起源结点运动,且每个结点都有相应的逻辑下标
	 若循环提前结束,要么传入下标无效,要么尾结点已运动到起源结点
	 end<position抑制下标右越界的情况 rearPointer==originalPointer抑制下标左越界的情况
	 */
	if (end < position || rearPointer==originalPointer)
	{
		conclude(InvalidPosition);
		return NULL;
	}
	return rearPointer;
}

int locateNodeForCircularDoubleLinkedList(DoubleNodePointer rearPointer, void* data)//根据结点数据,获取对应下标
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return -1;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return -1;
	}

	int begin = 1;//首结点下标
	int end = getLength(rearPointer);//尾结点下标,即双向循环链表的有效长度
	DoubleNodePointer frontPointer = rearPointer->next->next;//由尾结点到首结点
	while (begin <= end)//从双向循环链表的两端向中间搜索
	{
		if (strcmp((char*)frontPointer->data, (char*)data) == 0)//从首结点向后搜索
		{
			return begin;
		}
		if (strcmp((char*)rearPointer->data, (char*)data) == 0)//从尾结点向前搜索
		{
			return end;
		}

		frontPointer = frontPointer->next;//由首结点向后运动
		++begin;//对应结点下标加1
		rearPointer = rearPointer->prior;//由尾结点向前运动
		--end;//对应结点下标减1
	}
	conclude(InvalidData);//搜索无果后,给出"无效数据"信息
	return -1;
}

status isEmpty(DoubleNodePointer rearPointer)//判断双向循环链表是否为空
{
	//如果结点的前后指针均指向其本身,则表明双向循环链表只有一个起源结点,这种情况下表就为空
	if (rearPointer->prior==rearPointer && rearPointer->next==rearPointer)
		return YES;
	return NO;
}

void clearCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer)//销毁双向循环链表
{
	if ((*rearPointerPointer) == NULL)
	{
		conclude(NullPointer);
		return;
	}
	if (isEmpty((*rearPointerPointer)) == YES)//若双向循环链表为空
	{
		conclude(ListIsEmpty);//报出表为空的异常信息
		free((*rearPointerPointer)->next);//释放起源结点
		printf("The Original Node has been released completely !\n");
		*rearPointerPointer = NULL;//方法外的尾指针变量置空
		return;
	}
	DoubleNodePointer originalPointer = (*rearPointerPointer)->next;
	DoubleNodePointer temporaryPointer = NULL;
	char data[DataLength]="\0";
	int originalData;
	while((*rearPointerPointer)!=originalPointer)//从尾结点向起源结点运动,若运动到起源结点,结束循环
	{
		temporaryPointer = (*rearPointerPointer);//先存储待销毁结点的指针
		strcpy(data, (*rearPointerPointer)->data);
		(*rearPointerPointer) = (*rearPointerPointer)->prior;//再从待销毁结点运动至其前驱结点
		free(temporaryPointer->data);//释放待销毁结点的数据域
		free(temporaryPointer);//释放待销毁结点
		printf("The Node\t%s\t has been released completely !\n", (char*)data);
	}
	originalData =*(int*)originalPointer->data;
	free(originalPointer->data);//释放起源结点的数据域
	free(originalPointer);//释放起源结点
	printf("The Original Node\t%d\thas been released completely !\n",originalData);
	*rearPointerPointer = NULL;// 方法外的尾指针变量置空
}

status insertForCircularDoubleLinkedList(DoubleNodePointer rearPointer, int position, void* data)//插入结点
{
	DoubleNodePointer aimPointer = getNodeViaPosition(rearPointer,position);//获取指定下标的目标结点
	if (aimPointer == NULL)
		return NO;

	DoubleNodePointer newbornPointer =(DoubleNodePointer)malloc(sizeof(DoubleNode));//创建新结点
	if (newbornPointer == NULL)
	{
		printf("The Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	newbornPointer->data = malloc(sizeof(char) * DataLength);//为新结点创建数据域
	if (newbornPointer->data == NULL)
	{
		printf("The Data Scope Of Newborn Node Failed To Allocate Memory !\n");
		exit(-1);
	}
	strcpy((char*)newbornPointer->data, (char*)data);//为新结点的数据域赋值
	newbornPointer->prior = aimPointer->prior;//新结点的前指针域指向目标结点的前驱结点
	newbornPointer->next = aimPointer;//新结点的后指针域指向目标结点
	aimPointer->prior->next = newbornPointer;//目标结点的前驱结点的后指针域指向新结点
	aimPointer->prior = newbornPointer;//目标结点的前指针域指向新结点
	setLength(rearPointer, getLength(rearPointer) + 1);
	return YES;
}

status deleteForCircularDoubleLinkedList(DoubleNodePointer* rearPointerPointer, int position)//删除结点
{
	DoubleNodePointer destinationPointer = getNodeViaPosition((*rearPointerPointer), position);//获取指定下标的目标结点
	if (destinationPointer == NULL)
		return NO;
	
	destinationPointer->prior->next= destinationPointer->next;//目标结点的前驱结点的后指针域指向目标结点的后继结点
	destinationPointer->next->prior = destinationPointer->prior;//目标结点的后继结点的前指针域指向目标结点的前驱结点
	if (destinationPointer == (*rearPointerPointer))//若删除的目标结点为尾结点
		*rearPointerPointer = destinationPointer->prior;//将方法外的尾指针变量变更为尾结点的前驱结点指针
	free(destinationPointer);//释放目标结点
	setLength(*rearPointerPointer, getLength(*rearPointerPointer) - 1);
	return YES;
}

status modifyForCircularDoubleLinkedList(DoubleNodePointer rearPointer, int position, void* data)//修改指定结点数据
{
	DoubleNodePointer purposePointer = getNodeViaPosition(rearPointer, position);//获取目标结点
	if (purposePointer == NULL)
		return NO;
	strcpy((char*)purposePointer->data, (char*)data);//修改目标结点数据域的数据
	return YES;
}

status inverseForCircularDoubleLinkedList(DoubleNodePointer rearPointer)//逆转双向循环链表
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return NO;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return NO;
	}
		
	DoubleNodePointer originalPointer = rearPointer->next;//从尾结点到起源结点
	DoubleNodePointer frontPointer = rearPointer->next->next;//从尾结点到首结点
	int begin = 1;//首结点的逻辑下标
	int end = getLength(rearPointer);//尾结点的逻辑下标
	void* data=NULL;
	while (begin <= end)//从双向循环链表的两端向中间运动,当两端结点在运动中碰撞后,结束循环
	{
		data = rearPointer->data;//存储尾端结点的数据
		rearPointer->data = frontPointer->data;//将首端结点的数据赋值给尾端结点
		frontPointer->data = data;//将尾端结点的数据赋值给首端结点
		frontPointer = frontPointer->next;//首端结点向后运动
		++begin;//其逻辑下标加1
		rearPointer = rearPointer->prior;//尾端结点向前运动
		--end;//其逻辑下标减1
	}
	return YES;
}

status sortForCircularDoubleLinkedList(DoubleNodePointer rearPointer)//排序,这里选用插入排序
{
	if (rearPointer == NULL)
	{
		conclude(NullPointer);
		return NO;
	}
	if (isEmpty(rearPointer) == YES)
	{
		conclude(ListIsEmpty);
		return NO;
	}

	DoubleNodePointer originalPointer = rearPointer->next;//起源结点
	DoubleNodePointer currentPointer = rearPointer->next->next->next;//第二个有效结点
	DoubleNodePointer frontPointer=NULL;
	char* data;
	for (; currentPointer!= originalPointer; currentPointer = currentPointer->next)//从第二个结点向后运动,到达起源结点,结束循环
	{
		data =(char*)currentPointer->data;//存储当前结点的数据
		frontPointer = currentPointer->prior;//从当前结点回到其前驱结点
		if (strcmp(data,(char*)frontPointer->data) > 0)
			continue;
		for (; strcmp(data,(char*)frontPointer->data) < 0; frontPointer = frontPointer->prior)//动脑思考
		{
			frontPointer->next->data = frontPointer->data;
		}
		frontPointer->next->data = data;
	}
	return YES;
}

void conclude(int state)//由状态值报出对应的异常信息
{
	if (state ==ListIsEmpty)
	{
		printf("The CircularDoubleLinkedList Is Empty !\n");
	}else if(state==InvalidPosition)
	{ 
		printf("INVALID POSITION !\n");
	}else if (state == NullPointer)
	{
		printf("Null Pointer !\n\nThe CircularDoubleLinkedList may not be constructed !\n ");
	}
	else if (state == InvalidData)
	{
		printf("Invalid Data !\n");
	}
}

三、运动效果GIF

1.操作菜单

在这里插入图片描述

2.在双向循环链表未创建的情况下进行操作

双向循环链表未创建,只有创建双向循环链表和退出功能能够正常使用,其他操作皆给出提示信息” Null Pointer !The CircularDoubleLinkedList may not be constructed !
在这里插入图片描述

2.在双向循环链表为空的情况下进行操作

双向循环链表为空,即双向循环链表只有一个起源结点,只有创建双向循环链表、销毁双向循环链表、追加结点、退出能正常进行。其它操作均会给出提示信息” The CircularDoubleLinkedList Is Empty !
在这里插入图片描述

3.预期的双向循环链表操作

(1)创建链表

在这里插入图片描述

(2)销毁双向循环链表

在这里插入图片描述

(3)为双向循环链表排序

在这里插入图片描述

(4)逆转双向循环链表

在这里插入图片描述

(5)反向遍历双向循环链表

在这里插入图片描述

(6)追加结点

在这里插入图片描述

(7)插入结点

输入无效下标POSITION,POSITION<=0或者POSITION>尾结点下标,均为无效下标,给出“INVALID POSITION”提示信息
在这里插入图片描述

输入有效下标POSITION,1<=POSITION<=尾结点下标为有效下标,
尾结点下标是多少?你猜!
在这里插入图片描述

(8)删除结点

输入无效下标,POSITION<=0或者POSITION>尾结点下标,均为无效下标,给出“INVALID POSITION”提示信息
在这里插入图片描述

输入有效下标POSITION,1<=POSITION<=尾结点下标为有效下标,
尾结点下标是多少?你猜!
在这里插入图片描述

(9)修改结点数据

输入无效下标修改数据
在这里插入图片描述

输入有效下标修改数据
在这里插入图片描述

(10)按下标获取对应结点数据

输入无效下标获取对应结点数据在这里插入图片描述
输入有效下标获取对应结点数据
在这里插入图片描述

(11)按结点数据获取对应下标

输入无效结点数据获取对应下标
在这里插入图片描述

输入有效结点数据获取对应下标
在这里插入图片描述

(12)退出

退出前,先判断双向循环链表是否已经销毁,若已经销毁,直接退出;若仍未销毁,销毁后退出
①双向循环链表已经销毁的情况下退出
在这里插入图片描述
②双向循环链表为空,也就是只剩下起源结点的情况下退出
在这里插入图片描述

②双向循环链表存在多个结点的情况下退出
在这里插入图片描述

四、所感所想

前期的链表所操作的数据均是整型数据,这次真的不想再用整型数据了,内心有排斥,所以采用了字符串作为链表结点的数据,感觉还不错。
双向循环链表的功能实现起来还是比较容易的,稍微动动脑筋,花点心思就可以独立完成它。

在实现双向循环链表的时候,脑子里先得有一幅双向循环链表的结构图,编写起来才会得心应手,不然准玩得心累!

在完成双向循环链表后,想修改前面所写博客的冲动越来越强烈,大概这就是数据结构无形的力量吧!规整!
是的,我一定得规整下,太难受了!


本文链接: http://www.dtmao.cc/news_show_650257.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?