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

#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;
}