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

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

（C語言版）

中國石油大學(xué)（北京）計(jì)算機(jī)科學(xué)與技術(shù)系李莉

1計(jì)算機(jī)科學(xué)與技術(shù)系地質(zhì)樓（608）聯(lián)系電話：89733006（O）

取課件郵箱：pubcup@聯(lián)系方式2主教材：數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏，清華出版社輔助教材：數(shù)據(jù)結(jié)構(gòu)（C語言版）陳明，清華出版教材與參考書3課程安排64學(xué)時(shí)：

理論課：48學(xué)時(shí)實(shí)踐課：16學(xué)時(shí)第2,3,5,7,9,11,13周周五3、4節(jié)上機(jī)地點(diǎn)：三教403

4why?what?how?課程地位5Why---計(jì)算機(jī)專業(yè)基礎(chǔ)課之一6

求1名學(xué)生10次C語言程序設(shè)計(jì)的測(cè)驗(yàn)成績總分與平均分。其中10次成績分別為：80，85，77，56，68，83，90，92，80，98.Why---軟件開發(fā)中的重要作用main(){intsum,aver;intt1,t2,t3,t4,t5,t6,t7,t8,t9,t10;t1=80;t2=85;t3=77;t4=56;t5=68;t6=83;t7=90;t8=92;t9=80;t10=98;sum=t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;aver=sum/10;printf(“總分=%d\n”,sum);printf(“平均分=%d”,aver);}采用數(shù)組結(jié)構(gòu)存儲(chǔ)，提高程序的使用范圍。7例如：酒店客房分配問題要求計(jì)算機(jī)能夠輔助解決酒店客人入住時(shí)的房間合理分配的問題；要求每間客房分配給客人入住的機(jī)會(huì)均等。具體問題8經(jīng)過抽象：計(jì)算機(jī)通過管理與酒店客房有關(guān)的數(shù)據(jù)來合理分配客房客房數(shù)據(jù)：1、房間號(hào)碼2、房間的狀態(tài)（已分配、未分配）將空客房數(shù)據(jù)放在一起，排成一隊(duì)得到數(shù)學(xué)模型9在計(jì)算機(jī)中存儲(chǔ)表示可以采用高級(jí)程序設(shè)計(jì)語言中的一維數(shù)組來存放客房信息；空客房之間的關(guān)系通過在物理存儲(chǔ)器的相鄰性來體現(xiàn)；10保證客房能夠機(jī)會(huì)均等的分配的處理方法：將空客房排成一個(gè)隊(duì)列，每次只能從隊(duì)頭分配客房，客人結(jié)賬離店時(shí)將客房回收，排到空客房隊(duì)列的末尾。402517411234出租402517411234若再有客人入住，則分配51711517411234此時(shí)若402房間的客人離店，則將402房間放在空房間隊(duì)列的隊(duì)尾。517411234402這是一種常見的數(shù)據(jù)結(jié)構(gòu)，它要求只能在隊(duì)頭作出隊(duì)操作，在隊(duì)尾作進(jìn)隊(duì)操作，具體實(shí)現(xiàn)方法會(huì)在后期課程中介紹給大家。12what---利用計(jì)算機(jī)解決問題的方法：

具體問題數(shù)學(xué)模型編寫算法解決問題在計(jì)算機(jī)中存儲(chǔ)（物理結(jié)構(gòu)）1、數(shù)據(jù)(事物)2、數(shù)據(jù)間的關(guān)系（事物間的聯(lián)系）將算法轉(zhuǎn)換成程序抽象數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)1.事物2.事物間的聯(lián)系13NiklausWirth：

Programs=

DataStructures

+Algorithm程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制的一組指令集數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型算法：處理問題的策略Why---軟件開發(fā)中的重要作用14how?15how？16讀算法模仿寫自己寫，找差距算法分析how？循序漸進(jìn)，切忌心浮氣躁提高課外學(xué)習(xí)的時(shí)間和內(nèi)容理解科學(xué)而不是背誦科學(xué)→讀書正確對(duì)待考試作習(xí)題

華羅庚：“學(xué)數(shù)學(xué)不做習(xí)題等于入寶山而空返”

作實(shí)驗(yàn)

計(jì)算機(jī)學(xué)科是一門科學(xué)性與工程性并重的學(xué)科，表現(xiàn)為理論和實(shí)踐緊密結(jié)合的特征。

17考核方法考試課，滿分100分。考核分平時(shí)成績和期末考試兩部分。平時(shí)成績占30%：日?？己耍?0分，包括出勤情況和課堂提問

