数据结构教案市公开课金奖市赛课一等奖课件

第0章绪论教学目的：1.掌握数据结构基本概念；

2.掌握抽象数据类型概念和软件结构办法

3.理解算法含义，掌握算法时间复杂度计算教学重点：1.数据结构概念

2.抽象数据结构软件结构办法

3.时间复杂度计算教学难点：算法和算法时间复杂度作业：1-1

1-3

1-11（前三道小题）第1页第1页

一.基本概念数据：人们利用文字符号、数字符号以及其它要求符号对现实世界事物及其活动所作抽象描述．*数据元素：表示一个事物一组数据称为一个数据元素．*数据项：构成数据元素数据称为该数据元素数据项．抽象数据元素：没有实际含义数据元素．抽象数据类型：没有确切定义数据类型叫抽象数据类型，用符号DataType来表示．数据逻辑结构：即为数据元素之间互相联系方式．可分为线性结构、树结构和图结构．1.1数据结构基本概念第2页第2页二本门课程主要内容数据存储结构：数据元素在计算机中存储方式．它基本形式有两种：顺序存储结构，链式存储结构．数据操作：对一个数据类型数据进行某种处理．数据操作集合：对一个数据类型数据所有操作．数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型惯用数据结构．在讨论这些结构时，主要从它们逻辑结构、存储结构和数据操作三个方面进行分析讨论．第3页第3页三.

.

数据元素数据项举例假设要描述学生信息，看表1-1学生信息表学号

姓名性别年令01张三男20

02李四男21

03王五女22表中除第一行标题行外，其它每一行为一个数据元素，每一列为一个数据项．三举倒第4页第4页关于数据元素、数据项描述都能够使用某种高级程序设计语言来描述，本书采用C语言描述．如上表学生信息可定义为下列结构体：

typedefstructstudent{charnumber[8];charname[10];charsex[3];intage;}studenttype用C语言描述

第5页第5页

有了上面定义后，studenttype就可看做与structstudent含义相同标识符1．线性结构树结构图结构ABCDABDFCEGABCDFEG结构与标识符由图可见，线性结构除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素．而树结构是除根结点外每个元素只有一个前驱元素，可有零个或若干个后继元素．图每个元素可有零或多个前驱或后继元素．第6页第6页1.

把数据元素存放在一块连续地址空间内存中，其特点是逻辑上相邻数据元素在物理上也相邻，数据间逻辑关系表现在数据元素存放位置上．以下图所表示：

a0

a1a2……an-2an-1

2。顺序存储结构0

12

ｎ-2

ｎ-1第7页第7页使用指针把相互直接关联结点链接起来，其特点是逻辑上相邻数据元素在物理上不一定相邻，数据间逻辑关系表现在结点链接关系上．以下图示3。链式存储结构第8页第8页

数据类型：指一个类型和定义在这个类型上操作集合.比如，当说计算机中整数数据类型时，就不但指计算机所能表示整数数值集合，而且指能对这个整数类型进行+、-、*、＼和求模（％）操作．抽象数据类型（AbstractDataType缩写为ADT）：是指一个逻辑概念上类型和这个类型上操作集合．数据类型和抽象数据类型不同之处于于：数据类型指是高级程序设计语言支持基本数据类型，而抽象数据类型指是在基本数据类型支持下用户新设计数据类型．像表、堆栈、队列、串、数组、树、图等就是一个个不同抽象数据类型．12抽象数据类型和软件结构办法第9页第9页13。算法和算法时间复杂度（1）1.3.1算法算法是描述求解问题办法操作环节集合．它主要有三种形式：文字形式伪码形式和程序设计语言形式．例1-1设计一个把存储在数组A中ｎ个抽象数据元素ａ0，ａ1，…，ａｎ-1逆置算法，即要求逆置后数组中数据元素序列为ａｎ－１，…ａ1，ａ0，并要求原数组中数据元素值不能被改变．设计：这是一个算法设计问题．该算法要求有一个表示元素个数输入参数ｎ，一个表示原数组输入参数ａ和一个表示逆置后数组输出参数ｂ．第10页第10页．算法设计下列：voidReverse(intn,DataTypea[],DataTypeb[]){inti;for(i=0;i<n;i++)b[i]=a[n-1-i];}算法时间复杂度（2）第11页第11页该算法实现办法如图1-3所表示．b0+3↵a0↵b1+3↵.↵a1↵.↵bn-2↵an-2↵bn-1↵An-1↲

图1-3例1-1算法实现办法图示该算法实现办法第12页第12页

