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

Teenits

Passion

Administrator

Rank: 20

Stubc Team

UID: 1
帖子: 1014
精华: 9
积分: 13754
所在学校: 南京理工大学
所属专业: 计算机科学与技术
阅读权限: 200
性别: 男
来自: 江苏
在线时间: 1362 小时
注册时间: 2008-3-9

管理员荣誉勋章论坛建设者荣誉勋章

1^# 大中小发表于 2008-5-14 20:00 只看该作者

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

教学目的：掌握线性表的概念和类型定义

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

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

授课内容：

复习：数据结构的种类

线性结构的特点：

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

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

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

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

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

一、线性表的定义

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

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

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

线性表例：

1、

2、

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

数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。
线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

...

ai-1

ai+1

...

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
}//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 !