단일 체인 표 2 [앞장 서지 않 는 노드 링크]
단 방향 체인 시 계 는 체인 시계의 일종 이다.단 방향 링크 는 일련의 메모리 가 연속 되 지 않 는 노드 로 구성 되 고 모든 노드 는 가리 키 는 값 의 도 메 인 과 다음 노드 를 가리 키 는 next 지침 을 포함한다.마지막 노드 의 next 도 메 인 은 NULL 값 으로 링크 가 끝 난 것 을 의미 합 니 다.
링크 설명도 아래 와 같다.
구조 체
1. 구조 체 정의:
struct LinkNode
{
void *x;
struct LinkNode *next;
};2. 구조 체 크기:
1) 구조 체 크기 를 취 하 는 방법: sizeof (struct LinkNode);64 비트 시스템 에서 구조 체 크기 를 꺼 내기: sizeof (struct LinkNode) = 16;
2) 왜 16 바이트 입 니까?포인터 가 주 소 를 저장 하기 때문에 같은 시스템 플랫폼 에서 포인터 변 수 는 sizeof 크기 가 일치 합 니 다.즉, 포인터 변수의 크기 는 포인터 유형 에 달 려 있 지 않 고 시스템 플랫폼 에 달 려 있다.32 비트 = 4 바이트, 64 비트 = 8 바이트.그러므로 64 비트 시스템 에서 sizeof (void *) = sizeof (struct LinkNode *) = = 8 이 있 습 니 다.32 비트 시스템 에서 sizeof (void *) = sizeof (struct LinkNode *) = 4.
3) 노드 ABCD 가 메모리 연속 이 고 A 가 메모리 의 시작 점, 즉 A 의 주소 가 0x 00 이 라 고 가정 하면 이때 B, C, D 의 주 소 는 다음 과 같다. 0x 10, 0x 20, 0x 30 이다.또한 A 의 next 지침 은 노드 B (A - > next = & B) 를 가리 키 며 노드 D 의 next 가 끝 문자 NULL 이 저 장 될 때 까지 순서대로 유추 합 니 다.
2. 링크 생 성
1. 링크 생 성 1 (1 급 포인터 사용)
프로그램 설명:
1) 프로그램 호출 방식 szyulink_create 1 ("AA", "BB", NULL), NULL 은 for 순환 을 정확하게 종료 하 는 데 사 용 됩 니 다.
2) 새로 추 가 된 노드 node 를 만 듭 니 다.
3) 링크 가 비어 있 으 면 새로 추 가 된 노드 (node) 를 head 에 할당 하고 last 가 최신 head 를 가리 키 도록 합 니 다.링크 가 비어 있 지 않 으 면 꼬리 노드 의 next 를 최신 노드 로 가리 키 고 꼬리 노드 를 다시 할당 하면 됩 니 다.
struct LinkNode
*szyu_link_create1(void *x, ...)
{
struct LinkNode *head = NULL;
struct LinkNode *last = head;
va_list args;
va_start(args, x);
for ( ; x ; x = va_arg(args, void *) )
{
struct LinkNode *node = NULL;
node = (struct LinkNode *)malloc(sizeof(struct LinkNode));
if ( node == NULL )
{
return head;
}
node->x = x;
node->next = NULL;
if ( head == NULL )
{
head = node;
last = head;
}
else
{
last->next = node;
last = node;
}
}
va_end(args);
return head;
}2, 링크 생 성 2 (2 급 포인터 사용)
프로그램 설명:
1) 2 급 포인터 node 는 다음 과 같은 성립 등식 이 존재 합 니 다. * node = = head, * * node = * head;
2) for 처음에는 * node (* node) = head) 머리 노드 를 만 드 는 동시에 공간 을 만 듭 니 다.
3) (* node) 노드 의 x 할당 값 이 고 포인터 node 가 새로운 노드 의 next, 즉 할당 후 * node 는 전 node 의 next 도 메 인 값 입 니 다.
4) 두 번 째 for 를 시작 으로 * node 에 값 을 부여 하 는 것 은 (* node) - > next 에 값 을 부여 하 는 것 입 니 다.
5) NULL 이 들 어 올 때 까지 3, 4 절 차 를 반복 한다.
6) 마지막 노드 에서 node 를 next 로 가리 킨 후 NULL 값 을 부여 하지 않 았 습 니 다.그러므로 for 순환 이 끝 날 때 * node 에 값 을 부여 합 니 다. NULL.대표 링크 끝.
struct LinkNode
*szyu_link_create2(void *x, ...)
{
struct LinkNode *head = NULL;
struct LinkNode **node = &head;
va_list args;
va_start(args, x);
for ( ; x; x = va_arg(args, void *) )
{
(*node) = (struct LinkNode *)malloc(sizeof(struct LinkNode));
if ( (*node) == NULL )
{
return head;
}
(*node)->x = x;
node = &(*node)->next;
}
*node = NULL;
va_end(args);
return head;
}3. 1 급 포인터 와 2 급 포인터 비교
1 단 지침
1) 장점: 절차 가 통속 적 이 고 알 기 쉽다.
2) 단점: 헤드 노드 를 삽입 하 는 것 과 다른 위치 에 삽입 하 는 방식 이 다 르 고 코드 스타일 이 일치 하지 않 습 니 다.
2 단 지침
1) 장점: 어떤 위 치 를 삽입 하 든 코드 스타일 이 고도 로 통일 된다.코드 간소화.
2) 단점: 기교 가 높다.
4. 디자인 사고
2 급 포인터 의 사용 장면 은 바로 '1 급 포인터 가 가리 키 는 메모리 주 소 를 간접 적 으로 바 꾸 는 것' 이다.변 경 된 1 급 지침 은 next 지침 을 가리킨다.헤드 노드 를 제외 한 모든 노드 의 추가 주 소 는 이전 노드 의 next 에 존재 합 니 다. 고유 디자인 node 는 next 를 가리 키 고 * node 로 값 을 부여 할 때 next 로 값 을 부여 합 니 다.
3. 링크 삽입
1. 링크 삽입 1 (1 급 포인터 사용)
프로그램 설명:
1) key 의 판단 은 입력 위치 가 1 보다 작 으 면 안 되 고 링크 맨 뒤에 새 노드 를 삽입 할 수 있 습 니 다.
2) 새로 추 가 된 노드 를 초기 화 합 니 다.
3）int cnt = 2;key = 1 시 첫 번 째 노드 를 다시 삽입 합 니 다.key = 2 시 에 삽 입 된 이전 노드 는 첫 번 째 노드 입 니 다.따라서 key < = 2 시 링크 이동 이 필요 없 기 때문에 cnct = 2 가 실 행 됩 니 다.
4) 선두 노드 가 없 기 때문에 삽입 할 때 머리 노드 의 위치 와 뒤의 위 치 를 구분 하고 고려 해 야 한다.
struct LinkNode
*szyu_link_insert1(struct LinkNode *head, void *x, int key)
{
if ( head == NULL )
{
return head;
}
int len = szyu_link_length1(head);
if ( key len )
{
return head;
}
struct LinkNode *node = NULL;
node = (struct LinkNode *)malloc(sizeof(struct LinkNode));
if ( node == NULL )
{
return head;
}
node->x = x;
node->next = NULL;
struct LinkNode *list = head;
int cnt = 2;
for ( ; cnt next;
}
if ( key == 1 )
{
node->next = head;
head = node;
}
else
{
node->next = list->next;
list->next = node;
}
return head;
}2. 링크 삽입 2 (2 급 포인터 사용)
프로그램 설명:
1) key - 1 은 링크 뒤에 노드 를 삽입 하 는 것 이 정상 입 니 다.
2) 2 급 지침 을 사용 하기 때문에 cnct 를 1 로 초기 화하 면 됩 니 다. 헤드 노드 삽입 상황 을 따로 고려 할 필요 가 없습니다.
struct LinkNode
*szyu_link_insert2(struct LinkNode *head, void *x, int key)
{
if ( head == NULL )
{
return head;
}
int len = szyu_link_length1(head);
if ( key len )
{
return head;
}
struct LinkNode **list = &head;
int cnt = 1;
while ( cnt next;
cnt += 1;
}
struct LinkNode *remain = *list;
*list = (struct LinkNode *)malloc(sizeof(struct LinkNode));
if ( (*list) == NULL )
{
return head;
}
(*list)->x = x;
(*list)->next = remain;
return head;
}3. 1 급 포인터 와 2 급 포인터 의 장단 점 을 사용 하여 링크 를 만 듭 니 다.
4. 2 급 포인터 로 디자인 방향
1) 우선 2 급 포인터 list 를 1 급 포인터 head 로 가리킨다.
2) 링크 를 순환 적 으로 사용 하여 삽입 위치 앞 노드 에 머 물 러 있 습 니 다.이때 머리 노드 위치 가 아니라면 list 는 위치 앞의 노드 를 삽입 하 는 next 를 가리 키 며 삽입 할 때 * list 에 새 노드 주 소 를 부여 하면 됩 니 다.머리 노드 라면 * list 는 머리 노드 를 가리킨다.
3) 머리 노드 든 아니 든 남 은 링크 를 remain 에 할당 합 니 다 (머리 노드 로 삽입 하면 remain 이 유지 하 는 모든 링크 입 니 다. 마지막 에 삽입 하면 remain 은 NULL 입 니 다).
4) * list 에 새 노드 주 소 를 부여 합 니 다.그리고 remain 을 * list 노드 뒤에 추가 하면 됩 니 다.
4. 링크 노드 삭제
1. 링크 노드 삭제 (1 급 포인터)
프로그램 설명:
1) 헤드 노드 가 노드 를 삭제 하려 면 헤드 를 헤드 - > next 로 가리 키 기만 하면 된다.
2) delete 는 노드 를 삭제 할 이전 노드 에 머 물 러 있 기 때문에 delete - > next 대 가 를 remain 에 부여 하고 free 에 있 으 면 됩 니 다.
struct LinkNode
*szyu_link_delete1(struct LinkNode *head, void *x)
{
if ( head == NULL )
{
return NULL;
}
struct LinkNode *delete = head;
struct LinkNode *remain = NULL;
if ( strcmp((char *)delete->x, (char *)x) == 0 )
{
remain = delete;
head = delete->next;
}
else
{
while ( delete->next != NULL && strcmp((char *)delete->next->x, (char *)x) != 0)
{
delete = delete->next;
}
remain = delete->next;
delete->next = delete->next->next;
}
free(remain);
return head;
}2, 링크 노드 삭제 (2 단계 포인터)
프로그램 설명
1) 머리 노드 일 때 * list = head, head = head - > next 이면 됩 니 다. 즉 * list = (* list) - > next 입 니 다.
2) 머리 노드 가 아니라면 list 는 next 를 가리 키 는 지침 입 니 다. 이때 * list 는 다음 노드 입 니 다. 다음 노드 를 삭제 하려 면 * list 에 값 을 다시 부여 하면 다음 노드 의 방향 을 바 꿀 수 있 습 니 다.
struct LinkNode
*szyu_link_delete2(struct LinkNode *head, void *x)
{
if ( head == NULL )
{
return head;
}
struct LinkNode **list = &head;
while ( (*list) != NULL && strcmp((char *)(*list)->x, (char *)x) != 0 )
{
list = &(*list)->next;
}
struct LinkNode *remain = *list;
(*list) = (*list)->next;
free(remain);
return head;
}5. 링크 방출
프로그램 설명:
1) 2 단 포인터 사용 후 * head 는 노드 를 삭제 합 니 다.
void
szyu_link_free2(struct LinkNode **head)
{
if ( *head == NULL || head == NULL )
{
return;
}
struct LinkNode *next = NULL;
for ( ; *head; *head = next )
{
next = (*head)->next;
free(*head);
}
}6. 링크 길이 획득
프로그램 설명:
1) 링크 가 앞장 서지 않 기 때문에 헤드 링크 를 직접 할당 합 니 다.
int
szyu_link_length1(struct LinkNode *head)
{
if ( head == NULL )
{
return 0;
}
struct LinkNode *pLen = head;
int len = 0;
for ( ; pLen != NULL; pLen = pLen->next )
{
len += 1;
}
return len;
}7. 링크 인쇄
void
szyu_link_print1(struct LinkNode *head)
{
if ( head == NULL )
{
return;
}
struct LinkNode *print = head;
for ( ; print != NULL; print = print->next )
{
printf("%s ", (char *)print->x);
}
printf("
");
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조 상의 연습 (2) 싱글 체인 시트#include "stdafx.h" #include "stdlib.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