设计一个把存储在数组A中ｎ个抽象数据元素ａ0，ａ1，…，ａｎ-1就地逆置算法，即要求逆置后数组中数据元素序列为ａｎ－１，…ａ1，ａ0，并要求原数组中数据元素值被改变．设计：这是另一个算法设计问题．该算法要求有一个表示元素个数输入参数ｎ，一个表示原数组输入参数ａ和一个表示逆置后数组输出参数ｂ．由于要求原数组中数据元素这被改变，因此输出参数ｂ必须与输入参数ａ相同，因此，这两个参数应设计为同一个参数，其参数类型设计为输入输出混合型参数．例1---2第13页第13页算法设计下列：voidReverse(intn,DataTypea[]){inti,m=n/2;DataTypetemp;for(i=0;i<m;i++){temp=a[i];a[i]=a[n–1–i];a[n–1–i]=temp;}该算法实现办法如图1—4所表示p20算法设计第14页第14页

(1)正确性能(2)可读性

(3)健壮性

(4)

高时间效率

(5)

高空间效率13.2算法设计目的第15页第15页.（1）

事后统计办法（2）

事前分析办法事前分析办法主要分析算法时间效率与算法所处理数据个数ｎ函数关系定义1-1

T(n)=O(f(n))当且仅当存在正常数c和n0对所有n(n≥n0)满足T(n)≤c*f(n).即：当算法时间复杂度T(n)与数据个数n无关系时，T(n)≤c﹡1，因此此时算法时间复杂度T(n)=

O(1)；当算法时间复杂度T(n)与数据个数n为线性关系时，因此此时算法时间复杂度T(n)=O(ｎ)；依次类推分析一个算法中基本语句执行次数与数据个数函数关系，就可求出该算法时间复杂度．13.3算法时间效率度量第16页第16页例1-3

设数组ａ和ｂ在前边部分已赋值，求下列两个ｎ阶矩阵相乘运算算法时间复杂度．for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;／*基本语句1*／for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][j]b[k][j];/*基本语句2*/}举例阐明下面举例阐明算法时间复杂度分析办法：第17页第17页解：设基本语句执行次数为f(n)，有f(n)=c1*n2+c2*n3因T(n)=f(n)=c1*n2+c2*n3=c*n3，其中c1,c2,c可为任意常数，因此该算法时间复杂度为T(n)=O(n3)

第18页第18页例1-6

下边算法是在一个有ｎ个数据元素数组ａ中删除第ｉ个位置数组元素，要求当删除成功时数组元素个数减1，求该算法时间复杂度．其中，数组下标为0～ｎ-1．intDelete(inta[],int*n,inti){↵intj;f(i<0‖I>=*n)return0;/*删除位置错误，失败返回*/ifor(j=i+1;j<*n;j++)a[j-1]=a[j];/*顺次移位填补*/(*n)--;/*数组元素个数减1*/return;/*删除成功返回*/}第19页第19页

解：此算法时间复杂度随删除数据位置不同而不同．当删除最终一个位置数组元素时有i＝n－1，j＝i+1＝n，故不需要移位填补二循环次数为0，…，当删除第一个位置数组元素时有i＝0，j＝i+1＝1，需移位填补n－1次而循环次数为n－1．此时算法时间复杂度应是删除数据位置等概率取值情况下平均次数．设为删除第个位置上数据元素概率，则有，设E为删除数组元素平均次数，则有E=1/n∑0n-1(n-1-i)=1/n[(n-1)+(n-2)+…2+1+0]=1*/n1n(n-1)/2=(n–1)/2因T(n)=E≤(n–1)/2≤c*n，其中c为常数，因此该算法等概率平均时间复杂度为T(n)=0(n)

算法时间复杂度隋删除数据位置不同而不同第20页第20页（）

(1)

各种符号均以英语单词命名，所有命名应见名知意．(2)

变量名字母均小写，若单词多于一个时，第二个单词首字母大写．

(3)

自定义结构体名常量名和文献名均小写．但所有单词首字母大写．可缩写．

(4)

函数中抽象数据类型参数用单字母大写，顺序表SeqList类型参数L．1.4算法书写要求第21页第21页教学目的：1.理解线性表抽象数据类型2.掌握线性表顺序表示和实现3.掌握线性表链式表示和实4.掌握静态链表概念5.掌握顺序表和单链表算法设计教学重点：1.概念理解2.线性表操作3.算法设计办法教学难点：线性表概念，顺序表和链表操作作业：2-11

2-12第二章线性表第22页第22页2.1.1线性表定义线性表是一个能够在任意位置进行插入和删除数据元素操作由n(n≥0)个相同类型数据元素a0,a1,a2,…,an-1构成线性结构．顺序存储结构存储数据元素详细是用数组存储，数据元素编号从0开始．2。1。1线性表抽象数据类别第23页第23页.

线性表抽象数据类型主要包括两个方面，即数据集合和该数据集合上操作集合．

数据集合：线线性表数据集合能够表示为a0,a1,a2,…,an-1或a1,a2,…,an，每个数据据元素数据类型为抽象数据元素类型DataType．

