线性表应用（非递减合并、分解链表、删除线性表）

         将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。

#include
using namespace std;
typedef struct list
{
	int data;
    list* next;
}list,*linklist;
void Createlist(linklist& l)
{
	l = new list;
	l->next = NULL;
	linklist p,r;
	r = l;
	for (int i = 0; i < 5; i++)
	{
		p = new list;
		cin >> p->data;
		r->next = p;
		r = p;
	}
	p->next = NULL;
}
void Addlist(linklist& L1, linklist& L2)
{
	linklist L3, pa, pb,p;
	pa = L1->next;
	pb = L2->next;
	L3 = L1, L3->next = NULL;
	while (pa || pb)
	{
		if (pa==NULL)
		{
			p = pb;
			pb = pb->next;
		}
		else if (pb==NULL)
		{
			p = pa;
			pa = pa->next;
		}
		else if (pa->data <= pb->data)
		{
			p = pa;
			pa = pa->next;
		}
		else
		{
			p = pb;
			pb = pb->next;
		}
		p->next = L3->next;
		L3->next = p;
	}
	delete L2;
}
void Printlist(linklist& l)
{
	linklist p;
	p = l->next;
	while (p)
	{
		cout << p->data<<" ";
		p = p->next;
	}
}
int main()
{
	linklist L1, L2;
	cout << "输入第一个链表：" << endl;
	Createlist(L1);
	cout << "输入第二个链表：" << endl;
	Createlist(L2);
	Addlist(L1, L2);
	cout << "合并链表：" << endl;
	Printlist(L1);
}

       设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

#include
using namespace std;
typedef struct list
{
	int data;
    list* next;
}list,*linklist;
void Createlist(linklist& l)
{
	l = new list;
	l->next = NULL;
	linklist p,r;
	r = l;
	for (int i = 0; i <10; i++)
	{
		p = new list;
		cin >> p->data;
		r->next = p;
		r = p;
	}
	p->next = NULL;
}
void Separatelist(linklist& L1, linklist& L2, linklist& L3)
{
	L3 = new list;
	L3->next = NULL;
	linklist p,r;
	p = L1->next;
	L2 = L1;
	L2->next = NULL;
	while (p)
	{
		r = p->next;
		if (p->data < 0)
		{
			p->next = L2->next;
			L2->next = p;
		}
		else
		{
			p->next = L3->next;
			L3->next = p;
		}
		p = r;
	}
}
void Printlist(linklist& l)
{
	linklist p;
	p = l->next;
	while (p)
	{
		cout << p->data<<" ";
		p = p->next;
	}
	cout << endl;
}
int main()
{
	linklist L1, L2,L3;
	cout << "输入第一个链表：" << endl;
	Createlist(L1);
	Separatelist(L1, L2, L3);
	cout << "拆分链表：" << endl;
	Printlist(L2);
	Printlist(L3);
}

 

       已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O (1）的算法，该算法删除线性表中所有值为ite m的数据元素。

#include
#define maxsize 100
using namespace std;
typedef struct node
{
	int data;
}Node;
typedef struct
{
	Node* elem;
	int length;
}Sqlist;
void Initlist(Sqlist& L)
{
	L.elem = new Node[maxsize];
	L.length = 0;
}
int Createlist(Sqlist& L)
{
	if (L.length == maxsize) return 0;
	for (int i = 0; i < 10; i++)
	{
		cin >> L.elem[i].data;
		L.length++;
	}
	return 1;
}
void Deletelist(Sqlist& L, Node e)
{
	int k = 0;
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i].data != e.data)
		{
			L.elem[k].data = L.elem[i].data;
			k++;
		}
	}
	L.length = k;
}
void Printlist(Sqlist L)
{
	for (int i=0;i
	{
		cout << L.elem[i].data << " " ;
	}
	cout << endl;
}
int main()
{
	Sqlist A;
	Initlist(A);
	Createlist(A);
	cout << "原线性表：" << endl;
	Printlist(A);
	cout << "输入要删除的一个数：" << endl;
	Node n;
	cin >> n.data;
	Deletelist(A,n);
	Printlist(A);
}