數(shù)據(jù)結(jié)構(gòu)第一章1

數(shù)據(jù)結(jié)構(gòu)

DATASTRUCTURE,DS

郭艷副教授guoyanwuhan@（但是與課程有關(guān)的郵件請發(fā)至datastructure@163.com）（課件登錄dsshare@163.com下載，密碼：課堂給出）辦公室：北一樓215電話Q：323110966助教：劉洋，cug2011@126.com中國地質(zhì)大學(xué)計算機學(xué)院2011年春教材及參考書目

教材：《數(shù)據(jù)結(jié)構(gòu)——使用C語言（第4版）》，朱戰(zhàn)立編著，電子工業(yè)出版社《C程序設(shè)計（第三版）》，譚浩強著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)實習(xí)指導(dǎo)書》，中國地質(zhì)大學(xué)（武漢）計算機科學(xué)與技術(shù)系主要參考書目：《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴蔚敏等編著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++描述》，殷人昆著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版），嚴蔚敏、吳偉民編著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》（C語言篇），李春葆編著，清華大學(xué)出版社內(nèi)容安排章內(nèi)容學(xué)時章內(nèi)容學(xué)時1緒論27廣義表略2線性表6+48樹和二叉樹8+43棧和隊列49圖8+44串略10排序65數(shù)組111查找66遞歸算法112文件略總學(xué)時56，其中講課44學(xué)時，上機12學(xué)時成績評定分數(shù)備注作業(yè)15基本每次課有作業(yè)（概念題、算法設(shè)計題），每周二下午交上機15三次上機實習(xí)，要求每次提交實習(xí)報告；時間初步第4、7、9周周一考試70時間地點待定合計100學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義數(shù)據(jù)結(jié)構(gòu)是為研究和解決如何有效地組織和處理非數(shù)值數(shù)據(jù)而產(chǎn)生的理論、技術(shù)和方法數(shù)據(jù)結(jié)構(gòu)是軟件設(shè)計技術(shù)的理論基礎(chǔ)，是計算機學(xué)科的核心專業(yè)基礎(chǔ)課程數(shù)據(jù)結(jié)構(gòu)是后繼專業(yè)課學(xué)習(xí)的必要知識和技能準備學(xué)習(xí)這門課程的目的掌握常用的基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用學(xué)會分析具體問題中的數(shù)據(jù)特性，有效地組織、表示和處理數(shù)據(jù)增強處理復(fù)雜問題的能力，訓(xùn)練復(fù)雜程序設(shè)計技能，提高編程質(zhì)量基本掌握算法效率的度量——時間復(fù)雜度分析技巧數(shù)據(jù)結(jié)構(gòu)課程的特點及學(xué)習(xí)方法特點1：內(nèi)容廣，概念多學(xué)習(xí)方法1：抓住主線，注重各章節(jié)間的聯(lián)系與銜接，融會貫通特點2：實踐性強、動手編程難學(xué)習(xí)方法2：學(xué)習(xí)一個階段后及時作業(yè)和上機實習(xí)基本數(shù)據(jù)結(jié)構(gòu)——線性表、棧、隊列、數(shù)組、樹、二叉樹、圖邏輯特性在計算機中的存儲方式在不同存儲方式下操作的算法實現(xiàn)(重點、難點)各種算法的性能分析各種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用(重點、難點)學(xué)習(xí)的主線考勤可以申請自學(xué)，必須寫出書面申請自學(xué)的同學(xué)可以不來聽課同樣交作業(yè)、上機、考試不要遲到、早退、曠課有事提前請假曠課三次將給予不及格處理按時提交作業(yè)，嚴禁抄襲除非不可抗拒的客觀原因，所有作業(yè)必須在指定的時間內(nèi)完成并提交一般周二交作業(yè)記分標準：例如一作業(yè)題滿分10分（1）準時提交，滿分可達10分；（2）每延遲1天提交，得分減1分；（3）7天之后提交或不交，得?5分；（4）抄襲，被抄襲者和抄襲者得?20分。嚴重的欺騙給予課程不及格處理。作業(yè)提交要求電子版作業(yè)提交至datastructure@163.com電子版作業(yè)提交時打一個rar包，學(xué)號+姓名+作業(yè)次數(shù)，如“20091000231呂巖1.rar”包中含有：1.readme.txt文件，把你的程序運行環(huán)境、程序功能、用戶運行步驟等簡單說明2.源程序、頭文件以及相關(guān)項目和資源文件，如.dsp，.dsw3.上機實習(xí)題要求另外提交報告文檔編程風格要求結(jié)構(gòu)化程序設(shè)計方法（譚浩強P34）文檔化誠實代碼編寫的程序正確、結(jié)構(gòu)清楚、易讀（寫注釋），符合軟件工程的規(guī)范（P14）第一次課閱讀：

