數(shù)據(jù)結(jié)構(gòu) (2)市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

數(shù)據(jù)結(jié)構(gòu)中原工學(xué)院計(jì)算機(jī)學(xué)院1數(shù)據(jù)結(jié)構(gòu)(2)第1頁使用教材嚴(yán)蔚敏、吳偉民：數(shù)據(jù)結(jié)構(gòu)(C語言版)清華大學(xué)出版社（1997）嚴(yán)蔚敏、吳偉民：數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)清華大學(xué)出版社（1997）參考教材：殷人昆：數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）清華大學(xué)出版社（1997）胡學(xué)剛：數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo).清華大學(xué)出版社

李春保：數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語言篇），清華大學(xué)出版社，1月。￥28BrunoR.Preiss：數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社（）其它參考資料：學(xué)校圖書館、計(jì)算機(jī)學(xué)院資料室2數(shù)據(jù)結(jié)構(gòu)(2)第2頁考評成績（本課程為考試課）平時(shí)成績（20-30%）書面作業(yè)6-15（布置幾次、是否按時(shí)交、質(zhì)量怎樣）課堂討論和提問3-5（有成績統(tǒng)計(jì)）上機(jī)試驗(yàn)8-15（試驗(yàn)考勤、試驗(yàn)匯報(bào)是否按時(shí)交、質(zhì)量怎樣）考勤與綜合表現(xiàn)5-10（不缺課、不遲到、認(rèn)真聽課、恪守課堂紀(jì)律）學(xué)期測驗(yàn)（1-3次）期末考試（70-80%）誠信確保：“我XXX真誠地確保：我自己獨(dú)立地完成了整個(gè)作業(yè)、試驗(yàn)程序從分析、設(shè)計(jì)到編碼全部工作。我沒有剽竊任何其它人作業(yè)或代碼?！报C附在作業(yè)或試驗(yàn)匯報(bào)前3數(shù)據(jù)結(jié)構(gòu)(2)第3頁內(nèi)容安排（74=58+16）章內(nèi)容課時(shí)章內(nèi)容課時(shí)1序論27圖122線性表68動態(tài)存放管理略3棧和隊(duì)列49查找44串410內(nèi)部排序45數(shù)組和廣義表

411外部排序略6樹和二叉樹

1012文件略注：放假占用6課時(shí)，實(shí)際講課課時(shí)為：58-6

=524數(shù)據(jù)結(jié)構(gòu)(2)第4頁學(xué)習(xí)方式聽課：啟發(fā)式，重在主動思索、主動參加逐步培養(yǎng)分析問題、處理問題技能。讀書：預(yù)習(xí)、復(fù)習(xí)（多研讀算法）作業(yè)、試驗(yàn)和課外作業(yè)（大作業(yè)）：多實(shí)踐1、多做習(xí)題2、多練習(xí)：算法轉(zhuǎn)化為程序3、多實(shí)踐帶有實(shí)際背景算法問題5數(shù)據(jù)結(jié)構(gòu)(2)第5頁基于知識能力與素質(zhì)協(xié)調(diào)發(fā)展瀑布式教學(xué)理念6數(shù)據(jù)結(jié)構(gòu)(2)第6頁教學(xué)理念獲獎(jiǎng)證書河南省教育科學(xué)研究優(yōu)異結(jié)果二等獎(jiǎng)7數(shù)據(jù)結(jié)構(gòu)(2)第7頁教學(xué)理念獲獎(jiǎng)證書河南省信息技術(shù)教育優(yōu)異結(jié)果三等獎(jiǎng)8數(shù)據(jù)結(jié)構(gòu)(2)第8頁本課程地位是學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理等計(jì)算機(jī)專業(yè)關(guān)鍵課程基礎(chǔ)和必要條件，考研重頭課；必修專業(yè)計(jì)算機(jī)類、電訊通信類、信息管理類、信息安全從事計(jì)算機(jī)應(yīng)用、軟件行業(yè)必備條件。數(shù)學(xué)軟件硬件教材P4圖1.4”數(shù)據(jù)結(jié)構(gòu)“是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間一門關(guān)鍵課程9數(shù)據(jù)結(jié)構(gòu)(2)第9頁第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)討論范圍）1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型表示與實(shí)現(xiàn)1.4算法和算法分析

1.4.1算法1.4.2算法設(shè)計(jì)要求1.4.3算法效率度量1.4.4算法存放空間需求10數(shù)據(jù)結(jié)構(gòu)(2)第10頁課前索引【重點(diǎn)和難點(diǎn)】

本章討論都是一些基本概念，所以沒有難點(diǎn)，重點(diǎn)在于了解相關(guān)數(shù)據(jù)結(jié)構(gòu)各個(gè)名詞和術(shù)語含義，以及語句頻度和時(shí)間復(fù)雜度、空間復(fù)雜度估算?！局R點(diǎn)】

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法及其設(shè)計(jì)標(biāo)準(zhǔn)、時(shí)間復(fù)雜度、空間復(fù)雜度.11數(shù)據(jù)結(jié)構(gòu)(2)第11頁課前索引【學(xué)習(xí)指南】

1.熟悉各名詞、術(shù)語含義，掌握基本概念，尤其是數(shù)據(jù)邏輯結(jié)構(gòu)和存放結(jié)構(gòu)之間關(guān)系。分清哪些是邏輯結(jié)構(gòu)性質(zhì)，哪些是存放結(jié)構(gòu)性質(zhì)。

2.了解抽象數(shù)據(jù)類型定義、表示和實(shí)現(xiàn)方法。

