數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計（第二版）課件全套（張小艷） 第1-9章 緒論、線性表-排序

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計引言2計算機系統(tǒng)軟件和應(yīng)用軟件都用到各種類型的數(shù)據(jù)結(jié)構(gòu)引言輸入若干學(xué)生信息，按成績降序排序之后輸出；輸入姓名，查找學(xué)生信息分析問題：抽象處理對象信息及相應(yīng)操作問題操作的對象—學(xué)生信息（用數(shù)據(jù)類型表示數(shù)據(jù)）3structstudent{intnum;charname[20];……floatscore;}stu[30];引言操作：輸入、排序、查找、輸出用函數(shù)實現(xiàn)4初始化函數(shù)片段…….for(i=0;i<n;i++){scanf("%d",&stu[i].num);…….gets(stu[i].name);scanf("%f",&stu[i].score);}…….引言5路徑尋優(yōu)問題引言6從V0到V4的最優(yōu)路徑深度優(yōu)先遍歷、廣度優(yōu)先遍歷引言

數(shù)據(jù)結(jié)構(gòu)的任務(wù)：把現(xiàn)實世界中的問題以特定的數(shù)據(jù)類型和特定的存儲結(jié)構(gòu)保存到計算機內(nèi)存中，以及在此基礎(chǔ)上為實現(xiàn)某些功能（操作）設(shè)計有效的算法。7程序：數(shù)據(jù)的存儲(數(shù)據(jù)個體及個體之間的關(guān)系)

數(shù)據(jù)的操作（算法）可以被計算機執(zhí)行的語言9課程目的：學(xué)會分析和研究需解決的實際問題中的相關(guān)數(shù)據(jù)的特性為其選擇合適的數(shù)據(jù)結(jié)構(gòu)來描述在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上寫出處理問題的相應(yīng)的算法對算法進行相應(yīng)的分析教材：

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計張小艷李占利等主編數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計實踐與題解第一章緒論1946年2月14日，世界上第一臺電腦ENIAC在美國賓夕法尼亞大學(xué)誕生。目的是用來計算炮彈彈道，它的計算速度快，每秒可從事5000次的加法運算，運作了九年之久。10課程簡介

隨著計算機科學(xué)與技術(shù)的不斷發(fā)展，計算機的應(yīng)用領(lǐng)域已不再局限于科學(xué)計算，而更多地應(yīng)用于控制、管理等非數(shù)值處理領(lǐng)域。

處理的數(shù)據(jù)也由純粹的數(shù)值發(fā)展到字符、表格、圖形、圖象、聲音等具有一定結(jié)構(gòu)的數(shù)據(jù)，處理的數(shù)據(jù)量也越來越大非數(shù)值數(shù)據(jù)處理問題無法用數(shù)學(xué)方程式描述的。課程簡介非數(shù)值數(shù)據(jù)處理問題課程簡介這就給程序設(shè)計帶來一個問題：

應(yīng)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系（結(jié)構(gòu)）。從非數(shù)字計算應(yīng)用問題的現(xiàn)象中提煉問題的本質(zhì)對專業(yè)知識理解與應(yīng)用的同時加強學(xué)生利用辯證思想中的本質(zhì)論解決具體問題從唯物辯證法的基本范疇之現(xiàn)象與本質(zhì)的辯證關(guān)系課程研究對象：非數(shù)值數(shù)據(jù)在計算機中的處理課程簡介1968年克努思教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計算機程序設(shè)計藝術(shù)》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。70年代初，出現(xiàn)了大型程序，軟件也開始相對獨立，結(jié)構(gòu)化程序設(shè)計成為程序設(shè)計方法學(xué)的主要內(nèi)容，人們越來越重視“數(shù)據(jù)結(jié)構(gòu)”認為程序設(shè)計的實質(zhì)是對具體問題選擇一種好的結(jié)構(gòu)，加上設(shè)計好的算法。

數(shù)據(jù)結(jié)構(gòu)+算法=程序70年代初，數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程開始進入大學(xué)課堂。14課程簡介數(shù)據(jù)結(jié)構(gòu)是算法實現(xiàn)的基礎(chǔ)，算法總是要依賴于某種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。1.2什么是數(shù)據(jù)結(jié)構(gòu)由計算機處理問題的兩個問題：信息的表示，信息的處理。而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著計算機應(yīng)用的普及，處理信息量的增加，及處理信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當復(fù)雜。為了有效的運用計算機解決實際問題，需要透過現(xiàn)象看本質(zhì)，利用辯證思想中的本質(zhì)論解決具體問題，提取出待解決問題的特征，提煉出相應(yīng)的處理數(shù)據(jù)對象及各個對象之間的關(guān)系；然后將其存儲到計算機中；進而設(shè)計一個“好”的處理方法（算法），最后編制程序解決問題。這就是數(shù)據(jù)結(jié)構(gòu)課程所要研究的問題。1.2什么是數(shù)據(jù)結(jié)構(gòu)

描述客觀事物的符號，是信息的載體，它是能夠被計算機識別、存儲和加工處理的對象。

1.數(shù)據(jù)非數(shù)值類型1.2什么是數(shù)據(jù)結(jié)構(gòu)一是可以輸入到計算機中；

一是能被計算機程序處理。數(shù)值型數(shù)據(jù)，可以進行數(shù)值計算；

文字類字符，就需要進行非數(shù)值的處理；

聲音、圖像、視頻等，通過編碼的手段將他們變成字符數(shù)據(jù)來處理。

描述客觀事物的符號，是信息的載體，它是能夠被計算機識別、存儲和加工處理的對象。

