西北大学《数据结构》典型例题（1-5章）(4)

C=A;A->next=pc; //构造新表头 }//reverse_merge

分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25

void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中 {

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j]) {

if(A.elem[i]B.elem[j]) j++; if(A.elem[i]==B.elem[j]) {

C.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素, i++;j++; //就添加到C中 } }//while

}//SqList_Intersect 2.26

void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题 {

p=A->next;q=B->next;

pc=(LNode*)malloc(sizeof(LNode)); while(p&&q) {

if(p->datadata) p=p->next; else if(p->data>q->data) q=q->next; else {

s=(LNode*)malloc(sizeof(LNode));

s->data=p->data; pc->next=s;pc=s; p=p->next;q=q->next; } }//while C=pc;

}//LinkList_Intersect 2.27

void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中 {

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j]) {

if(A.elem[i]B.elem[j]) j++; else if(A.elem[i]!=A.elem[k]) {

A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素 i++;j++; //且C中没有,就添加到C中 } }//while

while(A.elem[k]) A.elem[k++]=0; }//SqList_Intersect_True 2.28

void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题 {

p=A->next;q=B->next;pc=A; while(p&&q) {

if(p->datadata) p=p->next; else if(p->data>q->data) q=q->next; else if(p->data!=pc->data)

{

pc=pc->next; pc->data=p->data; p=p->next;q=q->next; } }//while

}//LinkList_Intersect_True 2.29

void SqList_Intersect_delete(SqList &A,SqList B,SqList C)//从有序顺序表A中删除那些在B和C中都出现的元素 {

i=1;j=1;k=1;

while(B.elem[i]&&C.elem[j]) {

if(B.elem[i]C.elem[j]) j++; else //找到了需要从A中删除的元素 {

u=B.elem[i];

while(A.elem[k]

A.elem[k]=INFINITY; //把A中待删除元素置换为特殊记号 while(B.elem[i]==u) i++; while(C.elem[j]==u) j++; }//else }//while

for(i=1,j=1;j<=A.length;i++) //第二遍扫描A,删除特殊记号 {

while(A.elem[j]==INFINITY) {

j++;A.length--; }

if(i

j++; }//for

}//SqList_Intersect_delete

分析:本算法的时间复杂度为O(m),m为表长.思考:你自己的算法时间复杂度是多少?实际上也可以只用一遍扫描就完成整个操作,且时间复杂度也为O(m),但非常复杂,你能写出来吗? 2.30

void LinkList_Intersect_delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题 {

p=B->next;q=C->next;r=A-next; while(p&&q&&r) {

if(p->datadata) p=p->next; else if(p->data>q->data) q=q->next; else {

u=p->data; //确定待删除元素u

while(r->next->datanext; //确定最后一个小于u的元素指针r if(r->next->data==u) {

s=r->next; while(s->data==u) {

t=s;s=s->next;free(t); //确定第一个大于u的元素指针s }//while

r->next=s; //删除r和s之间的元素 }//if

while(p->data=u) p=p->next; while(q->data=u) q=q->next; }//else }//while

}//LinkList_Intersect_delete

2.31

Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱 { p=s;

while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p p->next=s; return OK; }//Delete_pre 2.32

Status DuLNode_pre(DuLinkList &L)//完成双向循环链表结点的pre域 {

for(p=L;!p->next->pre;p=p->next) p->next->pre=p; return OK; }//DuLNode_pre 2.33

Status LinkList_divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型. {

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) {

if(isalphabet(s->data)) {

p->next=s;p=s; }

else if(isdigit(s->data)) {

q->next=s;q=s; } else