3.熟悉類C語言書寫規(guī)范，尤其要注意值調(diào)用和引用調(diào)用區(qū)分，輸入、輸出方式以及錯(cuò)誤處理方式。

4.了解算法五要素確實(shí)切含義和對算法正確性了解。5.掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度方法。12數(shù)據(jù)結(jié)構(gòu)(2)第12頁1.1什么是數(shù)據(jù)結(jié)構(gòu)一、引言（數(shù)據(jù)結(jié)構(gòu)概況：引入）

概括地說，數(shù)據(jù)結(jié)構(gòu)是與程序設(shè)計(jì)親密相關(guān)一門課程，它主要是研究和處理非數(shù)值計(jì)算問題程序設(shè)計(jì)中，怎樣合理地組織、存放和處理數(shù)據(jù)。如：學(xué)生信息管理系統(tǒng)

算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)

（Algorithm+DataStructures=Programs）瑞士著名計(jì)算機(jī)科學(xué)家、Pascal語言創(chuàng)造者N.沃思教授提出（經(jīng)典書名）。

13數(shù)據(jù)結(jié)構(gòu)(2)第13頁1.1什么是數(shù)據(jù)結(jié)構(gòu)（續(xù)）

程序設(shè)計(jì)（實(shí)質(zhì)）：編制一套讓計(jì)算機(jī)按照人旨意進(jìn)行操作(去處理問題）一組有序“指令”。（數(shù)據(jù)結(jié)構(gòu)+

算法=

程序設(shè)計(jì)

）

程序設(shè)計(jì)首先需要處理兩個(gè)問題：數(shù)據(jù)結(jié)構(gòu)：對處理問題怎樣表示，即問題數(shù)學(xué)模型是什么。算法：怎么去處理問題，即處理問題策略（在該數(shù)學(xué)模型上操作）（任何程序設(shè)計(jì)都包含這兩方面內(nèi)容。）14數(shù)據(jù)結(jié)構(gòu)(2)第14頁

1、早期計(jì)算機(jī)主要用于科學(xué)計(jì)算：

如天文研究、工程計(jì)算等方面純數(shù)值計(jì)算，方程求解等。

2、計(jì)算機(jī)技術(shù)飛速發(fā)展引發(fā)其應(yīng)用領(lǐng)域擴(kuò)大：科學(xué)計(jì)算：天氣預(yù)報(bào)…控制：工業(yè)自動化、航天飛機(jī)，數(shù)控機(jī)床…數(shù)據(jù)處理：聲音、圖形、圖像，…管理：數(shù)據(jù)庫，辦公自動化…3、計(jì)算機(jī)處理對象發(fā)生復(fù)雜改變，處理問題方法也非常復(fù)雜：

純數(shù)值數(shù)據(jù)→非數(shù)值數(shù)據(jù)（含有一定結(jié)構(gòu)）如：字符、表格、聲音、圖形、圖像等，而且相互之間存在著聯(lián)絡(luò)。二、數(shù)據(jù)結(jié)構(gòu)發(fā)展背景--簡略用原有處理數(shù)值數(shù)據(jù)方法（代數(shù)/微分方程組），計(jì)算機(jī)無法識別、處理。15數(shù)據(jù)結(jié)構(gòu)(2)第15頁例一、圖書館書目檢索系統(tǒng)自動化問題。

一本書書目信息（編者、書名、出版社、出版時(shí)間、定價(jià)等內(nèi)容）怎樣在計(jì)算機(jī)內(nèi)表示，怎樣檢索（按書名、編者或是出版社）--顯然上述問題無法用方程組來表示。算法：？模型：？（表格（交大）-線性表（元素間線性關(guān)系））例二、多交叉路口紅綠燈管理。普通十字路口橫豎兩個(gè)方向都設(shè)有兩個(gè)紅綠燈，分別控制左拐、直行和右拐以保持正常交通秩序，而在多叉路口需設(shè)幾個(gè)紅綠燈。那么怎樣控制這些紅綠燈既使交通不堵塞，又使流量最大呢？若要編制程序處理問題，首先要處理一個(gè)怎樣表示問題。

算法：？－哪些路口可同時(shí)流通（綠色），而哪些不能（紅色）--圖著色問題

模型：？－圖（多對多網(wǎng)狀關(guān)系）登錄號書名作者名

分類號……非數(shù)值數(shù)據(jù)計(jì)算問題實(shí)例16數(shù)據(jù)結(jié)構(gòu)(2)第16頁例三、煤氣管道鋪設(shè)問題。

以下列圖所表示，需為城市各小區(qū)之間鋪設(shè)煤氣管道，對n個(gè)小區(qū)只需鋪設(shè)n-1條管線（若干種），因?yàn)榈乩憝h(huán)境不一樣等原因使鋪設(shè)各條管線所需費(fèi)用不一樣(如圖上所標(biāo)識)，怎樣鋪設(shè)使投資成本最低？這是一個(gè)討論圖生成樹問題。算法：？－圖最小生成樹模型：？－圖非數(shù)值數(shù)據(jù)處理實(shí)例（續(xù)）17數(shù)據(jù)結(jié)構(gòu)(2)第17頁

例四、人機(jī)對奕，棋盤為3x3，當(dāng)一方三個(gè)棋子占同一方同一行，或同一列，或同一對角線時(shí)，勝利。這里就存在棋子、棋盤格局表示問題、對弈過程有怎樣表示等問題。

算法：？－－對弈規(guī)則和策略

