数据结构算法练习2——链表

冷不防 2023-02-25 02:26 20阅读 0赞

1，设计一个递归算法，删除不带头节点的单链表L中所有值为x的节点

void Del_X(LinkList &L,Elemtype x){
    	LNode *p;//p指向待删除的节点
    	if(L==NULL)
    	return;
    	if(L->data==x){//如果找到节点值为X的元素 
    		p=L;//将L的引用传给p ，用来删除 
    		L=L->next;//进入上个节点 
    		free(p);//删除节点，因为p为L的引用，是对原链表进行操作，因此不会断链 
    		Del_X(L,x);//递归掉用 
    	}
    	else
    	Del_X(L->next,x);
    }

2，在带头节点的单链表L中，删除所有值为x的节点，并释放其空间，假设值为x不唯一。

void Del_X2(LinkList &L,Elemtype x){
    	LNode *p=L->next,*pre=L,*q;
    	while(p){
    		if(p->data==x){//找到值为x的节点 
    			q=p;//q指向该节点，待删除 
    			pre->next=p->next;//p的前驱节点指针域指向p的后继节点 
    			p=p->next;//遍历下一个元素 
    			free(q);//删除节点，释放空间 
    		}
    		else{//遍历下一节点 
    			pre=p;
    			p=p->next;
    		}
    	}
    }

3，设L为带头结点的单链表，编写算法实现从尾到头方向输出每个节点的值

void R_print(LinkList &L){
    	if(L->next!=NULL){//如果下一节点存在就继续遍历，直到最后一个节点 
    		R_print(L->next);//到达尾结点时，打印数值——》跳出本次函数，打印——》跳出本次函数，打印。。。 
    	}
    	printf("%d/n",L->data);
    }

4，在带头结点的单链表L中删除一个最小值节点的高效算法（假设最小值唯一）

void Del_min(LinkList &L){
    	LNode *p=L->next,*pre=L;
    	LNode *minPre=pre,*min=p;//存储最小值节点的前驱节点，和最小值节点 
    	
    	while(p){
    		if(p->data<min->data){//遍历链表得到最小值节点 
    			min=p;
    			minPre=pre;
    		}
    		else{//遍历下一节点 
    			pre=p;
    			p=p->next;
    	}}
    	minPre->next=min->next;//p的前驱节点指针域指向p的后继节点 
    	free(min);//删除节点，释放空间 
    	
    }

5，将带头节点的单链表L就地逆置，要求辅助空间的空间复杂度为O(1)

//方法一：将每个前端取下，使用头插法实现
    LinkList Reverse_1(LinkList &L){
    	LNode *p,*r;//p为工作指针，r为p的后继防止锻链
    	p=L->next;//从第一个节点开始,p为最前端的节点 
    	L->next=NULL;//先将头结点的指针域置为空,与原链表断开 
    	while(p){
    		r=p->next;//暂存p的后继节点
    		p->next=L->next;//将L第一个节点值给P的指针域，
    		L->next=p; //使用头插法将链表中的前端结点取出插到头节点之后
    		p=r; 
    	} 
    	return L;
    }

//方法二：将每个next的值存储为其前节点的地址
     
    LinkList Reverse_2(LinkList &L){
    	LNode *p=L->next,*pre,*r=p->next;//p为工作指针，r为p的后继防止锻链
    	p->next=NULL;//先将头结点的指针域置为空,它成为尾结点 
    	while(r!=NULL){//r为空说明是最后一个节点 
    		pre=p;//依次遍历 
    		p=r;
    		r=r->next;
    		p->next=p;//指针反转 
    		p=r; 
    	} 
    	L->next=p;//将最后一个节点作为头结点，接入表头 
    	return L;
    }

6，设计算法使得带头结点的单链表L中的元素递增有序

void Sort(LinkList &L){
    	LNode *p=L->next,*pre;
    	LNode *r=p->next;//r保持为*p的后继节点指针，保证不断链 
    	p->next=NULL;//构造只含一个节点的有序表
    	p=r;
    	while(p!=NULL){
    		r=p->next;//暂存p的后继节点指针 
    		while(pre->next!=NULL&&pre->next->data<p->data)
    		//在有序表中如果有元素并且不是尾结点元素满足小于要插入的节点，就将节点插入相邻节点之间。
    		//不满足要求就说明是最大值插到末尾  
    			p->next=pre->next;
    		pre->next=p;//将p插入到pre之后 
    		p=r;//扫描剩下的点 
    	} 
    }

7，设一个带表头节点的单链表中的所有元素都是无序的，编写一个函数，删除表中所有介于给定两个值之间的元素

void RangeDelete(LinkList &L,int min,int max){
    	LNode *pr=L,*p=L->next;//p是检查指针，pr是其前驱 
    	while(p){
    		if(p->data>min&&p->data<max){//寻找待删除节点 
    			pr->next=p->next;
    			free(p);
    			p=pr->next;
    		}
    		else{//遍历 
    			pr=p;
    			p=p->next;
    		}
    	}
    }

