资源描述：
《线性表(new).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第1章 数据结构1.1基本数据结构与算法1.2线性表1.3栈和队列1.4树和二叉树1.5查找1.6内部排序ABCDEFG姓名学号成绩班级李红976105995机97.610658651.2线性表1.线性表的定义1)定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。2)表示:L=(a1，a2，a3，…ai-1，ai，ai+1，an)其中:n为线性表长度(n=0称为空表)，表中相邻元素之间存在着顺序关系。a1：表头元素；an：表尾元素；ai-1称为ai的直接前驱；ai+1称为ai的直接后继。表头表尾1.2线
2、性表1.线性表的定义1)定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。2)表示:L=(a1，a2，a3，…ai-1，ai，ai+1，an)3)线性结构特点:(1)有且只有一个根结点a1，无前驱。(2)有且只有一个终端结点an，无后继。(3)其他结点有且只有一个直接前驱和一个直接后继。1.2线性表1.线性表的定义1)定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。2)表示:L=(a1，a2，a3，…ai-1，ai，ai+1，an)3)线性结构特点:4)线性表的
3、分类(1)简单线性表：数据元素是简单项(数字、字母、季节名等)。如:(12,34,4,67,8)(2)复杂线性表：数据元素由若干个数据项组成，此时数据元素称为记录或结点,如学生成绩表.学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….1.顺序表基本概念1.2.2线性表的顺序存储结构1)顺序存储结构：用一组地址连续的存储空间依次存放线性表的各元素。顺序表：采用顺序存储结构的线性表称为顺序表(一维数组)
4、表中的所有元素所占存储空间连续表中各元素在存储空间中按逻辑顺序存放顺序存储结构特点1.2线性表1.顺序表基本概念4.2.2线性表的顺序存储结构1)顺序存储结构：2)第i个元素地址4.2线性表其中:m：每个元素占m个存储单元Loc(a1)第一个元素地址(基址)对数组而言an－1……..ai……..a1a0bb+mb+i*mb+n*m存储地址存储状态空闲数据元素在线性表中的位序12ni从存取方式看,线性表的顺序存储结构是可以随机存储的存储结构.1.顺序表基本概念1.2.2线性表的顺序存储结构1)顺序存储结构：2)第i个元素地址1.2线性表2.顺序
5、表的基本运算存取:访问线性表的第i个元素，使用或改变数据元素的值。查找:在线性表中查找满足某种条件的数据元素。插入:在线性表的第i个元素之前，插入一个同类型的元素。(***)删除:删除线性表中第i个元素。(***)求表长:求出线性表中元素的个数。置空表:建立一个空表。清除表:将已有线性表变为空表，即删除表中所有元素。1.顺序表基本概念1.2.2线性表的顺序存储结构1)顺序存储结构：2)第i个元素地址1.2线性表2.顺序表的基本运算——插入和删除1)顺序表的插入运算:在线性表的第i个元素之前插入一个新的元素，先移动，后插入。ai-1…..a2a
6、1an…ai+1aixai-1…..a2a1ai…anan……ai+1aiai先移动后插入x步骤：(1)将ai~an顺序向后移动,为新元素让出位置(2)将x置入”空出”的第i个位置举例：(在第4个和第5个元素之间插入元素91)674126214891601234567867412621489160123456786741262148916012345678212191插入程序举例(在8个数中任意位置插入一个数)：#defineN8main(){inta[N+1]={12,34,45,6,78,9,10,91},i,j,x;printf(“in
7、putthelocationtobeinserted:”);scanf(“%d,%d”,&i,&x);a[i-1]=x;for(j=0;j<=N;j++)printf(“%d,”,a[j]);}for(j=i-1;j<=N-1;j++)a[j+1]=a[j];for(j=N-1;j>=i-1;j--)a[j+1]=a[j];在第i个位置上作插入x,则需将第i个至第n个元素移动，即共需移动(n-i+1)个元素。插入运算时间性能分析：插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数(期望值)：pi：在第i个
8、位置上作插入的概率。等差数列求和公式:((首项+末项)×项数)/2(n-i+1)线性表(a1,a2,a3)平局移动元素个数:(¼)*(3+2+1+0)=1.5<例>
