动态单向链表的C++实现

本文主要是介绍动态单向链表的C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.概念

链表是一种特殊的数组，它的每个元素称为节点，每个节点包括两个部分：

• 数据域：存放数据，此部分与数组相同
• 指针域：存放了下一个节点的地址（单向链表）、存放上一个和下一个节点的地址（双向链表）

其结构如下图所示

链表比数组多了指针域，因为链表结构是通过上一个节点的指针域去找下一个数据，比如有一个链表ABCD四个节点，其中A节点是链表的第一个节点，如果要访问D节点里边的数据。操作如下：

1. 先通过A节点的指针域找到B节点
2. 再通过B节点的指针域找到C节点
3. 再通过C节点的指针域找到D节点
4. 获取D节点数据域的数据

当遍历链表中的数据时，这种方法相比数组一般更加耗时，但是他的好处在于当插入和删除数据时非常方便，数组的插入和删除需要调整之后的每个数据，而链表则只需要调整结点的指针即可，如下图所示，删除同理

二.头指针和头结点

      头指针用来唯一确定单链表的身份，头指针指向链表的第一个结点，若第一个结点不存放数据，则为头结点。链表可以没有头结点，但必须有头指针，没有头指针的话链表也就不存在了。头结点的数据域可以不存放任何信息，也可以存放链表的长度等信息。

总结：

     头指针：

• 在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
• 头指针具有标识作用，常用头指针冠以链表的名字。
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

• 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（有些情况下也可存放链表的长度等等）。
• 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。即操作任何位置时代码相同，更加方便。
• 头结点不是链表所必需的。

三.实践

声明： LinkList.h

//
// Created by 开机烫手 on 2018/3/11.
//
#ifndef LINEARLIST_LINKLIST_H
#define LINEARLIST_LINKLIST_Hnamespace xq {typedef struct node {int data;struct node *next;} NODE;class LinkList {private:NODE* head;int len;LinkList(const LinkList&);public:LinkList();~LinkList();bool clearList();bool isEmpty();int length();void getElem(int, int *);int locateElem(int);bool insert(int, int);bool delete_(int,int*);void sort();void print();bool push_back(int);};}
#endif //LINEARLIST_LINKLIST_H

类实现：LinkList.cpp

//
// Created by 开机烫手 on 2018/3/11.
//
#include <iostream>
#include "LinkList.h"using namespace xq;
using namespace std;LinkList::LinkList() {head = new NODE;    // 创建头结点head->next = nullptr;len = 0;
}LinkList::~LinkList() {NODE *p = head->next;NODE *q;while (p) {q = p->next;delete p;p = q;}
}bool LinkList::clearList() {NODE *p = head->next;NODE *q;while (p) {q = p->next;delete p;p = q;}len = 0;head->next = nullptr;return true;
}bool LinkList::isEmpty() {return len == 0;
}int LinkList::length() {return len;
}void LinkList::getElem(int i, int *e) {if (i <= 0 || i > len || len == 0) {*e = -999;return;}int j = 1;NODE *p = head->next;while (j < i && p) {p = p->next;j++;}*e = p->data;
}int LinkList::locateElem(int e) {int i = 1;NODE *p = head->next;while (p) {if (p->data == e)return i;p = p->next;i++;}return -1;
}bool LinkList::insert(int i, int e) {if (i <= 0 || i-1 > len)return false;int j = 1;NODE *p = head;while (p && j < i) {p = p->next;j++;}NODE *s = new NODE;s->data = e;s->next = p->next;p->next = s;len++;return true;
}void LinkList::print() {if (len == 0) {cout << "list is empty!" << endl;return;}NODE *p = head->next;while (p) {cout << p->data << ' ';p = p->next;}cout << endl;
}bool LinkList::delete_(int i, int *e) {if (i <= 0 || i > len)return false;NODE *q = head;int j = 1;NODE *p = head->next;while (j < i) {q = p;p = p->next;j++;}*e = p->data;q->next = p->next;len--;delete p;return true;
}bool LinkList::push_back(int e) {NODE *p = head->next;while (p->next) {p = p->next;}NODE *s = new NODE;s->data = e;p->next = s;s->next = nullptr;len++;return true;
}void LinkList::sort() {if (len <= 1)return;int temp;NODE *p, *q;for (int i = 0; i < len - 1; i++) {p = head->next;q = head->next->next;for (int j = 0; j < len - 1 - i; j++) {if ((p->data) > (q->data)) {temp = p->data;p->data = q->data;q->data = temp;}p = p->next;q = q->next;}}
}

代码测试：main.cpp

#include <iostream>
#include "LinkList.h"using namespace std;
using namespace xq;int main() {cout << "----------List test programe!---------- " << endl;LinkList list1;cout << "is empty " << list1.isEmpty() << endl;list1.insert(1, 1);cout << "is empty " << list1.isEmpty() << endl;list1.clearList();cout << "is empty " << list1.isEmpty() << endl;list1.insert(1, 1);list1.insert(2, 2);list1.insert(3, 3);list1.insert(4, 5);list1.insert(5, 6);list1.print();list1.insert(4, 4);list1.print();int c;list1.delete_(5, &c);list1.print();int location = list1.locateElem(3);cout << "location is " << location << endl;int num2;list1.getElem(4, &num2);cout << "num2 = " << num2 << endl;list1.push_back(10);list1.push_back(5);list1.push_back(7);list1.push_back(2);list1.print();list1.sort();cout << "sort " ;list1.print();return 0;
}

程序输出为：

----------List test programe!----------
is empty 1
is empty 0
is empty 1
1 2 3 5 6
1 2 3 4 5 6
1 2 3 4 6
location is 3
num2 = 4
1 2 3 4 6 10 5 7 2
sort 1 2 2 3 4 5 6 7 10

这篇关于动态单向链表的C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---