数据结构教案

湖南涉外经济学院

教案

学院信息科学与工程学院

系/教研室软件工程系

课程名称数据结构

主讲教师邹竞

湖南涉外经济学院

讲授章节第12345讲绪论

授课时数2

I

:教学目的：

91.了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容；

2.掌握数据结构的基本概念；

3.理解算法描述和简单的算法分析。

I

教学内容(讲授提纲)

S++；

1从后序课(数据库、操作系统、编译原理、人工智能)的需要和考研两方面介绍数据结构课程

的重要性。

2通过三个例子讲解数据结构研究的内容。

3介绍基本概念：数据的三个层次，数据结构的三个要素，数据结构的分类，四种存

6储结构，抽象数据类型，算法，算法的五个特性，对算法设计的要求，算法描述和算法分析，时间复

杂度和空间复杂度。

4从百钱买百鸡”(一百元钱买一百支笔”的算法例子说明选择算法的重要性：

方案1:

for(i=0;i<=100;i++)

for(j=0;j<=100;j++)

for(k=0;k<=100;k++)

।

it(i+j+k==100&&3*i+2*j+0.5*k==100)printf("i=%dj=%d，k=%d”,i,j,k)

万案2：

for(i=0;i<=20;i++)

for(j=0;j<=34-i;j++)if(3*i+2*j+(100-i-j)*0.5==100)printf("i=%d,j=%d,k=%d°,i-j-

0j)po

方案1内层循环超过1oo万次，在某机器上运行了50分钟；方案2的if语句执行525

次，运行了2秒钟，相差1500倍。

I

5算法分析举例

(1)常量阶：时间复杂度为。(1)

++X；

s=0;

I

语句频度为1,时间复杂度为0(1)。

for(j=1;j<=10000;++j){++x;s+=x;}

语句频度为10000，时间复杂度为0(1)。

(2)对数阶：时间复杂度为O(logn)

s=0;

forG=1;j<=n;j*=2)

语句频度为logn，所以时间复杂度为O(logn)。

(3)线性阶：时间复杂度为O(logn)

s=o；

for(j=1;jv=n;++j)

s++;

语句频度为n,所以时间复杂度为0(n)<,

(4)时间复杂度为O(nlogn)

s=0;

for(j=1;j<=n;j*=2)

for(k=1;kv=n;++k)

1++;

时间复杂度为O(nlogn)

(5)平方阶：时间复杂度为O(logn)

s=0;

for(j=1;j<=n;++j)

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

!s++;

语句频度为n2，所以口寸间复杂度为0(n2)。

s=0;

for(j=1;j<=n;j++)

for(k=1;k<=j;++k)

|s++；

语句频度为n(n+1)/2，所以时间复杂度仍为0(M)。

(6)立方阶：时间复杂度为0(n》

例：矩阵乘法:nxn

for(i=0;i<n;i++)n(n+1)

for(j=0;j<n;j++)〃n(n+1)

{c[i]D]=0:〃M

for(k=0;k<n;j++)//n2(n+1)

c[i]U]=c[i]U]+a[i][k]*b[k]D];//n3

)

说明：各语句行后的数字是该语句重复执行的次数；

本算法时间复杂度为0(n3)

6.空间复杂度

算法原地(就地)工作：

若所用额外存储空间相对于输入数据量来说是常数，则称此算法为原地(就地)工作。

本章节的教学重点、难点：

1.重点是数据结构的基本概念

2.难点是时间复杂度分析

教考方法、教学手段：一

1.介绍到算法概念（45分钟）

2.算法分析和举例（45分钟）使用教具：计算机和投影仪

作业、讨论题、思考题：

编写最耳算法，从小到大依次输出顺序读人的三个整数。要求：

最佳情况：比较2次，无移动；最差情况：比较3次，7次移动

参考资料：

1.陈守孔等著《算法与数据结构C语言版》机械工业出版社2007

2.陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3•严蔚敏等著《数据结构C语言版》清华大学出版社2005

4.D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

教学目的：

讲授章节第2讲线性表一一顺序表

授课时数2

。1.理解非空线性结构的四个特征。

2.线性表是重要的线性结构，要掌握线性表的定义。

I

3.掌握线性表的操作在顺序表中的实现。

I

教学内容(讲授提纲)

I

非空线性结构的四个特征。

■:1.

2.线性表的定义

3.给定线性表的逻辑结构就可以设计算法：

■(1)遍历线性表L