2.1.2线性表抽象数据类型第24页第24页操作集合.

（1）初始化

ListInitiate(L)：初始化线性表

L.（2）求当前数据元素个数(ListLength(L)：函数返回线性表L当前数据元素个数

．

（3）

插入数据元素ListInsert(L,i,x)：在线性表L第i个数据前插入数据元素x

（4）

删除数据元素ListDelete(L,i,x)：删除线性表L第i个数据元素，所删除数据元素x由输出参数带回．（5）

取数据元素ListGet(L,i,x)：取线性表L第i个数据元素，所取数据元素x由输出参数带回．第25页第25页2。2线性顺序表示和实现线性表抽象数据类型有两种存储结构：顺序存储结构；链式存储结构．顺序存储结构线性表称作顺序表．2.2.1

顺序表存储结构数组有静态数组和动态数组两种．静态数组存储空间申请和释放由系统自动完毕，动态数组存储空间申请和释放由用户通过调用系统函数完毕．顺序表普通采用静态数组办法实现数据元素存储．第26页第26页顺序表存储结构示意图下列：List

0123456MaxSize-1size=5为用C语言描述上图所表示顺序表，定义结构体

SeqList下列：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;a0a1a2a3a4顺序表存储结构示意图第27页第27页（1）

初始化ListInitiate(SeqList*L)voidListInitiate(SeqList*L)/*初始化顺序表L*/{L->size=0;/*定义初始数据元素个数*/}（2）

求当前数据元素个数(ListLength(L)intListLength(SeqListL)

/*返回顺序表L当前数据元素个数*/{returnL.size;}2.2.2顺序表操作实现第28页第28页（3）

插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex)/*在顺序表L第i（0≤i≤size）个位置前插入数据元素x*//*插入成功返回1，插入失败返回0*/{intj;if(L->size>=MaxSize){printf(“顺序表已满无法插入！＼n”);return0;}elseif(i<0‖i>L->size){

2。2。2顺序表操作实现（2）第29页第29页插入数据元素（一）printf(“参数i不合法！＼n”);

return0;}return0;}else{/*为插入做准备*/

for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];L->list[i]=x;

/*插入x*/第30页第30页L->size++;/*元素个数加1*/return1;}}插入步骤：首先把存放单元size-1至存放单元i中数据元素依次后移一个存放单元，然后把数据元素x插入到存放单元i中（注意此操作是前插），最终把数据元素个数加1．其过程以下图：list01234567MaxSIZE-1…

插入数据元素（二）

1011121314151610111214151613list

0

1

2

3

4

5

6

7

MaxSize-1

第31页第31页（1）

（intintListDelete(SeqList*L,inti,DataType*x)//*删除顺序表L中位置为i（0≤i≤size-1）数据元素并存储到x中*//*/*删除成功返回1，删除失败返回0*/{)↵intj;if(L->size<=0){printf(“顺序表已空无法删除！＼n”);return0;}（4）删除数据元素取数据元素ListDelete(L,i,x)第32页第32页elseif(i<0‖i>L->size){printf(“参数i不合法！＼n”);

return0;}Else{*x=L->list[i];/*保留删除元素到x中*//*依次前移*/

for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];L->size--;/*数据元素个数减1*/return1;)↲)↲

删除和取数据元素（二）第33页第33页（5））

取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x)//*取顺序表L中第i个数据元素存于x中成功返回1失败返回0*/{if(i<0‖i>L.size-1){printf(“参数i不合法＼n”);return0;}else{x=L.list[i];return1）↵）↵;（5）取数据元素第34页第34页顺序表上插入和删除是顺序表中时间复杂度最高组员函数．在顺序表中插入一个数据元素时，最坏情况是pos＝0，需移动size个数据元素；最好情况是pos＝size，需移动0个数据元素．设pi是在第i个存储位置上插入一个数据元素概率，设顺序表中数据元素个数为n，当在顺序表任何位置上插入数据元素概率相等时，有pi＝1/（n+1），，则向顺序表插入一个数据元素需移动数据元素平均次数为：Eis=∑0npi(n-i)=∑0n(n-i)=n/2删除操作时间复杂度计算见教材ｐ33．顺序表中其余操作都与数据元素个数n无关，在顺序表中插入和删除一个数据元素时间复杂度为O(n)，其余操作时间复杂度为O(1)．2。2。3顺序表操作分析第35页第35页2。2。4顺序表应用举例请同窗们自己分析例题算法第36页第36页2。3线性表链式表示和实现指针：指向物理存储单元地址变量结点：由数据元素域和一个或若干个指针域构成一个结构体链表：链式存储结构线性表链表主要有单链表、单循环链表和双向循环链表三种．第37页第37页单链表是构成链表结点只有一个指向直接后继结点指针域．1.

