C'de düğüm nedir?
Cs50 pset5 heceleyici üzerinde çalışıyorum ve derste düğüm adı verilen yeni bir şey tanıtıyorlar. Düğüm nedir? Videoda ne dediklerini gerçekten anlamadım. Google'da araştırmayı denediğimde, düğümün ne olduğunu açıklayan bazı siteler buldum, ancak gerçekten anlamadım. C konusunda yeniyim, bu yüzden 'kodlama kelimeleri' dediğim şeye alışkın değilim. Örneğin, bunu düğümlerle ilgili bir sitede buldum: Dinamik bir dizi, boyutu iki katına çıkararak genişletilebilir, ancak eski verilerin kopyalanması ve eski veri yapısıyla ilişkili hafızanın serbest bırakılması işlemiyle ilişkili ek yük vardır. Bunun ne anlama gelmesi gerekiyor? Lütfen bir düğümün ne olduğunu anlamama yardım edin, çünkü bunlar özellikle pset5 için önemli ve kullanışlı görünüyorlar. Düğümüm şu şekilde tanımlandı:
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
Burada, pset5 hecelemesine göz atan bağlantı: https://cs50.harvard.edu/x/2020/psets/5/speller/
Yanıtlar
Düğüm tek bir blok göstermek için kullanılan genel bir terimdir linked listve treeilgili veri yapıları ya da.
Düğüm olarak adlandırmak bir kuraldır, aksi takdirde herhangi bir adla çağırabilirsiniz.
Standart
C ++
struct node{
int data;
int *next;
};
veya Python'da
class Node:
def __init__(self, data, next= None):
self.data = data
self.next = next
Ama onu bir isimle arayabilirsin
Standart Değil
C ++
struct my_own_name{
int data;
int *nextptr;
};
veya python'da
class my_own_name:
def __init__(self, data, next=None):
self.data = data
self.next = next
Bir "düğüm", grafik teorisinden bir kavramdır. Bir grafik, düğümleri (köşeler) ve düğümleri birbirine bağlayan kenarlardan oluşur.
C'deki bir düğüm, bir grafiği uygulamak için "yerleşik" tüm gerekli veri öğelerine sahip bir yapı (a struct) olarak temsil edilebilir . İsteğe bağlı olarak, kenarları temsil eden bir yapı gerekli olabilir.
Misal:
typedef struct NODE {
int node_id;
struct EDGE *edgelist;
} tNode;
typedef struct EDGE {
tNode *from, *to;
struct EDGE *next;
} tEdge;
Not: "düğüm" terimi başka bağlamlarda da kullanılabilir, örneğin bir ikili ağacın düğümleri, bir listenin düğümleri vb.
Bir 'düğüm' bir C anahtar kelimesi değildir.
Bunun anlamı:
Dinamik bir dizi, boyutun iki katına çıkarılmasıyla genişletilebilir, ancak eski verilerin kopyalanması ve eski veri yapısıyla ilişkili hafızanın serbest bırakılması işlemiyle ilişkili ek yük vardır.
Dinamik ayırma, belleğin yığın üzerinde tahsis edildiği anlamına gelir . Ayrılan bellek alanının boyutu, statik bellek tahsisinde olduğu gibi bir derleme zaman sabiti olmak zorunda değildir ve bu nedenle, programın çalıştırılmasında daha sonra daha fazla bellek yeniden tahsis edilerek değiştirilebilir.
Genel gider , aynı işlemi yapmanın başka bir yoluna kıyasla bir işlem yapmanın ek maliyeti anlamına gelir . Bu durumda, dinamik dizinin boyutunun artırılması, gerekli toplam alanın doğrudan tahsis edilmesine kıyasla bir ek yüktür.
Ahmad'ın cevabını genişleterek, genellikle "düğümler" olarak adlandırılan öğelerden oluşturulmuş bir dizi veri yapısı vardır - her düğüm bir veya daha fazla başka düğüme bazı veriler ve bir tür referans (tipik olarak C ve C ++ 'da bir işaretçi) içerir. Tek bağlantılı bir liste için düğüm tanımı tipik olarak şöyle görünür:
struct node {
data_t data; // for some arbitrary data_t type
struct node *next;
};
Her düğüm aşağıdaki düğümün adresini içerir. Grafik bir temsil tipik olarak şöyle görünür:
+------+------+ +------+------+ +------+------+
| data | next |------->| data | next |----->| data | next |------|||
+------+------+ +------+------+ +------+------+
Ayrıca, her bir düğümün hem önceki hem de sonraki düğümleri gösterdiği çift bağlantılı listeye sahip olabilirsiniz:
struct node {
data_t data;
struct node *prev;
struct node *next;
};
Ve her düğümün sol ve sağ alt düğümleri gösterdiği ikili ağaçlar vardır:
struct node {
data_t data;
struct node *left;
struct node *right;
};
"Düğüm" teriminin kullanımı yalnızca yaygın bir adlandırma kuralından ibarettir.
Dinamik bir dizi, boyutun iki katına çıkarılmasıyla genişletilebilir, ancak eski verilerin kopyalanması ve eski veri yapısıyla ilişkili belleğin serbest bırakılması işlemiyle ilişkili ek yük vardır. Bunun ne anlama gelmesi gerekiyor?
reallocKütüphane işlevini kullanarak dinamik olarak ayrılmış bir tamponu yeniden boyutlandırabilirsiniz . Örneğin, dizeyi depolamak için dinamik olarak bir tampon ayırmak istediğimizi varsayalım "foo". Şöyle bir şey yazardık:
size_t bufsize = 4;
char *buffer = malloc( bufsize );
if ( buffer )
strcpy( buffer, "foo" );
Gelen adresin mallocşu olduğunu hayal edeceğiz 0x1000:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
Şimdi, dize eklemek istediğiniz varsayalım "bar"için "foo". Bunu yapmak için yeterince büyük bir tampon ayırmadık, bu yüzden reallockütüphane işlevini kullanarak yeniden boyutlandırmamız gerekiyor :
char *tmp = realloc( buffer, bufsize * 2 ); // double the buffer size
if ( tmp )
{
buffer = tmp;
bufsize *= 2;
strcat( buffer, "bar" );
}
else
{
// could not extend buffer, handle as appropriate
}
Şimdi, eğer mümkünse, reallocsadece mevcut arabelleği takip eden alanı kapacaktır, dolayısıyla bu kodun sonucu şu olacaktır:
+---+---+---+---+
0x1000: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1004: |'a'|'r'| 0 | ? |
+---+---+---+---+
... ... ... ...
Ancak, adresindeki bellek 0x1004zaten başka bir şey için ayrılmışsa, bunu yapamayız. farklı bir adreste yeni bir arabellek atamak ve mevcut arabelleğin içeriğini ona kopyalamak, ardından orijinal arabelleği serbest reallocbırakmak zorunda kalacak . Yeterince büyük olan ilk boş alan bölgesinin şu noktadan başladığını hayal edeceğiz :0x100c
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: | ? | ? | ? | ? |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
Öyleyse realloc, önce 8 baytı 0x100cayırmalı, ardından mevcut tamponun içeriğini bu yeni alana kopyalamalıdır:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
ve son olarak adresindeki alanı serbest bırakın 0x1000. "bar"Bu yeni tampona ekleyerek bize şunları veriyoruz:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 | // free'd memory is not overwritten
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1010: |'a'|'r'| 0 | ? |
+---+---+---+---+
Eğer reallocisteğini karşılamak için yeterince büyük bir bölgeyi bulamıyorum, bu dönecektir NULLve yerinde geçerli tampon bırakın. Bu nedenle, dönüş değerini reallocfarklı bir işaretçi değişkenine atarız - eğer onu NULLgeri bufferatarsak, orijinal tampona erişimimizi kaybederiz.