| 网站首页 | 技术文章 | 下载频道 | 博客 | 编程论坛 |
 
| 技术教程首页 | 开发语言 | WEB开发 | .NET技术 | 数据库 | 操作系统 | 网页制作 |
 
 
您现在的位置: 编程中国 >> 技术教程 >> 开发语言 >> 数据结构 >> 正文
  ►  数据结构教程 第五课 线性表的类型定义
数据结构教程 第五课 线性表的类型定义
作者:未知    阅读人次:……    文章来源:未知    发布时间:2004/11/12    网友评论()条
 

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

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

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

授课内容:

复习:数据结构的种类

线性结构的特点:

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

(1)存在唯一的一个被称做“第一个”的数据元素;

(2)存在唯一的一个被称做“最后一个”的数据元素;

(3)除第一个之外,集合中的每个数据元素均只有一个前驱;

(4)除最后一个之外,集合中每个数据元素均只有一个后继。

一、线性表的定义

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

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

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

线性表例:

1、

1 2 3 4 5 6 7

2、

3、

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

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

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

a1
...
ai-1
ai
ai+1
...
an

aiai+1直接前驱元素,ai+1ai直接后继元素。

线性表中元素的个数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 !

三、总结

线性表的定义

线性表的类型定义

 

 
文章录入:静夜思    责任编辑:静夜思 
  • 上一篇文章:

  • 下一篇文章:

  •  
    相关文章
    原创地带
    24小时热门帖子