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

1、数据结构（C+版）第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 线性表的抽象数据类型线性表的数据元素线性表是由n（n0）个相同类型的数据元素a1，a2，an组成的有限序列，记作：LinearList=a1，a2，an其中，n表示线性表的元素个数，称为线性表的长度。若n=0，则

2、称为空表。若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: SeqList(int n=0); /构

5、造函数 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); /查找，返回k值首次出现的

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

7、再处决直到剩下的最后一个可赦免。数据结构（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 单链表的概念如果链表中的每个结点只有一个指针域，则该链表称为单链表（singly linked list）。单链表各结点的指针域通常指向其后继结点。数据结构（C+版）叶核亚2.3.2 单链表的结点类class OnelinkNode /

8、单链表的结点类 public: int data; /数据元素域 OnelinkNode *next; /指针域，指向后继结点的指针 OnelinkNode(int k=0,OnelinkNode *nextnode=NULL) /构造结点，内联函数 data=k; next=NULL; OnelinkNode() /析构函数 ;数据结构（C+版）叶核亚2.3.3 单链表类的设计与实现单链表类声明#include OnelinkNode.h /单链表的结点类class Onelink /单链表类 public: OnelinkNode *head; /单链表的头指针 Onelink(int n

9、=0); /构造函数，以n个自然数建立单链表 Onelink(); /析构函数 bool isEmpty()const return head=NULL; /判断单链表是否为空 bool isFull()const return false; /判断单链表是否已满(总是不满的) int length()const; /返回单链表的长度 OnelinkNode* index(int i)const;/定位,返回指向第i个结点的指针 int get(int i)const; /返回第i个数据元素值 bool set(int i,int k); /设置第i个数据元素值为k OnelinkNode*

10、insert(OnelinkNode* p,int k); /k值插入作为p结点的后继结点 bool remove(OnelinkNode *p); /删除p结点的后继结点 void output(OnelinkNode *p)const; /输出以p为头指针的单链表 void output()const; /输出以head为头指针的单链表 ;数据结构（C+版）叶核亚2单链表的操作图2-7 建立单向链表 (1) 建立单链表设rear指向原链表的最后一个结点，q指向新创建的结点，则将q结点链在rear结点之后的语句是：rear-next=q；rear=q；数据结构（C+版）叶核亚2单链表的操作

11、数据结构（C+版）叶核亚例2-2 单向链表逆转。 front=NULL数据结构（C+版）叶核亚例2-2 单向链表逆转。数据结构（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-next；P-next=q；数据结构（C+版）叶核亚（9）删除结点 图2-

12、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.3.5 单向循环链表类单向循环链表的概念数据结构（C+版）叶核亚2.

13、单向循环链表的声明与实现数据结构（C+版）叶核亚【例2-3】以单向循环链表求解约瑟夫环问题。 图2-12 以单向循环链表表示的约瑟夫环问题执行过程数据结构（C+版）叶核亚【例2-3】以单向循环链表求解约瑟夫环问题。数据结构（C+版）叶核亚2.4 双向链表类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 /双向链表的结点类 publi

14、c: 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() /构造函数，构造空链表 head=NULL; Twolink() /析构函数;双向链表类操