数据结构(二)线性表.pptx

第二章 线性表;2.1 线性表的逻辑结构 线性表：由n(n≥0)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，…an) 这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）; …….; 从以上例子可看出线性表的逻辑特征是： (1)对非空的线性表，有且仅有一个开始结点a1，它没有直接前驱，而仅有一个直接后继a2； (2)有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前驱an-1； (3)其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前驱ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。;2.2 线性表的顺序存储结构 2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点。则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系： Loc(ai+1)=Loc(ai)+m ;线性表的第i个数据元素ai的存储位置为 : ; 由于在高级语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，利用C++语言的结构类型来定义顺序表类型。 # define ListSize 100 //表容量 typedef int DataType;//以int为例 struct Sqlist{ DataType data[ListSize]; int lenth;//当前表中元素数 };;2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C/C++语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素位置是L.data[i-1]。 线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的i(1≤i≤n+1)个位置上，插入一个新结点x， 使长度为n的线性表 (a1，…a i-1，ai，…，an) 变成长度为n+1的线性表 (a1，…a i-1，x，ai，…，an);注： 可用memmove(L.data+i,L.dada+i-1,(L.lenth-i+1)*sizeof(DataType)) 代替for循环（包含文件： string.h,一般格式 格式： memmove(目的地址，源地址，移动字节数));memcpy(目的地址,源地址，字节数） memset(目的地址,字符，字节数）;算法分析 设表的长度为n。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此，所需移动结点的次数依赖于 (1) 表的长度 (2) 插入位置。 当=n+1时，不移动-最好情况； 当=1时，需移动表中所有结点-最坏情况，;算法的平均移动 由于插入可能在表中任何位置上进行，在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。 Pi代表在第i个位置插入概率，则 Eis(n)= p1 ×n+p2 ×(n-1)+ ….+ pn × 1+pn+1 × 0 若表中任何位置(1≤i≤n+1)上插入结点的概率是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 因此，在等概率插入的情况下： Eis(n)=1/(n+1)[n+(n-1)+…+1+0]=n/2;结论：在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就