第2章 线性表
基础知识题
2．1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解答：首元结点是存储线性表第一个元素的结点。为了方便链表对首元结点的操作，常在首元结点前增加一个头结点，该结点的数据域不存放任何线性表元素。有头结点时，头指针指向它，无头结点时，头指针指向首元结点。 2．2 填空题
（1）在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与 表长和该元素的位置有关。
（2）顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
（3）在单链表中，除了首元结点外，任一结点的存储位置由直接前驱结点的指针域的值指示。
（4）在单链表中设置头结点的作用是插入和删除首元结点时不必特殊处理。 2．3 在什么情况下用顺序表比链表好？
（1） 当线性表的长度变化较大或难以估计最大值时，采用链表较好；
（2） 如果对线性表常用的操作是查询，则使用顺序存储结构较好；如果是插入和删除，
则链表结构较好。
2．6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是 （4）（1） 。 b. 在P结点前插入S结点的语句序列是 （7）（11）（8）（4）（1） 。 c. 在表首插入S结点的语句序列是 （5）（12） 。 d. 在表尾插入S结点的语句序列是 （11）（9）（6）（1） 。 （1）P->next = S;
（2）P->next = P->next->next; （3）P->next = S->next; （4）S->next = P->next; （5）S->next = L;
（6）S->next = NULL; （7）Q = P;
（8）while(P->next != Q) P = P->next; （9）while(P->next != NULL) P = P->next; （10）P = Q; （11）P = L; （12）L = S; （13）L = P; 2．7 已知已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 删除P结点的直接后继结点的语句序列是 （11）（3）（14） 。 b. 删除P结点的直接前驱结点的语句序列是 （10）（12）（8）（11）（3）（14） 。 c. 删除P结点的语句序列是 （10）（12）（7）（3）（14） 。 d. 删除首元结点的语句序列是 （12）（11）（3）（14） 。
e. 删除尾元结点的语句序列是 （9）（11）（3）（14） 。 （1）P = P->next; （2）P->next = P;
（3）P->next = P->next->next; （4）P = P->next->next;
（5）while( P != NULL) P = P->next;
（6）while( Q ->next != NULL) {P=Q; Q=Q->next;} （7）while( P->next != Q ) P = P->next;
（8）while(P->next->next != Q ) P= P->next; （9）while(P->next->next != NULL) P= P->next; （10）Q=P;
（11）Q=P->next; （12）P=L;
（13）L=L->next; （14）free(Q);
2．8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是 （7）（6）（12）（3） 。 b. 在P结点前插入S结点的语句序列是 （5）（8）（13）（4） 。 c. 删除P结点的直接后继结点的语句序列是 （15）（1）（11）（18） 。 d. 删除P结点的直接前驱结点的语句序列是 （16）（2）（10）（18） 。 e. 删除P结点的语句序列是 （9）（14）（17） 。 （1）P->next = P->next->next; （2）P->priou = P->priou->priou; （3）P->next = S; （4）P->priou =S; （5）S->next = P; （6）S->priou = P; （7）S->next=P->next; （8）S->priou = P->priou;
（9）P->priou->next = P->next; （10）P->priou->next = P; （11）P->next->priou = P; （12）P->next->priou = S; （13）P->priou->next = S;
（14）P->next->priou = P->priou; （15）Q = P->next; （16）Q = P->priou; （17）free(P); （18）free(Q);
2．9 简述以下算法的功能。
（1） Status A(LinkedList L){//L是无表头结点的单链表 if (L && L->next) {
Q=L; L=L->next; P=L; while(P->next) P=P->next;
P->next=Q;Q->next = NULL:
}
return OK;
}//A
解答：当单向链表包含两个或两个以上的结点时，将首元结点变成尾结点，原来的2号结点变成了首元结点。
（2） void BB(LNode *s, LNode *q){ p=s;
while(p->next != q) p=p->next; p->next = s;
}//BB
void AA(LNode *pa, LNode *pb){
//pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); }//AA
解答：将原来的单循环链表拆分成两个，pa、pb分别指向这两个单向循环链表中的结点。 算法设计题
本章约定，顺序表中元素的下标从0开始，到顺序表长度length-1结束。
2． 10 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的
算法。
Status DeleteK(SqList &a,int i,int k) {
//本过程从顺序存储结构的线性表a中删除第i个起的k个元素
if(i<1 || k<0 || i+k>a.length) return INFEASIBLE;//参数不合法 else{ }
return OK;
for(count=1;count for(j=a.length;j>=i+1;j--) a.elem[j-1]=a.elem[j]; a.length--; }//DeleteK 解答： 算法分析：程序采用了逐个删除元素的方法，实际上可以将k个元素之后的元素整体向前移动k个位置，从而快速删除指定的k个元素。代码如下： int DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素 { if(i<1||k<0||i+k-1>a.length) return 0; for(int j=k+i;j a.elem[j-k]=a.elem[j]; a.length-=k; return 1; }//DeleteK 2． 11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到适当的位置上，以保持该表的有序性。 解答： 算法分析：先根据x的大小确定其插入位置；再将从插入位置开始之后的所有元素向后移动一个单元；最后插入x，使顺序表的长度加1。 int Insert(SqList &a,DataType t) { for(int i=0;i if( a.elem[i] > t ) break; //确定插入位置在i处 for(int j=a.length - 1; j>=i; j-- ) a.elem[j+1] = a.elem[j]; //移动元素 a.elem[i] = t; //插入t a.length ++; //线性表长度加1 return 1; } 2．12 设A=(a1,...,am)和B=(b1,...,bn)均为有序表，A’和B’分别为A和B中除去最大共同前缀后的子表。若A’=B’=空表，则A=B；若A’=空表，而B’?空表，或者两者都不为空表，且A’的首元小于B’的首元，则A 算法分析：此题类似于C语言中的字符串大小比较算法。程序使用了函数模板。 int SeqComp(SqList A,SqList B) { for(i=0;i return A.elem[i]>B.elem[i]?1:-1; if(A.length==B.length) return 0; return A.length>B.length?1:-1; } 2．13 试写一算法在带头接点的单链表结构上实现线性表操作Locate(L,X)。 解答： 算法分析：：若找到该结点，其地址通过形参p带回；若找不到，p=NULL。 void Locate(List &L,DataType x,Node *&p) { p=L.first->next; while(p){ if(p->Data == x) return; p=p->next; } p=0; } 2．14 试写一算法在带头结点的单向链表上实现线性表操作Length(L)。 int Length(List &L) { int m=0; for(Node *p=L.first->next;p;p=p->next) m++; return m; } 2．15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 解答： 算法分析：先使工作指针指向ha链表的尾结点，然后连接hb链表。 void MergeList(List &ha,List &hb,List &hc) { delete hc.first;//先释放hc链表的头结点空间，使头指针指向ha hc.first=ha.first; Node *p=hc.first; while(p->next) p=p->next;//p最后指向ha链表的尾结点 p->next=hb.first->next; delete hb.first;//释放hb链表的头结点空间 } 2．17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 解答： （1）带头结点的动态单链表 void Insert(List &L,int i,DataType m) { //先得到指向第i-1号结点的指针，然后插入新结点；若i超过范围，则将新结点插入到尾结点之后，若i=1，则插入到头结点之后 Node *q=L.first; int k=1; while(knext){ q=q->next; k++; } Node *p=new Node; p->Data=m; p->next=q->next;