朱戰(zhàn)立，第1-14頁

譚浩強，第131-134、155-188、204-214、

219-277、289-305頁練習(xí)：

作業(yè)1Chapter1緒論

1.1-2基本術(shù)語

-數(shù)據(jù)結(jié)構(gòu)

-抽象數(shù)據(jù)類型

1.3算法與算法分析

-算法

-

掌握估算算法時間復(fù)雜度的方法

1.1基本術(shù)語●數(shù)據(jù)（Data）

凡是能輸入到計算機，由計算機進行加工處理的數(shù)字、字母、文字和其它符號均叫做數(shù)據(jù)。

含義極為廣泛，如圖形、聲音等都屬數(shù)據(jù)的范疇?！駭?shù)據(jù)元素（DataElement）

數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的一個個體。有時，一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成，數(shù)據(jù)項是具有獨立含義的最小單位。

例如、圖書自動檢索系統(tǒng)的數(shù)據(jù)登錄號書名作者名出版單位分類號出版時間001002003高等數(shù)學(xué)理論力學(xué)數(shù)據(jù)結(jié)構(gòu)樊映川嚴蔚敏羅遠詳S01L01J01高等教育出版社┇┇┇┇┇┇┅┅┅┅┅●數(shù)據(jù)結(jié)構(gòu)（DataStructure） ◆

元素之間的關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)，簡單地說，就是數(shù)據(jù)元素的集合加上數(shù)據(jù)元素之間的相互關(guān)系的集合，可形式化地描述成一個二元組：

DataStructure=(D,S)

其中，D：數(shù)據(jù)元素的集合，

S：D上關(guān)系的集合。 ◆

1968年唐?歐?克努特[美]：

數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)的邏輯結(jié)構(gòu)+數(shù)據(jù)的存儲結(jié)

構(gòu)+數(shù)據(jù)的運算◆數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間抽象化的相互關(guān)系。二元組形式化定義DataStructure=(D,S)中的S即指邏輯結(jié)構(gòu)。三類基本結(jié)構(gòu)：線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)也可簡單分為： 線性結(jié)構(gòu)：線性表、棧、隊列、串、數(shù)組非線性結(jié)構(gòu)：樹、二叉樹、圖

例1、圖書自動檢索系統(tǒng)（建立、查找、插入/刪除）登錄號書名作者名出版單位分類號出版時間001002003高等數(shù)學(xué)理論力學(xué)數(shù)據(jù)結(jié)構(gòu)樊映川嚴蔚敏羅遠詳S01L01J01高等教育出版社┇┇┇┇┇┇┅┅┅┅┅例2、一個大學(xué)的人事檔案處理系統(tǒng)學(xué)校一院(系)二院(系)…n院(系)

一專業(yè)二專業(yè)…m專業(yè)教師學(xué)生檔案檔案…檔案例3、交通管理信息系統(tǒng)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)根結(jié)點線性結(jié)構(gòu)：除第一個和最后一個元素外，每個元素只有一個直接前驅(qū)和一個直接后繼元素。應(yīng)用最多。樹結(jié)構(gòu)：除根結(jié)點外，每個元素只有一個直接前驅(qū)元素，可有多個直接后繼元素。圖結(jié)構(gòu)：每個元素可有多個直接前驅(qū)元素和多個直接后繼元素?！?/p>

數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）

邏輯結(jié)構(gòu)到計算機存儲器的映象。

映象方法：

順序分配

鏈式分配n–1i120┇┇元素序號┇┇an–1

a2

a1

a0內(nèi)存ai∧a0a1an-1…ai…h(huán)ead◆數(shù)據(jù)的運算（操作）

邏輯結(jié)構(gòu) 邏輯操作

存儲結(jié)構(gòu) 操作實現(xiàn)

通常的邏輯操作有：（1）建立一個數(shù)據(jù)結(jié)構(gòu)（2）銷毀一個數(shù)據(jù)結(jié)構(gòu)（3）插入一個新元素到一個指定的數(shù)據(jù)結(jié)構(gòu)（4）刪除一個元素（插入、刪除操作必須保持結(jié)構(gòu)不變

）（5）修改一個元素（或其中的數(shù)據(jù)項）的內(nèi)容（6）排序（7）查找抽象只知道"做什么"，而無須考慮"如何做"

