什麼是資料結構
1、資料
資料是描述客觀世界的數字、字元以及一切能夠輸入到計算機中,并且能夠被計算機程式處理的符号集合。簡言之,資料就是計算機加工處理的原料,是資訊的載體。
2、資料元素
資料元素是能夠獨立、完整地描述問題世界中的實體的最小機關,它是資料這個集合中的一個一個的元素,資料元素也成為資料結點,或者簡稱結點
3、資料對象
一個資料對象被定義為具有相同性質的資料元素的集合。
4、結構
資料元素之間必然存在着某種聯系,這種聯系稱為結構。人們不僅要考慮到資料的這種結構,而且還要考慮到将要施加于資料上的各種操作及其種類。從這個意義上來說,資料元素是具有結構的資料元素的集合。
這裡也可以給資料結構一個形式化的描述。資料結構是一個二進制組Data-Structure=(D,R),其中,D是資料元素的有限集合,R是D上關系的集合。
上述定義中的"關系"通常是指資料元素之間的邏輯關系,也稱為資料的邏輯結構。通常把資料結構在計算機中的表示稱為資料的實體結構。實體結構又稱存儲結構,包括資料元素的表示以及關系的表示兩個方面。資料的邏輯結構與存儲結構是密不可分的兩個方面,一個算法的設計取決于標明的邏輯結構,而算法的實作則依賴于采用的存儲結構。
資料結構是互相之間存在一種或者多種特定關系的資料元素的集合。資料結構包括三方面的内容:邏輯結構,存儲結構和資料的運算。資料的邏輯結構和存儲結構是密不可分的兩個方面,一個算法的設計取決于所標明的邏輯結構,而算法的實作取決于所標明的存儲結構。
資料的存儲結構主要有:順序存儲結構、鍊式存儲結構、索引存儲結構和散列存儲結構。
1、順序存儲結構:順序存儲結構的優點是簡單,易了解,并且實際占用最少的存儲空間;缺點是需要占用一片位址連續的整塊空間,并且存儲配置設定要實作進行;另外,對于一些操作的時間效率較低也是這種存儲結構的主要缺陷之一。
2、鍊式存儲結構:鍊式存儲結構是指在計算機存儲器中用一片位址任意的(連續的或者不連續的)存放資料元素的資訊,一般稱每個資料元素占用的若幹存儲單元的組合作為一個鍊結點。每個鍊結點中不僅要存放一個資料元素的元素資訊,還要存放一個指出這個元素在邏輯關系中的直接後繼元素所在鍊結點的位址,該位址被稱為指針。這就是說,資料元素之間的邏輯關系通過指針間接地反映。由于不要求存儲空間位址連續,是以,邏輯上相鄰的資料元素在實體上不一定相鄰。這種存儲結構的優點是存儲空間不必事先配置設定,在需要存儲空間時可以臨時申請,不會造成存儲空間的浪費。像插入和删除這樣操作的時間效率采用鍊式存儲結構遠比采用順序存儲結構要高。但是在這種情況中,不僅資料元素本身的資料資訊需要占用存儲空間,而且指針也有存儲空間的開銷,是以,從這一點來說,鍊式存儲結構要比順序存儲結構的空間開銷大。
3、索引結構是利用資料元素的索引關系來确定資料元素的存放位置的一種存儲結構,它是由資料元素本身的資料資訊以及索引表兩個部分組成的。
4、散列結構是由事先構造的散列函數關系及處理沖突的方法來确定資料元素在散清單中的位置。
1、資料的邏輯結構:邏輯結構是指資料元素之間的邏輯關系,即在邏輯上描述資料,它與資料的存儲無關,是獨立于計算機的,資料的邏輯結構分為線性結構和非線性結構,線性表是典型的線性結構;集合,樹,圖是典型的非線性結構。
2、資料的存儲結構:存儲結構是指資料結構在計算機中的表示(又稱實體結構)。它包括資料元素的表示和關系的表示。資料的存儲結構是邏輯結構用計算機語言的實作。資料的存儲結構是邏輯結構用計算機語言的實作,它依賴于計算機語言。資料的存儲結構主要有順序存儲結構、鍊式存儲結構、索引存儲結構和散列存儲結構。
3、資料的運算:施加在資料上的運算包括資料的定義和實作。
是以,資料結構課程所要研究的主要内容可以簡要地歸納為以下3個方面:
1、研究資料元素之間固有的客觀聯系(邏輯結構)
2、研究資料在計算機内部的存儲方法(存儲結構)
3、研究資料在資料的各種結構(邏輯的和實體的)的基礎上如何對資料實施有效的操作或處理(算法)
為此,應該說資料結構是一門抽象的,研究資料之間結構關系的學科。