模型：？－－樹（棋盤及棋盤格局）（一對多層次關(guān)系）

樹根是對弈開始之前棋盤格局，全部葉子就是可能出現(xiàn)結(jié)局，對弈過程就是從樹根沿樹叉到某個(gè)葉子過程。

非數(shù)值數(shù)據(jù)處理實(shí)例（續(xù)）18數(shù)據(jù)結(jié)構(gòu)(2)第18頁從上述例子能夠看出，要編程實(shí)現(xiàn)上述問題，必須處理兩方面問題：

⑴、問題數(shù)學(xué)模型確實(shí)立

首先要處理是上述問題描述，即問題數(shù)學(xué)模型建立，顯然他們數(shù)學(xué)模型不能用數(shù)學(xué)方程來描述。那么這些數(shù)學(xué)模型是什么，問題所包括對象怎樣表示。這正是數(shù)據(jù)結(jié)構(gòu)所研究主要對象。⑵、確定在數(shù)學(xué)模型上進(jìn)行操作（找出處理問題方法）

從問題抽象出其數(shù)學(xué)模型，這并不是數(shù)據(jù)結(jié)構(gòu)課程研究最終目標(biāo)，而是討論這些非數(shù)值計(jì)算問題中數(shù)學(xué)模型怎么在計(jì)算機(jī)中表示，以及怎樣實(shí)現(xiàn)在數(shù)學(xué)模型上操作。這正是數(shù)據(jù)結(jié)構(gòu)這門課程所研究主要內(nèi)容。

三、數(shù)據(jù)結(jié)構(gòu)所研究范圍19數(shù)據(jù)結(jié)構(gòu)(2)第19頁

概括地說，數(shù)據(jù)結(jié)構(gòu)是一門討論“非數(shù)值計(jì)算“程序設(shè)計(jì)問題中數(shù)學(xué)模型(現(xiàn)實(shí)世界抽象描述)及施加在其上操作在計(jì)算機(jī)中怎樣表示和實(shí)現(xiàn)學(xué)科。

如學(xué)生信息管理系統(tǒng)中學(xué)生、成績表示及其查詢、排序等操作實(shí)現(xiàn)。三、數(shù)據(jù)結(jié)構(gòu)所研究范圍（續(xù)）20數(shù)據(jù)結(jié)構(gòu)(2)第20頁數(shù)據(jù)結(jié)構(gòu)涵蓋內(nèi)容21數(shù)據(jù)結(jié)構(gòu)(2)第21頁一、基本概念和術(shù)語數(shù)據(jù)(Data):

在計(jì)算機(jī)科學(xué)中，是指全部能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理符號總稱（集合）。

它是對客觀事物符號表示（描述），是計(jì)算機(jī)處理信息特定符號表示形式（信息載體）

。數(shù)據(jù)結(jié)構(gòu)中所討論數(shù)據(jù)范圍很廣泛，如：字符、聲音、圖形、圖像等多媒體信息。伴隨計(jì)算機(jī)發(fā)展，數(shù)據(jù)范圍不停擴(kuò)大。1.2基本概念和術(shù)語（了解）22數(shù)據(jù)結(jié)構(gòu)(2)第22頁數(shù)據(jù)元素(DataElement):

是數(shù)據(jù)(集合)中一個(gè)“個(gè)體”，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論“基本單位”，但不是最小單位，它經(jīng)常有若干數(shù)據(jù)項(xiàng)（是對數(shù)據(jù)元素不一樣屬性描述，含有獨(dú)立意義）組成。一、基本概念和術(shù)語（2）比如，在學(xué)生信息管理系統(tǒng)中，一條學(xué)生紀(jì)錄就是一個(gè)數(shù)據(jù)元素（學(xué)號、姓名、性別等數(shù)據(jù)項(xiàng)組成）。學(xué)號姓名性別班級

出生日期住址年月日描述一個(gè)學(xué)生信息數(shù)據(jù)元素由上述6個(gè)數(shù)據(jù)項(xiàng)組成三者之間關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：班級通訊錄>個(gè)人統(tǒng)計(jì)>姓名、年紀(jì)……23數(shù)據(jù)結(jié)構(gòu)(2)第23頁關(guān)鍵字

指能識別一個(gè)或多個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)。若能起唯一識別作用，則稱之為“主”關(guān)鍵字，不然稱之為“次”

關(guān)鍵字。如：學(xué)生紀(jì)錄（學(xué)號，姓名，性別，班級）數(shù)據(jù)對象(DataObject)：是性質(zhì)相同數(shù)據(jù)元素集合。是數(shù)據(jù)一個(gè)子集。

如：整數(shù)、實(shí)數(shù)等。它們是數(shù)據(jù)一個(gè)子集。一、基本概念和術(shù)語（3）24數(shù)據(jù)結(jié)構(gòu)(2)第24頁兩類數(shù)據(jù)元素：

一類是不可分割“原子”型數(shù)據(jù)元素，如：整數(shù)“5”，字符“N”等；另一類是由多個(gè)款項(xiàng)組成數(shù)據(jù)元素（結(jié)構(gòu)型），其中每個(gè)款項(xiàng)被稱為一個(gè)“數(shù)據(jù)項(xiàng)”，是對數(shù)據(jù)元素某種屬性描述，含有獨(dú)立意義。

比如描述一個(gè)學(xué)生信息數(shù)據(jù)元素由以下6個(gè)數(shù)據(jù)項(xiàng)組成：

組合項(xiàng)

一、基本概念和術(shù)語（4）學(xué)號姓名性別班級

