数据结构 第二章 顺序表

第二章顺序表线性结构（线性表）的定义：线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：其中：L为线性表名称，习惯用大写书写；ki为组成该线性表的数据元素，习惯用小写书写；k1是开始结点，kn是终端结点，ki是ki+1的前驱，而ki+1是ki的后继。线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。举例：L1=（34，89，765，12，90，-34，22）数据元素类型为int。L2=(“Hello”,”World”,“China”, “Welcome”)数据元素类型为string。一、向量如果线性表的所有表目都是同一类型的结点，我们便称为“向量”（或一维数组）。向量中的表目又称为“元素”。元素的索引又称为“下标”。线性表的向量（顺序存储结构）是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图所示：其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式：LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。在C语言中，实现线性表的顺序存储结构的类型定义#define LIST_MAX_LENGTH 100 //线性表的最大长度typedef struct {Elemtype *elem; //指向存放线性表中数据元素的基地址int length; //线性表的当前长度}SEQLIST；数组形式定义：typedef struct {Elemtype elem[LIST_MAX_LENGTH]; //指向存放线性表中数据元素int length; //线性表的当前长度}SEQLIST；下面以指针形式来讲解。典型操作的算法实现（1）初始化线性表LintInitList(SEQLIST *L) {L->elem=(Elemtype*)malloc(LIST_MAX_LENGTH*sizeof(Elemtype));if(L->elem==NULL) return ERROR;L->length=0;return OK;}（2）销毁线性表LvoidDestroyList(SEQLIST *L) {if (L->elem)free(L->elem); //释放线性表占据的所有存储空间}（3）清空线性表LvoidClearList(SEQLIST *L) {L->length=0; //将线性表的长度置为0}（4）求线性表L的长度intGetLength(SEQLIST L) {return(L.length);}（5）判断线性表L是否为空intIsEmpty(SEQLIST L) {if (L.length==0) return TRUE;else return FALSE;}（6）获取线性表L中的某个数据元素的内容intGetElem(SEQLIST L,int i,Elemtype *e) {//判断i值是否合理，若不合理，返回ERRORif(i<1||i>L.length) return ERROR;//数组中第i-1的单元存储着线性表中第i个数据元素的内容*e=L.elem[i-1];return OK;}（7）在线性表L中检索值为e的数据元素intLocateELem(SEQLIST L,Elemtype e) {for (i=0;ilength==LIST_MAX_LENGTH) return ERROR; //检查是否有剩余空间if(i<1||i>L->length+1) return ERROR; //检查i值是否合理for(j=L->length-1;j>=i-1;i++) //将线性表第i个元素之后的所有元素向后移动L.->elem[j+1]=L->elem[j];L->elem[i-1]=e; //将新元素的内容放入线性表的第i个位置L->length++;return OK;}（9）将线性表L中第i个数据元素删除intListDelete(SEQLIST *L,int i,Elemtype *e) {if (IsEmpty(L))return ERROR; //检测线性表是否为空if(i<1||i>L->length) return ERROR; //检查i值是否合理*e=L->elem[i-1]; //将欲删除的数据元素内容保留在e所指示的存储单元中for(j=i;j<=L->length-1;j++) //将线性表第i+1个元素之后的所有元素向前移动L->elem[j-1]=L->elem[j];L->length--;return OK;}【举例】Josephus（约瑟夫）问题 P19-21详细程序等见本章附录一。二、栈定义：栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：结论：后进先出（Last In First Out）表，简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作：（1）初始化栈InitStack(S)（2）入栈Push(S,elem)（3）出栈Pop(S,elem)（4）获取栈顶元素内容GetTop(S,elem)（5）判断栈是否为空StackEmpty(S)栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#define MAX_STACK 10 //栈的最大数据元素数目typedef struct stack {Elemtypeelem[MAX_STACK]; //存放栈中数据元素的存储单元int top; //栈顶指针}STACK;基本操作算法：（1）初始化栈voidInItStack(STACK *S) {s->top=-1;}（2）入栈void Push(STACK*S,Elemtype elem) {if(S->top==MAX_STACK-1) exit('Stack is full');elseS->elem[++S->top]=elem;}（3）出栈void Pop(STACK*S,Elemtype *elem) {if(StackEmpty(*S)) exit('Stack is empty');else*elem=S->elem[S->top--];}（4）获取栈顶元素内容voidGetTop(STACK S,Elemtype *elem) {if(StackEmpty(S)) exit('Stack is empty');else*elem=S.elem[S.top];}（5）判断栈S是否为空intStackEmpty(STACK S) {if (S.top==-1)return TRUE;else FALSE;}结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。栈的应用举例【举例1】将从键盘输入的字符序列逆置输出比如，从键盘上输入：tset a si sihT；算法将输出：This is a test。下面我们给出解决这个问题的完整算法。typedef char Elemtype;void ReverseRead( ) {STACK S; //定义一个栈结构Schar ch;InitStack(&S); //初始化栈while ((ch=getchar())!='\n') //从键盘输入字符，直到输入换行符为止Push(&S ,ch); //将输入的每个字符入栈while (!StackEmpty(S)) { //依次退栈并输出退出的字符Pop(&S,&ch);putchar(ch);}putchar('\n');}【举例2】十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10 =(1)2，其展转相除的过程如图所示：下面给出解决这个问题的完整算法。void Decimal _ Binary ( ) {STACK S; //定义栈结构SInitStack(&S); //初始化栈Sscanf('%d',data); //输入十进制正整数while (data) {Push(&S,data%2); //余数入栈data/=2; //被除数data整除以2，得到新的被除数}while (!StackEmpty(S)) { //依次从栈中弹出每一个余数，并输出之Pop(&S,&data);printf('%d',data);}}【举例3】检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：圆括号'（'和'）'，方括号'['和']'和花括号'{'和'}'，并且这三种括号可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。下面是解决这个问题的完整算法。typedef char Elemtype;int Check( ){STACK S; //定义栈结构Schar ch;InitStack(&S); //初始化栈Swhile ((ch=getchar())!='\n') { //以字符序列的形式输入表达式switch (ch) {case ( ch=='(' || ch== '[' || ch== '{' ):Push(&S,ch); //遇左括号入栈break;//在遇到右括号时，分别检测匹配情况case (ch== ')'):if (StackEmpty(S)) retrun FALSE;else {Pop(&S,&ch);if (ch!= '(') return FALSE;}break;case (ch== ']'):if (StackEmpty(S)) retrun FALSE;else {Pop(&S,&ch);if (ch!= '[') return FALSE;}break;case (ch== '}'):if (StackEmpty(S)) retrun FALSE;else {Pop(&S,&ch);if (ch!= '{') return FALSE;}break;default:break;}}if (StackEmpty(S)) return TRUE;else return FALSE;}栈和递归一个递归定义必须有确切的含义的，也就是说必须一步比一步简单，最后是有终结的，决不能无限循环下去。背包问题：P30-35详细见本章附录二