[데이터 구조] 더 블 링크 의 구축, 정렬, 삽입, 삭제

// Bi_linklist.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include 
#include 
#include 
#include 
using namespace std;


typedef struct student
{
	int data;
	struct student *pre;
	struct student *next;
}node;


//  
node *create()
{
	node *head, *p, *s;
	int x, cycle = 1;
	head = (node*)malloc(sizeof(node));
	p = head;
	while (cycle)
	{
		cout << "Please input an integer: " << endl;
		cin >> x;
		if (x != 0)
		{
			s = (node*)malloc(sizeof(node));
			s->data = x;
			p->next = s;
			s->pre = p;
			p = s;
		}
		else
			cycle = 0;
	}
	p->next = NULL;
	head = head->next;
	head->pre = NULL;


	return head;
}


//  
void print(node *head)
{
	node *p;
	p = head;
	while(p != NULL)
	{
		cout << p->data << endl;
		p = p->next;
	}
}


//  
int len(node *head)
{
	node *p;
	int length = 0;
	p = head;
	if (head == NULL)
		return length;
	while (p != NULL)
	{
		p = p->next;
		length++;
	}
	return length;
}


//  
node* sort_d_linklist(node *head)
{
	node *p;
	int temp;
	p = head;
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	for (int i = 0; i < len(head) - 1; i++)
	{
		p = head;
		for (int j = i + 1; j < len(head); j++)
		{
			if( p->data > p->next->data )
			{
				temp = p->data;
				p->data = p->next->data;
				p->next->data = temp;
			}
			p = p->next;
		}
	}
	return head;
}


//  
node *insert(node *head, int num)
{
	node *temp, *p1, *p2;
	temp = (node*)malloc(sizeof(node));
	temp->data = num;
	p1 = head;
	while ( (p1->data < temp->data ) && ( p1->next != NULL ) )
	{
		p1 = p1->next;
	}
	if (p1->data > temp->data)
	{
		//     
		if (head == p1)
		{
			p1->pre = temp;
			temp->next = p1;
			temp->pre = NULL;
			head = temp;
		}
		//    
		else
		{
			p2 = p1->pre;
			p1->pre = temp;
			temp->next = p1;
			temp->pre = p2;
			p2->next = temp;
		}
	}
	//   
	else
	{
		p1->next = temp;
		temp->pre = p1;
		temp->next = NULL;
	}
	return head;
}


//  
node *del(node *head, int num)
{
	node *p1;
	p1 = head;
	if (NULL == head)
		return head;
	while (p1->data != num && p1->next != NULL)
	{
		p1 = p1->next;
	}
	if (num == p1->data)
	{
		if (p1 == head)
		{
			head = head->next;
			head->pre = NULL;
			free(p1);
		}
		else if (NULL == p1->next)
		{
			p1->pre->next = NULL;
			free(p1);
		}
		else
		{
			p1->pre->next = p1->next;
			p1->next->pre = p1->pre;
			free(p1);
		}
	}
	return head;
}


int _tmain()
{
	int val = 10;
	node *d_linklist = create();
	cout << "The original double linklist is: 
" << endl;
	print(d_linklist);


	int l = len(d_linklist);
	cout << "The length is: "<< l << endl;


	d_linklist = sort_d_linklist(d_linklist);
	cout << "The sorted double linklist is: 
" << endl;
	print(d_linklist);


	d_linklist = insert(d_linklist, val);
	cout << "The inserted double linklist is: 
" << endl;
	print(d_linklist);


	d_linklist = del(d_linklist, val);
	cout << "The deleted double linklist is: 
" << endl;
	print(d_linklist);
	return 0;
}