【数据结构】链表相关例题（C/C++含注释）

一、链表合并

【问题描述】 两个非降序链表的并集，例如将链表1->2->3 和 2->3->5 并为 1->2->3->5，只能输出结果，不能修改两个链表的数据。

【输入形式】 第一行首先是数据的个数，然后是第一个链表的各结点值，以空格分隔。 第二行首先也是数据的个数，然后是第二个链表的各结点值，以空格分隔。

【输出形式】 合并好的链表，以非降序排列，值与值之间以空格分隔。

【样例输入】 4 4 7 10 34 7 1 4 6 29 34 34 52

【样例输出】 1 4 6 7 10 29 34 52

【完整代码】

#include
#include
#include
using namespace std;
//链表结构体
typedef struct Node
{
    int data;              //数据域
    struct Node *next;     //指针域
}Node,*LinkList;

LinkList LinkedListInit()  //初始化链表
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));
    L->next = NULL;
    return L;
}

LinkList CreateList() //尾插法建立单链表
{

    Node *L;
    L = (Node *)malloc(sizeof(Node));
    L->next = NULL;
    Node *r;
    r = L;
    int x,y;
    cin>>x;
    for(int i=0;i>y;
        Node *p;
        p = (Node *)malloc(sizeof(Node));
        p->data = y;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return L;
}

 void DeleteLink(LinkList L) //删除相同的元素
{
    Node *p,*q,*s;
    for(p=L->next;p!=NULL;)
   {
       q=p->next;
       if(q!=NULL)
       {
           //如果找到相同元素
           if(q->data==p->data)
          {
              s=q->next;
              p->next=s;
              free(q);    //释放节点
              q=s;
          }
          else p=p->next;
       }
       else break;
   }

}

LinkList CoalitionLinkList(LinkList l1,LinkList l2) //合并单链表
{
    Node *p1,*p2,*r;
    LinkList l3;
    p1 = l1->next;
    p2 = l2->next;
    l3 = l1;
    l3->next = NULL;
    r = l3;
    while(p1!=NULL&&p2!=NULL)
    {
        if(p1->datadata)
        {
            r->next = p1;
            r = p1;
            p1 = p1->next;
        }
        else
        {
            r->next = p2;
            r = p2;
            p2 = p2->next;
        }
    }
    if(p1) r->next = p1;
    else r->next = p2;
    free(l2);
    return l3;
}

int main()
{
    LinkList l1,l2,l3,p3;
    l1 = CreateList();
    l2 = CreateList();
    l3 = LinkedListInit();
    l3 = CoalitionLinkList(l1,l2);
    DeleteLink(l3);
    for(p3 = l3->next;p3!=NULL;p3 = p3->next) //遍历整个链表
        coutnext=l;
        l->pre=q;
        p=q;
    }
    return l;
}//创建初始化一个循环链表的操作
LinkList merge(LinkList l)
{
    LinkList p=l->next;
    int m=p->data;
    p->pre->next=p->next;
    p->next->pre=p->pre;
    free(p);//删除第一个元素
    LinkList r=l->next;
    while(r->datanext!=l){
        r=r->next;
    }//通过比较遍历找到插入点 但要注意可能到最后都没找到比删除的元素还要大的结点 所以要再讨论是否到了尾结点
    if(r->next!=l){
    LinkList q;
    q=(LinkList)malloc(sizeof(struct node));新建待插入的结点
    q->data=m;//1
    q->pre=r->pre;//2
    q->next=r;//3
    r->pre->next=q//;4
    r->pre=q;//5重要的五步
    }//在尾结点之前找到了比大的故插入进去
    else{
        LinkList q;
        q=(LinkList)malloc(sizeof(struct node));
        q->data=m;
        r->next=q;
        q->pre=r;
        q->next=l;
        l->pre=q;
    }//遍历到了尾还没有找到大的元素
    return l;
}
void show(LinkList l)//这就是简单的输出函数了
{
    LinkList p=l->next;
    while(p!=l)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}
int main()//主函数
{
    int n;
    LinkList L,K;
    scanf("%d",&n);
    L=CreateLink(n);
    K=merge(L);
    show(K);
    return 0;
}

