데이터 구조 - 양 방향 링크 (C 언어)

4739 단어
c 언어 양 방향 링크 실현
링크 만 들 기
체인 시 계 를 소각 하 다.
머리 추가
추가
끼어들다
위치 찾기 로 삭제
찾기 값 으로 삭제
링크
#include 
#include 
#include 

#define TYPE int

typedef struct Node
{
	struct Node* prev;	//      
	TYPE data;			//   
	struct Node* next;	//      
}Node;

//     
Node* creat_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->prev = NULL;
	node->data = data;
	node->next = NULL;
	return node;
}

typedef struct List
{
	Node* head;
	Node* tail;
	size_t size;
}List;

//   
List* creat_list(void);
//   
void destory_list(List* list);
//   
void head_add_list(List* list,TYPE data);
//   
void tail_add_list(List* list,TYPE data);
//   
bool insert_list(List* list,int index,TYPE data);
//     
bool delete_index_list(List* list,int index);
//    
bool delete_value_list(List* list,TYPE data);
//   
void show_list(List* list);
bool del_head_list(List* list);
bool del_tail_list(List* list);

int main()
{
	List* list = creat_list();
	for(int i=0; i<10; i++)
	{
		tail_add_list(list,i);
	}
	insert_list(list,1,100);
	show_list(list);
	delete_value_list(list,0);
	delete_value_list(list,100);
	delete_value_list(list,9);
	show_list(list);
	destory_list(list);
}

//   
List* creat_list(void)
{
	List* list = malloc(sizeof(List));
	list->head = NULL;
	list->tail = NULL;
	list->size = 0;
	return list;
}

//   
void destory_list(List* list)
{
	while(list->size>0)
	{
		del_tail_list(list);
	}
	free(list);
}

//   
void head_add_list(List* list,TYPE data)
{
	Node* node = creat_node(data);

	if(0 == list->size)
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		node->next = list->head;
		list->head->prev = node;
		list->head = node;
	}

	list->size++;
}

//   
void tail_add_list(List* list,TYPE data)
{
	Node* node = creat_node(data);
	if(0 == list->size)
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		list->tail->next = node;
		node->prev = list->tail;
		list->tail = node;
	}
	list->size++;
}

//   
bool insert_list(List* list,int index,TYPE data)
{
	if(index < 0 || index >= list->size) return false;
	if(0 == index)
	{
		head_add_list(list,data);
		return true;
	}

	Node* next = NULL;
	if(index < list->size/2)
	{
		next = list->head;
		for(int i=0; inext;
		}
	}
	else
	{
		next = list->tail;
		for(int i=list->size-1; i>index; i--)
		{
			next = next->prev;
		}
	}
	Node* prev = next->prev;
	Node* node = creat_node(data);

	node->next = next;
	node->prev = prev;
	prev->next = node;
	next->prev = node;
	list->size++;

	return true;
}

//    
bool del_head_list(List* list)
{
	if(list->size <= 0) return false;
	Node* node = list->head;
	if(1 == list->size)
	{
		list->head = NULL;
		list->tail = NULL;
	}
	else
	{
		list->head = node->next;
		node->next->prev = NULL;
	}
	free(node);
	list->size--;
	return true;
}

//    
bool del_tail_list(List* list)
{
	if(list->size <= 0) return false;
	Node* node = list->tail;
	if(1 == list->size)
	{
		list->head = NULL;
		list->tail = NULL;
	}
	else
	{
		list->tail = node->prev;
		node->prev->next = NULL;
	}
	free(node);
	list->size--;
	return true;
}

//     
bool delete_index_list(List* list,int index)
{
	if(index < 0 || index >= list->size) return false;
	if(0 == index) return del_head_list(list);
	if(list->size-1 == index) return del_tail_list(list);

	Node* node = NULL;
	if(index < list->size/2)
	{
		node = list->head;
		for(int i=0; inext;
		}
	}
	else
	{
		node = list->tail;
		for(int i=list->size-1; i>index; i--)
		{
			node = node->prev;
		}
	}

	Node* prev = node->prev;
	Node* next = node->next;
	
	prev->next = next;
	next->prev = prev;
	free(node);
	list->size--;
	return true;
}

//    
bool delete_value_list(List* list,TYPE data)
{
	if(data == list->head->data) 
		return del_head_list(list);
	if(data == list->tail->data)
		return del_tail_list(list);
	
	Node* node = list->head;
	while(NULL != node)
	{
		if(data == node->data) break;
		node = node->next;
	}

	Node* prev = node->prev;
	Node* next = node->next;
	
	prev->next = next;
	next->prev = prev;
	free(node);
	list->size--;
	return true;	
}

//   
void show_list(List* list)
{
	for(Node* i=list->head; i!=NULL; i=i->next)
	{
		printf("%d ",i->data);
	}
	printf("
"); for(Node* i=list->tail; i!=NULL; i=i->prev) { printf("%d ",i->data); } printf("
"); }

좋은 웹페이지 즐겨찾기