Apakah struktur data komputer?

Struktur data ialah cara komputer menyimpan dan menyusun data Ia merujuk kepada koleksi elemen data yang mempunyai satu atau lebih hubungan khusus antara satu sama lain; ia mengkaji struktur logik data dan struktur fizikal data. Saling hubungan antara mereka, tentukan operasi yang sesuai untuk struktur ini, reka bentuk algoritma yang sepadan, dan pastikan struktur baharu yang diperoleh selepas operasi ini masih mengekalkan jenis struktur asal.

Persekitaran pengendalian tutorial ini: sistem Windows 7, komputer Dell G3.

Struktur data

Struktur data ialah cara komputer menyimpan dan menyusun data. Struktur data merujuk kepada koleksi elemen data yang mempunyai satu atau lebih hubungan khusus antara satu sama lain. Selalunya, struktur data yang dipilih dengan teliti boleh membawa kepada kecekapan pengendalian atau penyimpanan yang lebih tinggi. Struktur data selalunya berkaitan dengan algoritma perolehan semula yang cekap dan teknik pengindeksan.

Definasi kata nama

Struktur data merujuk kepada himpunan elemen data yang mempunyai satu atau lebih hubungan antara satu sama lain dan hubungan antara elemen data dalam koleksi Hubungan antara mereka. Ditandakan sebagai:
Data_Structure=(D,R)
di mana D ialah set elemen data dan R ialah set terhingga perhubungan antara semua elemen dalam set.

(1) Struktur yang biasa digunakan

1. Tatasusunan: Dalam pengaturcaraan, untuk kemudahan pemprosesan, kumpulan daripada jenis yang sama adalah Beberapa pembolehubah disusun dalam bentuk tertib. Pengumpulan elemen data serupa yang disusun mengikut susunan dipanggil tatasusunan. Dalam bahasa C, tatasusunan dibina jenis data. Tatasusunan boleh diuraikan kepada berbilang elemen tatasusunan, yang boleh menjadi jenis data asas atau jenis yang dibina. Oleh itu, mengikut jenis elemen tatasusunan, tatasusunan boleh dibahagikan kepada pelbagai kategori seperti tatasusunan berangka, tatasusunan aksara, tatasusunan penunjuk dan tatasusunan struktur.

2. Timbunan: Ia adalah senarai linear khas yang hanya boleh disisipkan dan dipadamkan pada satu hujung. Ia menyimpan data mengikut prinsip masuk pertama, keluar terakhir Data yang masuk dahulu ditolak ke bahagian bawah tindanan, dan data terakhir berada di bahagian atas tindanan Apabila data perlu dibaca, data akan muncul dari bahagian atas timbunan (data terakhir dibacakan dahulu).

3. Baris Gilir: Jadual linear khas yang hanya membenarkan operasi pemadaman di hujung hadapan jadual (depan) dan operasi sisipan di hujung belakang (belakang) jadual. Penghujung yang melakukan operasi sisipan dipanggil ekor baris gilir, dan penghujung yang melakukan operasi pemadaman dipanggil ketua baris gilir. Baris gilir menyusun data mengikut prinsip "masuk dahulu, keluar dahulu" atau "masuk terakhir, keluar terakhir". Apabila tiada elemen dalam baris gilir, ia dipanggil baris gilir kosong.

4. Senarai terpaut: Ia adalah struktur storan tidak berterusan dan tidak berurutan pada unit storan fizikal Ia boleh mewakili sama ada struktur linear atau struktur bukan linear melalui senarai terpaut Susunan pautan penunjuk dalam . Senarai terpaut terdiri daripada satu siri nod (setiap elemen dalam senarai terpaut dipanggil nod), dan nod boleh dijana secara dinamik pada masa jalan. Setiap nod terdiri daripada dua bahagian: satu ialah medan data yang menyimpan elemen data, dan satu lagi ialah medan penunjuk yang menyimpan alamat nod seterusnya.

