รายการที่เชื่อมโยงใน C: วิธีการติดตั้งรายการที่เชื่อมโยงใน C?

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

รายการที่เชื่อมโยงใน C คืออะไร?

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

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

ประเภทรายการเชื่อมโยงที่ได้รับความนิยมมากที่สุด ได้แก่ :

1. รายการลิงค์เดี่ยว
2. รายการลิงก์ทวีคูณ

ตัวอย่างรายการที่เชื่อมโยง

รูปแบบ: [ข้อมูลที่อยู่]

หัวหน้า -> [3,1000] -> [43,1001] -> [21,1002]

ในตัวอย่างหมายเลข 43 แสดงอยู่ที่ตำแหน่ง 1000 และมีที่อยู่ในโหนดก่อนหน้า นี่คือวิธีแสดงรายการที่เชื่อมโยง

ฟังก์ชันรายการที่เชื่อมโยงพื้นฐาน

มีฟังก์ชันมากมายที่สามารถนำไปใช้ในรายการที่เชื่อมโยงใน C. มาลองทำความเข้าใจกับฟังก์ชันเหล่านี้ด้วยความช่วยเหลือของโปรแกรมตัวอย่างขั้นแรกเราสร้างรายการแสดงแทรกที่ตำแหน่งใดก็ได้ลบตำแหน่ง รหัสต่อไปนี้จะแสดงวิธีดำเนินการในรายการ

#include #include โมฆะ create () การแสดงโมฆะ () โมฆะ insert_begin () โมฆะ insert_end () โมฆะ insert_pos () โมฆะ delete_begin () โมฆะ delete_end () โมฆะ delete_pos () โหนดโครงสร้าง {int info struct node * next} struct node * start = NULL int main () {int choice ในขณะที่ (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3. ใส่ที่ จุดเริ่มต้น n ') printf (' n 4. ใส่ที่ปลาย n ') printf (' n 5. แทรกที่ตำแหน่งที่ระบุ n ') printf (' n 6. ลบจากจุดเริ่มต้น n ') printf (' n 7. ลบ จากท้าย n ') printf (' n 8. ลบจากตำแหน่งที่ระบุ n ') printf (' n 9.Exit n ') printf (' n ----------------- --------------------- n ') printf (' Enter your choice: t ') scanf ('% d ', & choice) switch (choice) {case 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d สร้าง () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('n ป้อนค่าข้อมูลสำหรับโหนด: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start ในขณะที่ (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n ') return} else {ptr = start printf (' nThe List elements are: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} เป็นโมฆะ insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEnter the ค่าข้อมูลสำหรับโหนด: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} โมฆะ insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} น rintf ('n ป้อนค่าข้อมูลสำหรับโหนด: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} โมฆะ insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('n ป้อนตำแหน่งสำหรับโหนดใหม่ที่จะแทรก: t') scanf ('% d' , & pos) printf ('n ป้อนค่าข้อมูลของโหนด: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {สำหรับ (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Handle with care] n') return}} temp-> next = ptr-> next ptr -> next = temp}} โมฆะ delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' n องค์ประกอบที่ถูกลบคือ:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('n องค์ประกอบที่ถูกลบคือ:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('n องค์ประกอบที่ถูกลบคือ:% dt', ptr-> info) free (ptr)}} เป็นโมฆะ delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('n ป้อนตำแหน่งของโหนดที่จะลบ : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' n องค์ประกอบที่ถูกลบคือ:% dt ', ptr-> info) ฟรี (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('n องค์ประกอบที่ถูกลบคือ: % dt ', ptr-> ข้อมูล) ฟรี (ptr)}}}

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

โหนดโครงสร้าง {int ข้อมูลโครงสร้างโหนด * ถัดไป}

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

java วิธีสร้างอาร์เรย์ของวัตถุ

• สร้าง()
• แสดง()
• insert_begin ()
• insert_end ()
• ] insert_pos ()
• delete_begin ()
• delete_end ()
• delete_pos ()

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

ขึ้นอยู่กับสิ่งที่ป้อนเข้าฟังก์ชันจะถูกเรียกใช้ ต่อไปเรามีฟังก์ชั่นต่างๆที่ต้องแก้ไข มาดูฟังก์ชันแต่ละอย่างกัน

สร้างฟังก์ชัน

ขั้นแรกมีฟังก์ชันสร้างเพื่อสร้างรายการที่เชื่อมโยง นี่เป็นวิธีพื้นฐานในการสร้างรายการที่เชื่อมโยง ให้เราดูรหัส

โมฆะ create () {struct node * temp, * ptr printf ('n ป้อนค่าข้อมูลสำหรับโหนด: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}

เอาต์พุต

ขั้นแรกมีการสร้างพอยน์เตอร์สองตัวในประเภท โหนด ptr และ temp . เรารับค่าที่จำเป็นในการเพิ่มในรายการที่เชื่อมโยงจากผู้ใช้และเก็บไว้ในส่วนข้อมูลของตัวแปร temp และกำหนด temp ของ next ซึ่งเป็นส่วนที่อยู่ให้เป็น null มีตัวชี้เริ่มต้นถือจุดเริ่มต้นของรายการ จากนั้นเราตรวจสอบจุดเริ่มต้นของรายการ หากจุดเริ่มต้นของรายการเป็นค่าว่างเราจะกำหนดอุณหภูมิให้กับตัวชี้เริ่มต้น มิฉะนั้นเราจะข้ามไปยังจุดสุดท้ายที่มีการเพิ่มข้อมูล

สำหรับสิ่งนี้เรากำหนด ptr เป็นค่าเริ่มต้นและข้ามไปจนถึง ptr-> next = null . จากนั้นเราจะมอบหมาย ptr-> ถัดไป ที่อยู่ของอุณหภูมิ ในทำนองเดียวกันมีรหัสที่กำหนดสำหรับการแทรกที่จุดเริ่มต้นการแทรกที่ส่วนท้ายและการแทรกในตำแหน่งที่ระบุ

ฟังก์ชันการแสดงผล

นี่คือรหัสสำหรับฟังก์ชันการแสดงผล

โมฆะ display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nThe List elements are: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> next}}}

