下载文档原格式
实验四：KMP算法实验报告一、问题描述模式匹配两个串。
二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。
注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：int Index(String S,String T,int pos)//参考《数据结构》中的程序{i=pos;j=1;//这里的串的第1个元素下标是1while(i<=S.Length && j<=T.Length){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}//**************(1)}if(j>T.Length) return i-T.Length;//匹配成功else return 0;}匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。
如果T为a bcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。
如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：...ababd...ababc->ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。
KMP算法的详细解释什么是kmp算法呢？这是⼀个处理字符串的算法，⽤来判断给出的模式串p是否存在于⽂本串t中（p的长度⼩于t）。
在本⽂中，字符串储存在字符数组中，并且第⼀个字符放在下标为1的元素中。
那么如何理解kmp算法呢？⾸先要从最朴素的匹配算法说起。
我们判断p是否存在于t中，最原始的⽅法就是从头到尾⼀直遍历。
定义变量i为⽂本串t中的下标，定义变量j为模式串p中的下标，然后i表⽰看⽂本串的前i个字符，j表⽰判断这前i个字符组成的⼦串中，长度为j的前后缀是否相等。
如果t[i] = p[j]，则i与j同时后移⼀位，⽐较下⼀位是否相同，如果t[i] != p[j]，则表⽰串t在i位置处“失配”，需要重新进⾏匹配，i保持不动，并且j 必须返回到模式串p的开头，也就是相当于回退到1，然后再次进⾏循环。
如果t的长度为m，p的长度为n时，这样做的时间复杂度为O(m*n)kmp就是在这种最原始匹配算法的基础之上的改进算法。
Kmp的改进之处在哪⾥呢？上⾯这种复杂度最⼤的朴素⽅法中，有⼀个步骤，当“失配”时，我们的i不移动，但是j需要回到串p的开头，这样每⼀次失配，我们都需要再从模式串的开头重新开始匹配，相当于将j直接回退到1，然后再从1开始去试满⾜的最⼤的相同前后缀长度，多了好多次循环，聪明的科学家们想到的办法是：假设现在有这样⼀种情况：在遍历到⽂本串t的的前i-1个字符组成的⼦串之后，我们已经确定了该⼦串中的长度为j-1的前后缀是相同的，那么现在在考虑下⼀个字符（第a个）时发⽣失配，也就是第a个字符不等于第b个，我们不想让b直接回退到1，⽽是回退到1和b之间的某个值，以减⼩复杂度。
我们先放下这个问题，思考另外⼀个问题：如果要求⼀个字符串中相同的前缀和后缀的最长长度，怎么求呢？和上⾯的kmp其实特别像，还是分治的思想：假设我们现在已经看到了字符串的前i-1个元素，并且在这i-1个元素的⼦串中，长度为j-1的后缀和前缀是⼀样的，表⽰匹配到了j-1的长度，那么我们就可以考虑第字符串中第i个元素是否和第j个元素相同了，如果相同就继续匹配下去，如果不同，j仍要回退，但是不能把j直接回退到1然后递增地去判断，这样复杂度太⼤。
KMP算法以及优化（代码分析以及求解next数组和nextval数组）KMP算法以及优化(代码分析以及求解next数组和nextval数组)来了,数据结构及算法的内容来了,这才是我们的专攻,前⾯写的都是开胃⼩菜,本篇⽂章,侧重考研408⽅向,所以保证了你只要看懂了,题⼀定会做,难道这样思想还会不会么?如果只想看next数组以及nextval数组的求解可以直接跳到相应部分,思想总结的很⼲~~⽹上的next数组版本解惑先总结⼀下,⼀般KMP算法的next数组结果有两个版本,我们需要知道为什么会存在这种问题,其实就是前缀和后缀没有匹配的时候next数组为0还是为1,两个版本当然都是对的了,如果next数组为0是的版本,那么对于前缀和后缀的最⼤匹配长度只需要值+1就跟next数组是1的版本⼀样了,其实是因为他们的源代码不⼀样,或者对于模式串的第⼀个下标理解为0或者1,总之这个问题不⽤纠结,懂原理就⾏~~那么此处,我们假定前缀和后缀的最⼤匹配长度为0时,next数组值为1的版本,考研⼀般都是⽤这个版本(如果为0版本,所有的内容-1即可,如你算出next[5]=6,那么-1版本的next[5]就为5,反之亦然)~~其实上⾯的话总结就是⼀句话next[1]=0,j(模式串)数组的第⼀位下标为1,同时,前缀和后缀的最⼤匹配长度+1即为next数组的值,j所代表的的是序号的意思408反⼈类,⼀般数组第⼀位下标为1,关于书本上前⾯链表的学习⼤家就应该有⽬共睹了,书本上好多数组的第⼀位下标为了⽅便我们理解下标为1,想法这样我们更不好理解了,很反⼈类,所以这⾥给出next[1]=0,前缀和后缀的最⼤匹配长度+1的版本讲解前⾔以及问题引出我们先要知道,KMP算法是⽤于字符串匹配的~~例如:⼀个主串"abababcdef"我们想要知道在其中是否包括⼀个模式串"ababc"初代的解决⽅法是,朴素模式匹配算法,也就是我们主串和模式串对⽐,不同主串就往前移⼀位,从下⼀位开始再和模式串对⽐,每次只移动⼀位,这样会很慢,所以就有三位⼤神⼀起搞了个算法,也就是我们现在所称的KMP算法~~代码以及理解源码这⾥给出~~int Index_KMP(SString S,SString T,intt next[]){int i = 1,j = 1;//数组第⼀位下标为1while (i <= S.length && j <= T.length){if (j == 0 || S.ch[i] == T.ch[j]){//数组第⼀位下标为1,0的意思为数组第⼀位的前⾯,此时++1,则指向数组的第⼀位元素++i;++j; //继续⽐较后继字符}elsej = next[j]; //模式串向右移动到第⼏个下标,序号(第⼀位从1开始)}if (j > T.length)return i - T.length; //匹配成功elsereturn 0;}接下来就可以跟我来理解这个代码~~还不会做动图,这⾥就⼿画了~~以上是⼀般情况,那么如何理解j=next[1]=0的时候呢?是的,这就是代码的思路,那么这时我们就知道,核⼼就是要求next数组各个的值,对吧,⼀般也就是考我们next数组的值为多少~~next数组的求解这⾥先需要给出概念,串的前缀以及串的后缀~~串的前缀:包含第⼀个字符,且不包含最后⼀个字符的⼦串串的后缀:包含最后⼀个字符,且不包含第⼀个字符的⼦串当第j个字符匹配失败,由前1~j-1个字符组成的串记为S,则:next[j]=S的最长相等前后缀长度+1与此同时,next[1]=0如,模式串"ababaa"序号J123456模式串a b a b a anext[j]0当第六个字符串匹配失败,那么我们需要在前5个字符组成的串S"ababa"中找最长相等的前后缀长度为多少再+1~~如串S的前缀可以为:"a","ab","aba","abab",前缀只不包括最后⼀位都可串S的后缀可以为:"a","ba","aba","baba",后缀只不包括第⼀位都可所以这⾥最⼤匹配串就是"aba"长度为3,那么我们+1,取4序号J123456模式串a b a b a anext[j]04再⽐如,当第⼆个字符串匹配失败,由前1个字符组成的串S"a"中,我们知道前缀应当没有,后缀应当没有,所以最⼤匹配串应该为0,那么+1就是取1~~其实这⾥我们就能知道⼀个规律了,next[1]⼀定为0(源码所造成),next[2]⼀定为1(必定没有最⼤匹配串造成)~~序号J123456模式串a b a b a anext[j]014再再⽐如,第三个字符串匹配失败,由前两个字符组成的串S"ab"中找最长相等的前后缀长度,之后再+1~~前缀:"a"后缀:"b"所以所以这⾥最⼤匹配串也是没有的长度为0,那么我们+1,取1序号J123456模式串a b a b a anext[j]0114接下来你可以⾃⼰练练4和5的情况~~next[j]011234是不是很简单呢?⾄此,next数组的求法以及kmp代码的理解就ok了~~那么接下来,在了解以上之后,我们想⼀想KMP算法存在的问题~~KMP算法存在的问题如下主串:"abcababaa"模式串:"ababaa"例如这个问题我们很容易能求出next数组序号J123456模式串a b a b a anext[j]011234此时我们是第三个字符串匹配失败,所以我们的next[3]=1,也就是下次就是第⼀个字符"a"和主串中第三个字符"c"对⽐,可是我们刚开始的时候就已经知道模式串的第三个字符"a"和"c"不匹配,那么这⾥不就多了⼀步⽆意义的匹配了么?所以我们就会有kmp算法的⼀个优化了~~KMP算法的优化我们知道,模式串第三个字符"a"不和主串第三个字符"c"不匹配,next数组需要我们的next[3]=1,也就是下次就是第⼀个字符"a"和主串中第三个字符"c"对⽐,之后就是模式串第⼀个字符"a"不和"c"匹配,就是需要变为next[1]=0,那么我们要省去步骤,不就可以直接让next[3]=0么?序号J12345模式串a b a b anext[j]01123nextval[j]00那么怎么省去多余的步骤呢?这就是nextval数组的求法~~nextval的求法以及代码理解先贴出代码for (int j = 2;j <= T.length;j++){if (T.ch[next[j]] == T.ch[j])nextval[j] = nextval[next[j]];elsenextval[j] = next[j];}如序号J123456模式串a b a b a anext[j]011234nextval[j]0⾸先,第⼀次for循环,j=2,当前序号b的next[2]为1,即第⼀个序号所指向的字符a,a!=当前序号b,所以nextval[2]保持不变等于next[2]=1序号J123456模式串a b a b a anext[j]011234nextval[j]01第⼆次for循环,j=3,当前序号a的next[3]为1,即第⼀个序号所指向的字符a,a=当前序号a,所以nextval[3]等于nextval[1]=0序号J123456模式串a b a b a anext[j]011234nextval[j]010第三次for循环,j=4,当前序号b的next[4]为2,即第⼆个序号所指向的字符b,b=当前序号b,所以nextval[4]等于nextval[2]=1序号J123456模式串a b a b a anext[j]011234nextval[j]0101就是这样,你可以练练5和6,这⾥直接给出~~序号J123456模式串a b a b a anext[j]011234nextval[j]010104⾄此nextval数组的求法你也应该会了,那么考研要是考了,那么是不是就等于送分给你呢?⼩练习那么你试着来求⼀下这个模式串的next和nextval数组吧~~next[j]nextval[j]⼩练习的答案序号j12345模式串a a a a b next[j]01234 nextval[j]00004。
KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。
简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。
可以证明它的时间复杂度为O(m+n).。
一.简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S [ ], char T [ ], int pos ){/* 若串S 中从第pos(S 的下标0≤pos<StrLength(S))个字符起存在和串T 相同的子串，则称匹配成功，返回第一个这样的子串在串S 中的下标，否则返回-1 */int i = pos, j = 0;while ( S[i+j] != '\0'&& T[j] != '\0')if ( S[i+j] == T[j] )j ++; // 继续比较后一字符else{i ++; j = 0; // 重新开始新的一轮匹配}if ( T[j] == '\0')return i; // 匹配成功返回下标elsereturn -1; // 串S中(第pos个字符起)不存在和串T相同的子串} // Index_BF此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。
即从j=0 起比较S[i+j] 与T[j]，若相等，则在主串S 中存在以i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即i 增1，而j 退回至0，重新开始新一轮的匹配。
例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等…我们发现一直比较到S[5] 和T[5]才不等。
KMP算法的应用2. 数据压缩：KMP算法可以用于数据压缩算法中，例如RLE（Run Length Encoding）算法。
RLE算法通过将连续出现的相同字符进行压缩，可以大大减小数据的存储空间。
KMP算法在判断连续字符的出现位置时非常高效，可以帮助提高压缩算法的速度。
3.DNA序列匹配：在生物信息学中，KMP算法可以用于DNA序列的匹配。
DNA序列是由A、C、G、T四种字符组成的序列，KMP算法可以帮助确定DNA序列中是否存在特定的子序列，并计算其出现的位置。
这对于基因分析和生物实验的设计都有重要意义。
4.正则表达式匹配：正则表达式是一种用于匹配字符串的表达式，通常由一系列字符和操作符组成。
KMP算法可以用于实现正则表达式引擎中的字符串匹配功能，例如在引擎中通过正则表达式进行页面的筛选和聚类。
5.图像处理：在图像处理中，KMP算法可以用于图像相似性。
例如，当需要在一张大图中查找与给定小图相似的部分时，KMP算法可以帮助确定小图在大图中的位置，并进行进一步的处理。
6.模式识别：KMP算法在模式识别中也有广泛的应用。
例如，在人脸识别中，KMP算法可以用于查找待识别人脸的特征点，以便进行进一步的识别和比对。
总结来说，KMP算法的应用非常广泛，涉及到字符串匹配、数据压缩、生物信息学、正则表达式、图像处理和模式识别等多个领域。
它通过利用模式串中已经匹配的信息减少匹配过程中的比较次数，从而提高了匹配的效率。
KMP算法的核心思想是使用有限状态自动机（Finite State Machine）来记录模式串与文本串在匹配过程中的关系，从而快速定位匹配的位置。
在实际应用中，KMP算法可以帮助提高程序的性能和效率，减少计算资源的消耗。
数据结构教学中KMP算法解析摘要：模式匹配是字符串的基本运算之一，也是数据结构教学中的难点之一。
分析了模式匹配KMP算法以及算法中next函数的含义，给出了next函数的两种实现方法，有助于在教学实践中帮助学生更好地理解该算法。
关键词：数据结构；模式匹配；KMP算法0引言模式匹配（Patten Matching）是许多计算机应用领域的基础问题，在数据结构中模式匹配是字符串的基本运算之一。
字符串模式匹配指的是，找出特定的模式串在一个较长的字符串中出现的位置。
有两个字符串S和T，字符串S称为目标串，字符串T称为模式串，要求找出模式T在S中的首次出现的位置。
一旦模式T在目标S中找到，就称发生一次匹配。
有些应用可能会要求找出所有的匹配位置<sup>[1]</sup>。
例如，目标串S= 'Shanghai'，模式串T= 'gha'，则匹配结果为4。
模式匹配的典型算法包括朴素匹配算法、KMP算法和BM算法等，其中KMP算法是效率较高且经典的模式匹配算法之一<sup>[2]</sup>。
在数据结构教学中，由于KMP算法较难理解，课堂讲授往往很难取得好的效果。
本文通过对传统的朴素匹配算法与KMP算法的比较，分析next函数的含义以及实现方法，来帮助理解KMP算法。
1朴素匹配算法在朴素匹配算法中，S和T分别为目标串和模式串，变量i和j 为两个静态指针，分别表示S和T中当前正待比较的字符位置。
算法的基本思想是：第1趟匹配：从S的第1个字符（序号为0）起和T的第一个字符比较之，如果相等，则继续逐个比较后续字符（i++；j++），否则开始下一趟匹配。
新的一趟匹配：i的初值为上一趟的初值+1 ，j的初值为1，如果比较结果相等，则继续逐个比较后续字符，否则开始下一趟匹配。
依次类推，直至某一趟匹配中，T的每个字符依次和S中的一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。
数据结构与算法_桂林电子科技大学中国大学mooc课后章节答案期末考试题库2023年1.下面哪种数据结构不是线性结构（）参考答案:二叉树2.串S=”myself“，其子串的数目是（）参考答案:223.设目标串为‘abccdcdccbaa'，模式串为'cdcc'，则第（）次匹配成功。
参考答案:64.串S='aaab'，其next数组为（）参考答案:-1 0 1 25.KMP算法相对于BF算法的优点是时间效率高参考答案:正确6.串是一种数据对象和操作都特殊的线性表参考答案:正确7.下面哪个（）可能是执行一趟快速排序能够得到的序列参考答案:[41，12，34，45，27] 55 [72，63]8.设主串t的长度为n，模式串p的长度为m，则BF算法的时间复杂度为O(n+m)参考答案:错误9.从一个长度为n的顺序表中删除第i个元素（0 ≤ i≤ n-1）时，需向前移动的元素的个数是（）参考答案:n-i-110.对线性表进行二分查找时，要求线性表必须（）参考答案:以顺序方式存储，且结点按关键字有序排序11.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
参考答案:仅有尾指针的单循环链表12.最小不平衡子树是指离插入结点最近，且包含不平衡因子结点的子树参考答案:正确13.在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的( )参考答案:直接后继14.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点参考答案:n/215.对以下单循环链表分别执行下列程序段，说明执行结果中，各个结点的数据域分别是（）p = tail→link→link; p→info = tail→info;【图片】参考答案:8，3，6，816.对以下单链表执行如下程序段，说明执行结果中，各个结点的数据域分别是（）void fun (Linklist H) //H是带有头结点的单链表{ PNode p,q; p=H->link;H->link=NULL; while (p) { q=p; p=p->link; q->link=H->link; H->link=q; }}【图片】参考答案:8，6，4，217.根据教科书中线性表的实现方法，线性表中的元素必须是（）参考答案:相同类型18.若线性表中最常用的操作是存取第i个元素及其前驱和后继元素的值，为了节省时间应采用的存储方式（）参考答案:顺序表19.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）参考答案:n-i+120.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）参考答案:(rear-front+m)%m21.已知其头尾指针分别是front和rear，判定一个循环队列QU（最多元素为m）为空的条件是（）参考答案:QU—>front= =QU—>rear22.一个队列的入列序列是1，2，3，4，则队列的输出序列是（）参考答案:1，2，3，423.已知其头尾指针分别是front和rear，判定一个循环队列QU（最多元素为m）为满的条件是（）参考答案:QU—>front= =（QU—>rear+1）%m24.在计算机内实现递归算法时所需的辅助数据结构是( )参考答案:栈25.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。
（原创）详解KMP算法KMP算法应该是每⼀本《数据结构》书都会讲的，算是知名度最⾼的算法之⼀了，但很可惜，我⼤⼆那年压根就没看懂过~~~之后也在很多地⽅也都经常看到讲解KMP算法的⽂章，看久了好像也知道是怎么⼀回事，但总感觉有些地⽅⾃⼰还是没有完全懂明⽩。
这两天花了点时间总结⼀下，有点⼩体会，我希望可以通过我⾃⼰的语⾔来把这个算法的⼀些细节梳理清楚，也算是考验⼀下⾃⼰有真正理解这个算法。
什么是KMP算法：KMP是三位⼤⽜：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。
其中第⼀位就是《计算机程序设计艺术》的作者！！KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。
说简单点就是我们平时常说的关键字搜索。
模式串就是关键字（接下来称它为P），如果它在⼀个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常⽤⼿段）。
⾸先，对于这个问题有⼀个很单纯的想法：从左到右⼀个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动⼀位。
这有什么难的？我们可以这样初始化：之后我们只需要⽐较i指针指向的字符和j指针指向的字符是否⼀致。
如果⼀致就都向后移动，如果不⼀致，如下图：A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后⼜重新开始这个步骤：基于这个想法我们可以得到以下的程序：1/**23 * 暴⼒破解法45 * @param ts 主串67 * @param ps 模式串89 * @return如果找到，返回在主串中第⼀个字符出现的下标，否则为-11011*/1213public static int bf(String ts, String ps) {1415char[] t = ts.toCharArray();1617char[] p = ps.toCharArray();1819int i = 0; // 主串的位置2021int j = 0; // 模式串的位置2223while (i < t.length && j < p.length) {2425if (t[i] == p[j]) { // 当两个字符相同，就⽐较下⼀个2627 i++;2829 j++;3031 } else {3233 i = i - j + 1; // ⼀旦不匹配，i后退3435 j = 0; // j归03637 }3839 }4041if (j == p.length) {4243return i - j;4445 } else {4647return -1;4849 }5051 }上⾯的程序是没有问题的，但不够好！（想起我⾼中时候数字⽼师的⼀句话：我不能说你错，只能说你不对~~~）如果是⼈为来寻找的话，肯定不会再把i移动回第1位，因为主串匹配失败的位置前⾯除了第⼀个A之外再也没有A了，我们为什么能知道主串前⾯只有⼀个A？因为我们已经知道前⾯三个字符都是匹配的！（这很重要）。
第3章线性结构的扩展1.选择题（1）B （2）A （3）DAB （4）CCC （5）C2.判断题（1）Ⅹ（2）√（3）√（4）√（5）Ⅹ（6）Ⅹ（7）Ⅹ（8）Ⅹ（9）Ⅹ（10）Ⅹ3.简答题1．KMP算法较朴素的模式匹配算法有哪些改进?【解答】KMP算法主要优点是主串指针不回溯。
当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。
2．设字符串S=‘aabaabaabaac'，P=‘aabaac'。
（1）给出S和P的next值和nextval值；（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。
【解答】（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。
（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaacaabaac(i=6,j=6) aabaac(i=6,j=6)第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaacaa(i=3,j=2) (aa)baac第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaaca(i=3,j=1) (成功) (aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功) aabaac(i=13,j=7)3．考虑对KMP算法能否再做改进。
【解答】4．说明一维数组与有序表的异同。
【解答】数组：数组是由类型名、标识符和维数组成的符合数据类型，类型名规定了存放在数组中的元素的类型，而维数则指数组中包含的元素个数。
线性表：（亦作有序表）是最基本、最简单、也是最常用的一种数据结构。
