资源描述：
《第02章 线性数据结构1-线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性数据结构及其运算1线性表栈和队列数组2线性表的定义线性表是由n（n>=0）个数据元素a1，a2，……，an组成的一个有限序列。表中的每一个数据元素，除了第一个外，有且只有一个前趋；除了最后一个外，有且只有一个后继。线性表或是一个空表（n=0），或可以表示为（a1，a2，…，ai，…，an）其中ai称为线性表中的一个结点，n为表的长度。数学形式描述：B=(D,R)D={ai
2、i=1,2,..,n},R={(ai-1,ai)
3、i=2,3,…,n}线性表3例子1n维向量（x1，x2，…，xn）是长度为n的线性表，xi为数据元素矩阵，每一行是一个
4、数据元素（一个线性表），行数为其长度线性表4例子2表格，数据元素由若干数据项组成，称为记录，有多个记录构成的线性表又称为文件。记录学生健康情况登记表线性表5非空线性表的特点有且只有一个头（根）结点a1，它没有前趋；有且只有一个尾（终端）结点an，它没有后继；除了头结点和尾结点外，每个结点有且只有一个前件和一个后件。线性表中的结点个数n称为线性表的长度。n＝0时，线性表为空表。线性表6线性表的顺序存储结构特点：线性表的前后件元素在存储空间中是相邻的（存储空间是连续的）;前件元素一定在后件元素的前面（有序的）。a1a2a3…ai…an顺序存储结构(顺序
5、表)：线性表7存储地址的计算假设线性表中的第一个数据元素的存储地址（首地址）为ADR(a1)，每个数据元素占k个字节，在线性表中第i个元素ai在计算机存储空间中的存储地址为:ADR(ai)＝ADR(a1)＋(i－1)k线性表8建立空线性表的顺序存储空间在C语言中，向量即一维数组，所以可用一维数组来描述顺序存储结构。线性表#definemaxlen100structsqlisttp{intelem[maxlen];intlast;};其中maxlen是大于线性表长度的一个整数，线性表的各个元素a1，a2，…，an依次存放在一维数组elem的各个分量e
6、lem[1],elem[2],…,elem[n]中。数据域last指示最后一个数据元素在数组中的位置，也即线性表的长度。9线性表顺序存储结构的主要运算插入--在线性表的指定位置处加入一个新的元素删除--在线性表中删除指定的元素查找--在线性表中查找某个(或某些)特定的元素排序--对线性表中的元素进行整序分解--按要求将一个线性表分解成多个线性表合并--按要求将多个线性表合并成一个线性表复制--复制一个线性表逆转--逆转一个线性表线性表10线性表在顺序存储下的插入运算下图(a)为一个长度为8的线性表顺序存储在长度为10的存储空间中图(b)表示是在第2
7、个元素位置插入新元素87图(c)表示是在图(b)中的第9个元素位置又插入新元素14(a)长度为8的线性表(b)插入元素87后(c)又插入元素14后线性表11线性表插入运算的一般描述对于一个长度为n的线性表(a1,a2,…,ai,…,an)在线性表的第i个元素ai的位置插入一个新元素b,得到长度为n+1的线性表为(al',a2',…,aj',aj+1',…,an',an+1')则插入前后的两线性表中的元素满足如下关系:线性表12线性表插入算法的效率分析要在第i(1≤i≤n)个元素位置插入一个新元素:将从最后一个(即第n个)元素开始,直到第i个元素之间
8、的共n-i+1个元素,依次向后移动一个位置；移动结束后,第i个位置将被空出；将新元素插入到第i项;插入结束后，线性表长度就增加了1。插入运算在线性表的末尾进行时，则只要在表的末尾增加一个元素；在线性表的第1个位置插入一个新元素，则需要移动表中所有的元素；通常插入运算在第i(1≤i≤n)个位置进行,则原来第i个元素之后(包括第i个元素)的所有元素都必须移动；在平均情况下,要在线性表中插入一个新元素,需要移动表中一半的元素。在线性表顺序存储的情况下,要插入一个新元素,其效率是很低的；特别是在线性表比较大的情况下更为突出，这是因为数据元素的移动需消耗较多
9、的处理时间，算法的时间复杂度记为O（n）。线性表13线性表在顺序存储结构下的插入算法elseif(v.last>=maxlen-1)printf(''线性表已满！'');else{for(k=v.last;k>=i;k--)v.elem[k]=v.elem[k-1];v.elem[i-1]=x;v.last++;}}在第i个位置插入一个新元素x线性表#definemaxlen100structsqlisttp{intelem[maxlen];intlast;};sqlisttpv;voidinsert(sqlisttpv,inti,intx){
10、intk;if(i<1
11、
12、i>v.last+1)printf(''插入位置不合适！'');14线性表在顺序存储结构下的
