c语言数据结构基础课件.ppt

1、1/6/202311065865姓名姓名 学号学号 成绩成绩 班级班级 李红李红 9761059 95 机机97.6 ABCDEFG1/6/20232第十三章第十三章 数据结构基础数据结构基础加油啊!本章主要内容:数据结构基本概念 数据结构常用算法1/6/20233 13.1.1 概述概述 13.1.1 数据结构的基本概念 程序=数据结构+算法（著名的计算机科学家wirth(沃思）提出的表达程序设计实质的公式）例例1:书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书

2、S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。线性表1/6/20234例例 1:1:英文26个字母表的数据结构是一个线形表，可表示为:B=D,R D=a,b,c,，x,y,z R=(a,b),(b,c),，(y,z)此例数据元素是简单项。学号学号姓名姓名成绩成绩98611099861

3、109张卓张卓10010098611079861107刘忠赏刘忠赏959598611039861103胡孝臣胡孝臣8686例例 2:2:学生成绩表（复杂的线性表）数据元素是由若干个数据项组成，如每个学生的情况，称为记录（Record）；由多个记录组成的线性表称为文件（File).1/6/20235树形结构例子结点间具有分层次的连接关系HBCDEFGAHGFECDBA例2 计算机中的目录结构问题树1/6/202361423 D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)213 D=1,2,3 R=,图形结构例子图形结构例子结点间的连结是任意的结点间的

4、连结是任意的例3 交通、道路问题的数学模型图1/6/20237数据结构定义：1/6/202381.概念与术语：数据（data)所有能输入到计算机中去的描述客观事物的符号数据元素（data element）数据的基本单位，也称节点（node）或记录（record）数据项（data item）有独立含义的数据最小单位，也称域(field)数据结构（data structure)数据元素和数据元素关系的集合.1/6/20239 2.2.数据结构研究的三个问题数据结构研究的三个问题（1 1）数据的逻辑结构：）数据的逻辑结构：反映数据之间的逻辑关系。反映数据之间的逻辑关系。三种基本结构三种基本结构:线性

5、结构线性结构:结构中的数据元素存在着线性结构中的数据元素存在着线性(一对一一对一)的关系的关系.树形结构树形结构:结构中的数据元素存在着层次结构中的数据元素存在着层次(一对多一对多)的关系的关系.图形结构图形结构:结构中的数据元素存在着任意结构中的数据元素存在着任意(多对多多对多)的关系的关系.任何数据结构在逻辑上可描述为任何数据结构在逻辑上可描述为 Group=Group=（D D，R R）其中：其中：D D是数据元素的集合，是数据元素的集合，R R是是D D上的关系集合。上的关系集合。（2 2）数据的存储结构：）数据的存储结构：数据在计算机内部的存储方式。数据在计算机内部的存储方式。（3

6、3）数据的操作：）数据的操作：数据的操作即是对数据进行的处理。数据的操作即是对数据进行的处理。1/6/2023101.数据的逻辑结构数据的逻辑结构 2.数据的存储结构数据的存储结构 3.数据的运算：检索、排序、插入、删除、修改等。数据的运算：检索、排序、插入、删除、修改等。A.线性结构线性结构 B.非线性结构非线性结构A.顺序存储顺序存储 B.链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面反映数据元素反映数据元素之间的逻辑关之间的逻辑关系系数据元素在计算机数据元素在计算机内部的组织方式内部的组织方式1/6/202311元素元素n n.

7、元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺顺序序存存储储把线性表中数据元素依次存放到一把线性表中数据元素依次存放到一组连续的存储单元中。组连续的存储单元中。1/6/2023121536元素元素2 21400元素元素1 11346元素元素3 3元素元素4 41345存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1

8、536 元素元素3 3 1346 1346 链式存储链式存储 h1/6/20231313.1.2 13.1.2 算法的基本概念算法的基本概念 1.算法算法(algorithm)是对特定问题求解步骤的一种描述。是对特定问题求解步骤的一种描述。算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。可行性：算法的每一步都是能够实现的，即可操作的。输 入：算法有零个或多个输入。有输出：算法执行完毕，必须有一个或若干个输出结果。2.“好”算法应达到的目标正确性：对于一切合法输入都能产生满足规格要求的结果。易读性：算法要便于阅读，有助

