数据结构系列-链表实现

🌈个人主页: 会编辑的果子君

💫个人格言:“成为自己未来的主人~”

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void ListTest01() {
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
}
int main() {
	ListTest01();
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
LTNode* LTBuyNode(LTDataType x) {
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

LTNode* LTInit() {
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x) {
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next = newnode;
}

void LTPrint(LTNode* phead) {
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//尾删
void LTPopBack(LTNode* phead) {
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

	prev->next = phead;
	phead->prev = prev;

	free(del);
	del = NULL;
}


//头删
void LTPopFront(LTNode* phead) {
	assert(phead);
	assert(phead->next != phead);
	LTNode* del = phead->next;
	LTNode* next = del->next;

	next->prev = phead;
	phead->next = next;

	free(del);
	del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在pos位置之后插入数据
void LTInset(LTNode* pos, LTDataType x) {
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除pos位置的数据
void LTErase(LTNode* pos) {
	assert(pos);

	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

void LTDesTroy(LTNode* phead) {
	//哨兵位不能为空
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//链表中只有一个哨兵位
	free(phead);
	phead = NULL;
}

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//注意，双向链表是有一个哨兵位的，所以在插入数据之前需要先初始化一个哨兵位
LTNode* LTInit();
void LTDesTroy(LTNode* phead);
void LTPrint(LTNode* phead);

//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

//头删，尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);