软件测试

收藏 / 订阅

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

  今天实现了下链表的基本操作,包括节点的创建,头插尾插,头删尾删,一次遍历寻找链表的中间节点,寻找链表的倒数第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;

}

喜欢 (88) or分享 (0)
首页  上一页  12345678910  下一页 尾页 共73条记录 7/10

网友评论:7

  1. 小编 1年前 (2015-03-22) #5

    软件测试入门 :mrgreen:

留言主题 *

您的姓名 *

电子信箱:

电话号码:

请你留言: