资源描述：
《线性表及其顺序存储结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章 线性表及其顺序存储结构简单就是美线性表是最简单、最常用的一种数据结构数据结构课程的内容概览排序运算查找运算修改运算删除运算运算的实现依赖于其存储结构插入运算运算散列结构索引结构链式结构存储结构不唯一顺序结构存储（物理）结构非线性结构【树、图】逻辑结构唯一线性结构【线性表、栈、队列、串、数组】逻辑结构数据结构什么是线性表(LinearList)●n维向量(x1，x2，…，xn)是一个长度为n的线性表●英文小写字母表(a，b，c，…，z)是一个长度为26的线性表●一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表●矩阵是一个比较复杂的线性表
2、30072001082000600094A＝线性表由一组数据元素组成，数据元素的含义很广泛，在不同的情况下，可以有不同的含义。复杂的线性表学生情况登记表学号姓名性别年龄成绩970156张小明男2086970157李小青女1983970158赵 凯男1970970159李启明男2191970160刘 华女1878970161曾小波女1990970162张 军男1880970163王 伟男2065970164胡 涛男1995970165周 敏女2087970166杨雪辉男2289970167吕永华男1861970168梅 玲女1793970169刘 健男
3、20752.1线性表基本概念线性表的定义：线性表（linearlist）是最简单、最常用的数据结构，是由n（n≥0）个元素组成的一个有限序列。如果用a表示元素，n个元素的线性表可以表示为：{a1,a2,……,a[i-1],a[i],a[i+1],……,an}数据元素根结点终端结点下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长a[i]的前件a[i]的后件注意：线形表也可以是一个空表2.1线性表基本概念2非空线性表特征：有且只有一个根结点，它没有前件；有且只有一个终端结点，它没有后件；除两端外，其他结点均有且只有一个前件和后件线性表中结点
4、的个数n称为线性表的长度，但n=0时即为空表很显然，线性表是一种线性数据结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。同时也应该注意到，线性表中的元素间的逻辑关系是一对一的。线性表的顺序存储结构在计算机中存放线性表，最简单的方法是顺序存储。顺序存储的两个基本特点：线性表中的所有元素所占的存储空间是连续的；线性表中的各元素在存储空间中是按逻辑顺序依次存放的。ADR(ai)＝ADR(a1)+(i-1)k存储地址ADR(a1)ADR(a1)+kADR(a1)+(i-1)kADR(a1)+(n-1)k…占k个字节占k
5、个字节占k个字节占k个字节a1a2…ai…an…在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定前提为线性表中各数据元素所占的存储空间（字节数）相等根据线性表顺序存储的特点，在程序设计语言中，通常定义一个一维数组表示线性表的顺序存储空间。在用一维数组存放线性表时，该一维数组的长度通常要定义得比现行表的实际长度大一些，以便对线性表进行各种运算。在一般情况下，如果线性表的长度在处理过程中是动态变化的，则在开辟线性表的存储空间时要考虑到线性表的动态变化过程中可能达到的最大长度。建立一个容量为m的空线性
6、表的顺序存储空间（即初始化线性表的顺序存储空间）的C语言描述为：#include“stdlib.h”voidinitsl(ET*v,intm,intn){v=(ET*)malloc(m*sizeof(ET));n=0;return;}要释放线性表的顺序存储空间，可以用free(v)实现线性表的主要运算在线性表中的指定位置加入一个新的元素（线性表的插入）在线性表中删除指定元素（线性表的删除）在线性表中查找某个特定的元素（线性表的查找）对线性表的元素进行排序按某要求把一个线性表分解成多个线性表（线性表的分解）按某要求将多个线性表合并成一个线性表（线性表的
7、合并）复制一个线性表逆转一个线性表4731243563562.1.3线性表在顺序存储下的插入运算473124356356182987V(1:10)长度为8的线性表14V(1:10)插入元素87后变为长度为9的线性表473124356356188729V(1:10)再插入元素14后变为长度为10的线性表4714312435635618872912345678910471887142.1线性表的基本概念一般来说，设长度为n的线性表为：(a1,a2,…,ai,…,an)在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n+1的线性表为：(a’1
8、,a’2,…,a’j,a’j+1,…a’n,a’n+1)则插入前后的两线性表中的元素满足如下关系：a’j=a
