[数据结构与算法]2021-11-13

设有一个正整数序列组成的有序单链表（按递增有序，且允许
有相等的整数存在），请设计一个用最小的时间和最小空间的算
法实现下列功能：(a) 确定在序列中比正整数 x 大的数有几个（相
同的数只计算一次，如序列{3、5、6、6、8、10、11、13、13、
16、17、20、20}中比 10 大的数有 5 个）；(b) 将单链表中比正整
数 x 小的数按递减次序排列；? 将正整数比 x 大的偶数从单链
表中删除。要求：
（1）描述算法的基本设计思想；
（2）根据设计思想，采用 C 或 C++语言描述算法，给出注释; （3）说明你所设计的算法的时间复杂度和空间复杂度。

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int data;
	struct  node* next;
}Node;
void insertlist1(Node* list, int arr[], int n)
{
	Node* hail;
	hail = malloc(sizeof(Node));
	hail = list;
	Node* temp;
	for (int i = 0; i < n; i++)
	{
		temp = malloc(sizeof(Node));
		temp->next = NULL;
		temp->data = arr[i];

		hail->next = temp;
		hail = temp;
	}
	hail->next = NULL;
}
void insertlist2(Node* list, int arr[], int n)
{
	Node* temp;
	for (int i = 0; i < n; i++)
	{
		temp = malloc(sizeof(Node));
		temp->data = arr[i];
		temp->next = NULL;

		temp->next = list->next;
		list->next = temp;
	}
}
void printflist(Node* list)
{
	Node* p;
	p = malloc(sizeof(Node));
	p = list->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}
int countx(Node* list, int x)
{
	Node* p;
	p = malloc(sizeof(Node));
	p = list->next;
	int count = 0;
	while (p->data < x)
	{
		p = p->next;
	}
	Node* q;
	q = malloc(sizeof(Node));
	q = p->next;
	Node* qleft;
	Node* qright;
	qleft = malloc(sizeof(Node));
	qright = malloc(sizeof(Node));
	qleft = p;

	while (q)
	{
		qright = q->next;
		if (q->data > x && q->data != qleft->data)
		{
			count++;
		}
		qleft = qleft->next;
		q = qright;
	}
	//printf("%d ", count);
	return count;

}
int deleteeven(Node* list, int x)
{
	Node* p;
	p = malloc(sizeof(Node));
	p = list->next;
	while (p->data < x)
	{
		p = p->next;
	}
	Node* q;
	q = malloc(sizeof(Node));
	q = p->next;
	Node* qleft;
	Node* qright;
	qleft = malloc(sizeof(Node));
	qright = malloc(sizeof(Node));
	qleft = p;
	Node* temp;
	while (q)
	{
		qright = q->next;
		if (q->data % 2 == 0)
		{
			temp = malloc(sizeof(Node));
			temp = q;
			qleft->next = qright;
			q = qright;

			free(temp);
		}
		else
		{
			qleft = qleft->next;
			q = qright;
		}
	}
}
void inverlist(Node* list, int x)
{
	Node* p;
	p = malloc(sizeof(Node));
	p = list->next;
	Node* pre = malloc(sizeof(Node));
	pre = list;
	while (p->data < x)
	{
		pre = pre->next;
		p = p->next;
	}
	Node* r;
	r = malloc(sizeof(Node));
	r = list->next;
	Node* rright;
	rright = malloc(sizeof(Node));
	list->next = NULL;

	while (r != pre)
	{
		rright = r->next;
		r->next = pre->next;
		pre->next = r;
		r = rright;
	}
	list->next = pre;

}
int main()
{
	int arr[13] = { 3,5,6,6,8,10,11,13,13,16,17,20,20 };
	Node* list;
	list = malloc(sizeof(Node));
	list->next = NULL;
	insertlist1(list, arr, 13);
	//insertlist2(list, arr, 13);
	printflist(list);
	printf("\n");

	int count = 0;
	count = countx(list, 10);
	printf("the >x numbers is %d \n", count);


	deleteeven(list, 10);
	printflist(list);
	printf("\n");

	inverlist(list, 10);
	printflist(list);
	printf("\n");
	return 0;
}