算法與數(shù)據(jù)結(jié)構(gòu)-第1章概論

算法與數(shù)據(jù)結(jié)構(gòu)——第1章概論第一頁，共78頁。胡志坤,博士，副教授，1976年出生電話：Email:

qq:61560522第二頁，共78頁。1）點(diǎn)名7次，未到按此比例進(jìn)行2）期末閉卷考試，80%的題目會(huì)在上課出現(xiàn)3）期末考試原則上是以考試成績和考勤來計(jì)算4）定期進(jìn)行溝通3第三頁，共78頁。學(xué)時(shí)數(shù)：64（52＋12）學(xué)分：3.5教材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，1997年4月（配題集）

參考書：[1]殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），清華大學(xué)出版社，1999年7月。￥26[2]殷人昆等，數(shù)據(jù)結(jié)構(gòu)習(xí)題解析，清華大學(xué)出版社，2002年4月。￥26[3]李春保，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語言篇），清華大學(xué)出版社，2001年1月。￥28[4]

丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社，2001年5月。￥234第四頁，共78頁。內(nèi)容安排章內(nèi)容學(xué)時(shí)章內(nèi)容學(xué)時(shí)1序論27圖82線性表68動(dòng)態(tài)存儲(chǔ)管理23棧和隊(duì)列49查找64串410內(nèi)部排序65數(shù)組和廣義表411外部排序略6樹和二叉樹812文件略注：國慶長假占用4學(xué)時(shí)，機(jī)動(dòng)2學(xué)時(shí)。6次實(shí)驗(yàn)安排在6個(gè)周日，5個(gè)班5第五頁，共78頁。數(shù)據(jù)結(jié)構(gòu)課程的地位是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程關(guān)系對(duì)象關(guān)系操作數(shù)學(xué)軟件硬件對(duì)象關(guān)系操作6第六頁，共78頁。第0章C/C++程序設(shè)計(jì)補(bǔ)充0.1指針0.2函數(shù)與參數(shù)作業(yè)7第七頁，共78頁。指針的概念指針數(shù)據(jù)類型指針與其他數(shù)據(jù)類型指針修飾符0.1指針第八頁，共78頁。一般的32位CPU都有硬件MMU單元，能將有限的硬件內(nèi)存(如512M)虛擬成一個(gè)較大(如2G)的虛擬內(nèi)存這樣軟件可以在一個(gè)非常大的范圍里使用內(nèi)存每個(gè)內(nèi)存單元（8bits組成一個(gè)內(nèi)存單元byte）都有一個(gè)地址地址是一個(gè)無符號(hào)的整數(shù)表示，通常與CPU字長相等(在32位CPU上就是4byte的空間)內(nèi)存與地址第九頁，共78頁。1、變量是對(duì)程序中數(shù)據(jù)存儲(chǔ)空間(地址和值)的抽象intnum=100;printf(“numis%d,numaddris%p\n”,num,&num);2、可以將變量的地址保存在一個(gè)整型變量中unsignedintaddr=0;addr=#printf(“addris%#x\n”,addr);3、問題是，怎么通過addr簡(jiǎn)接獲取該地址內(nèi)保存的值（100）?變量與地址第十頁，共78頁。1、C定義了一種專門用于表示地址的變量—指針

int*addr;//定義指針變量2、將內(nèi)存中數(shù)據(jù)的地址賦值給指針變量：表示將指針指向該數(shù)據(jù)addr=#//指針變量addr指向num變量3、通過指針變量可以間接訪問被指向的數(shù)據(jù)

printf(“numis%d\n”,*addr);//通過addr獲取num*addr=200;//通過addr修改numprintf(“numis%d\n”,num);指針的由來第十一頁，共78頁。用好指針可以: 使程序簡(jiǎn)潔、緊湊、高效有效地表示復(fù)雜的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)分配內(nèi)存得到多于一個(gè)的函數(shù)返回值直接操作地址造就了C/C++的強(qiáng)大用不好指針造成：非法內(nèi)存訪問，程序死機(jī)或異常內(nèi)存泄露，減低系統(tǒng)性能指針屬于間接訪問，指來指去最終變得不可維護(hù)指針是把雙刃劍第十二頁，共78頁。指針的概念指針數(shù)據(jù)類型指針與其他數(shù)據(jù)類型指針修飾符0.1指針第十三頁，共78頁。指針的定義實(shí)例：int*pi;char*pc;double*pd;info_t*pinfo;staticint*pi;staticchar*pc;staticinfo_t*pinfo;關(guān)鍵概念：1、指針類型與指針指向?qū)ο箢愋?、指針的值與指針指向?qū)ο蟮闹?/p>