1.數(shù)據(jù)1.2什么是數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)元素與數(shù)據(jù)項數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位，是數(shù)據(jù)集合的個體，在計算機中通常作為一個整體進行考慮和處理。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。在計算機中通常把數(shù)據(jù)元素作為一個整體進行考慮和處理。書號書名編著出版社出版時間庫存量101高等數(shù)學(xué)華羅庚電子工業(yè)出版社2010-01300102計算機網(wǎng)絡(luò)孫科名清華大學(xué)出版社2010-01320103軟件工程程海帆西安電子科技大學(xué)2010-01230104數(shù)據(jù)結(jié)構(gòu)張小艷西安電子科技大學(xué)2010-01206105高等數(shù)學(xué)樊映川同濟大學(xué)出版社·····················圖書管理系統(tǒng)數(shù)據(jù)數(shù)據(jù)元素書號書名編著出版社出版時間庫存量101高等數(shù)學(xué)華羅庚電子工業(yè)出版社2010-01300102計算機網(wǎng)絡(luò)孫科名清華大學(xué)出版社2010-01320103軟件工程程海帆西安電子科技大學(xué)2010-01230104數(shù)據(jù)結(jié)構(gòu)張小艷西安電子科技大學(xué)2010-01206105高等數(shù)學(xué)樊映川同濟大學(xué)出版社·····················數(shù)據(jù)項一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，也把數(shù)據(jù)項稱為數(shù)據(jù)元素的域、字段、關(guān)鍵字。數(shù)據(jù)圖書管理系統(tǒng)1.2什么是數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)元素與數(shù)據(jù)項具有相同性質(zhì)的數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象，它是數(shù)據(jù)的一個子集數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。3數(shù)據(jù)對象1.2什么是數(shù)據(jù)結(jié)構(gòu)例如，(1)字母字符數(shù)據(jù)對象的集合C={'A','B',…,'Z'}，它是字符數(shù)據(jù)的一個子集；(2)偶數(shù)數(shù)據(jù)對象的集合N={0,±2,±4,…}是整數(shù)數(shù)據(jù)的子集；(3)圖書管理表中的書的信息是圖書數(shù)據(jù)的子集。在具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)(元素值不一定相等)，且屬于同一數(shù)據(jù)對象(數(shù)據(jù)元素類)。數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。書號書名編著出版社出版時間101高等數(shù)學(xué)華羅庚電子工業(yè)出版社2010-01102數(shù)據(jù)結(jié)構(gòu)張小艷西安電子科技大學(xué)2010-01103高等數(shù)學(xué)樊映川同濟大學(xué)出版社···具有相同性質(zhì)的數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象，它是數(shù)據(jù)的一個子集數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。數(shù)據(jù)對象數(shù)據(jù)對象數(shù)據(jù)對象3數(shù)據(jù)對象1.2什么是數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)，簡單理解就是關(guān)系；數(shù)據(jù)元素之間不是獨立的，而是存在特定關(guān)系的，將這種關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)簡單說就是：互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。有兩個要素：數(shù)據(jù)元素集合、關(guān)系的集合。二元組來表示：Data_Structure=(D，R)其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。數(shù)據(jù)結(jié)構(gòu)，分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。4數(shù)據(jù)結(jié)構(gòu)1.2什么是數(shù)據(jù)結(jié)構(gòu)

討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機中實現(xiàn)其所需的各種操作。數(shù)據(jù)結(jié)構(gòu)的操作與其具體問題要求有關(guān)?；镜牟僮髦饕幸韵聨追N：

插入、刪除、修改、查找、排序根據(jù)插入、刪除、修改、查找、排序等操作的特性，所有的操作可以分為兩大類：一類是加工型操作，其操作改變了結(jié)構(gòu)的值；另一類是引用型操作，其操作不改變結(jié)構(gòu)的值。1.2什么是數(shù)據(jù)結(jié)構(gòu)24數(shù)據(jù)結(jié)構(gòu)包含三部分：數(shù)據(jù)---特性（數(shù)據(jù)元素）數(shù)據(jù)（元素）之間的關(guān)系---邏輯關(guān)系、物理關(guān)系數(shù)據(jù)集合上的一組操作---算法

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象、對象之間的關(guān)系以及在此之上的一系列操作的學(xué)科。1.2什么是數(shù)據(jù)結(jié)構(gòu)指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

現(xiàn)實世界中事物之間的關(guān)聯(lián)關(guān)系表像上紛亂復(fù)雜，但是透過現(xiàn)象看本質(zhì)，事物之間的關(guān)系可分為四種：事物之間相互獨立（沒有關(guān)系）;一對一的關(guān)系;一對多的關(guān)系;任意兩個之間都可能存在關(guān)系（多對多）。指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。(1)集合結(jié)構(gòu)：數(shù)據(jù)元素間的關(guān)系是“屬于同一個集合”。

(a)集合結(jié)構(gòu)邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)書號書名編著出版社出版時間101高等數(shù)學(xué)華羅庚電子工業(yè)出版社2010-01102數(shù)據(jù)結(jié)構(gòu)張小艷西安電子科技大學(xué)2010-01103高等數(shù)學(xué)樊映川同濟大學(xué)出版社···學(xué)號姓名籍貫性別學(xué)院1801李明陜西男計算機1802張華河南男計算機1803李雪江蘇女計算機指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對一的關(guān)系。(b)線性結(jié)構(gòu)邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的關(guān)系。賈府賈源賈代善賈敏林黛玉賈政賈環(huán)探春寶玉賈桂元春賈珠賈蘭賈赦迎春賈璉巧姐賈演賈代化賈敬惜春賈珍賈蓉指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)在我們中國，家譜約有三千年之攸久歷史，素來與國史，方志并稱為三大歷史文獻，是華夏民族的一種特有的用以記載著在同宗共祖下的世系人物文獻和事跡的志系圖籍。通過家譜，可使子孫后輩知悉祖先的淵源、人口、遷徙、分布、名人傳略、故事傳說、先賢史跡等等。通過家譜，可激勵子孫后輩傳承家族美德，發(fā)揚優(yōu)良傳統(tǒng)，賡續(xù)家族源流。(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的關(guān)系。賈府賈源賈代善賈敏林黛玉賈政賈環(huán)探春寶玉賈桂元春賈珠賈蘭賈赦迎春賈璉巧姐賈演賈代化賈敬惜春賈珍賈蓉指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

族譜就是一個家族所有人員構(gòu)成的大名單。而這個名單中的成員并不是雜亂羅列的，而是一個用血緣聯(lián)系起來的系統(tǒng)。按照嫡系繼承的原則，通過繪制世系表，依次將各代各輩記錄下來。通過繪制家譜樹，記錄家族成員的相互關(guān)系。家譜樹，是一種描繪家庭關(guān)系的樹狀結(jié)構(gòu)圖，樹中的每個成員可以清楚的知道自己的家族起源、家族關(guān)系以及其他成員的基礎(chǔ)信息。在族譜中，把其中的每一個成員都視為系統(tǒng)的一個要素，他們按照“祖—父—子—孫”的關(guān)系構(gòu)成了一個樹狀結(jié)構(gòu)。(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的關(guān)系。賈府賈源賈代善賈敏林黛玉賈政賈環(huán)探春寶玉賈桂元春賈珠賈蘭賈赦迎春賈璉巧姐賈演賈代化賈敬惜春賈珍賈蓉指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的關(guān)系。賈府賈源賈代善賈敏林黛玉賈政賈環(huán)探春寶玉賈桂元春賈珠賈蘭賈赦迎春賈璉巧姐賈演賈代化賈敬惜春賈珍賈蓉(c)樹形結(jié)構(gòu)指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)(4)圖形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對多的關(guān)系。(d)圖形結(jié)構(gòu)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)指在抽象的層面上數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)集合結(jié)構(gòu)：元素屬于或不屬于同一個集合線性結(jié)構(gòu)：元素之間存在著一對一的關(guān)系。樹形結(jié)構(gòu)：元素之間存在著一對多的關(guān)系。圖狀結(jié)構(gòu)：元素之間存在著多對多的關(guān)系。

集合線形表樹圖1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)邏輯結(jié)構(gòu)

物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式，是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，包括數(shù)據(jù)元素的存儲及元素之間關(guān)系的組織。數(shù)據(jù)的存儲結(jié)構(gòu)要能正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。如何存儲數(shù)據(jù)元素之間的關(guān)系，是實現(xiàn)物理結(jié)構(gòu)的重點和難點。

