[Powered by Google Translate] Proqramlaşdırma, biz tez-tez dəyərlərin siyahıları təmsil lazımdır belə bir bölmə tələbələrin adları kimi son viktorina və ya onların puanları. 

C dilində, diziler istifadə edilə bilər elan siyahıları saxlamaq üçün. Bu siyahı elementləri sadalamaq asandır bir sıra saxlanılır və siz daxil olmaq üçün lazımdır və ya İTH siyahısı element dəyişdirmək bəzi ixtiyari indeksi I, ki, daimi vaxt edilə bilər amma seriallarda də mənfi cəhətləri var. 

Biz onlara bəyan etdikdə, biz demək tələb edirik onlar necə böyük ön up, ki, onlar saxlaya bilərsiniz neçə elementlər edir və necə böyük bu elementlər, onların növü ilə müəyyən edilir. Məsələn, int Varış (10) 10 maddələr saxlaya bilərsiniz bir int həcmi var. 

Biz bəyannamə sonra bir sıra nin ölçüsünü dəyişə bilməz. Daha çox elementləri saxlamaq istəyirsinizsə, yeni bir sıra etmək lazımdır. Bu məhdudiyyət mövcuddur səbəbi bizim proqram bütün array saxlayan yaddaş bitişik yığın kimi. Bu bizim array saxlanılır yerləşir bufer demək. Digər dəyişənlərin ola bilər serialın hüququ yanında yaddaş, biz bilməz yalnız array böyük edir. 

Bəzən biz serialın sürətlə data çıxış sürəti ticarət istərdim bir az daha çox rahatlıq üçün. Də bağlı siyahısı, digər əsas məlumatlar strukturu daxil edin siz kimi tanış ola bilərsiniz. Yüksək səviyyədə, bir bağlı siyahı qovşaqlarının bir ardıcıllıqla data saklar ki, links ilə bir-birinə bağlı beləliklə adı 'bağlı siyahısı.' Dizayn biz görəcəksiniz ki, bu fərq müxtəlif üstünlükləri və mənfi cəhətləri gətirib çıxarır bir sıra çox. 

Burada integers çox sadə bağlıdır siyahısı üçün bir C kodu var. Biz hər node təmsil edən bilərsiniz 2 şeyi olan bir struct kimi siyahıda, "val" adlanan saxlamaq üçün bir tam Siyahıda növbəti node və link biz adlı göstərici kimi təmsil olan "Növbəti. Bu yolla biz bütün siyahısı izleyebilirsiniz 1-ci node yalnız bir göstərici ilə, və sonra biz növbəti göstəricilərinə edin 2-ci node, 3-cü node, 4-cü node, və s, biz siyahısına sonuna almaq qədər. 

Bu var 1 üstünlüyü bax edə bilər statik array strukturu üzərində - bir bağlı siyahısı ilə, biz ümumiyyətlə yaddaş böyük bir yığın ehtiyac yoxdur. Siyahısında 1-ci node, yaddaş bu yerdə yaşaya bilər və 2-ci node burada bütün yolu ola bilər. Yaddaş onlar Biz bütün qovşaqlarının heç məsələ əldə edə bilərsiniz çünki hər node növbəti pointer, 1-ci node başlayan tam sonrakı getmək üçün bizə deyir. 

Bundan əlavə, biz ön up Cavab yoxdur necə böyük bir bağlı siyahısı, biz statik serialların ilə yol olacaq biz siyahısına qovşaqlarının əlavə edə bilərsiniz ildən kimi uzun kosmik yeni qovşaqlarının üçün yaddaş yerdə var kimi. Buna görə də, bağlı siyahıları dinamik boyutlandır asandır. Sonra proqram daha çox qovşaqlarının əlavə etmək lazımdır De bizim siyahısına daxil. Tez bizim siyahısına yeni node daxil etmək üçün biz bütün ki, node üçün yaddaş ayrılması deyil məlumatların dəyəri Plop, biz müvafiq göstəricilərinə düzəliş istədiyiniz və sonra qoyun. 

