抽象数据类型（ADT）

深藏阁楼爱情的钟 2022-05-12 11:54 316阅读 0赞

**一、抽象数据类型定义（ADT）**

> 作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
> 
> 定义：一个数学模型以及定义在该模型上的一组操作。
> 
> 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
> 
> 例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td colspan="2"> 
>     <div>
>       抽象数据类型分类 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td>原子类型</td> 
>    <td>值不可分解，如int</td> 
>   </tr> 
>   <tr> 
>    <td>固定聚合类型</td> 
>    <td>值由确定数目的成分按某种结构组成，如复数</td> 
>   </tr> 
>   <tr> 
>    <td>可变聚合类型</td> 
>    <td>值的成分数目不确定如学生基本情况</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 抽象数据类型表示法：
> 
> 一、
> 
> **三元组表示：（D，S，P）**
> 
> **其中D是数据对象，S是D上的关系集，P是对D的基本操作集。**
> 
> 二、书中的定义格式：
> 
> **ADT 抽象数据类型名\{** 
> 
> > **数据对象：<数据对象的定义>**
> > 
> > **数据关系：<数据关系的定义>**
> > 
> > **基本操作：<基本操作的定义>**
> 
> **\}ADT 抽象数据类型名**
> 
> 例：线性表的表示
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>名称</td> 
>    <td>线性表</td> 
>    <td>&nbsp;</td> 
>   </tr> 
>   <tr> 
>    <td>数据对象</td> 
>    <td>D={ai| ai(-ElemSet,i=1,2,...,n,n&gt;=0}</td> 
>    <td>任意数据元素的集合</td> 
>   </tr> 
>   <tr> 
>    <td>数据关系</td> 
>    <td>R1={&lt;ai-1,ai&gt;| ai-1,ai(- D,i=2,...,n}</td> 
>    <td>除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继</td> 
>   </tr> 
>   <tr> 
>    <td>基本操作</td> 
>    <td>ListInsert(&amp;L,i,e)</td> 
>    <td>L为线性表，i为位置，e为数据元素。</td> 
>   </tr> 
>   <tr> 
>    <td>ListDelete(&amp;L,i,e)</td> 
>   </tr> 
>   <tr> 
>    <td>...</td> 
>   </tr> 
>  </tbody> 
> </table>

二、类C语言语法

> <table> 
>  <tbody> 
>   <tr> 
>    <td colspan="3"> 
>     <div>
>       类C语言语法示例 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td>1、预定义常量和类型</td> 
>    <td colspan="2">#define TRUE 1<br> #define FALSE 0<br> #define OK 1<br> #define ERROR 0<br> #define INFEASIBLE -1<br> #define OVERFLOW -2<br> typedef in Status; //Status是函数的类型，其值是函数结果状态代码。</td> 
>   </tr> 
>   <tr> 
>    <td>2、数据结构的存储结构</td> 
>    <td colspan="2">typedef ElemType first;</td> 
>   </tr> 
>   <tr> 
>    <td>3、基本操作的算法</td> 
>    <td colspan="2"> <p>函数类型 函数名（函数参数表）{ <br> //算法说明<br> 语句序列<br> }//函数名</p> </td> 
>   </tr> 
>   <tr> 
>    <td>4、赋值语句</td> 
>    <td>简单赋值：</td> 
>    <td>变量名=表达式；</td> 
>   </tr> 
>   <tr> 
>    <td>串联赋值：</td> 
>    <td>变量名1=变量名2=...=变量名k=表达式；</td> 
>   </tr> 
>   <tr> 
>    <td>成组赋值:</td> 
>    <td>（变量名1，...,变量名k）=（表达式1，...,表达式k);<br> 结构名=结构名；<br> 结构名=（值1，...，值k);<br> 变量名[]=表达式；<br> 变量名[起始下标..终止下标]=变量名[起始下标..终止下标]；&nbsp;</td> 
>   </tr> 
>   <tr> 
>    <td>交换赋值：</td> 
>    <td>变量名&lt;--&gt;变量名；</td> 
>   </tr> 
>   <tr> 
>    <td>条件赋值：</td> 
>    <td>变量名=条件表达式？表达式？表达式T：表达式F</td> 
>   </tr> 
>   <tr> 
>    <td>5、选择语句</td> 
>    <td colspan="2"> <p>1、if（表达式） 语句；<br> 2、if（表达式） 语句；<br> else 语句；<br> 3、switch(表达式）{ <br> case 值1：语句序列1；break;</p> <p>...<br> case 值n：语句序列n；break;&nbsp;<br> default:语句序列n+1；break;&nbsp;<br> }<br> 4、switch{ <br> case 条件1：语句序列1；break;</p> <p>...<br> case 条件n：语句序列n；break;&nbsp;<br> default:语句序列n+1；break;&nbsp;<br> }</p> </td> 
>   </tr> 
>   <tr> 
>    <td>6、循环语句</td> 
>    <td colspan="2">for（赋初值表达式；条件；修改表达式序列）语句；<br> while（条件）语句；<br> do{ 语句序列}while（条件）；</td> 
>   </tr> 
>   <tr> 
>    <td>7、结束语句</td> 
>    <td colspan="2"> <p>return [表达式]；<br> return; //函数结束语句<br> break; //case结束语句<br> exit(异常代码); //异常结束语句</p> </td> 
>   </tr> 
>   <tr> 
>    <td>8、输入和输出语句</td> 
>    <td colspan="2">scanf（[格式串]，变量1，...,变量n）；</td> 
>   </tr> 
>   <tr> 
>    <td>9、注释</td> 
>    <td colspan="2">//文字序列</td> 
>   </tr> 
>   <tr> 
>    <td>10、基本函数</td> 
>    <td colspan="2">max（表达式1，...，表达式n）<br> min,abs,floor,ceil,eof,eoln</td> 
>   </tr> 
>   <tr> 
>    <td>11、逻辑运算</td> 
>    <td colspan="2">&amp;&amp;与运算；||或运算</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 例：线性表的实现：  
> 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语言编译通过的示例][C]：
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td> <p><strong>#define ERROR 0&nbsp;<br> #define OK 1&nbsp;<br> struct STU<br> { char name[20];<br> char stuno[10];&nbsp;<br> int age; int score;&nbsp;<br> }stu[50];&nbsp;<br> struct LIST&nbsp;<br> { struct STU stu[50];&nbsp;<br> int length;&nbsp;<br> }L;&nbsp;<br><br></strong><strong>int printlist(struct LIST L)<br> { int i;<br> printf("name stuno age score/n");&nbsp;<br> for(i=0;i&lt;L.length;i++)&nbsp;<br> printf("%s %s/t%d/t%d/n", L.stu[i].name, L.stu[i].stuno, L.stu[i].age, L.stu[i].score);&nbsp;<br> printf("/n");&nbsp;<br> }<br><br> int listinsert(struct LIST *L,int i,struct STU e)&nbsp;<br> { struct STU *p,*q;&nbsp;<br> if (i&lt;1||i&gt;L-&gt;length+1)&nbsp;<br> return ERROR;&nbsp;<br> q=&amp;(L-&gt;stu[i-1]);&nbsp;<br> for(p=&amp;L-&gt;stu[L-&gt;length-1];p&gt;=q;--p)&nbsp;<br> *(p+1)=*p; *q=e; ++L-&gt;length;&nbsp;<br> return OK;&nbsp;<br> }/*ListInsert Before i */<br><br> main()&nbsp;<br> { struct STU e;&nbsp;<br> L.length=0;&nbsp;<br> strcpy(e.name,"zmofun");&nbsp;<br> strcpy(e.stuno,"100001");&nbsp;<br> e.age=80;&nbsp;<br> e.score=1000;&nbsp;<br> listinsert(&amp;L,1,e);&nbsp;<br> printlist(L);&nbsp;<br> printf("List length now is %d./n/n",L.length);</strong></p> <p><strong>strcpy(e.name,"bobjin");&nbsp;<br> strcpy(e.stuno,"100002");&nbsp;<br> e.age=80;&nbsp;<br> e.score=1000;&nbsp;<br> listinsert(&amp;L,1,e);&nbsp;<br> printlist(L);&nbsp;<br> printf("List length now is %d./n/n",L.length);&nbsp;<br> }</strong></p> </td> 
>   </tr> 
>  </tbody> 
> </table>

[C]: http://219.219.90.4:8080/datastru/class02/Listdemo.txt