양 방향 링크 의 첨삭 과 수정 조 사 를 실현 하 다.

11104 단어 데이터 구조-링크
좋 은 하루 는 정오 에 일어나 기 시작 해서 늦잠 을 자 는 것 이 정말 편안 합 니 다. 그리고 우 리 는 코드 를 올 려 서 양 방향 링크 의 삭제 와 수정 을 실현 하려 고 합 니 다. 먼저 각 함수 의 기능 을 보 여 줍 니 다.
        
void DLinkListInit(DLinkNode** head); 
양 방향 링크 초기 화
DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value); 
끝 에 원 소 를 삽입 하 다.
void DLinListPopBack(DLinkNode* head); 
원소 하 나 를 삭제 하 다
void DLinkListPushFront(DLinkNode* head, DLinkType value); 
머리 에 원 소 를 삽입 하 다.
void DLinkListPopFront(DLinkNode* head); 
원소
DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find); 
지정 한 요소 값 을 찾 아 노드 아래 표 시 를 되 돌려 줍 니 다.
void DLinkListInsert(DLinkNode* pos, DLinkType value); 
지정 한 위치 에 요소 삽입 하기
void DLinkListInsertAfter(DLinkNode* pos, DLinkType value);
지정 한 위치 에 요 소 를 삽입 합 니 다.
업데이트:
        양 방향 링크 의 지정 한 위치 에서 노드 를 삭제 하고 링크 의 길이 와 비어 있 는 지 여 부 를 구 합 니 다.우선 목록 을 통 해 각 함수 기능 을 보 여 줍 니 다.
void DLinkListErase(DLinkNode* head,DLinkNode* pos);
지정 한 위치의 노드 삭제
void DLinkListRemove(DLinkNode* head,DLinkType value);
양 방향 링크 의 첫 번 째 값 이 value 인 노드 를 제거 합 니 다.
void DLinkListRemoveAll(DLinkNode* head,DLinkType value);
양 방향 링크 의 모든 값 이 value 인 노드 를 제거 합 니 다.
size_t DLinkListSize(DLinkNode* head);
양 방향 링크 의 길 이 를 구하 다.
int DLinkListEmpty(DLinkNode* head);
양 방향 링크 가 빈 링크 인지, 0 으로 돌아 가 는 지, 1 로 돌아 가 는 지 판단 합 니 다.
dlinklist.h 
#include
#include

typedef char DLinkType;
typedef struct DLinkNode{
	DLinkType data;
	struct DLinkNode* next;
	struct DLinkNode* prev;

}DLinkNode;

void DLinkListInit(DLinkNode** head);

DLinkNode* DLinkListPushBack(DLinkNode* head,DLinkType value);

void DLinkListPushFront(DLinkNode* head,DLinkType value);

void DLinkListPopBack(DLinkNode* head);

void DLinkListPopFront(DLinkNode* head);

DLinkNode* DLinkListFind(DLinkNode* head,DLinkType to_find);

void DLinkListInsert(DLinkNode* head,DLinkNode* pos,DLinkType value);

void DLinkListInsertAfter(DLinkNode* head,DLinkNode* pos,DLinkType value);

업데이트:
void DLinkListErase(DLinkNode* head,DLinkNode* pos);

void DLinkListRemove(DLinkNode* head,DLinkType value);

void DLinkListRemoveAll(DLinkNode* head,DLinkType value);

size_t DLinkListSize(DLinkNode* head);

int DLinkListEmpty(DLinkNode* head);

dlinklist.c 
#include
#include"dlinklist.h"
#include

DLinkNode* CreateDLinkNode(DLinkType value){
	DLinkNode* new_node = (DLinkNode*)malloc(sizeof(DLinkType));
	new_node->data = value;
	new_node->prev = new_node;
	new_node->next = new_node;
	return new_node;
}

void DLinkListInit(DLinkNode** head){
	if(head == NULL){
		return;//feifashuru
	}
	*head == CreateDLinkNode(0);
}

