欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

有关链表的实现(单向/双向 + 不带头/带头 + 非循环/循环)

程序员文章站 2024-03-21 13:06:34
...
//LinkList.h 单向不带头非循环
#pragma once

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int ElementType;

typedef struct LinkList {
	ElementType e;
	struct LinkList* next;
}LinkList;

/*初始化链表*/
void InitLinkList(LinkList** LL);
/*头插法*/
void PushFront(LinkList** LL, ElementType ET);
/*尾插法*/
void PushBack(LinkList** LL, ElementType ET);
/*打印链表*/
void PrintList(LinkList* LL);
/*头删法*/
void PopFront(LinkList** LL);
/*尾删法*/
void PopBack(LinkList** LL);
/*查找链表*/
LinkList* SListFind(LinkList* L, ElementType x);
/*pos之后插入一个值*/
void SListInsertAfter(LinkList* pos, ElementType x);
/*删除pos之后的值*/
void SListEraseAfter(LinkList* pos);
/*销毁链表*/
void destroyLinkList(LinkList** LL);
//LinkList.c
#include"LinkList.h"

void InitLinkList(LinkList** LL)
{
	*LL = NULL;
}

LinkList* BuyNode(ElementType ET) {
	LinkList* newnode = (LinkList*)malloc(sizeof(LinkList));
	newnode->e = ET;
	newnode->next = NULL;
	return newnode;
	}
void PushFront(LinkList** LL, ElementType ET)
{
	LinkList* newnode = BuyNode(ET);
	newnode->next = *LL;
	*LL = newnode;
}

void PushBack(LinkList** LL, ElementType ET)
{
	LinkList* newnode = BuyNode(ET);
	
	if (*LL == NULL) {
		*LL = newnode;
	}
	else {
		LinkList* tail = *LL;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void PrintList(LinkList* LL)
{
	LinkList* cur = LL;
	while(cur != NULL){
		printf("%d->", cur->e);
		cur = cur->next;
	}
	printf("NULL\n");
}

void PopFront(LinkList** LL)
{
	if (*LL == NULL) {
		return;
	}
	else if ((*LL)->next == NULL) {
		free(*LL);
		*LL = NULL;
	}
	else {
		LinkList* cur = *LL;
		*LL = (*LL)->next;
		free(cur);
		cur->next = NULL;
	}
}

void PopBack(LinkList** LL) {
	if (*LL == NULL) {
		return;
	}
	else if ((*LL)->next == NULL) {
		free(*LL);
		*LL = NULL;
	}
	else {
		LinkList* cur = *LL;
		LinkList* prev = NULL;
		while (cur->next != NULL) {
			prev = cur;
			cur = cur->next;
		}
		free(cur);
		if (prev != NULL) {
			prev->next = NULL;
		}
	}
}

LinkList* SListFind(LinkList* L, ElementType x)
{
	LinkList* cur = L;
	while (cur) {
		if (cur->e == x) {
			return  cur;
		}
		else {
			cur = cur->next;
		}
	}
	return NULL;
}

void SListInsertAfter(LinkList* pos, ElementType x)
{
	assert(pos);

	LinkList* newnode = BuyNode(x);
	newnode->next =pos->next;
	pos->next = newnode;
}

void SListEraseAfter(LinkList* pos)
{
	LinkList* next = pos->next;
	if (next != NULL) {
		LinkList* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}


void destroyLinkList(LinkList** LL)
{
	LinkList* cur = *LL;
	while (cur) {
		*LL = (*LL)->next;
		free(cur);
		cur = *LL;
	}
}
//LinkList.h 带头双向循环
#pragma once
#include<stdio.h>
#include<assert.h>

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
//LinkList.c
#include"LinkList.h"

ListNode* ListCreate()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	head->_next = head;
	head->_prev = head;
	return head;
}

void ListDestory(ListNode* plist)
{
	ListNode* cur = plist->_next;
	while (cur != plist) {
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	free(plist);
}

void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->_next;
	while (cur != plist) {
		printf("%d->", cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}

void ListPushBack(ListNode* plist, LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->_data = x;
	newnode->_next = NULL;
	newnode->_prev = NULL;
	ListNode* tail = plist->_prev;
	newnode->_prev = tail;
	tail->_next = newnode;
	newnode->_next = plist;
	plist->_prev = newnode;
}

void ListPopBack(ListNode* plist)
{
	ListNode* tail = plist->_prev;
	ListNode* tail_prev = tail->_prev;
	tail_prev->_next = plist;
	plist->_prev = tail_prev;
	free(tail);
}

void ListPushFront(ListNode* plist, LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->_data = x;
	newnode->_next = NULL;
	newnode->_prev = NULL;
	ListNode* first = plist->_next;
	newnode->_next = first;
	newnode->_prev = plist;
	plist->_next = newnode;
	first->_prev = newnode;
}

void ListPopFront(ListNode* plist)
{
	ListNode* first = plist->_next;
	ListNode* second = first->_next;
	plist->_next = second;
	second->_prev = plist;
	free(first);
}

ListNode* ListFind(ListNode* plist, LTDataType x)
{
	ListNode* cur = plist;
	while (cur != plist){
		if (cur->_data == x) {
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->_data = x;
	newnode->_next = NULL;
	newnode->_prev = NULL;
	ListNode* pos_prev = pos->_prev;
	newnode->_next = pos;
	newnode->_prev = pos_prev;
	pos->_prev = newnode;
	pos_prev->_next = newnode;
}

void ListErase(ListNode* pos)
{
	ListNode* pos_prev = pos->_prev;
	ListNode* pos_next = pos->_next;
	pos_prev->_next = pos_next;
	pos_next->_prev = pos_prev;
	free(pos);
}
相关标签: c/c++