5. Pokok: Ia ialah set terhingga K yang mengandungi n (n>0) nod dan hubungan N ditakrifkan dalam K. N memenuhi syarat berikut:

( 1) Terdapat dan hanya satu nod K0, yang tidak mempunyai pendahulu untuk hubungan N. K0 dipanggil nod akar pokok. Dirujuk sebagai akar.

(2) Kecuali K0, setiap nod dalam K mempunyai dan hanya mempunyai satu pendahulu untuk hubungan N.

(3) Setiap nod dalam K boleh mempunyai m pengganti (m>=0) untuk hubungan N.

6 Graf: Ia terdiri daripada set terhingga V nod dan set E tepi. Antaranya, untuk membezakannya daripada struktur pokok, nod sering dipanggil bucu dalam struktur graf, dan tepi disusun pasangan bucu Jika terdapat tepi di antara dua bucu, ia bermakna kedua-dua bucu mempunyai hubungan bersebelahan.

7 Heap: Dalam sains komputer, heap ialah struktur data pokok khas, setiap nod mempunyai nilai. Biasanya apa yang kita panggil struktur data timbunan merujuk kepada timbunan binari. Ciri timbunan ialah nod akar mempunyai nilai terkecil (atau terbesar), dan dua subpokok nod akar juga merupakan timbunan.

8. Jadual cincang (jadual cincang, juga dipanggil jadual cincang): Jika terdapat rekod dengan kunci bersamaan dengan K dalam struktur, ia mesti berada di lokasi penyimpanan f(K). Oleh itu, rekod yang dicari boleh diperolehi terus tanpa perbandingan. Surat-menyurat f ini dipanggil fungsi cincang (fungsi Hash), dan jadual yang dibina berdasarkan idea ini ialah jadual cincang.

9. Lapan algoritma pengisihan: Algoritma pengisihan boleh dibahagikan kepada pengisihan dalaman dan pengisihan luaran ialah rekod data diisih dalam ingatan, manakala pengisihan luaran adalah kerana data yang diisih adalah sangat besar dan tidak boleh ditampung. Semua rekod pengisihan memerlukan akses kepada storan luaran semasa proses pengisihan. Algoritma pengisihan dalaman yang biasa termasuk: isihan sisipan, isihan bukit, isihan pemilihan, isihan gelembung, isihan gabungan, isihan pantas, isihan timbunan, isihan radix, dsb.

1. Struktur logik data : merujuk kepada struktur data yang mencerminkan hubungan logik antara elemen data Hubungan logik merujuk kepada hubungan sebelum dan selepas antara elemen data, dan ia berkaitan dengan komputer Lokasi penyimpanan tidak relevan.

Struktur logik termasuk:

1) Set
Tiada perhubungan lain antara elemen dalam struktur data kecuali ia "kepunyaan set yang sama"; 🎜 >2) Struktur linear

Unsur-unsur dalam struktur data mempunyai hubungan satu-dengan-satu; hubungan;

4) Struktur graf

Elemen dalam struktur data mempunyai hubungan banyak-ke-banyak.

2. Struktur fizikal data:

merujuk kepada bentuk storan struktur logik data dalam ruang storan komputer.

Struktur fizikal data ialah perwakilan struktur data dalam komputer (juga dikenali sebagai imej), yang merangkumi perwakilan dalam mesin bagi elemen data dan perwakilan dalam mesin bagi perhubungan. Memandangkan kaedah pelaksanaan khusus termasuk urutan, memaut, pengindeksan, pencincangan, dsb., struktur data boleh dinyatakan sebagai satu atau lebih struktur storan.

