第1講：課程概述和數(shù)據(jù)結(jié)構(gòu)基本概念課件

1數(shù)據(jù)結(jié)構(gòu)NeusoftInstituteofInformationITEducation&Training1數(shù)據(jù)結(jié)構(gòu)NeusoftInstituteofInf2

姓名：李德光

系部：計算機系

辦公地址：

C7201

E--mail:lideguang@一、自我介紹第一章：緒論2姓名：李德光一、自我介31、為什么要學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》在本專業(yè)中的地位：數(shù)據(jù)結(jié)構(gòu)是主修課，4個學(xué)分,是后續(xù)課程的基礎(chǔ)畢業(yè)后工作的需要面試題中主要考數(shù)據(jù)結(jié)構(gòu)的內(nèi)容工作中經(jīng)常會用到數(shù)據(jù)結(jié)構(gòu)的知識二、課程介紹第一章：緒論程序＝數(shù)據(jù)結(jié)構(gòu)＋算法31、為什么要學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》二、課程介紹第一章：緒論程序＝42、如何學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》學(xué)好理論，掌握算法

—要想做與數(shù)據(jù)結(jié)構(gòu)相關(guān)的項目，就必須首先掌握數(shù)據(jù)結(jié)構(gòu)的各項知識和技能。將算法用一種程序設(shè)計語言實現(xiàn)

—數(shù)據(jù)結(jié)構(gòu)有比較多的概念和知識點，因此要多編程，多實踐，以加深對這些概念的理解二、課程介紹第一章：緒論42、如何學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》二、課程介紹第一章：緒論53、數(shù)據(jù)結(jié)構(gòu)和編程語言(C語言)的關(guān)系

數(shù)據(jù)結(jié)構(gòu)：是一個概念和理論的集合

編程語言：對這些概念和理論進行實現(xiàn)，以便于在軟件項目中使用。第一章：緒論數(shù)據(jù)結(jié)構(gòu)C語言Java語言……實現(xiàn)關(guān)系53、數(shù)據(jù)結(jié)構(gòu)和編程語言(C語言)的關(guān)系第一章：緒論數(shù)據(jù)結(jié)構(gòu)64、課程講述內(nèi)容第一章緒論第二章線性表第三章棧和隊列第四章串第六章樹和二叉樹第七章圖

第九章查找第十章內(nèi)部排序第一章：緒論64、課程講述內(nèi)容第一章：緒論75、課程教學(xué)目標⑴理解三種數(shù)據(jù)結(jié)構(gòu)：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)；掌握典型算法的基本思想。⑵能將常用算法用c語言程序?qū)崿F(xiàn)并運行正確，加深理解數(shù)據(jù)結(jié)構(gòu)。⑶靈活運用各種數(shù)據(jù)結(jié)構(gòu)，設(shè)計高效的算法解決實際問題第一章：緒論75、課程教學(xué)目標第一章：緒論81、考核方法：三、考核方法第一章：緒論平時成績60％出勤率10％平時作業(yè)、測試40％課堂表現(xiàn)10％期末考試40％授課的課時：4學(xué)時/周81、考核方法：三、考核方法第一章：緒論平時成績60％出勤91、座位前排不留空，后排不坐人四、課堂要求第一章：緒論看視頻、打游戲，扣分如下：第1次違紀寫不少于3000字檢討！第2次違紀平時考勤和課堂表現(xiàn)按0分記！第3次違紀，本門課程不合格！其余課堂違紀現(xiàn)象（例如戴耳機、玩手機）視其情節(jié)具體扣除1-10分。曠課1次扣10分，曠課次數(shù)達到5次，本門課程不合格！遲到5分鐘扣2分，遲到10分鐘扣5分，超過10分鐘扣10分。2、課堂違紀處理：91、座位前排不留空，后排不坐人四、課堂要求第一章：緒論看視10第一章緒論

