정렬된 순환 단일 연결 목록을 구현하는 C++ 프로그램

데이터 구조에서 연결 목록은 데이터 요소의 선형 모음입니다. 목록의 각 요소 또는 노드는 데이터와 다음 노드에 대한 참조라는 두 가지 항목으로 구성됩니다. 마지막 노드에는 null에 대한 참조가 있습니다. 연결 목록에서 진입점을 목록의 머리라고 합니다.

목록의 각 노드는 내용과 목록의 다음 노드에 대한 포인터 또는 참조를 단일 연결 목록에 저장합니다. 단일 연결 리스트는 이전 노드에 대한 포인터나 참조를 저장하지 않습니다.

정렬된 단일 연결 목록이므로 연결 목록의 데이터 항목은 항상 정렬된 상태로 유지됩니다.

다음은 Sorted Circularly Singly Linked List를 구현하는 C++ 프로그램입니다.

알고리즘

Begin
   function createnode() to insert node in the list:
      It checks whether the list is empty or not. If the list is empty put the node as first element and update head.
      If list is not empty,
      It creates a newnode and inserts the number in the data field of the newnode.
      Now the newnode will be inserted in such a way that linked list will remain sorted.
      If it gets inserted at the last, then the newnode points to the head.
      If the newnode inserted at the first, then the linked list starts from there.
End
Begin
   function display() to print the list content having n number of nodes:
      Initialize c = 0.
      Initialize pointer variable with the start address
      while (c <= n)
         Print the node info
         Update pointer variable
         Increment c.
End

예시 코드

#include<iostream>
using namespace std;
struct nod {
   int d;
   nod *n;
}
*p = NULL, *head = NULL, *q = NULL, *np = NULL;
int c = 0;
void createnode(int n) {
   np = new nod;
   np->d = n;
   np->n = NULL;
   if (c == 0) {
      head = np;
      p = head;
      p->n = head;
      c++;
   } else if (c == 1) {
      p = head;
      q = p;
      if (np->d < p->d) {
         np->n = p;
         head = np;
         p->n = np;
      } else if (np->d > p->d) {
         p->n = np;
         np->n = head;
      }
      c++;
   } else {
      p = head;
      q = p;
      if (np->d < p->d) {
         np->n = p;
         head = np;
         do {
            p = p->n;
         }
         while (p->n != q);
         p->n = head;
      } else if (np->d > p->d) {
         while (p->n != head && q->d < np->d) {
            q = p;
            p = p->n;
            if (p->n == head) {
               p->n = np;
               np->n = head;
            } else if (np->d< p->d) {
               q->n = np;
               np->n = p;
               break;
            }
         }
      }
   }
}
void display(int i) {
   nod *t = head;
   int c = 0;
   while (c <= i ) {
      cout<<t->d<<"\t";
      t = t->n;
      c++;
   }
}
int main() {
   int i = 0, n, a;
   cout<<"enter the no of nodes\n";
   cin>>n;
   while (i < n) {
      cout<<"\nenter value of node\n";
      cin>>a;
      createnode(a);
      i++;
   }
   cout<<"sorted circularly singly link list"<<endl;
   display(n);
}

출력

enter the no of nodes
5
enter value of node
6
enter value of node
4
enter value of node
7
enter value of node
3
enter value of node
2
sorted circularly singly link list
2 3 4 6 7 2