王道資料結構經典代碼題-連結清單

王道資料結構經典代碼題 − 連結清單 \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;
}