内容发布更新时间 : 2024/5/10 4:56:35星期一 下面是文章的全部内容请认真阅读。
qb->next=pb; free(pt); } pb=B; free(pb); return OK; } (2)
// A、B求交，结果放在A表中，并删除相同元素
Status ListCrossDelSame_L(LinkList &A,LinkList &B) {
LinkList pa,pb,qa,qb,pt; pa=A; pb=B;
qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; while(pa&&pb){
if(pa->data
pa=pa->next; qa->next=pa; free(pt); } else
if(pa->data>pb->data){ pt=pb;
pb=pb->next; qb->next=pb; free(pt); }
else{
if(pa->data==qa->data){ pt=pa;
pa=pa->next; qa->next=pa; free(pt); } else{
qa=pa;
pa=pa->next; } }
精选
}
while(pa){ pt=pa;
pa=pa->next; qa->next=pa; free(pt); }
while(pb){ pt=pb;
pb=pb->next; qb->next=pb; free(pt); } pb=B; free(pb); return OK; } 2.29 已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。
解：
// 在A中删除既在B中出现又在C中出现的元素，结果放在D中 Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C) {
SqList Temp;
InitList_Sq(Temp);
ListCross_L(B,C,Temp); ListMinus_L(A,Temp,D); }
2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。
解：
// 在A中删除既在B中出现又在C中出现的元素，并释放B、C Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C) {
ListCross_L(B,C); ListMinus_L(A,B); }
// 求集合A-B，结果放在A表中，并删除B表 Status ListMinus_L(LinkList &A,LinkList &B) {
LinkList pa,pb,qa,qb,pt; pa=A; pb=B;
精选
qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; while(pa&&pb){
if(pb->data
pb=pb->next; qb->next=pb; free(pt); } else
if(pb->data>pa->data){ qa=pa;
pa=pa->next; }
else{
pt=pa;
pa=pa->next; qa->next=pa; free(pt); } }
while(pb){ pt=pb;
pb=pb->next; qb->next=pb; free(pt); } pb=B; free(pb); return OK; }
2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
解：
// 在单循环链表S中删除S的前驱结点 Status ListDelete_CL(LinkList &S) {
LinkList p,q;
if(S==S->next)return ERROR; q=S;
p=S->next;
精选
while(p->next!=S){ q=p;
p=p->next; }
q->next=p->next; free(p); return OK; }
2.32 已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。
解：
// 建立一个空的循环链表
Status InitList_DL(DuLinkList &L) {
L=(DuLinkList)malloc(sizeof(DuLNode)); if(!L) exit(OVERFLOW); L->pre=NULL; L->next=L; return OK; }
// 向循环链表中插入一个结点
Status ListInsert_DL(DuLinkList &L,ElemType e) {
DuLinkList p;
p=(DuLinkList)malloc(sizeof(DuLNode)); if(!p) return ERROR; p->data=e;
p->next=L->next; L->next=p; return OK; }
// 将单循环链表改成双向链表
Status ListCirToDu(DuLinkList &L) {
DuLinkList p,q; q=L;
p=L->next; while(p!=L){ p->pre=q; q=p;
p=p->next; }
精选
if(p==L) p->pre=q; return OK; }
2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。
解：
// 将单链表L划分成3个单循环链表
Status ListDivideInto3CL(LinkList &L,LinkList &s1,LinkList &s2,LinkList &s3) {
LinkList p,q,pt1,pt2,pt3; p=L->next; pt1=s1; pt2=s2; pt3=s3; while(p){
if(p->data>='0' && p->data<='9'){ q=p;
p=p->next;
q->next=pt1->next; pt1->next=q; pt1=pt1->next; } else
if((p->data>='A' && p->data<='Z') || (p->data>='a' && p->data<='z')){ q=p;
p=p->next;
q->next=pt2->next; pt2->next=q; pt2=pt2->next; }
else{ q=p;
p=p->next;
q->next=pt3->next; pt3->next=q; pt3=pt3->next; } } q=L; free(q); return OK;
精选