ชี้ไปยังตัวชี้ในรายการที่เชื่อมโยง
ใครช่วยอธิบายฉันได้ไหมว่าทำไมรหัสนี้ถึงให้รายการว่างเปล่า:
typedef struct str_node{
int data;
struct str_node *next;
}node;
void begin(node *head);
void display_list(node *head);
int main(){
node *head;
int i;
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
display_list(head);
return 0;
}
void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}
แต่ถ้าฉันเปลี่ยนฟังก์ชัน start () โดยให้ตัวชี้เป็นตัวชี้จะให้รายการที่ถูกต้องหรือไม่?
void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}
คุณสามารถอธิบายฉันได้ไหมว่าทำไมเมื่อฉันส่งโหนดหลักไปยังฟังก์ชันเริ่มต้นฉันต้องส่งเป็น "& head"? และไม่เป็น "หัว" อีกต่อไป
คำตอบ
ในโปรแกรมแรกในข้อมูลโค้ดนี้
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
ตัวชี้headจะถูกส่งผ่านไปยังฟังก์ชันbeginตามค่า นั่นคือสำเนาของค่าของตัวชี้ที่headประกาศใน main ถูกสร้างขึ้นและถูกกำหนดให้กับพารามิเตอร์ที่มีชื่อเดียวกันของฟังก์ชันเริ่มต้น
void begin(node *head);
ดังนั้นภายในฟังก์ชันจึงเป็นพารามิเตอร์headที่เก็บสำเนาของตัวชี้เดิมheadที่เปลี่ยนแปลง ตัวชี้เดิมheadซึ่งเป็นค่าที่กำหนดให้กับพารามิเตอร์จะไม่มีการเปลี่ยนแปลง
ในการเปลี่ยนหัวตัวชี้เดิมที่ประกาศไว้ใน main คุณจะต้องส่งต่อไปยังฟังก์ชันโดยอ้างอิงทางอ้อมผ่านตัวชี้ไปยังหัวตัวชี้ตามที่ทำในโปรแกรมที่สอง
ดังนั้นควรประกาศฟังก์ชันเช่น
void begin(node **head);
และคุณต้องส่งหัวตัวชี้ทางอ้อมผ่านตัวชี้ไปที่มัน
begin( &head );
ในกรณีนี้การยกเลิกการอ้างอิงตัวชี้ที่ส่งผ่านฟังก์ชันจะได้รับการเข้าถึงโดยตรงไปยังส่วนหัวของตัวชี้ดั้งเดิมที่ประกาศไว้ใน main และสามารถเปลี่ยนแปลงได้ (ไม่ใช่สำเนาของค่าตามที่เกิดขึ้นในนิยามฟังก์ชันแรก)
new->next = *head;
*head = new;
เพื่อให้ชัดเจนยิ่งขึ้นให้พิจารณาโปรแกรมสาธิตง่ายๆนี้
#include <stdio.h>
typedef int T;
void f( T t )
{
t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
ผลลัพธ์คือ
Before calling f t is equal to 0
After calling f t is equal to 0
เนื่องจากฟังก์ชัน f เกี่ยวข้องกับสำเนาของค่าของอาร์กิวเมนต์ที่ส่งผ่านค่าของตัวแปรที่tประกาศใน main จึงไม่เปลี่ยนแปลง
ดังนั้นคุณต้องส่งผ่านตัวแปรดั้งเดิมtโดยการอ้างอิงผ่านตัวชี้เช่น
#include <stdio.h>
typedef int T;
void f( T *t )
{
*t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( &t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
ตอนนี้ผลลัพธ์ของโปรแกรมคือ
Before calling f t is equal to 0
After calling f t is equal to 10
ในโปรแกรมสาธิตเหล่านี้ชื่อTจะใช้เป็นนามแฝงสำหรับประเภทintและในอ็อบเจ็กต์หลักtมีประเภทนี้
ตอนนี้สมมติว่าชื่อ T เป็นนามแฝงสำหรับประเภท int *
typedef int * T;
ในกรณีนี้การประกาศใน main เป็นตัวอย่าง
T t = NULL;
หมายความว่าตัวแปรมีประเภทตัวชี้t int *นั่นคือเทียบเท่ากับ
int * t = NULL;
ดังนั้นในการส่งผ่านไปยังฟังก์ชันที่ต้องเปลี่ยนตัวแปรเดิมเราต้องส่งผ่านโดยการอ้างอิงเช่น
f( &t );
นั่นหมายความว่าฟังก์ชันที่เกี่ยวข้องจะต้องมีการประกาศประเภทพารามิเตอร์เช่น
void f( T *t );
แต่ในฐานะที่Tเป็นนามแฝงสำหรับด้วยเหตุนี้มันหมายความว่าฟังก์ชั่นมีพารามิเตอร์ชนิดที่int *int **
void f( int * *t );
เนื่องจากheadเป็นตัวแปรท้องถิ่น (อย่างมีประสิทธิภาพ) ดังนั้นการเปลี่ยนแปลงจึงไม่มีผลกระทบภายนอกฟังก์ชันในขณะที่การ*headเปลี่ยนแปลงจะเปลี่ยนแปลงสิ่งที่headชี้ไปและทำให้เกิด
หากคุณต้องการฟังก์ชั่นเพื่อให้สามารถเปลี่ยนค่าในintตัวแปร (พูดx) คุณจะผ่านมันชี้ไปxซึ่งจะมีชนิดint*และคุณจะได้รับตัวชี้ไปโดยใช้x &xเช่นเดียวกันไม่ว่าxจะเป็นประเภทใด
ความสับสนเล็กน้อยอาจมาจากการประกาศ
node *head;
แทน
node* head;
headคุณกำลังประกาศ headเป็นตัวแปรและเป็นตัวชี้ ไม่ใช่โหนด โปรดทราบด้วยว่าโหนดไม่ใช่รายการที่เชื่อมโยง: รายการที่เชื่อมโยงคือชุดของโหนดและอาจเป็นอย่างอื่นเพื่อให้มีการนำไปใช้งานที่เป็นประโยชน์ เพิ่มเติมเกี่ยวกับเรื่องนี้ในตอนท้าย
คุณได้main()ประกาศข้อเท็จจริงheadแล้วเพียงแค่กnode*. โหนดเองยังไม่มีอยู่ คุณประกาศbegin()เป็น
void begin(node *head);
และฉันคิดว่าคุณจะเห็นมันชัดเจนขึ้นเช่นกัน
void begin(node* parameter);
parameterคือnode*.
ภายในbegin()คุณจะได้รับสำเนาของตัวชี้และการเปลี่ยนตัวชี้จะไม่ทำให้ตัวชี้เดิมเปลี่ยนmain()ไป ในกรณีของคุณก็จะอยู่ในตลอดไปชี้ไปที่main()NULL
สิ่งที่สำคัญคือตัวชี้ก็เหมือนกับตัวแปรใด ๆ : ตัวชี้มีที่อยู่ และเนื้อหา เมื่อคุณผ่านค่าเช่นเดียวกับคุณได้ชี้ในการbegin()เริ่มต้นด้วยค่าที่มาจากNULL main()แต่พันธะระหว่างพวกเขาสิ้นสุด int the call: ค่าเริ่มต้น
เมื่อคุณส่งตัวชี้ไปbegin()โดยใช้โอเปอเรเตอร์ 'ที่อยู่ของ' และการเขียน&headสิ่งต่างๆจะเปลี่ยนไป: คุณจะเปลี่ยนโดยใช้ตัวดำเนินการ'*'ซึ่งหมายความว่าคุณจะเปลี่ยนที่อยู่ที่ชี้ไปดังนั้นมันจะเปลี่ยนmain()ไป เนื่องจากheadเป็นnode*ตัวชี้จะถูกประกาศเป็นnode**
แต่ให้พิจารณาเปลี่ยนการประกาศbegin()สำหรับรายการที่เชื่อมโยงโดยใช้:
node* begin(node* node);
ตรรกะคือการแทรกโหนดสามารถเปลี่ยนส่วนหัวของรายการได้ดังนั้นคุณจึงส่งคืนที่อยู่ใหม่เช่นเดียวกับใน
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
เป็นวิธีทั่วไปในการเขียนสิ่งนี้ node**ก็คือการใช้งาน
วิธีที่ฉันอธิบายที่นี่การดำเนินการใด ๆ ที่สามารถเปลี่ยนส่วนหัวของรายการต้อง
- กลับหัวใหม่
- รับและอัปเดตตัวชี้เป็นตัวชี้ของส่วนหัว
ดูรหัสนี้อีกครั้งที่แทรกที่จุดเริ่มต้นของรายการ:
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
กลับมาnewคุณจะได้รับheadการปรับปรุง และคุณสามารถเขียนmain()
node* another = NULL;
display_list(another);
// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
สังเกตบรรทัดanother = _insert_begin(i, another);และคุณจะเห็นว่าตัวชี้ในmain()ได้รับการอัปเดตอย่างไร
นี่คือผลลัพธ์
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
ด้วยการใช้งานนี้display_list()ซึ่งจะพิมพ์ 5 ค่าต่อบรรทัด:
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
อีกตัวอย่างหนึ่ง: การแทรกที่ส่วนท้าย
โปรดทราบว่าการแทรกที่ส่วนท้ายยังสามารถเปลี่ยนส่วนหัวได้ในกรณีที่รายการว่างเปล่าดังนั้นเรายังคงต้องส่งคืนที่อยู่หัว
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
การใช้งานอื่น: การแทรกจากน้อยไปหามาก
แน่นอนว่าการแทรกจากน้อยไปหามากสามารถเปลี่ยนหัวได้เช่นกัน
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
การลบรายการ
การลบรายการควรส่งคืนค่าnode*เพื่อทำให้ตัวชี้หัวไม่ถูกต้อง เป็นเรื่องปกติ ในขณะที่คุณคุ้นเคยกับกลไกนี้ทำให้แน่ใจได้ว่าตัวชี้ที่ไม่ถูกต้องจะไม่อยู่รอบ ๆ
โปรดทราบว่าตรรกะนี้ทำงานร่วมกัน: คุณต้องกำหนดตัวชี้หัวกลับทุกครั้งที่มีการโทรที่สามารถเปลี่ยนหัวได้
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
โปรแกรมที่กำลังทำงานอยู่
ผลลัพธ์ของโปรแกรมตัวอย่าง
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
inserted 6 to 10 at the end
0 1 2 3 4
5 6 7 8 9
10
list has 11 elements
inserted 0 to 10, ordered
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 22 elements
inserted -1 to -10, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 32 elements
inserted 11 to 20, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10 11 12 13
14 15 16 17 18
19 20
list has 42 elements
about to delete list
empty list
ตัวอย่างโปรแกรม C
#include <stdio.h>
#include <stdlib.h>
typedef struct str_node
{
int data;
struct str_node* next;
} node;
void begin(node* pNode);
node* delete_list(node*);
int display_list(node*);
node* _insert_begin(int, node*);
node* _insert_end(int, node*);
node* _insert_ordered(int, node*);
int main()
{
node* another = NULL;
display_list(another);
// insert 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
// insert 6 to 10 at the end
for (int i = 6; i <= 10; i += 1)
another = _insert_end(i, another);
printf("inserted 6 to 10 at the end\n");
display_list(another);
// insert 0 to 10 ordered
for (int i = 0; i <=10; i += 1)
another = _insert_ordered(i, another);
printf("inserted 0 to 10, ordered\n");
display_list(another);
// insert -1 to -10 ordered
for (int i = -1; i >= -10; i -= 1)
another = _insert_ordered(i, another);
printf("inserted -1 to -10, ordered\n");
display_list(another);
// insert 11 to 20 ordered
for (int i = 11; i <= 20; i += 1)
another = _insert_ordered(i, another);
printf("inserted 11 to 20, ordered\n");
display_list(another);
printf("about to delete list\n");
another = delete_list(another);
display_list(another);
return 0;
}
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
โครงสร้างรายการที่เชื่อมโยงที่มีประโยชน์มากขึ้น
พิจารณาสิ่งต่อไปนี้
struct no
{
void* item;
struct no* next;
struct no* prev;
}; // no
typedef struct no Node;
typedef struct
{ // example, more flexible
char* name;
unsigned size;
unsigned capacity;
Node* head;
Node* tail;
} Linked_list;
วิธีนี้รายการที่เชื่อมโยงถูกกำหนดให้เป็นคอนเทนเนอร์ของโหนด
nameมันมีแม้กระทั่งตัวเลือกsizeพร้อมใช้งานและทันสมัยอยู่เสมอ- ขีด จำกัด ขนาดสามารถใช้เป็น
capacity - แทรกในตอนท้ายและที่จุดเริ่มต้นไม่ไม่ต้องการให้คุณทำตามทุกโหนดอื่น ๆ เนื่องจากรายการห่อหุ้มตัวชี้ไปทั้งหัวและหาง
- โหนดมีตัวชี้ไปยังโหนดถัดไป AND ก่อนหน้าดังนั้นข้อมูลบางอย่างเช่นเพลย์ลิสต์หรือคอลเลคชันเช่นนี้สามารถทำซ้ำได้ง่ายขึ้น
- โปรแกรมสามารถมีรายการจำนวนเท่าใดก็ได้เนื่องจากแต่ละรายการจะสรุปข้อมูลเมตาทั้งหมดนี้
- รายการสามารถมีอะไรก็ได้เนื่องจากข้อมูลเป็นตัวชี้ให้เป็นโมฆะ
void* - สามารถใช้งานฟังก์ชันเช่น empty () หรือ size () ได้อย่างง่ายดาย
- ฟังก์ชันทั้งหมดใช้ตัวชี้ไปที่รายการ
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
เกี่ยวกับ:
void begin(node *head){
การเปลี่ยนheadเฉพาะ call stack 'head' สิ่งที่จำเป็นคือการเปลี่ยนตำแหน่งที่ 'head' ในฟังก์ชันของผู้โทรชี้ไป ในการทำเช่นนั้นผู้โทรจะต้องส่งที่อยู่ของ "หัว" ความจริงที่ว่า 'หัว' คือตัวชี้ไม่ได้ช่วยให้ชัดเจนว่าต้องทำอะไร