出生日期住址年月日

原子項(xiàng)25數(shù)據(jù)結(jié)構(gòu)(2)第25頁1、數(shù)據(jù)結(jié)構(gòu)定義：是相互之間存在一個(gè)或各種特定關(guān)系（結(jié)構(gòu)）數(shù)據(jù)元素集合。說明：在客觀世界中存在各個(gè)事物之間存在著千絲萬縷“聯(lián)絡(luò)”，所以當(dāng)用計(jì)算機(jī)對它進(jìn)行處理時(shí)候必然也要將這種關(guān)系描述進(jìn)去，如數(shù)學(xué)方程就是變量之間約束關(guān)系一個(gè)描述，在此稱這種關(guān)系為結(jié)構(gòu)。能夠說，數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間關(guān)系總和，換句話說，數(shù)據(jù)結(jié)構(gòu)是帶"結(jié)構(gòu)"數(shù)據(jù)元素集合。二、數(shù)據(jù)結(jié)構(gòu)(DataStructure)26數(shù)據(jù)結(jié)構(gòu)(2)第26頁比如，一個(gè)2行3列矩陣，含6個(gè)數(shù)據(jù)元素a1,a2,a3,a4,a5,a6集合，且集合上存在“行關(guān)系”和“列關(guān)系”兩個(gè)次序關(guān)系，能夠用下述數(shù)據(jù)結(jié)構(gòu)來描述：

{a1,a2,a3,a4,a5,a6}

–元素集合，其中行關(guān)系為：

{<a1,a2>，<a2,a3>，<a4,a5>，<a5,a6>}列關(guān)系為：{<a1,a4>，<a2,a5>，<a3,a6>}。

---線性關(guān)系集合

以上所舉數(shù)據(jù)結(jié)構(gòu)例子中關(guān)系都是“線性”次序關(guān)系”，數(shù)據(jù)元素之間還可能存在非線性關(guān)系，如1.1節(jié)中“管道圖”，人機(jī)對弈中“樹型”關(guān)系。2、數(shù)據(jù)結(jié)構(gòu)舉例NOa1a2a3a4a5a627數(shù)據(jù)結(jié)構(gòu)(2)第27頁

依據(jù)數(shù)據(jù)元素之間所存在關(guān)系（結(jié)構(gòu)）不一樣，數(shù)據(jù)結(jié)構(gòu)通常有四種基本類型：線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對一次序關(guān)系。

例,用三個(gè)4位數(shù)表示一個(gè)12位數(shù)：123456789123可表示為：a1(1234)，a2(5678)，a3(9123)

a1,a2,a3存在次序關(guān)系<a1,a2>、<a2,a3>,不一樣于<a2,a1>、<a1,a3>樹型結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對多層次關(guān)系。

比如，三代家譜圖（層次：輩分）。3、數(shù)據(jù)結(jié)構(gòu)四種基本類型園圈-數(shù)據(jù)元素線段-關(guān)系28數(shù)據(jù)結(jié)構(gòu)(2)第28頁圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在多對多網(wǎng)狀關(guān)系。集合結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素除了同屬于一個(gè)類型外，別無其它關(guān)系（特殊關(guān)系）。

注：上述四種結(jié)構(gòu)主要是對數(shù)據(jù)元素之間存在邏輯關(guān)系描述。3、數(shù)據(jù)結(jié)構(gòu)四種基本類型（續(xù)）29數(shù)據(jù)結(jié)構(gòu)(2)第29頁解釋：什么叫數(shù)據(jù)邏輯結(jié)構(gòu)？答：指數(shù)據(jù)元素之間邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)存放無關(guān)，是獨(dú)立于計(jì)算機(jī)。上述四類結(jié)構(gòu)既是數(shù)據(jù)邏輯結(jié)構(gòu)：集合結(jié)構(gòu)：

僅同屬一個(gè)集合線性結(jié)構(gòu):一對一（1:1)

樹結(jié)構(gòu):一對多（1:n)

圖結(jié)構(gòu):多對多(m:n)非線性線性數(shù)據(jù)邏輯結(jié)構(gòu)即可用圖形表示，也可代數(shù)關(guān)系表示30數(shù)據(jù)結(jié)構(gòu)(2)第30頁數(shù)據(jù)結(jié)構(gòu)形式定義為一個(gè)二元組：Data-Structure=(D，S)其中：D是數(shù)據(jù)元素有限集，

S是D上關(guān)系有限集。例復(fù)數(shù)數(shù)據(jù)結(jié)構(gòu)定義以下:(復(fù)數(shù)x=C1+C2i)Complex=(C，R)其中：C是含兩個(gè)實(shí)數(shù)集合﹛C1，C2﹜，分別表示復(fù)數(shù)實(shí)部和虛部。

R={P}，P是定義在集合上一個(gè)序偶關(guān)系：{<C1，C2>}。有序?qū)?lt;>,區(qū)分（）4、數(shù)據(jù)結(jié)構(gòu)形式定義（邏輯結(jié)構(gòu)表示）31數(shù)據(jù)結(jié)構(gòu)(2)第31頁（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表示式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性。例：用圖形表示以下數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。二元組舉例32數(shù)據(jù)結(jié)構(gòu)(2)第32頁（2）S=(D,R)

D={di|1≤i≤5}

R={<di,dj>,1≤i<j≤5}

