当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

双向链表的实现

发表于: 2013-04-27   作者:chinrui   来源:转载   浏览次数:
摘要: #include <iostream> #include <stdlib.h> using namespace std; typedef int Elemtype; typedef struct lNode { Elemtype data; struct lNode *prior; struct lNode *next; }
#include <iostream>
#include <stdlib.h>

using namespace std;

typedef int Elemtype;
typedef struct lNode {
    Elemtype data;
    struct lNode *prior;
    struct lNode *next;
} *LinkedList;

//函数声明
LinkedList initNode();
void showNodesInClockwise(LinkedList);
void showNodesInAnticlockwise(LinkedList);
void initLinkedList(LinkedList , int);
int getLength(LinkedList);

int main()
{
    LinkedList lHead = initNode();
    lHead->next = lHead;
    lHead->prior = lHead;
    cout << "输入要建立链表的长度:" << endl;
    int length;
    cin >> length;
    cout << "输入要建立链表的数据值,共" << length << "个数 :" << endl;
    initLinkedList(lHead , length);

    //测试插入
    void insertNode(LinkedList , int , Elemtype);
    int iInsertIndex;
    cout << "请输入要插入的地址:" << endl;
    cin >> iInsertIndex;
    Elemtype eInsertValue;
    cout << "请输入要插入的值:" << endl;
    cin >> eInsertValue;
    insertNode(lHead , iInsertIndex , eInsertValue);

    //测试删除
    /*LinkedList deleteNode(LinkedList , int);
    int iDeleteIndex;
    cout << "请输入要删除的地址值,不小于1,不大于" << getLength(lHead) << ":" << endl;
    cin >> iDeleteIndex;
    lHead = deleteNode(lHead , iDeleteIndex);*/

    //测试修改
    /*void modifyNode(LinkedList , int , Elemtype);
    cout << "输入要更新结点的地址值,不小于1,不大于" << getLength(lHead) << ":" << endl;
    int iModifyIndex;
    cin >> iModifyIndex;
    cout << "输入要更新的结点值:" << endl;
    Elemtype iModifyValue;
    cin >> iModifyValue;
    modifyNode(lHead , iModifyIndex , iModifyValue);*/

    //测试查找
    /*Elemtype searchNode(LinkedList , int);
    Elemtype eSearchResult;
    cout << "输入要查找的结点的地址值:" << endl;
    int iSearchIndex;
    cin >> iSearchIndex;
    eSearchResult = searchNode(lHead , iSearchIndex);
    cout << "链表中地址值为" << iSearchIndex << "的结点值为:" << endl;
    cout << eSearchResult << endl;*/


    cout << "顺序输出链表里面的结点值:" << endl;
    showNodesInClockwise(lHead);
    //cout << "逆序输出链表里面的值:" << endl;
    //showNodesInAnticlockwise(lHead);

    //获得链表长度测试
    //cout << getLength(lHead) << endl;
    return 0;
}

//初始化结点
LinkedList initNode() {
    return (LinkedList)malloc(sizeof(lNode));
}

//链表展示
void showNodesInClockwise(LinkedList head) {
    cout << head->data << " ";
    LinkedList lCurr = head->next;
    while(lCurr != head) {
        cout << lCurr->data << " ";
        lCurr = lCurr->next;
    }
    cout << endl;
}

void showNodesInAnticlockwise(LinkedList head) {
    LinkedList lCurr = head->prior;
    while(lCurr != head) {
        cout << lCurr->data << " ";
        lCurr = lCurr->prior;
    }
    cout << head->data << endl;
}

//尾插法初始化链表
void initLinkedList(LinkedList head , int iSize) {
    LinkedList lCurr = head;
    cin >> lCurr->data;
    for(int i = 1; i < iSize; i++) {
        LinkedList lNew = initNode();
        cin >> lNew->data;
        lNew->next = head;
        head->prior = lNew;
        lCurr->next = lNew;
        lNew->prior = lCurr;
        lCurr = lNew;
    }
}

int getLength(LinkedList head) {
    int length = 1;
    LinkedList lCurr = head->next;
    while(lCurr != head) {
        length++;
        lCurr = lCurr->next;
    }
    return length;
}

//向链表中插入相应的数据
void insertNode(LinkedList head , int index , Elemtype value) {
    LinkedList lCurr = head;
    //判断插入地址的合法性
    if(index <= 0 || index > getLength(head) + 1) {
        cout << "插入的地址不存在!" << endl;
        return;
    }
    //移动到要插入的位置
    for(int i = 1; i < index; i++) {
        lCurr = lCurr->next;
    }
    //生成新的结点并插入
    LinkedList lNew = initNode();
    lNew->data = value;
    lNew->prior = lCurr->prior;
    lCurr->prior->next = lNew;
    lNew->next = lCurr;
    lCurr->prior = lNew;
}

//删除链表中的元素
LinkedList deleteNode(LinkedList head , int index) {
    LinkedList lResult = head;
    LinkedList lCurr = head;
    //判断插入地址的合法性
    if(index <= 0 || index > getLength(head)) {
        cout << "要删除的地址不存在!" << endl;
        return lResult;
    }
    //移动到要插入的位置
    for(int i = 1; i < index; i++) {
        lCurr = lCurr->next;
    }
    lCurr->prior->next = lCurr->next;
    lCurr->next->prior = lCurr->prior;
    lResult = lCurr->next;
    free(lCurr);
    return lResult;
}

//修改链表中的结点值
void modifyNode(LinkedList head , int index , Elemtype value) {
    //判断插入地址的合法性
    if(index <= 0 || index > getLength(head)) {
        cout << "要修改的地址不存在!" << endl;
        return;
    }
    //移动到要插入的位置
    for(int i = 1; i < index; i++) {
        head = head->next;
    }
    head->data = value;
}

//查找结点值
Elemtype searchNode(LinkedList head , int index) {
    //判断插入地址的合法性
    if(index <= 0 || index > getLength(head)) {
        cout << "查找的结点不存在!" << endl;
        return -1;
    }
    //移动到要插入的位置
    for(int i = 1; i < index; i++) {
        head = head->next;
    }
    return head->data;
}

双向链表的实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
实现双向链表的任意遍历打印,涉及到双向链表和递归调用。本这段代码一共实现了5中遍历打印的方法,
概要 前面一章"介绍双向链表并给出了C/C++/Java三种实现",本章继续对双向链表进行探讨,介绍的内容
一、双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双
双向链表 2015-04-04 Lover雪儿 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #def
双向链表 在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指
基本上,我们可以认为双向链表是单链表的一个改进。这个改进一个有益的地方就是,双链表不必像单链
一、双向链表说明: 1. 以前所遇到的链表都只提供了从前向后遍历数组的功能,而双向链表提供了从最
一、双向链表说明: 1. 以前所遇到的链表都只提供了从前向后遍历数组的功能,而双向链表提供了从最
概要 线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列。本章先介绍线性
学校数据结构的课程实验之一。 用到的数据结构:双向链表 主要功能:对由用户输入的两个任意长的整
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号