數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程（第3版）課件 第1、2章 概論、線性表

數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程（第3版）高等學(xué)校數(shù)據(jù)結(jié)構(gòu)課程系列教材1/105數(shù)據(jù)結(jié)構(gòu)教材介紹第1章概論1.1數(shù)據(jù)結(jié)構(gòu)概述1.2算法和算法分析1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)第1章概論2/1051.1數(shù)據(jù)結(jié)構(gòu)概述1.1.1什么是數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)數(shù)據(jù)運(yùn)算的一般過程：

數(shù)據(jù)是信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理，數(shù)據(jù)包括文字、表格、圖像等。

信息是數(shù)據(jù)的內(nèi)涵，即數(shù)據(jù)所表達(dá)的意義。1.1數(shù)據(jù)結(jié)構(gòu)概述3/105數(shù)據(jù)的基本單位是數(shù)據(jù)元素（有時(shí)稱為結(jié)點(diǎn)、記錄等），通常把數(shù)據(jù)元素作為一個(gè)整體進(jìn)行處理。例如，一個(gè)班的學(xué)生數(shù)據(jù)包括張三、李四等數(shù)據(jù)元素。

一個(gè)學(xué)生數(shù)據(jù)張三，男，101班李四，計(jì)科系，北京……數(shù)據(jù)元素1.1數(shù)據(jù)結(jié)構(gòu)概述4/105

數(shù)據(jù)對(duì)象是具有相同類型的數(shù)據(jù)元素的集合，因?yàn)樗袛?shù)據(jù)元素類型相同時(shí)處理起來更加方便，所以在數(shù)據(jù)結(jié)構(gòu)中除特別指定外數(shù)據(jù)通常都是數(shù)據(jù)對(duì)象。一個(gè)學(xué)生數(shù)據(jù)對(duì)象張三，男，101班李四，男，102班……相同類型的數(shù)據(jù)元素姓名性別班號(hào)1.1數(shù)據(jù)結(jié)構(gòu)概述5/105

有時(shí)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也可稱為字段、域、屬性）組成。

數(shù)據(jù)項(xiàng)是具有獨(dú)立意義的不可分割的最小標(biāo)識(shí)單位。

例如在1～100的整數(shù)數(shù)據(jù)中，10就是一個(gè)數(shù)據(jù)元素；又比如在一個(gè)學(xué)生表中，一個(gè)學(xué)生記錄可稱為一個(gè)數(shù)據(jù)元素，而這個(gè)元素中的某一字段（如姓名）就是一個(gè)數(shù)據(jù)項(xiàng)。一個(gè)學(xué)生數(shù)據(jù)對(duì)象張三，男，101班李四，男，102班……相同類型的數(shù)據(jù)元素姓名性別班號(hào)1.1數(shù)據(jù)結(jié)構(gòu)概述6/105

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。這些數(shù)據(jù)元素不是孤立存在的，而是有著某種關(guān)系，這種關(guān)系構(gòu)成了某種結(jié)構(gòu)。在數(shù)據(jù)結(jié)構(gòu)中主要討論數(shù)據(jù)元素之間的相鄰關(guān)系數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)+結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)可以看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合1.1數(shù)據(jù)結(jié)構(gòu)概述7/105邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系的整體。它是數(shù)據(jù)結(jié)構(gòu)在用戶面前呈現(xiàn)的形式。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。運(yùn)算：施加在該數(shù)據(jù)上的操作。數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)方面：1.1數(shù)據(jù)結(jié)構(gòu)概述8/1051.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)的視角：邏輯結(jié)構(gòu)+運(yùn)算定義存儲(chǔ)結(jié)構(gòu)運(yùn)算實(shí)現(xiàn)用戶視角程序員視角數(shù)據(jù)結(jié)構(gòu)9/105例如一個(gè)學(xué)生成績(jī)表Score，它由多個(gè)學(xué)生成績(jī)記錄（即數(shù)據(jù)元素）組成，每個(gè)元素又包括多個(gè)數(shù)據(jù)項(xiàng)，其中學(xué)號(hào)數(shù)據(jù)項(xiàng)是關(guān)鍵字，即學(xué)號(hào)唯一標(biāo)識(shí)一個(gè)學(xué)生記錄。現(xiàn)求計(jì)算所有學(xué)生的平均分。邏輯結(jié)構(gòu)表示學(xué)號(hào)姓名分?jǐn)?shù)201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功901.1數(shù)據(jù)結(jié)構(gòu)概述10/105

Score的數(shù)據(jù)運(yùn)算是求所有學(xué)生的平均分。

為了實(shí)現(xiàn)這個(gè)功能，先要設(shè)計(jì)對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)，即把Score表存放到計(jì)算機(jī)內(nèi)存中，然后設(shè)計(jì)出實(shí)現(xiàn)求平均分的算法。數(shù)據(jù)運(yùn)算的描述數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)1.1數(shù)據(jù)結(jié)構(gòu)概述11/105數(shù)據(jù)元素之間的邏輯關(guān)系的整體稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，這里的邏輯關(guān)系主要指數(shù)據(jù)元素之間的相鄰關(guān)系。

根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同特性，分為下列4類基本結(jié)構(gòu)。1.1.2邏輯結(jié)構(gòu)集合：包含的所有數(shù)據(jù)元素同屬于一個(gè)集合（最松散的關(guān)系）。線性結(jié)構(gòu)：包含的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。樹形結(jié)構(gòu)：包含的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。圖形結(jié)構(gòu)：包含的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。也稱為網(wǎng)狀結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)概述12/105數(shù)據(jù)的邏輯結(jié)構(gòu)可以采用多種方式描述，二元組是一種既常用也十分通用的數(shù)據(jù)邏輯結(jié)構(gòu)表示方式。二元組表示如下：S=(D，R)D={di

|1≤i≤n}R={rj

|1≤j≤m}D是數(shù)據(jù)元素的有限集合，即D是由有限個(gè)數(shù)據(jù)元素（簡(jiǎn)稱為元素）所構(gòu)成的集合。R是D上的關(guān)系的有限集合，即R是由有限個(gè)關(guān)系rj（1≤j≤m）所構(gòu)成的集合。rj是指從D→D的關(guān)系。1.1數(shù)據(jù)結(jié)構(gòu)概述13/105每個(gè)關(guān)系rj用序偶集合來表示。一個(gè)序偶表示兩個(gè)元素的關(guān)系。用尖括號(hào)表示有向關(guān)系，如<a,b>表示存在元素a到b的關(guān)系。用圓括號(hào)表示無向關(guān)系，如（a,b）表示既存在元素a到b的關(guān)系，又存在元素b到a的關(guān)系。

