王道数据结构经典代码题−链表
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;
}
6.从链表中删除给定值在s到t之间(不包含s和t)的所有元素
#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 min, int max) {
LNode *p = L;
/*LNode *P = L;*/
while (p->next!=NULL) {
if (p->next->data > min && p->next->data < max) {
LNode *u = p->next;
p->next = u->next;
free(u);
}
else {
p = p->next;
}
}
}
int main() {
/*LNode *L = aaaa();
del(L, 1, 4);
LNode *q = L->next;
while (q!=NULL) {
cout << q->data << " ";
q = q->next;
}
return 0;*/
LNode *L = aaaa();
del(L, 1, 4);
LNode *q = L->next;
while (q != NULL) {
cout << q->data << " ";
q = q->next;
}
return 0;
}
7、试编写在带头结点的单链表L中删除最小值点的高效算法(已知最小值唯一)
#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_min(LNode *&L) {
LNode *p = L->next;
LNode *minp = L;
while (p->next!=NULL) {
if (p->next->data < minp->next->data) {
minp = p;
}
p = p->next;
}
LNode *u = minp->next;
minp->next = u->next;
free(u);
}
int main() {
LNode *L = aaaa();
del_min(L);
LNode *q = L->next;
while (q!=NULL) {
cout << q->data << " ";
q = q->next;
}
return 0;
}
8 、试编写在不带头结点的单链表L中删除最小值点的高效算法(已知最小值唯一)
#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;
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_min(LNode *&L) {
LNode *minp = L;
LNode *p = L->next;
while (p!=NULL) {
if (p->data < minp->data) {
minp = p;
}
p = p->next;
}
if (L == minp) {
L = L->next;
free(minp);
return;
}
p = L;
while (p->next!=minp) {
p = p->next;
}
p->next = minp->next;
free(minp);
}
int main() {
LNode *L = aaaa();
del_min(L);
LNode *q = L->next;
while (q!=NULL) {
cout << q->data << " ";
q = q->next;
}
return 0;
}