Bağlantılı listedeki işaretçiye işaretçi
Birisi bana bu kodun neden bana boş listeyi verdiğini açıklayabilir mi:
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;
}
Ancak, bir işaretçi ile begin () işlevini değiştirirsem, bana doğru listeyi verir?
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;
}
Ayrıca, ana düğüm başından işleve geçtiğimde onu neden "& head" olarak geçirmek zorunda olduğumu da açıklayabilir misin? ve artık "kafa" olarak değil
Yanıtlar
Bu kod parçacığındaki ilk programda
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
işaretçi head, işleve begindeğere göre iletilir . Yani headmain içinde bildirilen işaretçi değerinin bir kopyası oluşturulur ve aynı isimdeki parametreye atanır begin
void begin(node *head);
Dolayısıyla, işlevin içinde, headbaşlangıçta headdeğiştirilen orijinal işaretçinin bir kopyasını tutan parametredir . headDeğeri parametreye atanan orijinal işaretçi değiştirilmiyor.
Esas olarak bildirilen orijinal işaretçi başlığını değiştirmek için, ikinci programda yapıldığı gibi, dolaylı olarak bir işaretçi aracılığıyla işaretçi kafasına başvurarak işleve aktarmanız gerekir.
Yani işlev şu şekilde beyan edilmelidir:
void begin(node **head);
Ve işaretçi kafasını dolaylı olarak bir işaretçiden ona geçirmeniz gerekir.
begin( &head );
Bu durumda, geçirilen göstericinin başvurusunu kaldıran işlev, ana olarak bildirilen orijinal işaretçi başlığına doğrudan erişim elde eder ve onu değiştirebilir (ilk işlev tanımında yer aldığı için değerinin bir kopyası değil)
new->next = *head;
*head = new;
Daha açık hale getirmek için bu basit gösterici programı düşünün.
#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;
}
Çıktısı
Before calling f t is equal to 0
After calling f t is equal to 0
F işlevi, iletilen bağımsız değişkenin değerinin bir kopyasıyla tilgilendiğinden, main içinde bildirilen değişkenin değeri değiştirilmedi.
Bu nedenle, orijinal değişkeni treferans olarak işaretçi üzerinden geçirmeniz gerekir.
#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;
}
Şimdi program çıktısı
Before calling f t is equal to 0
After calling f t is equal to 10
Bu gösterici programlarda Tad, tür için bir takma ad olarak kullanılır intve esas olarak nesne tbu türe sahiptir.
Şimdi, T adının int * türü için bir takma ad olduğunu varsayalım.
typedef int * T;
Bu durumda, örneğin esas olarak bir beyan
T t = NULL;
değişkenin tişaretçi tipine sahip olduğu anlamına gelir int *. Yani eşdeğerdir
int * t = NULL;
Dolayısıyla, onu orijinal t değişkenini değiştirmesi gereken bir işleve geçirmek için, onu aşağıdaki gibi referansla iletmemiz gerekir:
f( &t );
bu, karşılık gelen işlevin aşağıdaki gibi tanımlanmış parametre türüne sahip olacağı anlamına gelir
void f( T *t );
ancak Tbir takma ad olduğu için int *bu, işlevin türde bir parametreye sahip olduğu anlamına gelir int **.
void f( int * *t );
Çünkü head(etkili) yerel bir değişken, bu yüzden onu değiştirmenin işlevin dışında bir etkisi yoktur, oysa değiştirmek *headneyi headişaret ettiğini değiştirir ve dolayısıyla yapar.
Bir işlevin bir intdeğişkendeki değeri değiştirebilmesini xistiyorsanız (örneğin, ), xtürüne sahip bir işaretçi iletirsiniz int*ve xkullanarak işaretçiyi alırsınız &x. Ne tür olursa olsun aynı şey geçerlidir x.
Açıklamadan biraz karışıklık gelebilir
node *head;
onun yerine
node* head;
Beyan ediyorsun head. headdeğişkendir ve bir göstericidir. Bu bir düğüm değil. Ayrıca bir düğümün bağlantılı bir liste olmadığına dikkat edin: bağlantılı bir liste, bir düğümler koleksiyonudur ve muhtemelen yararlı bir uygulamaya sahip olmak için başka bir şeydir. Bununla ilgili daha sonra daha sonra.
Gerçek şu ki, main()beyan ettiniz head, sadece bir node*. Düğümün kendisi henüz mevcut değil. Sen beyan begin()olarak
void begin(node *head);
ve daha net göreceğinizi düşünüyorum
void begin(node* parameter);
parameterolduğunu node*.
İçeride begin()işaretçinin bir kopyasını alırsınız ve işaretçiyi değiştirmek, orijinal işaretçiyi değiştirmez main(). Senin durumunda main()sonsuza kadar işaret edecek NULL.
Önemli olan, bir göstericinin herhangi bir değişken gibi olmasıdır: Bir göstericinin bir adresi vardır. Ve bir içerik. Değere göre geçtiğinizde, tıpkı sizin yaptığınız gibi, işaretçi , gelen DEĞER begin()ile başlar . Ancak aralarındaki bağ, çağrı ile biter: başlangıç değeri.NULLmain()
Sınavı geçtikten sonra bir işaretçi için begin()'adresi' operatörünü kullanarak ve yazma, &headişler değişikliği: Eğer operatörünü kullanarak bunu değiştirecek '*'o değişecek yüzden, bu işaret adresi değişecek yani main(). Yana headolduğunu node*buna bir işaretçi olarak ilan edileceknode**
Ancak, aşağıdakileri begin()kullanarak bağlantılı bir listenin bildirimini değiştirmeyi düşünün :
node* begin(node* node);
Mantık, bir düğüm eklemenin listenin başını değiştirebilmesidir, böylece yeni adresi döndürürsünüz.
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
bunu yazmanın yaygın bir yoludur. Bir diğeri kullanmaktır node**.
Burada anlattığım şekilde, listenin başını değiştirebilecek herhangi bir işlem,
- yeni kafayı geri getir
- başın işaretçisine bir işaretçi alın ve güncelleyin
Listenin başına ekleyen bu koda tekrar bakın:
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;
}
newsize geri dönerek headgüncellenir. Ve yazabilirsinmain()
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);
Çizgiyi not edin another = _insert_begin(i, another);ve içerideki işaretçinin nasıl main()güncellendiğini görün.
Bu çıktı
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
display_list()Satır başına 5 değer basan bu uygulamasını kullanarak :
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;
};
Başka bir örnek: sonuna eklemek
Listenin boş olması durumunda, sonuna eklemenin başlığı da değiştirebileceğini unutmayın, bu nedenle yine de baş adresini döndürmemiz gerekir
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;
}
Başka bir kullanım: artan sırayla ekleme
Elbette, artan sırayla eklemek de başlığı değiştirebilir.
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()
Bir listeyi silme
Bir listeyi sil, ayrıca node*baş işaretçisini geçersiz kılmak için a döndürmelidir . Normaldir. Mekaniğine alıştıkça, bu geçersiz bir işaretçinin etrafta kalmamasını sağlar.
Bu mantığın işbirlikçi olduğuna dikkat edin: kafayı değiştirebilecek her aramada baş işaretçisini geri atamanız gerekir.
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;
};
Çalışan bir program
Örnek programın çıktısı
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
Örnek C programı
#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;
};
Muhtemelen daha kullanışlı bir Bağlantılı Liste yapısı
Aşağıdakileri göz önünde bulundur
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;
Bu şekilde bağlantılı bir liste, düğümlerin bir kapsayıcısı olarak tanımlanır.
- Hatta isteğe bağlı
name. sizeher zaman kullanılabilir ve güncel- boyut sınırı şu şekilde uygulanabilir:
capacity - Liste, hem başa hem de kuyruğa işaretçileri kapsadığından , sonuna ve başlangıca eklemek, diğer tüm düğümleri izlemenizi gerektirmez
- bir düğümün sonraki VE önceki düğümlere işaretçileri vardır, böylece çalma listeleri veya koleksiyonlar gibi bazı veriler daha kolay yinelenebilir.
- bir programın herhangi bir sayıda listesi olabilir, çünkü her biri bu meta verilerin tümünü kapsamaktadır.
- bir liste herhangi bir şey içerebilir, çünkü veri geçersiz bir göstericidir,
void* - empty () veya size () gibi işlevler kolayca uygulanabilir
- tüm işlevler listeye bir işaretçi kullanır
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
ile ilgili:
void begin(node *head){
Değiştirildiğinde headyalnızca çağrı yığını "baş" değişir, gerekli olan, arayanın işlevinde "baş" ın gösterdiği yeri değiştirmektir. Bunu yapmak için, arayan kişinin 'baş' adresini iletmesi gerekir. "Baş" ın kendisi bir işaretçi olduğu gerçeği, yapılması gerekenlerin netliğine yardımcı olmaz,