《数据结构 C++ 版 教学课件 ppt 作者 叶核亚 主编 第02章 线性表》由会员分享，可在线阅读，更多相关《数据结构 C++ 版 教学课件 ppt 作者 叶核亚 主编 第02章 线性表（45页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C+版）,叶核亚,数据结构（C+版）,第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计,数据结构（C+版）叶核亚,第2章 线性表,2.1 线性表的概念 2.2 顺序表类 2.3 单链表类 2.4 双向链表类,数据结构（C+版）叶核亚,2.1 线性表的概念,2.1.1 线性表的抽象数据类型 2.1.2 线性表的存储结构,数据结构（C+版）叶核亚,2.1.1 线性表的抽象数据类型,线性表的数据元素 线性表是由n（n0）个相同类型的数据元素a1，a2，an组成的有限序列，记作
2、： LinearList=a1，a2，an 其中，n表示线性表的元素个数，称为线性表的长度。若n=0，则称为空表。若n0，对于线性表中第i个数据元素ai，有且仅有一个直接前驱数据元素ai-1和一个直接后继数据元素ai+1，而a1没有前驱数据元素，an没有后继数据元素。,数据结构（C+版）叶核亚,线性表的基本操作 求长度：求线性表的数据元素个数。 访问：对线性表中指定位置的数据元素进行存取、替换等操作。 插入：在线性表指定位置上，插入一个新的数据元素，插入后仍为一个线性表。 删除：删除线性表指定位置的数据元素，同时保证更改后的线性表仍然具有线性表的连续性。 复制：重新复制一个线性表。 合并：将两
3、个或两个以上的线性表合并起来，形成一个新的线性表。 查找：在线性表中查找满足某种条件的数据元素。 排序：对线性表中的数据元素按关键字值，以递增或递减的次序进行排列。 遍历：按次序访问线性表中的所有数据元素，并且每个数据元素恰好访问一次。,数据结构（C+版）叶核亚,2.1.2 线性表的存储结构,线性表的顺序存储结构 线性表的链式存储结构,数据结构（C+版）叶核亚,1. 线性表的顺序存储结构,线性表的顺序存储结构是用一组连续的存储单元顺序存放线性表的数据元素，数据元素在内存的物理存储次序与它们在线性表中的逻辑次序是一致的，即数据元素ai与其前驱数据元素ai-1及后继数据元素ai+1的位置相邻。,数
4、据结构（C+版）叶核亚,图2-1 线性表的顺序存储结构,数据结构（C+版）叶核亚,2. 线性表的链式存储结构,线性表的链式存储结构是把线性表的数据元素存放在结点中。结点（node）由数据元素域和一个或若干个指针域组成。指针是用来指向其他结点地址的，这样，线性表数据元素之间的逻辑次序就由结点间的指针来实现。用链式存储结构实现的线性表称作链表。,数据结构（C+版）叶核亚,2.2 顺序表类,2.2.1 顺序表类声明 2.2.2 顺序表类操作 2.2.3 顺序表类操作的效率分析,数据结构（C+版）叶核亚,2.2.1 顺序表类声明,class SeqList /顺序表类 private: int *ta
5、ble; /指向数组的指针 int size; /顺序表的数组容量 int len; /顺序表的实际长度 public: SeqList(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
6、值作为第i个数据元素 bool insert(int k); /将k值添加到顺序表最后,函数重载 int search(int k); /查找，返回k值首次出现的位置 bool remove(int k); /删除k值首次出现的数据元素 ;,数据结构（C+版）叶核亚,2.2.2 顺序表类操作,数据结构（C+版）叶核亚,图2-2 顺序表中插入数据元素,数据结构（C+版）叶核亚,图2-3 删除顺序表中的数据元素,数据结构（C+版）叶核亚,2.2.3 顺序表类操作的效率分析,在顺序表中插入一个数据元素的平均移动次数为 时间复杂度为O(n) 。,数据结构（C+版）叶核亚,例2-1 以顺序表求解约瑟夫环
7、问题,约瑟夫环（Josephus）问题：古代某法官要判决n个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第s个人开始数起，每数到第d个犯人，就拉出来处决，然后再数d个，数到的人再处决直到剩下的最后一个可赦免。,数据结构（C+版）叶核亚,图2-4 约瑟夫环问题执行过程,数据结构（C+版）叶核亚,例2-1 以顺序表求解约瑟夫环问题,数据结构（C+版）叶核亚,2.3 单链表类,2.3.1 单链表的概念 2.3.2 单链表的结点类 2.3.3 单链表类的设计与实现 2.3.4 两种存储结构性能的比较 2.3.5 单向循环链表类,数据结构（C+版）叶核亚,2.3.1 单链表的概念,如果链表中的
8、每个结点只有一个指针域，则该链表称为单链表（singly linked list）。单链表各结点的指针域通常指向其后继结点。,数据结构（C+版）叶核亚,2.3.2 单链表的结点类,class OnelinkNode /单链表的结点类 public: int data; /数据元素域 OnelinkNode *next; /指针域，指向后继结点的指针 OnelinkNode(int k=0,OnelinkNode *nextnode=NULL) /构造结点，内联函数 data=k; next=NULL; OnelinkNode() /析构函数 ;,数据结构（C+版）叶核亚,2.3.3 单链表类的
9、设计与实现,单链表类声明 #include “OnelinkNode.h“ /单链表的结点类 class Onelink /单链表类 public: OnelinkNode *head; /单链表的头指针 Onelink(int n=0); /构造函数，以n个自然数建立单链表 Onelink(); /析构函数 bool isEmpty()const return head=NULL; /判断单链表是否为空 bool isFull()const return false; /判断单链表是否已满(总是不满的) int length()const; /返回单链表的长度 OnelinkNode* in
10、dex(int i)const; /定位,返回指向第i个结点的指针 int get(int i)const; /返回第i个数据元素值 bool set(int i,int k); /设置第i个数据元素值为k OnelinkNode* insert(OnelinkNode* p,int k); /k值插入作为p结点的后继结点 bool remove(OnelinkNode *p); /删除p结点的后继结点 void output(OnelinkNode *p)const; /输出以p为头指针的单链表 void output()const; /输出以head为头指针的单链表 ;,数据结构（C+版）
11、叶核亚,2单链表的操作,图2-7 建立单向链表,(1) 建立单链表 设rear指向原链表的最后一个结点，q指向新创建的结点，则将q结点链在rear结点之后的语句是： rear-next=q； rear=q；,数据结构（C+版）叶核亚,2单链表的操作,数据结构（C+版）叶核亚,例2-2 单向链表逆转。,front=NULL,数据结构（C+版）叶核亚,例2-2 单向链表逆转。,数据结构（C+版）叶核亚,（8） 插入结点,图2-9 单链表插入结点,数据结构（C+版）叶核亚,（8） 插入结点,空表插入 head=new OnelinkNode(1)； 头插入 q=new OnelinkNode(2)；
12、 q-next=head； head=q；,尾插入 q=new OnelinkNode(3)； q-next=NULL； P-next=q； 中间插入 q=new OnelinkNode(4)； q-next=p-next； P-next=q；,数据结构（C+版）叶核亚,（9）删除结点,图2-10 单链表删除结点,数据结构（C+版）叶核亚,（9）删除结点,删除单结点链表，只要使链表的引用head为空即可。 head=NULL; 删除链表第1个结点，只要将head指向链表第1个结点的后继结点即可。 head=head-next; 删除链表中间（尾）结点，设p指向单向链表中的某一结点，删除p的后继
13、结点的语句是： p-next=(p-next)-next；,数据结构（C+版）叶核亚,2.3.4 两种存储结构性能的比较,（1）直接访问元素的性能 （2）存储空间的利用 （3）存储密度 （4）插入和删除操作 （5）查找和排序,数据结构（C+版）叶核亚,2.3.5 单向循环链表类,单向循环链表的概念,数据结构（C+版）叶核亚,2. 单向循环链表的声明与实现,数据结构（C+版）叶核亚,【例2-3】以单向循环链表求解约瑟夫环问题。,图2-12 以单向循环链表表示的约瑟夫环问题执行过程,数据结构（C+版）叶核亚,【例2-3】以单向循环链表求解约瑟夫环问题。,数据结构（C+版）叶核亚,2.4 双向链表类
14、,2.4.1 双向链表的概念 2.4.2 双向链表的结点类 2.4.3 双向链表类的设计与实现 2.2.4 双向循环链表,数据结构（C+版）叶核亚,2.4.1 双向链表的概念,(p-prior)-next=p (p-next)-prior=p,数据结构（C+版）叶核亚,2.4.2 双向链表的结点类,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 双向链表类的设计与实现,双向链表类的声明 #include “TwolinkNode.h“ /双向链表的结点类 class Twolink /双向链表类 public: TwolinkNode *head; /头指针 Twolink() /构造函数，构造
