資料結構之雙向循環連結清單

雙向循環連結清單

.h檔案

#ifndef  _LINKLIST_H_
#define  _LINKLIST_H_

typedef enum {TRUE,FALSE,ERROR} Bool;

typedef int Data;

typedef struct _node
{
	Data  data ;            //存儲資料
	struct _node   *pre;    // 指向上一個節點	
	struct _node   *next;   // 指向下一個節點
}Node;

typedef struct _list
{
	Node *head;  //指向頭結點；
}List;



//建立空連結清單
List* Creat ();

//摧毀連結清單
//[in]list  : 需要摧毀的連結清單
void destroy(List*list);


//插入資料：頭插
// [in]list  : 要插入的雙向連結清單
// [in]data  : 要插入的資料
Bool Insert_Head(List*list,Data data);

//插入資料：尾插
// [in]list  : 要插入的雙向連結清單
// [in]data  : 要插入的資料
Bool Insert_Tail(List*list,Data data);

//插入資料：	按位置插入
// [in]list  : 要插入的雙向連結清單
// [in]pos  : 要插入的位置
// [in]data  : 要插入的資料
Bool Insert_Pos(List*list,int pos,Data data);


//删除資料：	按位置删除
// [in]list  : 要插入的雙向連結清單
// [in]pos  : 要插入的位置
Bool Delete_Pos(List*list,int pos);


//删除資料：	按資料删除
// [in]list  : 要插入的雙向連結清單
// [in]data  : 要插入的資料
Bool Delete_Data(List*list,Data data);


//雙向連結清單逆序
Bool Reverse(List *list);


//列印
void Display(List*list);

#endif  // _LINKLIST_H_
           

.c檔案

#include <stdlib.h>
#include <stdio.h>
#include "linklist.h"

//建立空雙向循環連結清單
List* Creat ()
{
	List *list = (List*)malloc(sizeof(List)/sizeof(char));
	if(NULL ==list)
	{
		return NULL ;
	}

	list->head = (Node*)malloc(sizeof(Node)/sizeof(char));
	if(NULL == list->head )
	{
		free(list);
		return NULL;
	}

	list->head->pre  = list->head;
	list->head->next = list->head;
	
	return list;
}

//摧毀連結清單
void destroy(List*list)
{
	if(list == NULL)
		return;

	Node *tmp = list->head->next; //指向第一個節點

	while(tmp != list->head)
	{
		Node *p   = tmp;
		tmp       = tmp->next;
		free(p);
	}

	free(list->head);
	free(list);

}

Bool Insert_Head(List*list,Data data)
{
	if(NULL == list)
		return ERROR;

	Node * new_node= (Node*)malloc(sizeof(Node)/sizeof(char));
	if(NULL == new_node)
	{
		return FALSE;
	}
	new_node ->data  = data;

	new_node ->next  = list->head->next;
	list->head->next = new_node;

	new_node->pre       = list->head;
	new_node->next->pre = new_node;

	return TRUE;
}

Bool Insert_Tail(List*list,Data data)
{
	if(NULL == list)
		return ERROR;

	Node * new_node= (Node*)malloc(sizeof(Node)/sizeof(char));
	if(NULL == new_node)
	{
		return FALSE;
	}

	new_node ->data = data;
	new_node ->next = list->head;

	//找到最後指向空的節點
	Node *tmp = list->head;  //指向頭結點
	while(tmp->next != list->head)
	{
		tmp = tmp->next;
	}

	tmp->next       = new_node;
	new_node->next  = list->head;
	new_node->pre   = tmp;
	list->head->pre = new_node;

	return TRUE;
}

Bool Insert_Pos(List*list,int pos,Data data)
{

	if(NULL == list || pos <1)
		return ERROR;

	Node *node = (Node*)malloc(sizeof(Node)/sizeof(char));
	if(NULL == node)
	{
		return FALSE;
	}

	Node *tmp =list->head;  //指向頭結點

	//找到指點位置的插入的前一個節點
	int i;
	for(i=0;i<pos-1;i++)
	{
		tmp = tmp->next;
		if(list->head == tmp)
		{
			printf("%d的位置已越界\n",pos);
			return ERROR;
		}
	}

	node->data = data;

	node->next       = tmp->next;
	tmp->next        = node;
	node->pre        = tmp;
	node ->next->pre = node;
	
	return TRUE;
}

Bool Delete_Pos(List*list,int pos)
{
	if(NULL == list || pos<1)
		return ERROR;


	Node *tmp = list->head;//指向頭結點


	int i;
	for(i=0;i<pos-1;i++)
	{
	
		tmp =tmp->next;
		if(list->head == tmp->next   )
		{
			printf("%d的位置已經越界\n",pos);
			return ERROR;
		}
	
		
	}

	Node *pos_node = tmp->next;
	tmp->next      = pos_node->next;
	pos_node->next->pre  = tmp; 
	
	free(pos_node);

	return TRUE;
}

Bool Delete_Data(List*list,Data data)
{

	if(NULL == list )
		return ERROR;

	Node *tmp =list->head;

	while (tmp->next != list->head)
	{
		if (tmp->next->data == data)
		{
			Node *cur = tmp->next;
			tmp->next = cur->next;
			cur->next->pre  = tmp;

			free(cur);

			return TRUE;
		}
		tmp = tmp->next;
	}
	return FALSE;
}

Bool Reverse(List *list)
{

	// NULL == list || NULL == list->head || list->head == list->head->next  空連結清單
	//  list->head == list->head->next->next  隻有一個節點
	if(NULL == list || NULL == list->head || list->head == list->head->next|| list->head == list->head->next->next)
		return ERROR;

	Node *cur = list->head->next;  //第一個節點
	
	while(cur != list->head )
	{
		//交換 pre 和 next
		Node *tmp = cur->next;  
		cur->next = cur->pre;	
		cur->pre  = tmp;         	
		
		//下一個節點
		cur = tmp;
	}
	
		//頭結點逆序
		Node *tmp = cur->next;  
		cur->next = cur->pre;	
		cur->pre  = tmp;	
	
	return TRUE;
}

void Display(List*list)
{
	//
	if(NULL == list)
		return ;

	Node *tmp = list->head->next;  //指向第一個節點
	while(tmp != list->head )
	{
		printf("%-4d",tmp->data);
		tmp = tmp->next;
	}
	printf("\n");
}