线性表,数组,链接表

《线性表,数组,链接表》由会员分享，可在线阅读，更多相关《线性表,数组,链接表（60页珍藏版）》请在金锄头文库上搜索。

1、第二章 数据结构（DS）l基本概念l线性表和数组l栈和队列l链接表l字符串l树l图l查找与排序DS基本概念l为什么研究DS？对象复杂设立于1968年。美国唐欧克努特教授计算机 程序设计技巧第一卷基本算法计算机专业基础课，是学习编译原理、操作系统 、数据库原理的基础DS基本概念l数据：信息的载体，计算机加工处理的对象l数值数据l非数值数据l数据元素组成数据的基本单位l数据项，域，字段 基本项 组合项DS基本概念l数据结构相互之间具有一种或多种特定关系的数据元素的集合lData_Structure=（D,R）逻辑结构：数据元素之间的相互关系，面向问题存储结构：逻辑结构在计算机中的实现，面向计算机运

2、算：在逻辑结构上定义一组相应的运算，在存储结构 上建立算法实现这些运算DS的抽象数据类型（ADT）描述l对象的抽象数据模型和一组相关操作l定义与实现分离，实现信息隐蔽lC中用类定义ADT逻辑结构l集合结构群聚集，无顺序，不重复用途：分类、查找l线性结构线性聚集，有序，一对一关系l树型结构l图/网结构树型结构l层次聚集，元素之间为一对多关系l用途树表查找：构建小型多级索引，优化查找过程，二叉排序 树，二叉平衡树， B、B-树堆：内、外排序，优先级队列前缀编码2012618342735图/网结构l群聚集，多对多，无序l无向、有向、加权l应用广泛：语言学、逻辑学、物理、化学、 电信工程、计算机科学以

3、及数学的其它分支 中。 存储结构l顺序存储逻辑上相邻则物理上相邻，存放于连续存储单元中 如数组l链接存储每个元素含指针域以存放其它元素的地址l索引存储包含索引表和子表的存储结构索引函数索引表子表首地址子表l散列存储理想的查找，不经过任何比较直接得到被查元素地址Loc(d)=H(d.key)运算l给出数据被使用的方式l常见运算建立DS清除DS插入元素删除元素排序检索更新判DS空或满求长度算法l定义精确地描述解决问题所用方法的一系列确切有穷的步骤l特性输入输出确定性有穷性有效性l描述 自然语言、框图、高级语言，本教材中的算法描述语言算法的性能标准l正确性达到功能要求l编程风格可用性：友好性、模块化

4、可读性：结构化、命名规则、文档l健壮性含数据检查、调用状态检查，出错处理及用户对话l效率算法消耗的资源算法的空间、时间复杂度分析算法举例编写函数 strcpychar *strcpy(char *strDest, const char *strSrc); assert(strDest!=NULL) /在函数的入口处，使用断言检查参数的合法性 char *address = strDest;while( (*strDest+ = * strSrc+) != 0 )/使用链式表达式NULL ; return address ; 算法的定量分析l算法的先验估计空间复杂度 l算法存储空间随问题规模n增

5、长的数量g（n）问题规模：实例的特性，如记录个数 空间单位：一个工作单元所占存储空间的大小l静态部分（程序代码、常量）和可变部分（变量、栈、动态申请） l例如，递归深度为n1，所需栈空间为4（n1）float rsum(float a ,const int n) if(n| ai-1，aiD, i=0,1,2, ，n-1n（n=0）个数据元素（a1， a2， an)的有限序列ln为表长，n0时为空表，有限个数la1为 a2的直接前驱结点， a2 为 a1的直接后继结点l元素之间为线性关系l广义表：元素也可为线性表，例如 （A，（B，C），D)矩阵线性表的存储结构l顺序存储逻辑上相邻则物理上相邻

6、同构线性表，可用数组存储顺序存储的线性表称为顺序表，向量l数组的特点数组为二元组（值，下标)的集合，给定下标直接存取元素 ，O（1）均匀性、连续性空间分配：静态，动态，最大空间一次分配好动态变化：在所分配的最大空间内，边界可移动数组的顺序分配一维l一维数组:向量，设d为每个元素的存储大小数组的顺序分配二维l二维数组:矩阵，一维数组的元素是一维数组若定义数组Anm，表示此数组有n行m列，nm 个元素0 1 2 j m-1 0 a00 a01 a02 a0j a0 m-11a10 a11 a12 a1j a1 m-12a20 a21 a22 a2j a2 m-1i ai0 ai1 ai2 aij

7、ai m-1n-1 an-1 ,0 an-1,1 an-1,2 an-1,j an-1,m-1数组的顺序分配二维l由 n个行向量与m个列向量组成l元素ajk(0j n-1,0 k m-1),处于第j个行向量和第k个列向量中行向量中前驱为ajk-1 ，后继为ajk+1列向量中前驱为aj-1k ，后继为aj+1kl行优先及列优先计算机存储空间是一维的，实现存储要将而维转 换为一维行优先：按下标由外至里顺序依次存放列优先：按下标由里至外顺序依次存放数组的顺序分配二维l地址计算公式设每个元素存储大小为1，即编址单位空间，则任 一元素ajk的地址为：数组的顺序分配三维l三维数组:一维数组的元素是矩阵若定

