c语言 双向链表的基础操作
程序员文章站
2022-03-08 23:10:34
//头文件
#pragma once
typedef int datatype;
typedef struct linklist
{
datatype _data;...
//头文件 #pragma once typedef int datatype; typedef struct linklist { datatype _data; struct linklist* _next; struct linklist* _prev; }linklist,*plinklist; void initlist(plinklist pnode); plinklist _buynode(plinklist& pnode,datatype x); void printlist(plinklist phead); void pushback(plinklist& phead,datatype x); void popback(plinklist& phead); void pushfront(plinklist& phead,datatype x); void popfront(plinklist& phead); plinklist find(plinklist phead, datatype x); void insert(plinklist pos,datatype x); void erase(plinklist& phead, plinklist pos); void reverse(plinklist& phead); void destroylist(plinklist& phead); //函数文件 #include<stdio.h> #include<assert.h> #include"linklist.h" #include<malloc.h> //初始化 void initlist(plinklist pnode) { assert(pnode); if (pnode->_next == null) { pnode->_prev = null; } } //创建节点 plinklist _buynode(plinklist& pnode, datatype x) { pnode = (plinklist)malloc(sizeof(linklist)); pnode->_data = x; pnode->_next = null; pnode->_prev = null; return pnode; } //遍历输出链表数据域 void printlist(plinklist phead) { plinklist head = phead; if(phead == null) { printf("链表为空!\n"); return; } while (head) { printf("%d ",head->_data); head = head->_next; } printf("\n"); } //尾插 void pushback(plinklist& phead, datatype x) { plinklist head = phead; if (head == null) { _buynode(phead, x); return; } while (head->_next) { head = head->_next; } head->_next = _buynode(head->_next,x); head->_next->_prev = head; } //尾删 void popback(plinklist& phead) { plinklist head = phead; plinklist tmp = null; if (phead == null) { printf("链表已空!\n"); return; } if (head->_next == null) { free(head); phead = null; return; } while (head->_next) { head = head->_next; } tmp = head->_prev; tmp->_next = null; free(head); } //头插 void pushfront(plinklist& phead, datatype x) { plinklist head = phead; plinklist tmp = phead; if (phead == null) { _buynode(phead, x); return; } phead=_buynode(head->_prev, x); phead->_next = tmp; } //头删 void popfront(plinklist& phead) { plinklist tmp = phead; if (phead == null) { printf("链表已空!\n"); return; } phead = phead->_next; if (phead) { phead->_prev = null; } free(tmp); } //查找 plinklist find(plinklist phead, datatype x) { plinklist head = phead; assert(phead); while (head) { if (head->_data == x) return head; head = head->_next; } return null; } //中插_之后 void insert(plinklist pos, datatype x) { plinklist tmp = pos->_next; assert(pos); _buynode(pos->_next, x); pos->_next->_prev = pos; pos->_next->_next = tmp; } //中删 void erase(plinklist& phead, plinklist pos) { plinklist tmp = pos; assert(pos); if (pos->_next == null) { pos->_prev->_next = null; free(tmp); return; } if (pos==phead) { phead = phead->_next; phead->_prev = null; free(pos); return; } tmp->_prev->_next = tmp->_next; tmp->_next->_prev = tmp->_prev; free(pos); } //逆置 void reverse(plinklist& phead) { plinklist head = phead; plinklist tmp = phead; if (phead == null&&phead->_next == null) return; while (head) { tmp = head->_next; head->_next = head->_prev; head->_prev = tmp; if (head->_prev == null) phead = head; head = tmp; } } //销毁 void destroylist(plinklist& phead) { while (phead) { popfront(phead); } } //测试用例 主函数 #include"linklist.h" #include<stdio.h> void test1() { plinklist phead=null; //pushback(phead, 1); //pushback(phead, 2); //pushback(phead, 3); // pushback(phead, 4); //pushback(phead, 5); //printlist(phead); //popback(phead); //popback(phead); //popback(phead); //popback(phead); //popback(phead); //popback(phead); pushfront(phead, 1); pushfront(phead, 2); pushfront(phead, 3); pushfront(phead, 4); pushfront(phead, 5); printlist(phead); //popfront(phead); //popfront(phead); //popfront(phead); //popfront(phead); //popfront(phead); //popfront(phead); //printf("%d\n",find(phead, 6)); insert(find(phead, 1), 6); erase(phead,find(phead,2)); printlist(phead); reverse(phead); printlist(phead); destroylist(phead); printlist(phead); } int main() { test1(); return 0; }