d1d5d2d4d3該結(jié)構(gòu)是非線性。解：上述表示式可用圖形表示為：思索：R={（di,dj）,1≤i,j≤5}33數(shù)據(jù)結(jié)構(gòu)(2)第33頁三、數(shù)據(jù)存放結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含數(shù)據(jù)“邏輯結(jié)構(gòu)”和數(shù)據(jù)“物理結(jié)構(gòu)”兩個(gè)方面（層次）。

數(shù)據(jù)邏輯結(jié)構(gòu)，是對數(shù)據(jù)元素之間存在邏輯關(guān)系描述，它能夠用圖形表示，也能夠用二元組表示。

數(shù)據(jù)物理結(jié)構(gòu)，又稱數(shù)據(jù)存放結(jié)構(gòu)，是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中表示（映像），包含數(shù)據(jù)元素表示和關(guān)系表示。34數(shù)據(jù)結(jié)構(gòu)(2)第34頁用二進(jìn)制位(bit)“位串”表示數(shù)據(jù)元素

在計(jì)算機(jī)中表示信息最小單位是“位(bit)”，任何一個(gè)數(shù)據(jù)元素都能夠用一個(gè)“位串”表示，如：A=（01000001）2－－位串－元素（結(jié)點(diǎn)）當(dāng)數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成時(shí)，每個(gè)數(shù)據(jù)項(xiàng)即為表示數(shù)據(jù)元素位串中一個(gè)"子位串"。數(shù)據(jù)元素表示（映像）：35數(shù)據(jù)結(jié)構(gòu)(2)第35頁表示有序?qū)?lt;x,y>方法

全部關(guān)系均可用一個(gè)有序?qū)?lt;x,y>集合表示。

（注：有序?qū)?lt;x,y>－y是x后繼，x是y前驅(qū)）

比如：有一個(gè)線性結(jié)構(gòu)B=(D,R),其中D={A,B,C,D,E}A-B-C-D-ER={<A,B>,<B,C>,<C,D>,<D,E>}–有序?qū)镆粋€(gè)<x,y>有序?qū)κ墙M成關(guān)系基本單位，所以討論關(guān)系表示方法只需討論這個(gè)有序?qū)υ谟?jì)算機(jī)中表示方法即可，即怎樣表示“y是x后繼”。關(guān)系表示（映像）方法：36數(shù)據(jù)結(jié)構(gòu)(2)第36頁有序?qū)煞N映象方法一：次序映象：

以數(shù)據(jù)元素存放位置相鄰表示后繼關(guān)系（邏輯相鄰）

比如線性結(jié)構(gòu)B=(D,R),R={<A,B>,<B,C>,<C,D>,<D,E>}次序存放示意圖次序存放特點(diǎn):

用數(shù)據(jù)元素在存放器中相對位置（相鄰）來隱含地表示數(shù)據(jù)元素之間邏輯關(guān)系，只存放數(shù)據(jù)元素本身值，不用另外存放關(guān)系。缺點(diǎn)：占連續(xù)空間ABCDE999100010011002100310041005→次序存放37數(shù)據(jù)結(jié)構(gòu)(2)第37頁有序?qū)煞N映象方法二：鏈?zhǔn)接诚?/p>

有序?qū)?lt;x,y>

以和x綁定在一起附加信息(指針)表示后繼關(guān)系，這個(gè)指針即為y存放地址，由此得到數(shù)據(jù)存放結(jié)構(gòu)為“鏈?zhǔn)酱娣沤Y(jié)構(gòu)”。

結(jié)點(diǎn)結(jié)構(gòu)比如：R={<A,B>,<B,C>,<C,D>,<D,E>}

結(jié)點(diǎn)

鏈?zhǔn)酱娣攀疽鈭D鏈?zhǔn)酱娣盘攸c(diǎn)：

不但要存放數(shù)據(jù)元素本身，還要存放其關(guān)系信息（增加一個(gè)指向其后繼地址指針）A106C108E^B102D104100101102103104105106107108109110111→鏈?zhǔn)酱娣艛?shù)據(jù)元素后繼地址38數(shù)據(jù)結(jié)構(gòu)(2)第38頁存放結(jié)構(gòu)描述方法-簡略在不一樣編程環(huán)境中，存放結(jié)構(gòu)有不一樣描述方法。

當(dāng)用高級程序編程時(shí)，通?？捎酶呒壘幊陶Z言中提供數(shù)據(jù)類型描述之。數(shù)據(jù)元素要借用高級編程語言中數(shù)據(jù)類型描述之。比如：定義“結(jié)點(diǎn)結(jié)構(gòu)”為：

typedefstructnode{

intdata;//數(shù)據(jù)元素

structnode*next;//后繼指針

}NODE;//結(jié)點(diǎn)類型－結(jié)構(gòu)體類型*本書中算法描述語言-本教材采取類C語言作為描述工具（P9-P13）39數(shù)據(jù)結(jié)構(gòu)(2)第39頁C/C++語言基礎(chǔ)摸底（需上交）問題1：編程求解SUM=1+2+3+…+N=?要求：以函數(shù)調(diào)用形式實(shí)現(xiàn)時(shí)間要求：5-10分鐘問題2：編程求解N個(gè)整數(shù)最大值和最小值。要求：以函數(shù)調(diào)用形式實(shí)現(xiàn)，時(shí)間要求：10-20分鐘說明：提議全部同學(xué)都能參加摸底，留名是否自愿，但需注明獨(dú)立實(shí)現(xiàn)方式（獨(dú)立思索、參考書籍）和完成時(shí)間；自律不剽竊。不能完成者能夠真實(shí)地表示自己語言基礎(chǔ)，40數(shù)據(jù)結(jié)構(gòu)(2)第40頁與數(shù)據(jù)結(jié)構(gòu)相關(guān)操作-簡略對每一個(gè)數(shù)據(jù)結(jié)構(gòu)而言，必定存在與它親密相關(guān)一組操作。不一樣數(shù)據(jù)結(jié)構(gòu)其操作集不一樣，但以下操作必不可缺：