2.存儲結(jié)構(gòu)（又稱物理結(jié)構(gòu)）1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)數(shù)據(jù)基本的存儲結(jié)構(gòu)：順序存儲、鏈式存儲

順序存儲是把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中。

鏈式存儲對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針字段來表示。1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)36

順序存儲結(jié)構(gòu)是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元中，其數(shù)據(jù)元素之間的邏輯關(guān)系和物理位置一致。（a1,a2,a3,……,an）順序存儲結(jié)構(gòu)線性結(jié)構(gòu)structstudent{intnum;charname[20];……floatscore;}stu[30];1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)37鏈式存儲結(jié)構(gòu)例如，百家姓的部分姓氏表(zhao,qian,sun,li,zhou,wu,zheng,wang)1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)食品族譜–樹形結(jié)構(gòu)381.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)交通圖–圖形結(jié)構(gòu)391.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)數(shù)據(jù)類型是指一個值的集合和定義在這個值集上的一組操作的總稱。1.4抽象數(shù)據(jù)類型1、數(shù)據(jù)類型

數(shù)據(jù)類型決定了數(shù)據(jù)占內(nèi)存的字節(jié)數(shù)、數(shù)據(jù)的取值范圍、可進行的操作。例如，C語言中

inta,b;規(guī)定了變量a、b在內(nèi)存中所占的字節(jié)數(shù)、取值范圍以及施加于a、b上的運算。在使用int類型時，既不需要了解在計算機內(nèi)部是如何表示的，也不需要知道其操作如何實現(xiàn)。如a?+?b，設(shè)計者僅僅關(guān)注其“數(shù)學(xué)上求和”的抽象特征。我們可以將數(shù)據(jù)類型進一步抽象，即抽象數(shù)據(jù)類型。數(shù)據(jù)類型是指一個值的集合和定義在這個值集上的一組操作的總稱。1.4抽象數(shù)據(jù)類型1、數(shù)據(jù)類型

數(shù)據(jù)類型決定了數(shù)據(jù)占內(nèi)存的字節(jié)數(shù)、數(shù)據(jù)的取值范圍、可進行的操作。

抽象數(shù)據(jù)類型(AbstractDataType，ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。

是將“數(shù)據(jù)”、“結(jié)構(gòu)”、“處理操作”封裝在一起而形成的復(fù)合體。抽象數(shù)據(jù)類型實際上就是對數(shù)據(jù)結(jié)構(gòu)的邏輯定義。2、抽象數(shù)據(jù)類型

1.4抽象數(shù)據(jù)類型例如，將與有序表有關(guān)的數(shù)據(jù)和處理操作封裝成一個ADT，包含數(shù)據(jù)元素及其關(guān)系，操作有初始建表、插入、刪除、查找，其描述如下：ADTOrdList//OrdList為抽象數(shù)據(jù)類型的名字

{數(shù)據(jù)對象：D?=?{ai|ai∈ElemSet,i=1,2,…,n,n≥0}//ElemSet為數(shù)據(jù)元素集合數(shù)據(jù)關(guān)系：R?=?{<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：

InitList(&L) //構(gòu)造一個空的有序表LListLength(L) //輸出L中數(shù)據(jù)元素個數(shù)

LocateElem(L,e) //在表L中查找與給定值e相等的元素

ListInsert(&L,i,e) //在表L中第i個位置之前插入新的數(shù)據(jù)元素eListDelete(*L,i,*e) //刪除表L的第i個數(shù)據(jù)元素

}ADTOrdList2、抽象數(shù)據(jù)類型

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

實現(xiàn)ADT的方法有三種：封裝法、分散法、半封裝法。

封裝法：數(shù)據(jù)及其操作封裝成一個整體，比如C++?中的類。分散法：將數(shù)據(jù)和處理數(shù)據(jù)的函數(shù)各自分開。無法從程序的物理結(jié)構(gòu)(即代碼的物理次序)上區(qū)分哪些數(shù)據(jù)和函數(shù)屬于哪個ADT。例如，用一個數(shù)組elem[?]存儲棧中的元素，再用一個整型變量top表示棧頂位置，其操作用一個一個的函數(shù)實現(xiàn)。

datatypeelem[MAXSIZE];inttop;3、抽象數(shù)據(jù)類型的實現(xiàn)方法

1.4抽象數(shù)據(jù)類型半封裝法：將數(shù)據(jù)和為處理數(shù)據(jù)需要而定義的相關(guān)變量封裝在一起形成一個結(jié)構(gòu)，有關(guān)處理函數(shù)定義在結(jié)構(gòu)之外。這種方法僅做到了對數(shù)據(jù)存儲結(jié)構(gòu)的封裝，其特點介于封裝法和分散法之間。例如，實現(xiàn)棧的抽象數(shù)據(jù)類型時，我們把存儲棧中元素的數(shù)組elem[]?和棧頂位置變量top封裝在一起，其操作函數(shù)實現(xiàn)如下：

#defineMAXSIZE<最大元素數(shù)>typedefstruct{datatypeelem[MAXSIZE];inttop;}SeqStack3、抽象數(shù)據(jù)類型的實現(xiàn)方法

1.4抽象數(shù)據(jù)類型用C語言編寫程序計算1?+?2?+?3?+?4?+?…?+?1001.5算法第一種算法：

main(){inti,sum=0,n=100;

for(i=1;i<n;i++)sum=sum+i;printf(″%d″,sum);

}用C語言編寫程序計算1?+?2?+?3?+?4?+?…?+?100sum?=1?+??2??+??3??+…+100sum?=?100+?99?+?98?+…+12*sum=?101?+?101?+?101?+…+?101

共100個所以sum=5050。1.5算法第二種：

main(){inti,sum=0,n=100;

sum=(1+100)*100/2;printf(″%d″,sum);

}用C語言編寫程序計算1?+?2?+?3?+?4?+?…?+?1001.5算法第一種：

main(){inti,sum=0,n=100;

for(i=1;i<n;i++)sum=sum+i;printf(″%d″,sum);

}第二種：

main(){inti,sum=0,n=100;

sum=(1+100)*100/2;printf(″%d″,sum);

}繼續(xù)精益求精、努力創(chuàng)新！提高算法的效率！

算法的含義與程序十分相似，但又有區(qū)別。一個程序不一定滿足有窮性。例如操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中，因此操作系統(tǒng)不是一個算法。另一方面，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的求解過程，而程序則是算法在計算機上的特定的實現(xiàn)。

一個算法若用程序設(shè)計語言來描述，則它就是一個程序。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相成的。解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當與否直接影響算法的效率；反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行效果來體現(xiàn)。算法與程序1.5算法

算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。1.5.1算法的基本概念1.5算法

算法是獨立語言而存在的一種解決問題的方法和思想。對于一個特定的問題，我們總想-去尋找更好的解決方法，也就是算法。

百元買白雞1.5.1算法的基本概念1.5算法

請同學(xué)們看視頻課

1.3百元買白雞(1)有窮性：有限步驟之內(nèi)完成,不能形成無窮循環(huán)。(2)確定性：每一個步驟必須有確定含義,無二義性。(3)可行性：操作可通過已實現(xiàn)的基本運算執(zhí)行有限次完成。(4)輸入：有多個或0個輸入。(5)輸出：至少有一個或多個輸出。

算法的特性1.5算法算法要求

正確、可讀、健壯、高效率低存儲

1.5算法(1)正確。算法“正確”的含義大體上可分為四個層次：一是所設(shè)計的程序沒有語法錯誤；二是所設(shè)計的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；三是所設(shè)計的程序?qū)τ诰倪x擇的典型、苛刻而且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果；四是所設(shè)計的程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。對于這四層含義，其中達到第四層含義下的正確是極其困難的。一般情況下，以達到第三層含義的正確性作為衡量一個程序是否正確的標準。例如，要求n個數(shù)的最大值問題，算法如下：