Perwakilan dalam mesin bagi elemen data (kaedah pemetaan): Elemen data diwakili oleh rentetan bit bit binari. Rentetan bit ini biasanya dipanggil nod. Apabila elemen data terdiri daripada beberapa item data, rentetan sub-bit yang sepadan dengan setiap item data dalam rentetan bit dipanggil medan data. Oleh itu, nod ialah perwakilan dalam mesin (atau imej dalam mesin) bagi elemen data. Perwakilan pada mesin bagi perhubungan (kaedah pemetaan): Perwakilan pada mesin bagi perhubungan antara elemen data boleh dibahagikan kepada imej berjujukan dan imej bukan berjujukan Terdapat dua struktur storan yang biasa digunakan: struktur storan berjujukan dan struktur storan rantai. Peta berjujukan mewakili hubungan logik antara elemen data melalui kedudukan relatifnya dalam ingatan. Imej tidak berurutan mewakili hubungan logik antara elemen data dengan bantuan penunjuk yang menunjukkan lokasi penyimpanan elemen.

3. Operasi struktur data

Secara amnya dipercayai bahawa struktur data disusun oleh elemen data mengikut beberapa sambungan logik daripada. Perihalan hubungan logik antara elemen data dipanggil struktur logik data mesti disimpan dalam komputer, dan struktur penyimpanan data adalah bentuk pelaksanaan struktur data dan perwakilannya dalam komputer; apabila membincangkan struktur data, kita juga mesti membincangkan Operasi yang dilakukan pada jenis data ini adalah bermakna. Struktur data logik boleh mempunyai berbilang struktur storan, dan pelbagai struktur storan mempengaruhi kecekapan pemprosesan data.

Dalam reka bentuk pelbagai jenis program, pilihan struktur data adalah pertimbangan reka bentuk asas. Pengalaman pembinaan banyak sistem berskala besar menunjukkan bahawa kesukaran pelaksanaan sistem dan kualiti pembinaan sistem sangat bergantung kepada sama ada struktur data optimum dipilih. Banyak kali, sebaik sahaja struktur data ditentukan, algoritma mudah didapati. Kadangkala keadaan menjadi sebaliknya, dan kami memilih struktur data agar sesuai dengan algoritma tertentu. Dalam kedua-dua kes, memilih struktur data yang sesuai adalah sangat penting.
Selepas memilih struktur data, algoritma juga ditentukan Data, bukan algoritma, adalah faktor utama dalam pembinaan sistem. Wawasan ini telah membawa kepada kemunculan banyak kaedah reka bentuk perisian dan bahasa pengaturcaraan, dan bahasa pengaturcaraan berorientasikan objek adalah salah satu daripadanya.
Apabila komputer menyelesaikan masalah tertentu, ia secara amnya perlu melalui langkah berikut: Pertama, ia mesti mengabstrak model matematik yang sesuai daripada masalah khusus, kemudian mereka bentuk algoritma (Algoritma) untuk menyelesaikan model matematik, dan akhirnya susun atur cara Uji dan tweak sehingga anda mendapat jawapan akhir.
Intipati mencari model matematik adalah untuk menganalisis masalah, mengekstrak objek operasi, mengetahui hubungan antara objek operasi ini, dan kemudian menerangkannya dalam bahasa matematik. Apabila orang menggunakan komputer untuk menangani masalah pengiraan berangka, model matematik yang digunakan diterangkan oleh persamaan matematik. Operan yang terlibat secara amnya adalah data integer mudah, nyata dan logik, jadi tumpuan utama pengaturcara adalah pada kemahiran pengaturcaraan dan bukannya penyimpanan dan organisasi data. Walau bagaimanapun, lebih banyak bidang aplikasi komputer adalah "masalah pengkomputeran bukan berangka". Model matematik masalah berangka diterangkan oleh struktur seperti jadual linear, pepohon, dan graf.
Algoritma komputer berkait rapat dengan struktur data, semuanya bergantung pada struktur data tertentu. Operasi diselesaikan oleh komputer, yang memerlukan reka bentuk algoritma sisipan, pemadaman dan pengubahsuaian yang sepadan. Dalam erti kata lain, struktur data juga perlu memberikan algoritma untuk pelbagai operasi yang ditakrifkan oleh setiap jenis struktur. Objek data ialah koleksi elemen data dengan sifat yang sama dan merupakan subset data. Objek data boleh menjadi terhingga atau tidak terhingga. Pemprosesan data merujuk kepada proses operasi mencari, memasukkan, memadam, menggabungkan, menyusun, statistik dan pengiraan mudah pada data.