1)結(jié)構(gòu)生成；

2)結(jié)構(gòu)銷毀；

3)在結(jié)構(gòu)中查找滿足要求條件數(shù)據(jù)元素；

4)在結(jié)構(gòu)中插入新數(shù)據(jù)元素；

5)刪除結(jié)構(gòu)中已經(jīng)存在數(shù)據(jù)元素；

6)遍歷。41數(shù)據(jù)結(jié)構(gòu)(2)第41頁1.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型-簡略一、數(shù)據(jù)類型--表明數(shù)據(jù)屬性和所允許操作

在用高級程序設(shè)計(jì)語言編寫程序中，必須對程序中出現(xiàn)每個(gè)變量、常量或表示式，明確說明它們所屬數(shù)據(jù)類型。比如，C/C++語言中基本數(shù)據(jù)類型有：整型、字符型、實(shí)型（包含單精度型和雙精度型）及枚舉型。不一樣類型變量，其所能取值范圍不一樣，所能進(jìn)行操作不一樣。每個(gè)數(shù)據(jù)類型都顯著或隱含說明了它所屬變量或表示式在程序運(yùn)行中所允許取值范圍以及進(jìn)行操作。42數(shù)據(jù)結(jié)構(gòu)(2)第42頁數(shù)據(jù)類型是一個(gè)“值”集合和定義在此集合上“一組操作”總稱。數(shù)據(jù)類型有兩種：原子類型：原子類型值不可再分解如C語言中基本類型（整型，實(shí)型、字符型等）結(jié)構(gòu)類型：其值由若干成份按某種結(jié)構(gòu)組合而成，所以是能夠分解，如數(shù)組（內(nèi)套數(shù)組），結(jié)構(gòu)體（若干數(shù)據(jù)類型組成）。43數(shù)據(jù)結(jié)構(gòu)(2)第43頁在實(shí)際應(yīng)用中，不論哪種數(shù)據(jù)類型，程序員重視是它所屬變量含有哪些數(shù)學(xué)特征，以及允許在這些變量上能夠施加哪些操作，而不考慮它在計(jì)算機(jī)中怎樣表示以及操作怎樣實(shí)現(xiàn)。

如C語言中整型類型變量能夠進(jìn)行“+”、“-”、“”、“/”及“取?！钡冗\(yùn)算。

對于這種“整型類型”，是由C語言設(shè)計(jì)者對整數(shù)進(jìn)行分析、歸納，提取出它數(shù)學(xué)特征，進(jìn)而找出允許進(jìn)行操作，這個(gè)過程，稱為抽象?？煞Q這個(gè)“整數(shù)類型”為“抽象數(shù)據(jù)類型”。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是同一個(gè)概念：含有相同數(shù)學(xué)特征和一組相同操作。但抽象數(shù)據(jù)類型特征是使用與實(shí)現(xiàn)分離，實(shí)施封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）。44數(shù)據(jù)結(jié)構(gòu)(2)第44頁二、抽象數(shù)據(jù)類型（AbstractDataType-ADT）抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上一組操作。比如，矩陣抽象數(shù)據(jù)類型定義為，矩陣是一個(gè)由mXn個(gè)數(shù)排成m行n列表，它能夠進(jìn)行初等變換、相加、相乘、求逆、……等運(yùn)算。

45數(shù)據(jù)結(jié)構(gòu)(2)第45頁ADT有兩個(gè)主要特征:數(shù)據(jù)抽象

用ADT描述程序處理實(shí)體時(shí)，強(qiáng)調(diào)是其本質(zhì)特征、其所能完成功效(重能做什么？不考慮怎么做)以及它和外部用戶接口（即外界使用它方法）。數(shù)據(jù)封裝

將實(shí)體外部特征和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，而且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。（認(rèn)識實(shí)體外部特征，預(yù)防非法訪問）46數(shù)據(jù)結(jié)構(gòu)(2)第46頁抽象數(shù)據(jù)類型描述方法-簡略

抽象數(shù)據(jù)類型形式定義--三元組表示：

(D，S，P）

其中：D

是數(shù)據(jù)對象；

S

是D

上關(guān)系集；

P

是對D

基本操作集。說明：三元組表示，只是方便數(shù)學(xué)描述，在實(shí)際定義時(shí)要采取以下格式：

47數(shù)據(jù)結(jié)構(gòu)(2)第47頁ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：〈數(shù)據(jù)對象定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系定義〉基本操作：〈基本操作定義〉}ADT抽象數(shù)據(jù)類型名

其中，數(shù)據(jù)對象，數(shù)據(jù)關(guān)系定義采取偽碼（數(shù)學(xué)形式或語言文字）抽象數(shù)據(jù)類型定義格式–略講48數(shù)據(jù)結(jié)構(gòu)(2)第48頁其中基本操作定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

參數(shù)表賦值參數(shù)

只為操作提供輸入值。引用參數(shù)

以&打頭，除可提供輸入值外，還將返回操作結(jié)果。49數(shù)據(jù)結(jié)構(gòu)(2)第49頁初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足條件，若不滿足，則操作失敗，并返回對應(yīng)犯錯(cuò)信息。

