课程咨询 :0571-56020834 QQ:3163902815

杭州软件测试培训

杭州软件测试培训 > 达内新闻 > 达内:C++实现链表的基本操作及测试用例
  • 达内:C++实现链表的基本操作及测试用例

    发布:杭州软件测试培训      来源:51测试网      时间:2016-01-13


  •     杭州达内软件测试培训专家讲解如何实现下链表的基本操作,包括节点的创建,头插尾插,头删尾删,一次遍历寻找链表的中间节点,寻找链表的倒数第x个节点,删除无头链表的非尾节点,链表的逆置。代码如下:

    #include "SLinkList.h"
    #include <stdlib.h>
    #include <stdio.h>
    #include <assert.h>
    void PrintList(SListNode* pHead)//从指针位置打印链表
    {
    while (pHead)
    {
    printf("->%d", pHead->data);
    pHead = pHead->next;
    }
    printf("\n");
    }
    static SListNode* _BuyNode(DataType x)//创建新的节点
    {
    SListNode*ret = (SListNode*)malloc(sizeof(SListNode));
    ret->next = NULL;
    ret->data = x;
    if (ret)
    {
    return ret;
    }
    printf("创建节点失败\n");//创建失败给出提示
    return NULL;
    }
    void PushBack(SListNode* & pHead, DataType x)//尾插
    {
    if (pHead == NULL)
    {
    pHead = _BuyNode(x);
    }
    else
    {
    SListNode*tail = pHead;
    while (tail->next)
    {
    tail = tail->next;
    }
    tail->next = _BuyNode(x);
    }
    }
    void PopBack(SListNode* & pHead)//尾删
    {
    if (pHead == NULL)
    {
    return;
    }
    else if (pHead->next->next == NULL)
    {
    free(pHead->next);
    pHead = NULL;
    }
    else
    {
    SListNode* tail = pHead;
    while (tail->next->next)
    {
    tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
    }
    }
    void PushFront(SListNode* & pHead, DataType x)//头插
    {
    if (pHead == NULL)
    {
    pHead = _BuyNode(x);
    }
    else
    {
    SListNode*tmp = _BuyNode(x);
    tmp->next = pHead;
    pHead = tmp;
    }
    }
    void PopFront(SListNode* & pHead)//t头删
    {
    if (pHead == NULL)
    {
    return;
    }
    else
    {
    SListNode*tail = pHead;
    pHead = pHead->next;
    tail->next = NULL;
    free(tail);
    }
    }
    SListNode* Find(SListNode *pHead, DataType x)//以x查找节点,若存在返回给节点,若不存在返回空
    {
    if (pHead == NULL)
    {
    return NULL;
    }
    SListNode* tail = pHead;
    while (tail)
    {
    if (tail->data == x)
    {
    return tail;
    }
    tail = tail->next;
    }
    return NULL;
    }
    void Insert(SListNode* & pos, DataType x)//所给位置后插入一节点
    {
    SListNode*tmp = _BuyNode(x);
    if (pos == NULL)
    {
    pos = tmp;
    }
    else
    {
    tmp->next = pos->next;
    pos->next = tmp;
    }
    }
    void Erase(SListNode * &pos)//删除无头链表的非尾节点
    {
    if (pos == NULL)
    {
    return;
    }
    else if (pos->next == NULL)
    {
    printf("该节点为尾节点,无法删除\n");
    }
    else
    {
    SListNode*tmp = pos->next;
    pos->data = pos->next->data;
    pos->next = pos->next->next;
    free(tmp);
    tmp = NULL;
    }
    }
    void ReveseList(SListNode * &pHead)//链表的逆置
    {
    SListNode*tail = pHead;
    while (tail->next)
    {
    SListNode*tmp=NULL;
    tmp = tail->next;
    tail->next = tail->next->next;
    tmp->next = pHead;
    pHead = tmp;
    }
    }
    SListNode* FindminList(SListNode*pHead)//一次遍历,寻找链表的中间节点
    {
    assert(pHead);
    SListNode *quick=pHead;
    SListNode *slow=pHead;
    while (quick)
    {
    slow = slow->next;
    if (quick->next)
    quick = quick->next->next;
    else
    return slow;
    }
    return slow;
    }
    SListNode* FindListPosList(SListNode*pHead, int lastpos)//寻找链表的倒数第lastpos个节点
    {
    SListNode *quick = pHead;
    SListNode *slow = pHead;
    while (quick&&lastpos--)
    {
    quick = quick->next;
    }
    if (quick == NULL)
    {
    return slow;
    }
    while (quick)
    {
    quick = quick->next;
    slow = slow->next;
    }
    return slow;
    }


    测试用例如下 


    #include <stdio.h>
    #include <stdlib.h>
    #include "SLinkList.h"
    void Test1()//PushBack,PrintList,PopBack
    {
    SListNode*pHead=NULL;
    PushBack(pHead, 1);
    PushBack(pHead, 2);
    PushBack(pHead, 3);
    PushBack(pHead, 4);
    PushBack(pHead, 5);
    PrintList(pHead);
    PopBack(pHead);
    PopBack(pHead);
    PrintList(pHead);
    PopBack(pHead);
    PopBack(pHead);
    PopBack(pHead);
    PrintList(pHead);
    }
    void Test2()//PushFront,Popfront
    {
    SListNode*pHead = NULL;
    PushFront(pHead, 5);
    PushFront(pHead, 4);
    PushFront(pHead, 3);
    PushFront(pHead, 2);
    PushFront(pHead, 1);
    PrintList(pHead);
    PopFront(pHead);
    PrintList(pHead);
    PopFront(pHead);
    PrintList(pHead);
    PopFront(pHead);
    PrintList(pHead);
    PopFront(pHead);
    PrintList(pHead);
    PopFront(pHead);
    PrintList(pHead);
    PopFront(pHead);
    PrintList(pHead);
    }
    void Test3()//Find,Insert
    {
    SListNode*pHead = NULL;
    PushFront(pHead, 5);
    PushFront(pHead, 4);
    PushFront(pHead, 3);
    PushFront(pHead, 2);
    PushFront(pHead, 1);
    Insert(pHead, 0);
    pHead = Find(pHead, 3);
    PrintList(pHead);
    Insert(pHead, 4);
    PrintList(pHead);
    }
    void Test4()//Erase
    {
    SListNode*pHead = NULL;
    SListNode*tmp = NULL;
    PushFront(pHead, 5);
    PushFront(pHead, 4);
    PushFront(pHead, 3);
    PushFront(pHead, 2);
    PushFront(pHead, 1);
    tmp = Find(pHead, 5);
    Erase(tmp);
    PrintList(pHead);
    }
    void Test5()//ReveseList
    {
    SListNode*pHead = NULL;
    PushBack(pHead, 1);
    PushBack(pHead, 2);
    PushBack(pHead, 3);
    PushBack(pHead, 4);
    PushBack(pHead, 5);
    ReveseList(pHead);
    PrintList(pHead);
    }
    void Test6()//FindLastposList
    {
    SListNode*pHead = NULL;
    SListNode*ret = NULL;
    PushBack(pHead, 1);
    PushBack(pHead, 2);
    PushBack(pHead, 3);
    PushBack(pHead, 4);
    PushBack(pHead, 5);
    ret=FindListPosList(pHead, 2);
    printf("%d\n", ret->data);
    ret = FindListPosList(pHead, 6);
    printf("%d\n", ret->data);
    }
    int main()
    {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    system("pause");
    return 0;
    }




    原文链接:http://www.51testing.com/html/97/n-3703997.html
    推荐文章

上一篇:达内:10个PHP自动测试框架

下一篇:达内:Android应用性能测试

最新开班日期  |  更多

国际软件测试工程师精品班

国际软件测试工程师精品班

开班日期:每月底

国际软件测试工程师提升班

国际软件测试工程师提升班

开班日期:每月底

国际软件测试工程师就业班

国际软件测试工程师就业班

开班日期:每月底

国际软件测试工程师就业班

国际软件测试工程师就业班

开班日期:每月底

  • 地址:杭州市西湖区文三路199号创业大厦4楼
  • 课程培训电话:0571-56020834 QQ:3163902815     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56