(3.3)--1.3 线性表的顺序存储.ppt

《(3.3)--1.3 线性表的顺序存储.ppt》由会员分享，可在线阅读，更多相关《(3.3)--1.3 线性表的顺序存储.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、三、线性表的顺序存储用一组地址连续的存储单元依次存放线性表中的数据元素。线性表中任意一个数据元素的存储位置都可以用线性表中第一个数据元素a1的存储地址加上偏移表示。其中：K为一个数据元素所占存储量。第1节定义的线性表抽象数据类型List，可以采用顺序存储结构实现。1/Ex1.1 线性表的顺序表示声明模块SeqList.h#ifndef _SEQLIST_H_INCLUDED_#define _SEQLIST_H_INCLUDED_typedef int DataElem;/假设元素类型为整型/线性表类型struct SeqList DataElem*pDatas;/存放元素表的缓冲区指针 in

2、t iLength;/线性表长度 int iSize;/缓冲区大小;typedef DataElem*Position;/线性表中位置类型/.在此省略线性表各基本操作的函数声明#endif/_SEQLIST_H_INCLUDED_23/1.创建空线性表/建立一个最多可存放iSize个元素的空线性表，失败时缓冲区指针为NULLstruct SeqList Create(int iSize)struct SeqList list;/申请存放线性表元素的连续内存空间 list.pDatas=(DataElem*)malloc(iSize*sizeof(DataElem);list.iLength=0

3、;list.iSize=iSize;if(list.pDatas=NULL)/申请不到空间 list.iSize=0;return list;4/2.线性表清空/元素个数置为0void Clear(struct SeqList*pSeqList)pSeqList-iLength=0;/3.销毁一个线性表，不再使用，释放缓冲区void Destroy(struct SeqList*pSeqList)free(pSeqList-pDatas);/释放缓冲区 pSeqList-pDatas=NULL;pSeqList-iSize=0;5/4.根据已有线性表，复制一个内容相同的新线性表/返回复制后新线

4、性表，失败时返回线性表的头指针为NULL struct SeqList Copy(struct SeqList srcSeqList)struct SeqList destSeqList;destSeqList=Create(srcSeqList.iSize);/创建一个具有相同大小缓冲区的空线性表 if(destSeqList.pDatas=NULL)return destSeqList;/创建失败时直接返回 int i;for(i=0;i=1&i=list.iLength)return list.pDatas+(i-1);return list.pDatas+list.iLength;/超

5、出范围，返回结束位置9/11.定位元素位置/根据数据元素e查找它在线性表中出现的位置，若存在，则返回它的有效位置；/否则返回EndPosition(L)Position LocateElem(struct SeqList list,DataElem e)int i;for(i=0;i iSize=pSeqList-iLength)/空间已满，先扩充空间 struct SeqList newSeqList=Create(2*pSeqList-iSize);/建立2倍空间的临时线性表 if(newSeqList.pDatas=NULL)return 0;/申请不到空间，操作失败 int i;for

6、(i=0;i iLength;+i)/复制所有元素 newSeqList.pDatas i=pSeqList-pDatas i;newSeqList.iLength=i;/设置线性表长度 （待续）12 pos=newSeqList.pDatas+(pos-pSeqList-pDatas);/原pos必须更新 Destroy(pSeqList);/销毁原线性表，板卡它的缓冲区，避免内存泄漏 *pSeqList=newSeqList;/用扩充空间后线性表代替原线性表 assert(pSeqList-iSize pSeqList-iLength);/线性表内存空间必有空余 Position last

7、Pos=pSeqList-pDatas+pSeqList-iLength;/线性表后空余位置 while(pos!=lastPos)/从后往前循环后移，直到到达指定位置 *lastPos=*(lastPos-1);/元素后移一个位置 -lastPos;/准备处理前一位置元素 *pos=e;/将元素存入已空出位置 +pSeqList-iLength;/调整线性表长度 return 1;13/15.删除元素/删除线性表中pos有效位置所在数据元素，线性表的表长减1void Delete(struct SeqList*pSeqList,Position pos)Position endPos=End

8、Position(*pSeqList);assert(pos!=endPos);/断言，包含头文件assert.h +pos;/后移一位置 while(pos!=endPos)*(pos-1)=*pos;/后一位置元素前移 +pos;/准备后移下一个元素 -pSeqList-iLength;/调整线性表长度14/通过抽象数据类型SeqList的基本操作打印线性表void Print(struct SeqList list)printf();Position pos=BeginPosition(list);if(pos!=EndPosition(list)printf(%d,GetElem(li

9、st,pos);pos=NextPosition(list,pos);while(pos!=EndPosition(list)printf(,%d,GetElem(list,pos);pos=NextPosition(list,pos);printf()n);15 int main()int i;struct SeqList list=Create(1);/创建一个空线性表 Print(list);/打印线性表 for(i=1;i=5;+i)/尾部循环插入i InsertBefore(&list,EndPosition(list),i);Print(list);Position pos=LocateElem(list,3);/查找元素3 if(pos!=EndPosition(list)Delete(&list,pos);/查找到元素时，删除元素 InsertBefore(&list,BeginPosition(list),8);/头部插入元素8 Print(list);Destroy(&list);/销毁线性表，避免内存泄漏 return 0;1617