S=(D，R)D={di

|1≤i≤n}R={rj

|1≤j≤m}1.1數(shù)據(jù)結(jié)構(gòu)概述ab<a,b>ab(a,b)14/105設(shè)rj是一個(gè)D到D的關(guān)系，rj∈R。若元素d，d'∈D，且<d,d'>∈rj，則稱d'是d的后繼元素，d是d'的前驅(qū)元素，這時(shí)d和d'是相鄰的元素（都是相對(duì)rj而言的）。如果不存在一個(gè)d'使<d,d'>∈rj，則稱d為rj的終端元素。如果不存在一個(gè)d'使<d',d>∈rj，則稱d為rj的開始元素。如果d既不是終端元素也不是開始元素，則稱d是內(nèi)部元素。1.1數(shù)據(jù)結(jié)構(gòu)概述abcda是b的前驅(qū)b是a的后繼a為開始元素d為終端元素b、c為內(nèi)部元素15/105學(xué)號(hào)姓名分?jǐn)?shù)201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功90學(xué)生成績(jī)表Score開始元素:沒有前驅(qū)元素終端元素:沒有后繼元素其他所有元素都只有一個(gè)前驅(qū)元素和一個(gè)后繼元素這個(gè)表的邏輯結(jié)構(gòu)為線性結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)概述16/105實(shí)際上，Score表完整地描述了該數(shù)據(jù)的邏輯結(jié)構(gòu)，也可以用二元組表示其邏輯結(jié)構(gòu)如下（用學(xué)號(hào)表示相應(yīng)的元素）：Score=(D，R)D={201201，201202，201204，201205，201206}R={r} //只有一個(gè)邏輯關(guān)系r={<201201,201205>，201205,201206>，<201206,201202>，<201202,201204>}學(xué)號(hào)姓名分?jǐn)?shù)201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功90學(xué)生成績(jī)表Score1.1數(shù)據(jù)結(jié)構(gòu)概述17/105【例1.1】設(shè)數(shù)據(jù)的邏輯結(jié)構(gòu)如下：B1=(D,R)D={1,2,3,4,5,6,7,8,9}R={r}r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}試畫出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出哪些是開始結(jié)點(diǎn)，哪些是終端結(jié)點(diǎn)，說明是何種數(shù)據(jù)結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)概述18/105解：畫出B1對(duì)應(yīng)的邏輯結(jié)構(gòu)圖。123467958B1=(D,R)D={1,2,3,4,5,6,7,8,9}R={r}r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}1.1數(shù)據(jù)結(jié)構(gòu)概述19/1051是開始結(jié)點(diǎn)。2、6、8、9是終端結(jié)點(diǎn)。除開始結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有唯一的前驅(qū)結(jié)點(diǎn)。除終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有一個(gè)或多個(gè)后繼結(jié)點(diǎn)。123467958一種樹形結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)概述20/105【例1.2】設(shè)數(shù)據(jù)的邏輯結(jié)構(gòu)如下：B2=(D,R)D={1,2,3,4,5,6}R={r}r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}試畫出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，說明是何種數(shù)據(jù)結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)概述21/105214356解：畫出B2對(duì)應(yīng)的邏輯結(jié)構(gòu)圖。B2=(D,R)D={1,2,3,4,5,6}R={r}r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}1.1數(shù)據(jù)結(jié)構(gòu)概述22/105每個(gè)結(jié)點(diǎn)都零個(gè)或多個(gè)前驅(qū)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都零個(gè)或多個(gè)后繼結(jié)點(diǎn)214356一種圖形結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)概述23/1051.1.3存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。

通常情況下，同一種邏輯結(jié)構(gòu)可以設(shè)計(jì)多種存儲(chǔ)結(jié)構(gòu)，在不同的存儲(chǔ)結(jié)構(gòu)中，實(shí)現(xiàn)同一種運(yùn)算的算法可能不同。

邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)映射1.1數(shù)據(jù)結(jié)構(gòu)概述24/105邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算三者之間的關(guān)系：運(yùn)算的定義邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)映射運(yùn)算的實(shí)現(xiàn)將邏輯結(jié)構(gòu)映射為存儲(chǔ)結(jié)構(gòu)時(shí)，存儲(chǔ)邏輯結(jié)構(gòu)中的：所有元素。元素之間的關(guān)系。1.1數(shù)據(jù)結(jié)構(gòu)概述25/105主要的幾種存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)采用一組連續(xù)的存儲(chǔ)單元存放所有的數(shù)據(jù)元素。邏輯上相鄰的元素的存儲(chǔ)單元也相鄰。也就是說，元素之間的邏輯關(guān)系由存儲(chǔ)單元地址間的關(guān)系隱含表示，即順序存儲(chǔ)結(jié)構(gòu)將數(shù)據(jù)的邏輯結(jié)構(gòu)直接映射到存儲(chǔ)結(jié)構(gòu)。1．順序存儲(chǔ)結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)概述26/105順序存儲(chǔ)結(jié)構(gòu)可實(shí)現(xiàn)對(duì)各數(shù)據(jù)元素的隨機(jī)存取。即順序存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存取特性。隨機(jī)存取是指給定某元素的邏輯序號(hào)i，能在常量時(shí)間內(nèi)查找到對(duì)應(yīng)的元素值。1.1數(shù)據(jù)結(jié)構(gòu)概述27/105假設(shè)每個(gè)元素占用30個(gè)字節(jié)，且從100號(hào)單元開始由低地址向高地址方向存儲(chǔ)。地址學(xué)號(hào)姓名分?jǐn)?shù)100201201王實(shí)85130201205李斌82160201206劉英92190201202張山78220201204陳功90學(xué)號(hào)姓名分?jǐn)?shù)201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功90Score對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)所有元素的存儲(chǔ)地址是連續(xù)的通過存儲(chǔ)關(guān)系直接反映邏輯關(guān)系特點(diǎn)1.1數(shù)據(jù)結(jié)構(gòu)概述28/1052．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)單獨(dú)存儲(chǔ)，無需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放相鄰結(jié)點(diǎn)的存儲(chǔ)地址。1.1數(shù)據(jù)結(jié)構(gòu)概述29/105學(xué)號(hào)姓名分?jǐn)?shù)201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功90Score對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)地址學(xué)號(hào)姓名分?jǐn)?shù)下一個(gè)結(jié)點(diǎn)地址┆100201201王實(shí)85520┆230201204陳功90∧┆310201206劉英92450┆450201202張山78230┆520201205李斌82310┆1.1數(shù)據(jù)結(jié)構(gòu)概述30/105每個(gè)結(jié)點(diǎn)存放一個(gè)學(xué)生成績(jī)記錄。每個(gè)結(jié)點(diǎn)附加一個(gè)“下一個(gè)結(jié)點(diǎn)地址”即后繼指針域，用于存放后繼結(jié)點(diǎn)的首地址。head作為第一個(gè)結(jié)點(diǎn)的地址來標(biāo)識(shí)整個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。head201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功90∧更形象的圖示所有結(jié)點(diǎn)的地址不一定連續(xù)。一個(gè)結(jié)點(diǎn)的所有成員占用一片連續(xù)空間增加指針域來表示元素之間的邏輯關(guān)系特點(diǎn)1.1數(shù)據(jù)結(jié)構(gòu)概述31/1053．索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)=數(shù)據(jù)表

+索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式為：