Məsələn, biz arasında bir node yerləşdirmək istəyirdi siyahısında 2-ci və 3-cü qovşaqlarının,  biz bütün 2-ci və ya 3-cü qovşaqlarının hərəkət olmazdı. Biz bu qırmızı node daxil olduğunuz söyləyin. Biz istiyorum Bütün yeni node növbəti göstərici müəyyən edilir 3-cü node qeyd etmək və sonra 2-ci node növbəti pointer rewire bizim yeni node qeyd etmək. Belə ki, Tez bizim siyahıları boyutlandır bilər bizim kompüter endeksleme etibar etmir, əksinə onları saxlamaq göstəricilərinə istifadə birləşdirən haqqında. 

Lakin, bir dezavantaj bağlı siyahıları ki, statik bir sıra fərqli olaraq, kompüter yalnız siyahıda orta atlayamaz. Kompüter bağlı siyahıda hər node ziyarət ildən növbəti bir olmaq üçün, müəyyən bir node tapmaq üçün uzun olacaq bir sıra ki çox. Bütün siyahı proporsional vaxt vurduqdan sonra siyahısı uzunluğu, və ya O (n) asimptotik notation edir. Orta hesabla, hər node çatıb da vaxt n mütənasib edir. 

İndi həqiqətən bir kod yazmaq imkan ki, bağlı siyahıları ilə işləyir. Gəlin biz integers bir bağlı siyahı istəyirsiniz. Biz daha siyahısında node təmsil edə bilər 2 sahələri ilə bir struct kimi, "val" adlı tam dəyər və siyahıdan növbəti node növbəti göstərici. Bəli, kifayət qədər sadə görünür. 

Gəlin biz bir funksiyası yazmaq üçün demək olan hareket həyata siyahısını və baskı dəyər siyahısını son node saxlanılır. Yaxşı ki, biz siyahısına bütün qovşaqlarının axır lazımdır deməkdir son bir tapmaq, lakin biz əlavə deyilik ildən və ya bir şey silmə, biz dəyişmək istəmirəm Siyahıda növbəti göstəricilər daxili quruluşu. 

Belə ki, biz traversal üçün xüsusi bir pointer lazımdır olan biz browser. arayacaðým Bu siyahı bütün elementləri vasitəsilə tarama edəcək Növbəti göstəricilərinə silsiləsinin aşağıdakı. Biz saxlanılan bütün, 1-ci node bir göstəricisidir siyahısı və ya baş. 1-ci node rəhbəri xal. Bu tipli göstərici-to-node var. 

Siyahısına faktiki 1 node almaq üçün, biz dereference bu göstərici var biz bu dereference əvvəl, lakin biz yoxlamaq lazımdır İmleci ilk null olsun. Bu null varsa, siyahısı, boş və biz siyahısına boş ki, mesajı çap etməli son node yoxdur. Amma edək siyahısı boş deyil. O deyil, onda biz bütün siyahısını tarama olmalıdır biz siyahısının son node almaq qədər, və biz siyahısına son node at arıyorsanız necə deyə bilərsiniz? 

Yaxşı, bir node növbəti pointer null olduqda, biz sonunda olduğunu biliyorum son Növbəti göstərici qeyd etmək siyahısına heç bir sonrakı node olardı ildən. Bu həmişə null başlatılmış son node növbəti pointer saxlamaq üçün yaxşı təcrübə var biz siyahısına sonunda əldə etdiyiniz zaman bizə siqnallar bir standart əmlak var. 