8，给定两个单链表，给写算法求出两个第一个的公共节点。

int Length(LinkList &L){
    	LNode *p=L->next;
    	int len=0;
    	while(p){
    		len++;
    		p=p->next;
    	}
    	return len;
    } 
    //只要两个表可以同时遍历到最后一个节点，并且最后节点相同，则两个表有公共节点 
    LinkList Search_lst_Common(LinkList &L1,LinkList &L2){
    	int len1=Length(L1),len2=Length(L2);//求表长 
    	int dist;//记录表长之差 
    	LinkList longList,shortList;
    	if(len1>len2){
    		longList=L1->next;
    		shortList=L2->next;
    		dist=len1-len2;
    	}
    	else{
    		longList=L2->next;
    		shortList=L1->next;
    		dist=len2-len1;
    	}
    	while(dist--){//长表先遍历dist个元素然后两个表一起遍历 
    		longList=longList->next; 
    }	
    	while(longList){
    		if(longList==shortList)//寻找第一个公共点
    			return longList;
    		else{
    			longList=longList->next;
    			shortList=shortList->next;
    		} 
    	} 
    	return NULL;
     }

9，给定一个带表头节点的单链表，按递增顺序输出链表元素，并释放节点空间

//遍历链表，找到最小元素，打印值并删除 
    void Min_delete(LinkList &L){
    	LNode *p,*pre;
    	LNode *min=p,*minPre=pre; 
    	while(p!=NULL){
    		pre=L;//每次都从链表头部开始重新遍历，寻找最小值节点 
    		p=pre->next;
    		min=p;
    		minPre=pre;
    		while(p){//找出本次循环最小值节点，并删除 
    		if(p->data<min->data){
    			min=p;
    			minPre->next=pre; 
    		}
    		else{
    			pre=p;
    			p=p->next;
    		}
    	}
    	minPre->next=min->next;
    	free(min);
    	}
    }

10，将单链表A分为两个带头节点的链表B和C，B中存放原表奇序号元素，C存放偶序号元素

LinkList DisCreat(LinkList &A){
    	int i=0;//用来标记奇偶序号
    	LNode *B=(LinkList)malloc(sizeof(LNode));//创建B表表头 
    	B->next=NULL;//B表初始化 
    	LNode *ra,*rb;//分别指向A表和B表的尾结点
    	LNode *p=A->next;
    	A->next=NULL;//置空成为新A表 
    	while(p){
    		i++;
    		if(i%2==0){//将节点插入B表 
    			rb->next=p;
    			rb=p;
    		}
    		else{//将节点插入A表 
    			ra->next=p;
    			ra=p;
    		}
    		p=p->next;//将p恢复指向新的节点处理 
    	} 
    	ra->next=NULL;//处理表尾节点 
    	rb->next=NULL;
    	return B; 
    	 
    }

11，设链表A=\{a1,b1,a2,b2,,,,an,bn\}将其变为链表 A=\{a1,a2,,,an\} 和链表B=\{bn,,,b2,b1\}

//B表采用头插法实现逆序，A表尾插法顺序存储 
    LinkList DisCreat2(LinkList &A){
        LNode *B=(LinkList)malloc(sizeof(LNode));//创建B表表头 
        B->next=NULL;//B表初始化 
        LNode *ra;//指向A表尾结点 
        LNode *p=A->next,*q;//p为工作指针，q是为了防止断链记录p的后继节点指针 
        while(p){
            ra->next=p; ra=p;//将p节点插到A表尾
            p=p->next;
            q=p->next;//记录当前节点的后继节点位置，防止断链
            p->next=B->next;//将节点插入到B表前端 
            B->next=p ;
             
        } 
        ra->next=NULL;//处理表尾节点 
        return B; 
         
    }

12，去除递增有序带头节点链表中的相同元素，使得表中无重复元素

void Delete_Same(LinkList &L){
        LNode *p=L->next;//工作指针 
        LNode *q=p->next;//q是p的后继节点 
        while(p){
            if(p->data==q->data){//后继节点值与本节点值一样，删除后继节点 
                p->next=q->next;
                free(q);
                q=p->next;
            }
            else{
                p=q;
                q=q->next; 
            }
        } 
    }

13，将两个元素值递增排序的长度相同单链表A,B，合并成为一个元素值递减的单链表，要求利用原来的节点存放归并后的单链表

void MergeList(LinkList &A,LinkList &B){
        LNode *pa=A->next, *pb=B->next,*r;
        A->next=NULL;//A作为结果链表的头指针
        while(pa&&pb){//遍历A,B相同表长将它们使用头插法插入表中 
            if(pa->data<=pb->data){
                r=pa->next;//r暂存后继节点，防止断链 
                pa->next=A->next;
                A->next=pa;
                pa=r;
            }
            else{
                r=pb->next;
                pb->next=A->next;
                A->next=pb;
                pb=r;
            } 
        } 
        if(pa){//处理长表中剩下的部分 
            pb=pa;
        } 
        while(pb){
            r=pb->next;
            pb->next=A->next;
            A->next=pb;
            pb=r;
        }
        free(B);
    }

