c语言数据结构基础课件

在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构11/21/20221DATA1065865姓名学号成绩第十三章

数据结构基础加油啊!本章主要内容:数据结构基本概念数据结构常用算法11/21/20222第十三章

数据结构基础加油啊!本章主要内容:11/21/13.1概述

13.1.1数据结构的基本概念

程序=数据结构+算法（著名的计算机科学家wirth(沃思）提出的表达程序设计实质的公式）例1:书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。线性表11/21/2022313.1概述例1:书目自动检索系统登录号：例1:

英文26个字母表的数据结构是一个线形表，可表示为:B={D,R}D={a,b,c,·······，x,y,z}R={(a,b),(b,c),……，(y,z)}

此例数据元素是简单项。学号姓名成绩9861109张卓1009861107刘忠赏959861103胡孝臣86例2:

学生成绩表（复杂的线性表）数据元素是由若干个数据项组成，如每个学生的情况，称为记录（Record）；由多个记录组成的线性表称为文件（File).11/21/20224例1:英文26个字母表的数据结构是一个线形表，可表示为:树形结构例子——结点间具有分层次的连接关系HBCDEFGAHGFECDBA例2计算机中的目录结构问题树11/21/20225树形结构例子——结点间具有分层次的连接关系HBCDEFGAH1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}图形结构例子——结点间的连结是任意的例3

交通、道路问题的数学模型图11/21/202261423D={1,2,3,4}2通过上述例子可以看出：描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构定义：数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的学科。11/21/20227通过上述例子可以看出：11/21/202271.概念与术语：数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合.11/21/202281.概念与术语：11/21/202282.数据结构研究的三个问题（1）数据的逻辑结构：反映数据之间的逻辑关系。三种基本结构:线性结构:结构中的数据元素存在着线性(一对一)的关系.树形结构:结构中的数据元素存在着层次(一对多)的关系.图形结构:结构中的数据元素存在着任意(多对多)的关系.任何数据结构在逻辑上可描述为Group=（D，R）

其中：D是数据元素的集合，R是D上的关系集合。（2）数据的存储结构：数据在计算机内部的存储方式。

（3）数据的操作：数据的操作即是对数据进行的处理。

11/21/202292.数据结构研究的三个问题（2）数据的存储结构：数据在计1.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储B.链式存储线性表栈队树形结构图形结构数据结构的三个方面反映数据元素之间的逻辑关系数据元素在计算机内部的组织方式一种逻辑结构可以采取不同的存储方式，但必须都反映出要求的逻辑关系。11/21/2022101.数据的逻辑结构2.数据的存储结构3.数元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储把线性表中数据元素依次存放到一组连续的存储单元中。11/21/202211元素n……..元素i……..元素2元素1LoLo+mLo+(1536元素21400元素11346元素3∧元素41345存储地址存储内容指针1345元素1

14001346元素4∧…….……..…….

1400

元素21536…….……..…….1536元素31346

链式存储

h11/21/2022121536元素21400元素11346元素3∧元素4134513.1.2算法的基本概念

1.算法(algorithm)是对特定问题求解步骤的一种描述。算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。可行性：算法的每一步都是能够实现的，即可操作的。输入：算法有零个或多个输入。有输出：算法执行完毕，必须有一个或若干个输出结果。2.“好”算法应达到的目标正确性：对于一切合法输入都能产生满足规格要求的结果。易读性：算法要便于阅读，有助于人们对算法的理解。健壮性：当输入非法数据时，也能正常作出反应和处理。执行时间及占用空间：对相同规模的问题，执行时间短、占用空间少。11/21/20221313.1.2算法的基本概念1.算法(algorithm)

算法的时间复杂度：为便于比较解决同一问题的不同算法，通常以算法中基本操作重复执行的频度作为算法的时间度量标准。记作：T(n)=O(f(n))T(n)是问题规模的函数，O表示数量级随问题规模n的增大，算法执行时间的增长率T(n)和f(n)的增长率相同。简称时间复杂度。应选择算法内重复执行次数最多的基本语句，作为算法执行时间量度。一般情况下是最深层循环内的基本语句。11/21/202214算法的时间复杂度：随问题规模n的增大，例1：x+=5;单个语句的频度为1，则程序段的时间复杂度为T(n)=O(1)例2：两个n×n阶矩阵相乘算法中语句的执行次数

for(i=0;i<n;i++)nfor(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}T(n)=2n3+2n2+n=O(2n3+2n2+n),，T{n}=O{n3}即算法的执行时间与问题规模N的三次方同阶。一般情况下，随n的增大，T(n)的增长较慢的算法为最优算法。11/21/202215例1：x+=5;11/21/202215算法的空间复杂度：算法执行时存储空间需求的度量S(n)=O(f(n))通常只要分析算法在实现时所需的辅助空间单元个数即可。算法的时间的耗费和所占存储空间的耗费是矛盾的，难以兼得。一般情况，常常以算法的执行时间作为算法优劣的主要衡量指标。11/21/202216算法的空间复杂度：11/21/202216

13.2线性表（Linear_List)13.2.1线性表的定义

