考研資料結構:(三)單連結清單(帶頭節點)的基本操作(隻有幹貨)

/*
	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;
}