数据结构(C语言)

广东交通职业基数学院计算机系课件设计数据结构〔C语言〕DATASTRUCTURE

教材数据结构〔C语言〕曲建民刘元红郑陶然清华大学出版社参考教材1数据结构〔C语言版〕严蔚敏吴伟民清华大学出版社2数据结构题集〔C语言版〕严蔚敏吴伟民清华大学出版社课程特点及课时分配难度大综合性强必须下苦功学习课程说明考试每周4节，共20周评分标准：平时成绩20％〔包括考勤、课堂答复以下问题等〕、期中成绩30％，期末成绩50％教学内容第一章绪论第二章线性表第三章栈和队列第四章数组和串第五章树

第六章图第七章内部排序第八章查找第九章文件第一章绪论主要知识点

数据处理的种类和能力

数据数值数据：数(整数,实数)非数值数据：字符字符串文字图形图象声音数据：客观对象的符号表示数学中的整数、实数，

课程名，地名、书名1.1什么是数据结构

数据结构要解决的问题

数值问题与非数值问题1〕数值问题例1：游泳池的长len和宽wide，求面积area◆设计求解问题的方法◆编程main(){ intlen,wide,area;

scanf(“%d%d%\n〞,&l,&w);

area=len*wide;

printf(“area=%d〞,area);}◆建模型：

问题涉及的对象：游泳池的长len宽wide，面积area；

对象之间的关系：area=len

wide1.1什么是数据结构

学号姓名性别出生日期籍贯入学成绩所在班级00201

杨润生男82/06/01广州56100计算机2

00102石磊男83/12/21汕头51200计算机1

00202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机32〕非数值问题例2某级学生情况,要求分班按入学成绩排列顺序。在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性模型。1.1什么是数据结构城市间交通网问题1.1什么是数据结构数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。本课程讨论的问题：应用中常用的几种数据间的结构关系，及如何表示,如何存储，如何处理。1.1什么是数据结构数据：客观对象的符号表示。例如：学号，姓名，班名都是数据。数据元素：数据的根本单位。相当于“记录〞,在计算机程序中通常作为一个整体考虑和处理数据项:相当于记录的“域〞,是数据的不可分割的最小单位。如：学号数据对象：性质相同的数据元素的集合.例如:所有班名相同的记录集合数据结构：是相互间存在关系的数据元素集合。对每种数据结构，主要讨论如下两方面的问题：1〕数据的逻辑结构，数据结构的根本操作；

2〕数据的存储结构，数据结构根本操作的实现；数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的根本操作：指对数据结构的加工处理数据的存储结构(物理结构)：数据结构在计算机内存中的表示数据结构根本操作的实现：根本操作在计算机上的实现〔方法)数据的逻辑结构通常有四种根本结构：集合线性结构树型结构图结构一、运算加工型运算插入运算删除运算更新运算应用型运算查找运算读取运算1.3运算、算法和算法分析二、算法及其描述

算法是对求解某个问题的步骤的一种描述方法或操作序列。算法的根本特征：

1〕输入：0个或多个输入；

2〕输出：1个或多个输出；

3〕有穷性：算法必须在有限步内结束；

4〕确定性：组成算法的操作必须清晰无二义性。

5〕可行性：组成算法的操作必须能够在计算机上实现。求两个正整数m，n中的最大数MAX的算法〔1〕假设m>n那么max=m

〔2〕假设m<=n那么max=n例1.3运算、算法和算法分析描述算法的书写规那么所有算法均以函数形式给出,算法的输入数据来自参数表参数表的参数在算法之前均进行类型说明有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明1.3运算、算法和算法分析评价算法标准算法的正确性，易读性，可维护性，健壮性，高效率等。算法时间复杂度T〔n〕

本课程采用以求解问题的根本操作的执行次数作为算法时间的度量算法的空间复杂度S(n)一个算法所需要辅助存储空间的多少为空间复杂度O〔n3〕称为矩阵相乘算法时间复杂度；O〔n3〕表示矩阵相乘算法执行时间与n3成正比,即O〔n3〕与n3同一数量级；n阶矩阵相乘的算法For(i=1;i<=n;i++)

For(j=1;j<=n;j++){c[i][j]=0;

For(k=1;k<=n;k++)

c[i][j]+=a[i][k]*b[k][j]}

乘法加法执行次数均为n3

