浙江工商大学数据结构期末复习题2(7)

(1) if (L.len = =m0) error('overflow'); (2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }

(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }

(2)status delete(L,x) {

// 从线性表L中删除其值等于x的所有元素 i＝1;

while (i<＝L.len ) if (L.vec[i]= =x ){

(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[j－1]＝L.vec[j]; (Ⅱ) L.len＝L.len－1;

}

else i＝i＋1; }

(3)status merge(A,B,C){

// 将两个有序表A和B合并成一个有序表C (1) if ( A.len＋B.len>m0 ) error('overflow'):

(2) i=1;j＝1;k＝1;

// i和j分别作为扫描数组A和B的指针，k指示存入数组C中元素的下标位置 (3) while (i<＝A.len) && (j<＝B.len) if (A.vec[i]<＝B.vec[j]) { C.vec[k]＝A.vec[i]; i＝i＋1;

k＝k＋1; }

else {C.vec[k]＝B.vec[j]; j＝j＋1; k＝k＋1; } }

(4) while (i<＝A.len){

C.vec[k]＝A.vec[i]; i＝i＋1; k＝k＋1; }

(5) while (j<＝B.len ){

C.vec[k]＝B.vec[j]; j＝j＋1; k＝K＋1;

31

} }

22.编写算法

(1)status contrary(HL){

// 使HL单链表中的所有结点按相反次序链接

p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){

(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }

(2)status delete(HL,i){

(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )

{ HL＝HL->next; return ; }

(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j个结点 while (jnext; }

// 寻找第i个结点的前驱结点 (4) if (p->next!= =nil)

p->next＝p->next->next; else error('out of range'); }

(3)status delete(HL,P,X){

// 删除单链表HL中由指针p所指向的结点 if (p->next＝nil ) error ('not delete'); X＝p->data; q＝p->next;

p->data＝p->next->data; p->next＝p->next->next; free(q); }

或者：

status delete(HL,P,X) { if ( HL＝p ) {

X＝HL->data ;

HL＝HL->next;

32

free(p); } else{

(1) q＝HL;

(2) while (q->next!=nil) && (q->next!=p) q＝q->next; (3) if (q->next＝p){ X＝p->data;

q->next＝p->next;

free(p) }

else error('*p结点不存在');

}

}

(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)status insert(HL,p,x){ malloc(q);

q->data＝p->data; q->next＝p->next; p->next＝q; p->data＝x; }

(6) elemtype min(HL){

//从循环单链表HL中查找出最小值 if (HL= =nil ) {

printf('HL＝nil'); return; }

min＝HL->data; p＝HL->next; while (p!=HL) {

(1) if (p->datadata; (2) p＝p->next; }

33

}

(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 ; // 把最后一个结点的指针域置空 }

23.这是一个递归过程，n执行一次就减2，当n≤0时该过程执行结束。因此，当n＝5 时，其输出结果为1、3、5；当n＝6时，其输出结果为2、4、6。 24.循环链队的插入和删除操作 (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)status delete(Rear){

if( Rear＝nil ) error('underflow'); if (Rear->next= =Rear) Rear＝nil; else Rear->next＝Rear->next->next;

} //Rear＾.next 所指向的结点为循环链队的队首结点 25.解答

(1)查找x＝1,n …… 此处隐藏：1413字，全部文档内容请下载后查看。喜欢就下载吧 ……