max:=0;for(i=1;i<=n;i++)

{scanf(″%f″,&x);

if(x>max)max=x;

}

此算法無語法錯誤，請考慮，如果輸入的數(shù)全為負數(shù)時，會產(chǎn)生什么結(jié)果?其正確性達到了第幾層。1.5算法算法要求：正確、可讀、健壯、高效率低存儲

1.5算法

(2)可讀。算法首先應(yīng)該便于人們理解和相互交流，其次才是機器可執(zhí)行。所以一個算法應(yīng)當思路清晰，層次分明，簡單明了，易讀易懂。

(3)健壯。作為一個好的算法，當輸入不合法數(shù)據(jù)時，應(yīng)能適當?shù)刈龀稣_反應(yīng)或進行相應(yīng)的處理，而不至于產(chǎn)生一些莫名其妙的輸出結(jié)果。

(4)高效率低存儲。算法效率通常指算法的執(zhí)行時間。對于同一個問題如果有多個算法可以解決，執(zhí)行時間短的算法其效率高。所謂存儲量的要求，是指算法在執(zhí)行過程中所需要的最大存儲空間。這兩者都與問題規(guī)模有關(guān)。1.5.2算法的性能評價

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

算法的時間效率，大都指算法的執(zhí)行時間?？梢詫Σ煌惴ň幹瞥沙绦颍糜嬎銠C計時器，統(tǒng)計運行時間，進行比較，從而確定算法效率的高低。顯然這樣做是有缺陷的：(1)必須依據(jù)算法編制好程序，這通常需要花費大量的時間和精力，如果編制出來之后發(fā)現(xiàn)有很大缺陷，就會前功盡棄。(2)時間的比較依賴于計算機硬件和軟件的環(huán)境因素，有時會遮蓋算法本身的優(yōu)劣。(3)算法的測試數(shù)據(jù)設(shè)計困難，并且程序運行時間往往還與測試數(shù)據(jù)規(guī)模有很大關(guān)系，效率高的算法在小規(guī)模的測試數(shù)據(jù)面前往往得不到體現(xiàn)。1.5.2算法的性能評價

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

算法的時間效率，大都指算法的執(zhí)行時間?？梢詫Σ煌惴ň幹瞥沙绦?，利用計算機計時器，統(tǒng)計運行時間，進行比較，從而確定算法效率的高低。顯然這樣做是有缺陷的：(1)必須依據(jù)算法編制好程序，這通常需要花費大量的時間和精力，如果編制出來之后發(fā)現(xiàn)有很大缺陷，就會前功盡棄。(2)時間的比較依賴于計算機硬件和軟件的環(huán)境因素，有時會遮蓋算法本身的優(yōu)劣。(3)算法的測試數(shù)據(jù)設(shè)計困難，并且程序運行時間往往還與測試數(shù)據(jù)規(guī)模有很大關(guān)系，效率高的算法在小規(guī)模的測試數(shù)據(jù)面前往往得不到體現(xiàn)。（算法時間效率）√（算法空間效率-NEXT）如何評價算法的效率呢？算法時間效率的分析：在編制成計算機程序之前，依據(jù)統(tǒng)計方法進行估算假設(shè)每條語句執(zhí)行時間相同：t第i條語句的執(zhí)行次數(shù)：Ci一個算法是由一條條指令構(gòu)成的，算法的指令通常稱為語句算法的執(zhí)行時間:?Ci×t1.5算法59再來看看我們上節(jié)舉的例子，求1?+?2?+?3?+?4?+?…?+?100。用第一種方法：

main(){inti,sum=0,n=100;/*執(zhí)行1次*/for(i=1;i<=n;i++)/*執(zhí)行n+1次*/sum=sum+i;/*執(zhí)行n次*/printf(″%d″,sum);/*執(zhí)行1次*/}用第二種方法：

main(){inti,sum=0,n=100; /*執(zhí)行1次*/sum=(1+100)*100/2; /*執(zhí)行1次*/printf(″%d″,sum);/*執(zhí)行1次*/}算法執(zhí)行時間為(1+(n+1)+n+1)t=(2n+3)t算法執(zhí)行時間是(1+1+1)t=3t1.5算法兩種算法的第一句和最后一句是一樣的，我們關(guān)注的代碼其實是中間的那部分，我們把循環(huán)看做一個整體，忽略頭尾循環(huán)判斷的開銷，那么這兩個算法其實就是n和1的差距。

兩個n×n階矩陣相乘的算法。1for(i=0;i<n;i++) /*執(zhí)行n+1次*/2for(j=0;j<n;j++) /*執(zhí)行n*(n+1)次*/3{c[i][j]=0; /*執(zhí)行n2次*/4for(k=0;k<n;k++) /*執(zhí)行n2*(n+1)次*/5c[i][j]=c[i][j]+a[i][k]*b[k][j]; /*執(zhí)行n3次*/6}1.5算法

算法中語句的總的執(zhí)行次數(shù)為2n3?+?3n2?+?2n?+?1。顯然，算法執(zhí)行時間與語句的執(zhí)行次數(shù)成正比，我們可以用語句的執(zhí)行次數(shù)來描述算法的執(zhí)行時間?？梢钥闯?，算法的執(zhí)行時間是問題規(guī)模n的函數(shù)f(n)，n就是給定的問題規(guī)模。2.算法時間復(fù)雜度算法:控制結(jié)構(gòu)(順序、分支、循環(huán))+原操作1.5算法兩個n×n階矩陣相乘的算法。1for(i=0;i<n;i++) /*執(zhí)行n+1次*/2for(j=0;j<n;j++) /*執(zhí)行n*(n+1)次*/3{c[i][j]=0; /*執(zhí)行n2次*/4for(k=0;k<n;k++) /*執(zhí)行n2*(n+1)次*/5c[i][j]=c[i][j]+a[i][k]*b[k][j];/*執(zhí)行n3次*/6}算法執(zhí)行時間取決于兩者的綜合效果。

以原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。原操作2n3?+?3n2?+?2n?+?1引入漸進時間復(fù)雜度在數(shù)量上估計一個算法的執(zhí)行時間2.算法時間復(fù)雜度—漸進時間復(fù)雜度算法中語句的執(zhí)行次數(shù)T(n)，它是關(guān)于問題規(guī)模n的函數(shù)

