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

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

（C語言版）

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

1計算機科學(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é)時：

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

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

求1名學(xué)生10次C語言程序設(shè)計的測驗成績總分與平均分。其中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)存儲，提高程序的使用范圍。7例如：酒店客房分配問題要求計算機能夠輔助解決酒店客人入住時的房間合理分配的問題；要求每間客房分配給客人入住的機會均等。具體問題8經(jīng)過抽象：計算機通過管理與酒店客房有關(guān)的數(shù)據(jù)來合理分配客房客房數(shù)據(jù)：1、房間號碼2、房間的狀態(tài)（已分配、未分配）將空客房數(shù)據(jù)放在一起，排成一隊得到數(shù)學(xué)模型9在計算機中存儲表示可以采用高級程序設(shè)計語言中的一維數(shù)組來存放客房信息；空客房之間的關(guān)系通過在物理存儲器的相鄰性來體現(xiàn)；10保證客房能夠機會均等的分配的處理方法：將空客房排成一個隊列，每次只能從隊頭分配客房，客人結(jié)賬離店時將客房回收，排到空客房隊列的末尾。402517411234出租402517411234若再有客人入住，則分配51711517411234此時若402房間的客人離店，則將402房間放在空房間隊列的隊尾。517411234402這是一種常見的數(shù)據(jù)結(jié)構(gòu)，它要求只能在隊頭作出隊操作，在隊尾作進隊操作，具體實現(xiàn)方法會在后期課程中介紹給大家。12what---利用計算機解決問題的方法：

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

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

作實驗

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

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

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

線性表、棧和隊列、串、數(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ù)的存儲結(jié)構(gòu)算法20基本術(shù)語數(shù)據(jù)（data）信息的載體，它是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中，能被計算機程序識別、加工處理的信息的集合。DATA(計算機能接受和處理的符號集合)客觀事物（信息）21基本術(shù)語數(shù)據(jù)元素：數(shù)據(jù)的基本單位，是對一個客觀實體的數(shù)據(jù)描述學(xué)號姓名語文…物理000王明86…95001王志平73…92……………100李昕65…89數(shù)據(jù)元素數(shù)據(jù)項22基本術(shù)語數(shù)據(jù)對象：具有相同性質(zhì)的數(shù)據(jù)元素的集合。酒店系統(tǒng)的全部數(shù)據(jù)數(shù)據(jù)元素客房數(shù)據(jù)員工數(shù)據(jù)客人數(shù)據(jù)數(shù)據(jù)對象23基本術(shù)語數(shù)據(jù)類型（datatype）：具有相同性質(zhì)的計算機數(shù)據(jù)的集合及定義在這個集合上的一組操作的總稱。如：兩類數(shù)據(jù)類型：原子類型（其值不可分解，如：int,float.....）結(jié)構(gòu)類型（其值可以分解，如結(jié)構(gòu)體）如C/C++中的int就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合(在16位計算機中為－32768~32767的全體整數(shù))和相關(guān)的整數(shù)運算(如＋、－、＊、／等)。24基本術(shù)語——抽象數(shù)據(jù)類型（AbstractDataType,ADT）ADT：指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型=數(shù)據(jù)元素集合＋抽象運算ADT抽象數(shù)據(jù)類型名{

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Data_Stru