第十四頁，共78頁。指針內(nèi)存大小指針變量用來表示內(nèi)存地址，32位CPU上用4byte空間表示地址int*pi;char*pc;double*pd;info_t*pinfo;sizeof(pi)=?sizeof(pc)=?sizeof(pd)=?sizeof(pinfo)=?第十五頁，共78頁。指針初始化與賦值1、初始化為指向?qū)ο蟮牡刂?/p>

intnum=100;intpaddr=#//paddr指向num2、初始化為空指針

int*paddr=NULL;//NULL為0，表示空地址3、指針變量定義后可以隨時(shí)改變所指向的變量

intnum1=100,num2=200;intpaddr=NULL;paddr=&num1;paddr=&num2;第十六頁，共78頁。指針運(yùn)算1、取值運(yùn)算符

intnum=100;int*paddr=#

通過paddr間接取num值:*paddr2、取址運(yùn)算符

&paddr=?:表示paddr這個(gè)指針變量的地址3、加減運(yùn)算：偏移指針類型字節(jié)數(shù)

paddr+1=?paddr++?paddr–1=?paddr--?4、強(qiáng)制轉(zhuǎn)換

intnum=100;char*paddr=#*paddr=?paddr+1=?*(int*)paddr=?(int*)paddr+1=?第十七頁，共78頁。通用(void)指針指針變量的類型表示指針?biāo)赶驅(qū)ο蟮念愋湍懿荒芏x一種通用指針，將來根據(jù)需要再指向特定對(duì)象？void*point=NULL;//void指針，定義不指定指針指向哪種類型數(shù)據(jù)sizeof(point)=?point++?point--?使用時(shí)需要進(jìn)行強(qiáng)制類型轉(zhuǎn)換：intnum=100;charch=‘a(chǎn)’;void*point=NULL;point=#printf(“numis%d\n”,*(int*)point);point=&ch;printf(“chis%c\n”,*(char*)ch);

第十八頁，共78頁。指針的概念指針數(shù)據(jù)類型指針與其他數(shù)據(jù)類型指針修飾符0.1指針第十九頁，共78頁。數(shù)組與指針1、數(shù)組與指針的關(guān)系數(shù)組名表示數(shù)組首地址，可以把數(shù)組名可作指針常量

intarr[3]={1,2,3};int*p=arr;

p++?arr++?*p=?*(p+1)=?*(p+2)=?數(shù)組下標(biāo)操作符內(nèi)部實(shí)現(xiàn)機(jī)制：通過指針取值運(yùn)算符實(shí)現(xiàn)

arr[2]相當(dāng)于*(arr+2)數(shù)組作為函數(shù)參數(shù)，實(shí)際是轉(zhuǎn)化為指針實(shí)現(xiàn)

str_cpy(charsrc[],chardes[])=>str_cpy(char*src,char*des)數(shù)組作為函數(shù)返回值，必須通過指針實(shí)現(xiàn)

char*str_cpy(char*src,char*des)第二十頁，共78頁。數(shù)組與指針2、指針數(shù)組：即數(shù)組的元素為指針類型。

char*var[10];//10個(gè)int型指針的數(shù)組sizeof(var)=?var+1?3、數(shù)組指針：即指針的類型為數(shù)組（指向數(shù)組的指針）。

char(*var)[10];//指向10個(gè)int型數(shù)組的指針sizeof(var)=?var+1?4、字符串與指針字符串是屬于典型的字符數(shù)組，因而通常通過char型指針處理字符串

