模塊1數據結構概述

教學要求:

(1)了解數據結構的概念，熟悉數據結構的研究內容。

(2)會用邏輯結構描述數據，能夠熟練地說出數據的存儲結構。

(3)掌握算法的特性和效率，能夠對算法進行分析。

(4)熟練掌握數據結構與算法的關系。

教學重點：

數據結構中的一些基本術語、邏輯結構的描述、數據的存儲結構、數據類型、算法的描述及

復雜度分析。

教學難點：

數據的存儲結構、算法描述和復雜度分析。

課時安排：

本模塊安排4課時。其中，理論講授2課時，上機實驗2課時。

教學大綱：

模塊1數據結構概述

案例導入

案例分析

相關知識

1.1什么是數據結構

1.1.1從數據結構實例認識數據結構

1.1.2數據結構的研究內容

1.2邏輯結構的描述

1.3數據的存儲結構

1.4算法和算法分析

1.4.1算法特性

1.4.2算法的效率

1.4.3算法效率的評價

1.5數據結構與算法的關系

案例實施

案例總結

思考與練習

主要概念：

1.數據

2.數據元素

3.數據項

4.數據對象

5.數據結構

6.數據的邏輯結構

7.集合

8.線性結構

9.樹狀結構

10.圖狀結構

11.數據的存儲結構

12.非線性結構

13.位

14.字節

15.字

16.位串

17.結點

18.數據域

19.順序存儲

20.鏈式存儲

21.數據類型

22.原子類型

23.結構類型

24.抽象數據類型

25.算法

26.算法的5個特性

27.算法描述

28.類C語言

29.算法的時間復雜度

30.事前分析估算法

31.事后統計法

32.算法的空間復雜度

33.算法設計的要求

實驗：

實驗編寫程序實現算法，熟悉數據結構的有關概念(2學時)

1.試編寫算法，完成從大至小依次輸出順序讀入的三個整數x,y,z的值，并將此算法用

程序設計語言實現。

2.試編寫算法，完成復數的加、減操作，并用程序設計語言實現。有關抽象數據類型的描

述如下：

【復數抽象數據類型ADT的描述】

ADTcomplex{

數據對象：D={cl,c2cl,c2eFloatSet}

數據關系：R={clc2}

基本操作：

創建一個復數Create(a);

輸出一個復數Outputc(a);

求兩個復數相加之和Add(a,b);

求兩個復數相減之差Sub(a,b);

等等；

}ADTcomplex;

【部分實現的源碼】

〃存儲表示,結構體類型的定義

typedefstruct{

floatx;〃實部子域

floaty;//虛部的實系數子域

}comp;

//全局變量的說明

compa,b,al,bl;

intz;

〃子函數的原型聲明

voidCreate(comp*c);

voidOutputc(compa);

compAdd(compk,comph);

compSub(compk,comph);

〃主函數

main(){

Create(&a);

Outputc(a);

Create(&b);

Outputc(b);

al=Add(a,b);

Outputc(al);

al=Sub(a,b);

Outputc(al);

}//main

〃創建一個復數

voidCreate(comp*c){

floatcl,c2;

printf(〃輸入實部realx=");

scanf&cl);

printf(〃輸入虛部xvpuy=〃)；

scanf&c2);

(*c).x=cl;

c->y=c2;

}//Create

〃輸出一個復數

voidOutputc(compa){

printf("\n%f+%fi\n\n〃，a.x,a.y);

}//Outputc

〃求兩個復數