神马文学网第五课 线性表的类型定义
来源：百度文库 编辑：神马文学网 时间：2024/10/06 10:20:47
教学目的： 掌握线性表的概念和类型定义
教学重点： 线性表的类型定义
教学难点： 线性表的类型定义
授课内容：
复习：数据结构的种类
线性结构的特点：
在数据元素的非空有限集中，
（1）存在唯一的一个被称做“第一个”的数据元素；
（2）存在唯一的一个被称做“最后一个”的数据元素；
（3）除第一个之外，集合中的每个数据元素均只有一个前驱；
（4）除最后一个之外，集合中每个数据元素均只有一个后继。
一、线性表的定义
线性表是最常用且最简单的一种数据结构。
一个线性表是n个数据元素的有限序列。
数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
线性表例：
1、
1234567
2、
学号姓名语文数学C语言
6201001张三855492
6201002李四928464
6201003王五877473
6201004
...
数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。
线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。
a1...ai-1aiai+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(- 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)&&(jGetElem(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 !
三、总结
线性表的定义
线性表的类型定义
教学重点： 线性表的类型定义
教学难点： 线性表的类型定义
授课内容：
复习：数据结构的种类
线性结构的特点：
在数据元素的非空有限集中，
（1）存在唯一的一个被称做“第一个”的数据元素；
（2）存在唯一的一个被称做“最后一个”的数据元素；
（3）除第一个之外，集合中的每个数据元素均只有一个前驱；
（4）除最后一个之外，集合中每个数据元素均只有一个后继。
一、线性表的定义
线性表是最常用且最简单的一种数据结构。
一个线性表是n个数据元素的有限序列。
数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
线性表例：
1、
1234567
2、
学号姓名语文数学C语言
6201001张三855492
6201002李四928464
6201003王五877473
6201004
...
数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。
线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。
a1...ai-1aiai+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={
基本操作：
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
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 !
三、总结
线性表的定义
线性表的类型定义
第五课 线性表的类型定义
第六课 线性表的顺序表示和实现
C#和.NET Framework还允许用户根据这些简单的类型定义复合类型。
大众文化的定义[1]--------《文化研究》第五期
条款19：定义并实现接口优于继承类型 - 《Effective C#中文版：改善C#程序的...
通过typedef定义指针类型用法
4.6.2 第五媒体的媒介类型叙述_作家俱乐部_第五媒体_天极ChinaByte
信息学竞赛→图片作品→查看图片→线性表的数组实现
线性分类器的求解-直观角度
线性电源和开关电源的区别
线性科学观下糟糕的营养科学
浅谈低压差线性稳压器的压差和功耗
生物学中非线性数学模型的构建与应用
生物学中非线性数学模型的构建与应用2
线性和颜色函数方面的公式实例
辩证看待国家投融资模式---创新不是线性的
用线性加深工具拉出漂亮的虚化背景
说课的意义类型技巧
线性思维
MySQL的表类型和存储引擎
穿什么类型的服装,自查表
穿什么类型的服装,自查表
你适合类型的服装,自查表
MySQL的表类型和存储引擎