链表——C语言

一、单项不带头

#pragma once
#include<stdio.h>
#include<stdlib.h>typedef int data;
typedef struct list
{data a;struct list* next;
}list;list* buynode(data x);void pushback(list** phead,data x);void popback(list** phead);void pushfront(list** phead, data x);void popfront(list** phead);list* find(list* head,data x);void print(list* head);//在pos之前插入
void insert1(list** pphead, list* pos,data x);//在pos之后插入
void insert2(list** ppos,data x);void erase(list** phead, list* pos);void delete(list** phead);

#include"list.h"list* buynode(data x)
{list* newnode = (list*)malloc(sizeof(list));if (newnode == NULL){perror("mallpc failure");return -1;}newnode->a = x;newnode->next = NULL;return newnode;
}void pushback(list** phead, data x)
{list* cur = *(phead);while (cur->next != NULL){cur = cur->next;}list* newnode = buynode(x);cur->next = newnode;
}void print(list* head)
{list* cur = head;while (cur != NULL){printf("%d ", cur->a);cur = cur->next;}printf("\n");
}void popback(list** phead)
{list* cur = *(phead);while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;
}void pushfront(list** phead, data x)
{list* cur = *(phead);list* newnode = buynode(x);newnode->next = cur;(*phead) = newnode;
}void popfront(list** phead)
{list* cur = *(phead);(*phead) = cur->next;free(cur);
}list* find(list* head,data x)
{list* cur = head;while ((cur->next) != NULL){if (cur->a == x){return cur;}cur = cur->next;}return NULL;
}void insert2(list** ppos, data x)
{list* newnode = buynode(x);list* cur = (*ppos)->next;(*ppos)->next = newnode;newnode->next = cur;
}void erase(list** phead, list* pos)
{list* cur = *(phead);while (cur->next != pos){cur = cur->next;}list* tmp = cur->next;cur->next = cur->next->next;free(tmp);
}void insert1(list** pphead, list* pos, data x)
{list* cur = *(pphead);while (cur->next == pos){cur = cur->next;}list* newnode = buynode(x);cur->next = newnode;newnode->next = pos;
}void delete(list** phead)
{list* cur = (*phead);list* tmp = NULL;while (cur->next != NULL){tmp = cur;cur = cur->next;free(tmp);}free(cur);
}

#include"list.h"int main()
{list* head = buynode(1);list** phead = &head;pushback(phead, 2);pushback(phead, 3);pushback(phead, 4);pushback(phead, 5);print(head);list* pos = find(head, 3);insert1(phead, pos, 10);insert2(phead, 20);print(head);delete(phead);return 0;
}

二、双向带头

#pragma once
#include<stdio.h>
#include<stdlib.h>typedef int data;
typedef struct list
{data a;struct list* prev;struct list* next;
}list;list* buynode(data x);list* init();void destory(list** pphead);void pushback(list** pphead, data x);void popback(list** pphead);void pushfront(list** pphead, data x);void popfront(list** pphead);list* find(list* phead, data x);void insert1(list** pphead, data x,list** pos);void insert2(list** pphead, data x,list** pos);void erase(list** pphead, list** pos);int size(list* phead);void print(list* phead);

#include"list.h"list* buynode(data x)
{list* newnode = (list*)malloc(sizeof(list));if (newnode == NULL){perror("malloc failure");return -1;}newnode->prev = NULL;newnode->next = NULL;newnode->a = x;return newnode;
}list* init()
{list* phead = (list*)malloc(sizeof(list));if (phead == NULL){perror("malloc failure");return -1;}phead->next = phead;phead->prev = phead;phead->a = 0;return phead;
}void destory(list** pphead)
{}void pushback(list** pphead, data x)
{list* phead = *pphead;//只含头节点if (phead->next == phead && phead->prev == phead){list* newnode = buynode(x);phead->prev = newnode;newnode->next = phead;phead->next = newnode;newnode->prev = phead;(*pphead)->a++;}//含有其他节点else{list* tail = phead->prev;list* newnode = buynode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;(*pphead)->a++;}
}void print(list* phead)
{list* cur = phead->next;while (cur != phead){printf("%d ", cur->a);cur = cur->next;}printf("\n");
}int size(list* phead)
{return phead->a;
}void popback(list** pphead)
{list* phead = *pphead;list* tail = phead->prev;tail->prev->next = phead;phead->prev = tail->prev;free(tail);(*pphead)->a--;
}void pushfront(list** pphead, data x)
{list* phead = *pphead;list* newnode = buynode(x);list* tmp = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = tmp;tmp->prev = newnode;(*pphead)->a++;
}void popfront(list** pphead)
{list* phead = *pphead;list* tmp = phead->next;phead->next = tmp->next;tmp->next->prev = phead;free(tmp);(*pphead)->a--;
}list* find(list* phead, data x)
{list* cur = phead->next;while (cur != phead){if (cur->a == x){return cur;}cur = cur->next;}return NULL;
}void insert1(list** pphead,data x, list** pos)
{list* newnode = buynode(x);list* pre = (*pos)->prev;pre->next = newnode;newnode->prev = pre;newnode->next = (*pos);(*pos)->prev = newnode;(*pphead)->a++;
}void insert2(list** pphead, data x, list** pos)
{list* newnode = buynode(x);list* nex = (*pos)->next;nex->prev = newnode;newnode->next = nex;newnode->prev = (*pos);(*pos)->next = newnode;(*pphead)->a++;
}void erase(list** pphead,list** pos)
{list* pre = (*pos)->prev;list* nex = (*pos)->next;pre->next = nex;nex->prev = pre;(*pphead)->a--;
}

#include"list.h"void test1()
{list* phead = init();list** pphead = &phead;pushback(pphead, 1);pushback(pphead, 2);pushback(pphead, 3);pushback(pphead, 4);pushback(pphead, 5);pushfront(pphead, 0);list* pos = find(phead, 3);erase(pphead, &pos);print(phead);printf("%d", size(phead));
}int main()
{test1();return 0;
}