例1.3运算、算法和算法分析有些算法，根本操作执行次数与问题的输入数据有关，这时可考虑

〔1〕算法平均时间复杂度

〔2〕算法在最坏情况下的时间复杂度算法的时间复杂度一般来说，设算法中根本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作：

T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。1.3运算、算法和算法分析算法的时间复杂度为O(N3)

100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支.写算法输出各种组合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)printf(“%d,%d,%d\n%”,i,j,k);

}

}例1.3运算、算法和算法分析2算法空间复杂度

在本课程中，用执行算法所需的辅助空间的大小作为算法所需空间的度量。

设执行算法所需的辅助空间是问题规模n的某个函数g(n),那么算法空间复杂度记作：S〔n〕=O(g(n))表示算法辅助空间的增长率与g(n)的增长率相同1.3运算、算法和算法分析计算解法1先计算x的幂,存于power[]中,再分别乘以相应的系数#defineN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];

for(f=0,i=0;i<=N;i++)f=f+coef[i]*power[i];return(f);}1.3运算、算法和算法分析例问题规模为n,算法时间复杂度:O(n)空间复杂度：O(N)解法2#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;inti;for(f=coef[n],i=n-1;i>=0;i--)f=f*x+coef[i];return(f);}时间复杂度为O(n).空间复杂度为O(1)1.3运算、算法和算法分析第二章线性表2.1线性表的定义和根本运算2.2线性表的顺序存储结构2.3线性表的链式存储结构2.3.1单链表

2.3.2循环链表

2.3.3双向链表2.4线性表的应用举例主要内容第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个〞的数据元素存在唯一的一个被称作“最后一个〞的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继2.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例英文字母表〔A,B,C,…..Z)是一个线性表数据元素特征：元素个数n—表长度，n=0空表1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项2.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];

备用空间数据元素不是简单类型时,可定义结构体数组动态申请和释放内存Datatype*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);插入定义：线性表的插入是指在第I〔1in+1〕个元素之前插入一个新的数据元素x，使长度为n的线性表

变成长度为n+1的线性表需将第i至第n共〔n-i+1)个元素后移Ch2_1.c内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，那么在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：算法删除定义：线性表的删除是指将第i〔1in〕个元素删除，使长度为n的线性表

变成长度为n-1的线性表需将第i+1至第n共〔n-i)个元素前移Ch2_2.c内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2算法评价设Qi是删除第i个元素的概率，那么在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低算法顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点 数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针实现typedefstructnode{

datatype

data;structnode

*link;}JD;JD*h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).data

p->data表示p指向结点的数据域(*p).link

p->link表示p指向结点的指针域生成一个JD型新结点：p=(JD*)malloc(sizeof(JD));系统回收p结点：free(p)2.3.1线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^单链表的根本运算查找：查找单链表中是否存在结点X，假设有那么返回指向X结点的指针；否那么返回NULL算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为npabxs算法评价插入：在线性表两个数据元素a和b间插入x，p指向as->link=p->link;p->link=s;算法描述算法评价算法描述pabc算法评价删除：单链表中删除b，设p指向ap->link=p->link->link;动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法描述算法评价h头结点an^0h头结点an-10an^a2…...h头结点an-10an^ha1a2头结点an^…...0Ch2_3.ch头结点0^单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表根本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=Hhh空表双向链表〔doublelinkedlist〕单链表具有单向性的缺点结点定义typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;bcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}删除算法描述算法评价：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入1循环链表的概念

循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2循环链表图示(a)非空表〔b〕空表headheada1an2.3.2循环链表单向循环链表说明·在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；·循环链表与线性链表操作的主要差异是算法中循环结束的条件不是p或p->link是否为NULL,而是它们是否等于首指针；

·对循环链表，有时不给出头指针，而是给出尾指针aa1an给出尾指针的循环链表2.3.2循环链表baa1anbb1bnaa1anb1bnqqppp=a->link;q=b->link;a->link=q->link;b->link=p;free(q);2.3.2循环链表1双向链表的概念

(a)结点图示数据域指针域指针域结点存储数据元素data存储后继结点的地址next存储前趋结点的地址prior

双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。2.3.3双向链表2双向链表图示head