8、义数组Am1m2 m3 ， m1 m2m3个元素l由m1个页向量、 m2个行向量与m3个列向量组成，表 示此数组m1页，每页有n行m列l元素aijk(0i m1 -1,0j m2 -1,0 k m3 -1),处于第i个页向量、第j个行向量和第k个列向量中页向量、行向量、列向量中各有一个前驱一个后继（如果 存在）位置由下标3元组ijk唯一确定数组的顺序分配三维l地址计算公式设每个元素存储大小为1，即编址单位空间，则任 一元素aijk的地址为：数组的顺序分配n维ln维数组:一维数组的元素是n1维数组的广 义表若定义数组Am1m2 mn ， 个元素l由n维向量组成，属于n维线性空间l元素ai1i2i

9、n(0i1 m1 -1,0 i2 m2 -1,0 in mn -1),在每一维向量中各有一个前驱一个后继（如果存 在）位置由下标n元组i1i2 in唯一确定数组的顺序分配n维l地址计算公式设每个元素存储大小为1，即编址单位空间，则任 一元素ai1i2in的地址为：顺序表的操作定义l操作说明：参见MFC类Carrayl顺序表的类定义 template class SeqList public: SeqList(int MaxSize=defaultSize); seqList() delete data; int Length() const return last+1; int Find(Ty

10、pe /查找x在表中的位置 int Insert(Type /插入x在表中第i个位置处 int Remove(Type /删除xprivate: Type * data;/顺序表的存放数组 int MaxSize;/最大空间 int last;/当前已存元素的最后位置，1表示空 顺序表的算法描述l构造 template SeqList:SeqList(in sz) /构造函数，通过指定参数sz定义数组的长度 if(sz0) MaxSize = sz; last = -1;/顺序表长度，实际长度为 空 data = new TypeMaxSize;/创建顺序表数组 顺序表的算法描述l查找 tem

11、plate int SeqList:Find(Type while(ilast) return -1;/查找失败 else return i;/查找成功 顺序表的算法描述l插入 template int SeqList:Insert(Type/检查插入位置 及表容量 last+;/表长加1 for(int j=last; ji; j-) dataj = dataj-1;/依次后移 datai = x;/新元素加入 return 1;/返回成功标志1 顺序表的算法描述l删除 template int SeqList:Remove(Type/在表中查找x if(i-1) /x在表中存在 last-

12、;/表长减1 for(int j=i; jlink; k+;/沿链找第i1个结点 if(p=NULL first = newnode; else/插入在中间位置或链尾 newnode-link = p-link; p-link = newnode; return 1; /O（n）单链表删除算法删除第i个结点，i为0n1三种删除位置分析l删除表头结点： 修改头指针l删除中间结点或尾结点：修改中间结点链域l时间复杂度O（n），用于沿链找删除结点单链表删除算法int List:Remove(int i) /删除表中第i个元素，返回1删除成功，0不合理 ListNode *p = first, *q;

13、 int k = 0; while(p!=Null k+;/沿链找第i1个结点 if(p=NULL | p-link=NULL)/空链或链短，找不到第i1个或i结点 coutlink; else/删除中间结点和终端结点时，重新拉链 q = p-link; p-link = q-link; delete q;/释放被删除的空间 return 1;链表的蠕虫式查找思考题l将一个单链表的接序关系逆转循环链表l将单链表的最后一个结点的指针指向起始结 点l判断指针到达链尾的条件是p-link=first or p=last而不是p-link=NULL l可达性可从表中任一结点出发进行查找，更加灵活使用尾

14、指针更加方便，避免从头至尾搜索尾结点，可不设 头指针插入算法l设计链头与链尾的操作与单链表不同，其余类 似l在表的最前端插入新结点，需修改终端结点指 针如下： 当Last!=NULL时，表非空lNewNode-link=last-link;lLast-link=NewNode;当Last=NULL时，表为空lLast=NewNode;lNewNode-link=last/指向自己循环单链表的应用l用循环链表求解Josephus问题l实现多项式的存储和运算双向链表l单链表只能向一个方向查找，找前驱结点很 不方便，需从表头出发查找。l在单链表中，查找某结点的后继结点的执行 时间为O(1)，而查找其前驱结点的执行时间 为O(n)。l双向链表中，每一个结点除了数据域外，还 包含两个指针域，一个指针（llink）指向该 结点的前驱结点，另一个指针（rlink）指向 它的后继结点。带表头结点的双向循环链表l表头指针first指向表头结点，其rlink指向起始 结点，llink指向终端结点l起始结点的llink和终端结点的rlink指向表头结 点prior nextfirst(a) 空双向链表a0a1 an-1first(b) 非空的双向链表双向循环链表l假设p指向双循环链表中某一结点，有 P=P-llink-rlink=p-rli