void DestoryNode(DLinkNode* to_delete){
	free(to_delete);
}

DLinkNode* DLinkListPushBack(DLinkNode* head,DLinkType value){
	if(head == NULL){
		return NULL;
	}
	DLinkNode* tail = head->prev;
	DLinkNode* new_node = CreateDLinkNode(value);
	head->prev = new_node;
	new_node->next = head;
	tail->next = new_node;
	new_node->prev = tail;
	return head;
}



void DLinkListPushFront(DLinkNode* head,DLinkType value){
	if(head == NULL){
		return;
	}
	DLinkNode* new_node = CreateDLinkNode(value);
	DLinkNode* cur = head->next;
	cur->prev = new_node;
	new_node->next = cur;
	head->next = new_node;
	new_node->prev = head;
	return;
}

void DLinkListPopBack(DLinkNode* head){
	if(head == NULL){
		return;
	}
	if(head->next == head && head->prev == head){
		return;
	}
	DLinkNode* to_delete = head->prev;
	DLinkNode* pre = to_delete->prev;
	pre->next = head;
	head->prev = pre;
	DestoryNode(to_delete);
	return;
}

void DLinkListPopFront(DLinkNode* head){
	if(head == NULL){
		return;
	}
	if(head->next == head && head->prev == head){
		return;
	}
	DLinkNode* to_delete = head->next;
	DLinkNode* to_delete_next = to_delete->next;
	head->next = to_delete_next;
	to_delete_next->prev = head;
	DestoryNode(to_delete);
	return;
}

DLinkNode* DLinkListFind(DLinkNode* head,DLinkType to_find){
	 if(head == NULL){
		 return NULL;
	 }
	 DLinkNode* cur = head->next;
	 while(cur != head){
		if(cur->data == to_find){
			break;
		}
		cur = cur->next;
	 }
	 if(cur == head){
		 return NULL;
	 }
	 return cur;
}

void DLinkListInsert(DLinkNode* head,DLinkNode* pos,DLinkType value){//pos    
	if(head == NULL || pos == NULL){
		return;
	}
	DLinkNode* new_node = CreateDLinkNode(value);
	DLinkNode* pre = pos->prev;
	new_node->prev = pre;
	pre->next = new_node;

	new_node->next = pos;
	pos->prev = new_node;
	return;
}

void DLinkListInsertAfter(DLinkNode* head,DLinkNode* pos,DLinkType value){
	if(head == NULL || pos == NULL){
		return;
	}
	DLinkNode* cur = pos->next;
	DLinkNode* new_node = CreateDLinkNode(value);
	new_node->next = cur;
	new_node->prev = pos;
	pos->next = new_node;
	cur->prev = new_node;
	return;
}

업데이트:
void DLinkListErase(DLinkNode* head,DLinkNode* pos){
	if(head == NULL){
		return;
	}
	DLinkNode* cur = pos->next;
	DLinkNode* pre = pos->prev;
	pre->next = cur;
	cur->prev = pre;
	DestoryNode(pos);
	return;
}

void DLinkListRemove(DLinkNode* head,DLinkType value){
	if(head == NULL){
		return;
	}
	DLinkNode* to_remove = DLinkListFind(head,value);
	DLinkNode* to_remove_prev = to_remove->prev;
	DLinkNode* to_remove_next = to_remove->next;
	to_remove_prev->next = to_remove_next;
	to_remove_next->prev = to_remove_prev;
	DestoryNode(to_remove);
	return;
}

void DLinkListRemoveAll(DLinkNode* head,DLinkType value){
	if(head == NULL)	{
		return;
	}
	DLinkNode* to_remove = head->next;
	while(to_remove != head){
		if(to_remove->data == value){
			DLinkListRemove(head,value);
		}
		to_remove = to_remove->next;
	}
	return;	
}