若初始條件為空，則省略之。操作結(jié)果：說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)改變情況和應(yīng)返回結(jié)果。50數(shù)據(jù)結(jié)構(gòu)(2)第50頁比如，抽象數(shù)據(jù)類型復(fù)數(shù)定義：

數(shù)據(jù)對象：D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：R1＝{<e1,e2>|e1是復(fù)數(shù)實(shí)數(shù)部分，e2是復(fù)數(shù)虛數(shù)部分}ADTComplex{51數(shù)據(jù)結(jié)構(gòu)(2)第51頁基本操作：

AssignComplex(&Z,v1,v2)

操作結(jié)果：結(jié)構(gòu)復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2值。

DestroyComplex(&Z)

操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)

初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z實(shí)部值。52數(shù)據(jù)結(jié)構(gòu)(2)第52頁

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z虛部值。

Add(z1,z2,&sum)

初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2和值。}ADTComplex53數(shù)據(jù)結(jié)構(gòu)(2)第53頁抽象數(shù)據(jù)類型需要經(jīng)過高級編程語言中已經(jīng)實(shí)現(xiàn)數(shù)據(jù)類型（通常稱之謂固有數(shù)據(jù)類型）來實(shí)現(xiàn)。

比如利用C語言實(shí)現(xiàn)"復(fù)數(shù)"類型以下描述：

抽象數(shù)據(jù)類型表示和實(shí)現(xiàn)-簡略*本書中算法描述語言-本教材采取類C語言作為描述工具（P9-P13）54數(shù)據(jù)結(jié)構(gòu)(2)第54頁typedefstruct{

floatrealpart；floatimagpart；}complex；//complex復(fù)數(shù)抽象數(shù)據(jù)類型//復(fù)數(shù)抽象數(shù)據(jù)類型定義//-----基本操作函數(shù)原型說明void

AssignComplex

(complex&Z,floatrealval,floatimagval)；//結(jié)構(gòu)復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval和imagval值55數(shù)據(jù)結(jié)構(gòu)(2)第55頁floatGetReal(cpmplexZ)；//返回復(fù)數(shù)Z實(shí)部值float

GetImag(cpmplexZ)；//返回復(fù)數(shù)Z虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2和56數(shù)據(jù)結(jié)構(gòu)(2)第56頁//-----基本操作實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個(gè)復(fù)數(shù)z1,z2和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

…..//{其它省略}57數(shù)據(jù)結(jié)構(gòu)(2)第57頁1.4算法和算法分析一、算法二、算法設(shè)計(jì)標(biāo)準(zhǔn)三、算法效率衡量方法和準(zhǔn)則四、算法存放空間需求58數(shù)據(jù)結(jié)構(gòu)(2)第58頁一、算法何謂“算法”？

算法是對問題求解過程一個(gè)描述，是為處理某一個(gè)或一類問題而給出一個(gè)確定、有限長操作序列（求解步驟）。嚴(yán)格說來，一個(gè)算法必須滿足以下五個(gè)主要特征：1．有窮性2．確定性3．可行性4．有輸入5．有輸出59數(shù)據(jù)結(jié)構(gòu)(2)第59頁1．有窮性

對于任意一組正當(dāng)輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，也即算法中每個(gè)步驟都能在有限時(shí)間內(nèi)完成。注意：

1).兩重意思：即算法中操作步驟為有限個(gè)，且每個(gè)步驟都能在適當(dāng)有限時(shí)間內(nèi)完成。2).算法區(qū)分于程序：算法可轉(zhuǎn)化為程序，程序不含有有窮性。算法五個(gè)主要特征（五要素1）：60數(shù)據(jù)結(jié)構(gòu)(2)第60頁注意：確定性表現(xiàn)在對算法中每一步描述都沒有二義性，只要輸入相同，初始狀態(tài)相同，則不論執(zhí)行多少遍，所得結(jié)果都應(yīng)該相同。

2．確定性：

在任何情況下，算法中每一步都應(yīng)定義明確無誤，不存在二義性（在某種條件下，存在兩種可能）。即對于每種情況下所應(yīng)執(zhí)行操作，在算法中都有確切要求，使算法執(zhí)行者或閱讀者都能明確其含義及怎樣執(zhí)行。而且在任何條件下，算法都只有一條執(zhí)行路徑。算法五個(gè)主要特征（五要素2）：61數(shù)據(jù)結(jié)構(gòu)(2)第61頁3．可行性

算法中全部操作都必須足夠基本，都能夠經(jīng)過已經(jīng)實(shí)現(xiàn)基本操作運(yùn)算有限次實(shí)現(xiàn)之。4．有輸入（0個(gè)或多個(gè)）

輸入量值即為算法操作對象。有些輸入量需要在算法執(zhí)行過程中輸入，而有由算法本身生成.

判斷:一個(gè)算法有0個(gè)輸入并不表示它沒有輸入值.62數(shù)據(jù)結(jié)構(gòu)(2)第62頁

5．有輸出（最少有一個(gè)）

它是一組與“輸入”有確定關(guān)系量值，是算法進(jìn)行信息加工后得到結(jié)果，這種確定關(guān)系即為算法功效。63數(shù)據(jù)結(jié)構(gòu)(2)第63頁二、算法設(shè)計(jì)標(biāo)準(zhǔn)設(shè)計(jì)算法時(shí)，通常應(yīng)考慮到達(dá)以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存放量需求64數(shù)據(jù)結(jié)構(gòu)(2)第64頁1．正確性(Correctness)

首先，算法應(yīng)該滿足以特定“規(guī)格說明”方式給出需求。