第二十一頁，共78頁。數(shù)組與指針將字符串直接賦值給指針，表示指針指向字符串內(nèi)存首地址 注意：字符串常量內(nèi)存分配在只讀數(shù)據(jù)區(qū)（RODATA） 實(shí)例：char*p=“xnf”;chararr[]={“xnf”};

*p?*p++?*++p?*p=‘X’?arr[0]=‘X’?strcpy(p,“XNF”)?strcpy(arr,“XNF”)?

第二十二頁，共78頁。數(shù)組與指針通過指針數(shù)組表示字符串?dāng)?shù)組

chara[][16]={“welcome”,“to”,“xnf”}；

主函數(shù)參數(shù)就是通過指針數(shù)組實(shí)現(xiàn)的: intmain(intargc,char*argv[])

第二十三頁，共78頁。結(jié)構(gòu)與指針1、結(jié)構(gòu)包含指針：結(jié)構(gòu)體中包含指針域變量如：學(xué)生信息中name與phone定義為指針

注意：在程序中動(dòng)態(tài)修改學(xué)生信息表中的name和phone域可行么？

第二十四頁，共78頁。結(jié)構(gòu)與指針2、指向結(jié)構(gòu)體的指針

結(jié)構(gòu)體變量域通過.訪問，而結(jié)構(gòu)體指針域通過->訪問

sizeof(info)=?sizeof(p)=?下面這段代碼錯(cuò)在哪里？

第二十五頁，共78頁。結(jié)構(gòu)與指針

通過結(jié)構(gòu)體指針傳遞參數(shù)比直接傳遞結(jié)構(gòu)體變量更高效實(shí)參傳遞給形參時(shí)只拷貝了4個(gè)字節(jié)

第二十六頁，共78頁。指針與指針1、指向指針變量的指針

intnum=100;int*p=#int**pp=&p;

實(shí)現(xiàn)指針二級(jí)訪問:

第二十七頁，共78頁。函數(shù)與指針1、指針作為函數(shù)的參數(shù)向函數(shù)傳遞數(shù)組、字符串、結(jié)構(gòu):如strc_py、show_info作為函數(shù)的輸出參數(shù)

例如：實(shí)現(xiàn)交換兩個(gè)整數(shù)的函數(shù)voidsa,intb)

傳值，形參值改變并不能帶回給實(shí)參

傳址，在函數(shù)內(nèi)改變地址內(nèi)保存的內(nèi)容

第二十八頁，共78頁。函數(shù)與指針問題：要在函數(shù)能改變指針的值，怎么通過輸出參數(shù)返回？例如：voidget_mem(char*pmem,intsize){ pmem=malloc(size);}動(dòng)態(tài)分配的內(nèi)存能通過pmem帶回么？

不能！要將實(shí)參指針的地址傳遞給形參（二級(jí)指針）才能實(shí)現(xiàn)!更直接的方法是通過函數(shù)返回值實(shí)現(xiàn)

第二十九頁，共78頁。函數(shù)與指針2、指針作為函數(shù)的返回值返回字符串、動(dòng)態(tài)分配的內(nèi)存等，如*strcpy,*malloc注意返回地址的有效性（函數(shù)執(zhí)行完畢后該地址未被回收）

下面兩個(gè)函數(shù)哪個(gè)是合法的？第三十頁，共78頁。函數(shù)與指針3、指向函數(shù)的指針函數(shù)存放在TEXT段，同樣具有地址函數(shù)名就是函數(shù)在TEXT段的入口地址跟數(shù)組名一樣，函數(shù)名也可以看作是一個(gè)指針常量所以，函數(shù)名也可以賦值給指針變量，那么該指針變量類型呢？函數(shù)指針類型！通過函數(shù)指針，也可以間接調(diào)用函數(shù)。

第三十一頁，共78頁。函數(shù)與指針函數(shù)指針的應(yīng)用：1、作為函數(shù)參數(shù)實(shí)現(xiàn)回調(diào)函數(shù)所謂回調(diào)函數(shù)是指通過調(diào)用其他函數(shù)反過來調(diào)用某個(gè)函數(shù)模擬面向?qū)ο蟮亩鄳B(tài)，在UI組件的大量使用

