课件第二章线性表.pptx

第二章 线性表 ;第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序;数据结构课程的起点;线性结构;线性结构;2、线性结构的逻辑类型;第2章 线性表;（a1, a2, … ai-1，ai, ai＋1 ，…, an） ; （ A, B, C, D, …… , Z）;例2 分析学生情况登记表是什么结构。;1、“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。;线性表的物理结构;物理结构与逻辑结构区别;2.2 线性表的顺序表示和实现;2.2.1 顺序表的表示;2.2.1 顺序表的表示;线性表顺序存储特点;设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）;a1;设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的4个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？;例2 顺序表的操作;2.2.2 顺序表的实现（或操作）;2)插入 在线性表的第i个位置前插入一个元素;for (j=n; j=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++;;在线性表的第i个位置前插入一个元素的示意图如下：;实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当有1≤i≤n 或 i=[1, n];for ( j=i+1; j=n; j++ ) a[j-1]=a[j]; n--;;1;2.2.3 顺序表的运算效率分析;2.2.3 顺序表的运算效率分析;推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。 若在首结点前插入，需要移动的元素最多，后移n次； 若在a1后面插入，要后移n-1个元素，后移次数为n-1; …… 若在an-1后面插入，要后移1个元素； 若在尾结点an之后插入，则后移0个元素； 所有可能的元素移动次数合计： 0+1+‥+n = n(n+1)/2;;;课堂讨论：;1、抽象数据类型定义;线性表的基本操作如何表示？ （见教材P19）;顺序表???作的典型例子;2、动态数组;SqList L; 三个分量可写为： L.elem， L.length， L.listsize 动态顺序表的各项运算： ;sizeof(x)算符的意思是：计算变量x的长度(字节数);; q = L.elem[i-1] ; // q为插入位置指针 for ( p = L.elem[L.length-1] ; p=q ; --p ) *(p+1) = *p ; //插入位置及之后的元素统统后移, p为元素位置 *q= e ; //插入e ++L.length ; //增加1个数据元素，则表长+1 return OK ; } //ListInsert_Sq ;将数组中从第i个元素到最后一个元素整体后移一个位置另一种代码表示： for (int k=L.length-1; k=i-1;k--) L.elem[k+1]=L.elem[k];;Status ListDelete_Sq(SqList L, int i, ElemType e) { //在顺序表L中删除第 i 个元素，用 e 返回其值;链式存储结构;第2章 线性表;2.3 线性表的链式表示和实现;1、链式存储结构特点 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。;让每个存储结点都包含两部分：数据域和指针域;例：请画出26 个英文字母表的链式存储结构。 解：该字母表的逻辑结构为：（ a, b, … ,y, z） 该字母表在内存中链式存放的样式举例如下：;链表存放示意图如下： ;1）结点：数据元素的存储映像。由数据域和指针域两部分组成； 2）链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。;2、链式存储有关的术语;;3、头指针、头结点和首元结点的区别;讨论1. 在链表中设置头结