데이터 구조의 링크 드 - list) 및 조작

1. 데이터 구조의 링크 드 - list)
선형 표 는 가장 자주 사용 하 는 저장 구조 로 선형 표 의 모든 단원 을 요소 라 고 한다. 요 소 는 하나의 데이터 와 하나의 주소 선형 표를 가지 고 두 가지 물리 적 저장 방식 이 있다. 순서 저장 방식 과 체인 저장 방식 배열 은 대표 적 인 순서 저장 방식 을 가 진 선형 표 이 고 단일 체인 표 는 대표 적 인 체인 저장 방식 을 가 진 선형 표 이다.
1. 배열
배열 의 메모 리 는 연속 적 으로 분 배 됩 니 다. 배열 의 색인 을 통 해 해당 하 는 데 이 터 를 직접 얻 을 수 있 습 니 다. 색인 은 선형 표 에서 말 하 는 요소 의 '주소' 이지 만 색인 은 주소 가 아 닙 니 다.
2. 싱글 체인 리스트
단일 체인 시트 의 메모 리 는 체인 식 입 니 다. 즉, 연속 되 지 않 습 니 다. 요소 중의 주 소 는 링크 의 다음 요소 의 주 소 를 가리 키 고 있 습 니 다.
싱글 체인 시트 의 헤드 포인터 와 헤드 노드 에 대하 여
머리 지침 은 머리 결점 이 아니다.헤드 포인터 가 헤드 노드 를 가리 키 고 헤드 노드 는 보통 data 필드 가 NULL 또는 단일 체인 표 의 length 이 며 다음 과 같은 데이터 구조 에서

typedef struct LinkedListNode
{//     
    int value;
    struct LinkedListNode *next;
}*LinkedList;

만약 에 LinkedList L 을 정의 한다 면 L 은 우리 가 필요 로 하 는 헤드 포인터 (헤드 포인 터 는 싱글 체인 시트 에 있어 서 필수 적 이 고 헤드 노드 가 아 닙 니 다) 이 고 L = (LinkedList malloc (sizeof (LinkedList Node) 입 니 다. 이것 은 결점 을 신 청 했 습 니 다. 여기 서 첫 번 째 결점 은 바로 헤드 노드 입 니 다.
정의 단일 체인 테이블
단일 체인 시트 는 두 개의 도 메 인 이 있 습 니 다. data 도 메 인 은 데 이 터 를 저장 하 는 데 사용 되 고 next 도 메 인 은 다음 노드 의 주 소 를 저장 하 는 데 사 용 됩 니 다.

typedef struct LinkedListNode
{//     
    int value;
    struct LinkedListNode *next;
}*LinkedList;

단일 링크 만 들 기

LinkedList CreateLinkedList()
{
    LinkedListNode* newNode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (newNode != NULL)
    {
        newNode->value = 0;
        newNode->next = NULL;
        return newNode;
    }
    else
    {
        return NULL;
    }
}

새 노드 만 들 기

LinkedListNode* CreateLinkedListNode(int val)
{//         
    LinkedListNode* newNode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (newNode != NULL)
    {
        newNode -> value = val;
        newNode->next = NULL;
        return newNode;
    }
    else
    {
        return NULL;
    }
}

앞 삽입 법 에 새 요소 삽입 (새 노드)
앞 삽입: 머리 결점 뒤에 새로운 요 소 를 삽입 하면 머리 결점 뒤의 요 소 는 영원히 새로운 요소 입 니 다. 체인 표 의 끝 점 head, 요소 x1, x2, x3 을 순서대로 삽입 하고 링크 의 머리 끝 을 왼쪽 에서 오른쪽으로 설정 합 니 다 (1) Insert 후: head x1 (2) Insert 후: head x2 x1 (3) Insert 후: head x3 x2 x1

void anteriorInsert(LinkedListNode* head, int val)
{
    LinkedListNode* newNode = CreateLinkedListNode(val);
    newNode->next = head->next;//         next      next
    head->next = newNode;//      next     
    head->value++; //       data      length
}

후 삽입 법 새 요소 삽입 (새 노드)
후 삽입: 꼬리 포인터 가 가리 키 는 결점 뒤에 새 요 소 를 삽입 합 니 다. 꼬리 포인터 가 가리 키 는 결점 은 영원히 새로운 요소 입 니 다. 요소 x1, x2, x3 을 순서대로 삽입 하고 링크 의 머리 끝 을 왼쪽 에서 오른쪽으로 설정 합 니 다. 꼬리 지침 을 하나 더 설정 하여 조작 을 더욱 편리 하 게 합 니 다. 그렇지 않 으 면 링크 를 옮 겨 다 녀 야 합 니 다. (1) Insert 후: x1 (2) Insert 후: x1 x2 (3) Insert 후: x1 x2 x3

void posteriorInsert(LinkedListNode* head, LinkedListNode* tail, int val)
{
    LinkedListNode* newNode = CreateLinkedListNode(val);
    tail->next = newNode;//      next     
    tail = tail->next;//          
    head->value++; //       data      length
}

data 필드 의 값 으로 노드 를 찾 습 니 다.
여기 서 찾 는 것 은 링크 에서 첫 번 째 data 필드 가 val 과 같은 결점 을 찾 는 것 입 니 다. 모든 결점 이 아 닙 니 다.

LinkedListNode* SearchByVal(LinkedList L, int val)
{
    LinkedListNode* Node = L->next;
    while (Node)
    {
        if (Node->value == val)
        {
            //    return
            return Node;
        }
        Node = Node->next;
    }
    return Node;
}

data 필드 의 값 에 따라 노드 의 data 필드 의 값 을 수정 합 니 다.

void UpdateVal(LinkedList L, int preVal , int aftVal)
{//   data   preVal    data     aftVal
    LinkedListNode* Node = L->next;
    while (Node)
    {
        if (Node->value == preVal)
        {
            Node->value = aftVal;
        }
        Node = Node->next;
    }
}

data 필드 의 값 에 따라 노드 를 삭제 합 니 다.
첫 번 째 data 필드 가 val 과 같은 결점 을 찾 아 삭제 합 니 다.

void DeleteByVal(LinkedListNode* head, int val)
{
    if (head->next == NULL)
    {
        cout << "LinkedList is null" << endl;
    }
    else
    {
        //        
        LinkedListNode* previousNode = head, *currentNode = head->next;
        while (currentNode)
        {
            if (currentNode->value == val)
            {
                //      
                previousNode->next = currentNode->next;
                free(currentNode);
                head->value--;
                break;
            }   
            else
            {
                currentNode = currentNode->next;
                previousNode = previousNode->next;
            }
        }
    }
    return;
}

체인 리스트 비우 기

void FreeLinkedList(LinkedList L)
{
    for (LinkedListNode* temp = L; L!= NULL; temp = L)
    {
        L = L->next;
        free(temp);
    }
}

싱글 체인 시트 후 삽입 법 에 대한 의문
그 다음 에 코드 를 위 와 같이 꽂 으 면 어떻게 옮 겨 다 녀 야 합 니까? 꼬리 포인터 에서 앞으로 옮 겨 다 녀 야 합 니까? 그 느낌 은 머리 포인터 가 약간 흐리멍덩 합 니 다. 머리 결점 을 뒤로 옮 겨 다 녔 지만 위 코드 의 머리 결점 인 next 가 NULL 이 라 어색 합 니 다. 대신 에 답 을 구 합 니 다.