单链表表示办法定义单链表结点结构体下列：typedefstructNode{DataTypedata;structNode*next;}SLNode;数据域指针域

datanext2。3。1单链表存储结构（1）第38页第38页其中，data域用来存储数据元素，next域用来存储指向下一个结点指针．单链表有带头结点结构和不结点结构两种．指向单链表指针称作头指针，头指针所指不存储数据元素第一个结点称为头结点．存储第一个数据元素结点称为第一个数据元素结点．符号＂∧＂表示空指针，空指针是一个特殊标识，用来标识链结束．空指针在算法描述中用NULL表示．在链式存储结构中，数据元素逻辑顺序是通过链中指针链接实现．2。3。1（2）第39页第39页(1）带头单链表每个元素存贮区别为两大部分：headpdatanext带头和不带头结点单链表比较a0

an-1∧

X∧

上图是在带头结点单链表第一个数据元素前插入结点前图示第40页第40页a0a1an-1

∧x上图是在带头结点单链表第一个数据元素前插入结点后图示．也可参考下图：headp

s带头和不带头结点单链表比较（2）第41页第41页plen

a1↲

an↲

↲a2↲headq

单链表插入结点P->next=q;q->next=p->next;第42页第42页Headpnext

a0a1

a

n-1∧上图是删除带头结点单链表第一个数据元素结点示意图第43页第43页22）不带头结点单链表插入删除数据元素结点示意图下列：在第一个数据元素前插入结点时，头指针head值将改变为新插入结点指针s，其插入过程下列：heada0

a1an-1↵

x∧插入删除数据元素结点示意图第44页第44页在第一个数据元素前插入结点时，头指针head值将改变为新插入结点指针s，其插入过程下列：

head插入前示意图shead

sa0上图是在不带头结点单链表第一个数据元素前插入结点后示意图

a0a1an-1

∧x∧a0a1an-1

∧x不带头结点单链表插入删除数据元素示意图第45页第45页在不带头结点单链表其它数据元素前插入结点示意图下列：headdatanextpa0ai-1

aian-1∧

X↲

s插入结点示意图第46页第46页类似地，删除不带头结点单链表第一个数据元素结点时，头指针head值将改变为head->next，即指针head等于原head->next值headdatanexta0

a1

an-1∧

删除不带头结点示意第47页第47页

删除不带头结点单链表其它数据元素结点时示意图下列

：headdatanextpa0ai-1aiai+1an-1

∧第48页第48页单链表是由一个个结点链接构成，单链表中每个结点结构体定义下列：typedefstructNode{

DataTypedata;structNode*next;}SLNode;在带头结点单链存储结构下，线性表抽象数据类型操作集合中各个操作详细实现办法下列：（1）

初始化ListInitiate(SLNode**head)

voidListInitiate(SLNode**head)/*初始化*/{/*假如有内存空间，申请头结点空间并使头指针head指向头结点*/if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1)(*head)->next=NULL;}

第49页第49页intListLength(SLNode*head){SLNode*p=head;/*ｐ指向头结点*/intsize=0;/*size初始为0*/while(p->next!=NULL)/*循环计数*/{

p=p->next;size++;}returnsize;

}（2）求当前数据元素个数ListLength(SLNode*head)求当前数据元数个数第50页第50页headpsize=0a0

a1

an-1

^headpsize=na0

a1

an-1∧∧

接上面第51页第51页（1）（（3）

插入ListInsert(SLNode*head,inti,DataTypex)

intListInsert(SLNode*head,inti,DataTypex)/*在带头结点单链表head第i(0≤i≤size)个结点前*/

/*插入一个存储数据元素x结点．插入成功时返回1，失败返回0*/{SLNode*p,*q;intj;

while(p->next!=NULL&&j<i-1)

/*最后让指针p指向第i-1个结点*/{p=p->next;j++;}插入存储数据元素结点（1）第52页第52页if(j!=i-1){printf(“插入位置参数错!”);return0;}/*生成新结点由指针q批示*/if(q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1)q->data=x;q->next=p->next;/*插入环节1*/p->next=q;/*插入环节2*/return1;}插入存储数据元素结点（2）第53页第53页（4）

删除取数据元素ListDelete(SLNode*head,inti,DataTypex)

intListDelete(SLNode*head,inti,DataTypex)/*删除带头结点单链表head第i（0≤i≤size-1）个结点*//*被删除结点数据元素域值由x带回．删除成功时返回1，失败返回0*/{SLNode*p,*s;intj;p=head;j=-1;删除取数据元素（1）第54页第54页while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){/*最后让指针ｐ指向第i-1个结点*/

p=p->next;j++;}if(j!=i-1){printf(“删除位置参数错!”);return0;}

