数据结构与算法(C语言版)第二章.ppt

《数据结构与算法(C语言版)第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表内容提要线性表的类型定义线性表的顺序表示与实现线性表的链式表示与实现一元多项式的表示及相加小结什麽是线性表定义：n（0）个数据元素的有限序列，记作（a1,a2,…,an）ai是表中数据元素，n是表长度。英文小写字母表(a，b，c，…，z)是一个长度为26的线性表。一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表。学生情况登记表是一个复杂的线性表。由若干数据项组成的数据元素称为记录(record)，由多个记录构成的线性表又称为文件(file)。线性表的特点线性表(linearlist)是一种最简单、常用的数据结构，通常一个线性

2、表是由n(n≥0)个性质相同的数据元素组成的有限序列。线性表的长度即为线性表中元素的个数n(n≥0)，当n＝0时，称为空表。非空线性表结构特征：(1)有且只有一个首结点a1，它无前驱；(2)有且只有一个尾结点an，它无后继；(3)其它所有结点有且只有一个前驱，也有且只有一个后继。线性表中的数据元素可以是各种各样的，但同一表中的元素必定具有相同特性。抽象数据类型线性表的定义线性表数据结构：List=(D，R)数据对象：D={ai

3、ai∈Elemtype，i=1，2，…，n，i>=1}数据关系：R={

4、ai-1，ai，∈D，i=2，

5、3，…，n}。抽象数据类型线性表的定义：见P19。线性表的应用举例联合算法：见P20算法2.1归并算法：见P21算法2.2补充归并算法：VoidMergeList(List*LA，List*LB，List*LC){/*已知线性表LA和LB中的数据元素按值非递减排列。*//*归并LA和LB得到新的线性表LC，LC的数据元素也按值非递减排列。*/InitList(LC)；/*构造一个空的线性表LC*/i=j=1；k=0；/*指针i和j初始值为1*/LA_len=ListLength(LA)；LB_len=ListLength(LB)；while((i

6、<=LA_len)&&(j＜=LB_len))线性表的应用举例{/*LA和LB均非空*/GetElem(LA，i，ai)；GetElem(LB，j，bj)；if(ai＜bj){ListInsert(LC，++k，ai)；++i；}/*LA的元素插入到表LC中*/elseif(ai=bj){ListInsert(LC，++k，bj)；++i；++j；}else{ListInsert(LC，++k，bj)；++j；}}while(i<＝LA_len){/*如果LA完，则将表LA中的所剩元素插入到表LC中*/GetElem(LA，i++，ai)；Lis

7、tInsert(LC，++k，ai)；线性表的应用举例}while(j＜＝LB_len){GetElem(LB，j++，bj)；ListInsert(LC，++k，bj)；}}/*MergeList*/判断下面算法有何功能：PURGE(LA)/**/List*LA；{inti=1，k，x，y；while(i

8、*/内容提要线性表的类型定义线性表的顺序表示与实现线性表的链式表示与实现一元多项式的表示及相加小结线性表的顺序表示线性表的顺序表示就是：把线性表的各个数据元素依次存储在一组地址连续的存储单元里。线性表的这种机内表示称为线性表的顺序映像或线性表的顺序存储结构，用这种方法存储的线性表简称为顺序表。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)＝LOC(ai)+L线性表的顺序

9、表示一般来说，线性表的第i个数据元素ai的存储位置为：LOC(ai)＝LOC(a1)+(i-1)*L，式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。顺序表的特点是，为表中相邻的元素ai和ai+1分配相邻的存储位置。只要确定存储线性表的起始位置LOC(a1)，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。线性表的顺序实现各种高级语言中的一维数组也具有随机存取的特性，因此常用一维数组来表示线性表。在C语言中就是用数组来表示顺序存储结构的线性表。建立一个一维数组V[0，

10、1，…，n-1]，使数据元素ai的下标与数组V的下标i相关联，把a1，a2，a3，…，ai，ai+1，…，an依次相继存入存储单元V[0