三、多项式相加

【问题描述】编写一个程序用单链表存储多项式，并实现两个一元多项式A与B相加的函数。A，B刚开始是无序的，A与B之和按降序排列。例如： 多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5 多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10 多项式A与B之和：5.4X^10 6.4X^3 5X^1

【输入形式】任意两个多项式A和B的项数及对应的系数和指数，要查询的第几项 【输出形式】多项式中某一项的系数与指数，系数保留一位小数

【输入样例】 4 1.2 0 2.5 1 3.2 3 -2.5 5 5 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 10 2

【输出样例】

6.4 3

【样例说明】 第一个多项式的系数与指数对，以空格隔开 第二个多项式的系数与指数对，以空格隔开 输出第２项的系数与指数，系数与指数间用空格隔开，系数保留一位小数

【完整代码】

#include
#include
//#include

struct polynomial
{
	int    index;		//指数
	double coefficient;	//系数
	struct polynomial * next;
};

struct polynomial * input()
{
	int i, num, j;
	double c;
	struct polynomial *p, *q, *head;
	scanf("%d", &num);
	q = NULL;
	head = NULL;
	for (j = 0; j coefficient = c;
		p->index = i;
		p->next = NULL;
		if (head == NULL)
			head = p;
		if (q == NULL)
			q = p;
		else
		{
			p->next = q;	//链接到头部。
			q = p;
			head = p;
		}
	}
	for (p = head; p != NULL; p = p->next)
		for (q = p->next; q != NULL; q = q->next)
			if (q->index > p->index)
			{
				double temp;
				q->index ^= p->index;
				p->index ^= q->index;
				q->index ^= p->index;
				temp = q->coefficient;
				q->coefficient = p->coefficient;
				p->coefficient = temp;
			}
	return head;
}

struct polynomial * add(struct polynomial *h1, struct polynomial *h2)
{
	///变量声明与初始化///
	struct polynomial *ans_head, *ans_p, *ans_q, *p1, *p2;
	double a1 = 0, a2 = 0;
	int index = 0;
	ans_q = NULL; ans_head = NULL;
	p1 = h1; p2 = h2;

	while (p1 != NULL || p2 != NULL)
	{
		ans_p = (struct polynomial *)malloc(sizeof(struct polynomial));
		if (p1 == NULL || p2 == NULL || p1->index == p2->index)		//情况1
		{

			a1 = (p1 == NULL) ? 0 : p1->coefficient;
			a2 = (p2 == NULL) ? 0 : p2->coefficient;
			index = (p1 == NULL) ? p2->index : p1->index;
			if (a1 + a2 == 0)
			{
				free(ans_p);
				if (p1 != NULL) p1 = p1->next;
				if (p2 != NULL) p2 = p2->next;
				continue;
			}
			ans_p->coefficient = a1 + a2;
			ans_p->index = index;
			ans_p->next = NULL;

			if (p1 != NULL) p1 = p1->next;
			if (p2 != NULL) p2 = p2->next;
		}
		else if (p1->index > p2->index)		//情况2
		{
			ans_p->coefficient = p1->coefficient;
			ans_p->index = p1->index;
			ans_p->next = NULL;

			p1 = p1->next;
		}
		else //p2->index > p1->index	//情况3
		{
			ans_p->coefficient = p2->coefficient;
			ans_p->index = p2->index;
			ans_p->next = NULL;

			p2 = p2->next;
		}
	//
		if (ans_head == NULL)	//链接到尾部。
			ans_head = ans_p;
		if (ans_q == NULL)
			ans_q = ans_p;
		else
		{
			ans_q->next = ans_p;
			ans_q = ans_p;
		}
	}
	return ans_head;
}

void show(struct polynomial *h, int index)
{
	struct polynomial *p;
	int i;
	for (i = 0, p = h; i next;
	printf("%.1lf %d\n", p->coefficient, p->index);
}

int main()
{
	int i;
	struct polynomial *h1;
	struct polynomial *h2;
	struct polynomial *ans;

	h1 = input();
	h2 = input();
	scanf("%d", &i);
	ans = add(h1, h2);
	show(ans, i);

//	system("pause");
	return 0;
}