โปรแกรม C++ เพื่อใช้งาน Sorted Singly Linked List

ในโครงสร้างข้อมูล รายการที่เชื่อมโยง คือการรวบรวมองค์ประกอบข้อมูลเชิงเส้น องค์ประกอบหรือโหนดแต่ละรายการของรายการประกอบด้วยสองรายการ - ข้อมูลและการอ้างอิงไปยังโหนดถัดไป โหนดสุดท้ายมีการอ้างอิงถึงค่า null ในรายการที่เชื่อมโยง จุดเริ่มต้นเรียกว่าส่วนหัวของรายการ

แต่ละโหนดในรายการจะจัดเก็บเนื้อหาและตัวชี้หรือการอ้างอิงไปยังโหนดถัดไปในรายการ ในรายการที่เชื่อมโยงโดยลำพัง รายการที่เชื่อมโยงอย่างเดียวไม่ได้เก็บตัวชี้หรือการอ้างอิงไปยังโหนดก่อนหน้า

การพัฒนาโปรแกรม C++ เพื่อใช้งาน sorted Linked List

อัลกอริทึม

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.
      Initialize the next pointer with NULL.
      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 NULL.
      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 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 singly link list
2 3 4 6 7 2