欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

带头节点的双循环链表

程序员文章站 2022-03-01 19:50:15
...

如题;这是一套完整的可运行的代码;需要读者有一定的基础去阅读;

语言是用C语言实现;在C++环境中编写;在C++中可直接运行;在C语言中需要改部分头文件和输出语句;

头文件;这要是代码的声明部分;

# ifndef _LINKLIST_
# define _LINKLIST_

# include <iostream>
using namespace std;

typedef int DataType;

typedef struct Node
{
	DataType data;
	struct Node * next;
	struct Node * prior;
}LNode, *LinkList;

LinkList CreateLinkList(void);
void DestroyLinkList(LinkList * pH);
int LengthLinkList(LinkList H);
void TraversalLinkList(LinkList H);

LinkList SearchLinkListPos(LinkList H, int pos);
LinkList SearchLinkListValue(LinkList H, DataType x);
int InsertLinkListPos(LinkList H, int pos, DataType x);
int DeleteLinkListPos(LinkList H, int pos, int * val);

# endif

实现文件;主要是代码的实现;

# include "Head.h"

LinkList CreateLinkList(void)
{
	LinkList H = (LinkList)malloc(sizeof(LNode));

	if (NULL != H)
	{
		H->data = 0;
		H->prior = H;
		H->next = H;

		return H;
	}
	else
	{
		cout << "Memory allocate is error! " << endl;
		system("pause");
		exit(0);
	}
}

void DestroyLinkList(LinkList * pH)
{
	LinkList H = *pH;

	if (H == H->next)
	{
		free(H);
		H = NULL;

		*pH = NULL;
		return;
	}

	LinkList p = H->next;
	LinkList q = NULL;

	while (p != H)
	{
		q = p;
		p = p->next;
		free(q);
		q = NULL;
	}

	free(H);
	H = NULL;

	*pH = NULL;
	return;
}

int LengthLinkList(LinkList H)
{
	if (H == H->next)
	{
		return 0;
	}

	LinkList p = H->next;
	int cnt = 0;

	while (p != H)
	{
		p = p->next;
		cnt++;
	}

	return cnt;
}

void TraversalLinkList(LinkList H)
{
	if (H == H->next)
	{
		return;
	}

	LinkList p = H->next;

	while (p != H)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;

	return;
}

LinkList SearchLinkListPos(LinkList H, int pos)
{
	if (0 == pos)
	{
		return H;
	}

	LinkList p = H->next;

	int i = 0;
	while ((p != H) && (i < pos - 1))
	{
		p = p->next;
		i++;
	}

	if ((p == H) || (i > pos - 1))
	{
		cout << "LinkList is not exit or parameter error! " << endl;
		return NULL;
	}

	return p;
}

LinkList SearchLinkListValue(LinkList H, DataType x)
{
	if (H == H->next)
	{
		return NULL;
	}

	LinkList p = H->next;

	while ((p != H) && (p->data != x))
	{
		p = p->next;
	}

	if (p == H)
	{
		return NULL;
	}
	else
	{
		return p;
	}
}

int InsertLinkListPos(LinkList H, int pos, DataType x)
{
	LinkList p = SearchLinkListPos(H, pos - 1);
	if (NULL == p)
	{
		return -1;
	}

	LinkList q = (LinkList)malloc(sizeof(LNode));
	q->data = x;

	q->next = p->next;
	p->next->prior = q;
	p->next = q;
	q->prior = p;

	return 0;
}

int DeleteLinkListPos(LinkList H, int pos, int * val)
{
	if ((H == NULL) || (H == H->next))
	{
		return -1;
	}

	LinkList p = SearchLinkListPos(H, pos - 1);
	if ((NULL == p) || (p->next == H))
	{
		return -2;
	}

	*val = p->next->data;

	LinkList q = p->next;
	p->next = q->next;
	q->prior = p;
	free(q);
	q = NULL;

	return 0;
}

Main函数;

# include "Head.h"

int main(int argc, char ** argv)
{
	int val = 0;
	LinkList H = CreateLinkList();
	for (int i = 0; i < 10; i++)
	{
		InsertLinkListPos(H, i + 1, i + 1);
	}

	TraversalLinkList(H);
	LinkList p = H->prior;
	cout << p->data << endl;

	while (p != H)
	{
		cout << p->data << " ";
		p = p->prior;
	}
	cout << endl;

	//LinkList p = H;
	//while (p->next != H)
	//{
	//	p = p->next;
	//}

	//cout << p->data << endl;
	//p = p->next->next;
	//cout << p->data << endl;

	system("pause");
	return 0;
}