Belə ki, browser → növbəti null olduqda, ok sintaksis dereferencing üçün qısa olduğunu unutmayın bir struct bir pointer, sonra daxil the yöndəmsiz bərabər növbəti sahəsində: (* Browser). Gələcək. Sonra biz, son node gördük biz browser → val çap etmək istəyirəm cari node olan dəyər olan biz son biridir. Əks halda, biz siyahısına son node hələ değilseniz, biz siyahıda növbəti node hərəkət etmək ki, son bir varsa və yoxlayın. Bunu etmək üçün, biz yalnız tarayıcımızın göstərici müəyyən cari node növbəti dəyər qeyd etmək, ki, siyahıda növbəti node edir. Bu müəyyən edilir browser = browser → Növbəti. Sonra, məsələn bir loop, bu prosesi təkrar Biz son node tapmaq qədər. Belə ki, məsələn, browser baş işarə edilib, biz browser → növbəti qeyd etmək browser müəyyən 1-ci node növbəti sahəsində eyni. Belə ki, indi bizim browser, 2-ci node işarə edir və yenə biz bir loop ilə təkrar Biz son node gördük qədər ki, edir burada node növbəti pointer null işarə edir. Və biz var biz siyahısına son node gördük və onun dəyəri çap etmək biz yalnız browser → val istifadə edin. 

Traversing belə pis deyil, amma nə daxil haqqında? Lets biz 4-cü mövqeyi bir tamsayı daxil istəyirlər bir tam siyahısı. Yəni cari 3-cü və 4-cü qovşaqlarının arasında. Yenə yalnız siyahısını axır var 3-cü element, biz sonra daxil olduğunuz bir almaq. Belə ki, biz siyahısını axır yenə Skaner bir pointer yaratmaq baş göstərici null varsa, yoxlamaq bu deyil, əgər, baş node bizim browser göstərici qeyd. Belə ki, 1-ci element da edirik. Biz əlavə edə bilərsiniz əvvəl 2 elementlər irəli getmək biz loop üçün istifadə edə bilərsiniz int i = 1; i <3; i + + və loop hər iteration-ci ildə, 1 node tərəfindən irəli tarayıcımızın göstərici inkişaf cari node növbəti sahəsində null əgər yoxlanılması ilə bu deyil, əgər, növbəti node tarayıcımızın pointer hərəkət cari node növbəti pointer üçün bərabər yaradılması. Belə ki, bizim üçün loop bunu deyir ildən iki dəfə, biz, 3-cü node ulaştınız və bir dəfə tarayıcımızın göstərici sonra node çatdı olan biz yeni tam daxil etmək istəyirəm necə faktiki daxil edə bilərəm? 

Bəli, bizim yeni tam siyahısına daxil edilməlidir öz node struct hissəsi kimi, Bu, həqiqətən qovşaqlarının bir ardıcıllıqla göstərir. Belə ki, in node yeni pointer edək "new_node" adlı və müəyyən indi ayırırlar yaddaş qeyd etmək node özü üçün yığın haqqında və biz ayırmağa nə qədər yaddaş lazımdır? Yaxşı, bir node ölçüsü, və biz daxil etmək istəyirəm ki, tam öz val sahəsində müəyyən etmək istəyirik. Gəlin 6, deyirlər. İndi node bizim tam dəyəri var. Bu yeni node növbəti sahəsində başlamaq üçün də yaxşı təcrübə deyil null qeyd etmək, lakin indi nə? 

Biz siyahısı daxili quruluşu dəyişdirmək üçün və növbəti göstəricilərinə siyahısı mövcud olan 3-cü və 4-cü qovşaqlarının. Növbəti göstəricilərinə siyahısı qaydada müəyyən edir, ildən və biz yeni node daxil olduğunuz ildən sağ siyahısı ortasına, bu bir az çətin ola bilər. Unutmayın, çünki bu bizim kompüter edir yalnız siyahıda qovşaqlarının yeri bilir Əvvəlki qovşaqlarının saxlanılır növbəti göstəricilərinə görə. Belə ki, biz heç, bu yerlərdə hər hansı track itirilmiş əgər bizim siyahıda növbəti göstəricilərinə biri dəyişən demək, Məsələn, biz dəyişdi demək 3-cü node növbəti sahəsində burada bəzi node qeyd etmək. Biz ki, çünki həyata uğurlar olarıq olduğu siyahısı qalan tapmaq üçün hər hansı bir fikir var və təbii ki, həqiqətən pis. Beləliklə, biz sifariş haqqında həqiqətən ehtiyatlı olmalıdır biz durub zamanı sonrakı işaretçileri manipulyasiya olan. 

