有关链表的实现(单向/双向 + 不带头/带头 + 非循环/循环)
程序员文章站
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);
}