第三十二頁，共78頁。函數(shù)與指針

2、作為結(jié)構(gòu)體的動(dòng)作域模擬面向?qū)ο蟮念?，在Linux內(nèi)核中大量使用

作為一個(gè)現(xiàn)實(shí)中的對(duì)象，不但有數(shù)據(jù)屬性，還需要有行為屬性使用對(duì)象行為

第三十三頁，共78頁。指針的概念指針數(shù)據(jù)類型指針與其他數(shù)據(jù)類型指針修飾符0.1指針第三十四頁，共78頁。const修飾符1、const修飾符的作用：限定一個(gè)變量不允許被改變（只讀）

如：constintnum=100;//num是只讀整型變量constintarr[3]={10,20,30};//arr是只讀整型數(shù)組

num=200?arr[0]=100?arr[1]=200?

2、const指針:指向變量的只讀指針，指針本身只讀，但指向的對(duì)象非只讀

如：intnum1=100;intnum2=200;int*constp=&num1; *p=200?p=&num2?

第三十五頁，共78頁。const修飾符3、指向const變量的指針:指向只讀變量的指針，而指針本身不是只讀的如：const

intnum1=100;constintnum2=200;constint*p=&num1;*p=200?p=&num2?

注意:const也可以在int之后，如intconstnum1=100;intconst*p=&num14、指向const變量的const指針：指針和指向的變量都是只讀的

如：const

intnum1=100;constintnum2=200;constint*constp=&num1;*p=200?p=&num2?第三十六頁，共78頁。volatile修飾符1、編譯器總是試圖優(yōu)化編譯使代碼運(yùn)行得更快如果程序中變量未被改變，對(duì)變量的訪問盡量用寄存器代替內(nèi)存儲(chǔ)存寄存器屬于CPU內(nèi)部的存儲(chǔ)單元，比起內(nèi)存訪問來得更快2、但對(duì)于硬件驅(qū)動(dòng)程序來說，這樣做就存在風(fēng)險(xiǎn)constunsignedint*paddr=0x0012ff7c;//假定0x0012ff7c表示一個(gè)網(wǎng)卡內(nèi)存地址

data=*paddr;//第一次取網(wǎng)卡數(shù)據(jù)

data=*paddr;//第二次取網(wǎng)卡數(shù)據(jù)由于*paddr從未被程序改變，所以第二次取值從寄存器中進(jìn)行，跟第一次值一樣

但網(wǎng)卡內(nèi)存數(shù)據(jù)會(huì)隨時(shí)在通信中發(fā)生改變！

第三十七頁，共78頁。volatile修飾符3、使用volatile修飾符

volatile告訴編譯器，不要對(duì)其修飾的變量作優(yōu)化總是從內(nèi)存進(jìn)行讀寫，而不是僅僅在寄存器

volatileconstunsignedint*p=0x0012ff7c;//假定0x0012ff7c表示一個(gè)網(wǎng)卡內(nèi)存地址

第三十八頁，共78頁。typedef修飾符1、指針相關(guān)數(shù)據(jù)類型

定義含義inti;int*p;inta[n];int*p[n];int(*p)[n];intf();int*p();int(*p)();int**p;定義整型變量ip為指向整型數(shù)據(jù)的指針變量定義含n個(gè)元素的整型數(shù)組an個(gè)指向整型數(shù)據(jù)的指針變量組成的指針數(shù)組pp為指向含n個(gè)元素的一維整型數(shù)組的指針變量f為返回整型數(shù)的函數(shù)p為返回指針的函數(shù)，該指針指向一個(gè)整型數(shù)據(jù)p為指向函數(shù)的指針變量，該函數(shù)返回整型數(shù)p為指針變量，它指向一個(gè)指向整型數(shù)據(jù)的指針變量第三十九頁，共78頁。typedef修飾符2、更復(fù)雜的指針相關(guān)數(shù)據(jù)類型從變量名括號(hào)開始解釋，括號(hào)外面表示類型可以用typedef自定義類型來簡(jiǎn)化int(*p[3])(int);typedefint(func_t)(int);//定義返回整數(shù)的函數(shù)類型