本章主要介紹以下內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念算法的概念、描述方法以及評價標準10第一章緒論本章主要介紹以下內(nèi)容11要能回答的問題1.什么是數(shù)據(jù)結(jié)構(gòu)？2.數(shù)據(jù)結(jié)構(gòu)有那些基本結(jié)構(gòu)？3.什么是數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)？4.數(shù)據(jù)結(jié)構(gòu)主要研究什么？5.算法與程序的區(qū)別？6.算法的特性及其評價標準？第一章：緒論11要能回答的問題1.什么是數(shù)據(jù)結(jié)構(gòu)？第一章：緒論12一、什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（關(guān)系）第一章：緒論計算機科學(xué)：數(shù)據(jù)指所有能夠輸入到計算機中并被計算機程序處理的符號集合。12一、什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（關(guān)系）第一章：緒論計13第一章：緒論數(shù)據(jù)的表現(xiàn)形式簡單數(shù)據(jù)（數(shù)字、字符、非數(shù)字字符）例如：學(xué)號(20020001);年齡（18）；姓名（王紅）；照片復(fù)雜數(shù)據(jù)

例如：學(xué)生（20020001、王紅、男、18）；

學(xué)生信息表學(xué)號姓名性別年齡20020001王紅男1820020002張明男1920020003吳寧女1813第一章：緒論數(shù)據(jù)的表現(xiàn)形式學(xué)號姓名性別年齡200200014一、什么是數(shù)據(jù)結(jié)構(gòu)第一章：緒論因此,數(shù)據(jù)結(jié)構(gòu)是指具有某種聯(lián)系的數(shù)據(jù)元素以及元素之間所構(gòu)成的各種關(guān)系的集合。14一、什么是數(shù)據(jù)結(jié)構(gòu)第一章：緒論因此,數(shù)據(jù)結(jié)構(gòu)是指具有某種15二、數(shù)據(jù)結(jié)構(gòu)有那些基本結(jié)構(gòu)應(yīng)用舉例1——學(xué)籍檔案管理

假設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。第一章：緒論15二、數(shù)據(jù)結(jié)構(gòu)有那些基本結(jié)構(gòu)應(yīng)用舉例1——學(xué)籍檔案管理第一16

特點：

l 每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格；l 表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)；l 對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。第一章：緒論16特點：第一章：緒論17應(yīng)用舉例2——Windows文件系統(tǒng)第一章：緒論我的電腦C：\MydocumentWindowsD：\Jdk1.5eclipse17應(yīng)用舉例2——Windows文件系統(tǒng)第一章：緒論我的電腦18特點：l在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說的樹形結(jié)構(gòu)（層次結(jié)構(gòu)）；l對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點內(nèi)容等等。第一章：緒論18特點：第一章：緒論19第一章：緒論應(yīng)用舉例3——專業(yè)課程的開設(shè)軟件技術(shù)專業(yè)課程的開設(shè)情況：課程編號課程名稱需要先修的課程編號C1計算機文化基礎(chǔ)無C2Java語言(初級)C1C3數(shù)據(jù)結(jié)構(gòu)(Java版)C1C4Java語言(中級)C2，C3C5數(shù)據(jù)庫原理及應(yīng)用C3C6Java語言(高級)C4C7腳本語言C1C8JavaWeb程序設(shè)計C5，C6，C719第一章：緒論應(yīng)用舉例3——專業(yè)課程的開設(shè)軟件技術(shù)專業(yè)課程20第一章：緒論特點：在求解過程中，課程之間的先后關(guān)系具有圖結(jié)構(gòu)的特點，因此用圖形結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）描述；對圖形結(jié)構(gòu)的操作有：創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點進行線性排序。

C6C1C2C7C4C3C5C820第一章：緒論特點：C6C1C2C7C4C3C5C21二、數(shù)據(jù)結(jié)構(gòu)有那些基本結(jié)構(gòu)根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)（邏輯）結(jié)構(gòu)：集合——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)（層次結(jié)構(gòu)）——一個對多個，如樹圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）——多個對多個，如圖第一章：緒論21二、數(shù)據(jù)結(jié)構(gòu)有那些基本結(jié)構(gòu)根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，22數(shù)據(jù)