9、于人们对算法的理解。健壮性：当输入非法数据时，也能正常作出反应和处理。执行时间及占用空间：对相同规模的问题，执行时间短、占用空间少。1/6/202314 算法的时间复杂度算法的时间复杂度：为便于比较解决同一问题的不同算法，通常以算法中基本操作重复执行的频度作为算法的时间度量标准。记作：T(n)=O(f(n)T(n)是问题规模的函数，O表示数量级 随问题规模随问题规模n n的增大，算法执行时间的增长率的增大，算法执行时间的增长率T(n)T(n)和和f(n)f(n)的增长率相同。简称时间复杂度。应选择算法内重复的增长率相同。简称时间复杂度。应选择算法内重复执行次数最多的基本语句，作为算法执行时间量

10、度。一般执行次数最多的基本语句，作为算法执行时间量度。一般情况下是情况下是最深层循环内的基本语句最深层循环内的基本语句。1/6/202315例例1：x+=5;单个语句的频度为单个语句的频度为1，则，则程序段的时间复杂度为程序段的时间复杂度为T(n)=O(1)例例2：两个：两个nn阶矩阵相乘阶矩阵相乘算法中语句的执行次数算法中语句的执行次数for(i=0;in;i+)nfor(j=0;jn;j+)cij=0;for(k=0;kn;k+)cij=cij+aik*bkj;T(n)=2n3+2n2+n=O(2n3+2n2+n),，Tn=On3即算法的执行时间与问题规模即算法的执行时间与问题规模N的三次

11、方同阶。的三次方同阶。一般情况下，随一般情况下，随n的增大，的增大，T(n)的增长较慢的算法为最优的增长较慢的算法为最优算法。算法。1/6/202316算法的空间复杂度：算法的空间复杂度：算法执行时存储空间需求的度量算法执行时存储空间需求的度量S(n)=O(f(n)通常只要分析算法在实现时所需的辅助空间单元个通常只要分析算法在实现时所需的辅助空间单元个数即可。数即可。算法的时间的耗费和所占存储空间的耗费是矛盾的，算法的时间的耗费和所占存储空间的耗费是矛盾的，难以兼得。难以兼得。一般情况，常常以算法的执行时间作为算法优劣的一般情况，常常以算法的执行时间作为算法优劣的主要衡量指标。主要衡量指标。1

12、/6/2023171313.2.2 线性表（线性表（Linear_List)Linear_List)13.2.1 13.2.1 线性表的定义线性表的定义 线性表是n个元素的有限序列，是最常用最简单的数据结构，长度可增长或缩短。它们之间的关系可以排成一个线性序列：a1，a2，.，ai，.，an线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继在线性表上常用的运算有：初始化、求长度、取元素、定位、插入及删除等。1/6/20231813.

13、2.2 线性表的存储结构及其运算1.线性表的顺序存储结构特点：把线性表中数据元素依次存放到一组连续的存储单元中，每个数据元素对应一个存储单元。线性表中数据元素类型一致，占用相同大小的存储单元。存储空间利用率高。做插入、删除时需移动大量元素。空间估计不明时，按最大空间分配。1/6/202319元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址内存状态内存状态Loc(元素元素i)=Lo+（i-1)*m顺序存储结构示意图：顺序存储结构示意图：1/6/202320元素元素1 1元素元素2 2.元素元素i i.01i 线性表的

14、顺序存储结构线性表的顺序存储结构可用可用C C语言中的一维数组来描述语言中的一维数组来描述.#define M 100 /*定义M为常数100，M的值作为数组的最大容量*/。int VM;/*V是数组的名字，假设数组中的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*mVVViVm-11/6/202321.a2a1an.ai+1ai01i-1in-1（1 1）顺序表的插入运算）顺序表的插入运算 在线性表的第在线性表的第i i个元素之前插入一个新的元素，先移个元素之前插入一个新的元素，先移动，后插入。动，后插入。ai-1.a2a1alengthai+1ai