（關(guān)鍵字，對(duì)應(yīng)地址）其中“對(duì)應(yīng)地址”為該關(guān)鍵字的記錄在數(shù)據(jù)表中的存儲(chǔ)地址。索引表中所有關(guān)鍵字有序排列（如遞增）。1.1數(shù)據(jù)結(jié)構(gòu)概述32/1051.1數(shù)據(jù)結(jié)構(gòu)概述地址學(xué)號(hào)姓名分?jǐn)?shù)100201201王實(shí)85130201205李斌82160201206劉英92190201202張山78220201204陳功90數(shù)據(jù)表索引表地址關(guān)鍵字對(duì)應(yīng)地址300201201100310201202190320201204220330201205130340201206160Score的索引存儲(chǔ)結(jié)構(gòu)在進(jìn)行關(guān)鍵字（如學(xué)號(hào)）查找時(shí)：先在索引表中快速查找（因?yàn)樗饕碇邪搓P(guān)鍵字有序排列，可以采用二分查找）到相應(yīng)的關(guān)鍵字。然后通過對(duì)應(yīng)地址在數(shù)據(jù)表中找到該記錄的數(shù)據(jù)。33/105索引存儲(chǔ)結(jié)構(gòu)特點(diǎn)：通過索引表按關(guān)鍵字查找速度快增加索引表

存儲(chǔ)空間較大1.1數(shù)據(jù)結(jié)構(gòu)概述34/1054．哈希（散列）存儲(chǔ)結(jié)構(gòu)哈希存儲(chǔ)結(jié)構(gòu)=哈希函數(shù)+解決沖突方法。哈希函數(shù)H(key)將關(guān)鍵字為key的元素存放在該地址。查找關(guān)鍵字為key的元素時(shí)，先計(jì)算H(key)，由該值和解決沖突方法來確定其存儲(chǔ)地址。1.1數(shù)據(jù)結(jié)構(gòu)概述35/105key201201201205201206201202201204H(key)04513學(xué)號(hào)姓名分?jǐn)?shù)201201王實(shí)85201205李斌82201206劉英92201202張山78201204陳功90哈希表長(zhǎng)度m=6（存儲(chǔ)單元的地址為0～5）記錄個(gè)數(shù)n=5哈希函數(shù)：H(學(xué)號(hào))=學(xué)號(hào)-2012011.1數(shù)據(jù)結(jié)構(gòu)概述36/105Score哈希存儲(chǔ)結(jié)構(gòu)地址學(xué)號(hào)姓名分?jǐn)?shù)0201201王實(shí)851201202張山7823201204陳功904201205李斌825201206劉英92key201201201205201206201202201204H(key)04513特點(diǎn)按關(guān)鍵字查找速度快需要解決沖突1.1數(shù)據(jù)結(jié)構(gòu)概述37/1051.1.4數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算就是施加于數(shù)據(jù)的操作。

這種將運(yùn)算定義和運(yùn)算實(shí)現(xiàn)相互分離的做法具體軟件工程的思想，更加便于軟件開發(fā)。運(yùn)算定義（或運(yùn)算描述）：確定運(yùn)算的功能，是抽象的。運(yùn)算實(shí)現(xiàn)：在存儲(chǔ)結(jié)構(gòu)上確定對(duì)應(yīng)運(yùn)算實(shí)現(xiàn)算法，是具體的。1.1數(shù)據(jù)結(jié)構(gòu)概述38/1051.1.5數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型

數(shù)據(jù)結(jié)構(gòu)是指帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，包括數(shù)據(jù)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算。

1、數(shù)據(jù)結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)概述39/105

數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語言中的一個(gè)基本概念，用于指定變量數(shù)據(jù)的存儲(chǔ)方式。數(shù)據(jù)類型是一組性質(zhì)相同的值的集合和定義在此集合上的一組操作的總稱。shortint-32768～32767+-*/%…2、數(shù)據(jù)類型1.1數(shù)據(jù)結(jié)構(gòu)概述40/105C/C++語言中常用的數(shù)據(jù)類型（1）C/C++語言的基本數(shù)據(jù)類型int型：

可以有3個(gè)修飾符：short（短整數(shù)）、long（長(zhǎng)整數(shù)）和unsigned（無符號(hào)整數(shù)）float型double型char型1.1數(shù)據(jù)結(jié)構(gòu)概述41/105

數(shù)據(jù)類型用于定義變量，如有定義語句：intn=10;在執(zhí)行該語句時(shí)系統(tǒng)自動(dòng)為變量n分配一個(gè)固定長(zhǎng)度（如4個(gè)字節(jié)）的內(nèi)存空間。10n程序員通過變量名n對(duì)這個(gè)內(nèi)存空間進(jìn)行存取操作!當(dāng)超出作用范圍時(shí)系統(tǒng)自動(dòng)釋放其內(nèi)存空間，所以稱之為自動(dòng)變量。1.1數(shù)據(jù)結(jié)構(gòu)概述42/105（2）C/C++語言的指針類型C/C++語言允許直接對(duì)存放變量的地址進(jìn)行操作。例如：inti=2;int*p=&i;2ip&ii的存儲(chǔ)地址1.1數(shù)據(jù)結(jié)構(gòu)概述43/105可以使用malloc()函數(shù)為一個(gè)指針變量分配一片連續(xù)的空間（稱為動(dòng)態(tài)空間分配）。char*p;p=(char*)malloc(10*sizeof(char));

//動(dòng)態(tài)分配10個(gè)連續(xù)的字符空間strcpy(p,"China"); //將"China"存放到p所指向的空間中printf("%c\n",*p); //輸出字符Cprintf("%s\n",p); //輸出字符串"China"free(p); //釋放p指向的空間p1個(gè)地址空間，通常4字節(jié)10個(gè)字符空間大小China\0ChinaC計(jì)算機(jī)屏幕1.1數(shù)據(jù)結(jié)構(gòu)概述44/105pp的值和p指向的空間是不同的p的值存放指向空間的起始地址p指向的空間沒有名稱，不能直接操作，只能用p間接操作45/105（3）C/C++語言的數(shù)組類型數(shù)組是同一數(shù)據(jù)類型的一組數(shù)據(jù)的有限序列。數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組名標(biāo)識(shí)一個(gè)數(shù)組，下標(biāo)指示一個(gè)數(shù)組元素在該數(shù)組中的位置。數(shù)組下標(biāo)的最小值稱為下界，在C語言中總是為0。數(shù)組下標(biāo)的最大值稱為上界，在C語言中數(shù)組上界為數(shù)組長(zhǎng)度減1。例如，inta[10]定義了包含10個(gè)整數(shù)的數(shù)組a，其數(shù)組元素是a[0]～a[9]。1.1數(shù)據(jù)結(jié)構(gòu)概述46/105（4）C/C++語言中的結(jié)構(gòu)體類型結(jié)構(gòu)體是由一組稱為結(jié)構(gòu)體成員的數(shù)據(jù)項(xiàng)組成的。每個(gè)結(jié)構(gòu)體成員都有自已的標(biāo)識(shí)符，也稱為數(shù)據(jù)成員域。structteacher

//教師結(jié)構(gòu)體類型{intno; //成員編號(hào)，占4個(gè)字節(jié)charname[8]; //成員姓名，占8個(gè)字節(jié)intage; //成員年齡，占4個(gè)字節(jié)};1.1數(shù)據(jù)結(jié)構(gòu)概述47/105

