数据结构复习大纲ppt课件.ppt

《数据结构复习大纲ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构总目录第1章　数据结构概述第2章　线性表第3章　栈与队列第4章　数组、特殊矩阵和广义表第5章　串第6章　树第7章　图第8章　查找第9章　排序集合结构线性结构树形结构图状结构第1章　数据结构概述本章内容1线性表的定义与运算2线性表的顺序存储3线性表的链式存储结构第2章线性表本章内容1．线性表的二元组表示：Linearity=（D，R）数据对象：D=｛ai∣1<=i<=nn>=0｝数据关系：R=｛∣2<=i<=n｝ai-1,ai∈D关系中是一个序偶的集合，它表示线性表中数据元素的相邻关

2、系，即ai-1领先ai，ai领先ai+1。LOC(ai)=base+(i-1)*l存储空间必须是连续的，需要预分配，插入、删除操作要移动元素;逻辑顺序与物理顺序一致，用物理上的相邻来表示逻辑上的线性关系。任意相邻元素之间无空闲空间，且相距为l;已知基地址，可以计算出任意元素的存储地址：2、顺序存储特点：3。链式存储方式：用任意存储空间单元来存放线性表的各个元素，为了能体现元素之间的逻辑关系（线性），在存放每个元素的同时，也存放相关元素的信息（相关元素的存储地址），即用指针来表示元素之间的逻辑关系。存入一个数据元素占用的空间为

3、：相关元素的地址信息存放数据元素存储一个元素占用的空间称为结点存储空间不一定连续；逻辑关系是由指针来体现的；逻辑上相邻，物理上不一定相邻；非随机存取，即访问任何一个元素的时间不同；单链表的存取必须从头指针开始线性表链式存储结构的特点在C（或C++）中可以用“结构体指针”来描述单链表由一个个结点构成，其结点的定义如下：typedefstructLnode{datatypedata;structLnode*next;}LNode，*LinkList；定义头指针变量：LinkListL；算法中用到指向某结点的指针变量时按如下格式进

4、行说明：Lnode　＊p;p->datap->nextpp=(LinkList)malloc(sizeof(Lnode));（1）在链表的头部入结点建立线性表的算法：LinkListCreateList()//建立线性表{LinkListL=(LinkList)malloc(sizeof(LNode));/*生成头结点*/L->next=NULL;/*空表*/Lnode*p;intx;/*设数据元素的类型为int*/scanf("%d",&x);while(x!=-1){p=(LinkList)malloc(sizeof(L

5、Node));p->data=x;p->next=L->next;L->next=p;scanf("%d",&x);}returnL;}（2）在链表的尾插入结点建立线性表算法：LinkListCreateList()//建立线性表{LinkListL=(LinkList)malloc(sizeof(LNode));　　　　　　　　　　　　/*生成头结点*/L->next=NULL;　　/*空表*/Lnode*p,*r=L;intx;　　/*设数据元素的类型为int*/scanf("%d",&x);while(x!=-1){p

6、=(LinkList)malloc(sizeof(LNode));p->data=x;p->next=r->next;r->next=p;r=p;/*r指向新的尾结点*/scanf("%d",&x);}returnL;}第3章栈和队列本章学习两种特殊的线性数据结构,它们特殊在定义的操作不同,即插入和删除操作只能在线性表的两端进行.只能在一段进行的-----栈分别在两端进行的-----队列3-1栈的定义和运算3-1-1栈（Stack）的定义1.栈的定义栈是限制在表尾进行插入和删除的线性表。2.栈的特性（1）栈的主要特点是“后进

7、先出”（2）允许插入、删除的这一端称为栈顶（Top），另一端称为栈底（Bottom）。a1a2a3进栈出栈栈顶（Top）:插入、删除的一端;栈底（Bottom）:固定不动的一端;入栈(push);又称压入,即插入一个元素;出栈(pop):又称弹出,即删除一个元素;例1：假设有A,B,C,D四个元素,它们入栈的次序为A->B->C->D出栈的次序任意,请问不可能得到下面那些出栈序列?(1)ABCD(2)DBCA(3)CDBA(4)CBAD(5)ACBD(6)DBAC(7)ADCB(8)CABD例2：把3+4/（25–（6+15

8、））*8转换为后缀表达式3.2.1队列的定义和基本运算一、队列（QUEUE）的定义1．队列的定义设有n个元素的队列Q=（a1，a2，a3，…，an），则称a1为队首元素，an为队尾元素。队列中的元素按，a1，a2，a3，…，an–1，an的次序进队，按a1，a2，a3，…，an–1，an次