注：三次考勤未到，取消考試資格作業(yè)考核：10分實(shí)驗(yàn)考核：10分期末考試成績占70%，閉卷筆試。18基礎(chǔ)篇：基本概念（緒論）結(jié)構(gòu)篇：基本的數(shù)據(jù)結(jié)構(gòu)①線性結(jié)構(gòu)：

線性表、棧和隊(duì)列、串、數(shù)組和廣義表②非線性結(jié)構(gòu)：樹、圖技術(shù)篇：基本的數(shù)據(jù)處理技術(shù)①查找技術(shù)②排序技術(shù)課程主要內(nèi)容與安排19緒論第一章基本術(shù)語數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)算法20基本術(shù)語數(shù)據(jù)（data）信息的載體，它是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中，能被計(jì)算機(jī)程序識(shí)別、加工處理的信息的集合。DATA(計(jì)算機(jī)能接受和處理的符號(hào)集合)客觀事物（信息）21基本術(shù)語數(shù)據(jù)元素：數(shù)據(jù)的基本單位，是對(duì)一個(gè)客觀實(shí)體的數(shù)據(jù)描述學(xué)號(hào)姓名語文…物理000王明86…95001王志平73…92……………100李昕65…89數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)22基本術(shù)語數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素的集合。酒店系統(tǒng)的全部數(shù)據(jù)數(shù)據(jù)元素客房數(shù)據(jù)員工數(shù)據(jù)客人數(shù)據(jù)數(shù)據(jù)對(duì)象23基本術(shù)語數(shù)據(jù)類型（datatype）：具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及定義在這個(gè)集合上的一組操作的總稱。如：兩類數(shù)據(jù)類型：原子類型（其值不可分解，如：int,float.....）結(jié)構(gòu)類型（其值可以分解，如結(jié)構(gòu)體）如C/C++中的int就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合(在16位計(jì)算機(jī)中為－32768~32767的全體整數(shù))和相關(guān)的整數(shù)運(yùn)算(如＋、－、＊、／等)。24基本術(shù)語——抽象數(shù)據(jù)類型（AbstractDataType,ADT）ADT：指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型=數(shù)據(jù)元素集合＋抽象運(yùn)算ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：（數(shù)據(jù)對(duì)象的定義）數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系的定義）基本操作：（基本操作的定義）}ADT抽象數(shù)據(jù)類型名25例如,抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADTComplex{

D={e1,e2|e1,e2均為實(shí)數(shù)}R1={<e1,e2>|e1：實(shí)數(shù)部分,e2：虛數(shù)部分}AssignComplex(&Z,v1,v2)：構(gòu)造復(fù)數(shù)ZDestroyComplex(&Z):復(fù)數(shù)Z被銷毀

GetReal(Z,&real):返回復(fù)數(shù)Z的實(shí)部值

GetImag(Z,&Imag):返回復(fù)數(shù)Z的虛部值

Add(z1,z2,&sum):返回兩個(gè)復(fù)數(shù)z1,z2的和}ADTComplexe1＋e2i26抽象數(shù)據(jù)類型名數(shù)據(jù)對(duì)象基本操作數(shù)據(jù)關(guān)系基本術(shù)語數(shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)之間的相互關(guān)系及在這些數(shù)據(jù)上定義的數(shù)據(jù)運(yùn)算方法的集合。數(shù)據(jù)之間關(guān)系：邏輯關(guān)系：也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：也就是物理結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：對(duì)數(shù)據(jù)進(jìn)行的操作27數(shù)據(jù)的邏輯結(jié)構(gòu)1.集合：數(shù)據(jù)具有符合某一條件的相同的性質(zhì)，且無其它關(guān)系。2.線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。線性表、棧、隊(duì)列、字符串、數(shù)組、廣義表283.樹型結(jié)構(gòu)：數(shù)據(jù)之間存在一對(duì)多的關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)4.網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)之間存在多對(duì)多的關(guān)系。非線性結(jié)構(gòu)：樹、圖29數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的表示或?qū)崿F(xiàn)，包括數(shù)據(jù)元素的表示和關(guān)系的表示。30通常有兩種存儲(chǔ)結(jié)構(gòu)：1.

順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來表示。…batcateat…起始地址例：（bat,cat,eat）31通常有兩種存儲(chǔ)結(jié)構(gòu)：1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素。例：（bat,cat,eat）0200020803000325…………bat0200cat0325eat∧322.鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來表示。存放學(xué)生表的結(jié)構(gòu)體數(shù)組Stud定義為：

