数据结构讲义3.doc

数据结构讲义第一章 绪论41.1 什么是数据结构51.2 基本概念和术语513 抽象数据类型的表示和实现814 算法和算法分析91.4.1 算法91.4.2 算法设计的要求：9第二章 线性表122.1线性表的类型定义122.2线性表的顺序表示和实现142.3线性表的链式表示和实现182.3.1线性链表182.3.2循环链表242.3.3双向链表2524一元多项式表示及相加26第三章 栈和队列293.1栈293.1.1栈的定义293.1.2栈的表示和实现293.2栈的应用举例313.2.1数制转换313.2.2.括号的匹配的检验333.2.3.行编辑程序333.2.4迷宫求解343.2.5表达式求值343.3栈与递归过程3534 队列383.4.1 抽象数据类型队列的定义383.4.2 链队列队列的链式表示和实现383.4.3循环队列-队列的顺序表示和实现40第四章 串424.1 串类型的定义424.2 串的表示和实现464.2.1定长顺序存储表示464.2.2堆分配存储表示49423串的块链存储表示534.3串的模式匹配算法554.3.1 求子串位置的定位函数 Index( S, T ,pos)554.3.2 模式匹配的另一种改进算法574.4 .1文本编辑62442建立词索引表64第五章 数组和广义表695.1 数组的定义695.2 数组的顺序表示和实现715.3 矩阵的压缩存储765.3.1 特殊矩阵765.3.2 稀疏矩阵775.4 广义表的定义9055 广义表的存储结构945.6 m元多项式的表示96第六章树和二叉树9961 树的定义和基本术语996.2 二叉树的定义1006.2 .1 二叉树的定义1006.2. 2 二叉树的性质103623 二叉树的存储结构10463 遍历二叉树和线索二叉树105631 遍历二叉树1056.3. 2 线索二叉树1096.4 树和森林1106.4.1 树的存储结构110642 森林与二叉树的转换112643 树的遍历11365树与等价问题11466 赫夫曼树及其应用117661 最优二叉树117662 赫夫曼编码1176.7 回溯法与树的遍历11868 树的计数118第七章 图1197.1图的定义和术语1197.2图的存储结构1217.2.1数组表示法1217.2.2邻接表1227.2.3 十字链表1247.2.4邻接多重表1267.3图的遍历1267.3.1深度优先搜索1277.3.2 广度优先搜索1277.4图的连通性问题1287.4.1无向图的连通分量和生成树1287.4.2有向图的强连通分量1287.4.3最小生成树12975 有序无环图及其应用130751 拓扑排序1317.5.2关键路径13276 最短路径134761 以某个源点到其余个顶点的最短路径1347.6.2 每一对顶点之间的最短举例137第八章 动态存储管理138第九章 查找1409.1 静态查找表1409.1.1顺序表的查找1409.1.3 静态树表的查找1429.1.4索引顺序表的查找1429.2动态查找表1449.2.1二叉排序树和平衡二叉树1449.2.2 B-树和B+树146注：若从根开始查找时，若非终端结点等于该关键字，并不停止，继续到叶子。1499.2.3 键树1499.3.哈希表1499.3.1什么是哈希表1499.3.2. 哈希函数的构造方法1519.3.3 处理冲突的方法1539.3.4 哈希表的查找及分析155第十 章 内部排序15810.1 概述158102 插入排序159103 快速排序161104 选择排序16210.4.1 简单选择排序1621042 数形选择排序16210.4.3 堆排序163105 归并排序163106 基数排序1641061 多关键字的排序1641062 链式基数排序165107 各种内部排序方法的比较讨论166第十一章 外部排序16811.1 外存信息的存取16811.2外部排序的方法169第十二章 文件17112.1. 有关文件的基本概念17110.2 顺序文件17212.3 索引文件17212.4 ISAM文件和VSAM文件17312.4.1 ISAM文件17312.4.2 VSAM文件17412.5 直接存放文件（散列文件）17412.6 多关键字文件17412.6.1 多重表文件17412.6.2 倒排文件174第一章 绪论计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系产生背景。第二章：数据的线形关系 线性表、一元多项式的计算第三章： 栈与队列第四章：串 字符串的压缩存储、模式匹配第五章：数组 广义表 矩阵的表示及计算法、稀疏矩阵处理第六章：树和二叉树目录结构、文件结构 第七章：图 网络拓扑、工程网络第八章：动态存储管理 （OS简单介绍）第九章：查找第十章：排序第十一章：文件主要参考资料： 1EHorrowitz and S.sahni, Fandamentals of Dafa strucfares,by pimen Publishing limited.1976. 2. 数据结构 国防科技大学出版 王广芳 3数据结构 电子科技大学出版社 潘道才 陈一华4数据结构及应用算法教程 清华大学出版社 严蔚敏5数据结构（用面向对象示方法与C+描述） 清华大学出版社6、数据结构（C语言描述）与清华大学严蔚敏配套1.1 什么是数据结构计算机解题步骤：建立数学模型设计解此数学模型的算法编制程序进行测试调整解答其中建立数学模型的实质：找出操作对象之间的关系。例1 图书馆书目检索 对应线性关系例2 博奕树 对应树型关系例3 交叉路口交通灯管理 对应图状结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。（地位）1.2 基本概念和术语l 数据（Data）：是对客观事物的符号表示。可以输入到计算机的符号的总称； 计算机加工的原料。包括数值、字符、声音、图象等。l 数据元素（Data Element）：是数据结构的基本单位。作为逻辑整体进行处理。一个数据元素可由若干个数据项组成（Data Item）。l 数据对象（Data Object）：性质相同的数据元素的集合，是数据的一个子集 如N=0,1,2,是整数数据对象。l 结构（Structure）：数据元素相互之间的关系。有四种基本结构 集合：松散的关系。 线形结构：一一对应的关系。 树型结构：一对多的关系。 图状结构（网状结构）：多对多的关系。数据结构的形式定义：数据结构是一个二元组 Data_structure=(D,S) 其中：D为数据结构的有限集，S是D上关系的有限集。例：复数结构Complex=(C,R)其中：C为含两个实数的集合c1,c2；R=P，P是集合C上的一种关系， P=，为有序偶，c1表示复数的实部，c2表示复数的虚部。数学模型 抽象数据类型 建立数据结构 编写源程序 逻辑结构物理结构（存储结构）是数据元素及关系在计算机中的表示。元素（Element）可以看成数据元素在计算机中的映象。数据元素之间的关系在计算机中有两种表示方法：顺序映象和非顺序映象。并由此得到两种不同的存储结构：顺序存储结构和非顺序存储结构。 顺序结构用元素在存储器中的相对位置表示数据元素之间的逻辑关系。 非顺序映像借助指示元素存储地址的指针表示元素之间的逻辑关系。一维数组来描述顺序存储结构，用指针来描述链式存储结构。需要指出的是：本书讨论的存储结构是数据结构在C虚拟处理器中的表示，称为虚拟存储结构。l 数据类型（Data Type）：一个值的集合和定义在这个值集上的一组操作的总称。 一个值集和运算符集数据类型是描述操作对象的特性，规定变量的取值范围以及允许的操作。 原子类型：值不可分解。如C中的基本类型（整型，字符型） 结构类型：若干成分按某种结构组成，可以分解。使用类型增加了透明性。l 抽象数据类型（Abstract Data Type ）：一个数学模型以及定义在该模型上的一组操作。广义的数据结构。包括系统定义的数据类型和用户设计软件时自己定义的数据类型。在现代程序设计方法学中为提高软件的可重用性，设计建立在数据之上的软件框架。面向数据即数据对象。称之为面向对象的程序设计方法（Object Oriented Programming）OOP语言，而传统的软件是面向操作的程序设计。ADT分类： 原子类型（Atomic Data Type）：变量的值不可分解，如定义数值为100的整数 固定聚合类型（Fixed-aggregate Data Type）：由确定数目的成分按某种结构组。如记录成分 结构类型 可变聚合类型(Variable-aggregate Data Type)：值的数目不固定。如一个序列，其中序列的长度可变。抽象数据类型，可由固有的数据类型表示和实现。ADT的形式可用三元组表示，ADT（D，S，P） 其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT 抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名基本操作的定义格式：基本操作名（参数表）初始条件：操作结果：参数有两种：赋值参数 和 引用参数（以打头） 形参值传递指针地址传递例：P913 抽象数据类型的表示和实现操作， cnef(x,y,z) z=s+iy ADT complex add(z1,z2,sum) 数据对象D=c1,c2|c1,c2RsabTracf(z1,z2,difference)数据关系:R1+mulfiply基本操作: Cnenat (x,y,z,)Get_reipant(8) subtract(z1,z2,difference)Get (magepart(8) subtract(z1,z2,priduct)ADT anplex实现：（借助于高级语言）对象方法一，使用面向对象的语言，如标准C，用户的自定义类型，函数入，方法二，用Ada和Msdule-2提供模块（包）的结构，每个模块可争编译。TaRBOC，unit（单元）提供用户可的接口，而内部是透明的，方法三，面向对象的程序设计方法，类本书采用C的伪码，P1014 算法和算法分析1.4.1 算法算法（Algorithm）：对特定问题的求解步骤的描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性：1有穷性：对任何合法的输入值执行有穷步之后结束，且每一步都在有穷时间内完成。2确定性：算法中每一条指令必须有确切的含义，没有二义性。在任何时候，只有唯一的一条执行路径（即对相同的输入得到相同的输出）。3可行性：一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。4输入：一个算法有零个或多个输入，这些输入取自于特定的集合。5输出：一个算法有一个或多个输出，这些输出是同输入有某些特定关系的量。（执行的时间和空间）算法的描述：用C的伪码描述。1.4.2 算法设计的要求： 1正确性（Correctness）输入、输出无歧义。2可读性（Readability）使人能够阅读，便于调试和修改。3健壮性(Robustness)输入非法数据时，算法能适当地作出反应 或进行处理，不会使系统崩溃。4高效率与低存储量需求 算法效率的度量：事后设计；事前分析估算。消耗时间的因素：算法的选用系统；问题的规模；书写程序的语言；编译程序所产生的机器代码的质量；机器执行指令的速度。一个算法由控制结构（顺序，分支，循环）和原操作（特定的数据类型的操作）构成，通常从算法中选取一种对于所研究的问题来说是基本操作的原操作，以基本操作重复执行的次数为算法的时间参数。如：NN矩阵抽象的算法for(i=1;i=n;+i) 整个算法的执行时间与基本操作（乘法）for(j=1;j=n;+j)重复执行的次数n3成正比，记作T(n)=O(n3) ci j=0; for(k=1;k=n;+k) ci j+=aj j*bjk ;一般情况下，算法中基本操作重复执行的次数是问题规模的某个函数f(n)，算法的时间度量记作 T(n)=O(f(n) 它表示随的增大，T(n)的增长率和f(n)的增长率相同，称为渐近时间复杂度，简称时间复杂度。例: +x;s=0; T(n)=O(1) for(i=1;i=n;+i) +X; s+=x; T(n)=O(n) for(j=1;j=n;+i) for(k=1;k=n;+k) +x;s+=x; T(n)= O(n2) for(i=1;i=n;+i) for(j=2; j=i-1;+j) x:=x+1 T(n)=O(n2)有时取最坏情况下的时间复杂度，如排序操作。P16图空间复杂度： S(n)=O(f(n)图灵奖。策略1，2n次，最(2n-1)+(2n-3)+-+5+3 +(n-1)=n2+n-2 次 策略2，n+n=2n次 0(n)第二章 线性表线性结构的特点：在数据元素的非空有限集中， 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，集合中的每个元素均只有一个前驱； 除最后一个元素之外，集合中的每个元素均只有一个后继。2.1线性表的类型定义线性表：一个线性表是n（n0）个数据元素a1，a2.an的有限序列。表中元素除第一个和最后一个外有且仅有一个直接前驱和一个直接后继。线性表或是一个空表，或可以写成（a1，a2an） 如（10，20，5，7，9）是一个线性表若一个数据元素由若干个数据项组成，则称该数据元素为记录。含有大量记录的线性表称为文件，如学生登记表。同一个线性表中的元素必定具有相同的结构，即属同一数据对象，相邻数据元素之间存在序偶关系ai-1，ai表示相邻关系，若将线性表写成（a1，a2an）ai是线性表中的第i个元素，i为元素ai在线性表中的位置（位序），n为线性表的长度。线性表的ADT定义 P19对上述定义的线性表ADT还可进行复杂操作例21Void union (List &La, List Lb) La_len= ListLength (La); Lb_len= ListLength (Lb); For (i=1;i= Lb_len;i+)GetElem (Lb,i,e); If(!LocateElem(La,e,equal) ListInsert(La,+ La_len,e); O(Listlength(LA)* Listlength(LB)例22Void MergeList(List La,List Lb,List &Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength (Lb);While(i=La_Len)&(j=Lb_len) GetElem(La,i,ai);GetElem(Lb,j,bj); If(ai= bj)ListInsert(Lc,+k, ai);+i; Else ListInsert(Lc,+k, bj);+jwhile (i=La_len) GetElem(La, i+, ai);ListInsert(Lc, +k, ai);while (j=Lb_len) GetElem(Lb, i+, bj);ListInsert(Lc, +k, bj);2.2线性表的顺序表示和实现线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。设线性表的每个元素需要L个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表第i+1个数据元素的存储位置LOC（ai+1） LOC（ai+1）=LOC（ai）+L一般的 LOC（ai）=LOC（a1）+（i1）*L以元素在计算机内“物理位置相邻”来表示元素之间的逻辑关系，每一个元素的存储位置与起始位置相差一个与位序成正比的常数。它是一种随机存取的数据结构。#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct ElemType *elem; Int length; Int listsize;SqList;Status IniList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;Return OK;在这种结构中容易实现随机存取第i个数据元素，C语言中数组的下标从0开始，所以ai应在L.elem i-1中存取。线性表的插入操作，在第i-1个元素和第i个元素之间插入元素b，即（a1ai-1,aian）变成长度为n+1的线性表（a1ai-1,b,aian）。由于逻辑上相邻，物理位置也必须相邻，因此要移动n-i+1个元素。只有当i=n+1时不需移动元素。Status ListInsert_sq(sqList &L, int i, ElemType e)If(i=L.length+1) return ERROR;If(L.length=L.listsize)newbase=(ElemType*)realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType);If(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK插入元素时，时间主要耗费在移动元素上。移动个数取决于插入位置。设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线形表中插入一个元素时所需移动元素次数的期望值为删除元素：删除第i个元素（1in时需将从第i+1至第n（共n-i）个元素依次向前移动一个位置。Status ListDelete_Sq(sqList &L,int i,ElemType &e)If( (iL.length) ) return ERROR;P=&(L.elemi-1);e=*p; q=L.elem+L.length-1;For(+p; p=q; +p) *(p-1)=*p;-l.Length;return OK;设qi为删除第 i个元素的概率，则长度为n的线性表中删除一个元素时所需移动元素的期望值为 。假定在任何位置上插入和删除都是等概率的，即，则上述两式可简化为，。在顺序表中查找元素的算法：int LocatElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType, ElemType)i=1;p=L.elem;While (i=L.length & !(*compare)(*p+,e) +i;If (i=L.length) return i;else return 0;合并线性表：Void MergeList_Sq(SqList La, SqList Lb, SqList &Lc )Pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;Pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe);If (!Lc.elem) exit (OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;While (pa=pa_last & pb=pb_last) If (*pa=*pb) *pc+=*pa+; Else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+;while(pbnext=NULL。查找元素的算法：StatusGetElem_L(LinklistL,inti,ElemType&e)P=L-next;j=1;While(p & jnext;+j;if( !p ji)returnERROR;e=p-data;returnok;基本操作的频度：i-1如查不到，频度为n。时间复杂度为O(n)单链表的插入和删除：插入：s-next=p-next;p-next=s;删除：p-next=p-next-next;插入、删除：O（n）StatusListInsert_L(Linklist&L,inti, ElmeTypee)p=L;j=0;While( p & jnext; +jIf( !p ji-1)returnERROR;s=(Linklist)malloc(sizeof(LNode);s-data=e; s-next=p-next; p-next=s;returnOK;StatusListDelete_L(Linklist&L,inti,Elemtype&e)p=L;j=0;While( p-next & jnext; +j;if( !(p-next) ji-1)returnERROR;q = p-next; p-next=q-next;e = q-data; free(q);returnOK;动态存储：malloc()free()从表尾到表头逆向建立单链表：voidCreateList_L(Linklist&L,intn)L=(Linklist) malloc(sizeof(Lnode);L-next=NULL;For(i=n; i0; -i)p=(Linklist)malloc(sizeof(Lnode);scanf(& p-data);p-next=L-next; L-next=p;合并单链表：voidmergelist_L(Linklist&La,Linklist &Lb, Linklist&Lc)pa=La-next; pb=Lb-next;Lc=pc=La;While( pa & pb)if( pa-data data)pc-next=pa; pc=pa; pa=pa-next;else pc-next=pb; pc=pb; pb=pb-next;pc-next= pa ? pa : pb;free(Lb);与2.7相比，时间复杂度相同，空间复杂度为O（1）用一维数组来描述线性链表：defineMAXSIZE1000typedefstructElemTypedata;intcur;component,SlinkListMAXSIZE;设S为SlinkList型变量，则S0.cur指示第一个结点在数组中的位置，设i=s0.cur，则si.data存放线性表的第一个元素，且si.cur指示第二个结点在数组中位置。一般情况，若第i个分量表示链表的第k个结点，则si.cur指示第k+1个结点的位置。在静态链表中以整型游标i代替动态指针p，i=si.cur类似于p=p-next。定位函数：intLocateElem_SL(SlinkLists, ElemTypee)i=s0.cur;while( i & si.data!=e)i=si.cur;returni;在静态链表中，函数malloc和free需用户自己编程实现。例：（AB）（BA）P33页A=(c,b,e,g,f,d)B=(a,b,n,f)voidIniteSpace_SL(SlinkList&space)for(i=0; iMAXSIZE-1; +i) spacei.cur=i+1;spaceMAXSIZE-1.cur=0;intMalloc_SL(SlinkList&space)i=space0.cur;if(space0.cur) space0.cur=spacei.cur;return i;void Free_SL(Slinklist &space,jint k) spacek.cur=space0.cur; space0.cur=k;voiddifference(SlinkList&space,int&s)InitSpace_SL(space);/初始化备用空间S=malloc_SL(space);/生成s的头结点r=S;/r指向s的当前最后结点scanf(m, n);for(j=1; j=m; +j) /建立集合A链表i=malloc_SL(space);Scanf(spacei.data);Spacer.cur=i; r=i;spacer.cur=0;/尾结点指针为空for(j=1; jnext=H常设立尾指针，合并二个表方便。运算时间O(1)2.3.3双向链表在单链表中，NextElem的执行时间为O(1),PriorElem的执行时间为O(n)。为克服该缺点，利用双向链表typedefstructDulNodeElemTypedata;StructDulNode*prior,*next;DulNode,*DuLinklist;结点结构：priorelementnext设d为DuLinklist型变量，则有d-next-prior = d-prior-next = d。在双向链表中，ListLength、GetElem和LocateElem仅仅插入和删除操作不同，在双向链表中需同时修改两个方向上的指针。删除操作：图2.15 插入操作：图2.161.p-prior-next=p-next1.s-prior=p-prior;2.p-next-prior=p-prior2.p-prior-next=s;3free(p)3.s-next=p;4.p-prior=s;注意：1、2、4步执行顺序不能换算法：P3624一元多项式表示及相加Pn(x)=p0+p1x+p2x2+pnxn，它由n+1个系数唯一确定。因此可用一个线性表P来表示：P（p0，p1，pn）设Q为一元m次多项式，可表示为Q（q0,q1,qm）。设mn,则两个多项式相加的结果Rn(x)=Pn(x)Qm(x)可用线性表R表示：R（p0+q0,p1+q1,pm+qm,pm+1,pn）若采用顺序存储结构表示时，处理如S(x)=1+3x10000+2x20000的多项式时，需用长度为20001的线性表表示，表中仅有三个非零元素，这样对空间浪费很大。一般情况下，一元n次多项式可写成Pn(x)=p1xe1+p2xe2+pmxem0e1e2em=n若用一个长度为m且每个元素ai（i=1,m）有两个数据项（包含一个表示函数实数和一个表示指数的整数）的线性表(p1,e1),( p2,e2),( p3,e3)(pm,em)，便可唯一确定多项式Pn(x)。在最坏情况下，n+1个系数都不为零，则存储空间为2（n1）。对上述结构可采用顺序结构也可采用链式结构，若只是求值，不改变系数和指数，则可采用顺序存储结构，否则使用链式结构。ADT定义：P40如A17（x）=7+3x+9x+5x17和B8(X)=8X+22X7-9X8相加，设qa和qb分别指向当前比较的某个结点，一元多项式相加规则： 若qa的指数qb的指数,将qb所指结点加入到“和多项式”链表中，指针后移； 若qa的指数=qb的指数,则系数相加，若和不为空，修改qa所指结点系数，释放qb，qa、qb所指结点指针后移；若和为空，释放qa、qb所指结点。时间复杂度为O（m+n）多项式相乘：M(x)=A(x) B(x) =A(x)b1xe1+bnxen=biA(x)xeiA(X)的每一项都是一元多项式voidAddPolyn(polynomial&pa, polynomial&pb)ha=pa; hb=pb;qa=pa-next; qb=pb-next;while(qa & qb)a=qa-data; b=qb-data;switch(*comp(a.expn,b.expn) case-1: ha=qa;qa=qa-next;break;case0 : sum=a.coef+b.coef if(sum!=0.0)a.coef=sum; ha=qa;else ha=qa; free(qa);hb=qb; free(qb); qb=hb-next;qa=ha-next; break;case1 : hb-next=qb-next; ha-next=qb;qb-next=qa; ha=ha-next;qb=hb-next; break;if(!Empty(pb) ha-next=qb;free(hb);intcomp(terma, termb)ifabreturn1;elseifa=breturn0;elsereturn1;第三章 栈和队列栈和队列是定义在线形结构中操作受限的线性表，是一种限定性的数据结构。3.1栈3.1.1栈的定义栈（stank）是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶（top），表头称为栈底（bottom）。不含元素的空表称为空栈。设S=(a1,a2,an)表示栈，则a1为栈底元素，an 为栈顶元素。栈是一种后进先出（Last In First Out）的线性表（简称LIFO结构）。栈只能对栈顶元素进行插入和删除操作。例：若输入 A，B，C，D。可能的输出序列为D，A，C，B （错）、B，A，C，D（对）、D，C，A，B（错）、B，C，A，D（对）、A，C，B，D （错）ADT：P443.1.2栈的表示和实现栈也可以用两种存储结构来表示。栈的顺序存储结构：用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，top指示栈顶元素在顺序栈中的位置。一般用top=0表示空栈，但C语言中数组的下标从0开始，会有很大不便。一般来说，在初始化空栈时不应限定栈的最大容量。栈的定义如下：typedef struct SElemType * base; SElemType *top; Int stacksize; /栈可使用的最大容量 Sqstack;按初始分配量进行第一次存储分配，base为栈底指针，始终指向栈底。Top为栈顶指针，初值指向栈底，每插入一个元素，top增1；每删除一个元素，top减1，top始终在栈顶元素的下一个位置上。Status InitStack (SqStack &S) S.base=(SElemType &)malloc (STACK_INIT_SIZE *sizeof(SElemType);If (! S.base) exit (OVERFLOW);S.top=S.base; S.stacksize=STACK_INIT_SIZE;return OK;Statur GetTop(SqStack S, SElemType &e)if (S.top = S.base) return ERROR;e= * (S.top-1);return OK;Status Push(SqStack &S, SElemType e)if (S.top - S.base= S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S, SelemType &e)If( S.top=S.base) return ERROR;e=*-S.top;return OK;栈的链式表示：P47 图3.33.2栈的应用举例3.2.1数制转换十进制数N和其它d进制数的转换：N= (N /d) * d+ N % d如(1348)10=(2504)8NN / 8N % 8134816841682102125202void conversion()InitStack(S);scanf(“%d”,&N);while(N)Push(s, N % 8 );N=N / 8;while( !StackEmpty)Pop(S,e);printf(“%d”,e);3.2.2.括号的匹配的检验 （ ） 1 2 3 4 5 6 7 83.2.3.行编辑程序假设退格符“#”，退行符“”如输入以下两行字符：whli#ilr#e(s#*s)outchaputchar(*s=#+);则实际有效的是：while(*s)puchar(*s+);void LineEdit()InitStack(s);ch=getchar();while(ch!=EOF)while(ch!=EOF & ch!=n)switch(ch)case#: Pop(S,ch);case: ClearStack(S);default: Push(S,ch);ch=getchar();ClearStack(S);if(ch != EOF) ch=g