funct_t*p[3];//定義包含3個(gè)函數(shù)指針的數(shù)組int*(*p[3])(int);typedefint*(func_t)(int);//定義返回整數(shù)指針的函數(shù)類型func_t*p[3];//定義包含3個(gè)函數(shù)指針的數(shù)組

第四十頁，共78頁。typedef修飾符int(*p)[3](int);//錯(cuò)誤，不能聲明函數(shù)的數(shù)組 如何定義指向包含3個(gè)返回整數(shù)函數(shù)指針數(shù)組的指針？

typedefint(func_t)(int);//定義返回整型函數(shù)指針類型

typedeffunc_t*pfarr_t[3];//定義包含3個(gè)函數(shù)指針數(shù)組類型

pfarr_t*p;//定義指向數(shù)組的指針

第四十一頁，共78頁。上機(jī)實(shí)驗(yàn)1、指針應(yīng)用 （1）用指針實(shí)現(xiàn)char*str_cpy(char*des,char*src)voidset_info(info_t*pinfo)函數(shù) （2）封裝獲取動(dòng)態(tài)內(nèi)存函數(shù)get_mem，分別通過返回值和輸出參數(shù)帶回內(nèi)存分配結(jié)果2、函數(shù)指針使用在學(xué)生信息info_t中增加reading讀書行為,并通過回調(diào)函數(shù)調(diào)用reading3、指針數(shù)據(jù)表示 （1）如果顯卡內(nèi)存地址是0x345ff000(假定)，用指針表示并模擬讀寫顯卡操作(2)解釋void(*var[10])(void(*)(void))，并通過typedef簡(jiǎn)化表示第四十二頁，共78頁。第1章序論1.1計(jì)算機(jī)基本概念（復(fù)習(xí)）1.2數(shù)據(jù)結(jié)構(gòu)基本概念1.3抽象數(shù)據(jù)類型概念1.4算法效率的度量作業(yè)43第四十三頁，共78頁。1.1計(jì)算機(jī)基本概念(復(fù)習(xí)）計(jì)算機(jī)系統(tǒng)＝硬件系統(tǒng)＋軟件系統(tǒng)Q1硬件系統(tǒng)由哪幾部分組成？Q2微型計(jì)算機(jī)與其他計(jì)算機(jī)的區(qū)別？Q3內(nèi)存與外存的不同之處是？Q4計(jì)算機(jī)內(nèi)常用到哪些數(shù)制？Q5

計(jì)算機(jī)主要技術(shù)指標(biāo)有哪些?硬件概念復(fù)習(xí)軟件概念復(fù)習(xí)Q1軟件系統(tǒng)包含哪些軟件？Q2什么是系統(tǒng)軟件和應(yīng)用軟件？Q3機(jī)器語言、匯編語言、高級(jí)語言的區(qū)別？44第四十四頁，共78頁。Q1：計(jì)算機(jī)硬件系統(tǒng)由哪幾部分組成？答：計(jì)算機(jī)硬件系統(tǒng)由部分組成：也可濃縮為3部分：存儲(chǔ)器CPUI/O接口及設(shè)備人腦：感受→判斷→計(jì)算→記憶→反應(yīng)電腦：輸入→控制→運(yùn)算→存儲(chǔ)→輸出控制器

輸入運(yùn)算器

存儲(chǔ)器

輸出主機(jī)545第四十五頁，共78頁。Q2：微型計(jì)算機(jī)與一般意義上的計(jì)算機(jī)有什么區(qū)別？

其本質(zhì)特征是答：運(yùn)算器和控制器集成在一塊IC芯片上這種CPU簡(jiǎn)稱MPU46第四十六頁，共78頁。Q3：內(nèi)存與外存是一回事嗎？能被CPU直接控制（BUS直連）的存儲(chǔ)器稱為內(nèi)存通過I/O接口才能被CPU控制的存儲(chǔ)器稱為外存答：不是一回事。它們的區(qū)別是：

輸入運(yùn)算器

存儲(chǔ)器控制器

輸出BUS外存儲(chǔ)器CPU47第四十七頁，共78頁。Q4：計(jì)算機(jī)內(nèi)常用到哪些數(shù)制？A.（）B B.（75）D

C.（37）O D.（2A）H答案：

C2進(jìn)制(B)8進(jìn)制(O)10進(jìn)制(D)16進(jìn)制(H)例3：下列四種不同進(jìn)制的無符號(hào)數(shù)中，最小的數(shù)是∶例2：下列數(shù)據(jù)中，有可能是八進(jìn)制數(shù)的是∶

A.238 B.764 C.396 D.789例1：10(B)＝

D10(O)＝

D10(H)＝

D

281648第四十八頁，共78頁。Q5：

計(jì)算機(jī)主要技術(shù)指標(biāo)有哪些？——CPU一次能處理的二進(jìn)制位數(shù)，它與數(shù)據(jù)總線的根數(shù)有關(guān)，如8位機(jī)，16位機(jī)、32位機(jī)等等——運(yùn)算器做一次“加”動(dòng)作的最小可靠時(shí)間，如奔4機(jī)器主頻達(dá)1.6G（Hz）——CPU每秒能執(zhí)行加法指令的次數(shù)（MIPS）——bit，Byte，KB，MB，GB，TB練：微機(jī)中1K字節(jié)表示的二進(jìn)制位數(shù)是：1B=8bit1KB=210B1MB=210KB1GB=210MBA.1000B.8×1000C.1024D.8×1024答案：D字長主頻運(yùn)算速度主存容量49第四十九頁，共78頁。Q1：

軟件系統(tǒng)包含哪些軟件？裸機(jī)系統(tǒng)軟件操作系統(tǒng)支援軟件應(yīng)用軟件答：包含系統(tǒng)軟件和應(yīng)用軟件兩大類50第五十頁，共78頁。Q2：什么是系統(tǒng)軟件？什么是應(yīng)用軟件？答：系統(tǒng)軟件——管理計(jì)算機(jī)系統(tǒng)各部分，使之高效工作，同時(shí)為上層提供服務(wù)。應(yīng)用軟件——處于系統(tǒng)軟件的上層，幫助計(jì)算機(jī)用戶完成特定領(lǐng)域的工作。系統(tǒng)軟件中最重要的是操作系統(tǒng)（OperatingSystem），它是一個(gè)大型的、優(yōu)秀的程序，管理著計(jì)算機(jī)的全部軟、硬件資源，并提供人機(jī)交互的界面。51第五十一頁，共78頁。Q3：機(jī)器語言、匯編語言、高級(jí)語言的區(qū)別？——用二進(jìn)制代碼直接表示的語言，是計(jì)算機(jī)唯一能識(shí)別、執(zhí)行的語言——符號(hào)化了的機(jī)器語言（即用助記符來寫程序，靠匯編程序翻譯成機(jī)器碼才能執(zhí)行）——接近自然英語和數(shù)學(xué)公式的語言（要通過編譯或解釋程序翻譯成機(jī)器碼）答：低級(jí)語言面向機(jī)器，執(zhí)行速度快，效率高；高級(jí)語言面向問題，易理解，易移植。機(jī)器語言匯編語言高級(jí)語言52第五十二頁，共78頁。1.2數(shù)據(jù)結(jié)構(gòu)基本概念Q1什么是數(shù)據(jù)結(jié)構(gòu)？Q2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？

Q3數(shù)據(jù)結(jié)構(gòu)涵蓋的主要內(nèi)容？

討論：53第五十三頁，共78頁。Q1：什么是數(shù)據(jù)結(jié)構(gòu)？答:(見教材P5)

是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：（數(shù)值或非數(shù)值）Data_Structure=（D,S）或：是指同一數(shù)據(jù)元素類中各元素之間存在的關(guān)系。亦可表示為：S＝（D,R）或B=（K,R）元素有限集關(guān)系有限集54第五十四頁，共78頁。術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)（見教材P4定義）：數(shù)據(jù)(data)——所有能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)的集合（包括數(shù)字、字符、聲音、圖像等信息）。數(shù)據(jù)元素(dataelement)——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義(又稱元素、結(jié)點(diǎn)，頂點(diǎn)、記錄等）。數(shù)據(jù)項(xiàng)(Dataitem)——構(gòu)成數(shù)據(jù)元素的項(xiàng)目。是具有獨(dú)立含義的最小標(biāo)識(shí)單位（又稱字段、域、屬性等）。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：班級(jí)通訊錄>個(gè)人記錄>姓名、年齡……55第五十五頁，共78頁。Q2：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？答：計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。

這是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。程序設(shè)計(jì)實(shí)質(zhì)＝好算法＋好結(jié)構(gòu)同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能有明顯的差異。56第五十六頁，共78頁。Q3：數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容？57第五十七頁，共78頁。解釋1：什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？答：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)可細(xì)分為4類：集合結(jié)構(gòu)：僅同屬一個(gè)集合線性結(jié)構(gòu):