线性表是n个元素的有限序列，是最常用最简单的数据结构，长度可增长或缩短。它们之间的关系可以排成一个线性序列：

a1，a2，...，ai，...，an线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继在线性表上常用的运算有：初始化、求长度、取元素、定位、插入及删除等。线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。11/21/202217

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

线性表的顺序存储结构——可用C语言中的一维数组来描述.#defineM100/*定义M为常数100，M的值作为数组的最大容量*/。intV[M];/*V是数组的名字，假设数组中的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*mV[０]V[１]V[i]V[m-1]11/21/202220元素1元素2……..元素i……..01i

线性表的顺序…..a2a1an…..ai+1ai01i-1in-1

（1）顺序表的插入运算

在线性表的第i个元素之前插入一个新的元素，先移动，后插入。ai-1…..a2a1alength…ai+1aixai-1…..a2a1

aiai+1…alength

alength……ai+1aix11/21/202221…..a2a1an…..ai+1ai01i-1in-1（1

顺序表的插入算法：intinsq(inti，intx,intV[],intM,int*p）{/*在线性表V中第i个元素之前插入x，i的合法值为1in*/intn,j;n=*p;/*获取表长*/if（n==M)/*M是存储空间的大小，p是指向存储表长的指针变量*/{printf("overflow\n");return(0);}if((i<1)||(i>n+1)){printf("iiserror\n");return(0);}/*i值不合法*/else{for(j=n;j>=i;j--)V[j]=V[j-1];/*插入位置后的元素依次右移*/V[j]=x;/*插入x*/p=++n;/*表长加1,由p返回到函数调用处*/return(1);}}11/21/202222顺序表的插入算法：11/21/202222voidmain(){intM=10,n=4;/*M是数组的大小,n是表中元素个数,即表长*/intresult,k;staticintV[10]={3,5,7,10};/*数组赋初值*/result=insq(2,4,V,M,&n);/*执行函数调用,在第2个元素前插入4*/if(result==1){printf("success!\n");for(k=0;k<n;k++)printf("%d",V[k]);}elseprintf("failure!");}运行结果:success!34571011/21/202223voidmain()11/21/202223（2）顺序表的删除运算intdelsq(inti,intV[],int*p）{/*在线性表V中删除第i个元素*/intn,j;n=*p;if（i<1||i>n）{printf("Thiselementisnotinthelist\n");return(0);}else{for(j=i;j<n;j++)V[j-1]=V[j];/*被删除元素之后的元素左移*/*p=--n;/*表长减1*/return(1);}}算法评价：在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。T(n)=O(n)11/21/202224（2）顺序表的删除运算算法评价：在顺序表中插入或删除一个元素2.线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素。利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。结点 数据域：元素本身信息指针域：指示直接后继的存储位置，最后一个结点的指针域为空特点：插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。

链表的查找只能从头指针开始顺序查找。11/21/2022252.线性表的链式存储结构特点：11/21/202225typedefstructLNode{intdata;structLNode*link;}NODE;NODE*h,*p;链表结点的定义a1a2∧ana3h…..带头结点的线性链表(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).linkp->link表示p指向结点的指针域datalinkP生成一个NODE型新结点：p=(NODE*)malloc(sizeof(NODE));系统回收p结点：free(p)结点中只含一个指针域的链表叫单链表11/21/202226typedefstructLNode链表结点的定4.链表的基本运算(1)建立链表

动态建立如下链表的思想:ha1a2头结点an^…...011/21/2022274.链表的基本运算(1)建立链表ha1a2头结点an程序如下:#include“stdio.h”#include“malloc.h”typedefstructstudent{intnum;floatscore;structstudent*link;}stu;

11/21/202228程序如下:11/21/202228stu*creat(){stu*head;stu*p1,*p2;intn=0;p1=p2=(stu*)malloc(sizeof(stu));printf("inputnumberandscore:");scanf("%d,%f",&p1->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);}11/21/202229stu*creat()11/21/202229voidListInsert_L(NODE*L,inti,intx){/*在带头结点的线性链表L中第i个位置之前插入元素x*/NODE*p=L.*s;intj=0;while(p&&j<i-1){p=p->link;++j}；/*寻找第i-1个结点*/if(!p||j>i-1)return(0);/*插入位置错误*/s=(NODE*)malloc(sizeof(NODE))；/*生成新结点*/s->data=x;s->link=p->link;p->link=s;/*插入到表中*/return(1);}}(2)单链表的插入运算∧anaia1a2ai-1xL……11/21/202230voidListInsert_L(NODE*L,intvoidListDelete(NODE*L,inti,intx){/*在带头结点的线性链表L中,删除第i个元素*/NODE*p=L,*q;intj=0;while(p->link&&j<i-1){p=p->link;++j}；/*寻找第i个结点，并令p指向其前驱*/if(!(p->link)||j>i-1)return(0);/*删除位置错误*/q=p->link;p->link=q->link;free(q);/*删除并释放结点*/return(1);}

（3）单链表的删除运算ai-1a1aiai+1Lpq11/21/202231voidListDelete(NODE*L,inti,（4）线性链表的查找操作设无表头结点的线性链表的头指针为h,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址。NODE*lbcz(NODE*h,intx){NODE*p;p=h;/*p先指向第一个结点*/while(p!=NULL&&p->data!=x)p=p->link;/*p指向下一结点*/return(p);}11/21/202232（4）线性链表的查找操作11/21/202232(5)循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=hhh空表11/21/202233(5)循环链表：首尾相接的链表。hh空表11/21/20213．3栈和队列栈和队列是两种特殊的线性表，它们是运算要受到某些限制的线性表，故也称为限定性的数据结构。a1a2….an进栈出栈栈顶栈底13.3.1栈(Stack)1.栈的定义定义：限定只能在表的一端进行插入和删除的特殊的线性表。特点：后进先出(LIFO/先进后出（FILO)。设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素，其原理示意图为:栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。11/21/20223413．3栈和队列a1a2….an进2.栈的运算：设置一个空栈；插入一个新的栈顶元素；删除栈顶元素；读取栈顶元素。凡是对数据处理具有“后进先出”的特点，都可以用栈来操作。11/21/2022352.栈的运算：凡是对数据处理具有“后进先出”的特点，都可以顺序栈：用顺序存储结构表示的栈。

顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向栈顶的位置。

例：

进栈算法

弹栈算法a1a2a1a2top栈的上溢：栈满时(top=stacksize-1)，还有元素要进栈。栈的下溢：栈空时（top=-1)，还有元素要出栈。11/21/202236顺序栈：用顺序存储结构表示的栈。进栈算法弹栈算法例：设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=-1

10S[4]231010进栈:

top=top+1;s[top]=10top

10

25

30S[4]2310top30出栈:

y=s[top];top=top-1S[4]2310栈空:

top=-1top栈满:top=stacksize-1

10

25

30

40S[4]2310top11/21/202237例：设数组S是一个顺序栈，栈的最大容量stacksize=4·进栈算法#definestatcksize100intpush(ints[],intx,int*ptop){inttop;top=*ptop;if(top==stacksize-1){printf(“overflow”);return(0);}else{*ptop=++top;/*实际栈顶指针加1*/s[top]=x;return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4987654321a10top11/21/202238·进栈算法{通过地址传递，用ptop带回实际栈顶指针出栈算法：intpop(ints[],int*ptop,int*py){inttop;top=*ptop;if(top==-1){printf(“stackempty”);return(0);}else{*py=s[top];/*返回栈顶元素*/--top;*ptop=top;return(1);}

}通过地址传递，用ptop带回实际栈顶指针通过指针变量py带回栈顶元素栈sa2a3a4987654321a10top11/21/202239出栈算法：{通过地址传递，用ptop带回实际栈顶指针通过指3.栈的应用(1)

子程序的嵌套调用r主程序srrrs子程序1rst子程序2rst子程序311/21/2022403.栈的应用r主程序srrrs子程序1rst子程序2rstlongFact(intn){longs;if(n==1)s=1;elses=n*Fact(n-1);return(s);}计算N阶乘的递归函数

(2)

递归算法：

1(n=0,1)n!=n(n-1)！(n>1)11/21/202241longFact(intn)计算N阶乘的递归函数递归调用执行情况如下：主程序(1)输出f(4);

……4f(4);（1）n=4top(2)s=4*f(3)n3f(3);（2）n=3（1）n=4top(3)s=3*f(2)n2f(2);（3）n=2（2）n=3（1）n=4top(4)s=2*f(1)n1（4）n=1（3）n=2（2）n=3（1）n=4topss=3*2*1;(2)3(1)4tops=2*1(3)2(2)3(1)4tops=4*3*2*1(1)4top返回(3)2(2)3(1)4top(4)1结束输出2411/21/202242递归调用执行情况如下：主程序(1)输出f(4);……4队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；13.3.2队列1.队列的定义定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。特点：此种结构称为先进先出（FIFO）表。队尾a1,

a2,

a3,

a4,…………

an-1,

an

队列示意图队头先进先出FIFO11/21/202243队列的主要运算（1）设置一个空队列；13.3.2队列队2.队列的存储结构及运算（1）顺序存储结构(a)线性队列

3210(a)rear=front=-1(队空）e3e4(c)e1,e2出队，e4入队

队满rear=4fronte1e2e3

(b)rearfront(b)e1,e2,e3入队队空时，令rear=front=-1，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置11/21/2022442.队列的存储结构及运算（1）顺序存储结构(a)线性队列存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出当front-1,rear=M-1时，再有元素入队发生溢出——假溢出(b)将头尾连接成一个环，形成循环队列。让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];11/21/202245存在问题(b)将头尾连接成一个环，形成循环队列。11/21012345rearfronte3e4e5012345rearfronte8e7e6e3e4e5012345rearfront初始状态e3,e4,e5出队e6,e7,e8入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front队满、队空判定条件e3e4e5012345rearfronte7e6队满队空11/21/202246012345rearfronte3e4e5012345rea1)循环队列中加入一个元素的算法intEnQueue(intQ[],intx,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==front)return(0);else{rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(1);}}计算出新的队尾11/21/2022471)循环队列中加入一个元素的算法计算出新的队尾11/21/2)循环队列中删除一个元素的算法intDeQueue(intQ[],int*py,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if(rear==front)return(0);else{front=(front+1)%MAX;*py=Q[front];*pf=front;return(1);}}11/21/2022482)循环队列中删除一个元素的算法11/21/202248ana2a1

