LinkList

#define _CRT_SECURE_NO_WARNINGS //屏蔽vscode2019中不可以使用scanf函数错误的


#include 
#include 
#include 


typedef struct Node {
	int data;//数据域
	struct Node* next;//指针域
} NODE, *PNODE;//NODE等价于struct Node，PNODE等价于struct Node *
//函数声明
PNODE creat_list(void);
void traverse_list(PNODE pHead);//遍历链表
bool is_empty(PNODE pHead);
int lenth_list(PNODE pHead);
bool insert_list(PNODE pHead, int pos, int val);
bool delete_list(PNODE pHead, int pos, int* pVal);
void sort_list(PNODE pHead);//冒泡排序

int main() {
	//链表的程序不仅要会还要能敲出来
	PNODE pHead = NULL;//等价于struct Node * pHead
	//头指针

	pHead = creat_list();//创建一个链表
	traverse_list(pHead);

	int lenth = lenth_list(pHead);
	printf("链表节点:%d n",lenth);

	insert_list(pHead, 2, 30);
	traverse_list(pHead);

	
	return 0;
}

PNODE creat_list(void) {
	int len;
	int val;

	printf("请输入你要生成节点个数n");
	scanf("%d", &len);

	PNODE pHead = (PNODE)malloc(sizeof(NODE));//头节点
	if (pHead == NULL) {
		printf("分配失败，程序终止运行n");//如果内存都分配失败了，
		//程序就没运行下去的必要了！
		exit(-1);
	}

	PNODE pLow = pHead;//pLow永远指向最后一个节点
	pHead->next = NULL;

	for (int i = 0; i < len; i++) {
		printf("请输入这个节点的值n");
		scanf("%d", &val);
		PNODE pNew = (PNODE)malloc(sizeof(NODE)); 
		if (pNew == NULL) {
			printf("分配失败，程序终止运行n");
			exit(-1);
		}
		pNew->data = val;//pNew数据域初始化
		pNew->next = NULL;//pNew指针域初始化
		
		pLow->next = pNew;//让pLow指向的节点的指针域等于新节点
		pLow = pNew;//让pLow永远指向尾节点
	}
	return pHead;
}

void traverse_list(PNODE pHead) {
	PNODE p = pHead->next;//这是首节点
	//pHead是头指针 
	//pHead->next，是头结点的指针域是首节点

	
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("n");
}

int lenth_list(PNODE pHead) {
	int len = 0;
	PNODE p = pHead->next;
	while (p != NULL) {
		len++;
		p = p->next;
	}
	return len;
}

bool is_empty(PNODE pHead) {
	if (pHead->next == NULL) {
		return true;
	}
	return false;
}

void sort_list(PNODE pHead) {
	int i, j, t;
	PNODE p, q;

	int len = lenth_list(pHead);
	//这里把链表看成数组
	
	for (i = 0,p = pHead->next; i < len - 1; i++,p = p->next) {
								
		
		for (j = i + 1, q = p->next; j < len; j++, q = q->next) {
			if (p->data > q->data) {
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
	
}


bool insert_list(PNODE pHead, int pos, int val) {
	//pos的值要合理，要在合理节点范围
	int i = 0;
	PNODE p = pHead;
	while (p != NULL && i < pos - 1) {
		p = p->next;
		i++;
	}
	if (pos-1 < i || p == NULL) return false;
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew) {
		printf("动态分配内存失败n");
		exit(-1);
	}
	pNew->data = val;
	PNODE q = p->next;
	p->next = pNew;
	pNew->next = q;
	return true;
}

bool delete_list(PNODE pHead, int pos, int* pVal) {
	int i = 0;
	PNODE p = pHead;
	while (p->next != NULL && i < pos - 1) {
		p = p->next;
		i++;
	}
	if (pos - 1 < i || p->next == NULL) return false;
	
	PNODE q = p->next;
	*pVal = q->data;
	//删除p节点后面的节点
	p->next = p->next->next;
	free(q);
	q = NULL;

	return true;
}

个人觉得实现起来还是挺有成绩感的
有兴趣可以看一下我的另一篇ArrayList以数组为核心的线性表的实现方法