(b)空的双向循环链表（c）非空的双向循环链表headabtypestructdulnode*pointer;Typestructdulnode{datatypedata;pointerprior,next;}dulnode;2.3.3双向链表在双向链表中删除结点时指针变化情况在双向链表中插入一个结点时指针的变化情况pai-1x①②③④aipaiai+1①②ai-13、双向链表的根本操作算法2.3.3双向链表p1〕插入操作算法(在p所指结点之后插入q结点的过程)

q=(NODE*)malloc(sizeof(NODE));q->data=x;q->rlink=p->rlink;q->llink=p;p->rlink=q;(q->rlink)->llink=q;2.3.3双向链表2〕删除操作算法(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;free(p);aiai+1p①②ai-12.3.3双向链表2.4线性表的应用举例一元多项式的表示及相加一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表单链表的结点定义typedefstructnode{intcoef,exp;structnode*next;}JD;coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多项式相加设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p->exp与q->expp->exp<q->exp:p结点是和多项式中的一项p后移,q不动p->exp>q->exp:q结点是和多项式中的一项将q插在p之前,q后移,p不动p->exp=q->exp:系数相加0：从A表中删去p,释放p,q，p,q后移

0：修改p系数域,释放q，p,q后移直到p或q为NULL若q==NULL，结束若p==NULL，将B中剩余部分连到A上即可运算规那么q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^Ch2_7.c算法描述数据结构第三章栈和队列主要内容

栈的定义栈的存储结构及其运算的实现栈是限定仅能在表尾一端进行插入、删除操作的线性表〔a1,a2,...,ai-1,ai,ai+1,…,an〕插入删除一

什么是栈3.1.1栈的定义第一个进栈的元素在栈底，

最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。不含元素的栈称为空栈。出栈Pop进栈Push栈顶栈底二.栈的逻辑结构topbottom空栈topbottoman...a2a1bottomtopbottomtopAABCDEAB

栈操作图示A进栈

BCDE进栈EDC出栈CDEtoptoptop栈的特点后进先出LIFO入栈与出栈topbottomtopbottomtoptoptop思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA如果是4个元素，那么它不可能的出栈序列有哪些？可能的出栈序列：

12431324134221342143231424313241321434214321不可能出现的出栈序列：

2413312434124123423142134312栈是一种线性表，它的特点是A。设用一维数组A[1，…，n]来表示一个栈，令A[n]为栈底。用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入〔PUSH〕一个新元素时，变量T的值B，从栈中弹出〔POP〕一个元素时，变量T的值C。设栈空时，有输入序列a,b,c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素序列是D，变量T的值是E。A：1〕先进先出2)后进先出3〕进优于出4〕出优于进5〕随机进出B、C：1〕加12〕减13〕不变4〕清05〕加26〕减2D：1〕a,b 2〕b,c3〕c,a4〕b,a5〕c,b6〕a,c E：1〕n+1 2〕n+23〕n4〕n-15〕n-2水平考试试题设有四个数据元素a1,a2,a3和a4，对它们进行栈操作。在进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈的初始状态都是空。现要进行栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B经操作后，最后在栈中的元素还有C个。供选择的答案A：1〕a12〕a23〕a3 4〕a4B：1〕a12〕a23〕a3 4〕a4 C：1〕12〕23〕3 4〕0水平考试试题栈属于加了限制条件的线性结构；栈是后进先出的线性表；进栈和出栈只能从栈的一个端点进行；栈中的元素个数可以是0，此时是空栈；栈的元素的个数是可以变化的，可以是多个，但不能是无穷多个；每个栈中的元素的类型相同.栈的特性栈的应用实现数制转换实现函数的递归行编辑：接受用户从终端输入的程序或数据，并存入用户的数据区表达式求值：一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器那么应该能分析表达式并计算出结果Flash演示三栈的根本操作

初始化IniStack(S):构造一个空栈S，准备存放数据；进栈操作Push(S,x)：将数据元素x插入栈S，使x成为S的栈顶元素；出栈操作Pop(S)：当栈不空时返回栈顶元素为该函数的值，然后删除栈顶元素；取栈顶元素GetTop(S)：当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变；判栈空EmptyStack(S)：假设S为空栈那么该函数值为1，否那么为0。一、栈的顺序存储结构用一个一维数组和一个整型变量来实现。structstack{datatypearray[maxlen];inttop;}栈数组array[maxlen]用来存放栈中所有元素；整型变量top的整数值表示栈顶元素在数组array中的位置，也称为栈顶指针。3.1.2栈的存储结构及其运算的实现约定栈顶指针指向向栈顶元素的位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？？顺序栈的图示topMAX-1nn-1n-210anan-1a2a1栈空：栈满：Top=-1Top=maxlen-11)初始化栈viodinitstack(structstacks){s.top=-1;}

