C++实现单向链表-技术圈

之前相关的文章

#什么是链表

链表是一种基本的数据结构，之前我在C语言里面写过链表的知识，现在延申到C++，不管是什么语言，链表表示的是一种数据结构，跟语言没有强相关性的。

如果我们需要实现一个链表，首先最关键的就是节点，一个节点表示链表的一个数据存储点，链表是由很多个节点组成的。

链表还需要很多线把很多节点串联在一起，可以用数组的特性串联，也可以用指针串联。

/*节点类*/ 
class Node
{
public:
 DataType data;
 Node *next;
};

#链表头部

链表是一种数据结构，跟数组一样，和整型的数据一样，都需要一个起始位置，链表头就是这个起始位置，链表头存在，就表示链表存在，链表头没有了，那这个链表也就没有了。

链表头也是一个节点，只是这个节点保存的是这个链表的起始位置

头节点有点意思，它其实是不需要存储数据的，所以data的值可有可无。

代码上我们可以这样写，创建一个链表也就是创建一个链表头

LinkList::LinkList()
{
 head = new Node;
 head->data = 0;
 head->next = NULL;
 size = 0;
}

#插入一个数据到链表中

如果是一个已经成型的链表，我们要把一个数据插入到链表中，我们需要有几个判断，是从链表头插入，还是链表尾部插入，还是从链表的中间插入

— — 如果从链表头插入，如下图

— — 如果从链表中间插入，如下图

— — 如果从链表尾部插入，如下图

— —代码实现

int LinkList::InsertLinklList(Node *data, int n)
{
 Node *ptemp;
 if (this->head == NULL) {
     cout << "链表为空" << endl;
  return -1;
 }
 if (data == NULL) {
  cout << "插入节点为空" << endl;
  return -1;
 }
 /*头部插入*/ 
 if (n<2) {
  Node *pnew = new Node;
  pnew->data = data->data;
  pnew->next = this->head->next;
  this->head->next = pnew;
  this->size++;
  return 0;
 }
 /*尾部插入*/ 
 if (n > this->size) {
  ptemp = this->head;
  while (ptemp->next != NULL) {
   ptemp = ptemp->next;
  }
  Node *pnew = new Node;
  pnew->data = data->data;
  pnew->next = NULL;
  ptemp->next = pnew;
  this->size++;
  return 0;
 }else {/*中间插入*/ 
  ptemp = this->head;
  for (int i = 1; i < n; i++) {
   ptemp = ptemp->next;
  }
  
  Node *pnew = new Node;
  pnew->data= data->data;
  pnew->next = ptemp->next;
  ptemp->next = pnew;
  this->size++;
  return 0;
 }
}

#完整的代码

#include 
#include 
using namespace std;


/*节点类*/
class Node
{
public:
 int data;
 Node *next;
};

class LinkList
{
public:
 LinkList();/*构造函数*/
 ~LinkList();/*析构函数*/
 int CreateLinkList(int size);/*新建一个链表*/
 int DestroyLinkList();/*销毁一个链表*/
 int TravalLinkList();/*遍历一个链表*/
 int InsertLinklList(Node *data, int n);/*向链表插入一个数据*/
 int DeleteLinklist(int n);/*删除链表中的某个值*/

 int GetLength();/*获取链表的长度*/
 bool IsEmpty();/*判断链表是否为空*/

 Node *head;/*链表头*/
 int size;/*链表长度*/
};

LinkList::LinkList()
{
 head = new Node;
 head->data = 0;
 head->next = NULL;
 size = 0;
}

LinkList::~LinkList()
{
 delete head;
}

