线性表——链表

q1

数据文件data.txt里存储了若干个整型数，完成如下任务

1. 读取文件里的数值用数组存储。

2. 顺序和逆序遍历数组输出元素

3. 用链表存储数据，顺序遍历链表输出元素，将链表逆置（倒转）并输出元素。

   例如 2->3->10->6 逆置结果为 6->10->3->2

4. 删除重复的元素，创建并存储没有重复元素的数组（针对数组和链表分别实现）

#include<iostream>
using namespace std;
typedef struct Lnode
{
	int data;
	Lnode* next;
};

void delete1(int arr[],int len)
{
	//数组实现
	int arr2[100];
	int len2 = 0, i, j;
	for (i = 0; i < len; i++)
	{
		for (j = 0; j < len2; j++)
		{
			if (arr2[j] == arr[i])
				break;
		}
		if (j == len2)
		{
			arr2[j] = arr[i];
			len2++;
		}
	}
	cout << "数组实现，删除后:";
	for (i = 0; i < len2; i++)
	{
		cout << arr2[i] << " ";
	}
	cout << endl;

}
void delete2(int arr[], Lnode* head, int len)
{
	//链表实现
	Lnode* newhead = NULL;
	Lnode* newend = NULL;
	Lnode* tmp = head;
	while (tmp != NULL)
	{
		Lnode* ptr = newhead;
		while (ptr != NULL)
		{
			if (ptr->data == tmp->data)
				break;
			ptr = ptr->next;
		}
		if (ptr == NULL)
		{
			ptr = (Lnode*)malloc(sizeof(Lnode));
			ptr->data = tmp->data;
			ptr->next = NULL;
			if (newhead == NULL)
			{
				newhead = ptr;
				newend = newhead;
			}
			else
			{
				newend->next = ptr;
				newend = newend->next;
			}
		}
		tmp = tmp->next;
	}
	Lnode* tmp2 = newhead;
	cout << "链表实现，删除后:";
	while (tmp2 != NULL)
	{
		cout << tmp2->data << " ";
		tmp2 = tmp2->next;
	}
	cout << endl;

}
int main()
{
	
	int i = 0;
	int arr[100];
	cout << "输入:";
	while (1)
	{
		cin >> arr[i];
		i++;
		if (getchar() == '\n')
			break;
	}
	const int len = i;
	cout << "顺序:";
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	cout << "逆序:" ;
	for (int i = len - 1; i >= 0; i--)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	//建立链表
	Lnode* head = NULL;
	for (int i = len - 1; i >= 0; i--)
	{
		Lnode* ptr;
		ptr = (Lnode*)malloc(sizeof(Lnode));
		ptr->data = arr[i];
		ptr->next = NULL;
		if (head == NULL)
			head = ptr;
		else
		{
			ptr->next = head;
			head = ptr;
		}
	}
	Lnode* ptr = head;
	cout << "链表正序:" ;
	while (ptr != NULL)
	{
		cout << ptr->data << " ";
		ptr = ptr->next;
	}
	cout << endl;
	Lnode* end = NULL;
	cout << "链表逆序:" ;
	while (end != head)
	{
		ptr = head;
		while (ptr->next != end)
		{
			ptr = ptr->next;
		}
		cout << ptr->data << " ";
		end = ptr;
	}
	cout << endl;
	delete1(arr, len);
	delete2(arr, head, len);
}

q2

输入一个整数n，再输入n个整数，按照输入的顺序建立单链表，并遍历所建立的单链表，输出这些数据。

输入格式:

假定输入的测试数据有两组，每组测试输入一个整数n，再输入n个整数。

输出格式:

（1） 对于每组测试，按照输入次序输出链表中各结点数据域的值（数据之间留一个空格）。

（2） 对任意一个链表，删除数据值相同的结点。（时间复杂度O(n)）

（3） 检查两个链表是否为有序链表，若无序，则按递增顺序排序。

（4） 将两个递增链表合并为一个递减链表，合并过程中删除值相同的结点。

输入样例:

5 1 2 3 4 5

7 9 3 2 4 7 8 6

（1）输出样例:

5 4 3 2 1

6 8 7 4 2 3 9

（2）输出样例：

5 4 3 2 1

6 8 7 4 2 3 9

（3）输出样例：

1 2 3 4 5

2 3 4 6 7 8 9

（4）输出样例：

9 8 7 6 5 4 3 2 1

链表结点的定义struct Lnode；创建空链表

#include<iostream>
using namespace std;
#include<map>
#define SHOW 1
#define NOTSHOW 0
typedef struct Lnode
{
	int data;
	Lnode* next;
};
void add(Lnode* &head1)
{
	int n;
	cin >> n;
	while (n--)
	{
		int m;
		Lnode* ptr = NULL;
		cin >> m;
		ptr = (Lnode*)malloc(sizeof(Lnode));
		ptr->data = m;
		ptr->next = NULL;
		if (head1 == NULL)
			head1 = ptr;
		else
		{
			ptr->next=head1;
			head1=ptr;
		}

	}

}
void show(Lnode* head1)
{
	Lnode* ptr = head1;
	while (ptr != NULL)
	{
		cout << ptr->data << " ";
		ptr = ptr->next;
	}
	cout << endl;
}
void del(Lnode* &head,int a)
{
	map<int,int>m;
	Lnode* ptr = head;
	Lnode* pre = head;
	m[ptr->data] = 1;
	ptr = ptr->next;
	while (ptr != NULL)
	{

		if (m[ptr->data] == 1)
		{
			pre->next = ptr->next;
			free(ptr);
			ptr = pre;
		}
		else
			m[ptr->data] = 1;
		pre = ptr;
		ptr = ptr->next;
	}
	if (a)
		show(head);
}
void sort(Lnode* &head,int a)
{
	Lnode* ptr = head;
	Lnode* pre = head;
	while (ptr != NULL)
	{
		Lnode* tmp = ptr;
		while (tmp != NULL && tmp->data >= ptr->data)
			tmp = tmp->next;
		if (tmp == NULL)
		{
			pre = ptr;
			ptr = ptr->next;
		}
		else
		{
			if (ptr == head)//ptr换到tmp右边
			{
				head = head->next;
				ptr = head;
				pre->next = tmp->next;
				tmp->next = pre;

				ptr = head;
				pre = head;
			}
			else
			{
				pre->next = ptr->next;
				ptr->next = tmp->next;
				tmp->next = ptr;
				ptr = pre->next;
				
			}
		}
	}
	if (a)
		show(head);
}
void sort2(Lnode* &head, int a)//逆序
{
	Lnode* ptr = head;
	Lnode* pre = head;
	while (ptr != NULL)
	{
		Lnode* tmp = ptr;
		while (tmp != NULL && tmp->data <= ptr->data)
			tmp = tmp->next;
		if (tmp == NULL)
		{
			pre = ptr;
			ptr = ptr->next;
		}
		else
		{
			if (ptr == head)//ptr换到tmp右边
			{
				head = head->next;
				ptr = head;
				pre->next = tmp->next;
				tmp->next = pre;

				ptr = head;
				pre = head;
			}
			else
			{
				pre->next = ptr->next;
				ptr->next = tmp->next;
				tmp->next = ptr;
				ptr = pre->next;

			}
		}
	}
	if (a)
		show(head);
}

void com(Lnode* head1, Lnode* head2)
{
	Lnode* ptr1 = head1;
	while (ptr1->next != NULL)
	{
		ptr1 = ptr1->next;
	}
	ptr1->next = head2;
	Lnode* ptr2 = head1;
	del(head1,NOTSHOW);
	sort2(head1, SHOW);


}
int main()
{
	Lnode* head1 = NULL;
	Lnode* head2 = NULL;
	add(head1);
	add(head2);
	show(head1);
	show(head2);
	del(head1,SHOW);
	del(head2,SHOW);
	sort(head1,SHOW);
	sort(head2, SHOW);
	com(head1, head2);
}