数据结构(C语言)上ppt.ppt_第1页
数据结构(C语言)上ppt.ppt_第2页
数据结构(C语言)上ppt.ppt_第3页
数据结构(C语言)上ppt.ppt_第4页
数据结构(C语言)上ppt.ppt_第5页
已阅读5页,还剩169页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构(C语言)上,第1章 绪 论,(时间:1次课,2学时),第1章 绪 论,教学提示:本章主要介绍数据结构的概念及有关术语,为后续章节做好铺垫。 教学目标:通过本章的学习,使读者能掌握数据结构的概念和有关的术语。,第1章 数据库系统的基本概念,1.1 什么是数据结构 1.2 基本概念和术语 1.3 运算、算法和算法分析 1.4 习题,1.1 什么是数据结构,数据结构这门学科主要是研究各种结构、定义在各种结构上的操作和这些操作在计算机中的实现方法。 提示:数据结构研究实际问题中元素之间的逻辑关系、元素及其关系在计算机中的表示和相关的操作。数据结构是一门综合性的专业基础课,它涉及到计算机硬件的研究范围和软件的研究范围(存储装置和存取方法等)。,用计算机解决一个具体问题时要考虑以下步骤:,(1) 从具体问题中抽象出一个适当的数学模型。即从具体问题中找出操作对象之间含有的关系,然后用数学语言加以描述。 (2) 设计一个适合该数学模型的算法。 (3) 编写程序。 (4) 进行测试、调整、修改,直至解决问题。,在实际问题中,各个对象之间的关系有线性的、层次的和网状的等等. 实例1:,线性关系: 列车中各车箱之间的关系就是线性的。 排队买车票人之间的关系是线性的。 叠盘子中各盘子之间的关系是线性的。,实例2:,层次关系: 在军队的编制中,军下面是师,师下面是团,军、师、团之间是层次关系。 人的辈分关系中,祖辈下是父辈,父辈下是子辈,这些是层次关系。 学校的编制中,学校分成若干个学院、学院下又分成若干个系、系下又分成若干个教研室,这些也都是层次关系。,实例3:,网状关系: 在城市铁路交通图中,各城市之间的关系是网状关系。 电话网中,各电话之间是网状关系。 计算机网络中,各计算机之间是网状关系。,1.2 基本概念和术语,数据(Data): 数据是计算机表示客观事物的符号。在计算机科学中,所有能输入到计算机中并被计算机程序处理的符号统称为数据。它是计算机程序加工的“原料”。例如,一个用某种程序语言编写的源程序、一篇文章、一张地图、一幅照片、一首歌曲等等,都属于计算机能处理的数据。因此,对计算机科学而言,数据的含义极为广泛;图象、声音等也都可以通过编码而归之于数据的范畴。,1.2 基本概念和术语,数据元素: 数据元素是数据的基本单位。数据的范围非常广泛,数据元素也是可大可小的。在计算机程序中通常作为一个整体进行考虑和处理。有时,一个数据元素可由若干个数据项组成。例如,一本书的书目信息为一个数据元素,而书目信息中的每一项(如书名、作者名)是数据项。,1.2 基本概念和术语,数据结构: 数据结构是彼此具有一定关系的数据元素的集合。这些关系反映了客观世界事物之间的联系。这种数据元素之间的相互关系称为结构。由于客观事物存在着各种不同的联系形式,因此在计算机内反映数据的关系时,可以用结构来描述这些关系。数据结构分为逻辑结构和物理结构两个研究方面。逻辑结构是指数据元素之间的关系。,1.2 基本概念和术语,四种基本数据结构: 集合:这个结构中的数据元素之间同属于一个集合,除这一关系外没有其他关系。 线性结构:这个结构中数据元素存在着由依次排列的先后次序决定的关系。 树型结构:这个结构中数据元素之间存在着层次关系。 图结构:这个结构中数据元素之间相互连接成网状。,图1.1 四种基本数据结构,1.2 基本概念和术语,存储结构: 数据结构在计算机中的表示称为数据的物理结构,又称为存储结构。存储结构是指在计算机中存储数据和逻辑结构。同一种逻辑结构可以使用不同的物理结构来实现。 在计算机中表示信息的最小单位是一个二进制位,叫做bit位。一个数据元素的“bit位串”通常称为“结点”。 当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串称为数据字段。 数据元素之间的关系在计算机中有两种基本的存储结构:顺序存储结构和链式存储结构。 在高级语言的指针类型中,不是针对计算机的实际地址进行存储,称这种存储为数据结构的虚拟存储结构。,1.2 基本概念和术语,数据类型: 高级程序设计语言中的数据类型分为原子类型和结构类型。原子类型的值是不可分解的。C语言中的基本类型(整型、实型、字符型和枚举类型)、指针类型和空类型都是原子类型。结构类型是由若干类型组成的,是可以分解的。例如C语言中数组的类型和结构体类型是由其他类型定义的。 在计算机中,数据类型并非局限于高级语言中的一个具体类型,而是通常用抽象数据类型表示类型。上机实现时,再把抽象数据类型用具体的类型代替。,1.3 运算、算法和算法分析,1.3.1 运算 1.3.2 算法及其描述 1.3.3 算法分析和算法复杂度,1.3.1 运算,运算可以分为下列两种基本类型: 加工型运算:运算后改变了原结构中数据元素的个数或数据元素的内容。 (2) 引用型运算:运算不改变结构中数据元素的个数和元素的内容,只从结构中提取某些信息作为运算的结果。,1.3.1 运算,基本运算主要包括下列几种: 插入运算:属于加工型运算,在原结构的指定位置上增添新的数据元素。 删除运算:属于加工型运算,将原结构中的某个指定的数据元素删除。 查找运算:属于引用型运算,从结构中找出满足条件的数据元素的位置。 读取运算:属于引用型运算,使用结构中满足条件的数据元素的内容。 更新运算:属于加工型运算,更换结构中某个数据元素的内容。 使用这些基本运算,可以构成其他的复杂运算 。,1.3.2 算法及其描述,定义: 算法是计算机科学的一个概念,也是程序设计的一个重要概念。 算法是对求解某个问题的步骤的一种描述方法。 算法是描述操作步骤的有限序列。,1.3.2 算法及其描述,算法要具备下列五个特性: 有穷性:算法必须在执行有穷步之后结束,而每一步都必须在有穷时间内完成。 确定性:算法中每一步操作的含义都必须是确定的,不能有二义性。 可行性:一个算法必须是可行的,即算法中每一操作都能通过已知的一组基本操作来实现。 输 入:一个算法可以有零个或多个输入。 输 出:一个算法有一个或多个输出。,1.3.3 算法分析和算法复杂度,通常用以下几个标准来评价其优劣: 正确性:算法必须能正确解决问题。 易读性:算法应当便于阅读和理解,以利于修改和改写成程序。 健壮性:当输入非法数据时,算法也能做出特殊处理,不会继续操作或死机。 高效率:算法的效率主要从时间和空间两个方面考虑。解决一个问题的算法如果使用时间少和占用空间少,则是算法高效率的体现。,1.3.3 算法分析和算法复杂度,算法分析: 研究算法的效率称为算法复杂度的分析(简称算法分析)。简单地说,一个算法所进行的计算次数的多少称为时间复杂度,一个算法所需要辅助存储空间的多少称为空间复杂度。 在算法分析中绝对的量不能反映时间复杂度,使用一个函数T(n)表示一个算法的复杂度。一个算法所解决问题的规模n增大时,时间的增长率越小,时间复杂度越好,反之时间复杂度越坏。也就是说,时间复杂度是n的一个函数。从好到坏表示时间复杂度的函数依次是:常量阶O(1);对数阶O(log n);线性阶O(n);平方阶O(n2);多项式阶O(nk);指数阶O(2n)等。,1.3.3 算法分析和算法复杂度,算法复杂度,举例: x+; s=x+2; 时间复杂度为O(1) for(k=1; k=n; k+) s=k+2; 时间复杂度为O(n) for(k=1; k=n; k+) for(j=1; j=n; j+) s=k+j; 时间复杂度为O(n2),1.4 习 题,1 填空题 2 选择题 3 简答题,1.4 习 题_填空题,(1) 从数据结构S中找出满足条件的结点在S中位置的运算是_型运算。 (2) 从数据结构S中读出结构中指定位置上内容运算是_型运算。 (3) 从数据结构S中的某指定位置上增加一个新结点的运算是_型运算。 (4) 从数据结构S中撤消结构中指定位置上结点的运算是_型运算。 (5) 从数据结构S中修改结构中某指定结点内容的运算是_型运算。,1.4 习 题_选择题,(1) 数据表示是指数据_。 A. 书写在纸上 B. 从机外转为机内 C. 磁盘中的数据 D. 光盘中的数据 (2) 数据元素是数据的基本单位,其内_数据项。 A. 只能包括一个 B. 不包含 C. 可以包含多个 D. 必须包含多个 (3) 逻辑关系是指数据元素间的_。 A. 类型 B. 存储方式 C. 结构 D. 数据项,1.4 习 题_选择题,(4) 逻辑结构是_关系的整体。 A. 数据元素之间逻辑 B. 数据项之间逻辑 C. 数据类型之间 D. 存储结构之间 (5) 数据结构有_种基本逻辑结构。 A. 1 B. 2 C. 3 D. 4 (6) 下列四种基本的逻辑结构中,数据元素之间关系最弱的是_。 A. 集合 B. 线性结构 C. 树形结构 D. 图状结构,1.4 习 题_选择题,(7) 一个存储结点存放一个_。 A. 数据项 B. 数据元素 C. 数据结构 D. 数据类型 (8) 用类C语言描写的算法_。 A. 可以直接在计算机上运行 B. 可以描述解题思想和基本框架 C. 不能改写成C语言程序 D. 与C语言无关 (9) 算法能正确地实现预定功能的特性称为_。 A. 正确性 B. 易读性 C. 健壮 D. 高效率,1.4 习 题_选择题,(10) 下列时间复杂度中最坏的是_。 A. O(1) B. O(n) C. O(log2n) D. O(n2) (11) 下列时间复杂度中最好的是_。 A. O(1) B. O(n) C. O(log2n) D. O(n2) (12) 下列算法的时间复杂度是_。 for(i=0; in; i+ ) for(j=0; jn; j+ ) cij=i+j; A. O(1) B. O(n) C. O(log2n) D. O(n2),1.4 习 题_选择题,(13) 下列算法的时间复杂度是_。 for(i=0; in; i+ ) cii=i+i ; A. O(1) B. O(n) C. O(log2n) D. O(n2) (14) 在计算机中存储一个数据元素的位串称为_。 A. 结点 B. 数据项 C. 数据字段 D. 字符串 (15) 记录中的各个数据项的类型_。 A. 必须相同 B. 不必相同 C. 不能相同 D. 不确定,1.4 习 题_简答题,(1) 简述数据与数据元素的关系与区别。 (2) 说出数据结构中的四类基本逻辑结构,并说明哪种关系最简单、哪种关系最复杂。 (3) 画出线性结构的示意图。 (4) 画出树形结构的示意图。 (5) 画出图状结构的示意图。 (6) 什么是逻辑结构、存储结构?有哪几种存储结构? (7) 简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 (8) 简述逻辑结构与存储结构的关系。 (9) 通常从哪几个方面评价算法的质量? (10) 算法的时间复杂度主要有那几种?按从优到劣的顺序写出各种表示形式。,Q & A? Thanks!,第2章 线 性 表,(时间:2次课,4学时),第2章 线 性 表,教学提示:本章介绍的线性表结构是最基本的数据结构,也是学习后边章节重要的基础。重点介绍线性表的概念、运算、存储结构和算法。 教学目标:通过本章的学习,使读者能掌握线性表的概念、有关术语、存储方式、相关运算和算法,并能灵活应用。,第2章 线 性 表,2.1 线性表的定义和基本运算 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 链表的上机实习 2.5 习题,2.1 线性表的定义和基本运算,1线性表的定义 线性表是n(n0)个结点组成的有限序列。从这个定义中应当理解到以下几点: 线性表中的元素是有顺序的; 线性表中的元素个数可以为0,即可以是空的线性表; 线性表中的元素可以是多个,但不能是无穷多个; 同一个线性表中元素的类型相同,因此元素长度也相同。,2.1 线性表的定义和基本运算,2线性表的特点 任意一个非空的线性表都具有以下特点: 只有一个排在第一个的元素,称为线性表的起始元素。 只有一个排在最后的元素,称为线性表的终端元素。 除起始元素外,线性表中的其他元素仅有一个直接前驱元素;除终端元素外,线性表中的其他元素仅有一个直接后继元素。,2.1 线性表的定义和基本运算,3线性表的逻辑表示形式 线性表的逻辑表示形式如下: L1=( ):L1是一个空的线性表; L2=(a,b,c,d,e):L2线性表中有5个元素,a是起始元素、e是终端元素,c的直接前驱元素是b,c的直接后继元素是d。a元素的序号是1,c元素的序号是3。,2.1 线性表的定义和基本运算,4线性表的基本运算 InitList(L):初始化运算,其功能是创建了一个空的线性表L。 ListLength(L):求线性表L的长度运算。 GetNode(L,i):读元素运算,函数值是线性表L的第i个元素。 LocateNode(L,X):定位运算,是线性表L中X元素的位置。 InsertList(L,X,i):插入运算,其功能是将X插入线性表L中,作为线性表L的第i个元素。 DeleteList(L,i):删除运算,将线性表L的第i个元素删除。 Clear(L):清除表元素运算,其功能是删除 L表中的元素,使线性表L成为空表。 Empty(L):判断L表是否是空表,其功能是L表为空时函数值为1,否则为0。,2.2 线性表的顺序存储结构,2.2.1 线性表顺序存储结构的概念 2.2.2 线性表顺序存储的实现,2.2.1 线性表顺序存储结构的概念,顺序表: 将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元内,采用这种方法存储的线性表简称为顺序表。 顺序表的虚拟存储是采用程序设计语言的一维数组来存储线性表。 顺序表是存储在一段连续的空间内,逻辑上相邻的元素在存储位置上也相邻。,2.2.1 线性表顺序存储结构的概念,提示:用LOC(ai)表示线性表元素ai的存储空间的起始地址,若L表示一个元素的长度,则对于正整数i有: LOC(ai+1)= LOC(ai)+ L 若线性表的起始地址是b,则: LOC(ai)=b+(i-1)*L 或者 LOC(ai)= LOC(a1)+(i-1)*L,2.2.1 线性表顺序存储结构的概念,2.2.1 线性表顺序存储结构的概念,2.2.2 线性表顺序存储的实现,1顺序表的类型定义 struct sqlist datetype elemmaxlen; int length; ; 其中datetype表示线性表元素的抽象数据类型,用程序设计语言上机实现算法时,再定义为具体的数据类型。 maxlen表示线性表最多允许的元素个数。 length表示线性表的当前长度。其值是0至maxlen间的一个整数。,2.2.2 线性表顺序存储的实现,2. 运算的算法插入运算的算法(算法2.1) Insert_sqlist(struct qlist L, datetype x, int i) if(iL.length+1) error(“illegal value of i“); /*插入位置i不正确*/ else if(L.length = Maxlen) error(“List overflow“) ; /*表满*/ else /*将线性表的最后一个元素至第i个元素均向后移一个位置*/ for(k=L.length-1; k=i-1; k-) L.elemk+1= L.elemk; L.elemi-1=x ; /*将x插入线性表的第i个位置*/ L.length+ ; /*线性表长度加1*/ 插入算法的时间复杂度为O(n)。,2.2.2 线性表顺序存储的实现,2. 运算的算法删除运算的算法(算法2.2) elemtype Delete_sqlist(struct sqlist L, int i) if(iL.length) error(“illegal value of i“); /*删除元素的序号i不 正确*/ else if(L.length = 0) error(“List empty“); /*表空*/ else x=L.elemi-1; /*将线性表的第i+1个元素至最后一个元素均向前移一个位置*/ for(k=i;k=L.length-1; k+) L.elemk-1= L.elemk; L.length-; /*线性表长度减1*/ return(x); 删除算法的时间复杂度为O(n)。,2.3 线性表的链式存储结构,2.3.1 单链表 2.3.2 循环链表 2.3.3 双向链表,2.3.1 单链表,图2.1 单链表的示意图,2.3.1 单链表,1单链表结点的数据结构 用C语言表示单链表结点的数据结构如下: typedef struct node *pointer; struct node datatype data; pointer next; ; typedef pointer LIST ;,2.3.1 单链表,2单链表运算的算法 初始化运算的算法(算法2.3) void InitList(LIST L) /* L是指向链表结点的指针类型变量,使其指向链表的表头*/ L=(struct node *)malloc(sizeof(struct node); /* 申请结点空间,L指向它*/ L-next=null; /* L指向的结点作为链表的表头结点,空链表表头结点的指针域为空 */ ,2.3.1 单链表,求表长运算的算法(算法2.4) int ListLength(LIST L) p=L ; /* p是指针类型变量,开始时P指向表头结点*/ j=0; /* j是整型变量,用它记录着结点的个数*/ while(p-next!=null) p=p-next ; /* 让指针变量P指向链表的下一个结点*/ j+; /* j记录的个数加1*/ return(j); /* j的最后的值是链表的长度*/ ,2.3.1 单链表,读元素运算的算法(算法2.5) pointer GetNode(LIST L, int i) p=L; j=0; while(p-next!=null) /* 返回空指针*/ ,2.3.1 单链表,插入运算的算法(算法2.6) void InsertList(LIST L, datatype x, int i) p=L; j=0; while(p!=null) /* 使链表的原第i-1个结点指向新结点 */ ,2.3.1 单链表,删除运算的算法(算法2.7) Datatype DeleteList(LIST L, int i) p=L; j=0; while(p!=null) /*返回被删除结点的值 */ ,2.3.2 循环链表,提示:单链表的尾结点的指针域(next)是空指针,如果将该指针域改为指向表头结点的指针,则该链表就是循环链表。 提示:循环链表的算法与单链表的算法基本相同,只是单链表L是空链表的条件是: L-next=null,而循环链表L是空链表的条件是L-next=L。,图2.4 循环链表,2.3.3 双向链表,提示:如果将循环链表的每个结点都设置指向前驱和指向后继的指针,则该链表就是双向循环链表。,1双向链表结点的数据结构 typedef struct DuLNode *pointer; typedef struct DuLNode datatype data; pointer prior,next; DuLNode;,2.3.3 双向链表,图2.5 双向链表,2.3.3 双向链表,2双向链表运算的算法,双向链表删除的算法(算法2.8) Datatype DeleteList_DuL(DuLNode *L,DuLNode *p)/*删除双向链表L中p指针所指的元素,并将被删除的结点的值作为函数值返回*/ x=p-data; /* 使删除结点的值赋给x */ p-prior-next=p-next; /* 使p结点的前驱结点的后继指针指向p结点的后继结点*/ p-next-prior=p-prior; /* 使p结点的后继结点的向前指针指向p结点的前驱结点*/ free(p); /* 释放p所指被删除的结点 */ return (x); /* 返回被删除结点的值 */ ,2.3.3 双向链表,2双向链表运算的算法,在双向链表L中插入元素的算法(算法2.9) InserterList_DuL(DuLNode *L,DuLNode *p, Datatype e) /*将e元素插入到双向链表L中p指针所指的元素的前边*/ s=(struct DuLNode *)malloc(sizeof(struct DuLNode); /* 申请一个结点,让指针s指向它*/ s-data=x; /* 将x送入新结点*/ s-next=p; /* 使新结点的后继指针指向p结点*/ s-prior=p-prior; /* 使新结点的前驱指针指向p结点的前驱结点*/ p-prior-next=s; /* 使p结点的前驱结点的后继指针指向新结点*/ p-prior=s; /* 使p结点的前驱指针指向新结点*/ ,2.4 链表的上机实习,2.4.1 实习1,编写完整程序。程序中包括下列函数,在主程序中调用各函数,实现对单链表L的相关操作(算法2.10)。 1.建立链表函数 void createlist (L) 功能:输入n个元素,存放在单链表L中,可按顺序输出L中的元素。 2.插入函数 void insert (L, I, x) 功能:输入x,并将x插入到链表L中,作为链表的第i个元素,并按顺序输出L中的元素。 3.删除函数 void delete(L, i, x) 功能:将链表L中第i个元素删除,将删除的元素值赋给形参x并显示出来,并按顺序输出L中的元素。,2.4.1 实习1,4.输出函数 void print(L) 功能:将链表L的元素值输出。 在主菜单中提供下列菜单: 1-建立链表L 2-插入元素 3-删除元素 4-显示链表中的各元素 0-退出 程序参见P18.,2.4.2 实习2,设线性表A=(a1,a2,a3,an)以带头结点的单链表作为存储结构。编写一个函数,对A进行调整,使得当n为奇数时A=(a2,a4,an-1,a1,a3,,an);当n为偶数时A=(a2,a4, an,a1,a3,,an-1)。(算法2.11) 具体算法如下: Regulate(nodetype *p) /* p是指向表头结点的指针 */ nodetype *p1,*p2,*q; p1=p; q=p1-next; p2=q-next; while(p2) q-next=p2-next; p2-next=p1-next; p1-next=p2 p1=p2; q=q-next; p2=q-next; ,2.4.3 实习3,假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法,删除表中所有数值相同的多余元素,并释放结点空间。例如:(7,10,10,21,30,42,42,42,51,70),经算法操作后变为:(7,10,21,30,42,51,70)。(算法2.12) 具体算法如下:,DeleteEq(nodetype *L) nodetype *p ,*p1, *p2; p1=L-next; p=p1-next; while(p) if(p1-data=p-data) p2=p;,p=p-next; p1-next= p; free(p2); else p1=p; p=p-next; ,2.5 习 题,1 填空题 2 选择题 3 简答题 4 算法题,2.5 习 题_填空题,(1) 链表中逻辑上相邻的元素的物理位置_相连。 (2) 在单链表中除首结点外,任意结点的存储位置都由_结点中的指针指示。 (3) 在单链表中,设置头结点的作用是在插入或删除首结点时不必对_进行处理。 (4) 已带表头结点的单链表L,指针p指向L链表中的一个结点,指针q是指向L链表外的一个结点,则: 在指针p所指结点后插入q所指结点的语句序列是_; 在指针p所指结点前插入q所指结点的语句序列是_; 将q所指结点插入在链表首结点的语句序列是_; 将q所指结点插入在链表尾结点的语句序列是_。,2.5 习 题_填空题,(5) 已知带表头结点的单链表L,指针p指向L链表中的一个结点(非首结点非尾结点),则: 删除指针p所指结点的直接后继结点的语句是_; 删除指针p所指结点的直接前驱结点的语句序列是_; 删除指针p所指结点的语句序列是_; 删除首结点的语句序列是_; 删除尾结点的语句序列是_。 (6) 已知指针p指向双向链表中的一个结点(非首结点,非尾结点),则: 将结点s插入在指针p所指结点的直接后继位置的语句是_; 将结点s插入在指针p所指结点的直接前驱位置的语句是_; 删除指针p所指结点的直接后继结点的语句序列是_; 删除指针p所指结点的直接前驱结点的语句序列是_; 删除指针p所指结点的语句序列是_。,2.5 习 题_填空题,(7) 线性表的存储结构有顺序存储和_存储两种。 (8) 线性表的元素长度为4,在顺序存储结构下LOC(ai)=2000,则LOC(ai+1)= _。 (9) 线性表a的元素长度为L,在顺序存储结构下Loc(ai)=Loc(a1)+_。 (10) 在线性表的链式存储结构中,某结点的指针字段指向该结点的_两种存储。 (11) 线性表的元素长度为4,Loc(a1)=1000,则Loc(a3)= _。 (12) 在下图所示的链表中,若在指针p所指的结点之后插入数据字段相继为a和b的两个结点,则可用下列两个语句实现该操作,它们依次是_和_。,2.5 习 题_填空题,2.5 习 题_单项选择题,2.5 习 题_单项选择题,2.5 习 题_单项选择题,2.5 习 题_单项选择题,2.5 习 题_单项选择题,2.5 习 题_单项选择题,2.5 习 题_简答题,在什么情况下使用顺序表比链表好? 已知带表头的单链表L,简述下列对L链表操作算法的功能。 Status a(L) if(L-next ,2.5 习 题_简答题,(3) 已知带表头的循环链表L,简述下列对L链表操作算法的功能。 void BB(s,q) /* s、q是指向结点类型的指针 */ p=s; while(p-next!=q) p=p-next; p-next=s; void AA(pa,pb) /* pa、pb是指向单向循环表中的两个结点的指针 */ BB(pa,pb; BB(pb,pa); (4) 分别画出线性表L=(a,b,c)存储在单链表、循环链表、双向循环链表中的示意图。 (5) 哪些链表从尾指针出发可以访问到链表中的任意结点?,2.5 习 题_算法题,设某带头结点的单链表的结点结构说明如下: typedef struct node1 int data; struct node1 *next; node; 试设计一个算法:void copy(node *head1, node *head2),将以head1为头指针的单链表复制到一个以head2为头指针的单链表中。,2.5 习 题_算法题,(2) 设有两个按升序排列的单链表X和Y,其头指针分别为p、q,结点结构说明如下: typedef struct node1 intdata; struct node1 * next node; 试设计一个算法void concat(node p, q),将它们合并成一个以p为头指针的单链表Z,使其仍然有序。,2.5 习 题_算法题,2.5 习 题_算法题,2.5 习 题_算法题,Q & A? Thanks!,第3章 栈和队列,(时间:2次课,4学时),第3章 栈和队列,教学提示:本章介绍应用广泛的数据结构 栈(stack)和队列(queue),将分别给出这两种结构的定义、基本运算、存储结构以及一些基本运算的具体实现,并给出一些应用实例。 教学目标:通过本章的学习,使读者能够掌握栈和队列的概念、有关术语、存储方式、相关运算和算法,并能灵活应用。,第3章 栈和队列,3.1 栈 3.2 队列 3.3 栈和队列上机实习 3.4 习题,3.1 栈,3.1.1 栈的定义 3.1.2 栈的存储结构及其基本运算的实现,3.1.1 栈的定义,栈(Stack): 栈是限定仅在表尾进行插入或删除操作的线性表。栈的表尾端称为栈顶(top),表头端称为栈底(bottom)。不含元素的栈称为空栈。 假设栈S=(a1,a2,an),则称a1为栈底元素,an为栈顶元素。栈中元素进栈的顺序是a1,a2,an,出栈的第一个元素应是最后进栈的元素,也就是栈顶元素。,3.1.1 栈的定义,栈的基本运算如下: 初始化IniStack(S):其作用是建立一个空栈,准备存放数据。 进栈Push(S,x):其作用是将数据元素x插入栈S,使x成为S的栈顶元素。 出栈Pop(S):其作用是当栈不空时返回栈顶元素为该函数的值,然后删去栈顶元素。 读栈顶Get Top(S):其作用是当栈不空时返回栈顶元素为该函数的值,但是栈顶保持不变。 判栈空Empty Stack(S):若S为空栈则该函数值为1,否则为0。,3.1.2 栈的存储结构及其基本运算的实现,栈的存储结构有顺序存储和链式存储两种存储结构。 1. 顺序存储结构 用一个向量(一维数组)作为栈的顺序存储结构,C语言表示形式如下: struct stack datatypes arraymaxlen; int top; ,3.1.2 栈的存储结构及其基本运算的实现, 插入算法(算法3.1),void push(struct Stack s,datatype x) /*将数据元素x进栈*/ if(s.top = maxlen-1) error(“栈满“) /*栈已满,不能再插入新元素*/ else s.top=s.top+1; /*栈顶的位置上移一个位置*/ s.arraytop=x; /*将元素x放入新栈顶*/ ,3.1.2 栈的存储结构及其基本运算的实现, 删除算法(算法3.2),datatypes pop(struct stack s) /* s退栈,即删去栈顶元素*/ if(s.top=-1) error(“Emptystack“); /* s栈已空,不能退栈*/ else s.top=s.top-1; /*栈顶位置减1*/ return(arrays.top+1); /*返回原栈顶元素的值*/ ,3.1.2 栈的存储结构及其基本运算的实现,2. 链式存储结构 利用链式存储结构表示的栈称为链栈。其各结点的结构与单链表中的结点结构完全相同。 规定链表的首元素为栈顶,另一端为栈底。因为栈的主要运算都在栈顶进行,为访问单链表的表头方便,指定单链表的表头作为栈顶。 链栈的插入和删除运算实现起来和链表的操作相似,下面仅给出链栈的进栈和出栈操作的具体算法。其中结点结构定义为: typedef struct node elemtype data; struct node *next; node,*pointer;,3.1.2 栈的存储结构及其基本运算的实现,2. 链式存储结构 进栈算法(算法3.3),void push(pointer s,datatype x) /*将数据x插入到栈顶,s为表头指针*/ p=(pointer*)malloc(sizeof(node); /*申请一个新结点*/ p-data=x; /*将 x放入新结点的数据域*/ p-next=s-next; /*将新结点插入链表,作为首元素*/ s-next=p; ,3.1.2 栈的存储结构及其基本运算的实现,2. 链式存储结构 出栈算法(算法3.4),datatype pop(pointer s) /*将链栈s的栈顶出栈*/ if(s-next=null) return(null); /*空栈,返回空*/ else p=s-next; /*使P指针指向栈顶结点*/ x=p-data; /*将栈顶结点的数据域的值赋给 x*/ s-next=p-next; /*删除栈顶结点*/ free(p); /*释放被删除的结点*/ return(x); /*返回原栈顶结点的数据域的值*/ ,3.2 队 列,3.2.1 队列的定义 3.2.2 队列的基本运算 3.2.3 队列的存储结构及其基本运算的实现,3.2.1 队列的定义,队列(Queue)是只能在一端进行插入,而在另一端删除的线性表。能进行插入的一端称为队列的尾,能进行删除的一端称为队列的头。 队列是限定只能在队尾插入、只能在队列的头删除的线性表。 先进入队列中的元素称为队列的头元素(队列的头),最后进入队列中的元素称为队列的尾元素(队列的尾)。队列称为先进先出表(First In First Out),简称FIFO。,3.2.2 队列的基本运算,队列的基本运算有以下几种: 初始化InitQueue(Q):其作用是建立一个空队列Q,准备存放数据。 入队列EnQueue(Q,x):其作用是将数据x插入到队列Q的队尾,队列的长度加1。 读队头GetHead(Q):其作用是当队列非空时,返回队列头元素的值,但不删除队列头元素。 判队列空否EmptyQueue(Q):若队列Q为空,则返回的值为1,否则返回的值为0。,3.2.3 队列的存储结构及其基本运算的实现,队列和栈一样,也可采用顺序存储和链式存储两种存储结构。 1. 链式存储结构 采用链表存储的队列叫链队列。一般用单链表表示一个链队列。队列经常从队列的头出队,从队列的尾进队,所以用两个指针分别指向两端。一个指向头结点,称为front,另一个指向尾结点,称为rear。用这种链表表示队列的示意如图3.3所示。 提示:使用上述链表存储队列时,必须注意正确使用front和rear两个指针,才能方便地实现队列的各种运算。,图3.3 链表存储的队列,3.2.3 队列的存储结构及其基本运算的实现,1. 链式存储结构 进队列算法(算法3.5),void EnQueue(struct linkqueue Q,elemtype x)/*x进链式队列Q*/ p=(pointer*)malloc(sizeof(node); /*为新元素准备结点的空间*/ p-data=x; /*将数据 x存入该新结点*/ p-next=NULL; /*将尾结点的指针域置空指针*/ Q.rear-next=p; /*将新结点插入队列 Q的尾部*/ Q.rear=p; /*将尾指针指向新的尾元素*/ ,3.2.3 队列的存储结构及其基本运算的实现,1. 链式存储结构 出队算法(算法3.6),datatype OutQueue(stuct linkqueue Q) if(front=rear) error(“Empty Queue“); else p=Q.front-next; /*使P指向队列的头元素*/ x=p-data; /*将头元素的值赋给x*/ Q.front-next=p-next; /*删去队列的头元素*/ free(p); /*释放被输出元素所占的空间*/ return(x); /*返回x中存放的原队列头元素的值*/ ,3.2.3 队列的存储结构及其基本运算的实现,2. 顺序存储结构 用顺序存储结构存储的队列称为顺序队列。顺序队列用一个向量来存储队列元素,再用整型变量front存储队列的头元素位置的前一个位置,用整型变量rear存储队列的尾元素的位置。 初始化运算 进队列运算 出队列运算,将队列头元素删除,并返回其值。 读队列头元素运算 判断队列是否是空队列的运算,3.3 栈和队列上机实习,3.3.1 实习1 3.3.2 实习2 3.3.3 实习3 3.3.4 实习4,3.3.1 实习1,借助栈将输入的任意一个非负的十进制整数,转换成与其等值的八进制数并输出,用C语言编写函数。(算法3.13),conversion( ) InitStack(s); scanf(“%d“,n); while(n) push(s,n%8); n=n/8; ,while(!EmptyStack (s) pop(s,x); printf(“%d“,x); ,3.3.2 实习2,编写判断“”与“”是否配对的函数。(算法3.14) pracket( ) InitStack(s); ch=getchar( ); while(ch!=#) if(ch= ) Push(s,ch); if(ch= ) ,if(EmptyStack(s)error(“不配对“); else Pop(s,x); ch=getchar( ); if(!Emput(s)error(“不配对“); ,3.3.3 实习3,求链栈Ls中包括栈元素个数的算法。(算法3.15) StackLength(Ls) p=Ls-next; i=0; while(p) p=p-next; i+; return(i); ,3.3.4 实习4,求链队Lq中包括栈元素个数的算法。(算法3.16) QueueLength(Lq) p=Lq-front-next; i=0; while(p) p=p-next; i+; return(i); ,3.4 习 题,1 填空题 2 选择题 3 简答题 4 算法题,3.4 习 题_填空题,1. 填空题 (1) 已知顺序栈s,在对s进行进栈操作之前要先判断_。 (2) 已知栈s是顺序存储结构,在进行出栈操作之前要先判断_。 (3) 顺序栈s存储在数组Ss-data0max中,s栈满的条件是_。 (4) 同一栈内的各元素的类型_。 (5) 顺序栈s存储在数组Ss-data0max中,进行出栈操作后,要执行的语句是Ss-top_。 顺序栈s存储在数组Ss-data0max中,s进行进栈操作前,要执行的语句是Ss-top_运算。 顺序栈s存储在数组Ss-data0max中,s栈满时,Ss-top=_。,3.4 习 题_ 填空题,(8) 顺序栈s存储在数组Ss-data0max中,s栈空时,Ss-top=_。 (9) 对链栈ls,指向栈顶元素的指针是_。 (10) 链栈ls是空栈的条件是_。 (11) 链栈ls的栈顶元素是链表的_元素。 (12) 链栈ls的栈顶元素安排在链表的首元素,原因是_。 (13) 栈s经过运算InitStack(s);Push(s,a);Push(s,b)后,GetTop(S)的值是_。 (15) 元素进入队列的一端是_。 队列出队的一端是_。 已知循环队列sq,在进行进队操作之前要先判断_。,3.4 习 题_ 填空题,(18) 已知循环队列sq,在进行出队操作之前要先判断_。 (19) 循环队列sq存储在数组sq.data0max中,sq满的条件是_。 (20) 循环队列sq空的条件是_。 (21) 循环队列sq存储在数组sq.data0max中,sq.front为max,则存放队列头元素的数组元素是_。 (22) 循环队列sq存储在数组sq.data0max中,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论