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

双向链表的实现

发表于: 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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号