一對(duì)一（1:1)

樹結(jié)構(gòu):

一對(duì)多（1:n)

圖結(jié)構(gòu):

多對(duì)多(m:n)非線性線性58第五十八頁，共78頁。例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（1）

S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達(dá)式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。59第五十九頁，共78頁。（2）

S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}

d1d5d2d4d3該結(jié)構(gòu)是非線性的。解：上述表達(dá)式可用圖形表示為：60第六十頁，共78頁。解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？答：物理結(jié)構(gòu)亦稱存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。存儲(chǔ)結(jié)構(gòu)可分為4大類：例：（見教材P6）復(fù)數(shù)3.0－2.3i的兩種存儲(chǔ)方式：順序、鏈?zhǔn)?、索引、散列?.303023.00300041503023.003000415－2.3法1：地址內(nèi)容法2：地址內(nèi)容2字節(jié)61第六十一頁，共78頁。解釋3：什么是數(shù)據(jù)的運(yùn)算？答：在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。它在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。最常用的數(shù)據(jù)運(yùn)算有5種：插入、刪除、修改、查找、排序62第六十二頁，共78頁。63第六十三頁，共78頁。相關(guān)操作的不同實(shí)現(xiàn)方法的時(shí)間/空間代價(jià)分析不同的數(shù)據(jù)組織方案對(duì)具體實(shí)現(xiàn)帶來的影響操作從物理到邏輯，從邏輯到抽象，從抽象到…64第六十四頁，共78頁。1.3抽象數(shù)據(jù)類型概念Q1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？Q2抽象數(shù)據(jù)類型如何定義？Q3抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn)？

