数据结构教程第五课线性表的类型定义

文章作者 100test 发表时间 2007:03:10 18:29:57
来源 100Test.Com百考试题网

教学目的： 掌握线性表的概念和类型定义
教学重点： 线性表的类型定义
教学难点： 线性表的类型定义
授课内容：
复习：数据结构的种类
线性结构的特点：
在数据元素的非空有限集中，
（1）存在唯一的一个被称做“第一个”的数据元素；
（2）存在唯一的一个被称做“最后一个”的数据元素；
（3）除第一个之外，集合中的每个数据元素均只有一个前驱；
（4）除最后一个之外，集合中每个数据元素均只有一个后继。

二、线性表的类型定义

1、抽象数据类型线性表的定义如下：

ADT List{

数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}

数据关系: R1={i-1,ai>| ai-1,ai(- D,i=2,...,n}

基本操作：

InitList(&.L)
DestroyList(&.L)
ClearList(&.L)
ListEmpty(L)
ListLength(L)
GetElem(L,i,&.e)
LocateElem(L,e,compare())
PriorElem(L,cur_e,&.pre_e)
NextElem(L,cur_e,&.next_e)
ListInsert(&.L,i,e)
ListDelete(&.L,i,&.e)
ListTraverse(L,visit())
union(List &.La,List &.Lb)

}ADT List

2、部分操作的类C实现：

InitList(&.L)

{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)).

if(!L.elem)exit(OVERFLOW).

L.length=0.

L.listsize=LIST_INIT_SIZE.

return OK.

}//InitList

GetElem(L,i,&.e)

{*e=L.lem[i]

}//GetElem

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.

}//ListInsert