15、 xai-1.a2a1 aiai+1alength alength ai+1ai x1/6/202322 顺序表的插入算法：顺序表的插入算法：int insq(int i，int x,int V,int M,int*p）/*在线性表V中第i 个元素之前插入x，i 的合法值为 1 i n */int n,j;n=*p;/*获取表长*/if（n=M)/*M是存储空间的大小，p 是指向存储表长的指针变量*/printf(overflow n);return(0);if(in+1)printf(i is error n);return(0);/*i值不合法*/else for(j=n;j=i;j-)V

16、j=Vj-1;/*插入位置后的元素依次右移*/Vj=x;/*插入x*/p=+n;/*表长加1,由p返回到函数调用处*/return(1);1/6/202323void main()int M=10,n=4;/*M是数组的大小,n是表中元素个数,即表长*/int result,k;static int V10=3,5,7,10;/*数组赋初值*/result=insq(2,4,V,M,&n);/*执行函数调用,在第2个元素前插入4*/if(result=1)printf(success!n);for(k=0;kn;k+)printf(%d,Vk);else printf(failure!);运行

17、结果运行结果:success!3 4 5 7 101/6/202324（2 2）顺序表的删除运算）顺序表的删除运算int delsq(int i,int V,int*p）/*在线性表V中删除第i 个元素*/int n,j;n=*p;if（in）printf(This element is not in the list n);return(0);else for(j=i;jdata表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域datalink生成一个NODE型新结点：p=(NODE*)malloc(sizeof(NODE);系统回收p结点：free(p)结点中只含一

18、个指针域的链表叫单链表1/6/2023274.链表的基本运算(1)建立链表 动态建立如下链表的思想:ha1a2头结点an .01/6/202328程序如下程序如下:#include“stdio.h”#include“malloc.h”typedefstructstudentintnum;floatscore;structstudent*link;stu;1/6/202329stu*creat()stu*head;stu*p1,*p2;intn=0;p1=p2=(stu*)malloc(sizeof(stu);printf(inputnumberandscore:);scanf(%d,%f,&p

19、1-num1,&p1-score);head=NULL;while(p1-num!=0)n=n+1;if(n=1)head=p1;elsep2-link=p1;p2=p1;p1=(stu*)malloc(sizeof(stu);scanf(%d,%f,&p1-num,&p1-score);p2-link=NULL;return(head);1/6/202330voidListInsert_L(NODE*L,inti,intx)/*在带头结点的线性链表在带头结点的线性链表L中第中第i个位置之前插入元素个位置之前插入元素x*/NODE*p=L.*s;intj=0;while(p&jlink;+j；

20、/*寻找第寻找第i-1个结点个结点*/if(!p|ji-1)return(0);/*插入位置错误插入位置错误*/s=(NODE*)malloc(sizeof(NODE)；/*生成新结点生成新结点*/s-data=x;s-link=p-link;p-link=s;/*插入到表中插入到表中*/return(1);(2)(2)单链表的插入运算单链表的插入运算anaia1a2ai-1xL1/6/202331voidListDelete(NODE*L,inti,intx)/*在带头结点的线性链表在带头结点的线性链表L中中,删除第删除第i个元素个元素*/NODE*p=L,*q;intj=0;while(p

21、-link&jlink;+j；/*寻找第寻找第i个结点，并令个结点，并令p指向其前驱指向其前驱*/if(!(p-link)|ji-1)return(0);/*删除位置错误删除位置错误*/q=p-link;p-link=q-link;free(q);/*删除并释放结点删除并释放结点*/return(1);（3）单链表的删除运算）单链表的删除运算ai-1a1aiai+1Lpq1/6/202332（4 4）线性链表的查找操作）线性链表的查找操作 设无表头结点的线性链表的头指针为设无表头结点的线性链表的头指针为h,h,沿着链沿着链表的开始往后找结点表的开始往后找结点x x，若找到，则返回该结点在链，若

22、找到，则返回该结点在链表中的位置，否则返回空地址。表中的位置，否则返回空地址。NODE*lbcz(NODE*h,int x)NODE*p;p=h;/*p先指向第一个结点*/while(p!=NULL&p-data!=x)p=p-link;/*p指向下一结点 */return(p);1/6/202333(5)(5)循环链表：首尾相接的链表。循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。均可找到其它结点。v操作与单链表基本一致,循环条件不同l单链表p或p-link=NULLl循环链表p或p-lin

23、k=hhh空表1/6/202334 13 133 3 栈和队列栈和队列栈和队列栈和队列是两种特殊的线性表，它们是运算要受到某些限制的线性表，故也称为限定性的数据结构限定性的数据结构。a1a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底13.3.1 13.3.1 栈栈 (Stack)(Stack)1.1.栈的定义栈的定义定义：定义：限定只能在表的一端进行插入和删除的特殊的线性表。限定只能在表的一端进行插入和删除的特殊的线性表。特点：特点：后进先出后进先出(LIFO/(LIFO/先进后出先进后出（FILO)FILO)。设栈设栈s=s=（a a1 1，a a2 2，.,a.,ai i，.，a an n），

24、其中其中a a1 1是栈底元素，是栈底元素，a an n是栈顶元素，其原理示意图为是栈顶元素，其原理示意图为:栈顶（栈顶（top)top)：允许插入和删除的一端；：允许插入和删除的一端；栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。1/6/2023352.2.栈的运算：栈的运算：设置一个空栈；插入一个新的栈顶元素；删除栈顶元素；读取栈顶元素。凡是对数据处理具有“后进先出”的特点，都可以用栈来操作。1/6/202336 顺序栈：用顺序存储结构表示的栈。顺序栈：用顺序存储结构表示的栈。顺序栈用一组连续的存储单元存顺序栈用一组连续的存储单元存放自栈底到栈

25、顶的数据元素，一般用一放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量维数组表示，设置一个简单变量toptop指指示栈顶位置，称为示栈顶位置，称为栈顶指针栈顶指针，它始终指它始终指向栈顶的位置。向栈顶的位置。例：例：进栈算法进栈算法 弹栈算法弹栈算法 a1a2a1a2 top栈的上溢：栈满时栈的上溢：栈满时(top=stacksize-1)(top=stacksize-1)，还有元素要进栈。，还有元素要进栈。栈的下溢：栈空时（栈的下溢：栈空时（top=-1)top=-1)，还有元素要出栈。，还有元素要出栈。1/6/202337例：设数组例：设数组S S是一个顺序栈，栈的最大容量是

26、一个顺序栈，栈的最大容量stacksize=4 stacksize=4，初始状，初始状态态 top=-1 10S4231010进栈进栈:top=top+1;stop=10top 10 25 30S42310top30出栈出栈:y=stop;top=top-1S42310栈空栈空:top=-1top栈满栈满:top=stacksize-1 10 25 30 40S42310top1/6/202338 进栈算法进栈算法#define statcksize 100int push(int s,int x,int*ptop)int top;top=*ptop;if(top=stacksize-1)pr

27、intf(“overflow”);return(0);else*ptop=+top;/*实际栈顶指针加1*/stop=x;return(1);通过地址传递，用通过地址传递，用ptop带回实际栈顶指带回实际栈顶指针针a2a3a4987654321a10top1/6/202339出栈算法：出栈算法：int pop(int s,int*ptop,int*py)int top;top=*ptop;if(top=-1)printf(“stack empty”);return(0);else*py=stop;/*返回栈顶元素*/-top;*ptop=top;return(1);通过地址传递，用通过地址传递

28、，用ptop带回实际栈顶指带回实际栈顶指针针通过指针变量通过指针变量py带回栈顶元素带回栈顶元素栈栈 sa2a3a4987654321a10top1/6/2023403.3.栈的应用栈的应用 (1)(1)子程序的嵌套调用子程序的嵌套调用r主程序主程序srrrs子程序子程序1rst子程序子程序2rst子程序子程序31/6/202341long Fact(int n)long s;if(n=1)s=1;else s=n*Fact(n-1);return(s);计算计算N N阶乘的递归函数阶乘的递归函数 (2)(2)递归算法：递归算法：1 (n=0,1)n!=n(n-1)！(n1)1/6/20234

29、2递归调用执行情况如下：主程序主程序(1)输出输出f(4);4 f(4);（1）n=4top(2)s=4*f(3)n3 f(3);（2）n=3 （1）n=4 top(3)s=3*f(2)n2 f(2);（3）n=2 （2）n=3 （1）n=4 top(4)s=2*f(1)n1（4）n=1 （3）n=2 （2）n=3 （1）n=4 tops s=3*2*1;(2)3(1)4top s=2*1(3)2(2)3(1)4top s=4*3*2*1 (1)4top返回返回(3)2(2)3(1)4top(4)1结束结束输出输出241/6/202343队列的主要运算队列的主要运算（1 1）设置一个空队列；）

30、设置一个空队列；（2 2）插入一个新的队尾元素，称为进队；）插入一个新的队尾元素，称为进队；（3 3）删除队头元素，称为出队；）删除队头元素，称为出队；（4 4）读取队头元素；）读取队头元素；13.3.2 13.3.2 队列队列1.1.队列的定义队列的定义定义：定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。特点：此种结构称为先进先出（先进先出（FIFOFIFO）表）表。队尾 a1 ,a2 ,a3 ,a4 ,an-1 ,an 队 列 示 意 图队头先 进 先先 进 先出出FIFO1/6/2023442.2.队列的存储结构及运算队列的存储结构及运算（1 1）顺

31、序存储结构）顺序存储结构(a)(a)线性队列线性队列 3 2 1 0 (a)rear=front=-1(队空）队空）e3e4 (c)e1,e2出队，出队，e4入队入队 队队 满满rear=4fronte1e2e3 (b)rearfront(b)e1,e2,e3入队入队队空时，队空时，令令rear=front=-1，当有当有新元素入队时，尾指针加新元素入队时，尾指针加1，当有元，当有元素出队时，头指针加素出队时，头指针加1。故在非空队。故在非空队列中，列中，头指针头指针始终指向始终指向队头元素前一队头元素前一个位置个位置，而，而尾指针尾指针始终指向始终指向队尾元素队尾元素的位置的位置1/6/20

32、2345 存在问题设数组维数为M，则：v当front=-1,rear=M-1时，再有元素入队发生溢出真溢出v当front-1,rear=M-1时，再有元素入队发生溢出假溢出(b)(b)将头尾连接成一个环，形成循环队列。将头尾连接成一个环，形成循环队列。让sq0接在sqM-1之后，若rear+1=M,则令rear=0;实现：利用“模”运算 入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;1/6/202346012345rearfronte3e4e5012345rearfronte8e7e6e3e4e5012345rearfro

33、nt初始状态e3,e4,e5出队e6,e7,e8入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front队满、队空判定条件e3e4e5012345rearfronte7e61/6/2023471)循环队列中加入一个元素的算法循环队列中加入一个元素的算法 int EnQueue(int Q,int x,int*pf,int*pr)int front,rear;front=*pf;rear=*pr;if(rear+1)%MAX=front)return(0);else

34、 rear=(rear+1)%MAX;Qrear=x;*pr=rear;return(1);计算出新的队尾计算出新的队尾1/6/202348 2)循环队列中删除一个元素的算法循环队列中删除一个元素的算法int DeQueue(int Q,int*py,int*pf,int*pr)int front,rear;front=*pf;rear=*pr;if(rear=front)return(0);else front=(front+1)%MAX;*py=Qfront;*pf=front;return(1);1/6/202349 an a2 a1 an a3 a2 Q.frontQ.rear 删删 除除 一个元素一个元素 添加添加 一个元素一个元素e a1 a2 anQ.frontQ.rear （2）链式存储结构链式存储结构（队的容量无法预先估计时采用）（队的容量无法预先估计时采用）Q.frontQ.rear队头队尾Q.rear1/6/2023503.3.队列队列 的应用：的应用：队列的应用非常普遍，凡是符合“先来先服务”原则的问题，都可以采用队列结构来解决。在计算机程序设计中采用很多队列的结构：如：分时操作系统中的作业排队；输入输出缓冲区等都采用队列结构。