MAX-1nn-1n-210建立空栈top2)进栈操作viodPush(structstacks,datatypex){s.top=s.top+1;s.array[top]=x；}

MAX-1nn-1n-210anan-1a2a1x进栈前topx进栈后MAX-1nn-1n-210topxanan-1a2a13〕出栈操作intpop(structstacks)

{return(array[s.top]);s.top--;}

出栈操作前MAX-1nn-1n-210anan-1a2a1top

出栈操作后MAX-1nn-1n-210anan-1a2a1top栈在运算过程中可能发生“溢出〞现象：上溢下溢topMAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210top2〕进栈操作viodPush〔structstacks,datatypex〕{

s.top=s.top+1;s.array[top]=x；

}if〔s.top=MAXlen-1〕error(“栈满〞)else{}3〕出栈操作intpop〔structstacks〕

{return〔array[s.top]〕;s.top－－;}if〔s.top==-1〕Error〔“emptystack〞〕；else{}顺序栈的缺乏：存在栈满以后就不能再进栈的问题〔这是因为用了定长的数组存储栈的元素〕解决方法：使用链式存储结构。二、栈的链式存储和实现栈的链式存储结构，也称链栈。其各结点的结构与单链表中的结点结构完全相同。如下图：在前面学习了线性链表的插入删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法结点结构定义：Typedefstructnode{elemtypedata;structnode*next;}node,*pointer;Datanexts栈顶（单链表的表头）栈底an-1a1an(1)初始化栈Voidinitstack〔pointers〕{s=null;}^sDatanexts栈顶栈底an-1a1anDatanext栈顶栈底an-1a1an

xps进栈前进栈后(2)进栈进栈算法Voidpush(pointers,datatypex){p=(pointer*)malloc(sizeof(node));p->data=x;p->next=s->next;s->next=p;}出栈前出栈后Datanext栈顶栈底an-1a1ansDatanextp栈顶栈底an-1a1an

xs

(3)出栈出栈算法Datatypepop(pointers){if(s->next==null)return(null);else{p=s->next;x=p->data;s->next=p->next;free(p);return(x);}}3.2.1队列的定义队列是限定仅能在表头进行删除，表尾进行插入的线性表〔a1,a2,...,ai-1,ai,ai+1,…,an〕插入删除3.2队列

a1a2a3……an入队列队头队尾出队列队列的示意图队列的特点先进先出说明：第一个入队的元素在队头，

最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素3.2队列rearfrontJ1J2rearfrontJ2〔a)空队列(b)J1,J2相继入队列(c)J1出队(d)J3,J4和J5相继入队之后,J2出队rearfront-101234rearfrontJ5J4J3front,rear均为整数用箭头指示只是为了直观又有J6入队,怎么办？

？3.2队列3.2.2队列的根本操作1〕初始化操作initQueue(Q)：建立一个空队列Q，准备存放数据；2〕入队操作enQueue(Q,x)：将数据x插入到队列Q的队尾，队列的长度加1；

3〕出队操作outQueue(Q)：当队列为空时，返回队列头元素的值，同时删除队列头元素，队列的长度减1；4〕取队头元素操作GetQueue(Q)：当队列为空时，返回队列头元素的值，但不删除队列头元素；

5〕判空操作：假设队列为空，那么返回的值为1，否那么为0。3.2队列3.2.3队列的存储结构及其根本运算的实现1.链式存储结构3.2队列frontrear∧空链队列a1∧fronta2∧链队列图示structnode//链队列结点的类型定义

{intdata;

structnode*link;};typedefstructnodeNODENODE*front,*rear;1〕进队列运算Voidaddqlink(intx){NODE*p;p=(NODE*)malloc(sizeof(NODE));p->data=x;p->link=NULL;rear->link=p;rear=p;}3.2队列2〕出队列运算NODE*deleqlink(){NODE*p;if(front==rear)return(NULL);p=front->link;front->link=p->link;if(front->link==NULL)rear=front;return(p);}3.2队列3〕队列的应用1〕解决计算机主机与外设不匹配的问题；

2〕解决由于多用户引起的资源竞争问题；3〕离散事件的模拟----模拟实际应用中的各种排队现象；

