链表的实现

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