数据结构第02章-线性表课件.ppt

1、数据结构（数据结构（C+版）版）n 第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计第2章 线性表 2.1 线性表的概念 2.2 顺序表类 2.3 单链表类 2.4 双向链表类数据结构（C+版）叶核亚2.1 线性表的概念 2.1.1 线性表的抽象数据类型 2.1.2 线性表的存储结构数据结构（C+版）叶核亚2.1.1 线性表的抽象数据类型1.线性表的数据元素线性表是由n（n0）个相同类型的数据元素a1，a2，an组成的有限序列，记作：LinearList=a1，a2，an其中，n

2、表示线性表的元素个数，称为线性表的长度。若n=0，则称为空表。若n0，对于线性表中第i个数据元素ai，有且仅有一个直接前驱数据元素ai-1和一个直接后继数据元素ai+1，而a1没有前驱数据元素，an没有后继数据元素。数据结构（C+版）叶核亚线性表的基本操作求长度：求线性表的数据元素个数。访问：对线性表中指定位置的数据元素进行存取、替换等操作。插入：在线性表指定位置上，插入一个新的数据元素，插入后仍为一个线性表。删除：删除线性表指定位置的数据元素，同时保证更改后的线性表仍然具有线性表的连续性。复制：重新复制一个线性表。合并：将两个或两个以上的线性表合并起来，形成一个新的线性表。查找：在线性表中查

3、找满足某种条件的数据元素。排序：对线性表中的数据元素按关键字值，以递增或递减的次序进行排列。遍历：按次序访问线性表中的所有数据元素，并且每个数据元素恰好访问一次。数据结构（C+版）叶核亚2.1.2 线性表的存储结构线性表的顺序存储结构线性表的链式存储结构数据结构（C+版）叶核亚1.线性表的顺序存储结构线性表的顺序存储结构是用一组连续的存储单元顺序存放线性表的数据元素，数据元素在内存的物理存储次序与它们在线性表中的逻辑次序是一致的，即数据元素ai与其前驱数据元素ai-1及后继数据元素ai+1的位置相邻。数据结构（C+版）叶核亚图2-1 线性表的顺序存储结构 数据结构（C+版）叶核亚2.线性表的链

4、式存储结构线性表的链式存储结构是把线性表的数据元素存放在结点中。结点（node）由数据元素域和一个或若干个指针域组成。指针是用来指向其他结点地址的，这样，线性表数据元素之间的逻辑次序就由结点间的指针来实现。用链式存储结构实现的线性表称作链表链表。数据结构（C+版）叶核亚2.2 顺序表类2.2.1 顺序表类声明2.2.2 顺序表类操作2.2.3 顺序表类操作的效率分析数据结构（C+版）叶核亚2.2.1 顺序表类声明class SeqList /顺序表类 private:int*table;/指向数组的指针 int size;/顺序表的数组容量 int len;/顺序表的实际长度 public:S

5、eqList(int n=0);/构造函数 SeqList(void);/析构函数 bool isEmpty()const;/判断顺序表是否为空 bool isFull()const;/判断顺序表是否已满 int length()const;/返回顺序表的实际长度 int get(int i)const;/返回第i个数据元素值 bool set(int i,int k);/设置第i个数据元素值为k bool insert(int i,int k);/插入k值作为第i个数据元素 bool insert(int k);/将k值添加到顺序表最后,函数重载 int search(int k);/查找，

6、返回k值首次出现的位置 bool remove(int k);/删除k值首次出现的数据元素;数据结构（C+版）叶核亚2.2.2 顺序表类操作1.顺序表的初始化使用构造方法创建顺序表对象，为顺序表分配存储空间，设置顺序表为空状态。算法如下：SeqList:SeqList(int n)/构造函数,初始化顺序表 table=new intn;/为顺序表分配n个存储单元 size=n;len=0;/此时顺序表实际长度为02.撤销顺序表对象当一个顺序表对象被撤销时，使用析构方法释放该对象占用的内存空间。算法如下：SeqList:SeqList(void)/析构函数，撤销顺序表对象 delete tabl