結(jié)構(gòu)體類型是用于定義結(jié)構(gòu)體變量的，當(dāng)定義一個(gè)結(jié)構(gòu)體類型的變量時(shí)，系統(tǒng)按照結(jié)構(gòu)體類型聲明為對(duì)應(yīng)的變量分配存儲(chǔ)空間。structteachert;structteacher {intno;charname[8];intage;};t.not.aget1.1數(shù)據(jù)結(jié)構(gòu)概述48/105（5）C/C++語言中的共用體類型

共用體用于把不同的數(shù)據(jù)成員組織為一個(gè)整體，它們?cè)趦?nèi)存中共享一段存儲(chǔ)單元，但不同成員以不同的方式被解釋。uniontag

//tag共用體{shortintn; //成員n，占2個(gè)字節(jié)charch[2]; //成員ch數(shù)組，占2個(gè)字節(jié)};1.1數(shù)據(jù)結(jié)構(gòu)概述49/105

共用體類型是用于定義共用體變量的，當(dāng)定義一個(gè)共用體類型的變量時(shí)，系統(tǒng)按照共用體類型聲明為對(duì)應(yīng)的變量分配存儲(chǔ)空間。uniontagu;u.n=0x4142; //十六進(jìn)制數(shù)printf("%c,%c\n",u.ch[1],u.ch[0]);uniontag{shortintn;charch[2]; };u.nuu.chch[1]ch[0]AB計(jì)算機(jī)屏幕0x41420x410x421.1數(shù)據(jù)結(jié)構(gòu)概述50/105（6）C語言中的自定義類型C/C++語言中允許使用typedef關(guān)鍵字為一個(gè)數(shù)據(jù)類型指定一個(gè)別名，例如：該語句將char類型與ElemType等同起來。這樣做有兩個(gè)好處:typedefcharElemType;方便程序調(diào)試，例如，將上述語句改為typedefintElemType，則程序中所有ElemType都改為int類型了?？梢院?jiǎn)化代碼。1.1數(shù)據(jù)結(jié)構(gòu)概述51/105typedefstructstudent //student結(jié)構(gòu)體類型{intno; //學(xué)號(hào)成員charname[10]; //姓名成員charsex; //性別成員intcno; //班號(hào)成員}StudType; //用StudType別名表示student結(jié)構(gòu)體類型StudTypes1,s2;structstudents1,s2;等同1.1數(shù)據(jù)結(jié)構(gòu)概述52/105抽象數(shù)據(jù)類型（ADT）是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。定義一個(gè)抽象數(shù)據(jù)類型時(shí)，需要給出其名稱和各運(yùn)算名稱及其功能描述。抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型（高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型）來實(shí)現(xiàn)。3、抽象數(shù)據(jù)類型1.1數(shù)據(jù)結(jié)構(gòu)概述53/105從數(shù)據(jù)結(jié)構(gòu)的角度看，一個(gè)求解問題可以通過抽象數(shù)據(jù)類型來描述。

也就是說，抽象數(shù)據(jù)類型（ADT）對(duì)一個(gè)求解問題從邏輯上進(jìn)行了準(zhǔn)確的定義，所以抽象數(shù)據(jù)類型由數(shù)據(jù)邏輯結(jié)構(gòu)和運(yùn)算定義兩部分組成。抽象數(shù)據(jù)類型（ADT）=數(shù)據(jù)邏輯結(jié)構(gòu)+運(yùn)算定義1.1數(shù)據(jù)結(jié)構(gòu)概述54/105

【例1.4】定義單個(gè)集合的抽象數(shù)據(jù)類型ASet，其中所有元素為正整數(shù)，包含創(chuàng)建一個(gè)集合、輸出一個(gè)集合和判斷一個(gè)元素是否為集合中元素的基本運(yùn)算。在此基礎(chǔ)上再定義兩個(gè)集合運(yùn)算的抽象數(shù)據(jù)類型BSet，包含集合的并集、差集和交集運(yùn)算。1.1數(shù)據(jù)結(jié)構(gòu)概述55/105（1）抽象數(shù)據(jù)類型ASet的定義如下：ADTASet{

數(shù)據(jù)對(duì)象：D={di

|0≤i≤n，n為一個(gè)正整數(shù)}運(yùn)算的定義： voidcset(&s,a,n)：由含n個(gè)元素的數(shù)組a創(chuàng)建一個(gè)集合s。 voiddispset(s)：輸出集合s。 intinset(s,e)：判斷元素e是否為集合s中的元素。}1.1數(shù)據(jù)結(jié)構(gòu)概述56/105（2）抽象數(shù)據(jù)類型BSet的定義如下：ADTBSet{

數(shù)據(jù)對(duì)象：D={si∈ASet|0≤i≤n，n為一個(gè)正整數(shù)}

運(yùn)算的定義：voidadd(s1,s2,s3)：s3=s1∪s2

//求集合的并集voidsub(s1,s2,s3)：s3=s1-s2

//求集合的差集voidintersection(s1,s2,s3)：s3=s1∩s2

//求集合的交集}1.1數(shù)據(jù)結(jié)構(gòu)概述57/1051.2算法和算法分析1.2.1算法及其描述一個(gè)運(yùn)算實(shí)現(xiàn)是通過算法來表述的。算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。1.2算法和算法分析58/105算法設(shè)計(jì)應(yīng)滿足以下幾條目標(biāo)：正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要也是最基本的標(biāo)準(zhǔn)?？墒褂眯裕阂笏惴軌蚝芊奖愕厥褂?。這個(gè)特性也叫做用戶友好性?？勺x性：算法應(yīng)該易于人的理解，也就是可讀性好。為了達(dá)到這個(gè)要求，算法的邏輯必須是清晰的、簡(jiǎn)單的和結(jié)構(gòu)化的。健壯性：要求算法具有很好的容錯(cuò)性，即提供異常處理，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。不經(jīng)常出現(xiàn)異常中斷或死機(jī)現(xiàn)象。高效率與低存儲(chǔ)量需求。好的時(shí)間空間效率。1.2算法和算法分析59/105算法有以下5個(gè)重要特性。有限性：一個(gè)算法必須總是（對(duì)任何合法的輸入值）在執(zhí)行有限步之后結(jié)束，且每一步都可在有限時(shí)間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義，不會(huì)產(chǎn)生二義性。可行性：算法中每一條運(yùn)算都必須是足夠基本的，就是說它們?cè)瓌t上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運(yùn)算就能完成。輸入性：一個(gè)算法有零個(gè)或多個(gè)輸入。輸出性：一個(gè)算法有一個(gè)或多個(gè)輸出。1.2算法和算法分析60/105

這兩段描述均不能滿足算法的特性，試問它們違反了算法的哪些特性？【例1.6】有下列兩段描述：描述1： 描述2：voidexam1() voidexam2(){intn=2; {

intx,y;

while(n%2==0)

y=0;n=n+2; x=5/y;printf("%d\n",n);printf("%d,%d\n",x,y);} }1.2算法和算法分析61/105描述1是一個(gè)死循環(huán)，違反了算法的有限性特性。1.2算法和算法分析62/105描述1： 描述2：voidexam1() voidexam2(){intn=2; {

intx,y;

while(n%2==0)

y=0;n=n+2; x=5/y;printf("%d\n",n);printf("%d,%d\n",x,y);} }描述2出現(xiàn)除零錯(cuò)誤，違反了算法的可行性特性。1.2算法和算法分析63/105描述1： 描述2：voidexam1() voidexam2(){intn=2; {

intx,y;

while(n%2==0)

y=0;n=n+2; x=5/y;printf("%d\n",n);printf("%d,%d\n",x,y);} }描述算法的方式很多，有的采用類PASCAL語言，有的采用自然語言。本書采用C/C++語言來描述算法的實(shí)現(xiàn)過程，通常采用C/C++函數(shù)來描述算法。

算法如何描述？1.2算法和算法分析64/105

以設(shè)計(jì)求1+2+…+n值的算法為例說明C/C++語言描述算法的一般形式，該算法如下所示。1.2算法和算法分析intSum1(intn,ints){inti;if(n<=0)return0; //當(dāng)參數(shù)錯(cuò)誤時(shí)返回假s=0;for(i=1;i<=n;i++) s+=i;return1; //當(dāng)參數(shù)正確并產(chǎn)生正確結(jié)果時(shí)返回真}算法的返回值：正確執(zhí)行時(shí)返回真，否則返回假算法的形參65/105通常用函數(shù)返回值表示算法能否正確執(zhí)行，另外還可以帶有形參。任何算法（用函數(shù)描述）都是被調(diào)用的（在C/C++語言中除main函數(shù)外任何一個(gè)函數(shù)都會(huì)被其他函數(shù)調(diào)用，如何一個(gè)函數(shù)不被調(diào)用，這樣的函數(shù)是沒有意義的）。

1.2算法和算法分析66/105

C/C++語言中調(diào)用函數(shù)時(shí)只有從實(shí)參到形參的單向值傳遞，執(zhí)行函數(shù)時(shí)若改變了形參而對(duì)應(yīng)的實(shí)參不會(huì)同步改變。

例如，設(shè)計(jì)以下主函數(shù)調(diào)用Sum1函數(shù)：intmain(){inta=10,b=0;

if(Sum1(a,b))printf("%d\n",b);

elseprintf("參數(shù)錯(cuò)誤\n");}1.2算法和算法分析intSum1(intn,ints){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++) s+=i;return1;}67/105執(zhí)行時(shí)發(fā)現(xiàn)輸出結(jié)果為0。b對(duì)應(yīng)的形參為s，Sum1執(zhí)行后s=55，但s并沒有回傳給b。在C語言中可以用傳指針方式來實(shí)現(xiàn)形參的回傳，但增加了函數(shù)的復(fù)雜性。

1.2算法和算法分析intmain(){inta=10,b=0;

if(Sum1(a,b))printf("%d\n",b);

elseprintf("參數(shù)錯(cuò)誤\n");}intSum1(intn,ints){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++) s+=i;return1;}68/105C++語言中增加了引用型參數(shù)的概念，引用型參數(shù)名前需加上&，表示這樣的形參在執(zhí)行后會(huì)將結(jié)果回傳給對(duì)應(yīng)的實(shí)參。當(dāng)將形參s改為引用類型的參數(shù)后，執(zhí)行時(shí)main函數(shù)的輸出結(jié)果就正確了即輸出55。1.2算法和算法分析intSum1(intn,int&s){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++) s+=i;return1;}引用型參數(shù)：在變量名稱前面加上&69/105算法中引用型參數(shù)的作用1.2算法和算法分析intmain(){…fun(a,b)…}intfun(intn,ints){ …}：?jiǎn)蜗蛑祩鬟f，：回傳C語言中：

