链表的实现

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

#include <iostream>#include <stdlib.h>using namespace std;typedef struct lNode {    lNode *lNext;    int data;} lNode , *LinkedList;//函数声明LinkedList initNode();void showNodes(LinkedList head);int getLength(LinkedList);int main(){    //初始化头结点    LinkedList lHead = initNode();    int arr[100];    int length;    cout << "输入您要建立链表的长度：" << endl;    cin >> length;    cout << "输入您建立链表的各个结点值：" << endl;    for(int i = 0; i < length ; i++) {        cin >> arr[i];    }    //测试尾插法初始化链表    //void initLinkedListAtLast(LinkedList , int , int[]);    //initLinkedListAtLast(lHead , length , arr);    //测试头插法初始化链表    void initLinkedListAtHead(LinkedList , int , int[]);    initLinkedListAtHead(lHead , length , arr);    //插入测试    /*void insertNode(LinkedList head , LinkedList node , int index);    int iInsertIndex;    int iInsertValue;    cout << "插入前链表中所有元素的值为：" << endl;    showNodes(lHead);    cout << "请输入您要插入的元素值 ：" << endl;    cin >> iInsertValue;    LinkedList lInsert = initNode();    lInsert->data = iInsertValue;    lInsert->lNext = NULL;    cout << "请输入您要插入元素的位置，不小于 1，不大于" << getLength(lHead) + 1 << "：" << endl;    cin >> iInsertIndex;    insertNode(lHead , lInsert , iInsertIndex);    cout << "插入后链表里面的元素值为：" << endl;    showNodes(lHead);*/    //测试删除    /*void deleteNode(LinkedList , int);    int iDeleteIndex;    cout << "删除前链表中所有元素的值为：" << endl;    showNodes(lHead);    cout << "请输入要删除元素的地址值，不小于 1，不大于 " << getLength(lHead) << "：" << endl;    cin >> iDeleteIndex;    deleteNode(lHead , iDeleteIndex);    cout << "删除后链表里面的元素值为 ：" << endl;    showNodes(lHead);*/    //测试查找    /*LinkedList getNode(LinkedList , int);    int iSearchIndex;    cout << "当前链表中所有元素结点的值为：" << endl;    showNodes(lHead);    cout << "请输入您要查找元素的地址值，不小于 1，不大于 " << getLength(lHead) << "：" << endl;    cin >> iSearchIndex;    LinkedList lResult = getNode(lHead , iSearchIndex);    if(lResult != NULL) {        cout << "所查找到的元素值为：" << lResult->data << endl;    }*/    //测试修改    /*void changeNodeValue(LinkedList , int , int);    int iChangeIndex, iChangeValue;    cout << "修改前链表中所有元素结点的值：" << endl;    showNodes(lHead);    cout << "请输入您要修改结点的值：" << endl;    cin >> iChangeValue;    cout << "请输入您要修改结点的地址值：" << endl;    cin >> iChangeIndex;    changeNodeValue(lHead , iChangeIndex , iChangeValue);    cout << "修改后链表里面的元素值为：" << endl;    showNodes(lHead);*/    //测试链表的合并    /*LinkedList mergeLinkedList(LinkedList , LinkedList);    cout << "第一个链表的所有元素值为：" << endl;    showNodes(lHead);    LinkedList mergeList = initNode();    LinkedList lSecond = initNode();    initLinkedListAtHead(lSecond , 20);    cout << "第二个链表的所有元素值为：" << endl;    showNodes(lSecond);    mergeList = mergeLinkedList(lHead , lSecond);    cout << "合并后的链表的所有元素值为：" << endl;    showNodes(mergeList);*/    //测试链表的逆转    void reverseLinkedList(LinkedList , LinkedList);    cout << "逆转前的链表的所有元素值为：" << endl;    showNodes(lHead);    //LinkedList lResult2 = initNode();    //reverseLinkedList(lHead , lResult2);    void reverseList(LinkedList);    reverseList(lHead);    cout << "逆转后的链表的所有元素值为：" << endl;    //showNodes(lResult2);    showNodes(lHead);    //cout << "链表的长度为：" << getLength(lHead) << endl;    return 0;}//初始化结点LinkedList initNode() {    //初始化结点，分配适当的内存空间    LinkedList node = (LinkedList)(malloc(sizeof(lNode)));    return node;}//初始化链表(尾插法)void initLinkedListAtList(LinkedList lHead , int lSize , int arr[]) {    LinkedList curr = lHead;    LinkedList initNode();    //初始化长度为iSize的链表，取值以步长为1递增    for(int i = 0; i < lSize ; i ++) {        LinkedList lInsert = initNode();        lInsert->data = arr[i];        lInsert->lNext = NULL;        curr->lNext = lInsert;        curr = curr->lNext;    }}//初始化链表(头插法)void initLinkedListAtHead(LinkedList lHead , int iSize , int arr[]) {    LinkedList curr = lHead;    curr->lNext = NULL;    //声明生成结点的函数    LinkedList initNode();    //在当前指针    for(int i = 0; i < iSize; i++) {        LinkedList lInsert = initNode();        lInsert->data = arr[i];        lInsert->lNext = curr->lNext;        curr->lNext = lInsert;    }}//获得链表的长度int getLength(LinkedList lHead) {    LinkedList curr = lHead;    int length = 0;    while(curr->lNext != NULL) {        length++;        curr = curr->lNext;    }    return length;}//展示所有结点void showNodes(LinkedList head) {    while(head->lNext != NULL) {        head = head->lNext;        cout << head->data << " ";    }    if(head->lNext == NULL)        cout << endl;}//插入结点void insertNode(LinkedList head , LinkedList node , int index) {    //判断脚标是否越过下界    if(index <= 0) {        cout << "插入失败！您要插入的位置不存在！" << endl;        return;    }    //移动指针到插入脚标的前一个结点    LinkedList curr = head;    for(int i = 0; i < index - 1; i++) {        if(curr->lNext != NULL) {            curr = curr->lNext;        } else {            cout << "插入失败！您要插入的位置不存在！" << endl;            return;        }    }    //插入结点    node->lNext = curr->lNext;    curr->lNext = node;}//删除结点void deleteNode(LinkedList head , int index) {    //判断脚标是否越过下界    if(index <= 0) {        cout << "删除失败！您要删除的结点不存在！" << endl;        return;    }    //移动结点到要删除元素的前一位    LinkedList curr = head;    for(int i = 0; i < index - 1; i ++) {        if(curr->lNext != NULL) {            curr = curr->lNext;        } else {            cout << "删除失败！您要删除的结点不存在！" << endl;            return;        }    }    if(curr->lNext == NULL) {        cout << "删除失败！您要删除的结点不存在！" << endl;        return;    }    //删除元素并释放空间    LinkedList dNode = curr->lNext;    curr->lNext = dNode->lNext;    free(dNode);}//查找元素LinkedList getNode(LinkedList head , int index) {     //判断脚标是否越过下界    if(index <= 0) {        cout << "您要查找的结点不存在！" << endl;        return NULL;    }    LinkedList curr = head;    for(int i = 0; i < index ; i++) {        if(curr->lNext != NULL) {            curr = curr->lNext;        } else {            cout << "您要查找的结点不存在！" << endl;            return NULL;        }    }    return curr;}//修改结点值void changeNodeValue(LinkedList head , int index , int value) {     //判断脚标是否越过下界    if(index <= 0) {        cout << "您要修改的结点不存在！" << endl;        return;    }    //移到指针到要修改的结点处    LinkedList curr = head;    for(int i = 0; i < index ; i++) {        if(curr->lNext != NULL) {            curr = curr->lNext;        } else {            cout << "您要修改的结点不存在！" << endl;            return;        }    }    //修改结点值    curr->data = value;}//合并两个有序链表LinkedList mergeLinkedList(LinkedList la , LinkedList lb) {    LinkedList laCurr = la->lNext;    LinkedList lbCurr = lb->lNext;    LinkedList lcCurr = la;    //LinkedList lc = lcCurr;  //课本上设置的这个变量完全是多余的，可以去掉    while(laCurr != NULL && lbCurr != NULL) {        if(laCurr->data >= lbCurr->data){            lcCurr->lNext = lbCurr;            lcCurr = lcCurr->lNext;            lbCurr = lbCurr->lNext;        } else {            lcCurr->lNext = laCurr;            lcCurr = lcCurr->lNext;            laCurr = laCurr->lNext;        }    }    lcCurr->lNext = laCurr ? laCurr : lbCurr;    free(lb);    //return lc;    return la;}//逆转链表void reverseLinkedList(LinkedList lHead , LinkedList iResult) {    //如果传入的只是个头指针，则退出运算    if(lHead->lNext == NULL) {        free(lHead);        return;    }    //找到倒数第二个元素结点    LinkedList tail = lHead;    //int length = 0;    while(tail->lNext->lNext != NULL) {        tail = tail->lNext;        //length ++;    }    //让返回的LinkedList指针，指向传入LinkedList的最后一个元素结点    iResult->lNext = tail->lNext;    //把倒数第二个结点设成倒数第一个结点    tail->lNext = NULL;    //递归调用函数    reverseLinkedList(lHead , iResult->lNext);    //cout << tail->data << "  " << length << endl;}//头插法进行逆转void reverseList(LinkedList lHead) {    LinkedList list1 , list2;    //记录第二个结点    list1 = list2 = lHead->lNext->lNext;    lHead->lNext->lNext = NULL;    //将第二个结点及以后的所有结点依次插入头结点之后    while(list1 != NULL) {        list2 = list2->lNext;        list1->lNext = lHead->lNext;        lHead->lNext = list1;        list1 = list2;    }}