单链表的常见基础算法（三）

男娘i 2023-05-30 15:54 9阅读 0赞

*  **将带头结点的单链表A分解成两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持相对顺序不变**

LinkList Dis_List(LinkList &A){
        
    	LinkList B=(LinkList)malloc(SizeOf(LNode));
    	LNode *p=A->next,*ra=A->next;
    	A->next=NULL;
    	B->next=NULL;
    	LNode *rb=B->next;
    	//设置i计数用来区分奇偶
    	int i=0;
    	while(p!=NULL){
        
    		i++;
    		if(i%2==1){
        // 该结点为奇数，插入A表中
    			ra->next=p;
    			ra=p
    		}else{
        
    			rb->next=p;
    			rb=p;
    		}
    		p=p->next;
    	}
    	ra->next=NULL;
    	rb->next=NULL;
    	return B;
    }

*  **将C=\{a1,b1,a2,b2…an,bn\}线性表采用带头结点的单链表存放，设计一个算法，将其拆分为两个线性表，使得A=\{a1,a2,…an\},B=\{bn,…b2,b1\}**

//A采用尾插法，B采用头插法。在插入过程中，先插入一次A,再插入一次B
    LinkList Dis_List(LinkList &C){
        
    	LinkList A=C;
    	LinkList B=(LinkList)malloc(SizeOf(LNode));
    	LNode *ra=A; LNode *rb=B,*p=A->next,*q;
    	while(p!=NULL){
        
    		//对A进行尾插法
    		ra->next=p;
    		ra=p;
    		p=p->next;
    		q=p->next;
    		//对B进行头插法
    		p->next=rb->next;
    		rp->next=p;
    		p=q;
    	}
    	ra->next=NULL;
    	return B;
    }

*  **在一个递增有序的线性表中，单链表存储，设计算法删除表中数值相同的元素**

LinkList Del_Same(LinkList &L){
        
    	LNode *p=L->next,*q;
    	if(p==NULL) return NULL;
    	while(p->next!=NULL){
        
    		q=p->next;
    		if(p->data==q->data){
        
    			p->next=q->next;//删除相同元素
    			free(q);
    		}else{
        
    			p=p->next;
    		}
    		return L;
    	}
    }

*  **有两个按元素值递增次序排列的单链表。编写算法实现将这两个单链表归并为一个按元素值递减次序排列的单链表**

void Merge(LinkList L1,LinkList L2,LinkList &L3){
        
    	//采用头插法，将两个线性表中较小的元素插入
    	LNode *p1=L1->next,*p2=L2->next,*q1,*q2;
    	L3->next=NULL;
    	LNode *p3=L3;
    	while(p1->next!=NULL&&P2->next!=NULL){
        
    		if(p1->data<p2->data){
        
    			q1=p1->next;
    			p1->next=p3->next;
    			p3=>next=p1;
    			p1=q1;
    		}else{
        
    			q2=p2->next;
    			p2->next=p3->next;
    			p3->next=p2;
    			p2=q2;
    		}
    	}
    	while(p1->next!=NULL){
        
    		q1=p1->next;
    		p1->next=p3->next;
    		p3->next=p1;
    		p1=q1;
    	}
    	while(p2->next!=NULL){
        
    		q2=p2->next;
    		p2->next=p3->next;
    		p3->next=p2;
    		p2=q2;
    	}
    	free(L1);
    	free(L2);
    }

*  **A\\B是两个单链表，其中元素递增有序，设计一个算法从A和B中的公共元素中产生单链表C，要求不破坏A,B的结点**

LinkList Get_Common(LinkList L1,LinkList L2,LinkList &L3){
        
    	L3->next=NULL;
    	LNode *p1=L1->next,*p2=L2->next,*p3=L3;
    	while(p1!=NULL&&p2!=NULL){
        
    		if(p1->data==p2->data){
        
    			//将公共元素插入C
    			LNode *s=(LNode *)malloc(SizeOf(LNode));
    			s->data=p1->data;
    			p3->next=s;
    			p3=s;
    			p1=p1->next;
    			p2=p2->next;
    		}else if(p1->data<p2->data){
        
    				p1=p1->next;
    			}else{
        
    				p2=p2->next
    			}
    	}
    	p3->next=NULL;
    }

