双向链表的实现

编程技术  /  houtizong 发布于 3年前   40

#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;}