(2) Klasifikasi struktur

Struktur data merujuk kepada hubungan antara elemen data dalam kelas elemen data yang sama. Struktur data ialah struktur logik, struktur storan (struktur fizikal) dan operasi data. Struktur logik data ialah model matematik yang diabstrakkan daripada masalah tertentu Ia menerangkan ciri-ciri matematik unsur-unsur data dan hubungannya Kadang-kadang struktur logik hanya dirujuk sebagai struktur data. Struktur logik ialah imej dalam storan komputer, ditakrifkan secara rasmi sebagai (K, R) (atau (D, S)), di mana K ialah set terhingga elemen data dan R ialah set terhingga hubungan pada K.

Menurut ciri-ciri berbeza perhubungan antara elemen data, biasanya terdapat empat jenis struktur asas berikut:

⑴ Tetapkan struktur. Hubungan antara elemen data struktur ini adalah "kepunyaan set yang sama".

⑵Struktur linear. Terdapat hubungan satu dengan satu antara elemen data struktur ini.

⑶Struktur pokok. Terdapat hubungan satu dengan banyak antara elemen data struktur ini

⑷Struktur grafik. Terdapat hubungan banyak-ke-banyak antara elemen data struktur ini, juga dipanggil struktur rangkaian. Daripada konsep struktur data yang diperkenalkan di atas, kita dapat mengetahui bahawa struktur data mempunyai dua elemen. Satu ialah himpunan elemen data dan satu lagi ialah himpunan perhubungan. Secara formal, struktur data biasanya boleh diwakili oleh tupel.

Bentuk struktur data ditakrifkan sebagai: struktur data ialah tuple: Data_Structure=(D, R), dengan D ialah set terhingga elemen data dan R ialah set terhingga hubungan pada D. Ciri struktur linear ialah terdapat hubungan linear antara elemen data, dan elemen data "disusun satu demi satu." Jenis elemen data dalam jadual linear adalah sama, atau jadual linear ialah struktur linear yang terdiri daripada elemen data jenis yang sama. Terdapat banyak contoh jadual linear dalam masalah praktikal Contohnya, jadual maklumat status pelajar ialah jadual linear: jenis elemen data dalam jadual adalah jenis pelajar juga adalah jadual linear elemen dalam jadual adalah jenis aksara dll.
Jadual linear ialah struktur linear yang paling mudah, paling asas dan paling biasa digunakan. Jadual linear ialah jujukan terhingga bagi n (n>=0) elemen data dengan jenis data yang sama, biasanya direkodkan sebagai: (a1, a2,... ai-1, ai, ai 1,...an), di mana n ialah panjang jadual , apabila n=0 ia dipanggil senarai kosong. Ia mempunyai dua kaedah penyimpanan: storan berurutan dan storan rantaian operasi asas utamanya ialah memasukkan, memadam dan mendapatkan semula.

Perwakilan (imej) struktur data dalam komputer dipanggil struktur fizikal (storan) data. Ia termasuk perwakilan elemen data dan perwakilan perhubungan. Terdapat dua kaedah perwakilan yang berbeza bagi perhubungan antara elemen data: pemetaan berjujukan dan pemetaan bukan berjujukan, dan dengan itu dua struktur storan berbeza diperoleh: struktur storan berjujukan dan struktur storan rantai.

Kaedah storan berjujukan: Ia menyimpan nod bersebelahan secara logik dalam unit storan bersebelahan secara fizikal Hubungan logik antara nod dicerminkan oleh hubungan bersebelahan unit storan. Struktur storan berjujukan ialah kaedah perwakilan storan yang paling asas, biasanya dilaksanakan dengan bantuan tatasusunan dalam bahasa pengaturcaraan.

Kaedah penyimpanan pautan: Ia tidak memerlukan nod bersebelahan secara logik juga bersebelahan secara fizikal Hubungan logik antara nod diwakili oleh medan penunjuk tambahan. Perwakilan storan yang terhasil dipanggil struktur storan rantai Struktur storan rantai biasanya dilaksanakan dengan bantuan jenis penunjuk dalam bahasa pengaturcaraan

