Biegral Blog

#include<iostream>
using namespace std;

typedef struct node
{
	int data;
	struct node *next, *prior;
}Node, *DList;

//建立带头结点的双链表（最终成环状）
DList createDList()
{
	int num;
	Node *head, *p1, *p2;
	head = new Node;
	p1 = p2 = head->prior = head->next = head; //头结点
	
	cin >> num;
	while(-1 != num)
	{
		p1 = new Node;
		p1->data = num;
		
		p2->next = p1;
		p1->next = head;
		p1->prior = p2;
		head->prior = p1;
		p2 = p1;  //不可少
		cin >> num;
	}

	return head;
}

int getDListLength(DList p)
{
	int length = 0;
	Node *head = p;
	while(head != p->next)
	{
		length++;
		p = p->next;
	}

	return length;
}

Node *getLocation(DList p, int location)
{
	//为了程序的健壮性，最好对location的合理性进行判断
	//为了简便，此处不进行判断（但一定要对程序容错性有意识）

	Node *head = p;
	int i;
	for(i = 0; head != p->next && i < location; i++)
		p = p->next;

	return p;	
}

void insertNode(DList p, int location ,int element)
{
	Node *q = getLocation(p, location - 1);//最好用location - 1 
	Node *s = new Node;
	s->data = element;

	s->prior = q;
	s->next = q->next;
	q->next->prior = s;
	q->next = s;
}

void delNode(DList p, int location)
{
	Node *q = getLocation(p, location);
	q->prior->next = q->next;
	q->next->prior = q->prior;
	delete q;
}

void printDList(DList p)
{
	Node *head = p;
	while(head != p->next)
	{
		cout << p->next->data << " ";
		p = p->next;
	}
	cout << endl;
}

void release(DList p)
{
	Node *head = p;
	if(head == p->next)
		delete p;
	else
	{
		release(p->next);
		delete p;
	}
}

int main()
{
	DList head = createDList();
	printDList(head);

	int location = 3;
	int element = 100;
	insertNode(head, location, element);
	printDList(head);

	location = 2;
	delNode(head, location);
	printDList(head);
	cout << getDListLength(head) << endl;

	release(head);

	return 0;
}