체인 시계(2)----더블 체인 시계 기본 조작
typedef struct DListElement_t_{
void *data;
struct DListElement_t *prev;
struct DListElement_t *next;
} DListElement_t
typedef struct DList_t_{
int size;
int (*match)( const void *key1, const void *key2);
int (*destroy)(void *data);
DListElement_t *head;
DListElement_t *tail;
} DList_t;typedef struct DListElement_t_{
void *data;
struct DListElement_t *prev;
struct DListElement_t *next;
} DListElement_t
typedef struct DList_t_{
int size;
int (*match)( const void *key1, const void *key2);
int (*destroy)(void *data);
DListElement_t *head;
DListElement_t *tail;
} DList_t;
2. 초기화
int dlist_init( DList_t *dlist, int (*match)( const void *key1, const void *key2), int (*destroy)(void *data ))
{
dlist->size = 0;
dlist->match = match;
dlist->destory = destory;
dlist->head = NULL;
dlist->tail = NULL;
return 0;
}int dlist_init( DList_t *dlist, int (*match)( const void *key1, const void *key2), int (*destroy)(void *data ))
{
dlist->size = 0;
dlist->match = match;
dlist->destory = destory;
dlist->head = NULL;
dlist->tail = NULL;
return 0;
}
3. 삽입 - 지정된 노드 뒤에 삽입:
원소 요소를 정하고 그 다음에 데이터 데이터를 삽입하기;
예외 고려 사항:
(1) 체인 테이블 용량 초과:
if( dlist_is_full( dlist))
return OVERFLOW;
(2) 노드 공간 신청 실패
if( new_element = (DListElement_t *)malloc( DListElement))) == NULL )
return ALLOCA_ERROR;
고려해야 할 사항은 다음과 같습니다.
(1) 요소가 NULL이면 헤드 결점에 삽입합니다.
체인 테이블이 비어 있을 때:
if( dlist_is_empty( dlist) )
dlist->head = dlist->tail = new_element;
체인 테이블이 비어 있지 않음:
new_element->prev = dlist->head->prev;
new_element->next = dlist->head;
dlist->head->prev = new_element;
dlist->head = new_element;
(2) 요소가 NULL이 아닌 경우 요소 뒤에 삽입합니다.
먼저 삽입할 노드의 앞뒤 포인터를 각각 해당 위치를 가리킵니다.
new_element->prev = element;
new_element->next = element->next;
다음은 요소의 뒷바늘과 그 다음 노드의 앞바늘을 고려한 것이다
요소가 끝 노드인지 여부를 고려해야 합니다.
if( dlist_is_tail(element)
dlist->tail = new_element;
else
element->next->prev = new_element;
element->next = new_element;
int dlist_insert_next( DList_t *dlist, DListElement_t *element, const void *data){
DListElement_t *new_element = NULL;
if( (new_element = ( DListElement_t *)malloc( sizeof( DListElement_t ))) == NULL )
return ALLOCA_ERROR;
new_element->data = data;
new_element->prev = NULL;
new_element->next = NULL;
if( element == NULL ){
if ( dlist_is_empty(dlist)){
dlist->head = new_element;
dlist->tail = new_element;
} else {
new_element->next = dlist->head;
dlist->head->prev = new_element;
dlist->head = new_element;
}
}else{
new_element->prev = element;
new_element->next = element->next;
if( dlist_is_tail ( element ) )
dlist->tail = new_element;
else
element->next->prev = new_element;
element->next = new_element;
}
dlist->size++;
return 0;
}int dlist_insert_next( DList_t *dlist, DListElement_t *element, const void *data){
DListElement_t *new_element = NULL;
if( (new_element = ( DListElement_t *)malloc( sizeof( DListElement_t ))) == NULL )
return ALLOCA_ERROR;
new_element->data = data;
new_element->prev = NULL;
new_element->next = NULL;
if( element == NULL ){
if ( dlist_is_empty(dlist)){
dlist->head = new_element;
dlist->tail = new_element;
} else {
new_element->next = dlist->head;
dlist->head->prev = new_element;
dlist->head = new_element;
}
}else{
new_element->prev = element;
new_element->next = element->next;
if( dlist_is_tail ( element ) )
dlist->tail = new_element;
else
element->next->prev = new_element;
element->next = new_element;
}
dlist->size++;
return 0;
}
4. 삽입 -- - 지정된 노드 앞에 삽입
예외 고려 사항:
(1) 넘침 여부, 체인 테이블 용량 초과
if( dlist_is_full( dlist))
return OVERFLOW;
(2) 노드 공간 신청의 성공 여부
if(( new_element = (DListElement_t *)malloc( sizeof( DListElement_t ) )) == NULL )
return -1;
고려해야 할 사항은 다음과 같습니다.
(1) Element이 NULL이거나 Element이 헤드 노드인 경우 헤드 결점 전에 삽입하고 헤드 포인터를 유지해야 합니다.
만약 이 때 체인 시계가 비어 있다면, 머리 바늘과 꼬리 바늘을 동시에 유지해야 한다.
if( dlist_size (dlist) == 0 )
{
dlist->head = new_element;
dlist->tail = new_element;
}else{
new_element->next = dlist->head;
dlist->head->prev = new_element;
dlist->head = new_element;
}
(2) 요소가 NULL이 아닌 경우 요소 앞에 삽입
new_element->next = element;
new_element->prev = element->prev;
element->prev->next = new_element;
element->next = new_element;
int dlist_insert_prev( DList_t *dlist, DListElement_t *element, const void *data){
DListElement_t *new_element = NULL;
if( ( new_element = ( DListElement_t *)malloc( sizeof( DListElement_t ))) == NULL )
return ALLOCA_ERROR;
new_element->data = data;
new_element->prev = NULL;
new_element->next = NULL;
if( (element == NULL) || (dlist_is_head(element)){
if( dlist_is_empty( dlist)){
dlist->head = new_element;
dlist->tail = new_element;
} else {
new_element->next = dlist->head;
dlist->head->prev = new_element;
dlist->head = new_element;
}
} else {
new_element->next = element;
new_element->prev = element->prev;
element->prev->next = new_element;
element->next = new_element;
}
dlist->size++;
return 0;
}int dlist_insert_prev( DList_t *dlist, DListElement_t *element, const void *data){
DListElement_t *new_element = NULL;
if( ( new_element = ( DListElement_t *)malloc( sizeof( DListElement_t ))) == NULL )
return ALLOCA_ERROR;
new_element->data = data;
new_element->prev = NULL;
new_element->next = NULL;
if( (element == NULL) || (dlist_is_head(element)){
if( dlist_is_empty( dlist)){
dlist->head = new_element;
dlist->tail = new_element;
} else {
new_element->next = dlist->head;
dlist->head->prev = new_element;
dlist->head = new_element;
}
} else {
new_element->next = element;
new_element->prev = element->prev;
element->prev->next = new_element;
element->next = new_element;
}
dlist->size++;
return 0;
}
5, 삭제
지정된 요소 요소 요소 삭제
예외:
체인 테이블이 비어 있어 삭제할 수 없습니다
if(dlist_is_empty( dlist) )
return -1;
일반적인 상황:
(1) Element이 NULL이거나 Element이 헤드포인트인 경우 헤드포인트 삭제
체인 시계의 길이가 1일 경우 머리와 꼬리 지침을 유지해야 한다.그렇지 않으면 두 번째 노드의 앞 포인터를 유지해야 한다
if( (element == NULL ) || ( dlist_is_head(element)){
*data = dlist->head->data;
del_element = dlist->head;
if( dlist_size(dlist) == 1 ){
dlist->head = NULL;
dlist->tail = NULL;
} else {
dlist->head = dlist->head->next;
dlist->head->prev = NULL;
}
}
(2) 요소가 다른 노드인 경우
꼬리 노드 삭제를 고려할 때 꼬리 지침을 유지합니다
*data = element->data;
del_element = element;
if ( dlist_is_tail( element)){
dlist->tail = element->prev;
dlist->tail->next = NULL;
} else {
element->prev->next = element->next;
element->next->prev = element->prev;
}
int dlist_remove( DList_t *dlist, DListElement_t *element, void **data){
if( dlist_is_empty( dlist) )
return -1;
DListElement_t *del_element = NULL;
if( (element == NULL) || (dlist_is_head( element )){
*data = dlist->head->data;
del_element = dlist->head;
if( dlist_size(dlist) == 1 )
{
dlist->head = NULL;
dlist->tail = NULL;
} else {
dlist->head = dlist->head->next;
dlist->head->prev = NULL;
}
} else {
*data = element->data;
del_element = element;
if ( dlist_is_tail ( del_element) )
{
dlist->tail = element->prev;
dlist->tail->next = NULL;
} else {
element->prev->next = element->next;
element->next->prev = element->prev;
}
}
<p> free( del_element);</p><p> del_element = NULL;</p><p> dlist->size--;
</p><p> return 0;
</p><p>}</p><p>
</p>
dlist->size--;
return 0;
}
int dlist_remove( DList_t *dlist, DListElement_t *element, void **data){
if( dlist_is_empty( dlist) )
return -1;
DListElement_t *del_element = NULL;
if( (element == NULL) || (dlist_is_head( element )){
*data = dlist->head->data;
del_element = dlist->head;
if( dlist_size(dlist) == 1 )
{
dlist->head = NULL;
dlist->tail = NULL;
} else {
dlist->head = dlist->head->next;
dlist->head->prev = NULL;
}
} else {
*data = element->data;
del_element = element;
if ( dlist_is_tail ( del_element) )
{
dlist->tail = element->prev;
dlist->tail->next = NULL;
} else {
element->prev->next = element->next;
element->next->prev = element->prev;
}
}
dlist->size--;
return 0;
}
6. 목록 제거
int dlist_destroy( DList_t *dlist)
{
void *data;
while( dlist_size( dlist) > 0 ){
if ( dlist_remove( dlist, NULL, (void **)&data) == 0 && dlist->destory != NULL )
dlist->destory( data );
}
return 0;
}int dlist_destroy( DList_t *dlist)
{
void *data;
while( dlist_size( dlist) > 0 ){
if ( dlist_remove( dlist, NULL, (void **)&data) == 0 && dlist->destory != NULL )
dlist->destory( data );
}
return 0;
}
기타 관련 문제는 다음과 같습니다.
연쇄 면접 문제 모음집
1. 단일 체인 테이블 기본 조작
2. 쌍사슬표 기본 조작
3. 순환 단일 체인 테이블 기본 조작
4, 반전 단일 체인 테이블
5. 단일 체인 테이블 밑에서 K번째 노드 찾기
6, 역순 인쇄 체인 테이블
7. 체인 테이블 중간 노드 찾기
8. 체인 테이블 K번째 노드 삭제, 평균 시간 복잡도 O(1)
9. 체인 시계에 고리가 있는지 판단
10. 두 개의 단일 체인 테이블이 교차하는지 판단
11. 교차 체인표의 첫 번째 교차 노드를 구한다
12. 고리가 있는지 판단하고 6형 고리인지 0형 고리인지 판정한다.
13. 체인표에 고리가 있는지 판단하고 고리 입구 노드를 구한다.
14. 두 개의 질서정연한 단일 체인 테이블 병합
15. 주어진 체인 테이블 중간에 있는 어떤 노드가 체인 테이블을 누비지 않고 끼워진 노드를 주어진 노드에 삽입하기 전에
16. 체인 테이블 중복 요소 삭제
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