Kaedah penyimpanan indeks: Selain mewujudkan maklumat nod storan, jadual Indeks tambahan untuk. mengenal pasti alamat nod.

Kaedah storan cincang: Alamat storan nod dikira terus berdasarkan kata kunci nod.

Dalam struktur data, secara logik (struktur logik: hubungan logik antara elemen data), struktur data boleh dibahagikan kepada struktur linear dan struktur bukan linear. Struktur storan berjujukan bagi struktur linear ialah struktur storan capaian berjujukan, dan struktur storan terpaut bagi senarai linear ialah struktur storan capaian rawak. Jika jadual linear diwakili oleh storan rantai, alamat unit storan antara semua nod boleh berterusan atau tidak berterusan. Struktur logik tidak ada kaitan dengan bentuk, kandungan, kedudukan relatif atau bilangan nod yang terkandung dalam elemen data itu sendiri.

(3) Algoritma struktur

Reka bentuk algoritma bergantung pada struktur data (logik), dan pelaksanaan algoritma bergantung pada struktur simpanan yang digunakan. Struktur penyimpanan data pada asasnya adalah merealisasikan struktur logiknya dalam ingatan komputer Untuk menggambarkan secara menyeluruh struktur logik data, imejnya dalam ingatan merangkumi dua aspek, iaitu maklumat antara elemen data dan elemen data antara. Struktur data yang berbeza mempunyai operasi yang sepadan. Operasi data ialah algoritma operasi yang ditakrifkan pada struktur logik data, seperti pengambilan semula, penyisipan, pemadaman, kemas kini dan pengisihan.

Struktur data adalah berbeza daripada jenis data dan objek data Ia bukan sahaja menerangkan objek data jenis data, tetapi juga menerangkan hubungan antara elemen objek data.

Jenis data ialah koleksi nilai dan satu set operasi yang ditakrifkan pada set nilai ini. Jenis data boleh dibahagikan kepada dua kategori: jenis atom dan jenis struktur. Di satu pihak, dalam bahasa pengaturcaraan, setiap data tergolong dalam jenis data tertentu. Jenis secara eksplisit atau tersirat menentukan julat nilai data, cara ia disimpan dan operasi yang dibenarkan. Ia boleh dianggap bahawa jenis data adalah struktur data yang telah dilaksanakan dalam pengaturcaraan. Sebaliknya, semasa proses pengaturcaraan, apabila struktur data baharu perlu diperkenalkan, struktur penyimpanan data sentiasa diterangkan dengan bantuan jenis data yang disediakan oleh bahasa pengaturcaraan. Unit data terkecil yang diwakili dalam komputer ialah satu bit nombor binari, dipanggil bit. Kami menggunakan rentetan bit yang dibentuk oleh gabungan beberapa bit untuk mewakili elemen data Rentetan bit ini biasanya dipanggil elemen atau nod. Apabila elemen data terdiri daripada beberapa item data, rentetan sub-bit yang sepadan dengan setiap item data dalam rentetan bit dipanggil medan data. Elemen atau nod boleh dianggap sebagai imej elemen data dalam komputer.

Rangka kerja sistem perisian harus dibina berdasarkan data, bukan pada operasi. Modul perisian yang mengandungi jenis data abstrak harus mengandungi tiga bahagian: definisi, perwakilan dan pelaksanaan.

Untuk setiap struktur data, mesti ada satu set operasi yang berkait rapat dengannya. Jika jenis dan bilangan operasi berbeza, walaupun struktur logiknya sama, struktur data boleh memainkan peranan yang berbeza.

Struktur data yang berbeza mempunyai set operasi yang berbeza, tetapi operasi berikut amat diperlukan:

1 Penjanaan struktur
2. Pemusnahan struktur ;
3. Cari elemen data yang memenuhi syarat yang ditetapkan dalam struktur; 4. Masukkan elemen data baru ke dalam struktur;


