(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (4) 解答:status delete(HL,x) { (1) q＝HL; p＝HL->next;
(2) while (p!=HL) && (p->data!=x) { q＝p;
p＝p->next;
}
(3) if (p= =HL) error('not found'); else {q->next＝p->next; free(p); }
}
(5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (5) 解答:status insert(HL,p,x){
malloc(q);
q->data＝p->data; q->next＝p->next; p->next＝q; p->data＝x; }
(6)从循环单链表中查找出最小值。 (6) 解答: elemtype min(HL){ //从循环单链表HL中查找出最小值 if (HL= =nil ) {
printf('HL＝nil'); return; }
min＝HL->data; p＝HL->next;
while (p!=HL) {
(1) if (p->data
}
(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。
(7) 解答:status create(HL,A,n) {
(1) malloc(HL); q＝HL; // 产生附加表头结点 (2) for (i＝1 ;I<=n ;++i) { // 完成n个元素的依次链接 malloc(p);
p->data＝A(i); q->next＝p; q＝p;
}
(3) q->next＝nil ; // 把最后一个结点的指针域置空
17
}
23.请指出下面的过程执行p(5)和p(6)时分别输出的结果。 void P(int n); { if n>0 {
p(n-2);
printf(“%d”,n);
} }
23. 解答:这是一个递归过程，n执行一次就减2，当n≤0时该过程执行结束。因此，当n＝5 时，其输出结果为1、3、5；当n＝6时，其输出结果为2、4、6。 24.假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法：
(1)向循环链队插入一个元素为x的结点；
(1) 解答:status insert(Rear,x){
// 假定Rear为循环链队的队尾指针，x为待插入的元素 (1) malloc(p);
p->data＝x; // 建立值为x的新结点p＾ (2) if( Rear＝nil){
Rear＝p; Rear->next＝p; }
else {p->next＝Rear->next;
Rear->next＝p; Rear＝p;
}
// 若条件成立则建立循环链队的第一个结点，否则在队尾插入p＾结点 }
(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）。 (2) 解答:status delete(Rear){
if( Rear＝nil ) error('underflow'); if (Rear->next= =Rear) Rear＝nil;
else Rear->next＝Rear->next->next;
} //Rear＾.next 所指向的结点为循环链队的队首结点
25.设A(k)有如下10个元素：2，4，6，8，10，12，14，16，18，20。若对A(k)分别查找x＝1，3，13，21，试跟踪下面过程的执行，并分析该程序段关于n的计算时间。 【程序段】 i=1;j=n; do
18
{
k=(i+j)/2;
if A(k)<=x i=k+1 else j=k-1 }while !(i>j);
25.解答
(1)查找x＝1,n＝10
┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? X ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 1 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 1 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 > 1 ┃ 新j＝k－1＝0 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝1)>(j＝0)时，过程终止。未找到。
(2)查找x＝3,n＝10
┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 3 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 3 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 < 3 ┃ 新i＝k＋1＝2 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝2)>(j＝1)时，过程终止。未找到。
(3)查找x＝13,n＝10
┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <13 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 >13 ┃ 新j＝k－1＝7 ┃ ┃第3次┃6 ┃7 ┃6 ┃ 12 <13 ┃ 新i＝k＋1＝7 ┃ ┃第4次┃7 ┃7 ┃7 ┃ 14 >13 ┃ 新j＝k－1＝6 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝7)>(j＝6)时，过程终止。未找到。 (4)查找x＝21,n＝10
┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃ A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <21 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 <21 ┃ 新i＝k＋1＝9 ┃ ┃第3次┃9 ┃10┃9 ┃ 18 <21 ┃ 新i＝k＋1＝10┃ ┃第4次┃10┃10┃10┃ 20 <21 ┃ 新i＝k＋1＝11┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛
19
当(i＝11)>(j＝10)时，过程终止，未找到。该程序段的时间复杂型为O(log2 n)。
**26.分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。 26. 解答:中根遍历的非递归算法： status inorder(bt){ top＝0; p＝bt; do{
(1) while (p!=nil ){ top＝top＋1; s[top]＝p;
p:＝p->left; //p指向左子树 }
(2) if (top>0 ){
p＝s[top]; top＝top－1;
printf(p->data);
p＝p->right; // p指向右子树 }
}while !((top＝0) && (p＝nil)); }
解答: 先根遍历的非递归算法： status preorder(bt) { top＝0; p＝bt do{
(1) while( p!=nil ){
printf (p->data); if (p->right!=nil){ top＝top＋1;
s[top]＝p->right;
}
//若右子树非空，则把链接指针保存起来， 待访问过左子树后再访问它 p＝p->left; //使p指向左子树 }
(2) if (top>0) { // 出栈，使p指向右子树 p＝s[top] top＝top－1; }
}while !((top＝0) && (p＝nil));
20
相关推荐：
loading