#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#pragma once

using namespace std;

0.单链表结构体

typedef struct Linknode {
int info;
struct Linknode* next;
}*Link;

1.头插法创建单链表

不带头节点

Link create1() {
	struct Linknode* head, * p;
	head = (Link)malloc(sizeof(Linknode));
	head = NULL;
	int info;
	printf("999");
	scanf("%d", &info);
	while (info != 999) 
	{
		p = (Link)malloc(sizeof(Linknode));
		p->info = info;
		p->next = head;
		head = p;
		scanf("%d", &info);
	}
	return head;
}

带头结点

Link create2() {
	Linknode* head, * p;
	head = (Link)malloc(sizeof(Linknode));
	head->next = NULL;
	int info;
	printf("999");
	scanf("%d", &info);
	while (info != 999)
	{
		p = (Link)malloc(sizeof(Linknode));
		p->info = info;
		p->next = head->next;
		head->next= p;
		scanf("%d", &info);
	}
	return head;
}

2.尾插法创建单链表

不带头结点

Link create3()
{
	Linknode* head, * rear, * p;
	head = (Link)malloc(sizeof(Linknode));
	int info;
	head=rear= NULL;
	printf("999");
	scanf("%d", &info);
	while (info != 999)
	{
		p = (Link)malloc(sizeof(Linknode));
		p->info = info;
		if (head == NULL)
			head = p;
		else
			rear->next = p;
		rear = p;
		scanf("%d", &info);
	}
	rear ->next = NULL;
	return head;
}

带头结点

Link create4()
{
	Linknode* head, * rear, * p;
	head = (Link)malloc(sizeof(Linknode));
	head->next = NULL;
	rear = head;
	int info;
	printf("输入999结束\n");
	scanf("%d", &info);
	while (info != 999)
	{
		p = (Link)malloc(sizeof(Linknode));
		p->info = info;
		rear->next = p;
		rear = p;
		scanf("%d", &info);
	}
	rear->next = NULL;
	return head;	
}

3.查找第i个结点的地址

带头结点

Link find1(Linknode *head,int i)
{
	int j = 0;
	Linknode *p = head;
	if (i < 0)
	{
		printf("不存在第i个结点");
		return NULL;
	}
	else if (i == 0) 
	{
		return p;
	}
	while (p && i != j)
	{
		p = p->next;
		j++;
	}
	return head;

}

不带头结点

Link find2(Linknode* head, int i)
{
	int j = 1;
	Linknode* p = head;
	if (i < 1)
		return NULL;
	else if (i == 1)
		return p;
	while (p && j!=i) 
	{
		p = p->next;
		j++;
	}
	return p;
}

4.输出各个结点的值

不带头结点

void disp1(Linknode* head)
{
	Linknode* p = head;
	if (!p)
		printf("空");
	else
	{
		printf("\n");
		while (p)
		{
			printf("%d", p->info);
			p = p->next;
		}
		printf("\n");
	}
}

带头结点

void disp(Linknode* head)
{
	Linknode* p = head->next;
	if (!p)
		printf("空");
	else 
	{
		printf("\n");
		while (p)
		{
			printf("%d", p->info);
			p = p->next;
		}
		printf("\n");
	}
}

5.单链表删除第一个值为x的结点

带头

Link delX1(Linknode* head, int x)
 {
	 Linknode* q, * pre = head;
	 q = head->next;
	 while (q && q->info != x)
	 {
		 pre = q;
		 q = q->next;
	 }
	 if (q) 
	 {
		 pre->next = q->next;
		 free(q);
	 }
	 return head;
 }

不带头

Link delX2(Linknode* head, int x)
 {
	 Linknode* q, * pre = NULL;
	 if (head == NULL) 
	 {
		 printf("空");
		 return head;
	 }
	 q = head;
	 while (q&& q->info != x) 
	 {
		 pre = q;
		 q = q->next;
	 }
	 if (q)
	 {
		 if (!pre)
			 head = head->next;
		 else 
		 {
			 pre->next = q->next;
		 }
		free(q);
	 }
	 return head;
 }

6.单链表插入x结点

带头

Link insert1(Linknode* head,int i,int x) 
 {
	 Linknode* q, * p;
	 int j = 0;
	 q=find1(head, i);
	 if (!q)
		 printf("不存在此结点");
	 else {
		 p = (Link)malloc(sizeof(Linknode));
		 p->info = x;
		 p->next = q->next;
		 q->next = p;
	 }
	 return head;
 }