int LinkList::CreateLinkList(int n)
{
 if (n<0) {
  cout<<"error"<  return -1;
 }
 Node *ptemp = NULL;
 Node *pnew = NULL;

 this->size = n;
 ptemp = this->head;
 for(int i =0 ; i {
  pnew = new Node;
  pnew->next = NULL;
  cout << "输入第" << i+1 << "个节点值" << endl;
  cin >> pnew->data;
  ptemp->next = pnew;
  ptemp = pnew;
 }
 cout << "创建完成" << endl;
 return 0;
}

int LinkList::DestroyLinkList()
{
 Node *ptemp;
 if (this->head == NULL) {
  cout << "链表原本就为空" << endl;
  return -1;
 }
 while (this->head)
 {
  ptemp = head->next;
  free(head);
  head = ptemp;
 }
 cout << "销毁链表完成" << endl;
 return 0;
}

int LinkList::TravalLinkList()
{
 Node *ptemp = this->head->next;
 if (this->head == NULL) {
  cout << "链表为空" << endl;
  return -1;
 }
 while(ptemp)
 {
  cout << ptemp->data << "->";
  ptemp = ptemp->next;
 }
 cout <<"NULL"<< endl;
 return 0;
}

int LinkList::InsertLinklList(Node *data, int n)
{
 Node *ptemp;
 if (this->head == NULL) {
  cout << "链表为空" << endl;
  return -1;
 }
 if (data == NULL) {
  cout << "插入节点为空" << endl;
  return -1;
 }
 /*头部插入*/
 if (n<2) {
  Node *pnew = new Node;
  pnew->data = data->data;
  pnew->next = this->head->next;
  this->head->next = pnew;
  this->size++;
  return 0;
 }
 /*尾部插入*/
 if (n > this->size) {
  ptemp = this->head;
  while (ptemp->next != NULL) {
   ptemp = ptemp->next;
  }
  Node *pnew = new Node;
  pnew->data = data->data;
  pnew->next = NULL;
  ptemp->next = pnew;
  this->size++;
  return 0;
 }
 /*中间插入*/
 else {
  ptemp = this->head;
  for (int i = 1; i < n; i++) {
   ptemp = ptemp->next;
  }
  Node *pnew = new Node;
  pnew->data= data->data;
  pnew->next = ptemp->next;
  ptemp->next = pnew;
  this->size++;
  return 0;
 }
}

int LinkList::DeleteLinklist(int n)
{
 Node *ptemp;
 Node *ptemp2;
 if (n > this->size) {
  cout << "n太大" << endl;
  return -1;
 }
 /*删头节点*/
 if (n < 2) {
  ptemp = this->head->next;
  this->head->next = ptemp->next;
  free(ptemp);
  this->size--;
  return 0;
 }
 /*尾部删除*/
 if (n == this->size) {
  ptemp = this->head;
  for (int i = 1; i < this->size;i++) {
   ptemp = ptemp->next;
  }
  ptemp2 = ptemp->next;
  ptemp->next = NULL;
  free(ptemp2);
  this->size--;
  return 0;
 }
 /*中间删除*/
 else
 {
  ptemp = this->head;
  for (int i = 1; i < n; i++) {
   ptemp = ptemp->next;
  }
  ptemp2 = ptemp->next;
  ptemp->next = ptemp2->next;
  free(ptemp2);
  this->size--;
  return 0;
 }
}

int LinkList::GetLength()
{
 return this->size;
}

bool LinkList::IsEmpty()
{
 if (this->head == NULL) {
  return true;
 }
 else{
  return false;
 }
}

int main(void)
{
 LinkList list;
 LinkList *plist = &list;
 /*创建6个节点的链表*/
 plist->CreateLinkList(5);
 plist->TravalLinkList();

 /*向链表中插入一个数据*/
 Node temp;
 temp.data = 77;
 temp.next = NULL;
 /*向0号位置插入一个节点*/
 plist->InsertLinklList(&temp, 0);
 /*遍历整个链表*/
 plist->TravalLinkList();
 /*向尾部插入一个链表*/
 plist->InsertLinklList(&temp, plist->GetLength()+1);
 /*遍历整个链表*/
 plist->TravalLinkList();
 /*向5号位置插入一个链表*/
 plist->InsertLinklList(&temp, 5);
 /*遍历整个链表*/
 plist->TravalLinkList();

 plist->DeleteLinklist(0);
 /*遍历整个链表*/
 plist->TravalLinkList();
 /*删除第二个节点*/
 plist->DeleteLinklist(4);
 /*遍历整个链表*/
 plist->TravalLinkList();

 /*删除整个链表*/
 plist->DestroyLinkList();
 system("pause");
 return (0);
}

#代码输出

输入第1个节点值
2
输入第2个节点值
22
输入第3个节点值
3
输入第4个节点值
44
输入第5个节点值
5
创建完成
2->22->3->44->5->NULL
77->2->22->3->44->5->NULL
77->2->22->3->44->5->77->NULL
77->2->22->3->77->44->5->77->NULL
2->22->3->77->44->5->77->NULL
2->22->3->44->5->77->NULL
销毁链表完成
请按任意键继续. . .

推荐阅读：

嵌入式Linux

微信扫描二维码，关注我的公众号

下面是我的僚机号，欢迎大家关注

写代码的篮球球痴

微信扫描二维码，关注我的公众号