【正文】 數(shù)據(jù)處理的發(fā)展階段 ? 3． 60年代后期，數(shù)據(jù)庫系統(tǒng) ? 基本特征：面向全組織的復雜數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)冗余度小，易于擴充；數(shù)據(jù)與程序獨立；統(tǒng)一的數(shù)據(jù)控制功能。 數(shù)據(jù) 1 統(tǒng)一存取 數(shù)據(jù) 2 數(shù)據(jù) n 程序 2 程序 1 程序 n 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 22 數(shù)據(jù)組織 ? 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)文件 ? 數(shù)據(jù)庫 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 23 數(shù)據(jù)組織 ? 數(shù)據(jù)組織： 按照一定的方式和規(guī)則對數(shù)據(jù)進行歸并、存儲處理的過程 。 – 組織好數(shù)據(jù)，可以 便于數(shù)據(jù)更好的存儲、分類、檢索、歸并和調(diào)用 。 – 通常可以用 數(shù)組、文件及數(shù)據(jù)庫 來組織數(shù)據(jù)。 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 24 數(shù)據(jù)結(jié)構(gòu) 物理結(jié)構(gòu) （存儲結(jié)構(gòu)）：數(shù)據(jù)元素在計算機存儲器中的存儲方式 順序存儲 四種存儲方式 鏈接存儲 索引存儲 散列存儲 邏輯結(jié)構(gòu) ：數(shù)據(jù)間的邏輯關系 線性結(jié)構(gòu)（線性表、棧、隊列、串） 非線性結(jié)構(gòu)（樹、圖） 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)：包括數(shù)據(jù)的 存儲結(jié)構(gòu) 及 在此結(jié)構(gòu)上的運算或操作 。 物理結(jié)構(gòu) 是指數(shù)據(jù)具體存放在哪個位置 ,通俗些說就是數(shù)據(jù)放在硬盤里頭的哪一個地方。 邏輯結(jié)構(gòu) 是指數(shù)據(jù)高數(shù)據(jù)間是怎樣聯(lián)系的 . 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 25 數(shù)據(jù)結(jié)構(gòu) ? – 結(jié)點：在數(shù)據(jù)結(jié)構(gòu)中，表征某一數(shù)據(jù)結(jié)構(gòu)特點及其連接方式的基本單位。（字符、數(shù)字、記錄、集合） – 指針域：存放結(jié)點同其他結(jié)點關系信息的域。 – 數(shù)據(jù)域：存放結(jié)點自身信息的域。 – 指針：存放與結(jié)點地址有關的結(jié)點的地址稱為指針。 – 鏈：若干帶指針的結(jié)點組成的集合。 LL I N K 左指針 I N FO 信息 R LI N K 右指針 指向后繼結(jié)點，存放后繼結(jié)點地址 數(shù)據(jù)域 指針域 指向前趨結(jié)點，存放前趨結(jié)點地址 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 26 鏈表的邏輯結(jié)構(gòu) 職工登記表 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 27 數(shù)據(jù)結(jié)構(gòu) ? 2．線性表 – （ 1）概念：指數(shù)據(jù)結(jié)構(gòu)形式本質(zhì)上是一維的線性關系，其中的每個結(jié)點都是同一類型的數(shù)據(jù)結(jié)構(gòu) 。 ? 線性表中的每個元素可以是一個數(shù)字、一串字符、一項記錄。 – （ 2）線性表的存儲方式 ? (i) 順序存儲 ? (ii)鏈接存儲 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 28 （ i）順序存儲 ? 順序存儲： 把線性表的結(jié)點按邏輯次序依次存放在一組連續(xù)的存儲單元里，結(jié)點在計算機內(nèi)的存放位置完全由結(jié)點在線性表中的順序號決定 。 ? 順序表：用順序存儲方法存儲數(shù)據(jù)的表稱為順序表。 ? 順序表的檢索方法 – 順序表的插入 – 順序表的刪除 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 29 )1()()( 1 ???? iLklo cKL O C i ?? 若開始結(jié)點的存放位置為 L O C （ k1）每個結(jié)點占用空間大小為 L ，則第 i個結(jié)點 ki的存放位置可有下式直接計算得到： )1()()(1???? iLklo cKLO Ci ?? k1 k2 ki 順序表的檢索方法 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 30 序號 結(jié)點內(nèi)容 序號 結(jié)點內(nèi)容 1 9 1 9 2 15 2 15 3 17 3 17 4 25 4 23 5 39 5 25 6 6 39 插入前 插入后 順序表的插入 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 31 序號 結(jié)點內(nèi)容 序號 結(jié)點內(nèi)容 1 9 1 9 2 15 2 15 3 17 3 17 4 23 4 25 5 25 5 39 6 39 6 刪除前 刪除后 順序表的刪除 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 32 順序表的特點 ? 適用情況：適用于經(jīng)常檢索但數(shù)據(jù)不經(jīng)常變動的情況。 ? 優(yōu)點： – 能直接訪問線性表中的任一結(jié)點。存儲方式簡單，便于檢索。 ? 缺點： – 執(zhí)行線性表的結(jié)點插、刪操作時要移動存于其他元素，使插和刪操作不夠簡便。 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 33 （ ⅱ ）鏈接存儲 ? 鏈接存儲： 在每個結(jié)點設有鏈指針，用來指示下一個結(jié)點的位置，結(jié)點本身則可以存放在任意一組存儲單元中，這些存儲單元可以是連續(xù)的，也可以是分散的 。接點之間的邏輯關系由指針表示。 ? 鏈接表：以鏈接方式存儲的線性表成為鏈表。 – 單項鏈：每個結(jié)點只有一個指針指向下一個結(jié)點，通過鏈接指針來體現(xiàn)線性表中的先后次序關系。 ? 特點：搜索時沿一個方向進行，并且每搜索一個結(jié)點，都必須從頭結(jié)點開始，搜索效率很低。 – 雙向鏈表：在每個結(jié)點中增加一個指向前趨結(jié)點的指針。 ? 鏈表的插入和刪除 ? 鏈表的特點 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 34 鏈表的插入和刪除 H A B C D ^ H A B C D ^ H A C D ^ H A C D ^ B （ a ）刪除結(jié)點 （ b ）插入結(jié)點 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 35 鏈表的特點 ? 連接存儲的特點： – 鏈表結(jié)構(gòu)在每個結(jié)點設有鏈指針，用來指示下一個結(jié)點的位置，結(jié)點本身則可以存放在任意一組存儲單元中，這些存儲單元是可以連續(xù)的，也可是分散的。 ? 優(yōu)點： – 結(jié)點之間的邏輯關系由指針表示 – 在插入和刪除時，只需改變前后結(jié)點的指針，而不需大量的數(shù)據(jù)移動。 ? 缺點： – 每個表元增加了一個后繼指針成分，要花費更多的存儲空間。 – 不便隨機的直接訪問線性表的任一結(jié)點。 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 36 數(shù)據(jù)結(jié)構(gòu) ? ： 是一種多分支多層次數(shù)據(jù)結(jié)構(gòu)，由一組結(jié)點組成 。類似于自然界中的樹。是最重要的一類非線性結(jié)構(gòu)。 代碼 直徑指針 1 直徑指針 2 直徑 長度指針 1 長度指針 2 直徑 長度指針 1 長度指針 2 長度單價庫存 長度單價庫存 長度單價庫存 長度單價庫存 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 37 1 2 3 4 6 7 8 9 5 一棵樹 1 0 2 3 4 1 0 2 3 4 有向圖 無向圖 ? （自學） ： 一個結(jié)點的前趨結(jié)點和后繼結(jié)點的個數(shù)是任意的。 （有向圖、無向圖） 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 38 學號 姓名 年齡 性別 系別 9721108 李拓 21 男 管理系 9721126 王煙 22 女 管理系 9721206 馬凱 22 男 管理系 數(shù)據(jù)文件 ? 在信息系統(tǒng)中， 數(shù)據(jù)組織一般采用文件組織和數(shù)據(jù)庫組織 。 ? 文件組織： 是一種按某種數(shù)據(jù)結(jié)構(gòu)把數(shù)據(jù)記錄存放在外存設備上的方式，一般適用于數(shù)據(jù)記錄存儲的比較簡單的場合 。 2022年 2月 8日 11時 16分 重慶理工大學信息管理系 張興蘭 39