数据结构双向链表C++实现

创建一个cpp文件代码如下就可以实现双向链表的基本操作了（熬夜使我脱发，呜呜呜，代码使我入迷）

#include <iostream> #include <stdio.h> #include <stdlib.h> #define OVERFLOW -3 #define true 1 #define false 0 #define ok 1 #define error -1 using namespace std; typedef struct DuLNode { int data; struct DuLNode *prior; struct DuLNode *next; } * DuLinkList; //产生空的双向循环链表 void InitList(DuLinkList &L) { L = (DuLinkList)malloc(sizeof(DuLNode)); if (L) L->next = L->prior = L; else exit(OVERFLOW); } //销毁双向循环链表 void DestroyList(DuLinkList &L) { DuLNode *q, *p = L->next; //p指向第一个节点 while (p != L) //p还未达到表头 { q = p->next; free(p); p = q; } free(L); L = NULL; } //将L置为空表 void ClearList(DuLNode *L) { DuLNode *q, *p = L->next; while (p != L) { q = p->next; free(p); p = q; } L->next = L->prior = L; //头节点的两个指针域均指向自身 } //是空表返回1不是返回0 int ListEmpty(DuLNode *L) { if (L->next == L && L->prior == L) return true; else return false; } //返回表长度 int ListLength(DuLNode *L) { int i = 0; DuLNode *p = L->next; while (p != L) { i++; p = p->next; } return i; } //得到指定位置上的元素，赋值给e然后返回 int GetElem(DuLNode *L, int i, int &e) { int j = 1; DuLNode *p = L->next; while (p != L && j < i) //指针向后查找，直至找到第i个元素或者是p指向表头 { p = p->next; j++; } if (p == L || j < i) return error; e = p->data; return ok; } //判断指定元素是否在链表中，在的话返回位置 int LocateElem(DuLNode *L, int e) { int i = 0; DuLNode *p = L->next; //指向链表第一个节点位置 while (p != L) { i++; if (p->data == e) //对比找到这个位置 return i; p = p->next; } return 0; } //返回给定元素前面一个位置的元素 int PriorElem(DuLNode *L, int cur, int &pre) { DuLNode *p = L->next->next; //p指向第二个节点 while (p != L) //p不到表头的时候 { if (p->data == cur) { pre = p->prior->data; return true; } p = p->next; } return false; } //返回给定元素位置的下一个位置的元素 int NextElem(DuLNode *L, int cur, int &next) { DuLNode *p = L->next->next; //p指向第二个元素 while (p != L) //p未到表头 { if (p->prior->data == cur) { next = p->data; return true; } p = p->next; } return false; } //返回指定位置的地址 DuLinkList GetElemP(DuLNode *L, int i) { int j; DuLNode *p = L; //p指向表头 if (i < 0 || i > ListLength(L)) //i值不合法 return NULL; for (j = 1; j <= i; j++) p = p->next; return p; } //在链表指定位置插入元素 int ListInsert(DuLNode *L, int i, int e) { DuLNode *p, *s; if (i < 0 || i > ListLength(L) + 1) return error; p = GetElemP(L, i - 1); //指定位置的前驱指针 if (!p) return error; s = (DuLNode *)malloc(sizeof(DuLNode)); if (!s) return OVERFLOW; s->data = e; s->prior = p; //在i-1个元素之后插入 s->next = p->next; p->next->prior = s; p->next = s; return ok; } //删除带头节点的链表的第i个位置的元素 int ListDelete(DuLNode *L, int i, int &e) { DuLNode *p; if (i < 1) return ok; p = GetElemP(L, i); //确定第i个位置的元素指针p if (!p) return error; e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return ok; } //正向遍历链表 void ListTraverse(DuLNode *L) { DuLNode *p = L->next; //指向头节点 while (p != L) { cout << p->data << " "; p = p->next; } cout << endl; } //反向遍历链表 void ListTraverseBack(DuLNode *L) { DuLNode *p = L->prior; //指向尾节点 while (p != L) { cout << p->data << " "; p = p->prior; } cout << endl; } int main() { DuLNode *L; int i, n, j, e; InitList(L); for (i = 1; i <= 5; i++) ListInsert(L, i, i); cout << "output the list in Positive sequence:"; ListTraverse(L); cout << endl; cout << "output the list in The reverse:"; ListTraverseBack(L); cout << endl; n = 2; ListDelete(L, n, e); cout << "delete the " << n << "th and it worth:" << e << " the teft is:"; ListTraverse(L); cout << endl; cout << "the length of list is:" << ListLength(L) << endl; cout << "whether the list is empty or not(1:yes 0:no):" << ListEmpty(L) << endl; ClearList(L); cout << "after clear up whether the list is empty or not(1:yes 0:no):" << ListEmpty(L) << endl; for (i = 1; i <= 5; i++) { ListInsert(L, i, i); } ListTraverse(L); n = 3; j = GetElem(L, n, e); if (j) cout << "the " << n << "th of the list is:" << e << endl; else cout << "the nmber do not exit" << endl; n = 4; i = LocateElem(L, n); if (i) cout << "the " << n << "th of the list is:" << i << endl; else cout << "the nmber do not exit" << endl; j = PriorElem(L, n, e); if (j) cout << "the number before" << n << " is:" << e << endl; else cout << "the nmber do not exit" << endl; j = NextElem(L, n, e); if (j) cout << "the number after" << n << " is:" << e << endl; else cout << "the nmber do not exit" << endl; DestroyList(L); system("pause"); }

结果如下