進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(orderofmagnitude)。記作：T(n)?=?O(f(n))

表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。1.5算法兩個n×n階矩陣相乘的算法。1for(i=0;i<n;i++) /*執(zhí)行n+1次*/2for(j=0;j<n;j++) /*執(zhí)行n*(n+1)次*/3{c[i][j]=0; /*執(zhí)行n2次*/4for(k=0;k<n;k++) /*執(zhí)行n2*(n+1)次*/5c[i][j]=c[i][j]+a[i][k]*b[k][j];/*執(zhí)行n3次*/6}原操作2n3?+?3n2?+?2n?+?12.算法時間復(fù)雜度--漸進時間復(fù)雜度

在數(shù)量上估計一個算法的執(zhí)行時間

表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。1.5算法第一種：

main(){inti,sum=0,n=100;

for(i=1;i<n;i++)sum=sum+i;printf(″%d″,sum);

}第二種：

main(){inti,sum=0,n=100;

sum=(1+100)*100/2;printf(″%d″,sum);

}算法執(zhí)行時間為1+(n+1)+n+1=2n+3算法執(zhí)行時間是1+1+1=3表1.12n2、3n?+?1、2n2?+?3n?+?1的增長率次數(shù)算法A(2n2)算法B(3n?+?1)算法C(2n2?+?3n?+?1)n?=?1246n?=?28715n?=?1020031231n?=?10020?00030120?301n?=?10002?000?00030012?003?001n?=?10?000200?000?00030?001200?030?001n?=?100?00020?000?000?000300?00120?000?300?001n?=?1000?0002?000?000?000?0003?000?0012?000?003?000?001從表1.1的數(shù)據(jù)變化可以清楚地看到，當n值越來越大時，3n?+?1的增長和2n2相差甚遠，最終幾乎可以忽略不計。也就是說，隨著n的增大，2n2趨近于2n2?+?3n?+?1。結(jié)論：如果得出了基本操作執(zhí)行的次數(shù)的函數(shù)f(n)，判斷一個算法效率時，函數(shù)f(n)中的常數(shù)和其他次要項常?？梢院雎?，關(guān)注最高階的項即可。1.5算法表1.12n2、3n?+?1、2n2?+?3n?+?1的增長率次數(shù)算法A(2n2)算法B(3n?+?1)算法C(2n2?+?3n?+?1)n?=?1246n?=?28715n?=?1020031231n?=?10020?00030120?301n?=?10002?000?00030012?003?001n?=?10?000200?000?00030?001200?030?001n?=?100?00020?000?000?000300?00120?000?300?001n?=?1000?0002?000?000?000?0003?000?0012?000?003?000?0011.5算法忽略算法執(zhí)行時間公式中的低階項，抓住最高階這個主要因素，用它來表示算法的時間效率。

分析算法時間效率的策略：忽略細節(jié)，抓問題的本質(zhì)--抓主要矛盾！下面給出推導(dǎo)大O方法。第一步，找到原操作的執(zhí)行次數(shù)。第二步，用常數(shù)1取代運行時間中的所有加法常數(shù)。第三步，在修改后的執(zhí)行次數(shù)中，只保留最高階項。第四步，如果最高階項存在與這個項相乘的常數(shù)，則去掉這個常數(shù)。這樣就可得到大O階。1.5算法

(1)順序結(jié)構(gòu)的時間復(fù)雜度。

inti,sum=0,n=100; /*執(zhí)行1次*/sum=(1+100)*100/2; /*執(zhí)行1次*/printf(″%d″,sum); /*執(zhí)行1次*/這個算法的運行次數(shù)為f(n)?=?3。

順序結(jié)構(gòu)、分支結(jié)構(gòu)的程序，不管代碼有多少行，執(zhí)行次數(shù)不會隨著n的變化而發(fā)生變化，它與問題規(guī)模n的大小無關(guān)，執(zhí)行次數(shù)是恒定的，我們用O(1)來表示其時間復(fù)雜度。通常稱之為常量階。1.5算法(2)單循環(huán)結(jié)構(gòu)的時間復(fù)雜度。

for(i=1;i<n;i++) /*執(zhí)行n+1次*/sum=sum+i; /*原操作執(zhí)行n次*/其時間復(fù)雜度為O(n)，我們稱之為線性階。(3)多重循環(huán)結(jié)構(gòu)的時間復(fù)雜度。

for(i=1;i<=n;i++)

/*執(zhí)行n+1次*/for(j=1;j<=n;j++) /*執(zhí)行n+1次*/x=x+1; /*原操作執(zhí)行n2次*/其時間復(fù)雜度為O(n2)，我們稱之為平方階。如果是三重循環(huán)，其時間復(fù)雜度為O(n3)，我們稱之為立方階，以此類推。1.5算法當i

=

0時，內(nèi)循環(huán)執(zhí)行了n次，當i

=

1時，內(nèi)循環(huán)執(zhí)行了n-1次……當i

=

n-1時，執(zhí)行1次。所以總的執(zhí)行次數(shù)為n

+

(n-1)

+

(n-2)

+

…

+

1

=

n(n+1)/2

=

n2/2

+

n/2。用推導(dǎo)大O階的方法，第一，n2/2

+

n/2沒有加數(shù)常數(shù)，可以不予考慮；第二，保留最高項n2/2；第三，去掉這個項相乘的常數(shù)，最終得到n2，所以，這段代碼的時間復(fù)雜度為O(n2)。

inti,j;for(i=0;i<n;i++)for(j=i;j<n;j++)

x=x+1;/*原操作*/1.5算法(4)下面代碼時間復(fù)雜度又是多少?

intc=1;

while(c<n)

c=c*2;/*原操作*/

由于每次c乘以2之后，就離n更近，也就是說，多少個2相乘后大于n，才會退出循環(huán)。由2x

=

n得到x

=

lb

n。可以得出，循環(huán)的執(zhí)行次數(shù)為lb

n，時間復(fù)雜度為O(lb

n)。我們稱之為對數(shù)階。1.5算法(5)遞歸程序的時間復(fù)雜度的分析。

intBinrec(intn)

{ifn=1

return1;

else

returnBinrec(n/2)+1;/*原操作*/

}用A(n)表示所做的加法次數(shù)，建立遞推關(guān)系如下:設(shè)n?=?2k，當k?>?0時，A(2k)?=?A(2k-1)?+?1?=?[A(2k-2)?+?1]?+?1?=?A(2k-2)?+?2=?…?=?A(2k-i)?+?i?=?…?=?A(2k-k)?+?k?=?k

因為n?=?2k，所以k?=?lb?n。因此A(n)?=?lb?n。其時間復(fù)雜度為O(lb?n)我們稱之為對數(shù)階。1.5算法常用的時間復(fù)雜度：常量階O(1)、線性階O(n)、平方階O(n2)、對數(shù)階O(lb?n)。此外，算法還能呈現(xiàn)的時間復(fù)雜度有二維階O(n?lb?n)、立方階O(n3)、指數(shù)階O(2n)、階乘階O(n!)等，數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度關(guān)系如下：O(1)?<?O(lb?n)?<?O(n)?<?O(n?lb?n)?<?O(n2)?<?O(n3)?<?O(2n)?<?O(n!)?<?O(nn)常見的T(n)隨著問題規(guī)模n不斷增大時的變化情況。1.5算法地震預(yù)警系統(tǒng)中預(yù)測預(yù)報算法巖石圈地幔地核地球空間氣圈水圈計算機處理數(shù)據(jù)量越來越大，對算法效率的要求越來越高！有必要去追求提高算法效率嗎？