廣義：是對客觀事物的符號表示。

計算機科學(xué)：指所有能夠輸入到計算機中并被計算機程序處理的符號集合。

數(shù)據(jù)元素

表示一個事物的一組數(shù)據(jù)，數(shù)據(jù)元素是數(shù)據(jù)的基本單位。程序中通常作為整體處理，也可稱為結(jié)點、頂點、記錄等。數(shù)據(jù)項

構(gòu)成數(shù)據(jù)元素的最小單位。也稱字段或域。

三、數(shù)據(jù)結(jié)構(gòu)的基本概念第一章：緒論22數(shù)據(jù)三、數(shù)據(jù)結(jié)構(gòu)的基本概念第一章：緒論23學(xué)號姓名性別年齡20020001王紅男1820020002張明男1920020003吳寧女18數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)第一章：緒論23學(xué)號姓名性別年齡20020001王紅據(jù)類型

數(shù)據(jù)類型：一個類型和定義在該類型上的操作集合高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱三、數(shù)據(jù)結(jié)構(gòu)的基本概念第一章：緒論例C語言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體等構(gòu)造數(shù)據(jù)類型。structstudent{intnum;charname[20];floatscore;};24數(shù)據(jù)類型三、數(shù)據(jù)結(jié)構(gòu)的基本概念第一章：緒25有四種基本數(shù)據(jù)邏輯結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中所說的“關(guān)系”實際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱為邏輯結(jié)構(gòu)。第一章：緒論存儲結(jié)構(gòu)（物理結(jié)構(gòu)）

是指數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的具體實現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實際內(nèi)容，還要表示清楚數(shù)據(jù)元素之間的關(guān)系(邏輯結(jié)構(gòu))。25有四種基本數(shù)據(jù)邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)第一章：緒論存儲結(jié)構(gòu)（26數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別：

數(shù)據(jù)的邏輯結(jié)構(gòu)：它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。數(shù)據(jù)的存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，它是依賴于計算機的。數(shù)據(jù)的存儲結(jié)構(gòu)有以下幾種形式

順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)

索引存儲哈希存儲第一章：緒論26數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別：第一章：緒論27第一章：緒論順序存儲結(jié)構(gòu)：定義：將數(shù)據(jù)元素存儲在一塊地址連續(xù)的空間中。特點：邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素在物理上也相鄰。數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素的存儲位置關(guān)系上。案例：{A,B,C,D}用數(shù)組存儲ABCD100010011002100327第一章：緒論順序存儲結(jié)構(gòu)：{A,B,C,D}用數(shù)組存儲A28第一章：緒論鏈式存儲結(jié)構(gòu)：定義：使用指針將相互關(guān)聯(lián)的數(shù)據(jù)元素(節(jié)點)連接起來。節(jié)點：由數(shù)據(jù)元素域和指針域組成的一個整體。特點：邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在節(jié)點的連接關(guān)系上。案例：28第一章：緒論鏈式存儲結(jié)構(gòu)：291028B1020A1010C∧D1005h數(shù)據(jù)元素域指針域

A

1020

D∧

……..

…….

B

1028

……..

…….

C1010

鏈式存儲

h1005存儲地址101010201028…….…….291028B1020A1010C∧D1005h數(shù)據(jù)元30第一章：緒論四、數(shù)據(jù)結(jié)構(gòu)主要研究什么數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)各種操作的課程。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的操作(算法)：檢索、排序、插入、刪除、修改等線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲鏈式存儲線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)30第一章：緒論四、數(shù)據(jù)結(jié)構(gòu)主要研究什么數(shù)據(jù)的邏輯結(jié)構(gòu)31總結(jié)：1、什么是數(shù)據(jù)結(jié)構(gòu)？2、本課程主要研究什么？