4〕用于处理程序中具有先进先出特征的过程；在操作系统课程中会讲到3.2队列2.顺序存储结构将front和rear两个整型变量作为c语言结构体的两个成员，该结构体定义如下：Structsq_queue{Datatypedata[maxlen];Intfront,rear;}3.2队列1)初始化运算initqueue〔structsq_queuesq〕得到一个长度为maxsize的空队列sq，此时sq->front=0;sq->rear=0.2)进队列运算enqueue〔structsq_queuesq,datatypex)sq->rear=sq->rear+1,sq->rear.data=x3)出队列运算outqueue〔structsq_queuesq〕sq->front=sq->front-14)读队列头元素运算gethead(structsq_queuesq〕返回的函数值为sq->rear.data,sq队列没有改变5〕判断队列是否是空emptyqueue(structsq_queuesq〕3.2队列3.循环队列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b)队空(c)队满队空、队满都有front=rear如何判断循环队列队空、队满？

？J7rear3.2队列有两种方法：

1〕另设一个标志位以区分队空、队满。

2〕少用一个存储单元，队满条件:front=rear+1;front540312J6J7J8J4J5〔d〕rear3.2队列1〕初始化操作功能：建一个空队列Q；算法：Intqueue[MAX];Intfront,rear;intInitQueue_Sq(){

//构造一个空队列Q

front=0;rear=0;

Return(1)}循环队列的根本操作算法frontrear540312建一个空队列Q3.2队列2〕入队操作功能：将元素x插入队尾frontrear540312J1J3J2xfrontrear540312J1J3J2元素x入队前元素x入队后3.2队列求余运算intinsert_queue(intx)/*入队列*/{if((rear+1)%MAX==front)return(0);rear=(rear+1)%MAX;queue[rear]=x;return(1);}3〕出队操作功能：删除队头元素；

frontrear540312J1J3J2出队操作前frontrear540312J1J3J2出队操作后3.2队列intdel_queue()/*出队列*/

{if(rear==front)return(0);

front=(front+1)%MAX;

return(queue[front]);

}小结和作业作业:课后习题1、2、3实训题：参见://第四章数组和串主要内容4.1数组4.1.1数组的概念和运算4.1.2数组的顺序存储和访问4.1.3矩阵的压缩存储4.2串4.2.1串的根本概念4.2.2串的根本运算4.2.3串的存储结构4.1.1数组的概念运算数组是由一组个数固定，类型相同的数据元素组成阵列。以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1在行关系中aij直接前趋是aij-1aij直接后继是aij+1在列关系中aij直接前趋是ai-1jaij直接后继是ai+1j4.1数组 二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表 A=〔0,1,2,3,4,……,p) 其中每一个数据元素j是一个列向量的线性表 j=〔a0j,a1j,a2j,a3j,……,am-1j) 或i是一个行向量的线性表i=〔ai0,ai1,ai2,ai3,……,ain-1)4.1数组数组的根本操作访问：给定一组下标，存取相应的数据元素。修改：给定一组下标，修改相应数据元素中的某个数据项的值。 操作方法根据其存储结构决定4.1数组4.1.2数组的顺序存储和访问一维数组在内存中的存放很简单，只要顺序存放在连续的内存单元即可。二维数组，如何用顺序结构表示？内存地址是一维的，而数组是二维的，要将二维数组挤入一维的地址中，有两个策略： 以行为主序〔C语言使用〕以列为主序4.1数组a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1设A是一个具有m行n列的元素的二维数组:以行为主序的方式：a00a01a0n-1

a10a11a1n-1am-11am-1n-101n-1nn+12n-1mn-1a00a10am-10

a01

a11am-11

a0n-1a1n-1

am-1n-101m-1mm+12m-1nm-1以列为主序的方式：Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-14.1数组4.1.3矩阵的压缩存储

一特殊矩阵的压缩存储二稀疏矩阵的压缩存储

1三元组表的存储结构2十字链表的存储结构4.1数组数组元素存储地址的计算假设二维数组A每个元素占用s个存储单元，Loc(aij)为元素aij的存储地址，Loc(a00)是a00存储位置,也是二维数组A的基址。假设以行序为主序的方式存储二维数组，那么元素aij的存储位置可由下式确定：Loc(aij)=Loc(a00)+〔ni+j)s假设以列序为主序的方式存储二维数组，那么元素aij的存储位置可由下式确定：Loc(aij)=Loc(a00)+〔mj+i)s一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二维以上的多维数组使用相对较少，对于高维数组的顺序存储方法，可以将二维的情形加以推广便能够得到。4.1数组矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。一个m行n列的矩阵是一平面阵列，有m

