資源簡介

(共31張PPT)
認識數據和數據結構
1.1 數據及其價值
1．數字 數字（Number）是一種用來表示數的書寫符號。數字在不同的記數系統中表示的形式各不相同，阿拉伯數字是最普遍的一種。（二進制）
2．數值 量是事物在同一種屬性上的差別，通常用數字和單位來表示。一個量用數字表示時，這個數字叫作這個量的數值（Numerical Value）。例如，對于“質量”這種屬性，一個大蘋果質量約150克，一個小蘋果質量約100克；對于“長度”這種屬性，一張A4紙的兩條邊長分別為29.7厘米、21厘米
3．數據 數據（Data）是指對現實世界客觀事物進行記錄并可以鑒別的符號。數據是事實或觀察的結果，是對客觀事物的邏輯歸納，是用于表示客觀事物的未經加工的原始素材數據是信息的載體，是計算機程序加工的“原材料”。
可用于表示這個蘋果——“相片中、畫中描述的、近似球形的、紅色的、香甜的、質量為150克的物品”。當然，數據越詳細越準確，對于“蘋果”這個事物的表示就越準確。
1.下列描述正確的是( )。
A.“200”和“兩百”是相同的數值在不同的記數系統中的寫法
B.人體的正常體溫是37.9C,“37.9C" 是數據
C.小明的英語考試成績是90分，“90” 是數字
D.信息是數據的載體，是有意義的數據
1.2 對實際問題的數據抽象
計算機越來越多地用于控制、管理及數據處理等非數值計算的工作，這些工作的操作對象及其關系是一些具有一定結構的數據，無法用數學方程進行描述。因此，我們必須對實際問題進行數據抽象，分析待處理對象的特性以及各處理對象之間存在的關系，建立問題的數據模型。
1.2 對實際問題的數據抽象
2. 收集資料，進行分析，探究問題的解。
研究表明，對超市經營有影響的各種因素中，人的因素起重要作用。“人”的屬性眾多，“超市客戶”的屬性則需要篩選，可以從超市客戶管理需要的角度進行篩選。
1.2 對實際問題的數據抽象
1.2 對實際問題的數據抽象
1 . 2 . 2 　 分析數據之間的關系
1 . 2 . 2 　 分析數據之間的關系
1 . 2 . 2 　 分析數據之間的關系
在圖1-11中，數據間的聯系是多對多的：每個數據既有多個前驅，也有多個后繼。這種數據間的多對多聯系稱為網狀關系。例如，學校教育教學活動中涉及的人員之間的關系就是網狀關系：一個教師同時教多個學生，一個學生也同時有多個教師授課。
綜合以上三個例子可見，
描述這類非數值計算問題的數學模型不再是數學方程，而是用諸如表、樹、圖之類的數據模型進行描述。
數據模型是客觀事物及其關系的數據描述，是對客觀事物進行數據抽象的結果。
1 . 2 . 3 　 建立數據模型
線性關系是計算機中最常見的數據關系，表是計算機中最常見的數據模型。
在本教科書的后續章節中將要學習到的鏈表、隊列、棧、字符串，其數據模型都是表。具有層次關系的數據，其數據模型是樹——如家族成員樹（如圖1-10所示）、班級成員樹、學校機構樹等。
具有網狀關系的數據，其數據模型是圖——如城市交通圖（如圖1-11所示）、學校人員圖、（師生）教學圖等。
數據對象（Data Object）是性質相同的數據元素的集合，是數據的一個子集。例如，
整數數據對象是集合N={0，1，-1，2，-2，3，-3，…}
1.3　認識數據結構
假設超市商品數據是隨機排列的——查找的方法最簡單：從頭開始逐個比較，順序查對，直到找到目標為止。查找操作必須對所有數據進行，所以雖然方法簡單卻效率低下。
假設超市商品數據是有組織的——可按照商品所屬類別進行分類，同類商品數據放在一起，則商品查找效率將大大提高：先找到商品所屬類別，再從該類別下的首個數據開始進行逐個比較查對即可，無須對所有數據進行查找。
（1）對于商品數據，除了圖中所列組織方式，還有其他方式嗎？
（2）對應圖中數據的不同的組織方式，如果增加新的商品數據，其操作效率如何？刪除商品呢？
通過以上探究活動可知，當數據組織的方式、數據之間的關系不同時，實現同一功能的數據處理的過程就不同，數據處理的效率也不同。也就是說，在用計算機程序解決問題時，數據之間的關系會影響解決問題的步驟設計和程序執行效率。為了描述和處理越來越復雜的數據關系，人們需要研究數據結構。
在計算機世界中，把數據元素以及數據元素之間的關系構成的集合稱為數據結構（Data Structure）
數據元素之間的關系包括：
（1）數據元素之間的邏輯關系，即數據的邏輯結構（Logical Structure）。
（2）數據元素及其關系在計算機存儲器中的存儲方式，即數據的存儲結構（Storage
Structure），也稱為數據的物理結構。
2．數據的邏輯結構
根據數據元素之間邏輯關系的不同，數據結構有以下四種基本結構，如圖1-14所示。
（1）集合結構：數據元素除同屬于一個集合之外，沒有其他關系。
（2）線性結構：數據元素之間存在前后有序的一對一的關系。
（3）樹形結構：數據元素之間存在一對多的關系。
（4）圖形結構：數據元素之間存在多對多的關系。
3．數據的存儲結構
數據結構在計算機存儲器中的存儲方式稱為數據的存儲結構，又稱物理結構。它包括
數據元素的存儲和數據元素之間關系的存儲。二進制的一位是計算機存儲器的最小單位，數據在計算機中的存儲形式都是二進制位串。可以把這些位串看成數據元素在計算機中的存儲形式。
數據元素之間的關系在計算機中有兩種不同的表示方法：順序存儲和非順序存儲。因此，可以得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。
順序存儲結構是把邏輯上相鄰的數據元素存儲在物理位置也相鄰的單元中，這是最基本的存儲方法。
鏈式存儲結構對邏輯上相鄰的元素不要求其在物理位置上也相鄰。這種存儲結構就像鏈條一樣一環扣一環，存入每一數據元素的同時，也存入其下一元素的存儲地址。
圖1-13（b）中的數據表的順序存儲結構和鏈式存儲結構如圖1-15所示。
數據的存儲結構不同，對數據進行同一操作的實現方法也不同
1. 在順序存儲結構中：
（1）查找到“洗發水”的位置。
（2）“洗發水”后的數據逐個后移，空出一個位置。
（3）“沐浴露”存放進空出的位置中。
2. 在鏈式存儲結構中：
（1）找到空間存放“沐浴露”數據，記住這個位置的地址。
（2）“沐浴露”數據的下一地址指向原“洗發水”的下一地址，即指向“牙刷”數據。
（3）查找到數據“洗發水”，并使其下一地址指向“沐浴露”數據。
毛巾
洗發水
牙刷
1 . 3 . 2 　 數據類型
計算機通過執行程序進行數據處理。對于不同的數據，能執行的操作不盡相同。對于大多數編寫程序的人來說，只需要關心數據的取值范圍、數據元素間的關系、施加在數據上的操作規則。至于某種操作在計算機中如何實現，對程序員來說并不重要。例如，對于求和操作，程序員注重的僅僅是其“數學上求和”的抽象特性，而不是其在計算機硬件上究竟如何實現。于是，封裝了數據操作的數據類型就被引入程序設計語言中。
與數據結構相比，數據類型增加了對施加在數據元素上的操作的定義，即對數據的運算規則的定義。常用的運算有檢索、插入、刪除、更新、排序等，這些運算實質上是在抽象的數據上所施加的一系列的抽象的操作。
例如，整型變量之間的除法運算，結果也只能是整數。因此，整型變量的除法運算實際上是整除運算。如果整型變量的取值范圍為-32767~32767，則兩個整型變量的值分別為300和500，做加法運算，結果為800，在整型變量的取值范圍內，正確；但是，如果是30 000和30 000做加法，則會發生錯誤——結果60 000超出了整型變量的取值范圍，發生溢出錯誤。
不同的程序設計語言和不同的計算機系統對于數據類型的定義和實現可能稍有不同。
2．數據類型的分類
按數據類型“值”的不同特性，高級程序設計語言中的數據類型可分為兩類：簡單類型和結構類型。
簡單類型中的每個數據都是不可再分割的整體。例如C++語言中的基本類型（整型、實型、字符型和枚舉型）、指針類型和空類型。結構類型是由簡單類型按照一定的規則構造的。而且，結構類型內部還可以再包含結構類型。所以，每一種結構類型的值都是可以再分解為若干個簡單類型或結構類型的值。
1 . 3 . 3 　 數據結構的重要作用
用計算機解決此問題，首先要對數據進行組織，設計數據結構。
最簡單的方法就是將生活中的通信錄直接轉化存儲，構造一張號碼表，表中每個數據元素包含兩個數據項：姓名和號碼。將表中的數據元素順序存儲在計算機中，查找時從頭開始依次查對姓名，直到找到目標或找完整張表為止。當數據量大的時候，這種方法就不實用了。要提高查找速度，就要改進數據表的結構和存儲方式
1 . 3 . 3 　 數據結構的重要作用
要提高查找速度，就要改進數據表的結構和存儲方式。可通過以下方法改進數據結構的設計：
（1）號碼表中的數據元素按姓氏排列。
（2）設計一張姓氏索引表，采用如圖1-19所示的存儲結構。
1 . 3 . 3 　 數據結構的重要作用
算法是解決問題的有限步驟的序列，是一系列解決問題的清晰指令。
數據結構是數據元素以及數據元素之間的關系的集合。
程序是為實現特定目標或解決特定問題而用計算機語言編寫的命令序列的集合。
本質上，數據是客觀事物表示的一種抽象結果，而數據結構這門課程就是研究如何把客觀世界待處理的信息逐層抽象成計算機可以接受的某種形式。通俗地說，數據結構就是研究數據之間的相互關系，也就是數據的組織形式的一門科學。
程序員通過定義數據結構來描述數據以及數據之間的關系。算法的設計取決于選定的數據結構（邏輯結構），而算法的實現依賴于采用的存儲結構。選擇什么樣的邏輯結構決定了處理數據的步驟和方法，選擇何種存儲結構則決定了如何編寫程序語句。如果數據結構選擇不好，除影響程序開發速度之外，更重要的是影響設計出來的程序的運行效率。所以，學好數據結構是學好程序設計的基礎。
1．單選題
（1）對數字、數值、數據，以下描述正確的是（　　）。
A.“一個蘋果重150克”——“150克”是數值
B.“觀察一幅畫獲得了美的感受”——“美的感受”是數據
C.“100讀作一百”——同一個數在不同記數系統中的寫法不同
D.“計算機擅長計算”——計算機只能處理數值數據
（2）關于大數據的描述，下列說法錯誤的是（　　）。
A. 當今社會注重隱私，只要人們不愿意，人們在社會生活中生成的數據就不會被收集
B. 大數據計算可以給人們的社會活動提供參考
C. 大數據計算的結果，能夠調節、影響人們的活動
D. 自然界中的事物也能提供數據
（3）數據結構在解決問題的過程中有重要作用。下列對數據結構的描述中正確的
是（　　）。
A. 對同一事物，只能構造出一種數據結構
B. 選擇的數據結構不同，解決問題的步驟也不同
C. 數據邏輯結構中相鄰的數據，其存儲位置也一定相鄰
D. 對同一操作如插入、刪除等，不同數據存儲結構的實現方法相同

展開更多......

收起↑