C语言链表的所有相关操作详解

梦里梦外; 2022-03-16 02:38 160阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    typedef struct list List;
    List *create(); 
    void insertNode(List *L,int n);
    void deleteNode(List *L,int n);
    List *Listreverse(List *L);
    void merge(List *L1,List *L2);
    int serach(List *L,int n);
    void Listsort(List *L);
    void show(List *L);
    struct list{
    	int data;
    	List *next;
    };
    int main(){
    	char c;
    	int n,i,l,L1,L2;
    	printf("请输入你想要创建链表的数目:\n");
    	scanf("%d",&n);
    	List *L[n];
    	for(int i=1;i<=n;i++){
    		L[i] = create();
    	}
    	for(int i=1;i<=n;i++){
    		if(i==1){
    			printf("链表%d:\n",i);	
    		}else{
    			printf("\n链表%d:\n",i);	
    		} 
    		show(L[i]);
    	}
    	while(true){
    	printf("\n请输入你想要执行的操作:\n1.插入节点\n2.删除节点\n3.链表逆序\n4.链表合并\n5.链表排序\n6.退出程序\n");
    	scanf(" %c",&c);
    	if(c == '1'){
    		printf("你想要在哪个链表插入数据:\n");
    		scanf("%d",&l);
    		if(l>n){
    			printf("所选链表不存在！\n");
    		}else{
    	 	printf("请输入你想要插入节点的位置:\n");
    		scanf("%d",&i);
    		insertNode(L[l],i);
    		for(int i=1;i<=n;i++){
    		if(i==1){
    			printf("链表%d:\n",i);	
    		}else{
    			printf("\n链表%d:\n",i);	
    		} 
    		show(L[i]);
    	}
    	    }
    	}else if(c == '2'){
    		printf("你想要给:\n");
    		scanf("%d",&l);
    		if(l>n){
    			printf("所选链表不存在！\n");
    		}else{
    	 	printf("请输入你想要删除节点的位置:\n");
    		scanf("%d",&i);
    		deleteNode(L[l],i);
    		for(int i=1;i<=n;i++){
    		if(i==1){
    			printf("链表%d:\n",i);	
    		}else{
    			printf("\n链表%d:\n",i);	
    		} 
    		show(L[i]);
    	}
    	    }
    	}else if(c == '3'){
    		printf("你想要将哪个链表逆序:\n");
    		scanf("%d",&l);
    		if(l>n){
    			printf("所选链表不存在！\n");
    		}else{
    			L[l] = Listreverse(L[l]);
    			for(int i=1;i<=n;i++){
    				if(i==1){
    					printf("链表%d:\n",i);	
    				}else{
    					printf("\n链表%d:\n",i);	
    				} 
    					show(L[i]);
    			}	
    		}
    	}else if(c == '4'){
    		if(n>=2){
    		printf("你想要把哪两个链表合并:\n");
    		scanf("%d %d",&L1,&L2);
    		merge(L[L1],L[L2]);
    		for(int i=1;i<=n;i++){
    				if(i==1){
    					printf("链表%d:\n",i);	
    				}else{
    					printf("\n链表%d:\n",i);	
    				} 
    					show(L[i]);
    			}
    		}else{
    			printf("只创建了一个链表!\n"); 
    		}
    	}else if(c == '5'){
    		printf("请选择你想要排序的链表:\n");
    		scanf("%d",&l);
    		Listsort(L[l]); 
    		for(int i=1;i<=n;i++){
    				if(i==1){
    					printf("链表%d:\n",i);	
    				}else{
    					printf("\n链表%d:\n",i);	
    				} 
    					show(L[i]);
    			}	
    	}else{
    		exit(0);
    	}
    }
    	
    	return 0;
    } 
    List *create(){
    	int n;
    	List *head,*node,*end;
    	printf("请输入你想要创建的节点个数:\n"); 
    	scanf("%d",&n);
    	head = (List *)malloc(sizeof(List)); //给头节点申请内存 
    	head->data = n;  //头节点数据域存储链表长度 
     	end = head;   //首尾一致，空链表 
    	printf("请输入数据:\n");
    	for(int i=1;i<=n;i++){
    		node = (List *)malloc(sizeof(List));
    		scanf("%d",&node->data);
    		end->next = node;
    		end = node;
    	}
    	end->next = NULL;
    	return head;
    }
    void insertNode(List *L,int n){
    	List *p = L,*pi;
    	if(n>p->data){
    		printf("所插入位置大于链表长度!\n");
    	}else{
    	p->data++; //链表长度+1 
    	p = p->next;	
    	pi = (List *)malloc(sizeof(List));   //为新建节点申请内存 
    	printf("请输入插入节点的数据:\n");
    	scanf("%d",&pi->data);
    	int i = 1;
    	while(i<n){   
    		p = p->next;
    		i++;
    	}
    	pi->next = p->next;
    	p->next = pi;
        }
    }
    void deleteNode(List *L,int n){
    	List *p = L;
    	if(n>p->data){
    		printf("所选节点不存在！\n");
    	}else{
    	p->data--; //链表长度-1
    	p = p->next; 
    	int i = 1;
    	while(i<n-1){  //使p指向删除节点的上一个节点 
    		p = p->next;
    		i++;
    	}
    	p->next = p->next->next; 
    }
    } 
    List *Listreverse(List *L){
    	List *head = L,*p = L->next,*pr,*temp;   //使head指向头节点，p指向首节点 
    	if(head == NULL){
    		printf("链表为空！\n");
    		return head;
    	}else if(p->next == NULL){
    		printf("链表中只有一个元素！\n");
    		return head;
    	}else{
    		pr = p->next;	//pr指向p的下一个节点 
    		p->next = NULL;	//使p的指针域为空，变为尾节点 
    		while(pr!= NULL){	//当pr不等于NULL时 
    			temp = pr;	 
    			pr = pr->next;	
    			temp->next = p;	// 使p的下一个节点指向p 	
    			p = temp;
    		}
    		head->next = p;  //因为最后pr为NULL,所以头节点应该指向p
    		return head;
    	}
    } 
    int serach(List *L,int n){
    	List *p = L->next;
    	while(p){
    		if(p->data == n){
    			return 0;
    		}
    		p = p->next;
    	}
    	return -1;
    }
    void merge(List *L1,List *L2){
    	int n = 0;
    	List *p1 = L1->next,*p2 = L2->next,*p3 = L1,*p;
    	while(p3->next!=NULL){ //使p3指向L1的尾节点 
    		p3 = p3->next;
    	}
    	while(p2){
    		if(serach(L1,p2->data)!=0){
    			p = (List *)malloc(sizeof(List));
    			p->data = p2->data;
    			p3->next = p;
    			p3 = p;
    			p->next = NULL;	
    			n++;	
    		} 
    		p2 = p2->next; 
    	}
    	L1->data+=n;
    }
    void Listsort(List *L){	//冒泡排序 
    	List *head = L,*end = NULL,*p1,*p2,*p3,*temp;  //定义head指针指向L，end为空 
    	if(head->next==NULL){  
    		printf("链表为空!\n");
    		return ;
    	}else if(head->next->next == NULL){
    		printf("链表中只有一个元素!\n");
    		return;
    	}else{
    	while(head->next!= end){   //当head指针所指向节点的指针域不等于end 
    		for(p1 = head,p2 =	p1->next,p3 = p2->next;p3!=end;p1 = p1->next,p2 = p2->next,p3 = p3->next){
    			if(p2->data>p3->data){  //当p2的值比p3的值大，值大的往下沉 
    				p2->next = p3->next;  //地址互换 
    				p1->next = p3;
    				p3->next = p2;
    				temp = p3;		//将p2，p3的指向互换 
    				p3 = p2;
    				p2 = temp;
    			}
    		}
    		end = p2;  //当第一次for循环结束时，p3位于尾节点，p2位于尾节点的上一个节点，此时尾节点存放的数据是链表中最大的数 
    	}
    }
    }
    void show(List *L){
    	List *p = L->next;
    	while(p){
    		printf("%d\t",p->data);
    		p = p->next;
    	}
    }