struct{ intno;/*存儲(chǔ)學(xué)號(hào)*/ charname[8];/*存儲(chǔ)姓名*/ charsex[2];/*存儲(chǔ)性別*/ charclass[4];/*存儲(chǔ)班號(hào)*/}Stud[7]={{1,“張斌”,“男”,“9901”},…,{5,"王萍","女","9901"}};33結(jié)構(gòu)體數(shù)組Stud各元素在內(nèi)存中順序存放,即第i(1≤i≤6)個(gè)學(xué)生對(duì)應(yīng)的元素Stud[i]存放在第i+1個(gè)學(xué)生對(duì)應(yīng)的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男張斌1Stud[0]Stud[6]Stud數(shù)組起始地址34

存放學(xué)生表的鏈表的結(jié)點(diǎn)類型StudType定義為：

typedefstructstudnode{ intno; /*存儲(chǔ)學(xué)號(hào)*/ charname[8]; /*存儲(chǔ)姓名*/ charsex[2]; /*存儲(chǔ)性別*/ charclass[4]; /*存儲(chǔ)班號(hào)*/ structstudnode*next;/*存儲(chǔ)指向下一個(gè)學(xué)生的指針*/}StudType；35鏈表首結(jié)點(diǎn)地址head1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女9901∧

學(xué)生表構(gòu)成的鏈表如右圖所示。其中的head為第一個(gè)數(shù)據(jù)元素的指針。學(xué)生表構(gòu)成的鏈表36順序存儲(chǔ)方法定義：邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來表示特點(diǎn)：結(jié)點(diǎn)中只有自身信息域，沒有連接信息域,存儲(chǔ)密度大，存儲(chǔ)空間利用率高通過計(jì)算直接確定數(shù)據(jù)結(jié)構(gòu)的中的第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址Li，Li=L0+（i-1）*m,其中L0為第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，m為每個(gè)結(jié)點(diǎn)所占用的存儲(chǔ)單元個(gè)數(shù)。插入和刪除都會(huì)引起大量的結(jié)點(diǎn)移動(dòng)37鏈?zhǔn)酱鎯?chǔ)方法定義：鏈?zhǔn)酱鎯?chǔ)方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的關(guān)系由附加的指針來表示，指針指向結(jié)點(diǎn)的鄰接結(jié)點(diǎn)

結(jié)點(diǎn)特點(diǎn)：存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小，存儲(chǔ)空間利用率低。邏輯上相鄰的結(jié)點(diǎn)，物理上不必鄰接刪除和插入操作靈活方便，不必移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針值數(shù)據(jù)域：存儲(chǔ)結(jié)點(diǎn)本身的值指針域：后繼結(jié)點(diǎn)的存儲(chǔ)單元地址38索引存儲(chǔ)方法建立一個(gè)附加的索引表，利用索引表中索引想的值確定時(shí)間存儲(chǔ)單位地址。

散列存儲(chǔ)方法根據(jù)結(jié)點(diǎn)的關(guān)鍵字值，通過散列函數(shù)H（key）直接計(jì)算出結(jié)點(diǎn)的存儲(chǔ)地址。39數(shù)據(jù)的運(yùn)算查找插入刪除修改排序40數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)表示41數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象計(jì)算機(jī)求解問題:

問題→抽象出問題的模型→求模型的解問題——數(shù)值問題、非數(shù)值問題

數(shù)值問題→數(shù)學(xué)方程非數(shù)值問題→數(shù)據(jù)結(jié)構(gòu)42學(xué)籍管理問題——表結(jié)構(gòu)學(xué)號(hào)姓名性別出生日期政治面貌0001王軍男1983/09/02團(tuán)員0002李明男1982/12/25黨員0003湯曉影女1984/03/26團(tuán)員……………數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象43例:人機(jī)對(duì)弈問題——樹結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？…………..……..………...……44例:教學(xué)計(jì)劃編排問題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫原理C7C2,

C4計(jì)算機(jī)原理C6C3,C4數(shù)據(jù)結(jié)構(gòu)C5C1,C2程序設(shè)計(jì)C4C1離散數(shù)學(xué)C3無計(jì)算機(jī)導(dǎo)論C2無高等數(shù)學(xué)C1先修課課程名稱編號(hào)數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象C1C2C3C4C6C5C7如何表示課程之間的先修關(guān)系？45

多叉路口交通燈的管理——圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象設(shè)計(jì)幾種顏色的交通燈既能使車輛不碰撞，又能達(dá)到最大車流量？46數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象47

數(shù)據(jù)結(jié)構(gòu)形式定義：數(shù)據(jù)結(jié)構(gòu)在形式上可以定義為一個(gè)二元組：

Data_Stru