[数据结构与算法]链表的排序、插入和删除

链表的建立、排序、插入和删除操作

1、要求：
设有两个无头结点的单链表，分别为ha，hb，其链中有数据域data，链域next，两链表的数据都按递增序存放。
现要求将hb表归到ha表中，且归并后ha仍按递增排序，归并中ha表中已有的数据若与hb相同，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
头文件：

#include <cstdlib>
#include<cstdio>
#include <iostream>
using namespace std;

2，无头结点链表的建立

typedef struct LNode {
	int data;
	struct LNode* next;

}LNode, * LinkList;


void Create_List(LinkList& L,int n) {
	LinkList p,q;
	int a;
	L = (LinkList)malloc(sizeof(LNode));
	//L为指向第一个结点的指针
	cin >> a;
	L->data = a;
	L->next = NULL;
	q = L;
	for (int i=0;i<n-1;i++)		//顺序建表
	{	
		cin >> a;
		p = (LinkList)malloc(sizeof(LNode));
		p->data = a;
		p->next = NULL;
		q->next = p;
		q = p;	
	}
}

其升序排序为：

void SortUp_List(LinkList& L,int n) {	//升序
	LinkList p,p1,q;		//q等于L，p,p1比较
	
	if (L == NULL) return;

	for (int i=0;i<n-1;i++) {
		q = L;
		for (int j=0;j<n-i-1;j++) {
			p = q;
			p1 = p->next;
			if ((p->data) > (p1->data)) {
				//交换数据域
				int tem = p->data;
				p->data = p1->data;
				p1->data = tem;
			}
			q = q->next;
		}
		
	}
}

删除操作：

void ListDelete(LinkList& L, int delElem) {
	LinkList p;
	p = L;
	while (p->next != NULL) {
		if (p->next->data == delElem) {
			p->next->next = p->next;
		}	
	}
}

插入操作：

void Insert(LinkList& L, int elem) {  //插入一个元素
	LinkList p;
	LinkList s;
	p = L;
	s = (LinkList)malloc(sizeof(LNode));
	s->data = elem;
	s->next = NULL;
	while (p->next != NULL) {
		if (p->data == elem) break;
		if (p->next->data > elem && L->data < elem) {
			s->next = p->next;
			p->next = s;
			break;
		}
		if (L->data > elem) {
			s->next = L;
			L = s;
		}
		p = p->next;
	}
	if (p->next == NULL && p->data < elem) {
		p->next = s;
	}
}

void Insert_Link(LinkList& LA, LinkList& LB) {//插入一个链表
	LinkList p;
	p = LB;
	
	//LB链表长度
	int n = 0;
	LinkList q;
	q = LB;
	while (q != NULL) {
		n++;
		q = q->next;
	}

	for (int i = 0;i < n;i++) { //遍历LB
		Insert(LA, p->data);
		p = p->next;
	}
}

其他函数：

void Print(LinkList& L) { //输出
	LinkList p;
	p = L;
	if (p == NULL) {
		cout << "null" << endl;
		return;
	}
	while(p!=NULL){
		cout << (p->data)<<" ";
		p = p->next;
	}
	cout << endl;
}
int main() {
	LinkList LA,LB;
	int n,m;
	
	cin >> n;
	cout << "输入链表LA的" << n << "个元素：";
	Create_List(LA,n);

	cin >> m;
	cout << "输入链表LB的" << m << "个元素：";
	Create_List(LB, m);
	cout << endl;

	SortUp_List(LA,n);
	SortUp_List(LB, m);
	cout << "链表LA：";
	Print(LA);
	cout << "链表LB：";
	Print(LB);
	cout << endl;

	Insert_Link(LA, LB);
	cout << "----------LB插入后LA---------------" << endl;
	cout << endl;
	cout << "链表LA：";
	Print(LA);
	cout << "链表LB：";
	Print(LB);
	return 0;
}

其输出结果示例如下：

4
输入链表LA的4个元素：5 7 3 4
5
输入链表LB的5个元素：7 8 4 3 6

链表LA：3 4 5 7
链表LB：3 4 6 7 8

----------LB插入后LA---------------

链表LA：3 4 5 6 7 8
链表LB：3 4 6 7 8

好了，今天的实验作业完成啦，嘿嘿嘿，开心