单链表的应用——单链表的连接、合并及逆序

我就是我 2023-07-14 03:20 53阅读 0赞

#include<iostream>
    #include<stdio.h>
    #include<windows.h>
    #define N 5
    using namespace std;
    typedef struct Lnode
    {
        
    	int data;
    	Lnode *next;
    }Lnode, *Linklist;
    
    Linklist Greatendlist(int a[N])//创建一个单链表
    {
        
    	int i;
    	Linklist L, tail;
    	L = (Lnode*)malloc(sizeof(Lnode));
    	if (L == NULL)
    	{
        
    		cout << "申请空间失败";
    		exit(0);
    	}
    	else L->next = NULL;
    	tail = L;
    	for (i = 0; i < N; i++)
    	{
        
    		Linklist p;
    		p = (Lnode*)malloc(sizeof(Lnode));
    		if (p == NULL)
    		{
        
    			cout << "申请空间失败";
    			exit(0);
    		}
    		else p->next = NULL;
    		p->data = a[i];
    		tail->next = p;
    		tail = tail->next;
    	}
    	return L;
    }
    
    Linklist Connectlist(Linklist LA, Linklist LB)//连接两个单链表
    {
        
    	Linklist p;
    	p = LA->next;
    	while (p&&p->next != NULL)
    	{
        
    		p = p->next;
    	}
    	p->next = LB->next;
    	return LA;
    }
    
    Linklist Mergelist(Linklist LA, Linklist LB)//合并两个单链表
    {
        
    	int m;
    	Linklist p, p1, q, q1;
    	p = LA->next; p1 = LA;
    	q = LB->next; q1 = LB;
    	while (p&&q)
    	{
        
    		if (p->data < q->data)m = -1;
    		else if (p->data == q->data)m = 0;
    		else m = 1;
    		switch (m)
    		{
        
    		case -1:
    			p1 = p;
    			p = p->next;
    			break;
    		case 0:
    			int w;
    			w = p->data + q->data;
    			if (w == 0)
    			{
        
    				p1 = p->next;
    				free(p);
    				p = p1->next;
    				q1 = q->next;
    				free(q);
    				q = q1->next;
    			}
    			break;
    		case 1:
    			q1->next = q->next;
    			q->next = p;
    			p1->next = q;
    			p1 = p1->next;
    			q = q1->next;
    			break;
    		}
    	}
    	if (p == NULL)  //处理尾巴
    	{
        
    		p1->next = q;
    		free(q1);
    	}
    	return LA;
    }
    
    Linklist Inverselist(Linklist L)//将一个单链表逆序(头插法)
    {
        
    	Linklist p, q;
    	p = L->next;
    	L->next = NULL;
    	while (p != NULL)
    	{
        
    		q = p->next;
    		p->next = L->next;
    		L->next = p;
    		p = q;
    
    	}
    	cout << "逆序后";
    	return L;
    }
    
    void putlist(Linklist L)//输出单链表
    {
        
    	int i;
    	Linklist p;
    	p = L->next;
    	cout << "当前链表为：";
    	while (p != NULL)
    	{
        
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }
    
    int main()
    {
        
    	int G;
    	Linklist LA, LB, U;
    	int i, a[N], b[N];
    	printf("正在创建第一个链表，请输入%d个元素值:", N);
    	for (i = 0; i < N; i++)
    	{
        
    		cin >> a[i];
    	}
    	LA = Greatendlist(a);
    	printf("正在创建第二个链表，请输入%d个元素值:", N);
    	for (i = 0; i < N; i++)
    	{
        
    		cin >> b[i];
    	}
    	LB = Greatendlist(b);
    	while (1)
    	{
        
    		cout << "******操作选择******" << endl;
    		cout << "1:连接两个单链表" << endl;
    		cout << "2:合并连个单链表" << endl;
    		cout << "3:逆序一个单链表" << endl;
    		cout << "4:退出程序" << endl;
    		cout << "*******************" << endl;
    		cout << "请输入你的操作代号：";
    		cin >> G;
    		switch (G)
    		{
        
    		case 1:
    			Connectlist(LA, LB);
    			cout << "首尾连接后";
    			putlist(LA);
    			LA = Greatendlist(a);
    			LB = Greatendlist(b);
    			break;
    		case 2:
    			Mergelist(LA, LB);
    			cout << "两链表合并后";
    			putlist(LA);
    			LA = Greatendlist(a);
    			LB = Greatendlist(b);
    			break;
    		case 3:
    			int Q;
    			cout << "你要逆序哪一个单链表(LA:1或LB:2)请输入：";
    			cin >> Q;
    			switch (Q)
    			{
        
    			case 1:
    				Inverselist(LA);
    				putlist(LA);
    				LA = Greatendlist(a);
    				break;
    			case 2:
    				Inverselist(LB);
    				putlist(LB);
    				LB = Greatendlist(b);
    				break;
    			}
    			break;
    		}
    		if (G == 4)break;
    	}
    	return 0;
    }