[数据结构与算法]考研数据结构:(三)单链表(带头节点)的基本操作(只有干货)

/*
	Author : panxiaolan
	Time : 2021-10-12 

	单链表的基本操作(带头节点):
	(1)、单链表的定义
	(2)、单链表的初始化
	(3)、单链表的建立:
		a、头插法建立
		b、尾插法建立 
	(4)、单链表的插入:
		a、后插
		b、前插
		c、指定位置插入 
	(5)、单链表删除:
		a、按位序删
		b、前删
		c、后删 
	(6)、单链表查找:
		a、按位查找
		b、按值查找 
	(7)、单链表长度 
	(8)、单链表输出 


*/
#include <stdio.h>
#include <stdlib.h>

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

// 单链表的初始化(带头节点)
ListLink InitListLink(ListLink &L) {
	L = (LNode *)malloc(sizeof(LNode));
	if(!L) return NULL;
	L->next = NULL;
	return L;
}

// 头插法建立单链表(带头节点)
ListLink headCreateListLink(ListLink &L) {
	InitListLink(L);
	LNode *s,*p = L;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		s = (LNode *) malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
	}
	return L;
}

// 尾插法建立单链表(带头节点)
ListLink tailCreateListLink(ListLink &L) {
	// 初始化
	InitListLink(L);
	LNode *s,*r = L;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
	}
	r->next = NULL;
	return L;
}

// 按位查找,返回第 i 个元素(带头节点)
LNode* getElem(ListLink &L,int i) {
	LNode *p = L;
	int j = 0;
	while(p->next != NULL && j < i ) {
		p = p->next ;
		j ++;
	}
	return p;
}

// 按值查找,返回数据域是 e 的节点(带头节点)
LNode* locateElem(ListLink &L,int e) {
	LNode *p = L->next;
	while(p != NULL && p->data != e) {
		p = p->next;
	}
	return p;
}

// 统计单链表的长度(带头节点)
int length(ListLink &L) {
	int len = 0;
	LNode *p = L;
	while(p->next != NULL) {
		p = p->next;
		len ++;
	}
	return len;
}

// 后插操作,在节点 P 之后插入元素 e
bool insertNextNode(LNode *p,int e) {
	if(!p) return false;
	LNode *s;
	s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}


// 插入操作: 在第 i 个位置插入元素 e (带头节点)
bool insertNode(ListLink &L,int i,int e) {
	// 因为有头节点,所以不用再去特殊考虑第一个节点啦 ~
	LNode *p = getElem(L,i - 1);
	insertNextNode(p,e);
	return true;
}

// 前插操作: 在 P 节点前插入元素 e
bool insertPrionNodeE(LNode *p,int e) {
	if(!p) return false;
	LNode *s;
	s = (LNode *)malloc(sizeof(LNode));

	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;

	return true;
}

// 前插操作: 在节点 p 之前插入节点 s
bool insertPriorNode(LNode *p,LNode *s) {
	if(!p || !s) return false;
	s->next = p->next;
	p->next = s;
	int temp = p->data;
	p->data = s->data;
	s->data = temp;
	return true;
}

// 删除操作: 删除位序 i 的节点, e 是 i 节点的值
bool deleteNode(ListLink &L,int i,int &e) {
	// 因为带头节点,所以不用再去特殊考虑第 1 个节点啦 ~
	LNode *q;
	LNode *p = getElem(L,i - 1);
	q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

// 删除指定节点 P:
bool deletePositionNode(LNode *p) {
	if(p->next == NULL) return false;
	LNode *q = p->next;
	p->next = q->next;
	p->data = q->data;
	free(q);
	return true;
}

// 输出单链表(带头节点)
void print(ListLink &L) {
	LNode *p = L->next;
	while(p) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
	return ;
}
int main() {
	ListLink L;
	// 头插法建立单链表
//	headCreateListLink(L);
	// 尾插法建立单链表
	tailCreateListLink(L);
	printf("-------------尾插法建立单链表--------------\n");
	print(L);
	printf("-------------按位查找:返回第 2 个节点--------------\n");
	LNode *p = getElem(L,2);
	printf("%d\n",p->data);
	printf("-------------按值查找:返回数值是 8 的节点--------------\n");
	LNode *value = locateElem(L,8);
	printf("%d\n",value->data);
	printf("-------------单链表的长度--------------\n");
	printf("%d\n",length(L));

	printf("-------------后插操作,在节点 p 之后插入元素 999--------------\n");
	insertNextNode(p,999);
	printf("-------------后插操作,在节点 p 之后插入元素 999 的单链表:--------------\n");
	print(L);


	printf("-------------插入操作: 在第 4 个位置插入元素 10000000 (带头节点)--------------\n");
	insertNode(L,4,10000000);
	printf("-------------插入操作: 在第 4 个位置插入元素 10000000 (带头节点) 的单链表:--------------\n");
	print(L);


	printf("-------------前插操作: 在 P 节点前插入元素 555--------------\n");
	insertPrionNodeE(p,555);
	printf("-------------前插操作: 在 P 节点前插入元素 555 的单链表:--------------\n");
	print(L);

	printf("-------------前插操作: 在节点 p 之前插入节点 s--------------\n");
	LNode *s;
	s = (LNode *)malloc(sizeof(LNode));
	s->data = 666;
	s->next = NULL;
	LNode *q = getElem(L,4);
	insertPriorNode(q,s);
	printf("-------------前插操作: 在节点 q 之前插入节点 s 后的单链表:--------------\n");
	print(L);
	
	printf("-------------删除操作: 删除位序 i 的节点, e 是 i 节点的值--------------\n");
	int e; 
	deleteNode(L,5,e);
	printf("删除的值是 %d\n",e);
	printf("-------------删除操作: 删除位序 i 的节点, e 是 i 节点的值 的单链表:--------------\n");
	print(L);
	
	
	printf("-------------删除指定节点 m:--------------\n");
	LNode *m = getElem(L,2);
	deletePositionNode(m);
	printf("-------------删除指定节点 m 后的单链表:--------------\n");
	print(L);
	return 0;
}