Jenis data abstrak: model matematik dan satu set operasi yang ditakrifkan pada model. Jenis data abstrak sebenarnya adalah takrifan struktur data ini. Kerana ia mentakrifkan struktur logik data dan satu set algoritma pada struktur ini. Jenis data abstrak boleh diwakili oleh triplet berikut: (D, S, P). D ialah objek data, S ialah set perhubungan pada D, dan P ialah set operasi asas pada D. Takrifan ADT ialah: Nama jenis data abstrak ADT: {objek data: (set elemen data), hubungan data: (gabungan tuple hubungan data), operasi asas: (senarai fungsi operasi)}; Jenis data abstrak mempunyai dua ciri penting:

Abstraksi data: Apabila menggunakan ADT untuk menerangkan entiti yang diproses oleh atur cara, penekanan adalah pada ciri pentingnya, fungsi yang boleh dilengkapkan dan antara mukanya dengan pengguna luar ( iaitu cara dunia luar menggunakannya).

Enkapsulasi data: Asingkan ciri luaran entiti daripada butiran pelaksanaan dalamannya dan sembunyikan butiran pelaksanaan dalamannya daripada pengguna luaran.

Data ialah pembawa maklumat, yang boleh dikenali, disimpan dan diproses oleh komputer. Ia adalah bahan mentah yang diproses oleh program komputer, dan aplikasi memproses semua jenis data. Dalam sains komputer, data yang dipanggil adalah objek pemprosesan komputer Ia boleh menjadi data berangka atau data bukan angka. Data berangka ialah beberapa integer, nombor nyata atau nombor kompleks, terutamanya digunakan dalam pengiraan kejuruteraan, pengiraan saintifik dan data bukan angka termasuk aksara, teks, grafik, imej, suara, dsb.

Elemen Data ialah unit asas data. Di bawah keadaan yang berbeza, elemen data juga boleh dipanggil elemen, nod, bucu, rekod, dll. Sebagai contoh, rekod dalam jadual maklumat pelajar dalam sistem pencarian maklumat pelajar dipanggil elemen data. Kadangkala, elemen data boleh terdiri daripada beberapa item data Contohnya, setiap elemen data dalam jadual maklumat pelajar dalam sistem pengurusan status pelajar adalah rekod pelajar. Ia termasuk item data seperti nombor pelajar, nama, jantina, tempat asal, tarikh lahir dan gred. Item data ini boleh dibahagikan kepada dua jenis: satu dipanggil item asas, seperti jantina pelajar, tempat asal, dll. Item data ini adalah unit terkecil yang tidak boleh dibahagikan semasa pemprosesan data; seperti gred pelajar Ia boleh dibahagikan kepada istilah yang lebih kecil seperti matematik, fizik, kimia, dll. Lazimnya, setiap rekod pelajar diakses dan diproses sebagai unit asas apabila menyelesaikan masalah aplikasi praktikal.

Objek Data atau Kelas Elemen Data ialah koleksi elemen data dengan sifat yang sama. Dalam masalah tertentu, semua elemen data mempunyai sifat yang sama (nilai elemen tidak semestinya sama), tergolong dalam objek data yang sama (kelas elemen data), dan elemen data adalah contoh kelas elemen data. Sebagai contoh, dalam rangkaian trafik sistem nasihat trafik, semua bucu ialah kelas elemen data Pucuk A dan puncak B masing-masing mewakili bandar dan merupakan dua contoh kelas elemen datanya ialah A dan B. Struktur data merujuk kepada koleksi elemen data yang mempunyai satu atau lebih hubungan antara satu sama lain. Dalam sebarang masalah, elemen data tidak diasingkan Terdapat hubungan satu jenis atau lain di antara mereka Hubungan antara elemen data dipanggil struktur.

Untuk lebih banyak pengetahuan berkaitan, sila lawati ruangan
Soalan Lazim

!

Atas ialah kandungan terperinci Apakah struktur data komputer?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!