《数据结构域算法设计-第二章 线性表_1 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第二章 线性表_1 课件（54页珍藏版）》请在金锄头文库上搜索。
1、第一章回顾1、程序设计和算法、数据结构的 关系 2、数据结构讨论的内容 3、数据结构的定义 4、抽象数据类型的概念 5、算法及其度量1练习设 n 为正整数。试确定下列各程序段中前置以 记号 的语句的频度 i=1; k=0;while ( i=(y+1)*(y+1) y+; 4 x=91; y=100;while (y0 ) if (x100 ) x -= 10; y- -; else x+;11005数据结构部分的起点：数据结构部分的起点：什么是 线性结构？6第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组 第6章 树和二叉树 第9章 查找 第10章 排序数据库部分目
2、录7线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 可表示为：（a1 , a2 , , an） 简言之，线性结构反映结点间的逻辑关系是 的。特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个 直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是-线性表线性表一对一 (1:1)8第第2 2章章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现
3、线性表的链式表示和实现2.4 2.4 应用举例应用举例9（a1, a2, ai-1，ai, ai1 ，, an）2.12.1线性表的定义：线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的 序号，表示元素 在表中的位置n为元素总 个数，即表 长。n0n0空表线性终点10（ A, B, C, D, , Z）学号姓名性别年龄班级012006013112柳华兵男19电子信息工程200604班012006013211陈 是男19电子信息工程200605班012006013309邹礼见男19电子信息工程200606班012006013423刘述博
4、男19电子信息工程200607班012006013526郑 欢男19电子信息工程200608班 ： ：例2 分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析： 数据元素都是同类型（字母）， 元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！例1 分析26 个英文字母组成的英文表是什么结构。11“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：12线性表的抽象数据类型的定义ADT Li
5、st 数据对象：Dai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1,aiD, i=2,.,n 基本操作：结构初始化销毁结构引用型操作加工型操作 ADT List13线性表的抽象数据类型的定义 ADT List 数据对象：Dai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1,aiD, i=2,.,n 基本操作：结构初始化InitList( 2依值在线性表 LA 中进行查询；LocateElem(LA,e,equal( ) 3若不存在，则将它插入到 LA 中。ListInsert( LA, n+1,e ) 重复上述三
6、步直至 LB 遍历止。 19对应的线性表基本操作： 1. GetElem(Lb,i,e);2. LocateElem( LA, e, equal() ); 3. ListInsert( LA, n+1,e )void union(List / 求得线性表 LA 的长度Lb_len = ListLength(LB);/ 求得线性表 LB 的长度 for(i=1;i=i; j- -) aj+1=a j ; a i =x; n+;/ 元素后移一个位置 / 插入x / 表长加1 核 心 语 句 ：2)插入注意：注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当符合条件： 1in+1 或 i=
7、1, n+131在线性表的第i个位置前插入一个元素的示意图如下：12 13 21 24 28 30 42 7712 13 21 2425 28 30 42 7712345678123456789插入252532实现步骤： 将第i+1 至第n 位的 元素向前移动一个位置； 表长减1。删除线性表的第i个位置上的元素for ( j=i+1; jelem=(ElemType*)malloc (LIST_MAX_LENGTH *sizeof(ElemType); /分配空 间if (L-elem=NULL) return ERROR; /若分 配空间不成功，返回ERRORL-length=0; /将当前
8、线性表长度置0return OK; /成功返回OK / sizeof(x)算符的意思是：计算变量x的长度(字节 数)malloc(m)函数的意思是：新开一片大小为m字节的 连续空间，并把该区首址作为函数值。392. 销毁线性表L void DestroyList(SQ_LIST /释放线 性表占据的所有存储空间 403. 清空线性表L void ClearList(SQ_LIST /将线性表的长度置 为0 414. 求线性表L的长度 int GetLength(SQ_LIST L) return (L.length); 425. 判断线性表L是否为空 int IsEmpty(SQ_LIST L
9、) if (L.length=0) return TRUE; else return FALSE; 436. 获取线性表L中的某个数据元素的内容 int GetElem(SQ_LIST L,int i, ElemType /判 断i值是否合理，若不合理，返回ERRORe=L.elemi-1; /数组中第i-1的单元存 储着线性表中第i个数据元素的内容return OK; 447. 在线性表L中检索值为e的数据元素 int LocateELem(SQ_LIST L, int(*compare)(ElemType,ElemType)/* 操作结果：返回L中第1个与e满足关系compare()的数据
10、 元素的位序。若这样的数据元素不存在，则返回值为0。 */ElemType *p;int i=1; /* i的初值为第1个元素的位序 */p=L.elem; /* p的初值为第1个元素的存储位置 */while(i 或= b，分别返回0或1 */if(a=b)return 1;elsereturn 0;LocateElem(L,j,equal);458. 将线性表L中第i个数据元素删除 int ListDelete(SQ_LIST /检测线性 表是否为空if (iL-length) return ERROR; /检查i 值是否合理e=L-elemi-1; /将欲删除的数据元素内 容保留在e所指
11、示的存储单元中for (j=i;jlength-1;j+) /将线性表第 i+1个元素之后的所有元素向前移动L-elemj-1=L-elemj;L-length-; return OK; 469. 在线性表L中第i个数据元素之前插入数据元素e int ListInsert(SQ_LIST if (iL-length+1) return ERROR; /i值是 否合理for (j=L-length-1;j=i-1;i+) /将线性表第i个元 素之后的所有元素向后移动L.-elemj+1=L-elemj;L-elemi-1=e; /将新元素的内容放入线性表的第i 个位置L-length+; ret
12、urn OK; 47进一步讨论：顺序表的存储结构是一维数组，如果插入的 元素个数超过数组定义的长度怎么办？采用动态分配的一维数组48动态数组简介动态数组简介先为顺序表空间设定一个初始分配量，一旦因 插入元素而空间不足时，可为顺序表增加一个约定长 度的空间增量。 #define LIST_INIT_SIZE 100 /存储空间的初始分配量 #define LISTINCREMENT 10/存储空间的分配增量 Typedef structElemType *elem; /表基址(用指针*elem表示）int length; /表长度（表中有多少个元素）int listsize; /当前分配的表尺寸
13、（字节单位） SqList;注：三个分量可简写为：L.elem L.length L.listsize存储结构描述如下（见教材P22）：49Status InitList_Sq( SqList if(!L.elem) exit(OVERFLOW); /分配失败，结束程序L.length=0; /暂无元素放入，空表L.listsize=LIST_INIT_SIZE; /表尺寸=初始分配量Return OK; /InitList_Sq动态创建一个空顺序表的算法：50动态顺序表的插入算法 Status ListInsert_Sq(SqList / 检验i 值的合法性if ( L.length L.l
14、istsize ) /若表长超过表尺寸则要增加尺寸 newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + + LISTLISTINCREMENTINCREMENT )* sizeof ( ElemType ) );if (newbase=NULL )exit( OVERFLOW ) ; /分配失败则退出并报错L.elem = newbase ; /重置新基址L.listsize = L.listsize + + LISTINCREMENT LISTINCREMENT ; /增加表尺寸realloc (*p, newsize)函数的意思是：新开一片大小为newsize 的连续空间，并把以*p为首址的原空间数据都拷贝进去。51q = / q为插入位置。这是没有头结点的情况for ( p = p=q ; -p ) *(p+1) = *p ;/插入位置及之后的元素统统后移, p为元素位置*q= e ; /插入e+L.length ; /增加1个数据元素，则表长+1return OK ; /ListInsert_
