數據結構教程 第二課 抽象數據類型的表示與實現
責任編輯:chineselng    瀏覽:5137次    時間: 2008-04-05 22:47:56      

摘要:本課主題: 抽象數據類型的表示與實現 教學目的: 了解抽象數據類型的定義、表示和實現方法 教學重點: 抽象數據類型表示法、類C語言語法 教學難點: 抽象數據類型表示法 授課內容: 一、抽象數據類型定義(ADT) 作用:抽象數據類型可以使我們更容易描述現實世界。..

關鍵詞:數據 結構 教程
分享到:

本課主題: 抽象數據類型的表示與實現

教學目的: 了解抽象數據類型的定義、表示和實現方法

教學重點: 抽象數據類型表示法、類C語言語法

教學難點: 抽象數據類型表示法

授課內容:

一、抽象數據類型定義(ADT)

作用:抽象數據類型可以使我們更容易描述現實世界。例:用線性表描述學生成績表,用樹或圖描述遺傳關系。

定義:一個數學模型以及定義在該模型上的一組操作。

關鍵:使用它的人可以只關心它的邏輯特征,不需要了解它的存儲方式。定義它的人同樣不必要關心它如何存儲。

例:線性表這樣的抽象數據類型,其數學模型是:數據元素的集合,該集合內的元素有這樣的關系:除第一個和最后一個外,每個元素有唯一的前趨和唯一的后繼。可以有這樣一些操作:插入一個元素、刪除一個元素等。

抽象數據類型分類
原子類型 值不可分解,如int
固定聚合類型 值由確定數目的成分按某種結構組成,如復數
可變聚合類型 值的成分數目不確定如學生基本情況

抽象數據類型表示法:

一、

三元組表示:(D,S,P)

其中D是數據對象,S是D上的關系集,P是對D的基本操作集。

二、書中的定義格式:

ADT 抽象數據類型名{

數據對象:<數據對象的定義>

數據關系:<數據關系的定義>

基本操作:<基本操作的定義>

}ADT 抽象數據類型名

例:線性表的表示

名稱 線性表  
數據對象 D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 任意數據元素的集合
數據關系 R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 除第一個和最后一個外,每個元素有唯一的直接前趨和唯一的直接后繼
基本操作 ListInsert(&L,i,e) L為線性表,i為位置,e為數據元素。
ListDelete(&L,i,e)
...

二、類C語言語法

類C語言語法示例
1、預定義常量和類型 #define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef in Status; //Status是函數的類型,其值是函數結果狀態代碼。
2、數據結構的存儲結構 typedef ElemType first;
3、基本操作的算法

函數類型 函數名(函數參數表){
//算法說明
語句序列
}//函數名

4、賦值語句 簡單賦值: 變量名=表達式;
串聯賦值: 變量名1=變量名2=...=變量名k=表達式;
成組賦值: (變量名1,...,變量名k)=(表達式1,...,表達式k);
結構名=結構名;
結構名=(值1,...,值k);
變量名[]=表達式;
變量名[起始下標..終止下標]=變量名[起始下標..終止下標];
交換賦值: 變量名<-->變量名;
條件賦值: 變量名=條件表達式?表達式?表達式T:表達式F
5、選擇語句

1、if(表達式) 語句;
2、if(表達式) 語句;
else 語句;
3、switch(表達式){
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、循環語句 for(賦初值表達式;條件;修改表達式序列)語句;
while(條件)語句;
do{ 語句序列}while(條件);
7、結束語句

return [表達式];
return; //函數結束語句
break; //case結束語句
exit(異常代碼); //異常結束語句

8、輸入和輸出語句 scanf([格式串],變量1,...,變量n);
9、注釋 //文字序列
10、基本函數 max(表達式1,...,表達式n)
min,abs,floor,ceil,eof,eoln
11、邏輯運算 &&與運算;||或運算

例:線性表的實現:
ADT List{

數據對象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}

數據關系: R1={<ai-1,ai>| 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<L.length;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.

 

三、總結

抽象數據類型定義

抽象數據類型實現方法:一、類C語言實現 二、C語言實現

】【打印繁體】【投稿】 【收藏】 【推薦】 【舉報】 【評論】 【關閉】【返回頂部
亚洲AV国产AV手机在线