欢迎光临
梦想从学习开始!

C++实现链表的进本操作及测试用例| 小熊测试

本文主要介绍 C++实现链表的进本操作及测试用例| 小熊测试,小熊希望对大家的学习或者工作具有一定的参考学习价值,在测试领域有所提升和发展。

  今天实现了下链表的基本操作,包括节点的创建,头插尾插,头删尾删,一次遍历寻找链表的中间节点,寻找链表的倒数第x个节点,删除无头链表的非尾节点,链表的逆置,代码如下:

#include "SLinkList.h"

#include

#include

#include

void PrintList(SListNode* pHead)//从指针位置打印链表

{

while (pHead)

{

printf("->%d", pHead->data);

pHead = pHead->next;

}

printf("");

}

static SListNode* _BuyNode(DataType x)//创建新的节点

{

SListNode*ret = (SListNode*)malloc(sizeof(SListNode));

ret->next = NULL;

ret->data = x;

if (ret)

{

return ret;

}

printf("创建节点失败");//创建失败给出提示

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("该节点为尾节点,无法删除");

}

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

#include

#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", ret->data);

ret = FindListPosList(pHead, 6);

printf("%d", ret->data);

}

int main()

{

Test1();

Test2();

Test3();

Test4();

Test5();

Test6();

system("pause");

return 0;

}

  如有不足希望指正,有疑问希望提出

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持小熊分享邦(www.xxfxb.com),希望大家能坚持软件测试之路,谢谢。

赞(0) 打赏
未经允许不得转载:小熊分享邦 » C++实现链表的进本操作及测试用例| 小熊测试

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