[数据结构与算法]王导数据结构链表2-2.2

//删除带头结点的链表中的结点

note：这里需要三个指针，用递归法只需一个*q，遍历用L->next即可。

#include<iostream>
using namespace std;
typedef struct lnode {
	int data;
	struct lnode* next;
}lnode,*linklist;
int a[5] = { 1,2,1,1,3 };
int n = 5;
void buildlist(linklist& L) {
	L = (lnode*)malloc(sizeof(lnode));
	if (L == NULL)return;//判空
	lnode* r = L, * s;
	for (int i = 0; i < n; i++) {
		s = (lnode*)malloc(sizeof(lnode));
		s->data = a[i];
		r->next = s;
		r = r->next;
	}
	r->next = NULL;
}
void disp(linklist L) {
	lnode* s = L->next;
	while (s) {
		cout << s->data << "  ";
		s = s->next;
	}
	cout << endl;
}
void deletex(linklist& L, int x) {
	if (L == NULL)return;//判空
	lnode* q, * r = L, * p = L->next;//q用来释放空间，r表示要删除元素x的前序，p用来遍历链表
	while (p) {
		if (p->data != x) {
			r->next = p;//当删除元素x时，把x的前元素跟x的后元素相连
			r = p;
			p = p->next;
		}
		else {
			q = p;
			p = p->next;
			free(q);
		}
	}
}
int main()
{
	linklist L;
	buildlist(L);
	disp(L);
	deletex(L, 1);
	disp(L);
	return 0;
}