资源描述：
《chap02 v2数据结构线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表例、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17一般……..……..…….…….…….如何实现该系统?系统分析•(1)逻辑结构的分析•(2)系统操作的分析•(3)存储结构•(4)系统实现线性表的逻辑结构及其基本操作线性表是n(n>=0)个相同类型数据元素a,a,…，01a构成的有限序列。n-1形式化定义：Linearlist=(D,R)D={a
2、a∈D,i=0,1,Λ,n−1,n>0}其中：ii0R={N}
3、,N={
4、a,a∈D,i=1,2
5、,Λ,n−1}i−1ii−1i0D为某个数据对象的集合0N为线性表长度•线性表的逻辑特征是：¾在非空的线性表，有且仅有一个开始结点a，它1没有直接前趋，而仅有一个直接后继a；2¾有且仅有一个终端结点a，它没有直接后继，而n仅有一个直接前趋a；n-1¾其余的内部结点a(2≦i≦n-1)都有且仅有一个直i接前趋a和一个直接后继a。i-1i+1线性表是一种典型的线性结构。•数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。线性表抽象数据类型数据元素：a同属于一个数据元素类，i=1,2,……,nn≧0。i结构关系：对所有的数据元素a（i=1,2,……,n－
6、1）存在次序关系,iii+1a无前驱，a无后继。1n基本操作：对线性表可执行以下的基本操作Initiate(L)构造一个空的线性表L。Length(L)求长度。Empty(L)判空表。Full(L)判表满。Clear(L)清空操作。Get(L,i)取元素。Locate(L,x)定位操作。Prior(L,data)求前驱。link(L,data)求后继。Insert(L,i,b)插入操作（前插）。Delete(L,i)删除操作。线性表的抽象类templateclassLinearList{public:LinearList();//构造函数～Li
7、nearList();//析构函数virtualintSize()const=0;//求表最大体积virtualintLength()const=0;//求表长度virtualintSearch(Tx)const=0;//搜索virtualintLocate(inti)const=0;//定位virtualT*getData(inti)const=0;//取值virtualvoidsetData(inti,Tx)=0;//赋值virtualboolInsert(inti,Tx)=0;//插入virtualboolRemove(inti,T&x)=0;//删除virtua
8、lboolIsEmpty()const=0;//判表空virtualboolIsFull()const=0;//判表满virtualvoidSort()=0；//排序virtualvoidinput()=0；//输入virtualvoidoutput()=0；//输出virtualLinearListoperator=(LinearList&L)=0;//复制};线性表在计算机中的实现•1.存储结构•2.操作的实现线性表的顺序存储结构•顺序存储定义：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。存储地址的计算•
9、问题：假设线性表的每个元素需占用d个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置LOC(a)，那么线性表中第i个数据元素的1存储位置LOC(a)=？i存储地址的计算•由于LOC(a)与第i-1个数据元素的存储位置LOC(a)ii-1之间满足下列关系：LOC(a)=LOC(a)+dii-1•因此线性表的第i个数据元素a的存储位置为：iLOC(a)=LOC(a)+(i-1)*di1顺序存储类•存储空间：用数组实现•属性：….操作：….结构类型的描述#definemaxSize100data[0..maxSize-1]//constintmaxSize=最大
10、容量；TypedefintT;a1typedefstruct{Tdata[maxSize];//顺序表的静态存储表示a2intn;//intlast;}SeqList;ntypedefintT;maxSizetypedefstruct{T*data;//顺序表的动态存储表示anintmaxSize；intn;//intlast;}SeqList;SeqListLa,Lb;La.data[0]表示线性表的第一个元素，La.n则表示线性表的当前元素个数•顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i
