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

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

姓名：李德光

系部：計(jì)算機(jī)系

辦公地址：

C7201

E--mail:lideguang@一、自我介紹第一章：緒論2姓名：李德光一、自我介31、為什么要學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》在本專業(yè)中的地位：數(shù)據(jù)結(jié)構(gòu)是主修課，4個(gè)學(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)的項(xiàng)目，就必須首先掌握數(shù)據(jù)結(jié)構(gòu)的各項(xiàng)知識和技能。將算法用一種程序設(shè)計(jì)語言實(shí)現(xiàn)

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

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

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

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

本章主要介紹以下內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念算法的概念、描述方法以及評價(jià)標(biāo)準(zhǔn)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.算法的特性及其評價(jià)標(biāo)準(zhǔn)？第一章：緒論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)系）第一章：緒論計(jì)算機(jī)科學(xué)：數(shù)據(jù)指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號集合。12一、什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（關(guān)系）第一章：緒論計(jì)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è)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。第一章：緒論15二、數(shù)據(jù)結(jié)構(gòu)有那些基本結(jié)構(gòu)應(yīng)用舉例1——學(xué)籍檔案管理第一16

特點(diǎn)：

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

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

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

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

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

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

構(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ù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)第一章：緒論23學(xué)號姓名性別年齡20020001王紅據(jù)類型

數(shù)據(jù)類型：一個(gè)類型和定義在該類型上的操作集合高級語言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱三、數(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í)際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱為邏輯結(jié)構(gòu)。第一章：緒論存儲結(jié)構(gòu)（物理結(jié)構(gòu)）

是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲器中的具體實(shí)現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實(shí)際內(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)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它是依賴于計(jì)算機(jī)的。數(shù)據(jù)的存儲結(jié)構(gòu)有以下幾種形式

順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)

索引存儲哈希存儲第一章：緒論26數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別：第一章：緒論27第一章：緒論順序存儲結(jié)構(gòu)：定義：將數(shù)據(jù)元素存儲在一塊地址連續(xù)的空間中。特點(diǎn)：邏輯結(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第一章：緒論鏈?zhǔn)酱鎯Y(jié)構(gòu)：定義：使用指針將相互關(guān)聯(lián)的數(shù)據(jù)元素(節(jié)點(diǎn))連接起來。節(jié)點(diǎn)：由數(shù)據(jù)元素域和指針域組成的一個(gè)整體。特點(diǎn)：邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在節(jié)點(diǎn)的連接關(guān)系上。案例：28第一章：緒論鏈?zhǔn)酱鎯Y(jié)構(gòu)：291028B1020A1010C∧D1005h數(shù)據(jù)元素域指針域

A

1020

D∧

……..

…….

B

1028

……..

…….

C1010

鏈?zhǔn)酱鎯?/p>

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)順序存儲鏈?zhǔn)酱鎯€性表?xiàng)ｊ?duì)樹形結(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、本課程主要研究什么？