ในโครงสร้างข้อมูล รายการเชื่อมต่อ (Linked List) เป็นการรวบรวมข้อมูลแบบเส้นตรง แต่ละองค์ประกอบหรือโหนดของรายการประกอบด้วยสองรายการ - ข้อมูลและการอ้างอิงไปยังโหนดถัดไป โหนดสุดท้ายมีการอ้างอิงไปยัง null เข้าสู่รายการเชื่อมต่อ จุดเข้าถึงเรียกว่า head ของรายการ
แต่ละโหนดในรายการเก็บเนื้อหาและพอยน์เตอร์หรือการอ้างอิงไปยังโหนดถัดไปในรายการ ในรายการเชื่อมต่อเดี่ยว (singly linked list) ไม่ได้เก็บพอยน์เตอร์หรือการอ้างอิงไปยังโหนดก่อนหน้า
พัฒนาโปรแกรม C++ เพื่อนำรายการเชื่อมต่อเดี่ยวที่จัดเรียงแล้วมาใช้งาน
อัลกอริทึม
Begin ฟังก์ชัน createnode() เพื่อแทรกโหนดในรายการ: ตรวจสอบว่ารายการว่างหรือไม่ ถ้ารายการว่าง ให้วางโหนดเป็นองค์ประกอบแรกและอัปเดต head เริ่มต้นพอยน์เตอร์ next ด้วย NULL ถ้ารายการไม่ว่าง สร้าง newnode และแทรกตัวเลขในฟิลด์ข้อมูลของ newnode ตอนนี้ newnode จะถูกแทรกอย่างที่รายการเชื่อมต่อจะยังคงจัดเรียงแล้ว ถ้าแทรกที่ท้าย newnode จะชี้ไป NULL ถ้า newnode แทรกที่ต้น รายการเชื่อมต่อจะเริ่มจากนั้น End Begin ฟังก์ชัน display() เพื่อพิมพ์เนื้อหาของรายการที่มี n โหนด: เริ่มต้น c = 0 เริ่มต้นตัวแปรพอยน์เตอร์ด้วยที่อยู่เริ่มต้น while (c <= n) พิมพ์ข้อมูลโหนด อัปเดตตัวแปรพอยน์เตอร์ เพิ่ม 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