其次，對算法是否“正確”了解能夠有以下四個(gè)層次：a．程序中不含語法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求結(jié)果；65數(shù)據(jù)結(jié)構(gòu)(2)第65頁

c．程序?qū)τ诰倪x擇、經(jīng)典、苛刻且?guī)в械箅y性幾組輸入數(shù)據(jù)能夠得出滿足要求結(jié)果；

通常以第c層意義正確性作為衡量一個(gè)算法是否合格標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺姓?dāng)輸入數(shù)據(jù)都能得出滿足要求結(jié)果；66數(shù)據(jù)結(jié)構(gòu)(2)第66頁2.可讀性(Readability)

算法主要是為了人閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，所以算法應(yīng)該易于人理解；其次，艱澀難讀程序易于隱藏較多錯(cuò)誤而難以調(diào)試。注：在算法是正確前提下，算法可讀性是擺在第一位，這在當(dāng)今大型軟件需要多人合作完成環(huán)境下是非常重要。即便是個(gè)人開發(fā)亦是如此。67數(shù)據(jù)結(jié)構(gòu)(2)第67頁3．健壯性(Robustness)

當(dāng)輸入數(shù)據(jù)非法時(shí)，算法應(yīng)該恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行對應(yīng)處理，而不是產(chǎn)生莫名奇妙輸出結(jié)果。而且，處理犯錯(cuò)方法不應(yīng)是由中止程序執(zhí)行，而應(yīng)向調(diào)用它函數(shù)返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)值，方便在更高抽象層次上進(jìn)行處理。68數(shù)據(jù)結(jié)構(gòu)(2)第68頁4．高效率與低存放量需求

通常，效率指是算法執(zhí)行時(shí)間；存放量指是算法執(zhí)行過程中所需最大存放空間。二者都與問題規(guī)模相關(guān)。－高效率與低存放量需求往往是相互矛盾69數(shù)據(jù)結(jié)構(gòu)(2)第69頁三、算法效率衡量方法和準(zhǔn)則通常有兩種衡量算法效率方法:簡略事后統(tǒng)計(jì)法算法→程序→計(jì)算執(zhí)行時(shí)間事前分析估算法在算法執(zhí)行前，粗略估算其運(yùn)行時(shí)間缺點(diǎn)：1．必須執(zhí)行程序（耗時(shí)、輕易陷入盲目境地DS）2．其它原因(軟硬件)掩蓋算法本質(zhì)優(yōu)點(diǎn):一個(gè)問題有各種解法，能夠預(yù)先比較各種算法，方便均衡利弊而從中選優(yōu)。

70數(shù)據(jù)結(jié)構(gòu)(2)第70頁與算法執(zhí)行時(shí)間相關(guān)原因：1．算法選取策略2．問題規(guī)模3．編寫程序語言4．編譯程序產(chǎn)生機(jī)器代碼質(zhì)量5．計(jì)算機(jī)執(zhí)行指令速度（大、小型機(jī)）顯然，后三條受著計(jì)算機(jī)硬件和軟件制約，與算法本身無關(guān)，既然是算法"估算"，僅需考慮前兩條。

71數(shù)據(jù)結(jié)構(gòu)(2)第71頁

通常，一個(gè)特定算法執(zhí)行時(shí)間－“運(yùn)行工作量”大小，是隨問題規(guī)模增加而增加，只依賴于問題規(guī)模（通慣用整數(shù)量n表示），或者說，它是問題規(guī)模n函數(shù)f(n)。72數(shù)據(jù)結(jié)構(gòu)(2)第72頁

衡量不一樣算法優(yōu)劣不在于對某個(gè)特定大小問題做比較，應(yīng)該以其隨問題規(guī)模增加而“增加趨勢”為準(zhǔn)則。稱這種算法執(zhí)行時(shí)間度量為算法漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度，記作為：T(n)=O(f(n))

稱T(n)為算法(漸近)時(shí)間復(fù)雜度。它表示伴隨問題規(guī)模n增加，算法執(zhí)行時(shí)間增加率和f(n)增加率相同，把T(n)作為算法時(shí)間度量。算法漸近時(shí)間復(fù)雜度O()73數(shù)據(jù)結(jié)構(gòu)(2)第73頁

說明：“O”數(shù)學(xué)含義是，若存在兩個(gè)常量C和n0，當(dāng)n>n0時(shí)，|T(n)|≤C|f(n)|,則記作：T(n)=O(f(n))它表明算法執(zhí)行時(shí)間是和f(n)“同數(shù)量級”74數(shù)據(jù)結(jié)構(gòu)(2)第74頁怎樣估算算法時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作

（固有數(shù)據(jù)類型操作）算法執(zhí)行時(shí)間=∑原操作(i)執(zhí)行次數(shù)×原操作(i)執(zhí)行時(shí)間

算法執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和

成正比

例：i=1;K=0;①for(i=1;i<=n;i++)

k=k+i;②print(k);③75數(shù)據(jù)結(jié)構(gòu)(2)第75頁例：分析以下程序段時(shí)間復(fù)雜度。i=1;K=0;①For(i=1;i<=n;i++)

k=k+i;②該算法運(yùn)行時(shí)間由程序中全部語句頻度（即該語句重復(fù)執(zhí)行次數(shù)）之和組成。解：分析：顯然，語句①頻度是1。設(shè)語句2頻度是n，則有：所以該程序段時(shí)間復(fù)雜度T(n)=

O(1+n)=O(n)算法時(shí)間復(fù)雜度是由嵌套最深層語句頻度