【数据结构】单链表应用1

1.删除链表A中与B重复的元素，输出单链表A

主要是用到查找和删除算法

//扣掉A中与B中重复的元素，输出A链表
#include<stdio.h>
 
typedef struct Lnode{
	int data;
	struct Lnode *next;
}Lnode,*LinkList;
void DeleteList(LinkList &A,LinkList &B);
 
void InsertList(LinkList &L,int n,int a[]);
int main(){
	LinkList A,B;
	Lnode *p;
	int a[]={2,3,6,7,9,14,56,45,65,67};//两个数组
	int b[]={3,4,7,11,34,54,45,25};
	InsertList(A,sizeof(a)/sizeof(a[0]),a);
	InsertList(B,sizeof(b)/sizeof(b[0]),b);
	int ListLengthA=sizeof(a)/sizeof(a[0]);
	int ListLengthB=sizeof(b)/sizeof(b[0]);
	
	p=A->next;
	while(p){
		printf("%d ",p->data); 
		p=p->next;
	}	
	printf("\n");
	p=B->next;
	while(p){
		printf("%d ",p->data); 
		p=p->next;
	}
	printf("\n");
    DeleteList(A,B);
    p=A->next;
	while(p){
		printf("%d ",p->data); 
		p=p->next;
	}
}
//尾插法建立单链表，将数组里数变到单链表中
void InsertList(LinkList &L,int n,int a[]){
	L=new Lnode;
	L->next=NULL;
	Lnode *p;
	Lnode *r=L;
	int i;
	for(i=0;i<n;i++){
		p=new Lnode;
		p->data=a[i];
		r->next=p;
		r=p;
	}
	r->next=NULL;//设置A，B链表的尾结点指针域都为空
}
//这个函数里面主要是进行查找和删除工作
void DeleteList(LinkList &A,LinkList &B){
//为删除进行定义准备
	Lnode *pre;                      
	Lnode *p,*q,*r;
	pre=A;
//进行查找：依此取A中的元素，去B中查找	
    p=A->next;
	while(p){ 
		q=B->next;
		while(q&&q->data!=p->data){
			q=q->next;
		}
		//如果查找出的结果是找到了，那么进行删除，删除p指针所指的元素
		if(q){
			pre->next=p->next;
			r=p;
			p=p->next;
			delete r;
		//如果查找结果为没找到，则让pre指针指向将要进行被查找的元素的前一个
		}else{ 
			pre=p;
			p=p->next;
		}
	}
}
//删除算法的步骤就是1.找到要删除元素的前一个指针2.另设变量，开始链接3.释放要删除元素的指针
 
//这道题的pre指针就充当着将要删除元素的前一个指针

2.两个一般线性表合并

主要是用到查找和插入算法

#include<stdio.h>
#include<stdlib.h>
typedef struct Lnode{
	int data;
	struct Lnode *next;
}Lnode,*LinkList;
void InsertList(LinkList &L,int n,int a[]);
void MergeList(LinkList &A,LinkList &B);
int main(){
	LinkList A,B,C;
	Lnode *p;
	int a[]={7,5,3,11};//两个数组
	int b[]={2,6,3};
	InsertList(A,sizeof(a)/sizeof(a[0]),a);
	InsertList(B,sizeof(b)/sizeof(b[0]),b);
	   
	p=A->next;
	while(p){
		printf("%d ",p->data); 
		p=p->next;
	}
	printf("\n");
	p=B->next;
	while(p){
		printf("%d ",p->data); 
		p=p->next;
	}
	printf("\n");
	MergeList(A,B);
	p=A->next;
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
}
 //尾插法建立单链表，将数组里数变到单链表中
void InsertList(LinkList &L,int n,int a[]){
	L=new Lnode; 
	L->next=NULL;
	Lnode *p;
	Lnode *r=L;
	int i;
	for(i=0;i<n;i++){
		p=new Lnode;
		p->data=a[i];
		r->next=p;
		r=p;
	}
	r->next=NULL;
}
//这个函数主要用到查找和插入
void MergeList(LinkList &A,LinkList &B){ 
//进行插入工作的准备
	Lnode *p,*q,*r;
	p=A->next;
	int j=1;
	while(p&&j<4){
		p=p->next;//让p最终指向链表A的最后一个结点
		j++;
	}
	//依此取B元素，在A链中查找
	q=B->next;
	while(q){
		r=A->next;
		while(r&&r->data!=q->data){
			r=r->next;
		}
		if(!r){ //如果r为空，则说明B中的这个元素要插入在A后
		//下面是插入的算法
			LinkList s;
			s=new Lnode;
			s->data=q->data;
			s->next=p->next;
			p->next=s;
		}
		q=q->next;
	}
}