โปรแกรม C++ เพื่อใช้งานรายการเชื่อมโยงแบบวงกลมเดียว

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

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

มีโปรแกรมสำหรับใช้งานรายการเชื่อมโยงแบบวงกลมดังนี้

ตัวอย่าง

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
   struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
   struct Node *ptr = head;
   newnode->data = newdata;
   newnode->next = head;
   if (head!= NULL) {
      while (ptr->next != head)
      ptr = ptr->next;
      ptr->next = newnode;
   } else
   newnode->next = newnode;
   head = newnode;
}
void display() {
   struct Node* ptr;
   ptr = head;
   do {
      cout<<ptr->data <<" ";
      ptr = ptr->next;
   } while(ptr != head);
}
int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The circular linked list is: ";
   display();
   return 0;
}

ผลลัพธ์

The circular linked list is: 9 2 7 1 3

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

struct Node {
   int data;
   struct Node *next;
};

ฟังก์ชัน insert() แทรกข้อมูลลงในจุดเริ่มต้นของรายการที่เชื่อมโยง มันสร้างโหนดใหม่และแทรกตัวเลขในฟิลด์ข้อมูลของโหนดใหม่ ถ้าส่วนหัวเป็น NULL แล้ว newnode จะชี้ไปที่ตัวเอง มิฉะนั้น node สุดท้ายในรายการที่เชื่อมโยงแบบวงกลมจะชี้ไปที่ newnode จากนั้นส่วนหัวจะชี้ไปที่จุดเริ่มต้นของรายการ เช่น ไปยังโหนดใหม่ ด้านล่างนี้

void insert(int newdata) {
   struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
   struct Node *ptr = head;
   newnode->data = newdata;
   newnode->next = head;
   if (head!= NULL) {
      while (ptr->next != head)
      ptr = ptr->next;
      ptr->next = newnode;
   } else
   newnode->next = newnode;
   head = newnode;
}

ฟังก์ชั่น display() แสดงรายการที่เชื่อมโยงทั้งหมด ptr แรกชี้ไปที่หัว จากนั้นจะส่งต่อไปยังโหนดถัดไปอย่างต่อเนื่องจนกว่าจะพิมพ์ค่าข้อมูลทั้งหมดของโหนด ด้านล่างนี้

void display() {
   struct Node* ptr;
   ptr = head;
   do {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   } while(ptr != head);
}

ในฟังก์ชัน main() ค่าต่าง ๆ แรกจะถูกแทรกลงในรายการที่เชื่อมโยงแบบวงกลมโดยการเรียก insert() จากนั้นรายการที่เชื่อมโยงจะปรากฏขึ้น ด้านล่างนี้

int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The circular linked list is: ";
   display();
   return 0;
}