算法設(shè)計與優(yōu)化

學(xué)會抓主要矛盾-方法

樹立創(chuàng)新-意識

發(fā)揚精益求精、追求極致的工匠精神大數(shù)據(jù)、云計算基礎(chǔ)是分布式存儲、核心還是算法算法設(shè)計需要不斷創(chuàng)新與優(yōu)化知識給予力量

方法增長智慧1.5算法3.算法的最優(yōu)、最差與平均時間復(fù)雜度

算法的效率不僅依賴于問題的規(guī)模，還與問題的初始輸入數(shù)據(jù)集有關(guān)。例如，在數(shù)組a[1..n]?中查找值為k的元素，若找到，則輸出位置i(1≤i≤n)；否則輸出0。1.5算法

i=n;

while(i>0)&&(a[i]!=k)

i=i-1;printf(″%d″,i);while循環(huán)的執(zhí)行次數(shù)不僅與問題規(guī)模有關(guān)，還與k和數(shù)組a中各分量的取值有關(guān)。最壞情況下，即數(shù)組a中不含值為k的元素，while循環(huán)執(zhí)行n次；最好情況下，即數(shù)組中值為k的元素為a[n]，while循環(huán)執(zhí)行1次；平均情況下，while循環(huán)執(zhí)行(n+1)/2次，時間復(fù)雜度為線性階。

最優(yōu)時間復(fù)雜度是指在輸入規(guī)模為n時，算法在最優(yōu)情況下的時間復(fù)雜度。最差時間復(fù)雜度是指在輸入規(guī)模為n時，算法在最差情況下的時間復(fù)雜度。最差情況的運行時間是一種保證，那就是運行時間將不會再壞了。平均時間復(fù)雜度是指在“典型”或“隨機”輸入的情況下，算法具有的時間復(fù)雜度。

平均時間復(fù)雜度是從概率的角度進行分析的，研究它的直接方法就是將規(guī)模為n的實例劃分為幾種類型，需要得到或者假設(shè)各種輸入類型的概率分布，以便推導(dǎo)出基本操作的平均執(zhí)行次數(shù)。但是，這個方案的技術(shù)實現(xiàn)一般都不簡單，而且在各種特定的情況下，它所包含的概率假設(shè)也往往很難驗證。

如不作特殊說明，所討論的各種算法的時間復(fù)雜度均指最壞情況下的時間復(fù)雜度。1.5算法4.空間復(fù)雜度123…n-2n-1na[1]a[2]a[3]…a[n-2]a[n-1]a[n]123…n-2n-1na[n]a[n-1]a[n-2]…a[3]a[2]a[1]

類似于算法的時間復(fù)雜度，采用空間復(fù)雜度作為算法所需存儲空間的量度，記作：S(n)?=?O(f(n))其中n為問題的規(guī)模。在存儲空間使用方面，對于處理同一問題的不同算法，其對存儲空間的需求有較大的差異。例如：將存放在一維數(shù)組a中的n個整數(shù)反向存放，即原始數(shù)組a為反向存放后數(shù)組a為1.5算法

對于這一問題，可以用一組工作單元，即設(shè)置一個數(shù)組b[1..n]算法實現(xiàn)：

for(i=1;i<=n;i++)b[n-i+1]=a[i];for(i=1;i<=n;i++)a[i]=b[i];但也可以只使用一個工作單元temp，算法如下：

for(i=1;i<=n/2;i++){temp=a[i];a[i]=a[n-i+1];a[n-i+1]=temp;}顯然，采用后一種算法比前一種算法所需的存儲空間要節(jié)省得多。

一個程序的空間復(fù)雜度是指程序運行從開始到結(jié)束所需的存儲量。程序的一次運行是針對所求解的問題的某一特定實例而言的。程序運行所需的存儲空間包括以下兩部分：

(1)固定部分。這部分空間與所處理數(shù)據(jù)的大小和個數(shù)無關(guān)，或者稱與問題的實例的特征無關(guān)。主要包括程序代碼、常量、簡單變量、定長成分的結(jié)構(gòu)變量所占的空間。

(2)可變部分。這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。例如，100個數(shù)據(jù)元素的排序算法與1000個數(shù)據(jù)元素的排序算法所需的存儲空間顯然是不同的。

1.5.3算法描述

常用的算法描述方法有如下幾種：

(1)使用自然語言。

(2)使用流程圖。

(3)使用某種程序設(shè)計語言。

(4)使用類程序設(shè)計語言。本書采用類C語言作為算法描述工具，類C語言是一種偽碼語言。1.“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計”課程的地位是計算機專業(yè)中的一門專業(yè)基礎(chǔ)必修課,是一門理論與實踐相結(jié)合的課程。它是程序設(shè)計(特別是非數(shù)值計算的程序設(shè)計)的基礎(chǔ)，也是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。因此，“數(shù)據(jù)結(jié)構(gòu)”是數(shù)學(xué)、計算機硬件、計算機軟件三者之間的一門核心課程，是提高學(xué)生軟件設(shè)計水平的一門關(guān)鍵課程。該課程多年來一直是計算機相關(guān)專業(yè)研究生考試必考專業(yè)課之一，是反映學(xué)生數(shù)據(jù)抽象能力、編程能力的重要體現(xiàn)。1.6“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計”課程的地位及主要內(nèi)容2.“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計”課程的主要內(nèi)容名稱特點存儲結(jié)構(gòu)線性表數(shù)據(jù)元素之間的關(guān)系是一對一順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)棧插入操作和刪除操作位置在線性表的一端進行，具有先進后出的特點順序棧、鏈棧隊列插入操作在線性表的一端、刪除操作在線性表的另一端進行，具有后進先出的特點順序隊列、鏈隊列、循環(huán)隊列串

數(shù)據(jù)元素是字符的線性表，操作對象是數(shù)據(jù)元素的序列順序串、塊鏈結(jié)構(gòu)、堆存儲串數(shù)組線性表的推廣，數(shù)據(jù)元素可以是一個表，如二維數(shù)組、三維數(shù)組……

以行為主序或者以列為主序的順序存儲。特殊矩陣的壓縮存儲；稀疏矩陣的三元組表存儲、十字鏈表存儲廣義表

線性表的推廣，數(shù)據(jù)元素可以是一個表，也可以是一個元素

廣義表鏈式存儲樹

數(shù)據(jù)元素之間存在一對多的關(guān)系，具有清晰的層次關(guān)系