Belə ki, bu sadələşdirmək üçün deyək ki, ilk 4 qovşaqlarının göstəricilərinə silsiləsinin təmsil oxları ilə, A, B, C, və D adlanır bu qovşaqlarının birləşdirən. Belə ki, biz yeni node daxil etməlisiniz qovşaqlarının C və D. arasında Bu hüquq üçün bunu tənqidi, və nə sizə göstərmək lazımdır. 

Ilk bunu səhv yol baxaq. Hey, biz yeni node C sonra sağ gəlmək var bilirik, belə C növbəti göstərici müəyyən edək new_node qeyd etmək. Bütün hüquqlar, tamam görünür, biz yalnız artıq bitirmək üçün D yeni node növbəti pointer point edilməsi, lakin gözləyin, necə ki, biz nə edə bilər? D olduğu bizə biləcək tək şey, növbəti pointer əvvəl, C saxlanılır edilmişdir lakin biz yalnız pointer rewrote yeni node qeyd etmək, biz artıq, D yaddaş olduğu hər hansı bir ipucu yoxdur və biz siyahısına qalan kaybettim. Bütün yaxşı. 

Beləliklə, biz bu hüququ necə etməliyəm? Birincisi, D., yeni node növbəti göstərici qeyd İndi həm yeni node və C növbəti göstəricilər Eyni node, D işarə edilir, lakin gözəl var. İndi biz yeni node C növbəti göstərici qeyd edə bilərsiniz. Belə ki, biz hər hansı bir məlumat itirmədən bu etdik. Kodu, C cari node edir bu traversal göstərici browser, işarə edir ki, və D, cari node növbəti sahədə işarə node tərəfindən təmsil olunur və ya browser → Növbəti. Beləliklə, biz ilk yeni node növbəti göstərici müəyyən browser → Növbəti qeyd etmək, biz new_node növbəti göstərici olmalıdır bildirib eyni şəkildə kopyanın D qeyd. Sonra biz cari node növbəti pointer bilərsiniz yeni node, biz rəsm new_node C qeyd gözləyin idi kimi. İndi hər şey üçün, və biz itirməmişdir hər hansı bir məlumat takip və biz yalnız bilmişlər siyahısı ortasında yeni node qalmaq bütün şey bərpa və ya hətta hər hansı elementləri dəyişkən olmadan yolu biz bir sabit uzunluğu sıra ilə bilərdi. 

Belə ki, bağlı siyahıları bir əsas, lakin mühüm, dinamik data strukturu var olan üstünlükləri və mənfi cəhətləri də var serialların və digər strukturları ilə müqayisədə kimi, tez-tez kompüter olduğu o, hər bir alət istifadə üçün zaman bilmək vacibdir belə doğru iş üçün doğru vasitə seçə bilərsiniz. 

Daha çox təcrübə üçün funksiyaları yazılı cəhd bir bağlı siyahı qovşaqlarının silmək - siz yenidən sıraya haqqında ehtiyatlı olun unutmayın Siz siyahısı yığın itirmək deyil ki, təmin etmək üçün sonrakı işaretçileri - və ya bağlı siyahısında qovşaqlarının saymaq bir funksiyası, bir bağlı siyahısında qovşaqlarının bütün üçün geri və ya bir əyləncə bir. 

My name Jackson Steinkamp, ​​bu CS50 edir.