(2)合并线性表1:设La和Lb是元素属于同一数据对象且非递减有序的两个线

g性表，现要求将两个线性表合并成一个新的非递减有序的线性表Lc。

(3)合并线性表2:设La和Lb是元素属于同一数据对象的两个线性表，试将线性表Lb合

并到线性表La中。要求Lb中元素和La中元素相同的不再合并。

}SeqList;

I

要分析为什么(2)和(3)的时间复杂度分别是。(m*n)和。

I

4.线性表的顺序表示和实现

■

#defineMAXSIZE100〃顺序表的最大容量

I

I

；typedefstruct

{ElemType〃存放线性表的数组

EHAV/C1-7L1.

intlast;〃last是线性表的长度

?5.线性表的操作在顺序表中的实现。

I

I

(1)定义的线性表的10个操作在顺序表中的实现。

(2)分析在插入和删除操作中的时间复杂度。

I

6.几个算法举例：

■

(1)顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性

表空间足够大。试给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保

持非递减有序。高效指最大限度的避免移动元素。

(2)请写一个算法将顺序表(a1,…,an)逆置为(an,...,a1)。

(3)已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间

9复

杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。

(0(1)表示算法的辅助空间为常量)。

(4)设将n(n>1)个整数存放到一维数组R中。

试设计一个在时间和空间两方面

|都尽可能高效的算法，将R中保存的序列循环左移P(0<P<n)个位置，即将R

中的数据由(X0,据，…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求：

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之

处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

|解答：

(1)算法设计思想：按照下标。到P-1>P到n-1、0到n-1的顺序，将这三段分别逆置，最后的结果即为

所求。

(2)voidleftshift(intR[],intp,intn)

〃将有n个元素的一维数组R的序列循环左移p(0<pvn)个位置

{elemtypet;//t和数组R中的元素具有相同类型

for(i=0;i<p/2;i++)//逆置O..p-1段

{t=R[i]；R[i]=R[p-1-i];R(p-1-i]=t;}

for(i=p;i<(n+p)/2;i++)//逆置p..n-1段

{t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;}

for(i=0;i<n/2;i++)//逆置O..n-1段，即整个数组逆置

{t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;}

}〃算法初始调用：leftshift(R,p,n)，各参数意义如上。

(3)算法执行了两趟逆置，时间复杂度为0(n);用了一个辅助变量空间，空间复杂度为0(1)。

讨论：若采用直接左移P位，空间复杂度仍为0(1)>但时间复杂度为O(np),

本章节的教学重点、难点：

重点是顺序表的定义，基本操作的实现。

难点是高效算法设计，例如国家2010年硕士研究生入学考试算法题就有5种解法

教学方法、教学手段：

1.开始到顺序表中各种操作实现(45分钟)

2•顺序表算法举例(45分钟)

使用教具：计算机和投影仪

作业、讨论题、思考题：

2.3分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。

原2.16顺序表la与lb非递减有序，顺序表空间足够大。试设计一种高效算法，将lb中元素合到

la中，使新的la的元素仍保持非递减有序。高效指最大限度地避免移动元素­■

改为2.16顺序表la非递减有序，lb非递增有序，顺序表空间足够大。试设计一种高效算法，将lb

中元素合到la中，使新的la的元素仍保持非递减有序•高效指最大限度地避免移动元素。

参考资料：

1.陈守孔等著《算法与数据结构C语

言版》机械工业出版社2007

2.陈守孔等著《算法与数据结构考研试题精析》

机械工业出版社2008

3•严蔚敏等著《数据结构C语言版》清华大学出版社2005

4.D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

讲授章节第3讲单链表

授课时数2

教学目的：

1从顺序存储结构的优缺点，引出链表的必要性。

2.掌握链表的类型定义。

3.掌握线性表的操作在单链表中的实现。

4.掌握单链表的建立方法，特别是头插法和尾插法。

5.了解单链表的应用。

教学内容(讲授提纲)

1顺序存储结构的缺点：

插入和删除必须大量移动兀素；必须预先确;E空间；表空间不易扩充。

2.链表的类型定义。

typedefstructNode

{ElemTypedata;

structNode*next;

}LNode,*LinkedList;

几个概念：结点，首兀结点，第一兀素结点，头结点，指针，头指针

3.掌握线性表的操作在单链表中的实现。

ListInit(L)；ListLength(L)；

ListGet(LJ);ListLocate(L,x);

ListClear(L);ListEmpty(L)；

ListPrior(L,e)；ListNext(L,e)；

Listlnsert(L,i,e);ListDelete(LJ);

4.掌握单链表的建立方法，特别是头插法和尾插法。

(1)头插法

LinkedListLinkedListCreat1()

{〃用头插法建立带头结点的单链表

LinkedListL;

L=(LNode*)malloc(sizeof(LNode));〃申请结点

L->next=NULL;〃初始化一个空链表，L为头指针

seanf(&x);//x是和链表元素具有相同类型的变量

while(x!=flag)//flag为结束输入的标志

{p=(LNode*)malloc(sizeof(LNode));

p->data=x;n输入元素值

p->next=L->next;〃链接到表中

L->next=p;〃插入到表头

seanf(&x);〃读入下一个元素的值

returnL;

)

(2)尾插法

LinkedListLinkedListCreat2()

{〃用尾插法建立带头结点的单链表

LinkedListL;

L=(LNode*)malloc(sizeof(LNode));

L->next=NULL;r=L;

seanf(&x);

while(x!=flag)〃设置结束标志

{p=(LNode*)malloc(sizeof(LNode);

p->data=x;〃赋值元素值

r_>n〃在尾部插入新结

瞰P；点〃r指向新的尾结点

seanf(&x);

r->〃最后结点的指针域放空指

rwiM业ILL;针

)

(3)单链表的遍历

voidprint(LinkedListla)〃非递归

{LinkedListp=la->next;

while(p)

{printf(；%c,p->data);//正序输出

p=p->next;

voidout(LinkedListp)〃递归

攸p)

}//end

本章节的教学重点、难点：

1.动态存储（单链表）的概念。

2•单链表的算法设计。

教学方法、教学手段：

1.链表的定义和基本操作的实现（45分钟）

2•链表生成和链表应用的算法设计（45分钟）

使用教具：计算机和投影仪

作业、讨论题、思考题：

2.1试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作用。

2.2分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。

2.4为什么在单循环链表中常使用尾指针，若只设头指针，插入元素的时间复杂度如何？

2.5在单链表、双链表、单循环链表中，若知道指针p指向某结点，能否删除该结点，时间复杂度如何？

2.6下面算法的功能是什么？

LinkedListUnknown（LinkedListla）

{LNode*q，

1（la&&la->next）

；{q=la;la=la->next;p=la;

〔while（p->next）p=p->next;

p->next=q;q->next=null;

}

卜eturnla;一

}

2.7选择题：在循环双链表的*p结点之后插入*s结点的操作是（)

A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B、p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

Cs->prior=p;s->next=p->next;p->next:=s;p->next->prior=s;

Ds->prior=p;s>next=p>next;p>next->prior=s;p->next=s;

原：2.9设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有序链

表合并成一个非递增有序的单链表。要求使用原链表空间，表中无重复数据。

改：2.9设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有

序链表合并成一个非递减有序的单链表。要求使用原链表空间，表中无重复数据“

参考资料：

1.陈守孔等著《算法与数据结构C

语言版》机械工业出版社2007

2.陈守孔等著《算法与数据结构考研试题精析》

机械工业出版社2008

3•严蔚敏等著《数据结构C语言版》清华大学出版社2005

4.D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

讲授章节第4讲循环链表双链表

授课时数2

I

i

Q教学目的：

1•掌握循环链表引入的背景：从任一结点开始可以访问链表中的全部结点。

2•掌握循环链表(单循环链表，双循环链表)和双链表。

教学内容(讲授提纲)

1.比较顺序表和单链表操作的优缺点，使用范围。

2•介绍单循环链表。指出：单循环链表往往只设尾指针。

3.讲解两个只设尾指针的单循环链表合并成一个单循环链表的例子。

4.双链表的定义：

typedefstructDLNode

{ElemTypedata;

structDLNode*prior,*next;}DLNode,*DLinkedList;

5.双链表和双循环链表是两种链表。

6.线性表的操作在双链表中的实现

凡涉及一个方向的指针时，如求长度，取元素，元素定位等，其算法描述和单链表基本相同。

但是在插入或删除结点时，一个结点就要修改两个指针域，所以要比单链表复杂。由于双链表有两个

指针域，求前驱和后继都很方便。

6.算法设计举例：

(1)将单循环链表改为双循环链表

假设一个单循环链表，其结点含有三个域pre、data、next。其中data为数据域；pre为

0指针域，它的值为空指针(null)；next为指针域，它指向后继结点。请设计算法，将此表改成双向

循环链表。

voidSToDouble(LinkedListla)

{while(la->next->pre==null)

{la->next->pre=la;〃将结点la后继的pre指针指向la

la=la->next；//la指针后移

)

)"算法结束

(2)已知一双向循环链表，从第二个结点至表尾递增有序，(设a1<x<an)如下图。试

编写算法，将第一个结点删除并插入表中适当位置，使整个链表递增有序

voidDinsert(DLinkedListL)

{s=L；//s暂存第一结点的指针

P=L->next；//将第一结点从链表上摘下

p->prior=L_>prior；p->prior->next=p:

while(p->data<x)

p=p->next;〃查插入位置

s->next=p；〃插入原第一结点S

s->prior=p->prior；

p->prior->next=s；

p->prior=s;

〃算法结束

(3)链表的匹配逆置

L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字

母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。

LinkedListPatternlnvert(LinkedListL1,LinkedListL2)

{P=L1;//p是每趟匹配时L1中的起始结点前驱的指针

q=L1->next；//q是L1中的工作指针。

s=L2->next；//s是L2中的工作指针。

while(p!=null&&s!=null)

if(q->data==s->data)

{q=q->next;s=s->next;}〃对应字母相等，指针后移。

else//失配时L1起始结点后移，L2从首结点开始。

{P=P>next；q=p>next；s=L2>next；}

if(s==NULL”/匹配成功，这时p为L1中与L2中首字母结点相同数据域结点//的前驱，

q为L1中与L2最后一个结点相同数据域结点的后继。

{r=p->next;〃r为L1的工作指针，初始指向匹配的首字母结点。

p->next=q；〃将P与q结点的链接。

while(r!=q)；〃逐结点倒置。

{s=r->next；〃暂存r的后继。

r->next=p->next;〃将r所指结点倒置。

p_>next=r；

r=s;〃恢复r为当前结点。

}

}一

elseprintf(JL2并未在L1中出现”

)〃算法结束

本章节的教学重点、难点:

1.循环链表和双链表的概念。

2.难点是循环链表和双链表的应用算法设计。

教学方法、教学手段：

1•循环链表和双链表（45分钟）

2.算法设计（45分钟）

使用教具：计算机和投影仪

作业、讨论题、思考题：

2.10设la是一个双向循环链表，其表中元素递增有序。试写一算法插入元素x，使表中元素依然递增有

序。

改为：设la是一个双向循环链表，其表中元素递减有序。试写一算法插入元素x，使表中元素依然递减有序。

2.12设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次

察或偶次舞项，并要求利用原链表中的结点空间来构造这两个链表。

设循环链表表示的多项式的结点结构为：

typedefstructnode

{intpower;〃幕

floatcoef;〃系数

〃其他信息

ElemTypeother;struct

node*next;}PNode,*PolyLi〃指向后继的指针

nkedList:

2.18设la是带头结点的非循环双向链表的指针，其结点中除有prior>data和next夕卜，还有一访问频度域freq，

其值在链表初始使用时为0。当在链表中进行ListLocate（la，x）运算时，若查找失败，则在

表尾插入值为X的结点：若查找成功，值为x的结点的freq值增1，并要求链表按freq域值非增（递减）

的顺序排列，且最近访问的结点排在频度相同的结点的后面，使频繁访问的结点总是靠近表头。试编写符合上述要求

的ListLocate（la，x）运算的算法，返回找到结点的指针。

参考资料：

1•陈守孔等《算法与数据结构C语言版》机械工业出版社2007

箸•陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3♦严蔚敏等著《数据结构C语言版》清华大学出版社2005

4.D.E.Knuth著《计算机程序设计技巧》第管纪文译国防出版社

讲授章节第5讲线性表的算法设计举例

授课时数2

教学目的：

1.以线性表为具体例子深刻理解线性结构。

2.加深对算法设计的理解。

教学内容(讲授提纲)

1先.介绍线性表的应用：一兀n次多项式的表示。

2.选择题6——14

3.五个算法设计例子

(1)链表的逆置

(2)循环链表的分解

已知L为无头结点单链表中第一个结点的指针，每个结点数据域存放一个字符，该字

符可能是央文子母子符或数子子符或其它子符，编与算法构造一个以带头结点的单循环链表表示的线

性表，使每个表中只含同一类字符。(要求用最少的时间和最少的空间)

(3)删除有序链表中的重复元素

在一个非递减有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉

数值相同的元素，使表中不再有重复的元素。分析算法的时间复杂度。

(4)按序输出链表中各元素

设head是带头结点的单链表的头指针，试写出算法，按递增次序输出单链表中各结点的数据元

素，并释放结点所占的存储空间。要求不允许使用数组作辅助空间。

(5)链表的分解

将单链表L1拆成二个链表，其中以L1为头的链表保持原来向后的链接，另一个链表

的表头为L2，其链接方向与L1相反，L1包含原链表的奇数序号的结点，L2包含原链表

的偶物序号的结占。

本早节的教学重点、难点：

1•链表是本章重点。

2.难点是链表的算法设计。

教学方法、教学手段：

1.基本概念和算法(30分钟)

2.算法设计(60分钟)

使用教具：计算机和投影仪

作业、讨论题、思考题：

完成本章所留习题

参考资料：

1.陈守孔等著《算法与数据结构C语言版》机械工业出版社

2007

2.陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3•严蔚敏等著《数据结构C语言版》清华大学出版社2005

4.D.E.Knuth著《计算机程序设计技巧》第一'三卷管纪文译国防出版社

讲授章节第6讲栈

授课时数2

教学目的：

1理解栈和队列仍属于线性结构，其操作是线性表操作的子集，是操作受限的线性表。但从数据

类型的角度看，它们是和线性表大不相向的重要抽象数据类型。

2.掌握栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。

3.掌握栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。

4.栈的应用：表达式求值。

教学内容(讲授提纲)

1.栈的基本概念：栈、栈顶、栈尾，栈只在栈顶操作。

2•栈的抽象数据类型定义

3•顺序栈及栈的操作在顺序栈中的实现。

#defineMAXSIZE1024

typedefstruct

{ElemTypedata[MAXSIZE];

inttop;

}SeqStack；

4.双向栈的定义和使用

#definem64

typedefstruct

{ElemTypedata[m];

inttop[2];〃top[0],top⑴分别是两个栈的栈顶指针

JTStack;

5.链栈及栈的操作在顺序栈中的实现。

typedefstructStackNode

{ElemTypedata;

structStackNode*next;

JStackNode,*LinkedStack;

6.栈的应用

过程调用

递归

(1)使用栈进行数制转换十进制转为八进制

voidconversion()

{〃把十进制转换为八进制一一非递归

SeqStackS;intN;

S.top=-1;

scanf("％d,&N);

while(N)

|{S.data[++S.top]=N%8;

|N=N/8;一

while(S.top!=-1)

printf("%d',S.data{S}top

)

voidConvert(intn

{〃把十进制n转换为八进制--递归

计(n!=0)

|{Convert(n/8);

pritf("％d,n%8);

|}一

(2)中缀表达式的求值

算术表达式中运算符(+,・,*,/等)的优先规则

设置两个工作栈：运算符栈S1和操作数栈S2。S2存放表达式的运算结果。

算法思想:

1首先置操作数栈S2为空栈，置运算符栈的栈底为表达式的起始符#(优先级最低)。

2依次读人表达式的每个字符ch,直至表达式结束:

若ch是操作数，则进S2栈；

|若ch是运算符，若其优先级不高于栈顶运算符的优先级时，则取出栈S2的栈顶和

次栈顶的两个元素以及瓦5丁襁顶运算符'，进行租而的运算>笄恪结果放入栈S2中；如

此下去，直至ch的优先级高于栈顶运算符的优先级，将ch入S1栈。

本章节的教学重点、难点：

1.栈的概念和基础知识。

2.难点：中缀表达式求值，

教学方法、教学手段：

1.栈的基本概念和顺序栈(45分钟)

2.链栈、中缀表达式求值(45分钟)

使用教具：计算机和投影仪

作业、讨论题、思考题：

3.1有五个数依次进栈：1,2.3,4,5。在各种出栈的序列中，以3,4先出的序列有哪几

个。(3在4之前出栈)。

3.2.路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：L2,3,

4,5,6,那么是否能够得到435612,325641,154623和135426的出站序列，如果不能，

|说明为什么不能；如果能，说明如何得到(即写出“进栈"或“出栈”的序列)。

3.14双向栈S是在一个数组空间V[m]内实现的两个栈，栈底分别处于数组空间的两端。试

为此双向栈设计栈初始化Init(S)、入栈Push(S,i,x)、出栈Pop(S,i)算法，其中i为0或1,用以

指示栈号。

3.18设称正读和反读都相同的字符序列为“回文”，例如，“abba”和"abccba”是“回

文“'"abcde"和"ababab”则不是"回文"，试写一个算法，判别读人的一个以@为结

束符的字符序列是否是“回文”。

参考资料：

1.陈守孔等著《算法与数据结构C语言版》机械工业出版社2007

2.陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3•严蔚敏等著《数据结构C语言版》清华大学出版社2005

4.D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

讲授章节第7讲栈的应用递归

教学目的：

1.掌握栈的定义的本质：LIF。。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的

顶端。

授课时数2

0

2.掌握栈的应用：中缀表达式转为后缀表达式，并求值。

t

1

1

13.掌握递归过程的应用。

1

1

1

1教学内容(讲授提纲)

1

■

■

11.栈的本质是：LIFO。

1

1

1

12.中缀表达式转为后缀表达式

1

a1

i概念：前级表达式中级表达式，后缀表达式+ab,a+b,ab+

I

1

I卜设中级表达式和后缀表达式分别在向量IFX和PFX申，用栈S实现中缀式转为后缀

i

:式，对IFX中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述如下：

1

1

1栈初始化

1

o

从左到右扫描向量IFX，重复下述两步操作，直到表达式尾：

1

1

1①从IPX中取出下个TOKEN(数字、运算符、左括号、右括号)；

1

1

1②CASETOKENOF

1

I

I

1'('将TOKEN压入栈S;

1

1

1艮栈并将退栈兀素送直到碰到左括号，

1PFX•

1

1

a左括号退栈不送PFX。

1

1

l操作数：将操作数直接送入PFX;

i

■

■操作符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；否则，退栈并

i

1

1

1将退栈元素送入PFX，然后再将TOKEN与新栈顶元素比较之当遇到中缀表达式

1

■

Q结束符号，连续退栈并送退栈元素到PFX，直至栈空。

1

1举例：将中缀表达式8-(3+5)*(5-6/2)转为后缀表达式

1

1

1表达式转换的简单方法

1

■

1

1中缀表达式转为后缀表达式有三步：

1

1

■(1)加括号：将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来；

1

a

i(2)移运算符：顺序将每对括号中的运算符移到相应括号的后面；

i

l

1

I(3)删括号：删除所有括号。

i

i

i

i例如，将中缀表达式8-(3+5)*(5-6/2)转为后级表达式。按如上步骤：执行完上面第一步后

l

i

1为：(8-((3+5)*(5-(6/2))));

I

t

t

■执行完上面第二步后为：(8((35)+(5(62)/)-)*)-;

o

1执行完上面第三步后为：835+562/-*-。

1

1

1(2)对后缀表达式求值

用实型数栈S存放计算后缀式的中间及最终结果，求值算法可描述如下。

P=L；〃设局部变量p=L

while(p)

{printf(p->data);//输出结点的值

|p=p->next;〃向里一层修改变量值

)

}//Outputs

3)利用栈消除任何递归

利用栈可以将任何递归函数转换成非递归的形式，其步骤大致如下：

入栈处理

设一个工作栈代替递归函数中的栈，栈中每个记录包括函数的所有参数：函

数名'局部变量和返回地址。

所有递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。

修改确定本次递归调用时的实在参数之新值。

转到函数的第一个语句。

退栈处理

若栈空，算法结束，执行正常返回。

若栈不空，从栈中退出参变量赋给原来人栈时相对应的参变量，并退出返回地址。

转到执行返回地址处的语句，继续执行。

本章节的教学重点、难点：

1.中缀表达式转成前缀、后缀表达式,，并对两种表达式求值。

2•用递归解决的问题：问题的定义是递归的，数据结构是递归的，以及问题的解法是递归的，

掌握典型问题的算法。将递归算法转为非递归算法，特别是尾递归的消除。

教学方法、教学手段：

1.复习栈的基本概念、中缀表达式转为后缀表达式并求值(45分钟)

2.递归过程、消除递归(45分钟)

使用教具：计算机和投影仪

作业、讨论题、思考题：

3.7指出下面程序段的功能是什么？

(1)voiddemo1(SeqStackS)

{inti,arr[64],n=0;

while(IStackEmpty(S))arr[n++]=Pop(S);

for(i=0;i<n;i++)Push(S,arr[i]);

)

(2)voiddemo2(SeqStackS,intm)〃设栈中元素类型为int型

{intx;SeqStackT;

Stacklnit(T);

while(!StackEmpty(S))

if((x=Pop(S)!=m)Push(T,x);

while(!(StackEmpty(T)){x=Pop(T);Push(S,x);}