14，从两个元素值递增排序的长度相同单链表A,B，产生AB相同元素单链表C

void Get_common(LinkList &A,LinkList &B){
        LNode *pa=A->next,*pb=B->next;
        LinkList C=(LinkList)malloc(sizeof(LNode));
        C->next=NULL;
        LNode *r=C,*s;//r用来指向C的尾结点,s用来产生值相等时的节点 
        while(pa!=NULL&&pb!=NULL){
            if(pa->data<pb->data)//A的值较小，后移指针 
                pa=pa->next;
            else if(pa->data>pb->data)//B的值较小，后移指针 
                pb=pb->next;
            else{//两个节点值相等时，生成一个相同值节点插入表尾 
                s=(LNode*)malloc(sizeof(LNode));
                s->data=pa->data;
                r->next=s;
                r=s;
                pa=pa->next;//继续遍历 
                pb=pb->next; 
            }
            
        }
        r->next=NULL;//将C表尾结点指针置为空 
        
    }

15，A，B两个链表表示两个集合，其元素递增排列，求A,B交集存放在A中，B去除

void Union(LinkList &A,LinkList &B){
        LNode *pa=A->next,*pb=B->next,*r,*pc=A;//pa,pb是操作指针，r暂存待删除的指针空间，pc是新链表尾指针 
        LinkList C=(LinkList)malloc(sizeof(LNode));
        while(pa!=NULL&&pb!=NULL){
            if(pa->data<pb->data){//A的值较小，删除节点并后移指针 
                r=pa; 
                pa=pa->next;
                free(r);
        }
                
            else if(pa->data>pb->data){//B的值较小，删除节点并后移指针 
                r=pb; 
                pb=pb->next;
                free(r);    
            }
                
            else{//两个节点值相等时，生成一个相同值节点插入表尾 
                pc->next=pa;//将pa节点尾插入链表中 
                pc=pa; 
                pa=pa->next;//pa遍历下一个元素 
                r=pb;
                pb=pb->next;//继续遍历 
                free(r); 
            }
            
        }
        pc->next=NULL;//将C表尾结点指针置为空 
        free(B);
        return A;
        
    }

16，已知两个序列链表A，B，设计一个算法判断B是否是A的子序列

int Pattern(LinkList A,LinkList B){
    	LNode *pa=A,*pb=B,*pre=A;//pa,pb是A，B的工作指针，pre记住每趟比较中A链表的开始节点
    	while(pa&&pb){
    		if(pa->data==pb->data){//如果两个序列，该节点元素值相等，同时下移比较下一个节点 
    			pa=pa->next;
    			pb=pb->next;
    		}
    		else{//元素值不相等，A进入下一节点 
    			pre=pre->next;
    			pa=pre;
    		}
    	} 
    	if(pb==NULL)//pb为空，链表B遍历完了，说明B中的元素在A中都存在 
    		return 1;//B是A的子序列
    	else
    	return 0; 
    }

17，判断带头节点的循环双链表是否对称

bool Symmetry(DLinkList L){
    	//前后遍历双链表，判断收尾对应位置值是否相等 
    	DNode *p=L->next,*q=L->prior; 
    	while(p!=q&&q->next!=p){
    	//奇数节点前驱与后继指针同时指向一个节点时结束，偶数节点时后继节点是前驱节点时结束 
    		if(p->data==q->data){
    			p=p->next;
    			q=q->prior;
    		}
    		else
    		return false;
    	}
    	return true;
    }

18，有两个循环单链表，链表表头为A，B。将B接到A之后，链表仍然是循环链表

//找到两个链表的表尾指针，改变它们的指针域
    LinkList Link(LinkList &A,LinkList &B){
    	LNode *pa=A->next,*pb=B->next;
    	while(pa->next!=A){
    		pa=pa->next;
    	}
    	while(pb->next!=B){
    		pb=pb->next;
    	}
    	pa->next=B;
    	pb->next=A;
    	return A;
    }

19，将带头结点单循环链表中的元素从小到达输出，并删除节点。

void Delete_print(LinkList &L){
    	LNode *p=L->next,*pre=L;
    	LNode *min=p,*minPre=pre;
    	while(p){//如果链表中除头节点外还有节点，遍历链表 
    		while(p->next!=L){//找到最小节点的指针 
    		if(p->data>min->data){
    			min=p;
    			minPre=pre;
    		}
    		else{
    			pre=p;
    			p=p->next;
    		}
    	}
    	printf("%d",min->data); 
    	minPre->next=min->next;//删除最小值节点 
    	free(min);
    	}
    	free(L);//删除头节点 
    	
    }

20，查找带头结点单链表中倒数k个节点并输出它的数据

LNode* Search(LinkList &L,int k){
    	LNode *p=L->next,*q=L;//p是工作指针，q记录p的前，第k个指针。
    	int count=0;
    	while(p){
    		p=p->next;
    		count++;
    		if(count>k){
    			q=q->next;
    		}
    	}
    	printf("%d",q->data);
    	return q;
    	 
    }