北京交通大学 计算机与信息技术学院 李伟生教授 2008.11,“数据结构(本)”课程 学习指导,一、了解课程的性质、把握课程的学 习内容和要求 二、深入掌握前修课程“C语言程序设计”的主要知识点 三、各章节内容简介,1.课程性质和学习目的“数据结构”是计算机专业的专业基础课和主干课程，是理论和应用密切结合的课程.电视大学的学生更应注重于应用,一、了解课程的性质、把握课程的 学习内容和要求,认真阅读本课程的教学大纲和考核说明，并作为学习本课程的指南.本课程在计算机科学与技术专业课程体系中起着承上启下的作用.它在算法研究、软件开发、系统设计等方面有着重要作用。,1.课程性质和学习目的,学习基本的数据结构（逻辑结构和存储结构）、相关操作和基于上述数据结构的两种最基本的非数值算法（排序、查找）.其核心内容是如何依据数据间的逻辑关系，把数据合理、有效地存储到计算机上进行处理。,2.学习内容和学习要求,线性表的查找,树表的查找,数组(一维、二维)和广义表,树,二叉树,哈希表及查找,串,栈和队列,基于线性表的排序,基于树的堆排序,线性表,查 找,图状结构,排 序,线 性 结 构,树 形 结 构,算 法,数 据 结 构,绪论（数据结构和算法）,内容示意图,图1,图1中的重点内容包括：数据结构和算法的基本概念、线性表、栈和队列、二叉树、图、线性表的查找、树表的查找、基于线性表的排序、基于树的排序等。,定义,逻辑结构,基本性质,程序实现,基本操作,存储结构,算法简介和要点,某类数据结构,章节内容示意图,图2,图2中逻辑结构、基本性质和操作是存储结构和算法的基础，而存储结构和算法是核心.在学习算法时，要掌握基本原理、基本步骤、既要能人工实现简单算例，也要掌握算法的程序实现，特别是要重点掌握其中的关键步骤和语句。,1.数组、结构体 2.指针和指针变量（特别是结构体指针） 3.函数中的参数传递（传数值、传地址值） 4.运算符：sizeof、&、*、-、单目运算+、-等 5.typedef、强制类型转换,二、“C语言程序设计”主要知识点,6.动态分配和释放存储空间的函数例1. struct node int datd;struct node *next;,二、“C语言程序设计”主要知识点,2.typedef struct node NODE; 3. NODE a,*p; 4.p=(NODE*)malloc(sizeof(NODE); 5.a.data=1; a.next=NULL; 6.p-data=2;,二、“C语言程序设计”主要知识点,7. p-next=,二、“C语言程序设计”主要知识点,2,NULL,1,p,data a next,data next,第1章 1.数据结构及其相关术语 逻辑结构 物理结构,三、章节内容简介,第1章 2.基本的数据结构 集合 线性 树形 图,三、章节内容简介,第1章 3.算法 算法的特征 时间复杂度的基本概念,三、章节内容简介,第2章 线性表 1.线性表的定义 特点 基本操作,三、章节内容简介,第2章 线性表 2.顺序存储（顺序表） 特点 数组方式、指针方式 顺序表的操作插入、删除、时间复杂度分析,三、章节内容简介,第2章 线性表 3.链式存储（链表） 单向链表的特点 结点（结构变量）、用指针链接结点,三、章节内容简介,第2章 线性表 单向链表的操作 （1）利用说明结构变量建立链表 （2）动态产生结点（结构变量）建立链表头插法、尾插法 （3）结点的插入、删除,三、章节内容简介,第2章 线性表 单向循环链表 （1）特点 （2）判断尾结点的条件 （3）如何使单向链表成为循环链表 双向循环链表（1）存储结构（2）特点,三、章节内容简介,第2章 线性表 4.应用(一元多项式的运算） 数组方式 链表方式,三、章节内容简介,第3章 栈和队列 1.栈 特点 基本运算(1)初始化 (2)判空 (3)判满(4)进栈 (5)出栈 (6)取栈顶,三、章节内容简介,栈的顺序存储（1）栈的顺序存储结构的定义 struct SegStack ElemType dataMaxSize;int top; /* top为栈顶指针，栈底设在数组下标 为0一端*/ ; /* top为-1时栈空， top为MaxSize-1栈满*/ struct SegStack *s; /*指向栈的指针变量*/ 访问方式例：s-top+; s-datas-top=x; /*指针变量s 是静止的* /,三、章节内容简介,（2）顺序栈的基本操作 重点掌握进栈、出栈、取栈顶元素程序中的关键语句 （3）顺序栈的溢出（“上溢”、“下溢”）,三、章节内容简介,第3章 栈和队列 1.栈 栈的链式存储（1）栈的链式存储结构的定义 struct node ElemType data; /*结点的数据域*/struct node *next; /*结点的链接指针域*/ ; struct node *top; /*栈顶指针，它是动态变化的*/,三、章节内容简介,第3章 栈和队列 1.栈 栈的链式存储（2）链栈的基本操作重点是进栈、出栈、取栈顶元素的操作（3）栈的应用重点掌握数制转换算法中栈的相关操作读懂算术表达式求值的算法了解栈在递归程序设计中的应用,三、章节内容简介,第3章 栈和队列 2.队列 特点 基本运算（1）初始化 （2）入队 （3）出队（4）读队头元素 （5）判断空 （6）判队满,三、章节内容简介,第3章 栈和队列 2.队列 队列的顺序存储结构（1）队列的顺序存储结构的定义struct SeqQueue ElemType dataMaxSize; /*用以存放队列中的元素*/int front,rear; /* 队头、队尾指针*/ ; struct SeqQueue *sq; /*指向顺序队列的指针变量，sq 对某一个队列是静态不变的*/,三、章节内容简介,（2）顺序队列的基本操作 重点掌握入队、出队操作，设定初始化时front、 rear均置为0front指向队头，rear指向队尾元素的下一个位置front等于rear时为队空，rear等于MaxSize时为队满 （3）假上溢：尾指针已超越存储空间上界，但由于队头有出队操作，实际队列可能并没有占满,三、章节内容简介,第3章 栈和队列 2.队列 循环队列（1）克服“假上溢”现象把队列设想为一个首尾相接的圆环，初始状态front=0,rear=0.约定(rear+1)等于front时，则队满，所以少用一个元素空间当front=rear，队空当(rear+1)%MaxSize=front时，队满,三、章节内容简介,第3章 栈和队列 2.队列 循环队列（1）循环队列的基本操作重点是入队、出队操作，特别注意队尾、 队头指针加1时要进行取模运算sq-rear=(sq-rear+1)%MaxSize;sq-front=(sq-front+1)%MaxSize;,三、章节内容简介,第3章 栈和队列 2.队列 队列的链式存储结构（1）链队列的存储结构的定义struct node ElemType data; struct node *next; /*结点之间的链接指针*/ ; struct node *front，*rear; /*队头指针、队尾指针*/ 链队列是规定带头结点的,三、章节内容简介,第3章 栈和队列 2.队列 队列的链式存储结构（2）链队列的基本操作重点掌握 入队，在队尾操作（相当于单向链表的尾插法）出队，在队首操作（相当于单向链表删除第一个 结点）,三、章节内容简介,第4章 串1.串的定义C语言中字符和字符串的不同2.串的存储结构 顺序结构用一维字符型数组C语言中字符串的结束符0 链接存储结点的值域存字符，按字符串的先后用指针链起来,三、章节内容简介,第4章 串 2.串的存储结构 3.字符串的输入输出 4.串的运算（求串长、串的复制、串的链接、串的比较、从串中查字符和查子串等）,三、章节内容简介,第5章 数组和广义表1. 能正确使用C语言中的数组类型（一维、二维）2.掌握特殊矩阵的压缩存储（对称矩阵、三角矩阵、稀疏矩阵等）3.广义表的定义、了解广义表的存储结构,三、章节内容简介,第6章 树和二叉树1.树 树（递归定义、实际是图论中的根树）、子树 树的表示 树的日常应用例,三、章节内容简介,第6章 树和二叉树1.树 树的基本术语结点的度、树的度、分支结点、叶结点、孩子结点、双亲结点、兄弟、结点的层、树的深度 树的性质树中的结点数等于所有结点的度数加1度为k的树中第i层上至多有ki-1个结点深度为h的k叉树至多有(kh-1)/(k-1),三. 章节内容简介,第6章 树和二叉树2.二叉树 定义递归定义：或者是一棵空树，或者是由一个根结点和两棵互不相交的左子树和右子树组成，左子树和右子树同样是一棵二叉树 二叉树的类别（满二叉树、完全二叉树）,三、章节内容简介,第6章 树和二叉树2.二叉树 二叉树的性质二叉树终端结点数等于双分支结点数加1第i层上至多有2i-1个结点深度为h的二叉树至多有2h-1个结点编号为i的结点：左孩子编号为2i；右孩子编号为2i+1；双亲结点编号为【i/2】,三、章节内容简介,第6章 树和二叉树3.二叉树的存储结构 顺序存储结构用一维数组存储，结点的编号为相应元素的下标 链接存储结构,三、章节内容简介,left,right,data,第6章 树和二叉树3.二叉树的存储结构 链接存储结构struct BTreeNode /*结点类型为structBTreeNode */ char data;struct BTreeNode *left;struct BTreeNode *right; ;,三、章节内容简介,第6章 树和二叉树3.二叉树的存储结构 链接存储结构或：typedf struct BTreeNode /*结点类型为BTreeNode */ char data;struct BTreeNode *left;struct BTreeNode *right; BTreeNode;,三、章节内容简介,第6章 树和二叉树4.二叉树遍历 二叉树的遍历的概念 遍历算法：先序、中序、后序、层次递归算法：先序、中序、后序（包括手工计算和程序实 现）非递归算法：中序遍历 通过遍历结果确定二叉树（两种遍历结果中一定要包含中序遍历）,三、章节内容简介,第6章 树和二叉树5.其它运算读懂建立二叉树、求二叉树深度等算法 6.哈夫曼树 结点的权和带权路径长度 树的带权路径长度,三、章节内容简介,第6章 树和二叉树 6.哈夫曼树 哈夫曼树（最优二叉树） 建造哈夫曼树的算法，重点掌握构造过程（手工计算），能读懂相关程序 哈夫曼编码，重点能手工完成编码，能读懂相关程序,三、章节内容简介,第7章 图 1.图的基本概念定义：G=,顶点集、边集 2.图的基本术语边的端点、邻接点有向图中边：该边是Vi的出边，Vj的入边；Vi是该边的起点，Vj是终点,三、章节内容简介,第7章 图 2.图的基本术语顶点的度、入度、出度完全图、子图、路径、简单路径、回路、简单回路连通、连通图、连通分量、带权图等,