3、ai∈Elementset,i=1,2,…,n,n≥0}R={H}H={
4、ai-1,ai∈D,i=2,…,n}操作：设L的型为LIST线性表实例，x的型为elementtype的元素实例，p为位置变量。所有操作描述为：①INSERT(x,p,L)②LOCATE(x,L)③RETRI
5、EVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)数学模型3.1抽象数据型线性表举例：设计函数DELEVAL（LIST&L,elementtyped)，其功能为删除L中所有值为d的元素。VoidDELEVAL(LIST&L,elementtyped){positionp;p=FIRST(L);while(P!=END(L)){if(same(RETRIEVE(p,L),d))DELETE(p,L);elsep=NEXT(p,L);}}
6、3.2线性表的实现问题：确定数据结构（存储结构）实现型LIST，并在此基础上实现各个基本操作。存储结构的三种方式：①连续的存储空间（数组）→静态存储②非连续存储空间——指针（链表）→动态存储③游标（连续存储空间+动态管理思想）→静态链表3.2.1指针和游标指针：地址量，其值为另一存储空间的地址；游标：整型量，其值为数组的下标，用以表示指定元素的“地址”或“位置”3.2.2线性表的数组实现第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图2-1线性表的数组实现表的长度……第i个元
7、素1≤i≤last类型定义：#definemaxlength100structLIST{elementtypeelements[maxlength];intlast;};位置类型：typedefintposition;线性表L:LISTL;3.2.2线性表的数组实现操作：①VoidINSERT(elementtypex,positionp,LIST&L){positionq;if(L.last>=maxlength–1)error(“表满”)；elseif((P>L.last+1)
8、
9、(p<1))error(“指
10、定位置不存在”)；else{for(q=L.last;q>=p;q--)L.elements[q+1]=L.elements[q];L.last=L.last+1;L.elements[p]=x;}}②positionLOCATE(elementtypex,LISTL){positionq;for(q=1;q<=L.last;q++)if(L.elements[q]==x)return(q);return(L.last+1);}3.2.2线性表的数组实现③elementtypeRETRIEVE(positionp
11、,LISTL){if(p>L.last)error(“指定元素不存在”);elsereturn(L.elements[p]);}④VoidDELETE(positionp,LIST&L){positionq;if((p>L.last)
12、
13、(p<1))error(“指定位置不存在”)；else{L.last=L.last–1;for(q=p;q<=L.last;q++)L.elements[q]=L.elements[q+1];}}3.2.2线性表的数组实现⑤positionPREVIOUS(positionp,L
14、ISTL){if((p<=1)
15、
16、(p>L.last))error(“前驱元素不存在”);elsereturn(p–1);}⑧positionEND(LISTL){return(L.last+1);}⑦positionFIRST(LISTL){return(1);}positionNEXT(positionp,LISTL){if((p<1)
17、
18、(p>=L.last))er