s=p->next;/*指针ｓ指向ai结点*/*x=s->data;/*把指针ｓ所指向结点数据元素域值赋予x*/p->next=p->next->next;/*删除*/free(s);/*释放指针ｓ所指向结点内存空间*/return1;}删除取数据元素（2）第55页第55页（5）

取数据元素ListGet(SLNode*head,inti,DataTypex)

intListGet(SLNode*head,inti,DataTypex){SLNode*p;intj;

p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j!=i){printf(“取元素位置参数错！”);

return0;}x=p->data;return1;}

取数据元素第56页第56页（6）

撤消单链表Destroy(SLNode**head)

voidDestroy(SLNode**head){SLNode*p,*p1;p=*head;

while(p!=NULL){p1=p;p=p->next;free(p1);}head=NULL;}

撤消单链表第57页第57页当在单链表任何位置上插入数据元素概率相等时，在单链表中插入一个数据元素时比较数据元素平均次数为：Eis=∑0npi(n-i)=1/(n+1)∑0n(n-i)=n/2删除单链表一个数据元素时比较数据元素平均次数为：Edl=∑0n-1qi(n-i)=1/n∑0n-1(n-i)=(n-1)/2单链表数据元素个数操作时间复杂度为T（n）=O（n）单链表主要长处是不需要预先拟定数据元素最大个数，插入和删除操作时不需要移动数据元素；主要缺点是每个结点中要有一个指针域，因此，空间单元利用效率不高．另外，单链表操作算法较复杂．2。3。3单链表操作效率分析第58页第58页本章结束时，再行分析．2。3。4单链表应用举例第59页第59页循环单链表是单链表另一个形式，其结构特点是链表中最后一个结点指针域不再是结束标识∧，而是指向整个链表第一个结点，从而使链表形成一个环．带头结点循环链表操作与带头单链表操作相同，差别在于：1.

在初始化函数中，把语句(*head)->next=NULL改为(*head)->next=head．2.

在其它函数中，循环判断条件p->next!=NULL和p->next->next!=NULL中NULL改为头指针head．

2。3。5循环单链表第60页第60页1.双向链表存储结构双向链表是每个结点除后继指针域外尚有一个前驱指针域．这里讨论是带头结点双向循环链表．在双向链表中，每个结点包括三个域，分别是data域﹑next域﹑prior域．双向链表结点结构体定义下列：

priordatanext

typedefstructNode{DataTypedata;structNode*next;structNode*prior;}DLNode;双向循环链表后继指针和前驱指针各自构成自己单循环链表，见图ｐ482-17．双向链表有助于频繁查找当前结点后继结点和当前结点前驱结点．2。3。6双向链表第61页第61页3.双向链表操作实例

ai1

ai

ai+1

设指针ｐ指向双向链表中第i个结点，则p->next指向第i+1个结点，p->next->prior仍指向第i个结点，即p->next->prior==p；同样地，p->prior指向第i-1个结点，p->prior->next仍指向第i个结点，即p->prior->next==p．p

head

