Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 이중 연결 목록의 크기를 찾는 프로그램

<시간/>

이 문제에서는 이중 연결 목록이 제공됩니다. 우리의 임무는 C++에서 이중 연결 목록의 크기를 찾는 프로그램을 만드는 것입니다.

이중 연결 목록은 단일 연결 목록에 비해 쉽게 앞뒤로 탐색이 가능한 특수한 유형의 연결 목록입니다. 다음은 이중 연결 목록의 개념을 이해하는 데 중요한 용어입니다.

  • 링크 - 링크드 리스트의 각 링크는 요소라는 데이터를 저장할 수 있습니다.

  • 다음 - 연결 목록의 각 링크는 다음이라는 다음 링크에 대한 링크를 포함합니다.

  • Prev - 연결 목록의 각 링크에는 Prev라는 이전 링크에 대한 링크가 포함되어 있습니다.

  • LinkedList - Linked List는 First라는 첫 번째 링크와 Last라는 마지막 링크에 대한 연결 링크를 포함합니다.

이중 연결 목록의 표현 -

C++에서 이중 연결 목록의 크기를 찾는 프로그램

문제 설명 − 위와 같은 유형의 이중 연결 목록이 제공됩니다. 그리고 우리는 그것의 크기(길이)를 찾을 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

the above linked list A <-> B <-> C.

출력

3

해결 방법

이중 연결 목록의 크기를 찾으려면 이중 연결 목록을 순회하고 길이가 유효한 길이를 추적해야 합니다.

알고리즘

초기화 - 길이 =0, *temp =헤드

  • 1단계 − 목록을 순회합니다. 즉, temp !=NULL까지 수행합니다.
    • 1.1단계 − 길이 증가, 길이++
    • 1.2단계 − 포인터 업데이트, temp =temp -> next.
  • 2단계 - 인쇄 길이.

우리 솔루션의 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
struct doublyLL {
   char val;
   struct doublyLL *next;
   struct doublyLL *prev;
};
void insertNode(struct doublyLL** head_ref, int value){
   struct doublyLL* new_node = new doublyLL;
   new_node->val = value;
   new_node->next = (*head_ref);
   new_node->prev = NULL;
   if ((*head_ref) != NULL)
      (*head_ref)->prev = new_node ;
      (*head_ref) = new_node;
}
int calcDLLSize(struct doublyLL *temp) {
   int length = 0;
   while (temp != NULL){
      temp = temp->next;
      length++;
   }
   return length;
}
int main(){
   struct doublyLL* head = NULL;
   insertNode(&head, 'A');
   insertNode(&head, 'H');
   insertNode(&head, 'E');
   insertNode(&head, 'K');
   insertNode(&head, 'M');
   insertNode(&head, 'S');
   cout<<"The size of Doubly Linked List is "<<calcDLLSize(head);
   return 0;
}

출력

The size of Doubly Linked List is 6