intmain(){…fun(a,b)…}intfun(intn,int&s){ …}C++語言中：

函數(shù)調(diào)用70/1051.2.2算法分析計(jì)算機(jī)資源主要包括計(jì)算時(shí)間和內(nèi)存空間。算法分析是分析算法占用計(jì)算機(jī)資源的情況。所以算法分析的兩個(gè)主要方面是分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。算法分析的目的不是分析算法是否正確或是否容易閱讀，主要是考察算法的時(shí)間和空間效率，以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較。

1.2算法和算法分析71/105事后統(tǒng)計(jì)法。事前分析估算法。1.2算法和算法分析有兩種衡量算法效率的方法：事后統(tǒng)計(jì)法存在這些缺點(diǎn)：一是必須執(zhí)行程序，二是存在其他因素掩蓋算法本質(zhì)。通常采用事前分析估算法來分析算法效率。72/105采用事前分析估算方法分析算法的時(shí)間性能。一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的。算法的運(yùn)行時(shí)間取決于兩者的綜合效果。1.2算法和算法分析1.算法時(shí)間復(fù)雜度分析73/105例如，如下算法Solve，其中形參a是一個(gè)m行n列的數(shù)組，當(dāng)是一個(gè)方陣（m=n）時(shí)求主對(duì)角線所有元素之和并返回1，否則返回0。intSolve(doublea[][MAX],intm,intn,double&s){inti;s=0;if(m!=n)retun0;for(i=0;i<m;i++)s+=a[i][i];return1;

}順序結(jié)構(gòu)分支結(jié)構(gòu)循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)1.2算法和算法分析74/105算法的執(zhí)行時(shí)間主要與問題規(guī)模n有關(guān)。例如，數(shù)組的元素個(gè)數(shù)、矩陣的階數(shù)等都可作為問題規(guī)模。所謂一個(gè)語句的頻度，即指該語句在算法中被重復(fù)執(zhí)行的次數(shù)。算法中所有語句的頻度之和記做T(n)，它是問題規(guī)模n的函數(shù)。一個(gè)算法的語句的頻度之和T(n)與算法的執(zhí)行時(shí)間成正比，所以可以將T(n)看作算法的執(zhí)行時(shí)間。當(dāng)問題規(guī)模n趨向無窮大時(shí)，T(n)的數(shù)量級(jí)稱為漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度，記作T(n)=O(f(n))。1.2算法和算法分析75/105“O”的含義是為T(n)找到了一個(gè)上界f(n)，其嚴(yán)格的數(shù)學(xué)定義是：1.2算法和算法分析T(n)表示為O(f(n))是指存在正常量c和n0（為一個(gè)足夠大的正整數(shù)），使得當(dāng)n≥n0時(shí)，總有T(n)≤cf(n)成立。n0nT(n)cf(n)執(zhí)行時(shí)間76/105可以利用極限來證明，即如果則T(n)=O(f(n))，則：例如某算法A的所有語句的頻度之和為

TA(n)=5n3-2n2+3n-100，可以表示為TA(n)=O(n3)，因?yàn)橐粋€(gè)函數(shù)的上界可能不止一個(gè)，如TA(n)=O(n4)也成立，因?yàn)橥ǔ２捎么驩表示法時(shí)給出的是所有上界中最小的那個(gè)上界

