数据结构教程第六课线性表的顺序表示和实现

《数据结构教程第六课线性表的顺序表示和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、►  数据结构教程 第六课 线性表的顺序表示和实现数据结构教程 第六课 线性表的顺序表示和实现作者：未知    阅读人次：18914    文章来源：未知    发布时间：2004-11-12    网友评论(15)条 本课主题：线性表的顺序表示和实现教学目的：掌握线性表的顺序表示和实现方法教学重点：线性表的顺序表示和实现方法教学难点：线性表的顺序存储的实现方法授课内容：复习1、存储结构逻辑结构 “数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。存储结构 数据结构在计算机中的表示称为物理结构。又称存储结构。顺序存储结构链式存

2、储结构2、线性表的类型定义一、线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。2000:00012000:00032000:00052000:00072000:00092000:00112000:00132000:00152000:0017...2000:10012000:100300000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001

3、1100000000000010000000000000001001                                                a[9]123456789   假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。称顺序存

4、储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。二、顺序存储结构的线性表类C语言表示：线性表的动态分配顺序存储结构#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量以一数据元素存储长度为单位}SqList;三、顺序存储结构的线性表操作及C语言实现：顺序表的插入与删除操作：序号数据元素序号数据元素 序号数据

5、元素序号数据元素123456789   1213212428304277      <-25 123456789   121321242528304277    123456789   1213212428304277      ->24123456789   12132128304277     插入前n=8;插入后n=9; 删除前n=8;删除后n=7;顺序表的插入算法statusListInsert(List*L,inti,ElemTypee){structSTU*p,*q;if(i<1

6、

7、i>L->length+1)returnERROR;q

8、=&(L->elem[i-1]);for(p=&L->elem[L->length-1];p>=q;--p)*(p+1)=*p;*q=e;++L->length;returnOK;}/*ListInsertBeforei*/顺序表的合并算法voidMergeList(List*La,List*Lb,List*Lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pb=Lb->elem;Lc->listsize=Lc->length=La->length+Lb->length;pc=Lc->ele

9、m=(ElemType*)malloc(Lc->listsize*sizeof(ElemType));if(!Lc->elem)exit(OVERFLOW);pa_last=La->elem+La->length-1;pb_last=Lb->elem+Lb->length-1;while(pa<=pa_last&&pb<=pb_last){if(Less_EqualList(pa,pb))*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc+

10、+=*pb++;}顺序表的查找算法intLocateElem(List*La,ElemTypee,inttype){int