เอาต์พุต

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

ลบฟังก์ชัน

นี่คือข้อมูลโค้ดสำหรับลบโหนดออกจากรายการที่เชื่อมโยง

เป็นโมฆะ delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nEnter the position of the โหนดที่จะลบ: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' n องค์ประกอบที่ถูกลบคือ:% dt ', ptr-> ข้อมูล ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe องค์ประกอบที่ถูกลบคือ:% dt ', ptr-> info) free (ptr)}}}

เอาต์พุต

ในขั้นตอนการลบขั้นแรกจะตรวจสอบว่ารายการว่างหรือไม่หากมีอยู่ หากไม่ว่างจะขอให้ผู้ใช้ลบตำแหน่ง เมื่อผู้ใช้เข้าสู่ตำแหน่งจะตรวจสอบว่าเป็นตำแหน่งแรกหรือไม่หากใช่จะกำหนด ptr เพื่อเริ่มต้นและย้ายตัวชี้เริ่มต้นไปยังตำแหน่งถัดไปและลบ ptr ถ้า ตำแหน่งไม่ใช่ศูนย์ จากนั้นจะเรียกใช้ for loop จาก 0 ไปจนถึง pos ที่ผู้ใช้ป้อนและเก็บไว้ในไฟล์ ตำแหน่ง ตัวแปร. มีคำสั่ง if เพื่อตัดสินใจว่าตำแหน่งที่ป้อนไม่อยู่ ถ้า ptr เท่ากับ null แล้วมันไม่อยู่

เรา กำหนด ptr ให้กับ temp ใน for loop จากนั้น ptr จะย้ายไปยังส่วนถัดไป หลังจากนี้เมื่อพบตำแหน่ง เราสร้างตัวแปร temp เพื่อเก็บค่าของ ptr-> ถัดไป ดังนั้นการข้าม ptr จากนั้น ptr จะถูกลบ ในทำนองเดียวกันสามารถทำได้สำหรับการลบองค์ประกอบแรกและครั้งสุดท้าย

รายการที่เชื่อมโยงเป็นทวีคูณ

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

#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position previous Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} โมฆะ Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> previous p2 = p -> next p1 - > next = p -> next if (p2! = NULL) // ถ้าโหนดไม่ใช่โหนดสุดท้าย p2 -> previous = p -> previous} else printf ('Element ไม่มีอยู่ !!! n')} ถือเป็นโมฆะ แสดง (รายการ l) {printf ('องค์ประกอบรายการคือ ::') ตำแหน่ง p = l-> ถัดไปในขณะที่ (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('DOUBLY LINKED LIST IMPLEMENTATION OF L IST ADTnn ') ทำ {printf (' nn1. สร้าง 2. DELETEn 3. DISPLAYn 4. QUITnn ป้อนตัวเลือก :: ') scanf ('% d ', & ch) สวิตช์ (ch) {case 1: p = l printf (' Enter the element to be insert :: ') scanf ('% d', & x) printf ('ป้อนตำแหน่งขององค์ประกอบ ::') scanf ('% d', & pos) สำหรับ (i = 1 iถัดไป} แทรก (x, l, p) ตัวแบ่งตัวพิมพ์ 2: p = l printf ('ป้อนองค์ประกอบที่จะลบ ::') scanf ('% d', & x) ลบ (x, p) ตัวแบ่งตัวพิมพ์ 3: แสดง (l) break}} while (ch<4) } 

เอาต์พุต

ดังที่คุณเห็นแนวคิดของการดำเนินการนั้นค่อนข้างง่าย รายการที่เชื่อมโยงแบบทวีคูณมีการดำเนินการเช่นเดียวกับรายการที่เชื่อมโยงเดี่ยวในภาษาโปรแกรม C ข้อแตกต่างเพียงอย่างเดียวคือมีตัวแปรที่อยู่อื่นซึ่งช่วยในการข้ามรายการได้ดีขึ้นในรายการที่เชื่อมโยงแบบทวีคูณ

ฉันหวังว่าคุณจะเข้าใจวิธีดำเนินการขั้นพื้นฐานในรายการที่เชื่อมโยงแบบเดี่ยวและแบบทวีคูณใน C

หากคุณต้องการเรียนรู้ Linked List ใน Java นี่คือไฟล์ .

การตั้งค่า eclipse สำหรับ java

หากคุณพบคำถามใด ๆ อย่าลังเลที่จะถามคำถามทั้งหมดของคุณในส่วนความคิดเห็นของ 'รายการที่เชื่อมโยงใน C' และทีมงานของเรายินดีที่จะตอบ