Linear Meter adalah struktur linier, yang merupakan urutan terbatas yang memiliki elemen data tipe n (n ≥ 0) yang sama.
1. Array
Array memiliki batas atas dan bawah, dan unsur -unsur array terus menerus di batas atas dan bawah.
Diagram skematik dari array 10,20,30, 40, 50 50 adalah sebagai berikut:
Fitur Array : Data kontinu;
Array yang sedikit lebih rumit adalah array multidimensi dan array dinamis. Untuk bahasa C, array multidimensi juga direalisasikan melalui satu array -dimensi. Adapun array dinamis, ini adalah array dari kapasitas kelompok indeks yang dapat tumbuh secara dinamis; Vektor;
Kedua, daftar yang ditautkan -Daftar Tautan satu Jalan (Daftar Tertaut Tunggal) adalah jenis daftar tertaut.
Diagram skematik dari satu daftar tertaut adalah sebagai berikut:
Kepala kepala kosong, simpul penerus kepala adalah "simpul 10" (simpul data 10), dan simpul penerus "simpul 10" adalah "simpul 20" (data dengan data 10) ,. ..
Simpul hapus rantai tunggal
Hapus "Node 30"
Sebelum menghapus: simpul penerus "simpul 20" adalah "simpul 30", dan simpul penerus "simpul 30" adalah "Node 40".
Setelah menghapus: simpul penerus "simpul 20" adalah "Node 40".
Daftar tertaut tunggal ditambahkan node
Tambahkan "Node 15" antara "Node 10" dan "Node 20"
Sebelum menambahkan: simpul penerus "simpul 10" adalah "simpul 20".
Setelah menambahkan: simpul penerus "simpul 10" adalah "simpul 15", dan simpul penerus "simpul 15" adalah "simpul 20".
Karakteristik dari satu daftar tertaut adalah bahwa arah tautan node adalah satu jalan;
Ketiga, daftar tertaut dua arah
Daftar Tertaut Dua -Jalan (Daftar Tertaut Ganda) adalah jenis daftar tertaut. Seperti satu daftar tertaut, daftar rantai ganda juga terdiri dari node. Oleh karena itu, mulai dari node apa pun dalam daftar tertaut dua arah, Anda dapat dengan mudah mengakses node -node depan dan node berikutnya. Secara umum, kita semua membuat daftar tertaut melingkar dua arah.
Diagram skematik dari daftar dual yang ditautkan adalah sebagai berikut:
Header kosong, simpul penerus kepala adalah "simpul 10" (simpul data 10); Penerus Node adalah "Node 10"; .
Node hapus arloji rantai ganda
Hapus "Node 30"
Sebelum menghapus: simpul penerus "simpul 20" adalah "simpul 30", dan pre -node "simpul 30" adalah "node 20". Node penerus "simpul 30" adalah "node 40", dan pre -node "simpul 40" adalah "node 30".
Setelah menghapus: simpul penerus "simpul 20" adalah "node 40", dan pra -node "simpul 40" adalah "node 20".
Daftar tautan ganda Menambahkan node
Tambahkan "Node 15" antara "Node 10" dan "Node 20"
Sebelum menambahkan: simpul penerus "simpul 10" adalah "simpul 20", dan simpul "simpul 20" sebelumnya adalah "simpul 10".
Setelah menambahkan: simpul penerus "simpul 10" adalah "simpul 15", dan pre -node "simpul 15" adalah "simpul 10". Node penerus "simpul 15" adalah "node 20", dan simpul "simpul 20" sebelumnya adalah "node 15".
Implementasi daftar rantai ganda diperkenalkan di bawah ini, dan tiga implementasi C/C ++/Java diperkenalkan masing -masing.
1. C Menerapkan Daftar Tertaut Ganda
Implementasikan Kode Dua -Jalan Tautan Daftar (Double_link.h)
#IFNDEF_DOUBLE_LINK_H#DEFINE_DOUBLE_LINK_H // Buat "Dua Dua -Jalan Tingkat". Sukses, kembali ke kepala; Sukses, kembali 0; Kembali ke 1 untuk kekosongan; extern int dlink_is_empty (); Sukses, kembali ke pointer node; Extern void* dlink_get (indeks int); // Dapatkan "elemen pertama dalam daftar tertaut dua jalan". Sukses, kembali ke pointer node; Extern void* dlink_get_first (); Sukses, kembali ke pointer node; Extern void* dlink_get_last (); // masukkan "nilai" ke posisi indeks. Sukses, kembalikan 0; extern int dlink_insert (indeks int, void *pval); // masukkan "nilai" ke posisi kepala. Sukses, kembalikan 0; extern int dlink_insert_first (void *pval); // masukkan "nilai" ke posisi akhir. Sukses, kembalikan 0; extern int dlink_append_last (void *pval); Sukses, kembali 0; Sukses, kembali 0; Sukses, kembalikan 0;
Double_link.c dalam daftar tertaut dua arah
#include <stdio.h> #include <malloc.h>/*** C Lingle's Two -Way Linked Daftar dapat menyimpan data sewenang -wenang. ** @Author Skywang* @Tanggal 2013/11/07*/// Dua -Jalan Tautan Node Typedef Struct Tag_node {Stroct tag_node*prev; Perhatikan bahwa nilai kepala tidak menyimpan nilai elemen! Persimpangan Persimpangan Node statis *phead = null; // nomor simpul. Count int statis = 0; // Buat "node" baru. Sukses, kembali ke pointer node; Node statis *create_node (void *pval) {node *pnode = null; "); Return null;} // default, simpul pertama dan simpul terakhir titik pnode ke pnode-> prev = pnode-> next = pnode; // nilai node adalah pvalpnode-> p = PVAL; / Buat "Daftar Tertaut Dua Jalan". Sukses, kembalikan 0; int create_dlink () {// Buat header phead = create_node (null); Return count == 0;} // kembali ke "Dua -Jalan Tautan" int dlink_size () {return count;} // Dapatkan "node di posisi indeks dalam daftar dua -way yang tertaut" simpul statis* get_ node (node (indeks int) {ifx <0 || index> = count) {printf ("%s gagal! indeks keluar dari terikat!/n", __func __); if (index <= (count/2)) {int i = 0; pencarian j = 0; node "simpul statis * g et_first_node () () return get_node (0);} // Dapatkan simpul statis" node terakhir " * get_last_node () {return get_node (count-);} // Dapatkan" elemen posisi indeks) Dalam daftar tertaut dua arah ". Sukses, kembalikan nilai simpul; jika tidak, return -1. void * dlink_get (indeks int) {node * pindex = get_node (index); 1 个元素的值 ”batal* dlink_get_first () {return dlink_get (0);} // 获取“ 双向链表中最后 1 个元素的值 ”batal* dlink_get_last () {return dlink_get (count- 1);} // Masukkan "PVAL" ke posisi indeks. Sukses, kembalikan 0; int dlink_insert (indeks int, void * pval) {// Masukkan header if (index == 0) return dlink_insert_first (pvalt (pval); // dapatkan simpul yang sesuai dengan posisi yang akan dimasukkan; if (if (if (if (if (if (if (if (if (if (if (if if! pindex) return -1; // 创建 “节点” simpul *pnode = create_node (pval); if (! pnode) return -1; pnode-> prev = pindex-> prev; pnode-> next = pindex; pindex -> prev-> next = pnode; {node *pnod e = create_node (pval); ++; ; Way Linked List ". Sukses, kembalikan 0; int dlink_delete (int index) {node *pindex = get_node (index); > Next-> prev = pindex-> prev; pindex-> prev-> next = pindex-> next; free (pindex); count-; return 0;} // 删除第一个节点 int dlink_delete_first () {return dlink_delete (0);} // hapus node int dlink_delete_last () {return dlink_delete (count-);} // revisit "Daftar tertaut dua arah". Sukses, kembalikan 0; int dash_dlink () {if (! phead) {printf ("%s gagal! Dlink adalah null!/n", __func __); While (pnode! = Phead) {ptmp = pnode;Program Uji Daftar Tertaut Dua Jalan (dlink_test.c)
#include <stdio.h> #include "double_link.h"/*** C Bahasa untuk mengimplementasikan program uji daftar tertaut dua jalur. ** (01) int_test ()* Demonstrasi "int data" dalam daftar tertaut dua -jalur. * (02) String_Teest ()* Demonstrasi "Data Strine" dalam daftar tertaut dua jalur. * (03) Object_teest ()* Demonstrasi "objek" dalam daftar tertaut dua jalur. ** @Author Skywang* @Date 2013/11/07* /// DAFTAR TETAP DAFTAR OPERASI INT VOID INT_TEEST () {int iarr [4] = {10, 20, 30, 40}; n -----%s ------ ", __func __); create_dlink (); // Buat daftar tertaut dua arah dlink_insert (0, & iarr [0]); // Masukkan data dlink_insert (0, & & ig & & ig & & ig & & & 1]); // Masukkan data dlink_insert (0, & ig Igs [2]) ke header daftar ditautkan dua jalan; data printf ("dlink_is_empty () =%d/n", dlink_is_empty ()); Ukuran Dua -Jalan Terkait dari Dua -Jalan Tautan Int I; ) dlink_get (i); Dua puluh "," Tiga Puluh "," Fringf ("/n ----%s ----%s--/n", __func __); 0, Sarr [0]); // Masukkan data dlink_insert (0, Sarr [1]) ke header daftar tertaut dua arah; DAFTAR TEPAT -JAUH; n ", dlink_size ()); // Ukuran daftar tertaut dua jalur // cetak semua data int i dalam daftar tertaut dua -way; char *p; int sz = dlink_size (); untuk (i = 0; tag_stu {int id; {40, {40, {40, {40, "Dan"},};#define arr_stu_size ", __func __); create_dlink (); // Buat daftar tertaut dua jalur dlink_insert (0, & arr_stu [0] ); / Sisipkan Data DLink_insert (0, & arr_stu [1]) ke daftar tertaut dua -jalan ke daftar dua -link. "Dlink_is_empty () =%d/n", dlink_is_empl ()); Dua -way Linked Daftar // Semua data dalam daftar tertaut dua jalur int i; ) dlink_get (i); ); string_test (); // Demonstrasi "Data String" ke daftar tertaut dua jalan. Object_test (); // Demonstrasi "objek" dalam daftar tertaut dua -jalan. Mengembalikan 0;}Hasil berjalan
---- int_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = thirtydlink_get (1) = dua getydlink_get (2) = thirtydlink_get (1) = Twentdlink_get (2) = thirtydlink_get (1) = Twentdlink_get (thirtydlink- -Object_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = [30, vic] dlink_get (1) = [20, jody] dlink_get (2) = [10, Sky]
2. C ++ mewujudkan daftar rantai ganda
Implementasikan kode daftar daftar tertaut dua jalan (doubleLink.h)
; Sebelumnya, Next) {this-> value = t; size (); int delete_last (); ) {// Buat "kecepatan". Catatan: Tidak ada data penyimpanan di kepala! Phead = dnode baru <t> (); >: ~ DoughLink () {// Hapus semua node DNode <T>* ptmp; ; Daftar Rantai 为空 Templat <class t> int doublelink <t> :: is_empty () {return count == 0;} // 获取第 indeks 位置的节点 template <class t> dnode <t>* doublelink <t>: : get_node (indeks int) {// validitas parameter penilaian if (index <0 || index> = count) {cout << "Get node gagal! Indeks di Bound!" / Menemukan if (index <= count/ 2) {int i = 0; ;} / / Reverse Int J = 0; ; Temple <class t> trivelink <t> :: get_first () {return get_node (0)-> value;} // Dapatkan nilai node terakhir. Posisi indeks sebelum template <class t> int doublelink <t> :: insert (int index, t t) {ifx == 0) return insert_first (t) ;; > Sebelumnya); Template <class t> int doublelink <t> :: insert_fring (t) {dnode <t>* pnode = dnode baru <t> (t, phead-> next); > PNODE; > PNODE; > Next-> prev = pindex-> prev; pindex-> next = pindex-> next; T> int doublelink <t> :: delete_first () {return del (0);} // 删除最后一个节点 template <class t> int doublelink <t> :: delete_last () {return del (count-);} #EndifFile Uji Daftar Daftar Dua Jalan (dlinktest.cpp)
#include <ioStream> #include "doublelink.h" menggunakan namespace std; -"<< endl; // Buat daftar doublelink tertaut dua arah <int>* pdlink = doublelink baru <int> (); pdlink-> masukkan (0, 20); // Masukkan 20 ke posisi pertama pdlink- > append_last (10); "is_empty () =" << Pdlink-> is_empty () << endl; Endl; semua data int sz = pdlink-> ukuran (); get (i) << endl;} void string_test () {string sarr [4] = {"sepuluh", "dua puluh", "tiga puluh", "empat puluh"}; -"<< endl; elemen di Sarr ke dalam PDLink-> Append_Last (SARR [0]); Posisi // Apakah daftar ditautkan dua arah kosong << "is_empty () =" << Pdlink-> is_empty () << endl; = "<< pdlink-> ukuran () << endl; // semua data int sz = pdlink-> ukuran (); untuk (int i = 0; i <sz; i ++)" <") =" << Pdlink-> get (i) << endl;} struct stu {int id char [20];}; , {30, "vic"}, {40, "Dan"},};#define arr_stu_size cout << "/n ---- object_test ----" << endl; Daftar Doublelink <Stu>* pdlink = Doublelink baru <tu> (); (Arr_stu [0]); // Tambahkan elemen pertama di arr_stu ke elemen pertama ke ujung pdlink-> insert_fring (arr_stu [2 2 [2]; // masukkan elemen ketiga di arr_stu ke Posisi pertama // Apakah daftar ditautkan dua arah kosong << "is_empty () =" << Pdlink-> is_empty () << endl; <Pdlink-> ukuran () << endl; // cetak semua data int sz = pdlink-> -> get (i); ) {int_teest (); string_test (); // Demonstrasi "Data String" ke daftar tertaut dua jalan. Object_test (); // Demonstrasi "Objek" dalam daftar tertaut dua arah. Mengembalikan 0;}Deskripsi contoh
Dalam contoh di atas, saya meletakkan "pernyataan" dan "implementasi" dari daftar tertaut dua arah di file header. Spesifikasi pemrograman memperingatkan kami: Pisahkan deklarasi dan implementasi klaim, dan jumlah file header (file .h atau .hpp) hanya berisi pernyataan, dan bertanggung jawab atas implementasi dalam file implementasi (file .cpp)!
Jadi mengapa Anda melakukan ini? Ini karena dalam implementasi daftar tertaut dua arah, template diadopsi; dan kompiler C ++ tidak mendukung kompilasi template yang terpisah! Sederhananya, jika dinyatakan dalam Doublelink.h dan diimplementasikan di doublelink.cpp; ketika kita membuat objek Doublelink dalam kategori lain, kesalahan akan dikompilasi. Untuk alasan tertentu, Anda dapat merujuk pada "Mengapa Kompiler C ++ tidak dapat mendukung kompilasi templat yang terpisah".
Hasil berjalan
' = 3PDLink (0) = ThirdLink (1) = TwentyPdLink (2) = Ten ---- Object_test ---- Is_empty () = 0Size () = 3PDlink (0) = [30, VIC] PDLink (1) = [ 20 20, Jody] PDLink (2) = [10, Sky]
3. Java mewujudkan daftar rantai ganda
Implementasi Doublelink.java
/*** DUAIN DUA -JAVA TINGKAT. * CATATAN: Ada daftar tertaut dua jalan dalam paket koleksi Java. / Top headpate DNode <T> MEADE; {this.value = value; Catatan: Tidak ada data penyimpanan di kepala! Mhead = dnode baru <t> (null, null, null); Return mcount;} // Apakah daftar yang ditautkan adalah boolean kosong () {return mcount == 0;} // node private dnode <t> getNode (indeks int) {ifx) {index <0 || mcount) Lempar IndexOutOfBoundSException (); ;} // 反向查找 DNode <T> rnode = mhead.prev; int rindex = mcount - index -1; untuk (int j = 0; j <rindex; j ++) rnode = rnode. / Dapatkan nilai simpul posisi indeks. <t>, mhead, mhead.next); T> (t, inode.prev, inode); Public void InsertFirst (tt) {insert (0, t);} // Tambahkan node ke ujung daftar tertaut dari public void appendLast (t t) {dnode <T> DNode baru <T> (t, mhead. Prev mhead); .next = inode.Next; Node public void deleteLast () {del (mcount-);}}Program Uji (dlinktest.java)
/*** Dua Dua Java yang ditautkan. * CATATAN: Ada daftar tertaut dua arah dalam paket koleksi yang dilengkapi dengan java. Two-Way Table Operasi Int Private Static Void Int_teest () {int [] {10, 20, 30, 40}; = Doublelink baru <integer> (); Posisi pertama // Apakah daftar ditautkan dua jalan adalah System.out.printf ("isEmpty () =%b/n", dlink.isempty ()); d/n ", dlink.size ()); // cetak semua node untuk (int i = 0; i <dlink.size (); i ++) system.out .println (" dlink ("+i+") = "+dlink.get (i));} private static void string_test () {string [] sarr = {" sepuluh "," dua puluh "," tiga puluh "," empat puluh ""}; /n ---- string_test ---- "); // Buat daftar doublelink tertaut dua arah <string> dlink = doublelink baru <string> (); [1]); // Masukkan elemen kedua di SARR di SARR ke posisi pertama dlink.AppendLast (Sarr [0]); Posisi pertama // Apakah daftar ditautkan dua -way adalah System.out.printf ("isEmpty () =%b/ n", dlink.isempty ());// System.out.printf ("size () =%d/ n ", dlink.size ()); // cetak semua node untuk (int i = 0; i <dlink.size (); i ++) system.out.println (" dlink ("+i+ ") ="+dlink.get (i));} // Siswa kelas internal kelas statis {private string ID siswa (int id, string name) {this.id = id; ouVerridepublic string toString () {"+id+", "+name+"] ";} tudent [] studers = siswa baru [] {siswa baru (10," sky "), siswa baru (20," jody "), baru Siswa (30, "Vic"), siswa baru (40, "Dan"),}; DAFTAR TETAP DOUREKTIFT <Student> DLINK = Doublelink baru <spulhy> (); Elemen pertama pada siswa ke DLINK.InSertFirst (Siswa [Siswa [Siswa [Siswa [2]); printf ("isEmpty () =%b/n", dlink.isempty ()); node untuk (int i = 0; i <dlink.size ()); Static void main (string [] arts) {int_test (); string_test (); // Demonstrasi "Data String" ke daftar tertaut dua jalan. Object_test (); // Demonstrasi "objek" dalam daftar tertaut dua -jalan. }}Hasil berjalan
' 3DLink (0) = ThirtyDlink (1) = TwentyDlink (2) = Ten ---- Object_teest --- isempty () = falsaSize () = 3dlink (0) = [30, vic] dlink (1) = [20 20 , Jody] dlink (2) = [10, Sky]
Di atas adalah semua isi artikel ini.