《第2章线性表A》由会员分享，可在线阅读，更多相关《第2章线性表A（33页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论第2章 线性表第3章 栈和队列 第4章 串第5章 数组和广义表第6章 树和二叉树 第7章 图第9章 查找第10章 排序,目 录,数据结构课程的起点：,什么是线性结构？,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , , an）,简言之，线性结构反映结点间的逻辑关系是 的。,特点 只有一个首结点和尾结点；特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一 (1:1),第2章
2、 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 应用举例,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,（ A, B, C, D, , Z）,例2 分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析： 数据元素都是同类型（字母）， 元素间关系是线性的。,注意：同一线性表
3、中的元素必定具有相同特性 ！,例1 分析26 个英文字母组成的英文表是什么结构。,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示2.2.2 顺序表的实现2.2.3 顺序表的运算效率分析,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻
4、,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即： Vn的有效范围是从 V0Vn-1,1. 逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）,对上述公式的解释如图所示,线性表顺序存储特点：,地址 内容 元素在表中的位序,1,i,2,n,空闲区
5、,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,LOC ( ai ) = LOC( a1 ) + L *（i -1）,线性表的顺序存储结构示意图,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是多少？,113,但此题要注意下标起点略有不同：LOC( M3 ) = 98 + 5 (4-1) =113,解：已知地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,例1,char V30;void build() /*字母线性表
6、的生成，即建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; ,核心语句：法1 Vi= Vi-1+1;法2 Vi=a+i;法3 Vi= 97 +i;,例2,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,void main(void) /*主函数，字母线性表的生成和输出*/ n=26; /* n是表长，是数据元素的个数，而不是V的 实际下标*/build( );display( );,void display( ) /*字母线性表的显示，即读表操作*/ int i;for( i=0; i
7、=i; j-)aj+1=a j ; a i =x; n+;,/ 元素后移一个位置,/ 插入x,/ 表长加1,核心语句：,2)插入,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,实现步骤：将第i+1 至第n 位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i 是否合法?应当有1in 或 i=1, n,删除线性表的第i个位置上的元素,for ( j=i+1; j=n; j+ )aj-1=aj; n-;,/ 元素前移一个位置,/ 表长减1,核心语句：,3)删除,删除顺序表中某个指定的元素的示意图如下：,顺序表插入和删除的完整程序请同学们自编。,线性表的定义（见教材P19
8、）,ADT List 数据对象：D=ai | aiElemSet, i=1,2,n,n0数据关系：R1= | ai 1, ai D, i=2,n基本操作：,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除, ADT List,线性表的基本操作如何表示？ （见教材P19）,InitList( &L ); /建空表，初始化DestoryList( &L ); /撤销表，释放内存int LengthList( L ); /求表中元素个数，即表长POSITION LocateElem (L,ElemType e，compare() );PriorEle
9、m( L, cur_e, &pre_e ); /求当前元素e的前驱NextElem( L, cur_e, &next_e ); /求当前元素e的后继ListInsertBefore(&L, i, e ); /把e插入到第i个元素之前ListDelete( &L, i,&e ); /删除第i个元素并“看”此元素ListTraverse( L, Visit() ); / “看”表中全部元素（遍历）,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除,顺序表操作的典型例子,教材例2-1：求两个线性表的“并”，即：LA U LB = ?,算法至少有两种：
10、 LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入LA； 若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。,以上以静态的顺序表来存储数据元素，存在利弊。,动态数组如何实现（见教材P22和P24）,#define List_Init_Size 100 /初始空间#define List_Increment 10 /分配增量 typedef struct ElemType *elem; /存储空间基址int length; /当前长度 int listsize; /当前分配的存储容量（以sizeof(ElemType) /为单位）Sqlist;,P23的ma
11、lloc()函数与P24的realloc()函数有什么不同？,动态数组简介,先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。,#define LIST_INIT_SIZE 100 /存储空间的初始分配量#define LISTINCREMENT 10/存储空间的分配增量Typedef struct ElemType *elem; /表基址(用指针*elem表示） int length; /表长度（表中有多少个元素） int listsize; /当前分配的表尺寸（字节单位）SqList;,注：三个分量可简写为：(L.elem L.length
12、 L.listsize) (L-elem L-length L-listsize),存储结构描述如下：,sizeof(x)算符的意思是：计算变量x的长度(字节数),malloc (m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。,Status InitList_Sq( SqList &L ) /创建一个空线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType); If(!L.elem) exit(OVERFLOW); /分配失败，结束程序 L.length=0; /暂无元素放入，空表 L.listsize=LIST_INIT_SIZE; /表尺寸=初始分配量 Return OK; /InitList_Sq,动态创建一个空顺序表的算法：,realloc (*p, newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。,动态顺序表的插入算法Status ListInsert_Sq(SqList &L, int i, ElemType e) /在顺序线性表中第i个位置之前插入新的元素e,if( i L.length+1) return ERROR; / 检验i 值的合法性,