7、e;数据结构（C+版）叶核亚图2-2 顺序表中插入数据元素 数据结构（C+版）叶核亚图2-3 删除顺序表中的数据元素 数据结构（C+版）叶核亚2.2.3 顺序表类操作的效率分析在顺序表中插入一个数据元素的平均移动次数为时间复杂度为O(n)。niniinnnninnpin0022)1(11)(11)(数据结构（C+版）叶核亚例2-1 以顺序表求解约瑟夫环问题约瑟夫环（Josephus）问题：古代某法官要判决n个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第s个人开始数起，每数到第d个犯人，就拉出来处决，然后再数d个，数到的人再处决直到剩下的最后一个可赦免。数据结构（C+版）叶核亚图2-

8、4 约瑟夫环问题执行过程 数据结构（C+版）叶核亚例2-1 以顺序表求解约瑟夫环问题#include SeqList.h /顺序表类void display(int n,int s,int d)SeqList ring1(n);/初始化顺序表ring1 ring1.create(n);/顺序表ring1中添加n个自然数 cout1)/n-1个人依次出环 j=0;while(jnext=q；rear=q；数据结构（C+版）叶核亚2单链表的操作（1）建立单链表Onelink:Onelink(int n)/以n个自然数建立一条单链表 head=NULL;/n=0时，构造空链表 if(n0)/构造非空

9、链表 int i=1;OnelinkNode*rear,*q;head=new OnelinkNode(i+);rear=head;while(inext=q;/q结点链入rear结点之后 rear=q;/rear指向新的链尾结点数据结构（C+版）叶核亚例2-2 单向链表逆转。front=NULL数据结构（C+版）叶核亚例2-2 单向链表逆转。#include Onelink.h /单链表类void reverse(Onelink&h1)/将单链表h1逆转，引用类型参数 OnelinkNode*p=h1.head,*q,*front=NULL;while(p!=NULL)q=p-next;/q

10、是p的后继结点 p-next=front;/使p-next指向p结点的前驱front front=p;p=q;h1.head=front;/改变单链表h1的头指针void main(void)数据结构（C+版）叶核亚（8）插入结点图2-9 单链表插入结点 数据结构（C+版）叶核亚（8）插入结点 空表插入head=new OnelinkNode(1)；头插入q=new OnelinkNode(2)；q-next=head；head=q；尾插入q=new OnelinkNode(3)；q-next=NULL；P-next=q；中间插入q=new OnelinkNode(4)；q-next=p-ne

11、xt；P-next=q；数据结构（C+版）叶核亚（9）删除结点 图2-10 单链表删除结点 数据结构（C+版）叶核亚（9）删除结点 删除单结点链表，只要使链表的引用head为空即可。head=NULL;删除链表第1个结点，只要将head指向链表第1个结点的后继结点即可。head=head-next;删除链表中间（尾）结点，设p指向单向链表中的某一结点，删除p的后继结点的语句是：p-next=(p-next)-next；数据结构（C+版）叶核亚2.3.4 两种存储结构性能的比较（1）直接访问元素的性能（2）存储空间的利用（3）存储密度（4）插入和删除操作（5）查找和排序数据结构（C+版）叶核亚2

12、.3.5 单向循环链表类1.单向循环链表的概念数据结构（C+版）叶核亚2.单向循环链表的声明与实现#include#include OnelinkNode.h /单链表的结点类class Onering /单向循环链表类 public:OnelinkNode*head;/头指针 Onering(int n=0);/构造函数 Onering();/析构函数 bool isEmpty()const /判断单向循环链表是否为空 return head=NULL;bool remove(OnelinkNode*p);/删除p的后继结点 void output();/输出单向循环链表的各个结点值;数据结

13、构（C+版）叶核亚【例2-3】以单向循环链表求解约瑟夫环问题。图2-12 以单向循环链表表示的约瑟夫环问题执行过程数据结构（C+版）叶核亚【例2-3】以单向循环链表求解约瑟夫环问题。#include Onering.h /单向循环链表类void display(Onering&ring,int s,int d)/解约瑟夫环 int j=0;OnelinkNode*p=ring.head;while(jnext;while(p-next!=p)/多于一个结点时循环 j=1;while(jprior)-next=p(p-next)-prior=p数据结构（C+版）叶核亚2.4.2 双向链表的结点类

14、class TwolinkNode /双向链表的结点类 public:int data;/数据元素域 TwolinkNode*prior;/指针域，指向前驱结点的指针 TwolinkNode*next;/指针域，指向后继结点的指针 TwolinkNode(int k=0,TwolinkNode*p=NULL,TwolinkNode*q=NULL)/构造函数 data=k;prior=p;next=q;TwolinkNode()/析构函数 ;数据结构（C+版）叶核亚2.4.3 双向链表类的设计与实现1.双向链表类的声明#include TwolinkNode.h /双向链表的结点类class T

15、wolink /双向链表类 public:TwolinkNode*head;/头指针 Twolink()/构造函数，构造空链表 head=NULL;Twolink()/析构函数;双向链表类操作数据结构（C+版）叶核亚(1)双向链表插入结点q=new TwolinkNode(3)；q-prior=p；q-next=p-next；p-next-prior=q；p-next=q；数据结构（C+版）叶核亚(2)双向链表删除结点 p-prior-next=p-next；p-next-prior=p-prior；数据结构（C+版）叶核亚2.4.4 双向循环链表的概念数据结构（C+版）叶核亚例2-4 单向链表插入排序。在一条双向链表中，已知每个结点的next链指向后继结点，而prior链为空。设计一个函数，使每个结点的prior指向它的前驱结点，形成双向循环链表。算法实现如下：#include Twolink.h /双向链表类void makering(Twolink&h1)/将单方向的双向链表构建成双向循环链表 TwolinkNode*p=h1.head,*front=NULL;while(p!=NULL)p-prior=front;/使p-next指向p结点的前驱结点front front=p;p=p-next;数据结构（C+版）叶核亚