《数据结构题集》参考答案2 线性表

第二章 线性表 ◆2.11② 设顺序表L中的数据元素递增有序。 试写一算法，将x插入到L的适当位置上，并保 持该表的有序性。

要求实现下列函数： void InsertOrderList(SqList &L, ElemType x) /* 在有序的顺序表 L 中保序插入数据元素 x */

顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList;

void InsertOrderList(SqList &L, ElemType x) // 在有序的顺序表 L 中保序插入数据元素 x { int j,i=L.length-1; while (x=0) i--; for (j=L.length-1;j>i;j--) { L.elem[j+1]=L.elem[j]; } L.elem[i+1]=x; L.length++; }

◆2.12③ 设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表， A'和B'分别为A和B中除去最大共同前缀后的子表（例如， A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大 的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后 的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表， 则A=B；若A'=空表，而B'≠ 空表，或者两者均不为空表， 且A'的首元小于B'的首元，则AB。试写一个比 较A和B大小的算法。（注意：在算法中，不要破坏原表A 和B，也不一定先求得A'和B'才进行比较）。

要求实现下列函数： char Compare(SqList A, SqList B); /* 比较顺序表A和B, */ /* 返回'<', 若A/* '=', 若A=B; */ /* '>', 若A>B */

顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList;

char Compare(SqList A, SqList B) // 比较顺序表A和B, // 返回'<', 若A// '=', 若A=B; // '>', 若A>B { int i=0,j=0; while (i { if (A.elem[i]!=B.elem[j]) { if (A.elem[i] else return '>'; } else { i++; j++; } } if (i==j) return '='; else if (i==A.length) return '<'; else return '>'; } 2.13② 试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x)。

实现下列函数： LinkList Locate(LinkList L, ElemType x); // If 'x' in the linked list whose head node is pointed // by 'L', then return pointer pointing node 'x', // otherwise return 'NULL'

单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

LinkList Locate(LinkList &L, ElemType x) // If 'x' in the linked list whose head node is pointed // by 'L', then return pointer ha pointing node 'x', // otherwise return 'NULL' { LinkList P; P=L->next; while (P!=NULL&&P->data!=x) {P=P->next;} return P;

}

2.14② 试写一算法在带头结点的单链表结构上实现线性表 操作Length(L)。

实现下列函数： int Length(LinkList L); // Return the length of the linked list // whose head node is pointed by 'L'

单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; int Length(LinkList L) // Return the length of the linked list // whose head node is pointed by 'L' { int i=0; LinkList P; P=L->next; while (P!=NULL) { P=P->next; i++; } return i; }

2.16③ 已知指针la和lb分别指向两个无头结点单链表中 的首元结点。 下列算法是从表la中删除自第i个元素起共 len个元素后，将它们插入到表lb中第i个元素之前。试问 此算法是否正确? 若有错，则请改正之。

实现下列函数： Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len); // la和lb分别指向两个单链表中第一个结点， */ /* 本算法是从la表中删去自第i个元素起共len个元素，*/ /* 并将它们插入到lb表中第j个元素之前， */ /* 若lb表中只有j-1个元素，则插在表尾。 */

单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len) // la和lb分别指向两个单链表中第一个结点， */ /* 本算法是从la表中删去自第i个元素起共len个元素，*/ /* 并将它们插入到lb表中第j个元素之前， */ /* 若lb表中只有j-1个元素，则插在表尾。 */ { if(i<=0 || j<=0 || len<=0) return INFEASIBLE; //i,j,len初检 LNode *p,*q,*o,*r; int m=0,n=0,l=1; p=(LinkList)malloc(sizeof(LNode)); q=(LinkList)malloc(sizeof(LNode)); p->next=la; //建立临时头结点p q->next=lb; //建立临时头结点q la=p; lb=q; while(p->next!=NULL && m<(i-1)) {p=p->next;m++;}//判断是否存在并且将p定位在第i-1个元素 if(p->next==NULL && m<(i-1)) { p=la;q=lb;la=la->next;lb=lb->next; free(p);free(q);//删除临时头结点p,q return INFEASIBLE; } r=o=p->next; while(o!=NULL && lnext;l++;}//判断是否存在len个元素 if(o==NULL || l { p=la;q=lb;la=la->next;lb=lb->next; free(p);free(q);//删除临时头结点p,q return INFEASIBLE; } while(q->next!=NULL && n<(j-1)) {q=q->next;n++;}//判断是否存在并且将q定位在第j-1个元素 if(q->next==NULL && n<(j-1)) { p=la;q=lb;la=la->next;lb=lb->next; free(p);free(q);//删除临时头结点p,q return INFEASIBLE; } p->next=o->next;//执行插入 o->next=q->next; q->next=r; p=la;q=lb;la=la->next;lb=lb->next; free(p);free(q);//删除临时头结点p,q return OK; }