討論：提示：教材中例1-6和例1-7分別給出了抽象數(shù)據(jù)類型“三元組”的定義、表示和實(shí)現(xiàn)，請(qǐng)?jiān)囬喿x。65第六十五頁，共78頁。Q1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？數(shù)據(jù)類型：是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）它與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）。66第六十六頁，共78頁。Q2抽象數(shù)據(jù)類型如何定義？抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，S，P）數(shù)據(jù)對(duì)象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式67第六十七頁，共78頁。例：給出自然數(shù)(Natural

Number

)的抽象數(shù)據(jù)類型定義。ADT

Natural_Number

isobjects:

一個(gè)整數(shù)的有序子集合，它開始于0，結(jié)束于機(jī)器能表示的最大整數(shù)(MAXINT)functions:

對(duì)于所有的x,yNatural_Number；TRUE,FALSEBoolean；

+,

-,<,==,=等都是可用的服務(wù)。Zero()：Natural

Number

返回0IsZero(x)：Booleanif(x==0)返回TRUE

else返回FALSEAdd(x,y)：Natural

Number

if(x+y<=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):Natural

Number

if(x<y)返回0else返回x-yEqual(x,y):Boolean

if(x==y)返回TRUEelse返回FALSESuccessor(x):

Natural

Number

if(x==MAXINT)返回xelse返回x+1end

Natural_Number

68第六十八頁，共78頁。Q3抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn)？

抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。注1

：它有些類似C語言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的服務(wù)。注2

：教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具。其描述語法見P10-11。但上機(jī)時(shí)要用具體語言實(shí)現(xiàn)，如C或C++等69第六十九頁，共78頁。70第七十頁，共78頁。71第七十一頁，共78頁。