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

最详细的不带头结点的双循环链表

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



#include<iostream>

/*
双向循环链表

一般来说循环双链表带头节点操作会方便一些的



不带头结点的循环双链表适合浏览图片







*/





using namespace std;


//设计节点
typedef struct doublelinknode
{
	int data;
	struct doublelinknode* prior;
	struct doublelinknode* next;
}Node;

//初始化链表
Node* Initdoublelinklist()
{
	Node* head = new Node;
	head = NULL;
	return head;
	
}

//新建一个节点
Node* Newnode(int data)
{
	Node* s = new Node;
	s->data = data;
	s->next = s;
	s->prior = s;
	//cout << __LINE__ << endl;
	return s;
}

//头插法插入一个节点
void AddHeadDList(Node** head, int data)
{
	Node* s = Newnode(data);
	if (head == NULL)
	{
		*head = s;
		return;
	}
	s->prior = *head;
	s->next = (*head)->next;
	(*head)->next->prior = s;
	(*head)->next = s;
}

//尾部插入一个节点
void AddTailDList(Node** head, int data)
{
	
	Node* s = Newnode(data);		//33
	if (*head == NULL)
	{
	//	cout << __LINE__ << endl;
		*head = s;
		return;
	}
	
//	cout << __LINE__ << endl;			//64
	s->next = *head;
	s->prior =(*head)->prior;
	(*head)->prior->next = s;
	(*head)->prior = s;
}


//创建链表


void CreateDList(Node** head, int* str,int n)
{
	for (int i = 0;i < n ;i++)
	{
		AddTailDList(head, str[i]);

	}
}
//求链表的长度
int LengthDLisk(Node* head)
{
	Node* p = head;
	int i = 0;
	do {
		p = p->next;
		i++;
	} while (p != head);
	return i;
}


//展示链表
void show(Node* head)
{
	Node* p = head;
	if (head ==NULL)
	{
		cout << "链表为空" << endl;
		return;
	}
	//cout << "----------------" << __LINE__ << endl;
	
	do
	{
		cout << p->data << " ";
		p = p->next;
	} while (p != head);
	
	cout << endl;
}

//指定位置插入节点
void InsertDLink(Node** head, int i, int e)
{
	if (i <= 0||i>LengthDLisk(*head)+1)
	{
		cout << "Insert postiton error!" << endl;
		return;
	}
	Node* p = *head;
	//找i位置
	for (int j = 1;j < i;j++)
	{
		p = p->next;
	}
	//在i前面插入
	Node* s = Newnode(e);
	s->prior = p->prior;
	s->next = p;
	p->prior->next = s;
	p->prior = s;
	if (i == 1)
	{
		*head = s;
	}
}




//指定位置删除节点
void DelDList(Node** head, int i, int* e)
{
	if (i <= 0 || i > LengthDLisk(*head))
	{
		cout << "delete postiton error" << endl;
		return;
	}
	Node* p = *head;
	for (int j = 1;j < i;j++)
	{
		p = p->next;
	}
	*e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
}



//删除整个链表
Node* DestroyDList(Node* head)
{
	Node* p, * q;
	p = head;
	while (p != head)
	{
		q = p->next;
		p->prior = p->next;
		p->next->prior = p->prior;
		
		free(p);
		p = q;
	}
	free(head);
	return NULL;

}

//得到指定i位置的元素
void GetElem(Node* head,int i, int *e)
{
	if (i <= 0 || i > LengthDLisk(head))
	{
		cout << " postiton error" << endl;
		return;
	}
	Node* p = head;
	for (int j = 1;j < i;j++)
	{
		p = p->next;
	}
	*e = p->data;
}


//按值查找,返回与元素e相等的位置
int LocationElem(Node* head,int e)
{
	Node* p = head;
	if (head == NULL)
		exit(1);
	int i = 1;
	while (p->data != e )
	{
		
		p = p->next;
		i++;
		if (p == head)
			break;
	}
	return i;
}
int main()
{
	Node* head = Initdoublelinklist();
	int str[] = { 8,4,5,2,6,4,7,1,8, };
	int n = 9;
	CreateDList(&head, str, n);

	show(head);
	int i = LengthDLisk(head);
	cout << i << endl;

	InsertDLink(&head, 10, 10);
	
	show(head);

	int e;
	DelDList(&head, 8, &e);
	GetElem(head, 6, &e);
	cout << "e: " << e << endl;
	int j;
	j = LocationElem(head, 6);
	cout << "j: " << j << endl;					//

	head = DestroyDList(head);
	show(head);

	return 0;
}