第2章(二)(2[1].2 线性表及其顺序存储结构)ppt课件.ppt

《第2章(二)(2[1].2 线性表及其顺序存储结构)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.2线性表及其顺序存储结构2.2.1线性表及其运算2.2.2栈及其应用2.2.3队列及其应用1第2章基本数据结构及其运算2.2.1线性表及其运算1.什么是线性表(LinearList)n维向量(x1，x2，…，xn)是一个长度为n的线性表英文小写字母表(a，b，c，…，z)是一个长度为26的线性表一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表矩阵是一个比较复杂的线性表2第2章基本数据结构及其运算学生情况登记表是一个复杂的线性表由若干数据项组成的数据元素称为记录(record)由多个记录构成的线性表又称为文件(file)3第2章基本数据结构及其运算线性表是由n(n

2、≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为(a1，a2，…，ai，…，an)其中ai(i＝1，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。4第2章基本数据结构及其运算非空线性表结构特征：(1)有且只有一个根结点a1，它无前件；(2)有且只有一个终端结点an，它无后件；(3)除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。5第2章基本数据

3、结构及其运算2.线性表的顺序存储结构线性表的顺序存储结构基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表中第i个元素ai在计算机存储空间中的存储地址为ADR(ai)＝ADR(a1)＋(i－1)k6第2章基本数据结构及其运算长度为n的线性表(a1，a2，…，ai，…，an)顺序存储结构7第2章基本数据结构及其运算整型一维数组存放长度为8的线性表(29,18,56,63,35,24,31,47)8第2章基本数据结构及其运算建立空线性表的顺序存储空间（即初始化线性表的顺序存储空间）#include"stdl

4、ib.h"voidinitsl(v，m，n)ET*v；intm，*n；{v＝malloc(m*sizeof(ET))；*n＝0；return；}释放线性表的顺序存储空间free(v)；9第2章基本数据结构及其运算线性表顺序存储结构下的主要运算：(1)在线性表的指定位置处加入一个新的元素（即线性表的插入）；(2)在线性表中删除指定的元素（即线性表的删除）；(3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）；(4)对线性表中的元素进行整序（即线性表的排序）；(5)按要求将一个线性表分解成多个线性表（即线性表的分解）；(6)按要求将多个线性表合并成一个线性表（即线性表

5、的合并）；(7)复制一个线性表（即线性表的复制）；(8)逆转一个线性表（即线性表的逆转）等。10第2章基本数据结构及其运算3.线性表在顺序存储下的插入运算11第2章基本数据结构及其运算12第2章基本数据结构及其运算线性表在顺序存储下的插入算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。输出：插入后的线性表存储空间V(1：m)及线性表的长度n。PROCEDUREINSL(V，m，n，i，b)1.IF(n＝m)THEN{OVERFLOW；RETURN}2.IF(i＞n)THENi＝n＋13.IF(i＜

6、1)THENi＝14.FORj＝nTOiBY－1DOV(j＋1)＝V(j)5.V(i)＝b6.n＝n＋17.RETURN13第2章基本数据结构及其运算voidinsl(v，m，n，i，b)ETv[]，b；intm，*n，i；{if(*n＝＝m){printf("overflow")；return；}if(i＞*n－1)i＝*n＋1；if(i＜1)i＝1；for(j＝*n；j＜＝i；j――)v[j]＝v[j－1]；v[i－1]＝b；*n＝*n＋1；return；}14第2章基本数据结构及其运算4.线性表在顺序存储下的删除运算15第2章基本数据结构及其运算16第2章基本数据

7、结构及其运算线性表在顺序存储下的删除算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；删除的位置i（表示删除第i个元素）。输出：删除后的线性表存储空间V(1：m)及线性表的长度n。PROCEDUREDESL(V，m，n，i)1.IF(n＝0)THEN{UNDERFLOW；RETURN}2.IF(i＜1)or(i＞n)THEN{“Notthiselementinthelist”；RETURN}3.FORj＝iTOn－1DOV(j)＝V(j＋1)4.n＝n－15.RETURN17第2章基本数据结构及其运