【C++练手】C++实现单链表

前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作。

链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

我是用C++代码来写的。首先,定义一个linklist.h文件,该文件定义了链表的结点和链表支持的方法。如下所示:

//linklist.h:定义链表结点和方法。

#include <string>

using namespace std;

struct Info

{

string name; //姓名

int id; //学号

};

//链表定义

struct Node

{

Info val;

Node *next;

Node(Info x):val(x),next(NULL) {}

};

class LinkList

{

public:

//构造函数

LinkList();

//在链表头部插入结点

void InsertHead(Info val);

//插入结点

void Insert(Info val,int pos);

//删除结点

void Remove(Info val);

//得到链表长度

int Length();

//链表反序

void Reverse();

//查找结点位置

int Find(Info val);

//打印链表

void Print();

//析构函数

~LinkList();

private:

Node *head;

int length;

};

然后,定义一个linklist.cpp文件,是链表方法的实现。如下所示:

//linklist.cpp:链表方法的实现。

#include "stdafx.h"

#include <iostream>

#include "linklist.h"

using namespace std;

//构造函数

LinkList::LinkList()

{

head = NULL;

length = 0;

}

//析构函数

LinkList::~LinkList()

{

Node *temp;

for(int i=0;i<length;i++)

{

temp=head;

head=head->next;

delete temp;

}

}

//得到链表长度

int LinkList::Length()

{

return length;

}

//在链表头部插入结点

void LinkList::InsertHead(Info val)

{

Insert(val,0);

}

//插入结点

void LinkList::Insert(Info val,int pos)

{

if(pos<0)

{

cout<<"pos must be greater than zero"<<endl;

return;

}

int index = 1;

Node *temp = head;

Node *node = new Node(val);

if(pos == 0)

{

node->next = temp;

head = node;

length++;

return;

}

while(temp!=NULL && index<pos)

{

temp=temp->next;

index++;

}

if(temp == NULL)

{

cout<<"Insert failed"<<endl;

return;

}

node->next = temp->next;

temp->next = node;

length++;

}

//删除结点

void LinkList::Remove(Info val)

{

int pos = Find(val);

if(pos == -1)

{

cout<<"Delete failed"<<endl;

return;

}

if(pos == 1)

{

head = head->next;

length--;

return;

}

int index = 2;

Node *temp = head;

while(index < pos)

temp = temp->next;

temp->next = temp->next->next;

length--;

}

//查找结点位置

int LinkList::Find(Info val)

{

Node *temp = head;

int index = 1;

while(temp!=NULL)

{

if(temp->val.name == val.name && temp->val.id == val.id)

return index;

temp = temp->next;

index ++;

}

return -1; //不存在返回-1

}

//链表反序

void LinkList::Reverse()

{

if(head==NULL)

return;

Node *curNode=head,*nextNode=head->next,*temp;

while(nextNode!=NULL)

{

temp=nextNode->next;

nextNode->next=curNode;

curNode=nextNode;

nextNode=temp;

}

head->next=NULL;

head=curNode;

}

//打印链表

void LinkList::Print()

{

if(head == NULL)

{

cout<<"LinkList is empty"<<endl;

return;

}

Node *temp = head;

while(temp!=NULL)

{

cout<<temp->val.name<<","<<temp->val.id<<endl;

temp=temp->next;

}

cout<<endl;

}

最后,定义一个main.cpp,用来测试链表功能,如下所示:

// main.cpp : 测试链表功能。

#include "stdafx.h"

#include <iostream>

#include <string>

#include "linklist.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

LinkList head;

Info val1,val2,val3,val4;

val1.id =1,val1.name="Kevin",val2.id=2,val2.name="Cathy",val3.id=3,val3.name="Lucy",val4.id=4,val4.name="Gravin";

//测试插入功能

cout<<"Insert test:"<<endl;

head.InsertHead(val1);

head.Print();

head.Insert(val2,1);

head.Print();

head.Insert(val3,4);

head.Print();

head.InsertHead(val3);

head.Insert(val4,2);

head.Print();

//测试反序功能

cout<<"reverse test:"<<endl;

head.Reverse();

cout<<"reversed linklist is:"<<endl;

head.Print();

//测试删除功能

cout<<"remove test:"<<endl;

cout<<"the length of linklist is:"<<endl;

cout<<head.Length()<<endl;

head.Remove(val4);

head.Print();

cout<<"the length of linklist is:"<<endl;

cout<<head.Length()<<endl;

head.Remove(val4);

head.Print();

return 0;

}

测试结果如下图:

其实用C++实现链表的功能,基本上就是用来练手用,在C++的模版里面已经有很多实现了,作为练手的小练习还是挺有意思的。勤快的小伙伴可以对着代码调试起来,加强自己基本功的练习。

修改自:http://blog.csdn.net/kevin_zhai/article/details/50494020

原文发布于微信公众号 - 程序员互动联盟(coder_online)

原文发表时间:2016-11-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

263100
来自专栏王磊的博客

Java核心(四)面试必备—你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

10620
来自专栏Java学习网

Java中三种Set类型用法、性能大比拼

Java为开发者提供了大量的工具类,这给开发人员带来了很大方便,但是选择多了也有困扰,究竟用哪个类;我想选择什么,一是看自己具体需求,二是类本身的性能和用法;J...

89160
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

322120
来自专栏计算机视觉与深度学习基础

Leetcode 290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern. Here ...

23150
来自专栏落花落雨不落叶

线性表学习

350100
来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

7720
来自专栏恰童鞋骚年

剑指Offer面试题:24.复杂链表的复制

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

8720
来自专栏积累沉淀

[求助]castle多对多的分页大家都是怎么样做的?(更新)

这个是我自己做的,感觉效率很低,而且无法查询。 public IList GetPictureByPTypeID(string PTypesID, int ...

21580
来自专栏chenssy

【死磕Java并发】-----J.U.C之阻塞队列:PriorityBlockingQueue

我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的,线程优先级高的线程先执行,优先级低的后执行。而前面介绍的...

35940

扫码关注云+社区

领取腾讯云代金券