双向链表指针关系空链表第62页第62页双向链表操作实现下列：(1)初始化voidListInitiate(DLNode**head){if(*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);(*head)->prior=*head;/*构成前驱指针循环链*/(*head)->next=*head;/*构成后继指针循环链*/}操作实现下列第63页第63页/*在带头结点双向循环链表第i个结点前*//*插入一个存储数据元素x结点．插入成功返回1，失败返回0*/intListInsert(DLNode*head,inti,DataTypex){DLNode*p,*s;intj;

p=head->next;j=0;

while(p!=head&&j<i)/*寻找第i结点*/{p=p->next;j++;}if(j!=i){printf(“插入位置参数犯错！”)

return0;}(2)插入数据元素（1）第64页第64页if((s=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p->prior;/*插入环节1*/p->prior->next=s;/*插入环节2*/s->next=p;/*插入环节3*/p->prior=s;/*插入环节4*/

return1;}(2)插入数据单元（2）第65页第65页循环双向链表插入过程下列：head

p

插入过程

a

ai1

ai

an-1xs第66页第66页intListDelete(DLNode*head,inti,DataType*x)/*删除带头结点双向循环链表head第i(0≤i≤size-1)个结点*//*被删除结点数据元素域值由x带回，删除成功时返回1，失败返回0*/{DLNode*p;intj;

p=head->next;j=0;while(p->next!=head&&j<i)/*寻找第ｉ个结点*/{

p=p->next;j++;}（3）删除数据无数（1）第67页第67页（3）删除数据元素（2）if(j!=i){printf(“删除位置参数犯错！”);

return0;{p->prior->next=p->next;/*删除环节1*/p->next->prior=p->prior;/*删除环节2*/*x=p->data;free(p);return1;}

第68页第68页voidDestroy(DLNode**head){DLNode*p,*p1;inti,n=ListLength(*head);

p=*head;for(i=0;i<=n;i++){p1=p;p=p->next;free(p1);}head=NULL;}（4）撤消内存空间Destroy(DLNode**head)

第69页第69页2。4静态链表2。5算法设计举例（1）2.5.1

顺序表算法设计举例例2-4

结构一个顺序表删除算法，把顺序表L中数据元素ｘ删除．算法思想；此删除问题可通过一个循环比较过程来实现算法设计下列：intListDataDelete(SeqList*L,DataTypex){inti,j;第70页第70页for(i=0;i<L->size;i++)/*寻找元素x*/if(x==L->list[i])break;if(i==L->size)return0;/*未寻找到元素x*/else/*寻找到元素*/{

for(j=i;j<L->size;j++)/*元素依次前移*/L->list[j]=L->list[j+1];L->size--;/*元素个数减1*/

return1;}}算法设计举例（2）第71页第71页例2-5

设头指针为head，并设带头结点单链表中数据元素递增有序，编写算法将数据元素x插入到带头结点单链表适当位置，要求插入后保持单链表数据元素递增有序．算法思想；从链表第一个数据元素结点开始，逐一比较每个结点data域值和x值，当data小于等于x时，进行下一个结点比较；不然，就找到了插入结点适当位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾．2。5。2单链表算法设计举例第72页第72页voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;/*循环初始化*/curr=head->next;/*curr指向第一个设计元素结点*/pre=head;/*pre指向头结点*//*循环定位插入位置*/while(curr!=NULL&&curr->data<=x){pre=curr;curr=curr->next;}学生分析剩余例题．算法设计下列第73页第73页教学目的：1.掌握堆栈基本概念2.理解堆栈抽象数据类型

3.纯熟掌握堆栈表示和实现

4.掌握队列基本概念

5.掌握顺序循环队列表示和实现

6.掌握链式队列存储结构和操作实现教学重点：1.堆栈表示和实现

2.队列实现教学难点：堆栈实现

第三章堆栈和队列第74页第74页3.1.1

堆栈基本概念堆栈是一个特殊线性表．其数据元素以及数据元素间逻辑关系和线性表完全相同，差别在于线性表允许在任意位置插入和删除，而堆栈只允许在栈顶进行操作．堆栈也称作后进先出表．它可完毕比较复杂数据元素特定序列转换任务．3。1堆栈第75页第75页

数据集合：堆栈数据集合能够表示为a0,a1,…,an-1每个数据元素数据类型为DataType.操作集合：1.初始化StackInitiate(S)：初始化堆栈S2.非空否StackNotEmpty(S)：堆栈S非空否．若堆栈非空，则函数返回1；不然，返回03.入栈StackPush(S,x)：在堆栈当前栈顶插入数据元素x．4.出栈StackPop(S,d)：把堆栈S当前栈顶数据元素删除并由参数d带回．5.取栈顶数据元素StackTop(S,d)：取堆栈S当前栈顶数据元素并由参数d带回以上3.4.5均为成功返回1；不然，返回03。1。2堆栈抽象数类型

3。1。2堆栈抽象数据类型第76页第76页

1.

1.顺序堆栈存储结构顺序堆栈存储结构示意图下列：Stack栈底栈顶012345MaxStackSize-1top用C语言定义上述顺序堆栈结构体SeqStack下列：typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack;

a0a1a2a3a43。1。3堆栈顺序表示和实现第77页第77页;

.

(1)初始化StackInitiate(S)voidStackInitiate(SeqStack*S)/*初始化顺序堆栈S*/{S->top=0;/*定义初始栈顶下标值*/}（2）

非空否StackNotEmpty(S)intStackNotEmpty(SeqStackS)/*判断顺序堆栈S非空否，非空返回1，不然返回0*/{

if(S.top<=0)return0;elsereturn1;}2。顺序堆栈操作实现（1）第78页第78页intStackPush(SeqStack*S,DataTypex)/*把数据元素值x压入顺序堆栈S，入栈成功返回1，不然返回0*/{if(S->top>=MaxStackSize){printf(“堆栈已满无法插入！＼n”);return0;}else{S->stack[S->top]=x;S->top++;return1;}]

(3)入栈StackPush(SeqStack*Sz,DataTypex)操作实现（2）第79页第79页intStackPop(SeqStack*S,DataType*d)/*弹出顺序堆栈S栈顶数据元素值到参数d，出栈成功返回1，不然返回0*/{if(S->top<=0){printf(“堆栈已空无数据元素出栈！＼n”);return0;}else{S->top--;*d=S->stack[S->top];return1;}}操作实现（3）（4）

出栈StackPop(SeqStack*S,DataType*d)第80页第80页StackTop(SeqStackS,DataType*d)intStackTop(SeqStackS,DataType*d)/*取顺序堆栈S当前栈顶数据元素值到参数d，成功返回1，不然返回0*/{if(S.top<=0){printf(“堆栈已空！＼n”);return0;}else{*d=S.stack[S.top-1];return1;}（5）取顶数据元素第81页第81页设上述顺序堆栈结构体定义和操作实现函数存储在文件‘SS＂中，设计下列测试主函数进行测试：﹟include<stdio.h>/*该文献包括printf()函数*/﹟include<stdlib.h>/*该文献包括exit()函数*/﹟defineMaxStackSize100/*定义MaxStackSize为100*/typedefintDataType;/*定义DataType为int数据类型*/﹟include“SeqStack.h”

voidmain(void){SeqStackmyStack;inti,x;3。顺序堆栈测试（1）第82页第82页StackInitiate(&myStack);/*初始化*/for(i=0;i<10;i++){if(StackPush(&myStack,i+1)==0)/*入栈10个数据元素*/{

printf(“错误!＼n”);return;}｝

if(StackTop(myStack,&x)==0)/*取栈顶数据元素*/{

printf(“错误!＼n”);return;}3。顺序堆栈测试（2）第83页第83页

elseprintf(“当前栈顶数据元素为：%d＼n”,x);printf(“依次出栈数据元素序列下列：＼n”);while(StackNotEmpty(myStack)){StackPop(&myStack,&x);/*出栈*/printf(“%d”,x);/*显示数据元素*/}}程序运营输出结果下列：当前栈顶数据元素为：10依次出栈数据元素序列下列：109876543213。顺序堆栈测试（3）第84页第84页1.链式堆栈存储结构

与线性链表类似，链式栈也需要一个描述结点，它作为整个栈代表。链式栈中存贮栈元素结点结构与线性链表相同。3。1。4堆栈链式表示和实现（1）第85页第85页堆栈有两端，插入元素和输出元素一端为栈顶，另一端为栈底．链式堆栈都设计成把靠近头指针一端定义为栈顶．如上图所表示：链式堆栈结点结构体定义下列：

typedefstructsnode{DataTypedata;structsnode*next;}3.1.4堆栈链式表示和实现（2）第86页第86页链式堆栈插入和删除操作都是在链表表头进行．若把链式堆栈设计成带头结点结构，则入栈和出栈操作改变只是头指针所指头结点域值，而不是头指针值，因此，头指针参数可设计成结点指针类型，故此头指针参数必须设计成结点双重指针（即指针指针）类型．带头结点链式堆栈操作实现下列：（1）

初始化StackInitiate(LSNode**head)voidStackInitiate(LSNode**head)/*初始化带头结点链式堆栈*/{

if(*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);(*head)->next=NULL;}3。链式堆栈操作实现第87页第87页（2）

非空否StackNotEmpty(LSNode*head)intStackNotEmpty(LSNode*head)/*判断堆栈是否非空，非空返回1，不然返回0*/{

if(head->next==NULL)return0;return1;}3。链式堆栈操作实现（2）第88页第88页（3）入栈StackPush(LSNode*head,DataTypex)/*把数据元素x插入链式堆栈栈顶head作为新栈顶*/intStackPush(LSNode*head,DataTypex){LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){printf(“内存空间不足无法插入！\n”);return0;}

p->data=x;p->next=head->next;/*新结点链入栈顶*/head->next=p;/*新结点成为新栈顶*/return1;}3。链式堆栈操作实现（3）第89页第89页(4)出栈StackPop(LSNode*head,DataType*d)intStackPop(LSNode*head,DataType*d)/*出栈并把栈顶元素由参数d带回*/{

LSNode*p=head->next;if(p==NULL){printf(“堆栈已空犯错!”);

return0;}head->next=p->next;/*删除原栈顶结点*/*d=p->data;/*原栈顶结点元素赋予d*/free(p);/*释放原栈顶结点内存空间*/

return1;}3。链式堆栈操作实现（4）第90页第90页(5取栈顶数据元素StackTop(LSNode*head,DataType*d)intStackTop(LSNode*head,DataType*d)/*取栈顶元素并把栈顶元素由参数d带回*/{

LSNode*p=head->next;if(p==NULL){printf(“堆栈已空犯错!”);

return0;}d=p->data;return1;}3。链式堆栈操作实现（5）第91页第91页(5)

撤消动态申请空间Destroy(LSNode*head)voidDestroy(LSNode*head){LSNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;free(p1);}}与单链表操作集合相同，链式堆栈也要增长一个撤消动态申请空间操作．

3。链式堆栈操作实现（6）第92页第92页3。3队列3.3.1队列基本概念队列是一个特殊线性表．它允许在其一端进行插入操作，在其另一端进行删除操作．队列中允许进行插入操作一端称为队尾，允许进行删除操作一端称为队头．插入称为入队列，删除称为出队列．当队列中没有数据元素时称为空队列．因队尾插入，队头删除，它也称作先进先出表，即FIFO（FirstInFirstOut）结构．插入与删除分别称为入队与出队。第93页第93页数据集合：队列数据集合能够表示为a0,a1,…,an-1，每个数据元素数据类型为DataType．操作集合：（1）

初始化QueueInitiate(Q)：初始化队列Q.（2）

非空否QueueNotEmpty(Q)：队列Q非空否．若队列非空，函数返回1，不然，函数返回0．

（3）

入队列QueueAppend(Q,x):在队列Q队尾插入数据元素x．如入队列成功，返回1；不然，返回0．（4）

出队列QueueDelete(Q,d)：把队列 Q队头数据元素删除并由参数d带回．如出队列成功，返回1；失败，则返回0．（5）

取队头数据元素QueueGet(Q,d)：取队头数据元素并由参数d带回．如取到数据元素返回1；不然，返回0．.

3。3。2队列抽象数据类型第94页第94页1.

顺序队列存储结构见ｐ73图3-7队列顺序存储结构称为顺序队列，顺序队列事实上是运算受限顺序表，和顺序表同样，顺序队列也是必须用一个向量空间来存储当前队列中元素。由于队列队头和队尾位置是改变，因而要设两个指针以分别批示队头和队尾元素在队列中位置，它们初始值地队列初始化时均应置为０。入队时将新元素插入所指位置，然后尾指针将加１。出队时，删去所指元素，然后头指针将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素下一位置。顺序队列动态示意图见ｐ73图3-7

3。3。3顺序队列第95页第95页由于在入队和出队操作中，头尾指针只增长不减小，致使被删除元素空间永远无法重新利用。因此，尽管队列中实际元素个数远远小于向量空间规模，但也也许由于尾指针巳超出向量空间上界而不能做入队操作。该现象称为假上溢。见教材上例子．2.顺序队列“假溢出”问题第96页第96页.

1。顺序循环队列基本原理为充足利用向量空间。克服上述假上溢现象办法是将向量空间想象为一个首尾相接圆环，并称这种向量为循环向量，存储在其中队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只但是当头尾指针指向向量上界（QueueSize-1）时，其加1操作结果是指向向量下界0。由于循环队列元素空间能够被利用，除非向量空间真被队列元素所有占用，不然不会上溢。因此，除一些简朴应用外，真正实用顺序队列是循环队列。.

.。2。顺序循环队列队空和队满判断问题由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。

3。3。4顺序循环队列表示和实现1-2。第97页第97页（1）少用一个存储单元：

商定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指单元始终为空）队列满判断条件为：(rear+1)%MaxQueueSize==front队列空判断条件仍然为：

rear==front处理问题办法有三种（1）第98页第98页（2）设置一个标志位设标志位为tag，初始时置tag=0；每当入队列成功就置tag=1；每当出队列操作成功就置tag=0．则队列空判断条件为：rear==front&&tag=0队列满判断条件为:rear==front&&tag=1（3）

设置一个计数器（此办法最为简朴）设计数器为count，初始时置count=0；每当入队列操作成功就使count加1；每当出队列操作成功就使count减1．这样，队列空判断条件为：

count==0队列满判断条件为：

count>0&&rear==front

处理问题办法有三种（2-3）第99页第99页循环队列类型定义typedefStruct{DataTypequeue[MaxQqueueSize]intrear;/*队尾指针*/intfront;/*队头指针*/intcount;/*计数器*/}SeqCQueue;用上述第三种办法（计数器法）实现循环队列上六种基本操作

（1）初始化QueueInitiate(SeqCQueue*Q)voidQueueInitiate(SeqCQueue*Q)/*初始化顺序循环队列Q*/{Q->rear=0;/*定义初始队尾指针下标值*/Q->front=0;/*定义初始队头指针下标值*/Q->count=0;}/*定义初始计数器值*/

3。顺序循环队列实现第100页第100页（2）

非空否QueueNotEmpty(SeqCQueueQ)intQueueNotEmpty(SeqCQueueQ)/*判断顺序循环队列Q非空否，非空时返回1，不然返回0*/

{if(Q.count!=0)return1;elsereturn0;}

3。顺序循环队列实现（2）第101页第101页（3）

入队列QueueAppend(SeqCQueue*Q,DataTypex)intQueueAppend(SeqCQueue*Q,DataTypex)/*把数据元素值x插入顺序循环队列Q队尾，成功返回1，失败返回0*/{if(Q->count>0&&Q->rear==Q->front)/*判断队列满否*/{printf(“队列已满无法插入!＼n”)return0;}else{Q->queue[Q->rear]=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->count++;return1;}3。顺序循环队列实现（3）第102页第102页（4）

出队列QueueDelete(SeqCQueue*Q,DataType*d)intQueueDelete(SeqCQueue*Q,DataType*d)