應(yīng)該表示為TA(n)=O(n3)而不是TA(n)=O(n4)。1.2算法和算法分析77/105算法的時(shí)間復(fù)雜度是T(n)的數(shù)量級(jí)。算法中基本運(yùn)算語句的頻度與T(n)同數(shù)量級(jí)。被視為算法基本運(yùn)算的語句一般是最深層循環(huán)內(nèi)的語句。所以通常采用算法中基本運(yùn)算語句的頻度來分析算法的時(shí)間復(fù)雜度。1.2算法和算法分析78/105一個(gè)沒有循環(huán)的算法中基本運(yùn)算次數(shù)與問題規(guī)模n無關(guān)，記作O(1)，也稱作常數(shù)階。一個(gè)只有一重循環(huán)的算法中基本運(yùn)算次數(shù)與問題規(guī)模n的增長(zhǎng)呈線性增大關(guān)系，記作O(n)，也稱線性階。其余常用的還有平方階O(n2)、立方階O(n3)、對(duì)數(shù)階O(log2n)、指數(shù)階O(2n)等等。1.2算法和算法分析79/105

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)1.2算法和算法分析各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系：80/105對(duì)于求1+2+…+n值，圖1.17所示的算法（稱為算法1）不如下面的算法（稱為算法2）好。

intSum1(intn,int&s){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++)s+=i;return1;}intSum2(intn,int&s){if(n<0)return0;elsereturnn*(n+1)/2;}因?yàn)樗惴?的時(shí)間復(fù)雜度為O(n)，而算法2的時(shí)間復(fù)雜度為O(1)。算法1算法21.2算法和算法分析81/105voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++) //①{for(j=0;j<n;j++) //②

{c[i][j]=0; //③

for(k=0;k<n;k++) //④

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //⑤

}}}【例1.7】分析以下算法的時(shí)間復(fù)雜度。1.2算法和算法分析82/105語句①的執(zhí)行頻度為n+1（注意i<n判斷語句需執(zhí)行n+1次）語句②的執(zhí)行頻度為n(n+1)語句③的執(zhí)行頻度為n2語句④的執(zhí)行頻度為n2(n+1)語句⑤的執(zhí)行頻度為n31.2算法和算法分析voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++) //①for(j=0;j<n;j++) //②

{c[i][j]=0; //③

for(k=0;k<n;k++) //④

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //⑤

}}解法1：從求算法中所有語句的頻度來分析算法時(shí)間復(fù)雜度。T(n)=2n3+3n2+2n+1=O(n3)83/105基本運(yùn)算是語句⑤其頻度為n3

結(jié)論：從中看到，兩種方法的結(jié)果相同，而第二種方法更加簡(jiǎn)潔。1.2算法和算法分析解法2：從算法中基本運(yùn)算的頻度來分析算法時(shí)間復(fù)雜度。T(n)=n3=O(n3)voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++) //①for(j=0;j<n;j++) //②

{c[i][j]=0; //③

for(k=0;k<n;k++) //④

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //⑤

}}84/105【例1.9】給出以下算法的時(shí)間復(fù)雜度。voidfunc(intn){inti=1,k=100;while(i<=n){k++;i+=2;}}1.2算法和算法分析85/105

其中基本運(yùn)算語句是while循環(huán)內(nèi)的語句。

設(shè)while循環(huán)語句執(zhí)行的次數(shù)為m，i從1開始遞增，最后取值為1+2m，有：

i=1+2m≤n即

T(n)=m≤(n-1)/2=O(n)該算法的時(shí)間復(fù)雜度為O(n)。1.2算法和算法分析基本運(yùn)算語句voidfunc(intn){inti=1,k=100;while(i<=n){k++;i+=2;}}86/1052.算法空間復(fù)雜度分析一個(gè)算法的存儲(chǔ)量包括形參所占空間和臨時(shí)變量所占空間等。對(duì)算法進(jìn)行存儲(chǔ)空間分析時(shí)，只考察臨時(shí)變量所占空間。算法的臨時(shí)空間一般也作為問題規(guī)模n的函數(shù)，以數(shù)量級(jí)形式給出，記作：S(n)=O(g(n))，其中“O”的含義與時(shí)間復(fù)雜度中的含義相同。1.2算法和算法分析87/1051.2算法和算法分析intmax(inta[],intn){inti,maxi=0;for(i=1;i<=n;i++){if(a[i]>a[maxi])maxi=i;}returna[maxi];}函數(shù)體內(nèi)分配的變量空間為臨時(shí)空間，不計(jì)形參占用的空間這里的僅計(jì)i、maxi變量的空間，其空間復(fù)雜度為O(1)88/105為什么算法占用的空間只考慮臨時(shí)空間，而不必考慮形參的空間呢？voidmaxfun(){intb[]={1,2,3,4,5},n=5;printf("Max=%d\n",max(b,n));}intmax(int[]a,intn){inti,maxi=0;for(i=1;i<=n;i++){if(a[i]>a[maxi])maxi=i;}returna[maxi];}形參a僅僅為b數(shù)組的起始地址形參的空間會(huì)在調(diào)用該算法的算法中考慮89/105若算法所需臨時(shí)空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作或就地工作。若所需臨時(shí)空間依賴于特定的輸入，則通常按最壞情況來考慮。1.2算法和算法分析90/1051.2算法和算法分析【例1.10】分析例1.7和例1.9算法的空間復(fù)雜度。

解：這兩個(gè)算法中，臨時(shí)分配空間的變量只有固定幾個(gè)變量，故它們的空間復(fù)雜度均為O(1)，即該算法為原時(shí)工作算法。voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

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

{

for(j=0;j<n;j++)

{c[i][j]=0;

for(k=0;k<n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

}}}voidfunc(intn){inti=1,k=100;

while(i<=n)

{ k++; i+=2;

}}例1.7例1.991/1051.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)1.3.1數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)步驟分析求解問題的數(shù)據(jù)和求解功能，采用抽象數(shù)據(jù)類型來描述求解問題，主要包括數(shù)據(jù)邏輯結(jié)構(gòu)和運(yùn)算定義。設(shè)計(jì)邏輯結(jié)構(gòu)對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)。在存儲(chǔ)結(jié)構(gòu)上設(shè)計(jì)實(shí)現(xiàn)運(yùn)算定義的算法。1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)程序用于求解一個(gè)數(shù)據(jù)結(jié)構(gòu)問題。其設(shè)計(jì)的一般步驟如下：92/105③算法設(shè)計(jì)②設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)①問題描述ADT

＝邏輯結(jié)構(gòu)＋抽象運(yùn)算（功能描述）映射存儲(chǔ)結(jié)構(gòu)1存儲(chǔ)結(jié)構(gòu)n…算法11…算法1m算法n1…算法nk運(yùn)算實(shí)現(xiàn)最佳算法算法分析④算法分析數(shù)據(jù)結(jié)構(gòu)解決問題的思路93/1051.3.2應(yīng)用程序的結(jié)構(gòu)1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)基本運(yùn)算函數(shù)應(yīng)用程序94/105【例1.11】設(shè)計(jì)實(shí)現(xiàn)例1.4功能的完整程序SetApp。1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)95/105