*  **A\\B表示两个链表，其元素递增排列，求A与B 的并集，并存放于A链表中**

LinkList Union(LinkList &la,LinkList lb){
        
    	LNode *pa=la->next, *pb=lb->next *pre=la,*qa,*qb;
    	while(pa!=NULL&&pb!=NULL){
        
    		if(pa->data<pb->data){
        
    			qa=pa;
    			pa=pa->next;
    			free(qa);
    			qb=pb;
    			free(qb);
    		}
    		else if(pa->data>pb->data){
        
    			qb=pb;
    			pb=pb->next;
    			free(qb);
    			qa=pa;
    			free(qa);
    		}
    		else{
        
    			pre->next=pa;
    			pre=pa;
    			pa=pa->next;
    			qb=pb;
    			pb=pb->next;
    			free(qb)
    		}
    	}
    	while(pa!=NULL){
        
    		qa=pa;
    		pa=pa->next;
    		free(qa);
    	}
    	while(pb!=NULL){
        
    		qb=pb;
    		pb=pn->next;
    		free(qb);
    	}
    	pre->next=NULL;
    	free(lb);
    	return la;
    }

*  **判断带头结点的循环双链表是否对称**

bool Symmetry(LinkList L){
        
    	DNode *p=L->next,*r=L->prior;;
    	while(p!=r||r->next!=p){
        
    		if(p->data==r->data){
        
    			p=p->next;
    			r=r->prior;
    		}else{
        
    			return false;
    		}
    	}
    	return true;
    }

*  **尾插法建立双链表**

void CreateList(DLinkList &L){
        
    	L=(DLinkList)malloc(SizeOf(DLNode));
    	DLNode *r,*s;
    	ElemType x;
    	r=L;
    	cin>>x;
    	while(x!=9999){
        
    		s=(DLNode *)malloc(SizeOf(DLNode));
    		s->data=x;
    		r->next=s;
    		s->prior=r;
    		r=s;
    		cin>>x;		
    	}
    	r->next=NULL;
    }

*  **寻找两个单链表的公共结点**

void GetCommonNode(LinkList La,LinkList Lb){
        
    	LNode *long,short;
    	int len1=La.length(La);
    	int len2=Lb.length(Lb);
    	int len;
    	if(len1>len2){
        
    		long=La->next;
    		short=Lb->next;
    		len=len1-len2;
    	}else{
        
    		long=Lb->next;
    		short=La->next;
    		len=len2-len1;
    	}
    	while(len!=0){
        
    		long=long->next;
    		len--;
    	}
    	while(long!=short&&long!=NULL){
        
    		long=long->next;
    		short=short->next;
    	}
    	return long;
    }

*  **对两个无头结点的单链表ha,hb，按递增顺序存放。现将hb表归并到ha表中，且归并后hb仍然有序，归并后ha、hb共有数据不归并到ha中，ha,hb的链表不允许被破坏**

void Merge(LinkList &ha,LinkList &hb){
        
    	//为ha新增一个头结点
    	LinkList L=(LinkList)malloc(SizeOf(LNode));
    	LNode *pa=ha,*pb=hb;//工作指针
    	LNode *pre=L;
    	while(pa!=NULL&&pb!=NULL){
        
    		if(pa->data<pb->data){
        
    			pre->next=pa;
    			pre=pa;
    			pa=pa->next;
    		}
    		else if(pa->data>pb->data){
        
    			LNode *s=(LNode *)malloc(Sizeof(LNode));
    			s->data=pb->data;
    			s->next=pa;
    			pre->next=s;
    			pre=s;
    			pb=pb->next;
    		}else{
        
    			pre->next=pa;
    			pre=pa;
    			pa=pa->next;
    			pb=pb->next;
    		}
    	}//while
    	if(pa!=NULL){
        
    		pre=pre->next;
    	}
    	if(pb!=NULL){
        
    		pre->next=pb;
    	}
    	free(L);
    }