目录
定义
在单链表的每个结点中，在设置一个指向其前驱结点的指针域，最后一个结点又指向头结点，头节点的前驱指针指向最后一个结点，从而构成一个回路。
双向链表的构建
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode *next; struct ListNode *prev; }LtNode;
初始化双链表
//初始化双链表 LtNode*ListInit() { LtNode* phead = (LtNode*)malloc(sizeof(LtNode)); phead->next = phead; phead->prev = phead; return phead; }
获得双链表节点函数
//获得双链表节点函数 LtNode* BuyListNode(LTDataType x) { LtNode* newnode = (LtNode*)malloc(sizeof(LtNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
双链表尾插建表
void ListPushBack(LtNode* phead) { assert(phead); LTDataType x; while (1) { scanf("%d", &x); if (x == -1) break; ListNode* newnode = BuyListNode(x); phead->prev->next = newnode; newnode->prev = phead->prev; newnode->next = phead; phead->prev = newnode; } }
打印双链表
void ListPrint(LtNode* phead) { assert(phead); LtNode* p = phead->next; while (p!= phead) { printf("%d ", p->data); p = p->next; } }
查找双链表节点
LtNode* FindNode(LtNode*phead,int x) { LtNode* p = phead->next; while (x>1 && p != phead) { p = p->next; x--; } if (p == phead)//查找节点不存在 { return NULL; } else return p; }
双链表删除节点
void ListDel(LtNode*phead) { printf("您要删除第几个数据："); int k; scanf("%d",&k); if (k == 1) { LtNode* p = phead->next; p->prev->next = p->next; p->next->prev = p->prev; free(p); return; } LtNode* p = FindNode(phead,k); p->prev->next = p->next; p->next->prev = p->prev; free(p); }
双链表插入节点
void ListInsert(LtNode*phead) { printf("您要在第几个数据前插入："); int k; scanf("%d", &k); printf("请输入你要插入的数据："); int data; scanf("%d", &data); LtNode* newnode = BuyListNode(data); if (k == 1) { LtNode* p = phead->next; p->prev->next = newnode; newnode->prev = p->prev; newnode->next = p; p->prev = newnode; return; } LtNode* p = FindNode(phead, k); p->prev->next = newnode; newnode->prev = p->prev; newnode->next = p; p->prev = newnode; }
双链表销毁
void ListDistory(LtNode*phead) { LtNode* p = phead->next; LtNode* q = NULL; while (q!=phead) { q = p->next; free(p); p = q; } free(phead); }
