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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++实现链表的进本操作及测试用例，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4854字，纯文字阅读大概需要7分钟。

内容图文

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

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

本文出自 “pawnsir的IT之路” 博客，请务必保留此出处http://10743407.blog.51cto.com/10733407/1730962

原文：http://10743407.blog.51cto.com/10733407/1730962

内容总结

以上是互联网集市为您收集整理的C++实现链表的进本操作及测试用例全部内容，希望文章能够帮你解决C++实现链表的进本操作及测试用例所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1309357.html

来源：【匿名】

【下一篇】c++有个库什么的吗?

更多 ►

【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...

单链表C++实现【代码】

1// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。2//3 4 #include "stdafx.h" 5 #include"iostream" 6usingnamespace std;7 8 typedef int data;9 10 typedef struct node_list11{12 data info;;13 node_list *next;14}node;15 16 node *init();17 node *insert_head(node *head, data x);18 node *insert_rear(node *head, data x);19 node *insert_x(node *head, data x, data y);20 node *del_x(node *h...

C++反转链表【代码】【图】

建立新链表进行反转struct ListNode{int val;struct ListNode *next; }class solution{ public:ListNode* ReverseList(ListNode* pHead){ListNode* pNode=pHead; //当前节点ListNode* pPrev=nullptr; //前一个节点ListNode* pNext=nullptr; //后一个节点ListNode* pReverseHead=nullptr; //新链表的头指针while(pNode!=nullptr){pNext=pNode->next;if(pNext==NULL)pReverseHead=pNode;pNode->next=pPrev;pPrev=pNode...

C++实现单链表【代码】

C++实现单链表/实现堆什么的也是面试常客了，这里就实现一下。其实细心点写很简单，每个人的实现方式可能不一样，但是思路还是大体相同的。我这里是用一个head来指向链表头元素，head本身无意义，方便而已。 1 #include<bits/stdc++.h>2usingnamespace std;3 4//结点类结构 5struct node{6int val;7struct node *next;8};9 10class LinkList {11private:12 node *head;13public:14 LinkList() { 15 head=new ...

【C/C++学院】0802-链式栈/链表队列以及优先队列/封装链表库

链式栈// stacklinknode.h #define datatype int struct stacknode {int num;//编号datatype data;//数据struct stacknode *pNext;//指针域}; typedef struct stacknode StackNode;//简化 StackNode * init(StackNode * phead);//初始化 StackNode * push(StackNode * phead, int num, datatype data);//进栈 StackNode * pop(StackNode * phead, StackNode * poutdata);//出栈 StackNode * freeall(StackNode * phead);//清空 ...

C++链表，尽量使用C++11【代码】【图】

原创，转载请注明出处。为了熟悉vs环境、c++中的类写的链表 chainNode.h:#pragma once #include<memory> #ifndef CHAINNODE_H #define CHAINNODE_H using std::make_shared; using std::shared_ptr;template <typename T> struct chainNode {T element;shared_ptr<chainNode> next;chainNode(const T &theElement){element = theElement;next = nullptr;}chainNode(const T &theElement, const shared_ptr<chainNode<T>> theNext)...

C++二叉查找树实现及转化为双向链表【代码】

二叉树首先要有树节点template<class T> class BinaryNode { public:T element;BinaryNode *left;BinaryNode *right;public:BinaryNode(T passelement);~BinaryNode(); };template<class T> BinaryNode<T>::BinaryNode(T passelement) {this->element=passelement;this->left=NULL;this->right=NULL; }template<class T> BinaryNode<T>::~BinaryNode() { }二叉树对象则比较复杂 template<class T> class BinarySearchTree { privat...

【C++】通用单链表

在C++的学习中，采用模板类，而采用虚函数实现多态性，达到通用的目的。结点类数据域被改造为指针，而把数据放在一个抽象类中，由指针与之建立联系。采用虚函数实现多态性，达到通用的目的。堆内存的分配与释放，关键不是创建，而是释放！要特别仔细揣摩堆内存的分配与释放，删除一个结点时系统自动调用结点类析构函数释放结点占用的动态内存，而结点释放时系统自动调用数据域类析构函数释放数据类占用的动态内存，本...

c++实现链表【代码】

之前在学c的时候以c的版本谢了有关链表的最基础的几个函数，最近在学习C++，所以，，，哈哈就用另一种版本再次呈现给大家；感觉c++好像写起来比较简单一些。因为它有结构体，所以没有那么繁琐；cpp.h#pragma once#include<iostream>using namespace std;typedef int DataType; struct Node{DataType _data;struct Node * _next;Node(const DataType &d):_data(d),_next(NULL){}}; class Slist { friend ostream & operator<<(ostre...

用C++的类和结构体DIY静态链表及其接口函数【图】

转载请注明出处：http://blog.csdn.net/hongkangwl/article/details/21882459关于静态链表的C实现，网上已经烂大街了，这里就不在废话了。对于本文，纯粹是本屌闲的蛋疼，如有异议，请轻喷。对于每个节点，这里也不能免俗，使用结构体实现struct staticlinklistnode {int data;//数据int next;//下个数据的存储位置bool used;//是否放在链表中了 };静态链表的类主要仿照STL中实现了一些接口函数class staticlinklist { private:sta...

学习笔记 C++ 链表【代码】

今天查了不少关于链表的资料大概理解了链表，为记录只用留笔于此。链表概述：动态的数据存储单元，可以比数组更加灵活。链表的组成：存储的数据，下一个节点。首先让我们用代码完成一个节点。class Node //节点类{ public:Node() {}//三种不同的节点创建方式Node(int n) { num = n; next = NULL; }Node(int n, Node *p) { num = n; next = p; }void setNum(int n) { num = n; }void setNext(Node *p) { next = p; }int getNum() { ...

LeetCode 147. Insertion Sort List 链表插入排序 C++/Java【代码】【图】

Sort a linked list using insertion sort.A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.With each iteration one element (red) is removed from the input data and inserted in-place into the sorted listAlgorithm of Insertion Sort:1Insertion sort iterates, consuming one input element each repetition, and growing a sorted outp...

单链表之一元多项式求和C++实现

单链表之一元多项式求和一元多项式求和单链表实现伪代码1、工作指针 pre、p、qre、q 初始化2、while（p 存在且 q 存在）执行下列三种情况之一：　　2.1、若 p->exp < q->exp：指针 p 后移；　　2.2、若 p->exp > q->exp，则　　　　2.2.1、将结点 q 插到结点 p 之前　　　　2.2.2、指针 p 指向他原指结点的下一个结点；　　2.3、若 p->exp == q->exp，则　　　　2.3.1、p->coef = p->coef + q->coef 　　　　2.3.2、若 p...

[C++]LeetCode: 117 Simplify Path （简化Unix路径 list双向链表)【代码】

题目： Given an absolute path for a file (Unix-style), simplify it. For example,path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"click to show corner cases.Corner Cases:Did you consider the case where path = "/../"? In this case, you should return "/".Another corner case is the path might contain multiple slashes ‘/‘ together,such as "/home//foo/". In this case, you should ignore redu...

循环链表简单操作 C++【代码】【图】

带有头节点的循环链表。头节点的数据域为空，在查找某元素是否在链表中时，可用与存放该元素。头节点的next指针指向第一个元素。最后一个元素指向头节点。如图： //CircularList.h文件#pragma once template<class T> struct listNode{T element;listNode<T>* next;listNode(){}listNode(const T&theElement){ this->element = theElement; }listNode(const T&theElement, listNode<T>*theNext){ this->element = theElement; th...