《数据结构与算法分析课件第4章讲述》由会员分享，可在线阅读，更多相关《数据结构与算法分析课件第4章讲述（51页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法分析数据结构与算法分析 A Practical Introduction to Data Structures and Algorithm Analysis 陈陈 星星 第第4 4章章 线性表、栈和队列线性表、栈和队列 数据结构：相互有关联的数据元素的集合。 反映 数据的值和数据的位置 逻辑结构：反映数据元素之间逻辑关系。 存储结构(物理结构)：数据的逻辑结构在计算机存储空间的存放形式 。 4.1 线性表 由称为元素(element)的数据项组成的一种有限且有序的序列。 记为： 术语：空表、长度、表头、表尾、有序线性表、无序线性表 p线性和非线性: 线性linear，指量与量之间
2、按比例、成直线的关系，在数学上可以 理解为一阶导数为常数的函数； 非线性non-linear则指不按比例、不成直线的关系，一阶导数不为 常数。 p 线性结构是一个数据元素的有序集合,它有四个基本特征 ： 集合中必存在唯一的一个第一个元素； 集合中必存在唯一的一个最后的元素； 除最后元素之外，其它数据元素均有唯一的后继； 除第一元素之外，其它数据元素均有唯一的前驱。 线性表线性表ADTADT 抽象数据类型是指数据结构作为一个软件组件的实现。 通过ADT掌握数据结构的实现和操作。 线性表ADT设计的思想： 1. 当前位置。 2. 一个栅栏和两个分离部分。 如： 注：当前位置的元素（当前元素）为栅栏
3、右边的第1个 元素，或右边部分的第1个元素。 线性表的C+抽象类声明 template class List public: virtual void clear() = 0; /回收元素的存储空间 virtual bool insert(const Elem /当前位置插入新元素 virtual bool append(const Elem /表尾插入新元素 virtual bool remove(Elem /删除当前元素 virtual void setStart() = 0; / 将栅栏置于表头前 virtual void setEnd() = 0; / 将栅栏置于表尾后 virtual
4、 void prev() = 0; / 将栅栏向前（左）移动一个元素 virtual void next() = 0; / 将栅栏向后（右）移动一个元素 virtual int leftLength() const = 0; /返回左边部分的元素个数 virtual int rightLength() const = 0; /返回左边部分的元素个数 virtual bool setPos(int pos) = 0; /返回栅栏在表中的位置 virtual bool getValue(Elem /返回当前元素的值 virtual void print() const = 0; /输出线性表中元素
5、序列 ； 线性表的线性表的ADTADT举例举例 1. 线性表: MyList.insert(99); 结果: 2. 线性表循环获得每个元素的值: for (MyList.setStart(); MyList.getValue(it); MyList.next() DoSomething(it); 3. 在线性表中查找元素值k，找到返回True，未找到返回False。 bool find(List for (L.setStart(); L.getValue(it); L.next() if (K = it) return true; / Found it return false; / Not
6、found 4.1.1 顺序表的实现 线性表的两种实现方法 顺序表(又称顺序存储结构的线性，array- based list, sequential list)和链表(又称链式存储结构的线性表，Linked list) 顺序存储结构（向量式的存储结构，顺序分配）的基本特点： (1) 线性表中所有元素所占的存储空间是连续的。 (2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放。 逻辑上相邻的两个元素在存储空间中是相邻的。利用元素存储的位 置关系反映元素之间的逻辑关系。 通常用一个一维数组来表示线性表的顺序存储空间。 可以通过简单计算得到任意元素的存储地址： ADR(ai) = ADR(
7、a1) + ( i-1)*k 其中，k为每一个元素占的字节数，i为元素在线性表中的序号。 思考: 顺序表中插入和删除一个元素的过程和时间代价? 顺序表的插入操作 时间代价(n) / 在当前位置（栅栏右边第1个元素处）插入一个新元素 template bool AList:insert(const Elem /存储空间已满 /从线性表尾到插入处，每个元素向右移动一个存储单元 for(int i=listSize; ifence; i-) listArrayi = listArrayi-1; listArrayfence = item; /插入新元素 listSize+; / Increment
8、list size return true; 讨论：在实际应用中，顺序表有何优点和缺点，适宜用于 何种情况，不适宜用于何种情况？ 优点缺 点 1. 结构简单 2. 运算方便 3. 存储空间利 用效率高 1.插入和删除需移动大量数据元素， 时间代价大。 容量不易扩充。 存储空间分配困难：（1）静态分配 ：存储空间利用效率低。（2）动态 分配：每次重新分配需移动大量数据 元素。 结论：只适合小线性表、长度和数据元素不变化的线性 表。 算法编程课堂练习 对一个长度为n顺序表（用一维数组V 表示顺序表的存储空间），要求将元素x和 它后一个单元的元素交换，可用的中间变 量为T。 写出相应的算法程序。 P
9、rocedure EXCHANE(V, n, x) IF (n next; rightcnt+; return true; 问题：当链表为空，没有元素可供head，tail和fence来指向， 当链表左边部分为空时，fence不能指向任何元素。 解决方法：增加表头结点。 算法编程练习算法编程练习 一个链表长度为n，头指针为head，用两个 同样大小的一维数组V(1:m)和Next(1:m)分别保 存该链表各结点的数据域值和指针域值。 请编程实现: 在链表中元素值为x的结点之前 插入一个新元素。新元素值为b，数组下标为p 。 提示：不但要考虑一般情况下操作，还要考虑特殊 情况下的操作。 Proc
10、edure Insert(V, next, x, b, p) V(p) = b / 如果链表为空 if( head = NULL) return ; / 在第一个结点前插入 if(V(head)=x) next(p)=head; head = p; return /寻找值为x结点的前一个结点, 该结点地址保存在q中 q = head while( (next(q)!=NULL) /没有找到x /将结点p插入到结点q之后 next(p) = next(q); next(q) = p Return 算法编程练习算法编程练习 一个链表长度为n，头指针为head，用两个 同样大小的一维数组V(1:m)
11、和Next(1:m)分别保 存该链表各结点的数据域值和指针域值。 请编程实现: 在链表中元素值为x的结点之后后 插入一个新元素。新元素值为b，数组下标为p 。 Procedure Insert(V, next, x, b, p) V(p) = b / 如果链表为空 if( head = NULL) return ; /寻找值为x结点, 该结点地址保存在q中 q = head; while( (next(q)!=NULL) if( (next(q) = NULL) /没 有找到x if( (next(q) = NULL) /将结点p插入到结点q之后 next(p) = next(q); next
12、(q) = p Return 链表的删除操作链表的删除操作 可利用空间表可利用空间表 链表插入和删除操作 取得空结点和回收删除的结点 对存储空间合理的存储分配和回收机制 语言编译器的效率不高 可利用空间表 (freelist) 插入一个新结点到链表前,首先从可利用空间表中取走 一个结点。 删除一个链表上的结点后，要将删除的结点放到可利 用空间表的首端。 4.1.4 4.1.4 元素的表示元素的表示 1. 顺序表和链表中的元素是存储数据元素的一 份拷贝(副本)还是存储指向数据元素的指针? 建议: 数据元素大而且重复多,存储数据元素指针. 2. 是否要求线性表中元素类型相同? 根据应用选择元素类型是固定还是不同. 3. 当线性表被删除或调用Clear函数(回收)时,如何处理表 中对象占用的内存? 注意: 如果表中元素是对象的指针,就可能删除指向对象的 指针,从而使对象占用的内存变成不可访问的(悬挂引 用). 4.1.5 4.1.5 双链表双链表 单链表只允许从一个结点访问它的后
