데이터 구조 입문: 머리 없 는 단 방향 순환 링크 의 실현

25792 단어 데이터 구조
4. 567917. 링크 는 물리 적 저장 구조 에서 비 연속 적 이 고 비 순서 적 인 저장 구조 로 데이터 요소 의 논리 적 순 서 는 링크 에서 지침 의 연결 순 서 를 통 해 이 루어 진다
4. 567917. 8 에서 링크 에서 자주 사용 하 는 것 은 두 가지 가 있다. 머리 가 없 는 단 방향 불 순환 링크 와 선두 순환 양 방향 링크 이다
4. 567917. 먼저, 머리 가 없 는 단일 항목 의 순환 하지 않 는 링크 의 구 조 는 간단 하지만 보통 데 이 터 를 저장 하지 않 는 다. 실제 적 으로 다른 데이터 구조의 서브 구조 로 서 예 를 들 어 하 쉬 통, 그림 의 인접 표 등 이다
4. 567917. 다음은 삭제, 수정 등 작업 의 코드 실현 이다. 4. 567918.
typedef int SLDataType;
/  (             ,        )
typedef struct SListNode{
	SLDataType _data;
	struct  SListNode* _next;
}SListNode;
/   (     :     ,       )
typedef struct SList{
	SListNode* _head;
}SList;

void SListInit(SList* plist){
	assert(plist);
	plist->_head = NULL;
}

/               (void SListDestory(SList* plist){
	assert(plist);
	while (plist->_head){
		SListNode* tNode = plist->_head->_next;
		free(plist->_head);
		plist->_head = tNode;
	}
}

SListNode* BuySListNode(SLDataType x){
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	assert(newNode);
	newNode->_data = x;
	newNode->_next = NULL;
	return newNode;
}

/    (         ,            ,
/void SListPushFront(SList* plist, SLDataType x){
	assert(plist);
	SListNode* newNode = BuySListNode(x);
	assert(newNode);
	if (plist->_head == NULL){
		plist->_head = newNode;
		return;
	}
	else{
		newNode->_next = plist->_head;
		plist->_head = newNode;
	}
}

void SListPopFront(SList* plist){
	assert(plist);
	SListNode* tNode = plist->_head->_next;
	free(plist->_head);
	plist->_head = tNode;
}


//  :   
//     (              )
void SListPushBack(SList* plist,SLDataType x){
	assert(plist);
	SListNode* newNode = BuySListNode(x);
	assert(newNode);
	if (plist->_head == NULL){
		plist->_head = newNode;
	}
	else{
		SListNode* tail = plist->_head;
		while (tail->_next){
			tail = tail->_next;
		}
		tail->_next = newNode;
	}
}

/  :     ;
/void SListPopBack(SList* plist){
	assert(plist->_head);
	SListNode* tail = plist->_head;
	if (tail->_next == NULL){
		free(tail);
		plist->_head = NULL;
	}
	while (tail->_next->_next!=NULL){
		tail = tail->_next;
	}
	free(tail->_next);
	tail->_next = NULL;
}

SListNode* SListFind(SList* plist, SLDataType x){
	    assert(plist);
		SListNode* tNode = plist->_head;
		while (tNode != NULL){
			if (tNode->_data != x){
				tNode = tNode->_next;
			}
			else{
				return tNode;
			}
		}
		return -1;	
}

/ pos       (pos     ;pos   ;pos   )
void SListInsertAfter(SList*plist,SListNode* pos, SLDataType x){
	assert(plist);
	SListNode* newNode = BuySListNode(x);
	assert(newNode);
	if (pos == -1){
		return - 1;
	}
	else if (pos == plist->_head){
		SListPushFront(plist,x);
	}
	else{
		SListNode* tNode = plist->_head->_next;
		while (tNode != pos){
			tNode = tNode->_next;
		}
		tNode = pos->_next;
		pos->_next = newNode;
		newNode->_next = tNode;
	}
}

/ pos       
void SListEraseAfter(SList*plist, SListNode* pos){
	assert(plist);
	if (pos == -1){
		return -1;
	}
	else if (pos == plist->_head){
		SListPopFront(plist);
	}
	else{
		SListNode* tNode = plist->_head->_next;
		while (tNode != pos){
			tNode = tNode->_next;
		}
		SListNode* cur = tNode->_next;
		SListNode* tail = tNode->_next->_next;
		free(cur);
		tNode->_next = tail;
	}
}

/        X   
void SListRemove(SList* plist, SLDataType x){
	assert(plist);
	SListNode* bNode = plist->_head;
	if (bNode->_data == x){
		SListNode* cur = bNode;
		free(bNode);
		cur->_next = plist->_head;
		return;
	}
	else{
		SListNode* tNode = plist->_head->_next;
		while (tNode->_data != x){
			bNode = bNode->_next;
			tNode = tNode->_next;
		}
		SListNode* eNode = tNode->_next;
		free(tNode);
		bNode->_next = eNode;
	}
}

/     ,     plist->_head    ,         。
void SListPrint(SList* plist){
	assert(plist);
	SListNode* head = plist->_head;
	while (head->_next){
		printf("%d->", head->_data);
		head = head->_next;
	}
	printf("%d
"
, head->_data); }

좋은 웹페이지 즐겨찾기