不带头

Linknode* insert2(Linknode* head, int i, int x)
 {
	 Linknode* p, * q;
	 q = find2(head, i);
	 if (!q&&i!=0)
		 printf("此结点不存在");
	 else 
	 {
		 p = (Link)malloc(sizeof(Linknode));
		 p->info = x;
		 if (i == 0)//如果为空表
		 {
			 head->next = p;
			 head = p;
		 }
		 else 
		 {
			 p->next = q->next;
			 q->next = p;
		 }
	 }
	 return p;
 }

7.求带头节点单链表结点个数

int length(Linknode* head)
 {
	 int count = 0;
	 Linknode* p = head->next;
	 while (p)
	 {
		 count++;
		 p = p->next;
	 }
	 return count;
 }

8.求单链表结点个数

int length2(Linknode* head) 
 {
	 int count = 0;
	 Linknode* p = head;
	 if (!p)
		 return 0;
	 else {
		 count++;
		 while (p) {
			 count++;
			 p = p->next;
		 }
	 }
	 return count;
 }

9.在单链表中值为y的结点前面插入x结点，使x成为它的前驱结点。

void insertXY(Linknode* head, int x, int y)
 {
	Linknode *p, *pre, *s;
	pre = head;
	p = head->next;
	while (p && p->info != y)
	{
		pre = p;
		p = p->next;
	}
	if (p)
	{
		s = (Link)malloc(sizeof(Linknode));
		s->info = x;
		s->next = p;
		pre->next = s;

	}
 }

10.判断单链表是否有序(升序、降序)

int isSort(Linknode* head)
{
	Linknode * f=head->next, * r=f->next;
	while (r)
	{
		if (f->info <= r->info)
		{
			f = f->next;
			r = f->next;
		}
		else
			return 0;
	}
	return 1;
}

11.原地逆置单链表

void reverse(Linknode* head) 
{
	Linknode* p, * r;
	p = head->next;
	head->next = NULL;
	while (p)
	{
		r = p->next;
		p->next = head->next;
		head->next = p;
		p = r;
		
	}
}

12.将一个结点值为自然数的单链表拆分成两个单链表，原表保留偶数结点

Linknode *head2;
void cutLink(Linknode* head)
{
	head2 = (Link)malloc(sizeof(Linknode));
	head2->next = NULL;
	Linknode* r1 = head, * r2 = head2, * p = r1->next;
	while (p)
	{
		if (p->info % 2 != 0) 
		{
			r1->next = p->next;
			p->next = r2->next;
			r2->next = p;
			r2 = p;
		}
		else {
			r1 = p;
		}
		p = r1->next;
	}
}

13.对有序单链表，删除所有值大于x而不大于y的结点

递归(不带头结点)

void del1(Linknode*& head, int x, int y) {
	Linknode* pre;
	if (head == NULL && x < y) return;
	if (head->info > x && head->info < y) 
	{
		pre = head;
		head = head->next;
		free(pre);
		del1(head, x, y);
	}
	else 
	{
		del1(head->next, x, y);
	}
}

void del2(Linknode*& head, int x, int y) {
	Linknode* p = head->next, * r = head;
	while (p)
	{
		if (p->info>x && p->info<y) {
			r->next = p->next;
			free(p);
			p = r->next;
		}
		else 
		{
			r = p;
			p = p->next;
		}
	}
}

14.求两个单链表的交集，放入一个新表中

Linknode* L3;
Linknode* findd(Linknode* L1, Linknode* L2) 
{
	L3 = (Link)malloc(sizeof(Linknode));
	L3->next = NULL;
	Linknode* s1 = L1->next, * p, * r=L3;
	while (s1) {
		Linknode* s2 = L2->next;
		while (s2) {
			if (s1->info == s2->info)
			{
				p = (Link)malloc(sizeof(Linknode));
				p->info = s1->info;
				r->next = p;
				r = p;
			}
			s2 = s2->next;
		}
		s1 = s1->next;
	}
	r->next = NULL;
	return L3;
}

15.删除带头结点的单链表head中所有为奇数值的结点

void delX(Linknode* &head) 
{
	Linknode* pre = head, * p = pre->next;
	while (p)
	{
		if (p->info % 2 == 1) 
		{
			pre->next = p->next;
			free(p);
			p = pre->next;
		}
		pre = p;
		p = p->next;
	}
}

16.将带头结点的链表按升序排列