ana3a2

Q.frontQ.rear删除一个元素添加一个元素e^a1a2anQ.frontQ.rear

（2）链式存储结构（队的容量无法预先估计时采用）Q.frontQ.rear队头队尾Q.rear11/21/202249ana2a1ana3a23.队列的应用：队列的应用非常普遍，凡是符合“先来先服务”原则的问题，都可以采用队列结构来解决。在计算机程序设计中采用很多队列的结构：如：分时操作系统中的作业排队；输入输出缓冲区等都采用队列结构。11/21/2022503.队列的应用：11/21/202250在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构11/21/202251DATA1065865姓名学号成绩第十三章

数据结构基础加油啊!本章主要内容:数据结构基本概念数据结构常用算法11/21/202252第十三章

数据结构基础加油啊!本章主要内容:11/21/13.1概述

13.1.1数据结构的基本概念

程序=数据结构+算法（著名的计算机科学家wirth(沃思）提出的表达程序设计实质的公式）例1:书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。线性表11/21/20225313.1概述例1:书目自动检索系统登录号：例1:

英文26个字母表的数据结构是一个线形表，可表示为:B={D,R}D={a,b,c,·······，x,y,z}R={(a,b),(b,c),……，(y,z)}

此例数据元素是简单项。学号姓名成绩9861109张卓1009861107刘忠赏959861103胡孝臣86例2:

学生成绩表（复杂的线性表）数据元素是由若干个数据项组成，如每个学生的情况，称为记录（Record）；由多个记录组成的线性表称为文件（File).11/21/202254例1:英文26个字母表的数据结构是一个线形表，可表示为:树形结构例子——结点间具有分层次的连接关系HBCDEFGAHGFECDBA例2计算机中的目录结构问题树11/21/202255树形结构例子——结点间具有分层次的连接关系HBCDEFGAH1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}图形结构例子——结点间的连结是任意的例3

