5. fact(n)
{ if(n<=1)
return (1);
else
return (n*fact(n-1));
} 5. O(n)
第2章 线性表
【例2-1】试编写出将两个顺序存储的有序表A和B合成一个有序表C的算法。
解：假设A、B和C的类型为下述SqList类型：
#define maxlen 1000 typedef int elemtype typedef struct
{ elemtype elem[maxlen]; int len; }SqList;
设A和B的数据元素均为整数且为升序排列，设A的长度为m，B的长度为n，则合并后C的长度为m+n。合并时进行A、B元素的比较，将较小的链入C中，算法描述如下：
int merge (SqList *A, SqList *B, SqList *C) //将两个有序表A和B合成一个有序表C { int m,n,i,j,k;
m=(*A).len; n=(*B).len; if (m+n>maxlen-1) { printf(\
exit (0); }
i=0; j=0; //i和j分别作为扫描顺序表A和B的指针
k=0; //k指示顺序表C中当前位置 while ((i<=m)&&(j<=n))
if((*A).elem[i]<＝(*B).elem[j]) { (*C).elem[k]＝(*A)elem[i]; i++; k++; } else
{ (*C).elem[k]＝(*B)elem[j];
j++; k++; }
while(i<=m) //表B已结束，表A没有结束，链入表A的剩余部分 { (*C).elem[k]＝(*A).elem[i]; i++; k++;
}
while(j<=m) //表A已结束，表B没有结束，链入表B的剩余部分 { (*C).elem[k]＝(*B).elem[j]; i++; k++; } return (1); }
【例2-2】写一算法实现单链表的逆置。
解：假设单链表的表头指针用head表示，其类型为下面定义的LinkList，并且单链表不带头结点。逆置后原来的最后一个结点成为第一个结点，于是从第一个结点开始逐个修改每个结点的指针域进行逆置，且刚被逆置的结点总是新链表的第一个结点，故令head指向它（如图2-1所示）。
typedef struct Node { elemtype data; struct Node *next; }LinkList;
具体算法描述如下： head ? (a)单链表初始状态
head ∧ head q q p (b)第三个结点逆置 图2-1 单链表逆置示意图 void contray(LinkList *head)
{ //将head单链表中所有结点按相反次序链接 LinkList *p, *q;
∧
?
p=head; //p指向未被逆序的第一个结点,初始时指向原表头结点 head=NULL; while(p!=NULL)
{ q=p; //q指向将被逆序链接的结点 p=p->next; q->next=head; head=q; } }
【例2-3】假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指
向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。
解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下：
void delete (LinkList *p)
{ //在链表中删除p所指结点的前趋结点 LinkList *q,*t; q=p;
while(q->next->next!=p) //q->next不是p的前趋结点 q=q->next;
t=q->next; //t指向要删除结点 q->next=p; //删除t结点 free(t); ｝
【例2-4】试设计实现删除单链表中值相同的多余结点的算法。
解：该例可以这样考虑，先取开始结点的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
设单链表（其类型为LinkList）的头指针head指向头结点，则可按下列步骤执行： 首先，用一个指针p指向单链表中第一个表结点，然后用另一个指针q查找链表中其余结点元素，由于是单链表，故结束条件为p= =NULL，同时让指针s指向q所指结点的前趋结点，当查找到结点具有q->data= =p->data时删除q所指的结点，然后再修改q，直到q为空；然后使p指针后移（即p=p->next），重复进行，直到p为空时为止。算法描述如下：
del(LinkList *head)
{ //删除单链表中值相同的多余结点 LinkList *p, *s, *q; p=head->next;
while(p!=NULL && p->next!=NULL) { s=p; //s指向要删除结点的前趋
q=p->next;
while (q!=NULL)
{ if (q->data= =p->data)} //查找值相同的结点并删除
{ s->next=q->next; free(q); q=s->next; } else { s=q; q=q->next; } }
p=p->next; }
}
习题2
一、单项选择题
1. 线性表是________。1．A
A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空
2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 个元素。 2．A
A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。3．D A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以
4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。4．C
A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。5．D
A． p->next=s; s->prior=p;
p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。6．A
A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;
7. 在一个长度为n的顺序表中向第i个元素(0< i A．n-i B．n-i+l C．n-i-1 D．i 8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行8．B A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q 9. 以下关于线性表的说法不正确的是______。9．C A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。 C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种_______的存储结构。 10．A