天天看点

王道数据结构经典代码题-链表

王道数据结构经典代码题 − 链表 \color{#FF3030}{王道数据结构经典代码题-链表} 王道数据结构经典代码题−链表

所有代码均可直接运行

1、设计一个递归算法,删除不带头节点的单链表L中所有值为x的结点

#include <iostream>

using namespace std;

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

//不带头节点的链表
Linklist aaaa() {
	LNode *L = new LNode;
	int a;
	cin >> a;
	L->data = a;
	LNode *p = L; //声明一个指针指向头结点,
	//生成链表
	cin >> a;
	while (a != 0) {
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}

void del_x(LNode *&L, int x) {
	LNode *p;
	/*写递归函数的话首先写递归出口 ,然后再写else的部分,最后再来补充等于x的代码细节*/
	if (L == NULL) 
		return;

	if (L->data == x) {
		p = L;
		L = L->next;
		free(p);
		del_x(L, x);

	}
	else {
		del_x(L->next, x);
	}
}


int main() {

	LNode *L = aaaa();
	del_x(L, 10);

	while (L!=NULL) {
		cout << L->data << " ";
		L = L->next;
	}
}


           

2. 删除带头节点单链表中所有值为x的结点

#include <iostream>

using namespace std;

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode,*Linklist;
//创建带头链表
Linklist aaaa() {
	LNode *L = new LNode;
	LNode *p = L;

	int a;
	cin >> a;

	while (a != 0) {
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}
//法一:
void del(LNode *&L , int x) {
	LNode * p = L->next, *pre = L;
	LNode *q;

	while (p!=NULL) {
		if (p->data == x) {
			q = p;
			pre->next = p->next;
			p = p->next;
			free(q);
		}
		else {
			pre = p;
			p = p->next;
		}
	}
}
//法二:对比法一的好处就是用p充当法一pre的角色 写法更简单一些
void Del(LNode *&L, int x) {
	LNode *p = L;

	while (p->next != NULL) {
		if(p->next->data == x){
			LNode *q = p->next;
			p->next = q->next;

			free(q);
		
		}
		else {
			p = p->next;
		}

	}

}

int main() {
	LNode *L = aaaa();
	Del(L, 10);

	LNode *q = L->next;
	while (q!=NULL) {
		cout << q->data << " ";
		q = q->next;
	}

	return 0;
}

           

3、删除带头节点单链表中第一个值为x的结点

/* 这题和第二题很像,只不过这题是找到了第一个就退出,所以要比第二题多一个if判断找到了就直接退出*/
#include <iostream>

using namespace std;

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

//生成链表,a=0时就退出
Linklist aaaa() {
	LNode *L = new LNode;
	LNode *p = L;
	int a;
	cin >> a;

	while (a != 0) {
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}

	p->next = NULL;

	return L;

}

int finddelete(LNode *&C, int x) {
	LNode *p, *q;
	p = C;
	while (p->next!=NULL) {
		if (p->next->data == x) {
			q = p->next;
			p->next = q->next;
			free(q);
			return 1;
		}
		else {
			p = p->next;
		}

		
	}

	return 0;
}


int main() {
	LNode *L = aaaa();
	finddelete(L, 10);
	LNode * q = L->next;

	while (q != NULL) {
		cout << q->data << " ";
		q = q->next;
	}
	return 0;
}

           

5.试编写算法将单链表就地逆置

#include <iostream>

using namespace std;

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

Linklist aaaa() {
	LNode *L = new LNode;
	LNode *p = L;

	//生成链表
	int a;
	cin >> a;
	while (a!=0) {
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}

void reverse(LNode	*&L) {
	LNode *p = L->next, *r;
	/*LNode *P = L->next, *r;*/
	L->next = NULL;
	while (p!=NULL) {
		r = p->next;
		p->next = L->next;
		L->next = p;
		p = r; 
	}
}

void Reverse(LNode *&L) {
	LNode *p = L->next, *r = p->next;
	LNode *pre;
	p->next = NULL;
	while (r!=NULL) {
		pre = p;
		p = r;
		r = r->next;
		p->next = pre;
	}
	L->next = p;
}


int main() {
	LNode *L = aaaa();
	reverse(L);
	LNode *q = L->next;
	while (q!=NULL) {
		cout << q->data << " ";
		q = q->next;
	}

	return 0;
}


           

继续阅读