首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第五课 线性表的类型定义

数据结构教程 第五课 线性表的类型定义2007-05-17教学目的： 掌握线性表的概念和类型定义

教学重点： 线性表的类型定义

教学难点： 线性表的类型定义

授课内容：

复习：数据结构的种类

线性结构的特点：

在数据元素的非空有限集中，

（1）存在唯一的一个被称做“第一个”的数据元素；

（2）存在唯一的一个被称做“最后一个”的数据元素；

（3）除第一个之外，集合中的每个数据元素均只有一个前驱；

（4）除最后一个之外，集合中每个数据元素均只有一个后继。

一、线性表的定义

线性表是最常用且最简单的一种数据结构。

一个线性表是n个数据元素的有限序列。

数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。

线性表例：

1、

1

2

3

4

5

6

7

2、

学号	姓名	语文	数学	C语言
6201001	张三	85	54	92
6201002	李四	92	84	64
6201003	王五	87	74	73
6201004
...

数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。

线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

a1

...

ai-1

ai

ai+1

...

an

ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。

线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。

二、线性表的类型定义

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

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）
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

void union（List &La,List &Lb）

{La_len=ListLength（La）;Lb_len=ListLength（Lb）;

for（i=1;i<=Lb_len;i++）{

GetElem（Lb,i,e）;

if（！LocateElem（La,e,equal））

ListInsert（La,++La_len,e）;

}//union

void MergeList（List La,List Lb,List &Lc）

{InitList（Lc）;

i=j=1;k=0;

La_len=ListLength（La）;Lb_len=ListLength（Lb）;

while（（i<=La_len）&&（j<Lb_len））{

GetElem（La,i,ai）;GetElem（Lb,j,bj）;

if（ai<=bj）{ListInsert（Lc,++k,ai）;++i;}

else{ListInsert（Lc,++k,bj）;++j;}

}

while（k<=La_len）{

GetElem（La,i++,ai）;ListInsert（Lc,++k,ai）;

}

while（j<=Lb_len）{

GetElem（Lb,j++,bj）;ListInsert（Lc,++k,bj）;

}

}//MergeList

3、部分操作的C语言实现,下面是程序运行的结果：

-------------------List Demo is running...---------------- First is InsertList function. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 List A length now is 2. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 List A length now is 3. name stuno age score zmofun 100001 80 1000 bobjin 100002 80 1000 stu1 100001 80 1000 List B length now is 3. Second is UnionList function. Now union List A and List B..... name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 zmofun 100001 80 1000 bobjin 100002 80 1000 List A length now is 5. Welcome to visit http://zmofun.heha.net ！

三、总结

线性表的定义

线性表的类型定义