n个元素。可以对矩阵作加、减、乘等运算。只有少数程序设计语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。4.1数组Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1应用中常遇到一些阶数很高的矩阵，矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。例如，设一个10001000的矩阵中有800个非零元素，假设用二维数组存储需要106个存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩存储。本章将讨论两类矩阵的压缩存储：1特殊矩阵的压缩存储

2稀疏矩阵的压缩存储4.1数组Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1一特殊矩阵 值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例：对称矩阵、上〔下〕三角矩阵都是特殊矩阵a00a10a20…an-10a10a11a21an-10an-11an-1n-1a00a01a0n-10

a11a1n-1000

an-1n-14.1数组

特殊矩阵压缩存储(以对称矩阵为例)对称矩阵是满足下面条件的n阶矩阵:

aij=

aji0

i,j

n-1

a00a01a0n-1a10a11a1n-1an-10an-11an-1n-1对称矩阵元素可以只存储下三角局部，共需n(n+1)/2个单元的空间(三角矩阵的存储方式类似〕a00a10a11a20a21a22

an-10an-11an-1n-1a00

a10

a11

a20

a21a22

an-10an-11

an-1n-1k=012345n(n+1)/2-14.1数组k=i(i+1)/2+j当i

jj(j+1)/2+i当i

j以一维数组sa[]作为n阶对称矩阵A的存储结构，A中任意一元素aij与它的存储位置sa[k]之间存在着如下对应关系：a00

a10

a11

a20

a21a22

an-10an-11

an-1n-1k=012345n(n+1)/2-1例如，

a53在sa[]中的存储位置是：k=5*(5+1)/2+3=18sa[18]=a534.1数组压缩存储的对称矩阵的取值算法intget_M(inti,intj){if(i>=j)return(sa[i*(i+1)/2+j])elsereturn(sa[j*(j+1)/2+i]);}压缩存储的对称矩阵的赋值算法voidassign_M(inti,intj,intvalue){if(i>=j)sa[i*(i+1)/2+j]=value;elsesa[j*(j+1)/2+i]=value;}4.1数组

带状矩阵

所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个a00a01a020

0

0

0

0

0

0

0

0

a10a11a12a130

0

00

0

0

0

0a20a21a22a23a24000

0

0

0

00

a31a32a33a34a3500

0

0

0

00

0

a42a43a44a45a460

0

0

0

00

0

0a53a54a55a56a5700

0

0

0

0

00

a64a65a66a67a680

0

00

00

0

0

a75a76a77a78a790

0

00

0

0

0

0a86a87a88a89a810

0

00

0

0

0

0

0

a97

a98a99a910a91100

0

0

0

0

0

0

a108a109a1010a101100

0

0

0

0

0

0

0

a119a1110a1111d4.1数组a00a010

0

0

a10a11a1200

0

a21a22a2300

0

a32a33a340

0

0a43a44K=01234567891011121314为计算方便，认为每一行都有2d+1个非0元素，假设少那么用0补足，所以，存放矩阵的数组sa[]有n(2d+1)个元素数组元素sa[k]与矩阵元素aij之间有关系k=i*(2d+1)+d+(j-i)a00前为何放一个0？你会放d=2,n=6的带状矩阵吗？？4.1数组0a00

a01

a10

a11a12a21a22a23a32a33a34a43a440压缩存储的带状矩阵的取值算法intget_Md(inti,intj){if(abs(i-j)<=d〕return(sa[i*(2*d+1)+d+(j-i)])；elsereturn(0);}压缩存储的带状矩阵的赋值算法voidassign_Md(inti,intj,intvalue){if(abs(i-j)<=d〕sa[i*(i+1)/2+j]=value;}4.1数组稀疏矩阵

1什么是稀疏矩阵

有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。

例

A

=012900000000000-3000014000240000018000001500-7000A有42〔67〕个元素有8个非零元素如何进行稀疏矩阵的压缩存储？？4.1数组2稀疏矩阵的压缩存储〔只讨论有较多零元素矩阵的压缩存储〕1〕三元组表〔i,j,aij)A=((0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7))加上行、列数6，7A

=012900000000000-3000014000240000018000001500-7000表示非零元的三元组4.1数组2〕三元组顺序表

假设以顺序存储结构来表示三元组表，那么可得稀疏矩阵的一种压缩存储方式——我们称之为三元组顺序表。稀疏矩阵的三元组顺序表的类型定义structnode{introw,col;//非零元的行下标和列下标intvalue;//非零元值};typedefstructnodeNODE;NODEma[MAX]；ma[0]用于存储矩阵行数、列数、非零元个数用于存储非零元三元组的结构4.1数组A的三元组顺序表图示A

=012900000000000-3000014000240000018000001500-7000rowcolvalue01234567820-3501501124118029322453-72514678例如ma[1].row=0,ma[1].col=1,ma[1].value=124.1数组3)转置运算算法转置运算是一种最常用的矩阵运算。对于一个m行n列的矩阵A，它的转置矩阵B是一个n行m列的矩阵。例如，以下图中的矩阵A和B互为转置矩阵。A

=012900000000000-3000014000240000018000001500-7000B

=00-3001512000180900240000000-70000000014000000000

4.1数组

A第0列第一列第二列第三列第四列第五列第六列….

B第0行第一行第二行第三行第四行第五行第六行….转置运算算法4.1数组矩阵B矩阵Arowcolvalue01234567820-3501501124118029322453-72514678rowcolvalue012345678101235-702-32324051520952141418768分析：〔1〕将矩阵的行列数的值交换〔2〕将每一个三元组的i和j相互调换〔3〕重排三元组之间的次序4.1数组转置运算算法按照A的列序来进行转换的根本思想对ma[]从头至尾扫描： 第一次扫描时，将ma[]中列号为0的所有元组交换行列值后，依次赋值到mb[]中 第二次扫描时，将ma[]中列号为1的所有元组交换行列值后，依次赋值到mb[]中依此类推，直至将ma[]的所有三元组赋值到mb[]中4.1数组ijv011202920-3251432244118501553-7ijv20-3141802-3501505150112101241180292093224232453-735-725145214A矩阵B矩阵对A六次扫描完成转置运算第一次扫描查找第0列元素第一次扫描结束第二次扫描结束第二次扫描查找第1列元素第三次扫描查找第2列元素第四次扫描查找第3列元素第五次扫描查找第4列元素第六次扫描查找第5列元素转置运算算法图示0123456786787684.1数组转置算法:采用三元组表存储表示，求稀疏矩阵A的转置矩阵Binttranspose(NODEma[],NODEmb[]){inti,j,k;if(ma[0].value==0)return(0);mb[0].row=ma[0].col;mb[0].col=ma[0].row;mb[0].value=ma[0].value;k=1;//k为当前三元组在mb[]存储位置(下标)

for(i=0;i<ma[0].col;i++)//找ma[]中第i列所有非0元素for(j=1;j<=ma[0].value;j++)//j为扫描ma[]的“指示器〞//j“指向〞三元组称为当前三元组

if(ma[j].col==i){mb[k].row=ma[j].col;mb[k].col=ma[j].row;

mb[k].value=ma[j].value;k++;}

return(1);}4.1数组时间复杂度分析算法的根本操作为将ma[]中的三元组赋值到mb[]，是在两个循环中完成的，故算法的时间复杂度为O(nt),其中n为A矩阵的列数,t为非0元素个数。当非零元的个数t和矩阵元素个数mn同数量级时，即t≈mn，转置运算算法的时间复杂度为O〔nmn〕。由此可见：在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于t<<mn的情况。该算法效率不高的原因是：对为实现A到B的转置，该算法对ma[]进行了屡次扫描。其特点是：以B矩阵的三元组为中心，在A矩阵的三元组中通盘查找适宜的结点置入mb[k]中能否在对ma[]一次扫描的过程中，完成A到B的转置？4.1数组十字链表的存储结构以三元组表示的稀疏矩阵，在运算中，假设非0元素的位置发生变化，会引起数组元素的频繁移动。为解决这个问题，采用十字链表的存储结构在十字链表中，表示非0元素的结点除了三元组，还有两个指针域： 向下域〔down)链接同一列下一个非0元素 向右域(right)链接同一行下一个非0元素稀疏矩阵中同一行的非0元素结点通过向右域，链接成一个带头结点的行循环链表同一