雙親表示法、孩子表示法、孩子鏈表表示法、孩子兄弟表示法二叉樹數(shù)據(jù)元素之間存在一對多的關(guān)系，具有清晰的層次關(guān)系。每個結(jié)點最多有兩個孩子結(jié)點，而且有序順序存儲結(jié)構(gòu)、二叉鏈表存儲結(jié)構(gòu)、三叉鏈表存儲結(jié)構(gòu)圖數(shù)據(jù)元素之間存在多對多的關(guān)系，也稱網(wǎng)狀結(jié)構(gòu)鄰接矩陣、鄰接表、十字鏈表、多重鄰接表(2)查找與排序。查找方法包含有：靜態(tài)查找表的查找方法(順序查找、折半查找、分塊查找)、動態(tài)查找表的查找方法(二叉排序樹、平衡二叉樹、B樹)、哈希表的查找。排序方法包括：簡單的排序方法(簡單選擇排序、直接插入排序、希爾排序、冒泡排序)、先進的排序方法(快速排序、歸并排序、堆排序)、基數(shù)排序方法。(3)經(jīng)典算法。經(jīng)典算法包括分治法、貪婪法、回溯法、動態(tài)規(guī)劃法。1本課程的特點學(xué)習(xí)方法學(xué)到的知識是死的，總有過時的時候。只有通過學(xué)習(xí)知識提高學(xué)習(xí)能力，才是立于不敗之地的保證。記筆記：好記性不如爛筆頭，通過動手加深理解和記憶。做作業(yè)、做上機題。3勤動手、多實踐、提高學(xué)習(xí)能力適應(yīng)飛速變化的技術(shù)的根本是注重基礎(chǔ)理論學(xué)習(xí)理論的演變是緩慢的、理論基礎(chǔ)是相通的相同的原理可以應(yīng)用于不同的技術(shù)2理論與技術(shù)的關(guān)系理論與實踐并重理論學(xué)習(xí)要嚴謹、方法掌握要靈活提高自學(xué)能力

在學(xué)習(xí)過程中，建議學(xué)生注意以下幾個方面：

(1)非數(shù)值計算，這是數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的應(yīng)用范圍。比如，學(xué)生信息管理中的學(xué)生信息，每個學(xué)生信息包含學(xué)號、姓名、性別、年齡等，無法用具體的數(shù)值表達。

(2)操作對象，具體問題中的數(shù)據(jù)及其表示的形式。比如，學(xué)生信息管理中的學(xué)生記錄就是操作對象。

(3)關(guān)系，即數(shù)據(jù)間的關(guān)系。比如，學(xué)生信息管理中的學(xué)生記錄之間可以按學(xué)號逐個表示到計算機中，學(xué)生記錄之間存在著線性關(guān)系。

(4)操作，即針對數(shù)據(jù)元素的操作。比如，學(xué)生信息管理中，查找、插入、刪除某個學(xué)生信息等。

(5)算法復(fù)雜度，即對操作實現(xiàn)的算法進行性能分析。有三種由硬件系統(tǒng)直接支持實現(xiàn)的基本數(shù)據(jù)類型：char型、int型、float型。C語言允許直接對存放變量的地址進行操作。如：inta，則&a表示a的地址，也稱指向變量a的指針。C語言復(fù)習(xí)可略講1)C語言的基本數(shù)據(jù)類型2)C語言的指針類型數(shù)組是同一類型的一組數(shù)據(jù)的集合。數(shù)組名代表了這一組數(shù)的起始地址。3)C語言的數(shù)組類型如：inta[10],*p;

在C語言中，沒有字符串變量，字符串是作為一維字符數(shù)組來處理的。4)C語言的字符串typedefstruct{charname[20];floatscore[5];floataverage;}student;studentstu1,stu2[100],*p;5)C語言的結(jié)構(gòu)體類型C語言的結(jié)構(gòu)體由一組稱為結(jié)構(gòu)體成員的項組成。定義一個結(jié)構(gòu)體類型變量由兩步組成。第一步，定義結(jié)構(gòu)體類型；第二步，定義結(jié)構(gòu)體類型變量。例如：structstudent{charname[20];floatscore[5];floataverage;};

structstudentstu1,stu2[100],*p;或?qū)懽鳎旱诙戮€性表數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計第一章復(fù)習(xí)1.教學(xué)目標

通過線性表的學(xué)習(xí)，熟悉本書對每種數(shù)據(jù)結(jié)構(gòu)的描述方法，掌握線性表的定義、特點、典型算法及實際中的實用。2.教學(xué)要求①了解線性表的邏輯結(jié)構(gòu)特性。②熟練掌握線性表的兩種存儲結(jié)構(gòu)的描述方法。③熟練掌握線性表在順序存儲結(jié)構(gòu)上基本操作的實現(xiàn)④熟練掌握線性表在各種鏈式存儲結(jié)構(gòu)上基本操作的實現(xiàn)；⑤能夠從時間和空間復(fù)雜度的角度比較線性表兩種存儲結(jié)構(gòu)的特點第二章線性表3．教學(xué)重點：①線性表順序存儲結(jié)構(gòu)的特點及基本操作。②線性表鏈式存儲結(jié)構(gòu)的特點及基本操作。4．教學(xué)難點：①鏈表的概念。②鏈式存儲結(jié)構(gòu)上算法的實現(xiàn)。第二章線性表2.1線性表的定義及邏輯結(jié)構(gòu)2.1.1線性表的定義例2-1中華傳統(tǒng)文化經(jīng)典:二十四節(jié)氣。二十四節(jié)氣蘊含著中華民族悠久的文化內(nèi)涵和歷史積淀。在漫長的農(nóng)耕社會中，二十四節(jié)氣發(fā)揮著重要作用，擁有豐富的文化內(nèi)涵。2.1線性表的定義及邏輯結(jié)構(gòu)2.1.1線性表的定義例2-1中華傳統(tǒng)文化經(jīng)典:二十四節(jié)氣。二十四節(jié)氣歌訣：

立春雨水漸，驚蟄蟲不眠，春分近清明，采茶谷雨前；

立夏小滿足，芒種大開鐮，夏至才小暑，大暑三伏天；

立秋處暑去，白露南飛雁，秋分寒露至，霜降紅葉染；

立冬小雪飄，大雪兆豐年，冬至數(shù)九日，小寒又大寒。

節(jié)氣歌唱出了節(jié)氣的順序。一年中的節(jié)氣羅列出來如下：【立春

雨水

驚蟄

春分

清明

谷雨

立夏

小滿

芒種

夏至

小暑

大暑

立秋

處暑

白露

秋分寒露霜降立冬小雪大雪冬至小寒大寒】2.1線性表的定義及邏輯結(jié)構(gòu)2.1.1線性表的定義線性表——是n個相同類型數(shù)據(jù)元素組成的有限序列。記作：（a1,a2,…，ai-1，ai，ai+1，…，an）

其中a1稱作起始結(jié)點，

an稱作終端結(jié)點。i稱為ai在線性表中的位置或序號。

n為表長，n=0時，稱為空表。2.1線性表的定義及邏輯結(jié)構(gòu)

例2-2計算機學(xué)院學(xué)院從2008年到2013年擁有的學(xué)生人數(shù)的變化情況表：

