데이터 구조 입문: 앞장 서서 순환 하 는 양 방향 링크 의 실현

26001 단어
4. 567917. 앞장 서 는 양 방향 순환 링크: 링크 구조 에서 구조 가 가장 복잡 하지만 실제 적 으로 데 이 터 를 따로 저장 하 는 데 사용 된다
구조 가 복잡 하지만 코드 실현 은 간단 하 다
구체 적 인 코드 는 다음 과 같다.
typedef int LTDataType;
typedef struct ListNode{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

typedef struct List{
	ListNode* _head;
}List;

/             
void ListInit(List* plist){
	assert(plist);
	plist->_head = (ListNode*)malloc(sizeof(ListNode));
	plist->_head->_data = 0;
	plist->_head->_prev = plist->_head;
	plist->_head->_next = plist->_head;
}

/    (        )
void ListDestory(List* plist){
	assert(plist->_head);
	ListNode* cur = plist->_head;
	ListNode* eNode = plist->_head->_prev;
	ListNode* tNode = NULL;
	while (cur != eNode){
		tNode = cur->_next;
		free(cur);
		cur = tNode;
	}
	free(eNode);
	eNode = NULL;
	plist->_head = NULL;
}

//        ,        
ListNode* BuyNode(LTDataType x){
	ListNode* newNode = malloc(sizeof(ListNode));
	assert(newNode);
	newNode->_data = x;
	newNode->_next = NULL;
	newNode->_prev = NULL;
	return newNode;
}

/  
void ListPushBack(List* plist, LTDataType x){
	assert(plist->_head);
	ListNode* eNode = plist->_head->_prev;
	ListNode* newNode = BuyNode(x);
	assert(newNode);
	eNode->_next = newNode;
	newNode->_prev = eNode;
	newNode->_next = plist->_head;
	plist->_head->_prev = newNode;
}

/  
void ListPopBack(List* plist){
	assert(plist->_head);
	if (plist->_head->_next == plist->_head){
		return;
	}
	else{
		ListNode* eNode = plist->_head->_prev->_prev;
		free(plist->_head->_prev);
		eNode->_next = plist->_head;
		plist->_head->_prev = eNode;
	}
}

/  
void ListPushFront(List* plist, LTDataType x){
	assert(plist->_head);
	ListNode* newNode = BuyNode(x);
	assert(newNode);
	ListNode* tNode = plist->_head->_next;
	plist->_head->_next = newNode;
	newNode->_prev = plist->_head;
	newNode->_next = tNode;
	tNode->_prev = newNode;
}

/  
void ListPopFront(List* plist){
	assert(plist->_head);
	if (plist->_head->_next == plist->_head){
		return;
	}
	else{
		ListNode* tNode = plist->_head->_next->_next;
		free(plist->_head->_next);
		plist->_head->_next = tNode;
		tNode->_prev = plist->_head;
	}
}

ListNode* ListFind(List* plist, LTDataType x){
	assert(plist->_head);
	ListNode* tNode = plist->_head;
	if (tNode->_next == plist->_head){
		return -1;
	}
	while (tNode->_next != plist->_head){
		if (tNode->_data == x){
			return tNode;
		}
		else{
			tNode = tNode->_next;
		}
	}
	return -1;
}

/pos      ListFind      
/ pos       
void ListInsert(List* plist,ListNode* pos, LTDataType x){
	assert(plist->_head);
	if (pos == -1){
		return -1;
	}
	ListNode* bNode = pos->_prev;
	ListNode* newNode = BuyNode(x);
	assert(newNode);
	bNode->_next = newNode;
	newNode->_prev = bNode;
	newNode->_next = pos;
	pos->_prev = newNode;
}

/  pos     (pos     )
void ListErase(List* plist, ListNode* pos){
	assert(plist->_head);
	if (pos == -1){
		return -1;
	}
	ListNode* bNode = pos->_prev;
	ListNode* eNode = pos->_next;
	free(pos);
	bNode->_next = eNode;
	eNode->_prev = bNode;
}

void ListRemove(List* plist, LTDataType x){
		assert(plist->_head);
		ListNode* tNode = plist->_head->_next;
		while (tNode != plist->_head){
			if (tNode->_data == x){
				ListNode* bNode = tNode->_prev;
				ListNode* eNode = tNode->_next;
				free(tNode);
				bNode->_next = eNode;
				eNode->_prev = bNode;
				return;
			}
			else{
				tNode = tNode->_next;
			}
	}
}

void ListPrint(List* plist){
	assert(plist->_head);
	ListNode* tNode = plist->_head;
	while (tNode->_next != plist->_head){
		printf("%d<=>", tNode->_data);
		tNode = tNode->_next;
	}
	/  ,tNode      
	printf("%d<=>", tNode->_data);
	printf("
"
); }

좋은 웹페이지 즐겨찾기