一、抽象數(shù)據(jù)類型定義（ADT）
作用：抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實世界，
2、抽象數(shù)據(jù)類型的表示與實現(xiàn)
。例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。定義：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。
關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲方式。定義它的人同樣不必要關(guān)心它如何存儲。
例：線性表這樣的抽象數(shù)據(jù)類型，其數(shù)學(xué)模型是：數(shù)據(jù)元素的集合，該集合內(nèi)的元素有這樣的關(guān)系：除第一個和最后一個外，每個元素有唯一的前趨和唯一的后繼。可以有這樣一些操作：插入一個元素、刪除一個元素等。
抽象數(shù)據(jù)類型分類
原子類型值不可分解，如int固定聚合類型值由確定數(shù)目的成分按某種結(jié)構(gòu)組成，如復(fù)數(shù)可變聚合類型值的成分?jǐn)?shù)目不確定如學(xué)生基本情況抽象數(shù)據(jù)類型表示法：
一、
三元組表示：（D，S，P）
其中D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。
二、書中的定義格式：
ADT 抽象數(shù)據(jù)類型名{
數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>
數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>
基本操作：<基本操作的定義>
}ADT 抽象數(shù)據(jù)類型名
例：線性表的表示
名稱線性表數(shù)據(jù)對象D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}任意數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R1={| ai-1,ai(- D,i=2,...,n}除第一個和最后一個外，每個元素有唯一的直接前趨和唯一的直接后繼基本操作ListInsert(&L,i,e)L為線性表，i為位置，e為數(shù)據(jù)元素。ListDelete(&L,i,e)...二、類C語言語法
類C語言語法示例
1、預(yù)定義常量和類型#define TRUE 1#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef in Status; //Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼。2、數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)typedef ElemType first;3、基本操作的算法
函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）{
//算法說明
語句序列
}//函數(shù)名
4、賦值語句簡單賦值：變量名=表達(dá)式；串聯(lián)賦值：變量名1=變量名2=...=變量名k=表達(dá)式；成組賦值:（變量名1，...,變量名k）=（表達(dá)式1，...,表達(dá)式k);結(jié)構(gòu)名=結(jié)構(gòu)名；
結(jié)構(gòu)名=（值1，...，值k);
變量名[]=表達(dá)式；
變量名[起始下標(biāo)..終止下標(biāo)]=變量名[起始下標(biāo)..終止下標(biāo)]；
交換賦值：變量名<-->變量名；條件賦值：變量名=條件表達(dá)式？表達(dá)式？表達(dá)式T：表達(dá)式F5、選擇語句
1、if（表達(dá)式） 語句；
2、if（表達(dá)式） 語句；
else 語句；
3、switch(表達(dá)式）{
case 值1：語句序列1；break;
...
case 值n：語句序列n；break;
default:語句序列n+1；break;
}
4、switch{
case 條件1：語句序列1；break;
...
case 條件n：語句序列n；break;
default:語句序列n+1；break;
}
6、循環(huán)語句for（賦初值表達(dá)式；條件；修改表達(dá)式序列）語句；while（條件）語句；
do{ 語句序列}while（條件）；7、結(jié)束語句
return [表達(dá)式]；
return; //函數(shù)結(jié)束語句
break; //case結(jié)束語句
exit(異常代碼); //異常結(jié)束語句
8、輸入和輸出語句scanf（[格式串]，變量1，...,變量n）；9、注釋//文字序列10、基本函數(shù)max（表達(dá)式1，...，表達(dá)式n）min,abs,floor,ceil,eof,eoln11、邏輯運算&&與運算；||或運算
例：線性表的實現(xiàn)：
ADT List{
數(shù)據(jù)對象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
數(shù)據(jù)關(guān)系: R1={| ai-1,ai(- D,i=2,...,n}
基本操作：
InitList(&L)
DestroyList(&L)
ListInsert(&L,i,e)
ListDelete(&L,i,&e)
}ADT List
ListInsert(List &L,int i,ElemType e)
{if(i<1||i>L.length+) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}
下面是C語言編譯通過的示例：
#define ERROR 0
#define OK 1
struct STU
{ char name[20];
char stuno[10];
int age; int score;
}stu[50];
struct LIST
{ struct STU stu[50];
int length;
}L;
int printlist(struct LIST L)
{ int i;
printf("name stuno age score\n");
for(i=0;i printf("%s %s\t%d\t%d\n", L.stu[i].name, L.stu[i].stuno, L.stu[i].age, L.stu[i].score); printf("\n"); } int listinsert(struct LIST *L,int i,struct STU e) { struct STU *p,*q; if (i<1||i>L->length+1) return ERROR; q=&(L->stu[i-1]); for(p=&L->stu[L->length-1];p>=q;--p) *(p+1)=*p; *q=e; ++L->length; return OK; }/*ListInsert Before i */ main() { struct STU e; L.length=0; strcpy(e.name,"zmofun"); strcpy(e.stuno,"100001"); e.age=80; e.score=1000; listinsert(&L,1,e); printlist(L); printf("List length now is %d.\n\n",L.length); strcpy(e.name,"bobjin"); strcpy(e.stuno,"100002"); e.age=80; e.score=1000; listinsert(&L,1,e); printlist(L); printf("List length now is %d.\n\n",L.length); }
E:\ZM\Zmdoc\datastru\class02>listdemo
name stuno age score
zmofun 100001 80 1000
List length now is 1.
name stuno age score
bobjin 100002 80 1000
zmofun 100001 80 1000
List length now is 2.三、總結(jié)
抽象數(shù)據(jù)類型定義；
抽象數(shù)據(jù)類型實現(xiàn)方法：一、類C語言實現(xiàn) 二、C語言實現(xiàn)