具體概念小結(jié)數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)元素間在客觀世界的相互聯(lián)系、在計算機內(nèi)的存儲方法以及如何能在各種結(jié)構(gòu)上實施有效的操作算法.一個具體問題的軟件設(shè)計通常包含三個步驟：（1）分析和確定問題的邏輯結(jié)構(gòu)和邏輯操作

（2）設(shè)計該問題的具體存儲結(jié)構(gòu)

（3）設(shè)計該問題在具體存儲結(jié)構(gòu)下的操作實現(xiàn)算法●數(shù)據(jù)類型（DataType）數(shù)據(jù)類型是一組值的集合以及定義在這個值集上的一組操作的總稱。通?？煽醋魇歉呒壋绦蛟O(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。

例如C語言中基本類型有：整型、浮點型、字符型構(gòu)造類型有：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型●抽象數(shù)據(jù)類型（AbstractDataType,ADT）它是描述數(shù)據(jù)結(jié)構(gòu)的理論工具，目的是使人們能夠獨立于程序的實現(xiàn)細節(jié)來理解數(shù)據(jù)結(jié)構(gòu)的邏輯特性?？梢钥醋魇菙?shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。

ADT定義包含三部分：

數(shù)據(jù)元素數(shù)據(jù)元素之間的相互關(guān)系（結(jié)構(gòu)）定義在數(shù)據(jù)結(jié)構(gòu)上的一組操作例、線性表抽象數(shù)據(jù)類型的定義：

ADTList

數(shù)據(jù)元素：ai，i=0,1,…,n-1(n≥0)

結(jié)構(gòu)：對所有的數(shù)據(jù)元素ai(i=0,1,…,n-2)存在次序關(guān)系

<ai，

ai+1>,a0無前趨，an-1無后繼。

操作：設(shè)L為

List型的線性表

ListInitiate(L)//構(gòu)造一個空的線性表L。

ListLength(L)

//返回線性表L中的元素個數(shù)，即求表長。

ListInsert(L,i,x)

//在線性表L的第i個位置前插入一個值

為x的新元素，插入成功返回1，失敗返回0。

0≤i≤n，插入后表L的長度為n+1。

ListDelete(L,i,x)//刪除線性表L的第i個元素。0≤i≤n-1，

被刪除的元素通過x帶回。刪除成功返回1，失敗返回

0。刪除后表L的長度為n-1。

ListGet(L,i,x)//取線性表L中的第i個元素，并由參數(shù)x

帶回，0≤i≤n-1。成功返回1，失敗返回0。1.3算法和算法分析1.算法（Algorithm）●什么叫算法？

算法是為求解問題的步驟、方法、思路。

●算法的設(shè)計

“自頂向下，逐步以模塊的形式細化”原則●算法的描述

自然語言流程圖

程序設(shè)計語言（程序）偽碼語言●

算法的性質(zhì)

輸入性、輸出性、確定性、有窮性、可行性●

程序=算法+數(shù)據(jù)結(jié)構(gòu)（NiklausWirth)程序設(shè)計的實質(zhì)是對實際問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法。而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。2.算法分析

●

評價算法好壞的標準

除算法應(yīng)該是“正確”的外，還應(yīng)考慮：

◆該算法是易讀、易編碼、可調(diào)試（軟件工程）

◆該算法能有效利用計算機資源，歸結(jié)為CPU執(zhí)行指令數(shù)和占用內(nèi)存存儲單元數(shù)（數(shù)據(jù)結(jié)構(gòu)和算法）

●

評價方法

◆實驗方法（運行程序）

◆算法的漸進分析，簡稱算法分析

分析算法消耗的時間資源——時間復(fù)雜度

分析算法使用的空間資源——空間復(fù)雜度◆

算法的時間復(fù)雜度

設(shè)n表示問題的規(guī)模，則一個算法的時間復(fù)雜度是問題規(guī)模n的函數(shù)，記為T(n)。

當n逐步增大時，分析T(n)的增長率。 算法的時間復(fù)雜度T(n)采用算法中各個基本語句執(zhí)行次數(shù)的總和f(n)來度量，使用大O表示法，O(f(n))是算法的漸進時間復(fù)雜度，表達算法運行時間增長率的上界，即表示當n增大時，算法運行時間至多將以正比于f(n)的速度增長。

定義：T(n)=O(f(n))當且僅當存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤c×f(n)。

例1.

temp=i;i=j;j=temp;

f(n)=?

T(n)=O(1)