交通、道路问题的数学模型图11/21/2022561423D={1,2,3,4}2通过上述例子可以看出：描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构定义：数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的学科。11/21/202257通过上述例子可以看出：11/21/202271.概念与术语：数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合.11/21/2022581.概念与术语：11/21/202282.数据结构研究的三个问题（1）数据的逻辑结构：反映数据之间的逻辑关系。三种基本结构:线性结构:结构中的数据元素存在着线性(一对一)的关系.树形结构:结构中的数据元素存在着层次(一对多)的关系.图形结构:结构中的数据元素存在着任意(多对多)的关系.任何数据结构在逻辑上可描述为Group=（D，R）

其中：D是数据元素的集合，R是D上的关系集合。（2）数据的存储结构：数据在计算机内部的存储方式。

（3）数据的操作：数据的操作即是对数据进行的处理。

11/21/2022592.数据结构研究的三个问题（2）数据的存储结构：数据在计1.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储B.链式存储线性表栈队树形结构图形结构数据结构的三个方面反映数据元素之间的逻辑关系数据元素在计算机内部的组织方式一种逻辑结构可以采取不同的存储方式，但必须都反映出要求的逻辑关系。11/21/2022601.数据的逻辑结构2.数据的存储结构3.数元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储把线性表中数据元素依次存放到一组连续的存储单元中。11/21/202261元素n……..元素i……..元素2元素1LoLo+mLo+(1536元素21400元素11346元素3∧元素41345存储地址存储内容指针1345元素1

14001346元素4∧…….……..…….

1400

元素21536…….……..…….1536元素31346

链式存储

h11/21/2022621536元素21400元素11346元素3∧元素4134513.1.2算法的基本概念

1.算法(algorithm)是对特定问题求解步骤的一种描述。算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。可行性：算法的每一步都是能够实现的，即可操作的。输入：算法有零个或多个输入。有输出：算法执行完毕，必须有一个或若干个输出结果。2.“好”算法应达到的目标正确性：对于一切合法输入都能产生满足规格要求的结果。易读性：算法要便于阅读，有助于人们对算法的理解。健壮性：当输入非法数据时，也能正常作出反应和处理。执行时间及占用空间：对相同规模的问题，执行时间短、占用空间少。11/21/20226313.1.2算法的基本概念1.算法(algorithm)

算法的时间复杂度：为便于比较解决同一问题的不同算法，通常以算法中基本操作重复执行的频度作为算法的时间度量标准。记作：T(n)=O(f(n))T(n)是问题规模的函数，O表示数量级随问题规模n的增大，算法执行时间的增长率T(n)和f(n)的增长率相同。简称时间复杂度。应选择算法内重复执行次数最多的基本语句，作为算法执行时间量度。一般情况下是最深层循环内的基本语句。11/21/202264算法的时间复杂度：随问题规模n的增大，例1：x+=5;单个语句的频度为1，则程序段的时间复杂度为T(n)=O(1)例2：两个n×n阶矩阵相乘算法中语句的执行次数

for(i=0;i<n;i++)nfor(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}T(n)=2n3+2n2+n=O(2n3+2n2+n),，T{n}=O{n3}即算法的执行时间与问题规模N的三次方同阶。一般情况下，随n的增大，T(n)的增长较慢的算法为最优算法。11/21/202265例1：x+=5;11/21/202215算法的空间复杂度：算法执行时存储空间需求的度量S(n)=O(f(n))通常只要分析算法在实现时所需的辅助空间单元个数即可。算法的时间的耗费和所占存储空间的耗费是矛盾的，难以兼得。一般情况，常常以算法的执行时间作为算法优劣的主要衡量指标。11/21/202266算法的空间复杂度：11/21/202216

13.2线性表（Linear_List)13.2.1线性表的定义

