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

链表的实现

发表于: 2013-04-27   作者:chinrui   来源:转载   浏览次数:
摘要: #include <iostream> #include <stdlib.h> using namespace std; typedef struct lNode { lNode *lNext; int data; } lNode , *LinkedList; //函数声明 LinkedList initNode(); void
#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;
    }
}

链表的实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
JavaScript 本身提供了十分好用的数据类型,以满足大家的日常使用。单靠 Array 和 Object 也的确足
本文会记录一些linux内核实现中使用到的一些小技巧,工具等等,会根据学习进度不定时更新本文......
本文会记录一些linux内核实现中使用到的一些小技巧,工具等等,会根据学习进度不定时更新本文......
任务描述 :前几个的实现是线性表的基本操作 现在实现的是链表基本操作的实现。基本上是建立新结点
//利用链表构建栈。 //输入1 2 3 4 5 0时输出 5 4 3 2 1 #include<stdio.h> #include<stdl
package nodelist; public class LinkNode { public Object data;//节点内的数据对象 public LinkNo
前提:链表结点结构体: typedef struct node { ElemType data; node *next; }Node; 1、最初设想:
1 #include <stdio.h> 2 #include <malloc.h> 3 #define LEN sizeof(struct student) 4
链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较
1、像堆栈一样,也可以使用链表来实现一个队列。此时需要两个变量 f r o n t和r e a r来分别跟踪队
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号