首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:19:48来源：未知阅读 ()

双向循环链表

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

一个环。在双向循环链表的结点中有两个指针域，其中一个指向直接后继，另一个指向直接前趋。因此数据结构为：

#define ElemType int
typedef 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）头插法

向双向循环链表中进行插入数据元素.（4）展示双向循环链表的内容.（5）对双向循环链表进行尾部删除元素操作.（6）

按值向双向循环链表进行插入元素操作.（7）按值进行对双向循环链表的删除操作.（8）在双向循环链表进行按值进行

查找数据元素操作.（9）清除双向循环链表的数据元素操作.（10）摧毁双向循环链表.（11）逆置双向循环链表的数据

元素的操作.

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

#ifndef _DCLIST_H
#define _DCLIST_H

#include<iostream>
#include<assert.h>
using namespace std;

#define ElemType int
typedef 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;
}