数据结构课件-线性表顺序表.ppt

《数据结构课件-线性表顺序表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表程序=数据结构+算法数据结构的研究内容：逻辑结构：数据元素间的客观联系存储结构：数据在计算机内部的存储方法算法研究数据结构线性结构：线性表，栈，队列非线性结构：树，图在各种程序设计与软件开发中都要涉及到对数据的组织、存储、管理和处理在环境领域：不同环境监测点的监测指标统计在土地领域：不同宗地的属性在测绘领域：外业测绘信息的存储，各测点三维坐标的存储最常见的数据组织方式：表格形式的数据编号名称SO2含量水质指标悬浮物指标宗地号周长面积使用者土地等级点号等级XYH学号姓名性别籍贯年龄成绩2.1线性表的基本概念和运算2.1.1逻辑结构定义

2、定义：线性表是由n（n≥0）个数据元素a1,a2,……，an构成的有限序列。n为表的长度，n=0时称为空表。非空的线性表（n＞0）记作（a1,a2,……，an）。数据元素可以有不同的含义，但同一线性表中的元素必须具有相同的特性。9119辽宁男李铁02…20年龄87北京男杨晨01成绩籍贯性别姓名学号9520上海男祁宏30……………在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2(或没有后继)；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1(或没有前趋)；其余的内部结点ai(2≦i≦n-1

3、)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。2.1.2线性表的ADT表示ADTList{数据对象：L={ai

4、ai∈元素集合，i=1，2，…n，n≥0}数据关系：R={〈ai-1，ai〉

5、ai-1，ai∈元素集合，i=1，2，……n}基本操作：{构造空表initList(&L)销毁线性表destroyList(&L)清空表clearList(&L)求长度listLength(L)取结点getElem(L,index,&e)定位locateElem(L,x)插入insertElem(&L,index,e)删除deleteElem

6、(&L,index,&e)取直接前趋priorElem(L,cur_e,&prior_e)取直接后继nextElem(L,cur_e,&next_e)}}2.1.3线性表的运算清空表clearList(&L)学号成绩clearList(list);取结点getElem(L,index,&e)getElem(list,2,&e)序号成绩017802900384……定位locateElem(L,x)locateElem(list,84)==3学号成绩017802900384……插入insertElem(&L,index,e)：在index位置

7、插入值为e的元素insertElem(list,3,87)学号成绩017802900384……308390027801成绩学号83318404……8703删除deleteElem(&L,index)deleteElem(list,3)学号成绩017802900384……298390027801成绩学号83308404……870390027801成绩学号83308404……取直接前趋priorElem(L,cur_e,&prior_e)取直接后继nextElem(L,cur_e,&next_e)90027801成绩学号83308404……8

8、703PRIOR(L,87)NEXT(L,87)对线性表的所有复杂操作都可以由以上操作完成e.g清除线性表L中多余的重复结点从i=1开始，每次取第i个元素getElem(L,i,&e)对第i个元素后的所有元素进行比较，若值相同则删除判断完后将i++，继续执行，直到i=listLengh(L)Purge(Linear_Listlist){inti=1,j,x,y;while(i

9、&y);if(x==y)deleteElem(list,j);elsej++;}i++;}}可以在循环外把listLength(L)的值保存起来在后面使用吗？THENEXTIS线性表的存储结构及相应算法的实现顺序存储：顺序表数组链接存储：链表指针2.2线性表的顺序存储结构2.2.1顺序表用一组连续的存储单元依次存储线性表的元素Loc(ai+1)=Loc(ai)+cLoc(ai)=Loc(a1)+(i-1)*c1≤i≤nc为线性表每个元素占用的存储单元随机存取结构a1a2a3…ai…an元素序号123in备用区存储地址bb+cb+2cb+(

10、i-1)*cb+(n-1)*cb+n*c用C语言中的向量（一维数组）描述顺序表typedefintdatatype;/*int可以用其它类型代替*/#definemaxsize1024/*不加