




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數據結構
(C語言版)
中國石油大學(北京)計算機科學與技術系李莉
1計算機科學與技術系地質樓(608)聯系電話:89733006(O)
取課件郵箱:pubcup@聯系方式2主教材:數據結構(C語言版)嚴蔚敏,清華出版社輔助教材:數據結構(C語言版)陳明,清華出版教材與參考書3課程安排64學時:
理論課:48學時實踐課:16學時第2,3,5,7,9,11,13周周五3、4節(jié)上機地點:三教403
4why?what?how?課程地位5Why---計算機專業(yè)基礎課之一6
求1名學生10次C語言程序設計的測驗成績總分與平均分。其中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);}采用數組結構存儲,提高程序的使用范圍。7例如:酒店客房分配問題要求計算機能夠輔助解決酒店客人入住時的房間合理分配的問題;要求每間客房分配給客人入住的機會均等。具體問題8經過抽象:計算機通過管理與酒店客房有關的數據來合理分配客房客房數據:1、房間號碼2、房間的狀態(tài)(已分配、未分配)將空客房數據放在一起,排成一隊得到數學模型9在計算機中存儲表示可以采用高級程序設計語言中的一維數組來存放客房信息;空客房之間的關系通過在物理存儲器的相鄰性來體現;10保證客房能夠機會均等的分配的處理方法:將空客房排成一個隊列,每次只能從隊頭分配客房,客人結賬離店時將客房回收,排到空客房隊列的末尾。402517411234出租402517411234若再有客人入住,則分配51711517411234此時若402房間的客人離店,則將402房間放在空房間隊列的隊尾。517411234402這是一種常見的數據結構,它要求只能在隊頭作出隊操作,在隊尾作進隊操作,具體實現方法會在后期課程中介紹給大家。12what---利用計算機解決問題的方法:
具體問題數學模型編寫算法解決問題在計算機中存儲(物理結構)1、數據(事物)2、數據間的關系(事物間的聯系)將算法轉換成程序抽象數據結構邏輯結構1.事物2.事物間的聯系13NiklausWirth:
Programs=
DataStructures
+Algorithm程序設計:為計算機處理問題編制的一組指令集數據結構:問題的數學模型算法:處理問題的策略Why---軟件開發(fā)中的重要作用14how?15how?16讀算法模仿寫自己寫,找差距算法分析how?循序漸進,切忌心浮氣躁提高課外學習的時間和內容理解科學而不是背誦科學→讀書正確對待考試作習題
華羅庚:“學數學不做習題等于入寶山而空返”
作實驗
計算機學科是一門科學性與工程性并重的學科,表現為理論和實踐緊密結合的特征。
17考核方法考試課,滿分100分??己朔制綍r成績和期末考試兩部分。平時成績占30%:日??己耍?0分,包括出勤情況和課堂提問
注:三次考勤未到,取消考試資格作業(yè)考核:10分實驗考核:10分期末考試成績占70%,閉卷筆試。18基礎篇:基本概念(緒論)結構篇:基本的數據結構①線性結構:
線性表、棧和隊列、串、數組和廣義表②非線性結構:樹、圖技術篇:基本的數據處理技術①查找技術②排序技術課程主要內容與安排19緒論第一章基本術語數據結構的概念數據的邏輯結構數據的存儲結構算法20基本術語數據(data)信息的載體,它是描述客觀事物的數、字符以及所有能輸入到計算機中,能被計算機程序識別、加工處理的信息的集合。DATA(計算機能接受和處理的符號集合)客觀事物(信息)21基本術語數據元素:數據的基本單位,是對一個客觀實體的數據描述學號姓名語文…物理000王明86…95001王志平73…92……………100李昕65…89數據元素數據項22基本術語數據對象:具有相同性質的數據元素的集合。酒店系統(tǒng)的全部數據數據元素客房數據員工數據客人數據數據對象23基本術語數據類型(datatype):具有相同性質的計算機數據的集合及定義在這個集合上的一組操作的總稱。如:兩類數據類型:原子類型(其值不可分解,如:int,float.....)結構類型(其值可以分解,如結構體)如C/C++中的int就是整型數據類型。它是所有整數的集合(在16位計算機中為-32768~32767的全體整數)和相關的整數運算(如+、-、*、/等)。24基本術語——抽象數據類型(AbstractDataType,ADT)ADT:指一個數學模型以及定義在該模型上的一組操作。抽象數據類型=數據元素集合+抽象運算ADT抽象數據類型名{
數據對象:(數據對象的定義)數據關系:(數據關系的定義)基本操作:(基本操作的定義)}ADT抽象數據類型名25例如,抽象數據類型復數的定義:ADTComplex{
D={e1,e2|e1,e2均為實數}R1={<e1,e2>|e1:實數部分,e2:虛數部分}AssignComplex(&Z,v1,v2):構造復數ZDestroyComplex(&Z):復數Z被銷毀
GetReal(Z,&real):返回復數Z的實部值
GetImag(Z,&Imag):返回復數Z的虛部值
Add(z1,z2,&sum):返回兩個復數z1,z2的和}ADTComplexe1+e2i26抽象數據類型名數據對象基本操作數據關系基本術語數據結構:
數據之間的相互關系及在這些數據上定義的數據運算方法的集合。數據之間關系:邏輯關系:也稱為數據的邏輯結構存儲結構:也就是物理結構數據的運算:對數據進行的操作27數據的邏輯結構1.集合:數據具有符合某一條件的相同的性質,且無其它關系。2.線性結構:數據元素之間存在一對一的關系。線性表、棧、隊列、字符串、數組、廣義表283.樹型結構:數據之間存在一對多的關系。數據的邏輯結構4.網狀結構:數據之間存在多對多的關系。非線性結構:樹、圖29數據的存儲結構存儲結構(物理結構):數據的邏輯結構在計算機內的表示或實現,包括數據元素的表示和關系的表示。30通常有兩種存儲結構:1.
順序存儲結構:用一組連續(xù)的存儲單元依次存儲數據元素,數據元素之間的邏輯關系由元素的存儲位置來表示。…batcateat…起始地址例:(bat,cat,eat)31通常有兩種存儲結構:1.順序存儲結構:用一組連續(xù)的存儲單元依次存儲數據元素。例:(bat,cat,eat)0200020803000325…………bat0200cat0325eat∧322.鏈接存儲結構:用一組任意的存儲單元存儲數據元素,數據元素之間的邏輯關系用指針來表示。數據元素之間的邏輯關系由元素的存儲位置來表示。存放學生表的結構體數組Stud定義為:
struct{ intno;/*存儲學號*/ charname[8];/*存儲姓名*/ charsex[2];/*存儲性別*/ charclass[4];/*存儲班號*/}Stud[7]={{1,“張斌”,“男”,“9901”},…,{5,"王萍","女","9901"}};33結構體數組Stud各元素在內存中順序存放,即第i(1≤i≤6)個學生對應的元素Stud[i]存放在第i+1個學生對應的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男張斌1Stud[0]Stud[6]Stud數組起始地址34
存放學生表的鏈表的結點類型StudType定義為:
typedefstructstudnode{ intno; /*存儲學號*/ charname[8]; /*存儲姓名*/ charsex[2]; /*存儲性別*/ charclass[4]; /*存儲班號*/ structstudnode*next;/*存儲指向下一個學生的指針*/}StudType;35鏈表首結點地址head1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強男99025王萍女9901∧
學生表構成的鏈表如右圖所示。其中的head為第一個數據元素的指針。學生表構成的鏈表36順序存儲方法定義:邏輯上相鄰的結點存儲在物理位置上也相鄰的存儲單元里,結點之間的邏輯關系由存儲單元的鄰接關系來表示特點:結點中只有自身信息域,沒有連接信息域,存儲密度大,存儲空間利用率高通過計算直接確定數據結構的中的第i個結點的存儲地址Li,Li=L0+(i-1)*m,其中L0為第一個結點的存儲位置,m為每個結點所占用的存儲單元個數。插入和刪除都會引起大量的結點移動37鏈式存儲方法定義:鏈式存儲方法不要求邏輯上相鄰的結點在物理位置上亦相鄰,結點間的關系由附加的指針來表示,指針指向結點的鄰接結點
結點特點:存儲結構的存儲密度小,存儲空間利用率低。邏輯上相鄰的結點,物理上不必鄰接刪除和插入操作靈活方便,不必移動結點,只要改變結點中的指針值數據域:存儲結點本身的值指針域:后繼結點的存儲單元地址38索引存儲方法建立一個附加的索引表,利用索引表中索引想的值確定時間存儲單位地址。
散列存儲方法根據結點的關鍵字值,通過散列函數H(key)直接計算出結點的存儲地址。39數據的運算查找插入刪除修改排序40數據結構的基本概念(小結)數據的操作:插入、刪除、修改、檢索、排序等數據的邏輯結構
數據的存儲結構
順序存儲鏈式存儲集合線性結構樹結構圖結構數據表示41數據結構的研究對象計算機求解問題:
問題→抽象出問題的模型→求模型的解問題——數值問題、非數值問題
數值問題→數學方程非數值問題→數據結構42學籍管理問題——表結構學號姓名性別出生日期政治面貌0001王軍男1983/09/02團員0002李明男1982/12/25黨員0003湯曉影女1984/03/26團員……………數據結構的研究對象43例:人機對弈問題——樹結構數據結構的研究對象如何實現對弈?各格局之間是什么關系?…………..……..………...……44例:教學計劃編排問題——圖結構C4,C5,C6數據庫原理C7C2,
C4計算機原理C6C3,C4數據結構C5C1,C2程序設計C4C1離散數學C3無計算機導論C2無高等數學C1先修課課程名稱編號數據結構的研究對象C1C2C3C4C6C5C7如何表示課程之間的先修關系?45
多叉路口交通燈的管理——圖結構數據結構的研究對象設計幾種顏色的交通燈既能使車輛不碰撞,又能達到最大車流量?46數據結構是研究非數值問題中計算機的操作對象以及它們之間的關系和操作的學科。數據結構的研究對象47
數據結構形式定義:數據結構在形式上可以定義為一個二元組:
Data_Stru
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年高考物理“原子物理綜合”知識應用試題
- 高職銜接考試題及答案
- 高考政治會考試題及答案
- 項目團隊日常管理行為規(guī)范指南
- 企業(yè)信息安全管理制度及實施策略指南
- 2025年病案編碼相關知識試題及答案
- 甘肅美術聯考試題及答案
- 快樂的課堂生活話題作文(9篇)
- 財務預算編制與監(jiān)控模板及關鍵指標
- 財務管理工具報表分析框架構建
- 無損檢測技術課件
- 《3-6歲兒童學習與發(fā)展指南》健康領域解讀
- 銀行等金融機構業(yè)務連續(xù)性計劃書
- 盤扣租賃公司管理制度
- 2025河南大河控股有限公司招聘3人筆試參考題庫附帶答案詳解析集合
- 2025建筑與市政工程施工現場臨時用電安全技術標準(JGJ46-2024)解讀課件
- 普洱茶知識課件
- 《菊花》精致課件圖片
- 紀檢業(yè)務大比武復習測試卷含答案
- 人教版八年級下英語單詞默寫版與完整版
- 《電化學儲能電站接入電網技術規(guī)定》專題培訓
評論
0/150
提交評論