void sortlist(Linknode* head)
{
	Linknode* p = head->next, * r = p->next, * f;
	p->next = NULL;
	p = r;
	while (p)
	{
		r = p->next;
		f = head;
		while (f->next != NULL && f->next->info < p->info)
			f = f->next;
		p->next = f->next;
		f->next = p;
		p = r;
	}
}

17.1将两个都为升序的带头结点的单链表L1和L2合并按降序排列

Linknode* L2;
 void merge2(Linknode*& L1, Linknode*& L2)
{
	 Linknode* p1, * p2, * r;
	p1 = L1->next, p2 = L2->next;
	L1->next = NULL;
	while (p1 && p2) {
		if (p1->info <= p2->info)
		{
			r = p1->next;
			p1->next = L1->next;
			L1->next = p1;
			p1 = r;
		}
		else
		{
			r = p2->next;
			p2->next = L1->next;
			L1->next = p2;
			p2 = r;
		}
	}

	if (p1) p2 = p1;
	while (p2)
	{
		r = p2->next;
		p2->next = L1->next;
		L1->next = p2;
		p2 = r;
	}
	free(L2);
}

17.2.将两个都为升序的带头结点的单链表L1和L2合并按升序排列

void merge(Linknode* &L1, Linknode* &L2) {
	Linknode* p1 = L1->next, * p2 = L2->next, * r,*f;
	L1->next = NULL;
	f = L1;
	while (p1&&p2) {
		if (p2->info >= p1->info) {
			r = p1->next;
			p1->next = f->next;
			f->next = p1;
			p1 = r;
			f = f->next;
		}
		else{
			r = p2->next;
			p2->next = f->next;
			f->next = p2;
			p2 = r;
			f = f->next;
		}
	}
	if (p1) //如果p1不存在，那么p2肯定存在
		p2 = p1;
	while (p2)
	{
		r = p2->next;
		p2->next = f->next;
		f->next = p2;
		p2 = r;
		f = f->next;
	}
	free(L2);
}

18.将带头结点的单链表head中值为奇数的结点调整到链表前，所有偶数在链表后

Linknode* split(Linknode* head) {
	 Linknode *pre, *p;
	 pre = head;
	 p = head->next;
	 while (p->info % 2 != 0) 
	 {
		 pre = p;
		 p = p->next;
	 }
	 while (p)
	 {
		 if (p->info % 2 == 1)
		 {
			 pre->next = p->next;
			 p->next = head->next;
			 head->next = p;
			 p = pre;
		 }
		 else
		 {
			 pre = p;
			 p=p->next;
		 }
	 }
	 return head;
 }

19.编写一个算法尽可能快的返回表中倒数第k个结点地址如果不存在返回null

Linknode* findk2(Linknode* &head, int k) {
	 Linknode* p = head->next, * q = head->next;
	 int num = 0;
	 while (p) {
		 if (num < k)num++;
		 else
			 q = q->next;
		 p = p->next;
	 }
	 if (num < k) return NULL;
	 else
		 printf("倒数第%d个元素是%d", num, q->info);
	 return q;
 }

Q.E.D.

好好学习天天向上~~

0.单链表结构体

1.头插法创建单链表

不带头节点

带头结点

2.尾插法创建单链表

不带头结点

带头结点

3.查找第i个结点的地址

带头结点

不带头结点

4.输出各个结点的值

不带头结点

带头结点

5.单链表删除第一个值为x的结点

带头

不带头

6.单链表插入x结点

带头

不带头

7.求带头节点单链表结点个数

8.求单链表结点个数

9.在单链表中值为y的结点前面插入x结点，使x成为它的前驱结点。

10.判断单链表是否有序(升序、降序)

11.原地逆置单链表

12.将一个结点值为自然数的单链表拆分成两个单链表，原表保留偶数结点

13.对有序单链表，删除所有值大于x而不大于y的结点

递归(不带头结点)

14.求两个单链表的交集，放入一个新表中

15.删除带头结点的单链表head中所有为奇数值的结点

16.将带头结点的链表按升序排列

17.1将两个都为升序的带头结点的单链表L1和L2合并按降序排列

17.2.将两个都为升序的带头结点的单链表L1和L2合并按升序排列

18.将带头结点的单链表head中值为奇数的结点调整到链表前，所有偶数在链表后

19.编写一个算法尽可能快的返回表中倒数第k个结点地址如果不存在返回null

Springboot整合Redis

[考研]江西师范大学865考研数据结构二叉树考点

黄霸霸

HCXNB