[数据结构与算法]单链表的基本操作

SList.h头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode {
	SLTDateType data;
	struct SListNode * next;
}SLTNode;
void SListPrint(SLTNode *phead);
void SListPushBack(SLTNode** pphead, SLTDateType x);//后插
void SListPushFront(SLTNode** pphead, SLTDateType x);//前插
void SListPopBack(SLTNode** pphead);//后删操作
void SListPopFront(SLTNode** pphead);//前删操作
SLTNode *SListFind(SLTNode* phead, SLTDateType x);//查找链表中值为x的结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//pos之前插入一个结点
void SListErase(SLTNode** pphead, SLTNode* pos);
void SListDestory(SLTNode** pphead);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);

SList.c源文件

#include"SList.h"
SLTNode* BuyListNode(SLTDateType x) {//申请一个新结点
	SLTNode *newnode = (SLTNode *)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		printf("malloc fail.\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}
void SListPrint(SLTNode *phead) {//打印链表
	SLTNode* cur = phead;
	while (cur) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
void SListPushBack(SLTNode** pphead, SLTDateType x) {//后插操作
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL) {//当链表尾空链表的时候
		*pphead = newnode;
	}
	else {
		SLTNode *tail = *pphead;
		while (tail->next) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SListPushFront(SLTNode** pphead, SLTDateType x) {//前插
	SLTNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SListPopBack(SLTNode** pphead) {//后插
	assert(*pphead);
	if ((*pphead)->next == NULL) { //当链表为一个结点的时候
		free(*pphead);
		*pphead = NULL;
	}
	else {//当两个以及两个以上的时候
		SLTNode *tail = *pphead;
		while (tail->next->next) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;

	}

}
void SListPopFront(SLTNode** pphead) {//链表前删
	assert(*pphead);
	SLTNode *next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x) {//查找数
	SLTNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		else {
			cur = cur->next;
		}
	}
	return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode *pos, SLTDateType x) {//pos结点前插
	SLTNode *newnode = BuyListNode(x);
	if (*pphead == pos) {//当链表为空的时候
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else {
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos) {
			posPrev = posPrev->next;
		}
		posPrev->next = newnode;
		newnode->next = pos;
	}
}
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x) {//后插
	assert(pos);
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListErase(SLTNode **pphead, SLTNode* pos) {
	assert(pphead);
	assert(pos);
	if (*pphead == pos) {
		SListPopFront(pphead);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
void SListEraseAfter(SLTNode *pos) {
	assert(pos);
	assert(pos->next);
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}
void SListDestory(SLTNode **pphead) {
	assert(*pphead);
	SLTNode *cur = *pphead;
	while (cur) {
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

main.c源文件：

#include"SList.h"


void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);

	SListPrint(plist);

	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);

	SListPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);

	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	//SListPopBack(&plist);

	SListPrint(plist);
}

void TestSList3()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);

	SListPopFront(&plist);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPrint(plist);
}

void TestSList4()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	// 找
	SLTNode* pos = SListFind(plist, 2);
	int i = 1;
	while (pos)
	{
		printf("第%d个pos节点:%p->%d\n", i++, pos, pos->data);
		pos = SListFind(pos->next, 2);
	}

	// 修改 3->30
	pos = SListFind(plist, 3);
	if (pos)
	{
		pos->data = 30;
	}
	SListPrint(plist);
}

void TestSList5()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist, pos, 30);
	}
	SListPrint(plist);

	pos = SListFind(plist, 1);
	if (pos)
	{
		SListInsert(&plist, pos, 10);
	}
	SListPrint(plist);

	pos = SListFind(plist, 4);
	if (pos)
	{
		SListInsert(&plist, pos, 40);
	}
	SListPrint(plist);
}

void TestSList6()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);

	SListPrint(plist);

	SListDestory(&plist);
}

int main()
{
	//TestSList1();
	//TestSList2();
	//TestSList3();
	//TestSList4();
	TestSList6();

	return 0;
}



// // Definition for singly-linked list.
// struct ListNode {
//     int val;     
//	 struct ListNode *next;
// };
//
//struct ListNode* removeElements(struct ListNode* head, int val){
//	struct ListNode* prev = NULL, *cur = head;
//	while (cur)
//	{
//		if (cur->val == val)
//		{
//			// 1、头删
//			// 2、中间删除
//			prev->next = cur->next;
//			free(cur);
//			cur = prev->next;
//		}
//		else
//		{
//			// 迭代往后走
//			prev = cur;
//			cur = cur->next;
//		}
//	}
//
//	return head;
//}
//
//int main()
//{
//	// 方便快速调试oj代码
//	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//	n1->val = 7;
//	n2->val = 7;
//	n3->val = 7;
//	n4->val = 7;
//	n1->next = n2;
//	n2->next = n3;
//	n3->next = n4;
//	n4->next = NULL;
//
//	struct ListNode* head = removeElements(n1, 7);
//
//
//	return 0;
//}