C语言单链表操作基础

C语言单链表操作基础

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(NODE)

typedef struct _NODE//节点声明
{
	int val;
	struct _NODE* next;
} NODE, *PNODE;

void print(PNODE head){//打印所有节点
	while (head)
	{
		printf("%3d",head->val);
		head = head->next;
	}
	printf("\n");
}

void insertHead(PNODE *pHead, int val){//头插法
	PNODE n = (PNODE)malloc(LEN);
	n->val = val;
	n->next = *pHead;
	*pHead = n;
}

void insertTail(PNODE *pHead, int val){//尾插法
	PNODE t = *pHead;
	PNODE n = (PNODE)malloc(LEN);
	n->val = val;
	n->next = NULL;
	if (*pHead == NULL)
	{
		n->next = *pHead;
		*pHead = n;
	}else{
		while (t->next)
		{
			t = t->next;
		}
		t->next = n;
	}
}

void deleteHead(PNODE *pHead){//删除头
	if (*pHead == NULL)
	{
		return;
	}
	else
	{
		PNODE t = *pHead;
		*pHead = (*pHead)->next;
		free(t);
	}
}

void deleteTail(PNODE *pHead){//删除尾
	PNODE t = *pHead;
	if (t == NULL)
	{
		return;
	}
	else if (t->next == NULL)
	{
		free(t);
		*pHead = NULL;
	}
	else{		
		while (t->next->next != NULL)
		{
			t = t->next;
		}
		free(t->next);
		t->next = NULL;
	}
}

PNODE findByVal(PNODE head, int val){//根据值找到满足条件的第一个节点
	while (head != NULL && head->val != val)
	{
		head = head->next;
	}
	return head;
}

PNODE findByIndex(PNODE head, int index){//根据索引找节点
	if (index == 1)
	{
		return head;
	}
	else
	{
		int c = 1;
		while (head != NULL && index != c)
		{
			head = head->next;
			c++;
		}
	}
	return head;
}

void insertByIndex(PNODE *pHead, int index, int val){//根据索引插入节点
	if (index == 1)
	{
		insertHead(pHead, val);
	}
	else
	{
		PNODE t = findByIndex(*pHead,index - 1);
		if (t == NULL)
		{
			return;
		}
		else
		{
			PNODE n = t->next;
			t->next = (PNODE)malloc(LEN);
			t->next->next = n;
			t->next->val = val;
		}
	}
}

void deleteByIndex(PNODE *pHead, int index)//根据结点索引删除结点
{
	if (index == 1)
	{
		deleteHead(pHead);
	}
	else
	{
		PNODE t= findByIndex(*pHead, index - 1);
		if (t == NULL || t->next == NULL)
		{
			return;
		}else{
			PNODE n = t->next->next;
			free(t->next);
			t->next = n;
		}
	}
}

void deleteByVal(PNODE *pHead, int val)//根据值删掉第一个满足条件的
{
	if (*pHead == NULL)//如果空表退出
	{
		return;
	}
	else
	{
		if ((*pHead)->val == val)//如果第一个就是，删头
		{
			deleteHead(pHead);
		}
		else
		{
			PNODE t = *pHead;
			while (t->next != NULL && t->next->val != val)//遍历，若t的next为空或者next是要找的节点则退出
			{
				t = t->next;
			}
			if (t->next)//如果t指向要找的结点的上一个节点
			{
				PNODE n = t->next->next;//删除要找的结点
				free(t->next);
				t->next = n;
			}
		}
	}
}

void clear(PNODE *pHead)//清除链表
{
	while ((*pHead) != NULL)
	{
		deleteHead(pHead);//从头删除
	}
}

void main()
{
	PNODE head = NULL;

	insertTail(&head,1);
	deleteHead(&head);
	insertTail(&head,2);
	insertTail(&head,3);
	insertTail(&head,4);
	insertTail(&head,5);
	insertTail(&head,6);

	print(head);
	insertByIndex(&head, 6, 9);
	print(head);
	//deleteByIndex(&head,3);
	deleteByVal(&head, 2);
	print(head);
	clear(&head);
	print(head);
	insertByIndex(&head,1,12);
	print(head);
}