size_t DLinkListSize(DLinkNode* head){
	if(head == NULL){
		return;
	}
	DLinkNode* start = head->next;
	size_t len = 1;
	while(start != head){
		start = start->next;
		++len;
	}
	return len;
}

int DLinkListEmpty(DLinkNode* head){
	if(head == NULL){
		return;
	}
	if(head->next == head && head->prev){
		return 0;
	}
	return 1;
} 




///
//    
///
#if 1
#include
#define TEST_HEADER printf("
=========%s=========
",__FUNCTION__);
void DLinkListPrintChar(DLinkNode* head,const char* msg){
	printf("[%s]
",msg);
	DLinkNode* cur = head->next;
	for(;cur != head;cur = cur->next){
		printf("[%c]%p",cur->data,cur);
	}
	for(;cur = head->prev;cur != head){
		printf("[]%c]%p",cur->data,cur);
	}
	printf("
");
}

테스트 함수 업데이트:
void TestEmpty(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	int ret = DLinkListEmpty(head);
	printf("   ,excepted 1,actual %d
",ret);
	DLinkListPopBack(head);
	ret = DLinkListEmpty(head);
	printf("   ,excepted 0 ,actual %d
",ret);
}

void TestSize(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	int len = DLinkListSize(head);
	printf("      %d
",len);
	DLinkListPrintChar(head,"       ");
}


void TestRemoveAll(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkListPushBack(head,'b');
	DLinkListRemoveAll(head,'b');
	DLinkListPrintChar(head,"         b");
}


void TestRemove(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkListPushBack(head,'b');
	DLinkListRemove(head,'b');
	DLinkListPrintChar(head,"        b")；
}

void TestErase(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	pos = DLinkListFind(head,'b');
	DLinkListErase(head,pos);
	DLinkListPrintChar(head,"  pos     ")；
}



void TestInsertAfter(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkNode* pos = DLinkListFind(head,'b');
	DLinkListInsertAfter(head,pos,'y');
	DLinkListPrintChar(head,"  b        y");//    ：a b y c
}

void TestInsert(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkNode* pos = DLinkListFind(head,'b');
	DLinkListInsert(head,pos,'x');
	DLinkListPrintChar(head,"  b        x");//    ：a x b c
}

void TestFind(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkListFind(head,'c');
	DLinkListPrintChar(head,"     c");}

void TestPopFront(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkListPopFront(head);
	DLinkListPrintChar(head,"      ");
}

void TestPopBack(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPopBack(head);
	DLinkListPrintChar(head,"      ");
}

void TestInit(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	printf("head excepted not NULL,actual %p
",head);
	printf("data excepted 0,actual %d
",head->data);
}

void TestPushBack(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushBack(head,'a');
	DLinkListPushBack(head,'b');
	DLinkListPushBack(head,'c');
	DLinkListPushBack(head,'d');
	DLinkListPrintChar(head,"      ");
}


void TestPushFront(){
	TEST_HEADER;
	DLinkNode* head;
	DLinkListInit(&head);
	DLinkListPushFront(head,'a');
	DLinkListPrintChar(head,"      ");
}

int main(){
	TestInit();
	TestPushBack();
	TestPushFront();
	TestPopBack();
	TestPopFront();
	TestFind();
	TestInsert();
	TestInsertAfter();
	TestErase();
	TestRemove();
	TestRemoveAll();
	TestSize();
	TestEmpty();
	return 0;
}

#endif
        이상 은 양 방향 링크 의 추가 삭제 와 검사 기능 을 실현 하 는 함수 코드 입 니 다. 만약 에 저 에 게 칭찬 을 눌 러 주세요. 코드 에 오류 가 있 거나 더 좋 은 생각 이 있 으 면 메 시 지 를 남 겨 주세요. 시청 해 주 셔 서 감사합니다.
LeetCode105—Construct Binary Tree from Preorder and Inorder Traversal
배열 (기본 편)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage