数据结构实训一：单链表的基本运算

（1）设计一个CreatList函数，实现通过前插法创建一个有n个结点的单链表（带头结点）；设计一个 PrintList函数，实现输出单链表的各个元素的值。要求：用main函数控制调用实现相关功能。
（2）修改（1）中的CreatList函数，实现通过后插法创建一个有n个结点的单链表。
（3）设计一个ListDelete函数，在前面所创建的单链表中删除第i个元素。
（4）设计一个inverse函数，将不带头结点的单链表“原地”逆转，即要求仅利用原表的存储空间。
（5）利用CreatList函数创建两个递增的用序单链表，再设计一个MergeList函数，将这两个递增的有序链表合并为一个递增的有序链表。
要求①结果链表仍使用原来两个链表的存储空间；②表中不允许有重复的数据。

实现效果:

不多bb,直接上代码:

#include<iostream>

using namespace std;

typedef struct LNode{
	int data;
	struct LNode* next;
}LNode,*LinkList;

void CreatrList_H(LinkList &L, int n);//(1)前插法创建单链表
void CreateList_R(LinkList &L, int n);//(2)后插法创建单链表
bool ListDelete(LinkList &L, int i);//(3)链表删除
int InverseList(LinkList &L);//(4)逆转单链表 
void MergeList(LinkList &La,LinkList &Lb, LinkList &Lc);//(5)有序表的合并 

bool GetElem(LinkList L, int i,int &e);//取值 
int LengthList(LinkList &L);//求单链表的长度 
void PrintList(LinkList &L);//打印单链表 

int main()
{
	LinkList L;
	int n;
	cout << "====================" << endl << "(1).前插法创建单链表(在空链表上操作):" << endl << endl;
	cout << "请输入要插入的个数:";
	cin >> n;
	cout << "请输入要插入的元素(以空格分隔):";
	CreatrList_H(L, n);
	cout << "当前链表长度为:" << L->data << endl;
	cout << "当前链表元素为:";
	PrintList(L); 


	cout << endl<<"====================" << endl << "(2).后插法创建单链表(在空链表上操作):" << endl << endl;
	cout << "请输入要插入的个数:";
	cin >> n;
	cout << "请输入要插入的元素(以空格分隔):";;
	CreateList_R(L, n);
	cout << "当前链表长度为:" << L->data << endl;
	cout << "当前链表元素为:";
	PrintList(L); 
	cout << endl;

		cout << endl<<"===================="<< endl<<"(3):请输入要删除的位置(在(2)中的链表上操作):" << endl;
	int j2;
	cin >> j2;
	if (ListDelete(L, j2))
	{
		cout << "删除成功!" << endl;
	}
	else
	{
		cout << "删除位置不合法!" << endl;
	}
	cout << "当前链表元素为:";
	for (int i = 1;i <= L->data;i++)
	{
		int e;
		GetElem(L, i, e);
		cout << e << " ";
	}
	cout << endl;
	
	cout << endl<<"====================" << endl << "(4).逆转链表:" << endl << endl;
	cout<<"请输入新的单链表的元素个数:"<<endl; 
	cin>>n;
	cout<<"请输入新的单链表的元素(后插法):";
	CreateList_R(L, n); 
	InverseList(L);//逆转 
	cout<<"逆转后的链表为:";
	PrintList(L);
	cout<<endl<<endl;
	
	
	cout << endl<<"====================" << endl <<"(5)有序表的合并"<<endl<<endl;
	cout<<"请用后插法依次输入两个递增的单链表La和Lb:"<<endl;
	int n1,n2;
	LinkList La,Lb,Lc; 

	cout<<"请输入第一个链表La的长度n1:";
	cin>>n1;	
	cout<<"请输入第二个链表Lb的长度n2:";
	cin>>n2;
	cout<<"请依次输入链表La的元素(元素之间用空格分隔):";
	CreateList_R(La, n1);

	cout<<"请依次输入链表Lb的元素(元素之间用空格分隔):";	
	CreateList_R(Lb, n2);
	
	int l=(LengthList(La)+LengthList(Lb));
	cout<<"La与Lb合并后的链表为:" ; 	
	MergeList(La,Lb,Lc);
	for (int i = 1;i <=l;i++)
	{
		int e;
		GetElem(Lc, i, e);
		cout << e << " ";
	}	
	cout<<endl;

	system("pause");
	return 0;
}

void CreatrList_H(LinkList &L, int n)
{//(1)头插法创建单链表
	L = new LNode;
	L->next = NULL;
	L->data = 0;
	for (int i = 0;i < n;i++)
	{
		int m;
		LNode* p = new LNode;
		cin >> m;
		p->data= m;
		p->next = L->next;
		L->next = p;
		L->data++;
	}
}

void CreateList_R(LinkList &L, int n)
{//(2)尾插法创建单链表
	L = new LNode;
	L->data = 0;
	L->next = NULL;
	LNode* r = L;
	for (int i = 0;i < n;i++)
	{
		int m;
		LNode* p = new LNode;
		cin >> m;
		p->data=m;
		p->next = NULL;
		r->next = p;
		r = p;

		L->data++;
	}
}

bool ListDelete(LinkList &L, int i)
{//(3)链表删除
	LNode* p = L;
	int j = 0;
	while (p->next && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || (j > i - 1))
	{
		return false;
	}
	LNode* q=p->next;
	p->next = q->next;
	L->data--;
	delete q;
	return true;
}

int InverseList(LinkList &L)
{//(4)链表逆转 
	LinkList p = L->next;
	L->next = NULL;
	while(p)
	{
		LNode*q = p->next;//q指向*p的后继 
		p->next = L->next;
		L->next = p;
		p = q;
	}
}

void MergeList(LinkList &La,LinkList &Lb, LinkList &Lc)
{//(5)有序链表的合并
	LinkList pa = La->next;	//pa和pb分别是链表La和Lb的工作指针,
	LinkList pb = Lb->next;	//分别初始化为相应链表的第一个结点
	LinkList pc = La;  //用La的头结点作为Lc的头结点
	Lc = pc;
	while (pa && pb)
	{
		if (pa->data < pb->data)
		{
			pc->next = pa;//将pa链接在pc后
			pc = pa;
			pa = pa->next;//pa指针后移
		}
		else if (pa->data > pb->data)
		{//若Lb较小
			pc->next = pb;//将pb链接在pc后
			pc = pb;
			pb = pb->next;//pb指针后移
		}
		else 
		{//若La==Lb
			pc->next = pa;
			pc = pa;
			pa = pa->next;

			LNode*q = pb->next;//接下来三行为删除Lb
			delete pb;
			pb = q;
		}
	}
	pc->next = pa ? pa : pb;    //插入剩余段
	delete Lb;            //释放Lb的头结点

}

int LengthList(LinkList &L)
{//求长度 
	int count = 0;
	LinkList p;
	p =L->next;
	while(p)
	{
		count++;
		p=p->next;
	}
	return count;
} 

bool GetElem(LinkList L, int i,int &e)
{//取值(根据下标得到元素)
	LNode*p = L->next;
	int j = 1;
	while (p&&j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return false;
	}
	e = p->data;
	return true;
}

void PrintList(LinkList &L)
{//打印单链表 
	for (int i = 1;i <=L->data;i++)
	{
		int e;
		GetElem(L, i, e);
		cout << e << " ";
	}
}