問題描述ADTASet{

數(shù)據(jù)對(duì)象：D={di

|0≤i≤n，n為一個(gè)正整數(shù)}運(yùn)算的定義： voidcset(&s,a,n)：由含n個(gè)元素的數(shù)組a創(chuàng)建一個(gè)集合s。 voiddispset(s)：輸出集合s。 intinset(s,e)：判斷元素e是否為集合s中的元素。}ADTBSet{

數(shù)據(jù)對(duì)象：D={si∈ASet|0≤i≤n，n為一個(gè)正整數(shù)}

運(yùn)算的定義：voidadd(s1,s2,s3)：s3=s1∪s2

//求集合的并集voidsub(s1,s2,s3)：s3=s1-s2

//求集合的差集voidintersection(s1,s2,s3)：s3=s1∩s2

//求集合的交集}1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)96/105采用一個(gè)整型數(shù)組存放集合的元素。由于C/C++語言中數(shù)組并沒有一個(gè)標(biāo)識(shí)數(shù)組中實(shí)際元素個(gè)數(shù)的值，為此用一個(gè)整型變量length表示數(shù)組中的實(shí)際元素個(gè)數(shù)。typedefstruct //集合結(jié)構(gòu)體類型{intdata[MaxSize]; //存放集合中的元素，其中MaxSize為常量

intlength; //存放集合中實(shí)際元素個(gè)數(shù)}Set; //將集合結(jié)構(gòu)體類型用一個(gè)新類型名Set表示1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)

設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)集合類型Set如下：97/105

設(shè)計(jì)運(yùn)算算法

1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)ASet抽象數(shù)據(jù)類型中的運(yùn)算算法對(duì)應(yīng)的函數(shù)如下：voidcset(Set&s,inta[],intn)//由數(shù)組a創(chuàng)建集合s{for(inti=0;i<n;i++)s.data[i]=a[i];s.length=n;}98/1051.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)voiddispset(Sets) //輸出集合s中的所有元素{for(inti=0;i<s.length;i++)printf("%d",s.data[i]);printf("\n");}intinset(Sets,inte) //判斷e是否在集合s中{for(inti=0;i<s.length;i++){if(s.data[i]==e)

return1;}return0;}99/1051.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)BSet抽象數(shù)據(jù)類型中的運(yùn)算算法對(duì)應(yīng)的函數(shù)如下：voidadd(Sets1,Sets2,Set&s3) //求集合的并集{inti;for(i=0;i<s1.length;i++) //

將集合s1的所有元素

s3s3.data[i]=s1.data[i];s3.length=s1.length;for(i=0;i<s2.length;i++) //

將s2中不在s1中的元素

s3

{

if(!inset(s1,s2.data[i])){s3.data[s3.length]=s2.data[i];s3.length++;}}}100/1051.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)voidsub(Sets1,Sets2,Set&s3) //求集合的差集{s3.length=0;for(inti=0;i<s1.length;i++) { //將s1中不出現(xiàn)在s2中的元素

s3if(!inset(s2,s1.data[i])){s3.data[s3.length]=s1.data[i];s3.length++;}}}101/105voidintersection(Sets1,Sets2,Set&s3)//求集合的交集{s3.length=0;for(inti=0;i<s1.length;i++)

//將s1中出現(xiàn)在s2中的元素

s3{if(inset(s2,s1.data[i])){s3.data[s3.length]=s1.data[i];s3.length++;}}}1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)102/105

設(shè)計(jì)主函數(shù)intmain(){inta[]={1,4,2,6,8};intb[]={2,5,3,6};Sets1,s2,s3;

cset(s1,a,5);

cset(s2,b,4);

printf("集合s1:"); dispset(s1);

printf("集合s2:"); dispset(s2);

add(s1,s2,s3);

printf(“集合s1和s2的并集:”);

dispset(s3);

sub(s1,s2,s3);

printf(“集合s1和s2的差集:”);

dispset(s3);

intersection(s1,s2,s3);

printf(“集合s1和s2的交集:”);

dispset(s3);}1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)103/105應(yīng)用程序SetApp的結(jié)構(gòu)：1.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)maincsetdispsetinsetaddsubintersectionASetBSet104/105

程序執(zhí)行結(jié)果集合s1:14268集合s2:2536集合s1和s2的并集:1426853集合s1和s2的差集:148集合s1和s2的交集:261.3數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)105/105第2章線性表2.1線性表的基本概念2.2順序表2.3單鏈表和循環(huán)單鏈表2.4雙鏈表和循環(huán)雙鏈表2.5線性表的應(yīng)用第2章線性表106/1332.1線性表的基本概念2.1.1線性表的定義線性表是由n（n≥0）個(gè)相同類型的數(shù)據(jù)元素組成的有限序列。當(dāng)n=0時(shí)為空表，記為()或Φ.當(dāng)n>0時(shí)，線性表的邏輯表示為（al,a2,…,ai,…,an），也可以用下圖所示的邏輯結(jié)構(gòu)圖表示。2.1線性表的基本概念a1a2aian……107/133a1a2aian……開始元素尾元素邏輯序號(hào)或位置為i邏輯特征：若至少含有一個(gè)元素，則只有唯一的開始元素和終端元素除了起始元素外其他元素有且僅有一個(gè)前驅(qū)元素除了終端結(jié)點(diǎn)外其他元素有且僅有一個(gè)后繼元素2.1線性表的基本概念108/133線性表中的每個(gè)元素有唯一的序號(hào)（邏輯序號(hào)），同一個(gè)線性表中可以存在值相同的多個(gè)元素，但它們的序號(hào)是不同的。如一個(gè)整數(shù)線性表：（1，3，2，4，2，1，5）序號(hào)為1序號(hào)為62.1線性表的基本概念109/1332.1.2線性表的基本運(yùn)算初始化InitList(L)。其作用是建立一個(gè)空表L（即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素）。銷毀線性表DestroyList(L)。其作用是釋放線性表L的內(nèi)存空間。求線性表的長(zhǎng)度GetLength(L)。其作用是返回線性表L的長(zhǎng)度。求線性表中第i個(gè)元素GetElem(L,i,e)。其作用是返回線性表L的第i個(gè)數(shù)據(jù)元素。通常線性表List的基本運(yùn)算如下：2.1線性表的基本概念110/133按值查找Locate(L,x)。若L中存在一個(gè)或多個(gè)值與x相等的元素，則其作用是返回第一個(gè)值為x的元素的邏輯序號(hào)。插入元素InsElem(L,x,i)。其作用是在線性表L的第i個(gè)位置上增加一個(gè)以x為值的新元素，刪除元素DelElem(L,i)。其作用是刪除線性表L的第i個(gè)元素ai。輸出元素值DispList(L)。其作用是按前后次序輸出線性表L的所有元素值。2.1線性表的基本概念111/133線性表抽象數(shù)據(jù)類型List=線性表中元素的邏輯結(jié)構(gòu)+基本運(yùn)算定義2.1線性表的基本概念112/133

【例2.1】利用線性表List的基本運(yùn)算，設(shè)計(jì)一個(gè)在線性表A中刪除線性表B中出現(xiàn)的元素的算法。