(800，1000，2000，3600，3800，4500)

（a1,a2,…，ai-1，ai，ai+1，…，an）

從數(shù)據(jù)可以看到，我們學(xué)院在迅速發(fā)展。例2-3、

在校學(xué)生的健康信息表是一個線性表，表中每個學(xué)生的信息由學(xué)號、姓名、性別、年齡、班級和健康狀況等組成學(xué)號姓名性別年齡班級健康狀況1204101錢小明男19計科12健康1204108周維男18計科12一般1204111楊麗女20計科12健康1204112趙武男23計科12差………………1204135張麗女17計科12一般2.1線性表的定義及邏輯結(jié)構(gòu)

數(shù)據(jù)元素ai(1≤i≤n)只是一個抽象的符號，其具體含義在不同的情況下可以不同，可以是一個節(jié)氣，可以是一個數(shù)字，可以是一個學(xué)生信息。共同的特點就是：一個線性表中的數(shù)據(jù)元素必須屬于同一數(shù)據(jù)對象。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

線性表是由n(n≥0)個數(shù)據(jù)類型相同的數(shù)據(jù)元素a1，a2，…，ai-1，ai，ai+1，…，an組成的有限序列，通常記為：表中相鄰元素間存在著順序關(guān)系，對于任一對相鄰結(jié)點

<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼對于ai，當i=2,…,n時，有且僅有一個直接前趨ai-1；當i=1,2,…,n-1時，有且僅有一個直接后繼ai+1；而a1是表中第一個元素，它沒有直接前趨；an是表中最后一個元素，它沒有直接后繼。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

線性表是由n(n≥0)個數(shù)據(jù)類型相同的數(shù)據(jù)元素組成的有限序列，通常記為：<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

“二十四節(jié)氣”中節(jié)氣的時間<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

“每年學(xué)生人數(shù)”位置計算機學(xué)院學(xué)院從2008年到2013年擁有的學(xué)生人數(shù)的變化情況表：

(800，1000，2000，3600，3800，4500)<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

“每個學(xué)生信息”表中數(shù)值順序很重要，也不能隨意變換。這是線性表的基本要求，就如同國家有法律，學(xué)校有規(guī)章制度，家庭有規(guī)則，我們必須遵守規(guī)則、遵紀守法。學(xué)號姓名性別年齡班級健康狀況1204101錢小明男19計科12健康1204108周維男18計科12一般1204111楊麗女20計科12健康1204112趙武男23計科12差………………1204135張麗女17計科12一般線性表的特點：線性表由同一類型的數(shù)據(jù)元素組成，每個ai必須屬于同一數(shù)據(jù)類型。線性表中的數(shù)據(jù)元素個數(shù)是有限的，表長就是表中數(shù)據(jù)元素的個數(shù)。存在唯一的“第一個”數(shù)據(jù)元素；存在唯一的“最后一個”數(shù)據(jù)元素。除第一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素均有且只有一個前驅(qū)元素。除最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素均有且只有一個后繼元素。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

2.1.2線性表的基本操作

(1)初始化InitList(L)

(2)線性表判空EmptyList(L)

(3)求長度LengthList(L)

(4)取元素函數(shù)GetList(L,i)

(5)按值查找LocatList(L,x)

(6)插入操作InsertList(L,i,x)

(7)刪除操作DeleteList(L,i)2.1線性表的定義及邏輯結(jié)構(gòu)

（a1,a2,…，ai-1，ai，ai+1，…，an）

2.2線性表的順序存儲結(jié)構(gòu)2.2.1順序表

線性表的順序存儲結(jié)構(gòu)是指在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，元素之間的邏輯關(guān)系通過存儲位置來反映，用這種存儲形式存儲的線性表稱其為順序表。設(shè)a1的存儲地址為Loc(a1)，每個數(shù)據(jù)元素占L個存儲單元，則第i個數(shù)據(jù)元素的地址為：Loc(ai)=Loc(a1)+(i-1)×L1≤i≤n

按數(shù)據(jù)元素的序號隨機存取線性表的順序存儲結(jié)構(gòu)可用C語言定義如下：#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];

intlast;}

SeqList;

SeqList

L;線性表中最后一個元素在數(shù)組中的位置存放數(shù)據(jù)元素

順序存儲結(jié)構(gòu)三個重要屬性：存儲數(shù)據(jù)元素的空間：數(shù)組elem，用于存放數(shù)據(jù)元素。線性表的最大容量：MAXSIZE。線性表當前長度：由last+1確定，last：最后一個數(shù)據(jù)元素在數(shù)組中的下標。2.2線性表的順序存儲結(jié)構(gòu)細節(jié)決定成?。。?！線性表的順序存儲結(jié)構(gòu)可用C語言定義如下：#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];

intlast;}

SeqList;

SeqList

L;線性表中最后一個元素在數(shù)組中的位置存放數(shù)據(jù)元素

2.2線性表的順序存儲結(jié)構(gòu)細節(jié)決定成?。。?！強調(diào)兩個問題：“數(shù)組的長度”和“線性表的長度”兩個概念。注意區(qū)分數(shù)據(jù)元素的位序和數(shù)組的下標。SeqList*L

；SeqList

L;表長：L.last+1數(shù)據(jù)元素：L.elem[0]~L.elem[L.last]表長：（*L）.last+1或L->last+1數(shù)據(jù)元素：L->elem[0]~L->elem[L->last]2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];intlast;}

SeqList;

細節(jié)決定成?。。?！2.2.2順序表上插入與刪除操作的實現(xiàn)1初始化main(){inti,len;SeqListL;L.last=-1;scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L.elem[i]);

L.last++;}………}2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.2順序表上插入與刪除操作的實現(xiàn)1初始化main(){inti,len;SeqList*L;L.last=-1;scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L->elem[i]);

L->last++;}………}2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.2順序表上插入與刪除操作的實現(xiàn)1初始化SeqList*InitList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;returnL;}主函數(shù)對初始化函數(shù)的調(diào)用：main(){inti,len;SeqList*L;L=InitList();scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L->elem[i]);

L->last++;}……………}2.2線性表的順序存儲結(jié)構(gòu)本算法的主要運算是比較。2按值查找intLocatList(SeqList*L,datatypex){inti=0;

while(i<=L->last&&L->elem[i]!=x)i++;

if(i>L->last)return-1;elsereturni;/*返回的是存儲位置*/

}平均時間復(fù)雜度：

假設(shè)查找每個元素的概率相等：1/n;查找第i個的比較次數(shù)：i平均比較次數(shù)為:

(1+2+3+4+…+n)/n=(n+1)/2，時間復(fù)雜度為O(n)。2.2線性表的順序存儲結(jié)構(gòu)最好的比較次數(shù)為1次，最差的是比較n次。3插入運算線性表的插入是指在表的第i個位置上插入一個值為x的新元素,i的取值范圍為1≤i≤n+1。③修改last指針（相當于修改表長），

使之仍指向最后一個元素。步驟：①將ai～an

順序向下移動，

為新元素讓出位置；②將x置