徐士良《计算机软件技术基础》（第4版）笔记和课后习题详解.docx

目录内容简介目录第1章预备知识1.1 复习笔记1.2 课后习题详解第2章基本数据结构及其运算2.1 复习笔记2.2 课后习题详解第3章查找与排序技术3.1 复习笔记3.2 课后习题详解第4章资源管理技术4.1复习笔记42课后习题详解第5章数据库设计技术5.1 复习笔记5.2 课后习题详解第6章编译技术概述6.1 复习笔记6.2 课后习题详解第7章应用软件设计与开发技术7.1 复习笔记7.2 课后习题详解第1章预备知识1.I复习笔记、集合基本概念集合是指若干个或无穷多个具有相同属性的元(元素)的集体。通常,个集合名称用大 写字母表示,而集合中的某个元素用小写字母表示。如果集合M由n (n>0)个元素a“& ，a”组成,则称集合M为有限集。如果个集合中有无穷多个元素,则称此集合为无 限集。不包括任何元素的集合称为空集。空集通常用表示。如果M是个集合,a是集 合M中的一个元素,则记作aGM,称元素a属于集合M;如果a不是集合M中的元素,则记 作a£M,称元素a不属于集合M。(1)列举法用列举法表示一个集合是将此集合中的元素全部列出来，或者列出若干项但能根据规律可 知其所有的元素。例如:大于1而小于100的所有整数的集合A可以表示为A=2, 3, 4, ., 99(2)性质叙述法用性质叙述法表示一个集合是将集合中的元素所具有的属性描述出来。例如:大于1而小于100的所有整数的集合A可以表示为A=a| l<a <10()的所有整数设M与N为两个集合,若M中的每个元素也为N的元素，则称M为N的子集,记作MUN, 若MUN且N中至少有一个元素a£M,则称M为N的真子集，记作MuN。基本运算(1)两个集合的并设有两个集合M和N,它们的并集记作M UN,定义如下： MUN=a|aCM 或 a£N(2)两个集合的交 设有两个集合M和N,它们的交集记作MAN,定义如下:MDN=a| aWM且aGN 两个集合M和N的并、交均满足交换律,即M U N=N U M MnN=NDM (3)两个集合的差设有两个集合M和N,它们的差集记作M-N,定义如下:M-N=a|aCNHlla£N 两个集合的差不满足交换律,即M-N 声N-M 对于集合的并、交、差有以下几点基本性质: 结合律(acib) nc=An (Bnc)(AUB) UC=AU (BUC)分配律AD (BUC) = (ACIB) U (AClC)AU (Bnc) = (AUB) n (AUC)(A-B)U<B-A) = (AUB)-(AnB) BCKA-B) = 0(AAB)U(A-B)=A其他(4)映射映射的相关概念如下:设A、B是两个非空集，如果根据一定的法则f,对于每个xGA,在B中都有唯一确定 的y与之对应，则称f为定义在A上而在B中取值的映射,记作f： AB,并将x与y的关系记 作y = f(x) , x称为自变元,y称为在f作用下x的像;设给定映射f： A-B,且B = f (A),若对于每个yCB仅有唯一的xWA使f (x)= y,则称隋逆映射;若A、B两个集合有映射帝在,使f (A)= B,则称A与B成对应,A与B对等,记作AB。 集合的对等具有以下性质:自反性:AA；对称性:若AB,则BA；传递性：若AB且BC,则AC。自然数集与数学归纳法由所有自然数组成的集合1, 2, 3,称为自然数集。自然数集是一个无限集。由自然 数组成的集合均是自然数集的子集。自然数集的子集可以是有限集,也可以是无限集。它 们具有如下性质:(1)在自然数集的任一非空子集M中,必定有一个最小数;(2)设M是由自然数形成的集合,如果它含有1, 2, ., k,并且当它含有数n-1, n-2, ., n-k (n>k)时,那么它含有所有的自然数，即M是自然数集。笛卡儿积0! x D2 X X D = (,)I d, e D,U = 1,2,”设有n个集合D“ D2, ., D,此n个集合的笛卡儿积定义为其中(4,d)称为n元组,d称为n元组的第i个分量。由笛卡儿积的定义可以看出,n个集合的笛卡儿积是以n元组为元素的集合,而每个n元 组中的第i个分量取自于第i个集合D,。二元关系(1)笛卡儿积设M和N是两个集合,则其笛卡儿积MxN=(x, y)|xGNyGN)其中每个子集称为在MxN上的个二元关系。如果M = N,则其笛卡儿积MxM=(x, y) I x, y£M其中每个子集称为在集合M上的个二元关系,简称为在集合M上的一个关系。(2)前后件、自反、对称与传递设R是集合M上的一个关系：如果(a, b) GR1则称a是b的关于R的前件,b是a的关于R的后件;如果对于每个aCM,都有(a, a) CR,则称关系R是自反的:如果对于任何aM, (a, a) GR均不成立,则称关系R是非自反的；如果（a, b） CR时必有（b, a） GR,则称关系R是对称的;如果当（a, b） WR且（b, c） eR时必有（a, c） eR,则称关系R是传递的。（3）基与传递体设R是M上的个传递关系,且TUR,若对于任何（x, y） GR,在M中有元素x。,x., x2 ,x （n>l）满足: Xo=X; xn=y；（x» Xi） GT （i=l, 2, n）则称关系T是关系R的基,又称关系R是关系T的传递体。基本概念算法是指解题方案准确而完整的描述。算法具有如下基本特征:（1）能行性算法的能行性包括以下两个方面:算法中的每个步骤必须能够实现;算法执行的结果要能够达到预期的目的。（2）确定性算法的确定性,是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释 ,也不允许有多义性。（3）有穷性算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之 后终止。算法的有穷性还应包括合理的执行时间的含义。（4）拥有足够的情报个算法是否有效,还取决于为算法所提供的情报是否足够。综上所述，算法是组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明 确的,此顺序将在有限的次数内终止。基本方法（1）列举法列举法的基本思想是:根据提出的问题,列举所有可能的情况,并用问题中给定的条件检 验哪些是需要的,哪些是不需要的。列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会 很大,因此需要对算法进行优化。(2)归纳法归纳法的基本思想是,通过列举少量的特殊情况,经过分析，最后找出一般的关系。(3)递推法递推法是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。(4)递归法递归法的基本思想是在解决了逐层分解到最后的那些最简单的问题后,再沿着原来分解的 逆过程逐步进行综合。递归分为直接递归与间接递归两种。如果个算法P显式地调用自己则称为直接递归。如 果算法P调用另个算法Q,而算法Q又调用算法P,则称为间接递归调用。(5)分治法(减半递推技术)分治法,即对问题分而治之。工程上常用的分治法是减半递推技术。"减半是指将问题的 规模减半,而问题的性质不变。"递推''是指重复"减半''的过程。(6)回溯法通过对问题的分析,找出个解决问题的线索，然后沿着这个线索逐步试探。对于每步 试探,若试探成功,就得到问题的解;若试探失败,就逐步回退，换别的路线再进行试探。复杂度分析算法的复杂度主要包括时间复杂度和空间复杂度。(1)时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。客观地反应算法的效率可以用算法在执行过程中所需基本运算的执行次数来度量算法的 作量。而算法所执行的基本运算次数是问题规模的函数,即算法的工作量f (n)。其中n 是问题的规模。方法在同一问题规模下,如果算法执行所需的基本运算次数取决于某特定输入时,可以用以 下两种方法来分析算法的工作量。a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。 设X是所有可能输入中的某个特定输入，P(X)是X出现的概率，t(X)是算法在输入为X 时所执行的基本运算次数,则算法的平均性态定义为A(n) = / pwd”b.最坏情况复杂性W(打)=max(x) 了最坏情况分析是指在规模为n时,算法所执行的基本运算的最大次数。它定义为:(2)空间复杂度个算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以 及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元 以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数, 则称该算法是原地工作的。1.2课后习题详解集合M = d” d2> d3»,ds, 4上的一个关系R如下:R= (di, d2) , (d2, d&) , (d5, d4) , (di, d5) , (di, th) , (di, d6) , (di, d3 ),(d3, d6)试验证Ti= (d, d2) , (d2, 0(), (di, d3) , (&, &) , (d5, &) , (di, d5) 是 R的具有6个元素的基,而T2= (d2, d4) , (di, d3) , (di, d2) , (ds, ds) 不是R的 基。答:对于T”显然满足T£R,且对于关系R中的每一个二元组(x, y),在M中存在元素RX0，2（,）d , dz(di,dz)£Ti(dz,)dz 9d4（,）6%（ds,）d$ 9 d4（,）6。(dltd5)di0,4)£Ti(dt,d.)d 9 dz, d(.d ydz) »Cdz ,d&) W T（,）（,），（,）er（,&）d !6?3（4，4）GT】（4，）4（,）Xo, Xi, X2, ., X,满足基的三个条件。验证过程如下：由上可知,是R的具有6个元素的基。对于T”由于（do, ds） 0R,因此,T2不是R的基。设给定三个整数a, b, c,试写出寻找其中数的个算法（用C/C+描述）,并分析在平 均情况与最坏情况下,算法分别要进行多少次比较?答:算法的C+描述如下:/'chl.qjpincludeciostreanusing namespace std;int mid(int a,int b,int c)(intm;m=a;,吁页设a为中数if(m>=b)(if(m>=c)(if(b>=c) m=b; /b 为中数else m=c; c 为中数)else(if(m<=c)(if(b>-c) m=ci c 为中数else m=b; /b 为中数)return (m);j返回中数假设a, b, c中的每一个数为中数的概率相等(均为1/3)。由于当a为中数时需要比较2次2X(l/3)+3X(l/3)+3X(l/3) = 8/3,b或c为中数时均需要比较3次,因此,在平均情况下上述算法所需要的比较次数为即在平均情况下，上述算法需要比较(8/3)次。在最坏情况下,上述算法需要比较3次(当b或c为中数时)。主函数例如下:intmain()(int a,b,c;cout«" input 丄 b,c="；cin»a»b»c;cout«"m="«mid(a,b,c)«endl;return 0;运行结果如下(带有下划线的为键盘输入)：input a,b,c=4 8 3m=4利用减半递推技术,写出求长度为n的数组中最大元素的递归算法(用C/C+描述)。设n =2k,其中kNl。答:利用减半递推技术,求数组中最大元素的递归过程如下:如果数组中只有一个元素, 则该元素即是数组中最大的元素。否则将数组对分为前半部分和后半部分：用同样的方法求数组前半部分的最大值maxi。用同样的方法求数组后半部分的最大值max 2若maxl>max2,则maxi为数组中的最大值;否则max2为数组中的最大值。算法的C+描述如下：chl_2.cpp?mclude<iostream>using namespace std;int maxa(int a,int m,int n)(intd5dl,d2;if(m=n) return (am-l);else(d 1 =maxa( a1ms (m-n) 2);d2=maxa(a,(m*n),2+l sn);if(dl>d2)d=dl;elsed=d2;return (d);主函数例如下：int main()(mt a( 16 卜15,6,4“ 521,737851.40 6,43,49,6327; cout«"max-"maxa(i, 1,16)«ajdl,return 0;)运行结果如下:max=78编写二分法求方程实根的减半递推算法(用C/C+描述)。/chl_3.cpp include<iostream> mclude<cmath> using namespace std;double root(double a,double bdouble eps, double (*f)(double) (doublewhile( fabs( a-b)>=eps) (c=(a*b) 2;n«(*fXc)；if(fl+1.01.0)答:算法的C+描述如下:retum(c);if(f0*fl>0)a=c;取区间后半部分elseb=c;。取区间前半部分)c=(a*b) 2;retum(c);)主函数例如下:int main。(double a=0.0,b=3.0;double f( double);cout«root(丄 b,0.0000IQvvendl;return 0;)double f(double x)(return(x*x*x-x*x-1.0);)运行结果如下:1.46557编写用回溯法求解皇后问题的算法（用C/C+描述）。 答:算法的C+描述如下:chl_4 cpp#include<iostream>2?include<iomanip>#include<cmath>using namespace std;void queen(int n)(inti,j,k,jt,*q;q=nexv intn;for(i=0;i<n;i-Hh)qi=0；i-0;jt=l；cout«n«?,queen problem?,«endl;while(jt=l)(k-0;while(k<i)&&(qk-qi)*(febs(qk-qi>fabs(k-i)!M) kfif(k<i)砒 else i-i+1;(for(j=0j<nj+)cout«setw(5)«qj+l;cout«endl;qn-l=qn-l+l;i-n-1;) else (q«-o； "-1;(cout«endl;delete q;return;)qi-qW+l；1主函数例如下:int main()intn;cout«T,mput nr； cin»n;queen(n);return 0;)运行结果如下:(带有下划线的为键盘愉入)input n:44queen problem2 4 133 14 2设有12个小球。其中11个小球的重量相同,称为好球;有一个小球的重量与11个好球的 重量不同(或轻或重),称这个小球为坏球。试编写个算法(用C/C+描述),用个 无祛码的天平称3次找出这个坏球,并确定其比好球轻还是重。答:用个长度为12的整型数组A (1： 12)模拟表示编号分别为112的12个小球,其中 的元素值分别是各小球的重量。即在这个整型数组中,11个元素值是相同的,称为好元素 !只有一个元素的值与11个好元素值不同(其值或大或小),称为坏元素。下面通过对数组中元素值的比较来找出这个坏元素。具体比较过程如下。首先将12个元素分成以下三组:第一组为A (1) , A (2) , A (3) , A (4)四个元素;第二组为A (5) , A (6) , A (7) , A (8)四个元素;第三组为A (9) , A (10) , A (11) , A (12)四个元素。3次比较过程如表1-1所示。表1-1比较过程第一次比较第二次比較第三次比較若A+A(2) +A (3) +A (4) =A (5) +A (6) +A (7) +A (8) 则 A(9),A(10), A(11), A(12) 中有坏若 A(l) +A(9) =A (10) +A(11), 则A (12)坏若 A(l) >A(12),则 A (12)坏且轻若 A(l) <A(12),则 A (12)坏且重若 A(l) +A(9)>A(10) +A(11), 则A (9)坏目重或A (10)与A (11)中有坏且轻若 A (10) =A (11),则 A (9)坏目重若 A (10) >A (11),则 A (11)坏且轻若 A (10) <A (11),则 A (10)坏且轻若 A(l) +A(9) <A(10) +A(11),则A (9)坏且轻或A (10)与A (11)中有坏且重若 A (10) =A (11),则 A (9)坏且轻若 A (10) >A (11),则 A (11)坏且重若 A (10) <A (11),则 A (10)坏且重若 A(l)+A(2) +A(3)+A(4)>A(5) +A(6) +A +A(8)则A，A， A (3), A (4) 中有坏且重或 A(5), A(6), A (7), A (8) 中有坏且轻若 A (1) +A (2) +A (6) =A (3)+A (4) +A (5),贝 A (7), A (8)中有坏且轻若A(l) =A(7),则A (8)坏且轻若A (1)卢A (7),则A (7)坏且轻若 A +A (2) +A (6) >A (3)+A (4) +A (5),则 A (1), A 中有坏且重,或A (5)坏且轻若A(l) =A (2),则A (5)坏且轻若A(l) >A(2),则A (1)坏且重若A(l) <A(2),则A (2)坏且重若 A (1) +A (2) +A (6) <A (3) +A (4) +A (5),则 A (3), A (4) 中有坏且重,或A (6)坏且轻若A (3) =A (4),则A (6)坏且轻若A(3) >A(4),则A (3)坏目重若A (3) <A(4),则A (4)坏且重若 A(l)+A(2) +A (3) +A (4) <A (5) +A (6) +A (7) +A (8) 则 A(1),A(2), A (3), A (4) 中有坏且轻, 或 A(5), A(6), A (7), A (8) 中有坏且重若 A (1) +A (2) +A (6) =A (3)+A (4) +A (5),则 A (7), A (8)中有坏且重若A(l) =A(7),则A (8)坏目重若AA (7),则A (7)坏且重若 A (1) +A (2) +A (6) >A (3)+A (4) +A (5),则 A (3), A (4)中有坏且轻,或A (6)坏且重若A (3) =A (4),则A (6)坏且重若A(3) >A(4),则A (4)坏且轻若A (3) <A(4),则A (3)坏且轻若 A (1) +A (2) +A (6) <A (3) +A (4) +A (5),则 A ,A (2) 中有坏且轻,或A (5)坏且重若A(l) =A (2),则A (5)坏且重若A(l) >A (2),则A (2)坏且轻若A<A(2),则A (1)坏且轻根据表1-1所示的比较过程,可以写出算法的C+描述如下:,chl_5-cpp?rinclude<iostream>usmg namespace std;int al2(int afl)(if(al+a2亠a3-a4=a5卜a6-a7卜a8) ，a9, a10, all, a12中有坏 if(alha9=a10-all) 间12坏if(al>a12)retum(-12); > al2坏且轻elseretum(12); 间12坏且重elseif(al-a9>a10-all)a9坏且重,或 a10与 aU中有坏且轻if(a10=all)retuni(9);a9坏且重&sei<a10>allDretum(-ll);a 11 坏且轻elseretum(-10);坏目轻else，司9坏且轻,或a10与屮1中有坏且重if(a10=aH)retum(-9);a9坏且轻elseif(a10>all)retum(lO);a10坏且重elseretum(ll);a 11 坏目重&seif(al+a2+a3+a4>a习+a6+a7+a8D/al, a2, a3a4中有坏且重,或a5,旳切,a8中有坏且轻if(al-a2+a6=43-14卜a5)，a7, a8中有坏且轻if(al=a7)retum(-8);a8坏且轻elseretum(-7);旬T坏且轻elseif(ala(2-a6>43-a4-a5Dal a2中有坏且重,或-5坏且轻if(al=a2)retam(-5); a5坏且轻elseif(al>a2)retum(l);al坏且重elseretum(2);，a2坏目重else /闻3, a4冲有坏且重,或a6坏且轻if(a3=a4)retuni(-6);间6坏且轻else if(a3>a4)retum(3); h a3坏且重elseretum(4);a4坏且重else /a(l, a2, a3皿中有坏且轻,或a6明,晒中有坏且重国a-a2-a6=a3-a4卜a习)Za7, a8中有坏且重if(al-a7)retum(8); / a8坏且重elsereturn;厶a7坏且重else if(al-a2 +a>a3-a4 +a习)/闻3 a4中有坏且轻,或 a6坏且重 if(a3=a4)retuni(6); / a(习坏且重else if(a(3>a4)retum(-4);a4坏且轻elseretum(-3)ia3坏且轻else间1, a2中有坏且轻,或a»坏且重if(al=a2)retuni(5);a5坏且重elseif(al>a2)retum(-2);a2坏且轻elseretum(-l);询1坏且轻)在上述C程序中,为了直观起见,定义的数组长度为13,其中数组元素a0在程序中不用。主函数例如下:intmainO(im a口 3=0,5,5,5,555545555;cout«f,k=<*«al 2(a)«endl:return 0;)运行结果如下:k = -8表示数组中第S个元素为坏元素,即编号为8的小球为坏球,且比好球轻。第2章基本数据结构及其运算2.I复习笔记、基本概念数据结构的定义数据结构是指相互有关联的数据元素的集合。(1)数据的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含的信息:a.表示数据元素的信息;b,表示各数据元素之间的前后件关系。数据的逻辑结构要素:a.数据元素的集合,通常用D来表示;b. D上的关系,它反映了D中各数据元素之间的前后件关系,通常记为R。即数据结构可以表示成B=D, R其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元表示。(2)数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结 构)。在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后 件关系的信息。常用的存储结构有顺序、链接、索引等存储结构。数据结构的图形表示(1)将数据集合D中的每个数据元素用中间标有元素值的方框表示，称为数据结点， 简称结点；为了进步表示各数据元素之间的前后件关系,将关系R中的每一个二元组 ,用一条有向线段从前件结点指向后件结点。(2)在数据结构中,没有前件的结点称为根结点;没有后件的结点称为终端结点(也称 为叶子结点)。数据结构的类型根据数据结构中各数据元素之间前后件关系的复杂程度,可将数据结构分为线性结构与非 线性结构。线性结构又称线性表,与其相关的几个性质如下:(1)若一个线性结构非空，则其有且只有一个根结点,且每个结点最多有一个前件, 最多有一个后件;(2)在个线性结构中插入或删除任何个结点后还应是线性结构:(3)如果一个数据结构满足上述两个条件,但当在此数据结构中插入或删除任何个结 点后就不满足这两个条件了,则该数据结构不能称为线性结构。线性结构与非线性结构都可以是空的数据结构。个空的数据结构究竟是属于线性结构还 是属于非线性结构,这要根据具体情况来确定。二、线性表及其顺序存储结构线性表及其运算(1)定义线性表是由n (n>0)个数据元素4, a”，a”组成的个有限序列。矩阵也是个线性 表,在矩阵中,既可以把每一行看成是一个数据元素，也可以把每一列看成是一个数据元 素。其中,每个数据元素实际上又是个简单的线性表。非空线性表有如下些结构特征:有且只有一个根结点a”它无前件;有且只有一个终端结点,它无后件;除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。(2)顺序存储结构线性表的顺序存储结构具有以下两个基本特点:线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在程序设计语言中,通常定义个维数组来表示线性表的顺序存储空间。在用维数组 存放线性表时,该维数组的长度通常要定义得比线性表的实际长度略大,以便对线性表 进行各种运算,特别是插入运算。建立一个容量为m的空线性表的顺序存储空间的C+描述如下:templatecnpename T>模板声明,T为类型参数void init_sq_LList(T * v,int msmt *n)new Tm;动态申请存储空间*n=0i线性表长度置为return; ）在上述描述中,T为线性表中元素的虚拟数据类型。要释放线性表的顺序存储空间时,可以用“deletev； （3）顺序存储下的插入运算假设线性表的存储空间为V （1： m）,线性表的长度为n （n<m）,插入的位置为i （i表示 在第i个元素之前插入）。要插入新元素b,则插入的过程如下:首先处理以下三种异常情况。a.当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结束;b.当i>n时，认为在最后个元素之后插入;c,当i<l时,认为在第1个元素之前插入;从最后个元素开始,直到第i个元素,其中每个元素均往后移动个位置;最后将新元素b插入到第i个位置,并且将线性表的长度增加1。线性表在顺序存储结构下插入算法的C+描述如下:Iinclude<iostr¢am> using namespace std;template<typenme T>模板声明,T为类型参数void ins_sq_LLi8t (T * v, int m, int * n, int i, T b) iint k;if (*n«-m)存储空间已満,上溢错误 cout«Moverflow!nw;return; if (i> * n) i- » n+1;默认为在最后个元素之后插入ifC)，7,蒙认为在第一个元章之前揄入for (k* n; k>-l； k-)vk«vlk-i;从最后个元米开始,直到第i个元索均往后移动个位臂v(i-lj-b;插入新元素* n- » n*l;线性或长度增加1return;（4）顺序存储下的删除运算假设线性表的存储空间为V （1： m）,线性表的长度为n （n<m）,删除的位置为i,则删 除的过程如下:首先处理以下两种异常情况。a.当线性表为空时为“下溢”错误,不能进行删除,算法结束;b,当i<l或i>n时,认为在最后个元素之后删除。从第i+1个元素开始,直到最后个元素，其中每个元素均依次往前移动个位置;最后将线性表的长度减1。（5）顺序表类下面的描述是将顺序表的数据和基本操作（初始化、输出、插入与删除操作）封装成一个 sq丄List 类:/模板声明,数据元索虚拟类型为T顺序表类数据成员存储空间容依顺序表长度顺序表存储空间首地址成员函数return;)建立空顺序表,申请存储空间順序输出順序表中的元素与顺序表长度检测顺序表的状态/在表的指定元索前插入新元素/sq_LList.h#include< iostream> using namespace std; template<class T> class sq_LList private: int mm; int nn; T * v;public:sq_LList() mm=O; nn»O; sq_LList(int);void prt_sq_LList (); int flag_sq_LList ();void ins sq_LList (int, T);void del-Sq>List(int);在表中B(除指定元素建立空顺序表存储空间容置动态申请存储空间顺序衰长度为。,即建立空顺序表template<class T> sq_LList<T> :sq_LList(int m) m/n-m;v«new TfmmJ;nn0;recurn;顺序输出廡序表中的元素与顺序表长度tempiate<class T>void sq_LList<T> ： :prt_sq_LLlst () int i;cout« nnn- "« nn« endl ；for (t0; i<nn； i+ + ) cout«v(1 «end 1; return;检测顺序表的状态template<class T>存储空间已満,返回一】 顺序表为空，返回0 正常返回1int sq_LLiSt<T> : flag_sq List ()(if (nnmn) return(-1)； if (nn-«0) return(0); return ;在表的指定元素前插入新元素template<class T>void sq_LList<T> : ins_sq tList (int i, T b) (int k;if (nn*«iwn)( cout«"overfLowH«endl;if nZ1;if <i<l) i-1;for (K-nn; k>*i; k-) vjk)*vjk-l);vim ;nn-nn*l;存储空间已需，上溢槍误return；）跃认为在敷后个元素之后捕人默认为在第一个元素之前插入从最后个元家直到第i个元素均后移个位置摘入新元素顺序表长度加1return；在翔洋表中髭除指定元素template<class T>void sqLList<T> :del_sg_LList (int i) I int k;if (nn0)顺用表为空，下溢幡谈I cout«"underflow!"«endl; return; if顺序表中没有这个元案( cout"Not this element in the list!M«endl; return;)for (k»i; k<nn; k+ + )vk-l)-vk;从第i个元素直到最后个元素均前移个位置nn»nn-l;顺序表氏度减!return;利用顺序表类中的成员函数flag_sq_LList ()可以解决上溢错误信息没有返回给调用程序 ，调用程序无法处理的情况。成员函数flag.sq.LList ()的功能是检测顺序表的当前状态 若顺序表满,则返回函数值1；若顺序表空,则返回函数值;正常情况则返回函数值1。栈及(1)定义栈实际上也是线性表,只不过是种特殊的线性表。其插入和删除运算都只在线性表的 端进行。在栈中,将允许插入与删除的一端称为栈顶,将不允许插入与删除的一端称为栈底。栈顶 元素总是最后被插入的元素,也是最先被删除的元素;栈底元素总是最先被插入的元素, 也是最后被删除的元素。即栈是按照“先进后