解：算法思路：依次檢查線性表B中的每個(gè)元素x，看它是否在線性表A中。若x在線性表A中，則將其從A中刪除。2.1線性表的基本概念113/133voidDelete(List&A,ListB) //A為引用型參數(shù){inti,k;ElemTypex;for(i=1;i<=GetLength(B);i++){x=GetElem(B,i);//依次獲取線性表B中的元素，存放在x中

k=Locate(A,x);

//在線性表A中查找x

if(k>0)DelElem(A,k); //若在線性表A中找到了，將其刪除

}}線性表的基本運(yùn)算算法2.1線性表的基本概念114/133

【例2.2】利用線性表List的基本運(yùn)算，設(shè)計(jì)一個(gè)由線性表A和B中的公共元素產(chǎn)生線性表C的算法。

算法思路：先初始化線性表C，然后依次檢查線性表A中的每個(gè)元素x，看它是否在線性表B中；若x在線性表B中，則將其插入到線性表C中。2.1線性表的基本概念115/133voidCommelem(ListA,ListB,List&C) //C為引用型參數(shù){inti,k,j=1;ElemTypex;

InitList(C);

for(i=1;i<=GetLength(A);i++)

{x=GetElem(A,i); //依次獲取線性表A中的元素，存放在x中k=Locate(B,x); //在線性表B中查找x

if(k>0)

{InsElem(C,x,j);

j++; //若在線性表B中找到了，將其插入到C中

}

}}2.1線性表的基本概念116/1332.2順序表2.2.1順序表的定義順序表是線性表采用順序存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式，它由多個(gè)連續(xù)的存儲(chǔ)單元構(gòu)成，每個(gè)存儲(chǔ)單元存放線性表的一個(gè)元素。順序表邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存的存儲(chǔ)結(jié)構(gòu)中也是相鄰的，不需要額外的內(nèi)存空間來存放元素之間的邏輯關(guān)系。2.2順序表117/133假定線性表的數(shù)據(jù)元素的類型為ElemType，在C/C++語言中，順序表類型聲明如下：#defineMaxSize100typedefintElemType;

//假設(shè)順序表中所有元素為int類型typedefstruct{

ElemTypedata[MaxSize]; //存放順序表的元素

intlength; //順序表的實(shí)際長(zhǎng)度}SqList; //順序表類型2.2順序表118/133順序表的示意圖如下：

由于順序表采用數(shù)組存放元素，而數(shù)組具有隨機(jī)存取特性，所以順序表具有隨機(jī)存取特性。元素a1a2…an…下標(biāo)01n-1MaxSize-1空閑2.2順序表119/1332.2.2線性表基本運(yùn)算在順序表上的實(shí)現(xiàn)1.順序表的基本運(yùn)算算法（1）初始化線性表運(yùn)算算法將順序表L的length域置為0。voidInitList(SqList&L)

//由于L要回傳給實(shí)參，所以用引用類型{

L.length=0;}2.2順序表120/133（2）銷毀線性表運(yùn)算算法

這里順序表L的內(nèi)存空間是由系統(tǒng)自動(dòng)分配的，在不再需要時(shí)由系統(tǒng)自動(dòng)釋放其空間。所以對(duì)應(yīng)的函數(shù)不含任何語句。voidDestroyList(SqListL){}2.2順序表121/133（3）求線性表長(zhǎng)度運(yùn)算算法返回順序表L的length域值。intGetLength(SqListL){

returnL.length;}2.2順序表122/133（4）求線性表中第i個(gè)元素運(yùn)算算法

在邏輯序號(hào)i無效時(shí)返回特殊值0（假），有效時(shí)返回1（真），并用引用型形參e返回第i個(gè)元素的值。intGetElem(SqListL,inti,ElemType&e){if(i<1||i>L.length) //無效的i值返回0

return0;

else

{e=L.data[i-1]; //取元素值并返回1

return1;}}2.2順序表123/133（5）按值查找運(yùn)算算法

在順序表L找第一個(gè)值為x的元素，找到后返回其邏輯序號(hào)，否則返回0（由于線性表的邏輯序號(hào)從1開始，這里用0表示沒有找到值為x的元素）。intLocate(SqListL,ElemTypex) {inti=0;

while(i<L.length&&L.data[i]!=x)i++; //查找值為x的第1個(gè)元素,查找范圍為0～L.length-1

if(i>=L.length)return(0);//未找到返回0

elsereturn(i+1);

//找到后返回其邏輯序號(hào)}2.2順序表124/133（6）插入元素運(yùn)算算法將新元素x插入到順序表L中邏輯序號(hào)為i的位置（如果插入成功，元素x成為線性表的第i個(gè)元素）。當(dāng)i無效時(shí)返回0（表示插入失?。Ｓ行r(shí)將L.data[i-1..L.length-1]后移一個(gè)位置，在L.data[i-1]處插入x，順序表長(zhǎng)度增1，并返回1（表示插入成功。2.2順序表125/133元素a1…an…下標(biāo)0…

i-1

…

n-1均后移一個(gè)位置ai…元素a1…an…下標(biāo)0…

i-1

i

…

nai…x插入元素x2.2順序表126/133intInsElem(SqList&L,ElemTypex,inti){intj;

if(i<1||i>L.length+1||L.length==MaxSize)return0; //無效的參數(shù)ifor(j=L.length;j>=i;j--)//將位置為i的結(jié)點(diǎn)及之后的結(jié)點(diǎn)后移L.data[j]=L.data[j-1];L.data[i-1]=x; //在位置i處放入x

L.length++; //線性表長(zhǎng)度增1

return1;}2.2順序表127/133算法分析當(dāng)i=n+1時(shí)（插入尾元素），移動(dòng)次數(shù)為0，呈現(xiàn)最好的情況。當(dāng)i=1時(shí)（插入第一個(gè)元素），移動(dòng)次數(shù)為n，呈現(xiàn)最壞的情況。2.2順序表128/133平均情況分析a1a2aian……n+1種插入情況在位置i插入新元素x，需要將ai～an的元素均后移一次，移動(dòng)次數(shù)為n-i+1。假設(shè)在等概率下pi（pi=1/(n+1)），移動(dòng)元素的平均次數(shù)為：2.2順序表129/133插入算法的主要時(shí)間花費(fèi)在元素移動(dòng)上，所以算法InsElem()的平均時(shí)間復(fù)雜度為O(n)。2.2順序表130/133（7）刪除元素運(yùn)算算法

刪除順序表L中邏輯序號(hào)為i的元素。在i無效時(shí)返回0（表示刪除失敗）。有效時(shí)將L.data[i..length-1]前移一個(gè)位置，順序表長(zhǎng)度減1，并返回1（表示刪除成功。2.2順序表131/133均前移一個(gè)位置元素a1…an…下標(biāo)0…

i-1i

…

n-1ai+1…ai元素a1…an…下標(biāo)0…

i-1…

n-2ai+1…刪除元素ai2.2順序表132/133intDelElem(SqList&L,inti){intj;

if(i<1||i>L.length) //無效的參數(shù)ireturn0;

for(j=i;j<L.length;j++) //將位置為i的結(jié)點(diǎn)之后的結(jié)點(diǎn)前移L.data[j-1]=L.data[j];

L.length--; //線性表長(zhǎng)度減1

return1;}2.2順