线性表是n个元素的有限序列，是最常用最简单的数据结构，长度可增长或缩短。它们之间的关系可以排成一个线性序列：

a1，a2，...，ai，...，an线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继在线性表上常用的运算有：初始化、求长度、取元素、定位、插入及删除等。线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。11/21/202267

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

线性表的顺序存储结构——可用C语言中的一维数组来描述.#defineM100/*定义M为常数100，M的值作为数组的最大容量*/。intV[M];/*V是数组的名字，假设数组中的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*mV[０]V[１]V[i]V[m-1]11/21/202270元素1元素2……..元素i……..01i

线性表的顺序…..a2a1an…..ai+1ai01i-1in-1

（1）顺序表的插入运算

在线性表的第i个元素之前插入一个新的元素，先移动，后插入。ai-1…..a2a1alength…ai+1aixai-1…..a2a1

aiai+1…alength

alength……ai+1aix11/21/202271…..a2a1an…..ai+1ai01i-1in-1（1

顺序表的插入算法：intinsq(inti，intx,intV[],intM,int*p）{/*在线性表V中第i个元素之前插入x，i的合法值为1in*/intn,j;n=*p;/*获取表长*/if（n==M)/*M是存储空间的大小，p是指向存储表长的指针变量*/{printf("overflow\n");return(0);}if((i<1)||(i>n+1)){printf("iiserror\n");return(0);}/*i值不合法*/else{for(j=n;j>=i;j--)V[j]=V[j-1];/*插入位置后的元素依次右移*/V[j]=x;/*插入x*/p=++n;/*表长加1,由p返回到函数调用处*/return(1);}}11/21/202272顺序表的插入算法：11/21/202222voidmain(){intM=10,n=4;/*M是数组的大小,n是表中元素个数,即表长*/intresult,k;staticintV[10]={3,5,7,10};/*数组赋初值*/result=insq(2,4,V,M,&n);/*执行函数调用,在第2个元素前插入4*/if(result==1){printf("success!\n");for(k=0;k<n;k++)printf("%d",V[k]);}elseprintf("failure!");}运行结果:success!34571011/21/202273voidmain()11/21/202223（2）顺序表的删除运算intdelsq(inti,intV[],int*p）{/*在线性表V中删除第i个元素*/intn,j;n=*p;if（i<1||i>n）{printf("Thiselementisnotinthelist\n");return(0);}else{for(j=i;j<n;j++)V[j-1]=V[j];/*被删除元素之后的元素左移*/*p=--n;/*表长减1*/return(1);}}算法评价：在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。T(n)=O(n)11/21/202274（2）顺序表的删除运算算法评价：在顺序表中插入或删除一个元素2.线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素。利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。结点 数据域：元素本身信息指针域：指示直接后继的存储位置，最后一个结点的指针域为空特点：插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。

链表的查找只能从头指针开始顺序查找。11/21/2022752.线性表的链式存储结构特点：11/21/202225typedefstructLNode{intdata;structLNode*link;}NODE;NODE*h,*p;链表结点的定义a1a2∧ana3h…..带头结点的线性链表(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).linkp->link表示p指向结点的指针域datalinkP生成一个NODE型新结点：p=(NODE*)malloc(sizeof(NODE));系统回收p结点：free(p)结点中只含一个指针域的链表叫单链表11/21/202276typedefstructLNode链表结点的定4.链表的基本运算(1)建立链表

动态建立如下链表的思想:ha1a2头结点an^…...011/21/2022774.链表的基本运算(1)建立链表ha1a2头结点an程序如下:#include“stdio.h”#include“malloc.h”typedefstructstudent{intnum;floatscore;structstudent*link;}stu;

11/21/202278程序如下:11/21/202228stu*creat(){stu*head;stu*p1,*p2;intn=0;p1=p2=(stu*)malloc(sizeof(stu));printf("inputnumberandscore:");scanf("%d,%f",&p1->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);}11/21/202279stu*creat()11/21/202229voidListInsert_L(NODE*L,inti,intx){/*在带头结点的线性链表L中第i个位置之前插入元素x*/NODE*p=L.*s;intj=0;while(p&&j<i-1){p=p->link;++j}；/*寻找第i-1个结点*/if(!p||j>i-1)return(0);/*插入位置错误*/s=(NODE*)malloc(sizeof(NODE))；/*生成新结点*/s->data=x;s->link=p->link;p->link=s;/*插入到表中*/return(1);}}(2)单链表的插入运算∧anaia1a2ai-1xL……11/21/202280voidListInsert_L(NODE*L,intvoidListDelete(NODE*L,inti,intx){/*在带头结点的线性链表L中,删除第i个元素*/NODE*p=L,*q;intj=0;while(p->link&&j<i-1){p=p->link;++j}；/*寻找第i个结点，并令p指向其前驱*/if(!(p->link)||j>i-1)return(0);/*删除位置错误*/q=p->link;p->link=q->link;free(q);/*删除并释放结点*/return(1);}

（3）单链表的删除运算ai-1a1aiai+1Lpq11/21/202281voidListDelete(NODE*L,inti,（4）线性链表的查找操作设无表头结点的线性链表的头指针为h,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址。NODE*lbcz(NODE*h,intx){NODE*p;p=h;/*p先指向第一个结点*/while(p!=NULL&&p->data!=x)p=p->link;/*p指向下一结点*/return(p);}11/21/202282（4）线性链表的查找操作11/21/202232(5)循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=hhh空表11/21/202283(5)循环链表：首尾相接的链表。hh空表11/21/20213．3栈和队列栈和队列是两种特殊的线性表，它们是运算要受到某些限制的线性表，故也称为限定性的数据结构。a1a2….an进栈出栈栈顶栈底13.3.1栈(Stack)1.栈的定义定义：限定只能在表的一端进行插入和删除的特殊的线性表。特点：后进先出(LIFO/先进后出（FILO)。设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素，其原理示意图为:栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。11/21/20228413．3栈和队列a1a2….an进2.栈的运算：设置一个空栈；插入一个新的栈顶元素；删除栈顶元素；读取栈顶元素。凡是对数据处理具有“后进先出”的特点，都可以用栈来操作。11/21/2022852.栈的运算：凡是对数据处理具有“后进先出”的特点，都可以顺序栈：用顺序存储结构表示的栈。

顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向栈顶的位置。

例：

进栈算法

弹栈算法a1a2a1a2top栈的上溢：栈满时(top=stacksize-1)，还有元素要进栈。栈的下溢：栈空时（top=-1)，还有元素要出栈。11/21/202286顺序栈：用顺序存储结构表示的栈。进栈算法弹栈算法例：设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=-1

10S[4]231010进栈:

top=top+1;s[top]=10top

10

25

30S[4]2310top30出栈:

y=s[top];top=top-1S[4]2310栈空:

top=-1top栈满:top=stacksize-1

10

25

30

40S[4]2310top11/21/202287例：设数组S是一个顺序栈，栈的最大容量stacksize=4·进栈算法#definestatcksize100intpush(ints[],intx,int*ptop){inttop;top=*ptop;if(top==stacksize-1){printf(“overflow”);return(0);}else{*ptop=++top;/*实际栈顶指针加1*/s[top]=x;return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4987654321a10top11/21/202288·进栈算法{通过地址传递，用ptop带回实际栈顶指针出栈算法：intpop(ints[],int*ptop,int*py){inttop;top=*ptop;if(top==-1){printf(“stackempty”);return(0);}else{*py=s[top];/*返回栈顶元素*/--top;*ptop=top;return(1);}

}通过地址传递，用ptop带回实际栈顶指针通过指针变量py带回栈顶元素栈sa2a3a4987654321a10top11/21/202289出栈算法：{通过地址传递，用ptop带回实际栈顶指针通过指3.栈的应用(1)

子程序的嵌套调用r主程序srrrs子程序1rst子程序2rst子程序311/21/2022903.栈的应用r主程序srrrs子程序1rst子程序2rstlongFact(intn){longs;if(n==1)s=1;elses=n*Fact(n-1);return(s);}计算N阶乘的递归函数