# 数据结构之线性表（双向循环链表）

2018-01-30 19:19:24来源:cnblogs.com作者:XNQC人点击

1.定义：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成

`#define ElemType inttypedef struct ListNode{    ElemType data;    ListNode *prio;    ListNode *next;}ListNode;typedef struct List{    ListNode *first;    ListNode *last;    size_t    size;}List;`

2.因此在双向循环链表中有以下操作：

`void InitList(List *list);bool push_back(List *list, ElemType x);bool push_front(List *list, ElemType x);void showList(List *list);void pop_back(List *list);bool insert_val(List *list, ElemType x);bool delete_val(List *list, ElemType key);ListNode* find_key(List *list, ElemType key);void clear_list(List *list);void destroy_list(List *list);void reverse_list(List *list);`

以上声明的方法有：（1）初始化一个双向循环链表.（2）尾插法向双向循环链表中进行插入数据元素.（3）头插法

3.将上面声明的方法在DCList.h的头文件中进行实现：

`#ifndef _DCLIST_H#define _DCLIST_H#include<iostream>#include<assert.h>using namespace std;#define ElemType inttypedef struct ListNode{    ElemType data;    ListNode *prio;    ListNode *next;}ListNode;typedef struct List{    ListNode *first;    ListNode *last;    size_t    size;}List;void InitList(List *list);bool push_back(List *list, ElemType x);bool push_front(List *list, ElemType x);void showList(List *list);void pop_back(List *list);bool insert_val(List *list, ElemType x);bool delete_val(List *list, ElemType key);ListNode* find_key(List *list, ElemType key);void clear_list(List *list);void destroy_list(List *list);void reverse_list(List *list);void InitList(List *list){    ListNode *s = (ListNode*)malloc(sizeof(ListNode));    assert(s != NULL);    list->first = list->last = s;    list->first->prio = list->last;    list->last->next = list->first;    list->size = 0;}bool push_back(List *list, ElemType x){    ListNode *s = (ListNode*)malloc(sizeof(ListNode));    if (s == NULL)        return false;    s->data = x;    list->last->next = s;    s->prio = list->last;    list->last = s;    list->last->next = list->first;    list->first->prio = list->last;    list->size++;    return true;}bool push_front(List *list, ElemType x){    ListNode *s = (ListNode*)malloc(sizeof(ListNode));    if (s == NULL)        return false;    s->data = x;    s->next = list->first->next;    s->next->prio = s;    s->prio = list->first;    list->first->next = s;    if (list->last == list->first)        list->last = s;    list->size++;    return true;}void pop_back(List *list){    if (list->size == 0)        return;    ListNode *p = list->first;    while (p->next != list->last)        p = p->next;    ListNode *s = p->next;    s->next->prio = s->prio;    s->prio->next = s->next;    free(list->last);    list->last = p;    list->size--;}void showList(List *list){    ListNode *p = list->first->next;    while (p != list->first)    {        cout << p->data << "-->";        p = p->next;    }    cout << "Over." << endl;}ListNode* find_key(List *list, ElemType key){    if (list->size == 0)        return NULL;    ListNode *p = list->first->next;    while (p != list->first && p->data != key)        p = p->next;    if (p == list->first)        return NULL;    return p;}bool delete_val(List *list, ElemType key){    ListNode *p = find_key(list, key);    if (p == NULL)        return false;    p->next->prio = p->prio;    p->prio->next = p->next;    if (p == list->last)        list->last = p->prio;    free(p);    list->size--;    return true;}bool insert_val(List *list, ElemType x){    ListNode *p = list->first->next;    while (p != list->first && x>p->data)        p = p->next;    ListNode *s = (ListNode*)malloc(sizeof(ListNode));    if (s == NULL)        return false;    s->data = x;    s->next = p;    s->prio = p->prio;    p->prio->next = s;    p->prio = s;    if (p == list->first)        list->last = s;    list->size++;    return true;}void clear_list(List *list){    if (list->size == 0)        return;    ListNode *p = list->first->next;    while (p != list->first)    {        list->first->next = p->next;        p->next->prio = p->prio;        free(p);        p = list->first->next;    }    list->last = list->first;    list->size = 0;}void destroy_list(List *list){    clear_list(list);    free(list->first);    list->first = list->last = NULL;}void reverse_list(List *list){    if (list->size <= 1)        return;    ListNode *p = list->first->next;    ListNode *q = p->next;    ListNode *s = p;    while (q != list->first)    {        p = q;        q = p->next;        p->next = list->first->next;        p->next->prio = p;        p->prio = list->first;        list->first->next = p;    }    list->last = s;    list->last->next = list->first;}`

4.将上面所实现的方法在主函数中调用实现：

`#include <iostream>#include "DCList.h"using namespace std;int main(){    List mylist;    InitList(&mylist);    ListNode *p = NULL;    ElemType item;    int pos;    int select = 1;    while (select)    {        cout << "******************************************" << endl;        cout << "*[1] push_back       [2] push_front      *" << endl;        cout << "*[3] showList        [4] pop_back        *" << endl;        cout << "*[5] insert_val      [6] delete_val      *" << endl;        cout << "*[7] find_key        [8] reverse_list    *" << endl;        cout << "*[9] clear_list      [0] quit_system     *" << endl;        cout << "******************************************" << endl;        cout << "请选择:>";        cin >> select;        switch (select)        {        case 1:            cout << "请输入要插入的数据(-1结束):>";            while (cin >> item, item != -1)     //逗号表达式            {                push_back(&mylist, item);            }            break;        case 2:            cout << "请输入要插入的数据(-1结束):>";            while (cin >> item, item != -1)            {                push_front(&mylist, item);            }            break;        case 3:            showList(&mylist);            break;        case 4:            pop_back(&mylist);            break;        case 5:            cout << "请输入要插入的值:>";            cin >> item;            insert_val(&mylist, item);            break;        case 6:            cout << "请输入要删除的值:>";            cin >> item;            delete_val(&mylist, item);            break;        case 7:            cout << "请输入要查找的值:>";            cin >> item;            p = find_key(&mylist, item);            if (p == NULL)            {                cout << "要查找的值:" << item << "不存在!" << endl;            }            break;        case 8:            reverse_list(&mylist);            break;        case 9:            clear_list(&mylist);            break;        }        system("pause");        system("cls");    }    destroy_list(&mylist);    return 0;}`