C++链表(单、循环、双向)设计及操作

实验要求

概念理解

链表数据结构

链表是一种数据结构，和数组同级。之前JAVA里面的ArrayList数据结构，其实现原理是数组，而JAVA的LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显，其实C/C++抑或是JAVA这些数据结构都一样——地址……引用……

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

上图中最左边的节点即为头结点（Head），但是添加节点的顺序是从右向左的，添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一个节点而非下一个节点的对象。因为有着不断的引用，所以头节点就可以操作所有节点了。

下图描述了单向链表存储情况。存储是分散的，每一个节点只要记录下一节点，就把所有数据串了起来，形成了一个单向链表。

节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。下面图是具体的说明：

关于链表的指向

个人觉得链表的相关问题及操作就是理解链表的“指向”这么个概念，先明确以下几点

• 每个节点的next用来存放下一个节点的“地址”
• 每个节点的自身就是地址，相当于C语言中数组的数组名就是本数组的地址

总结：做题用下面总结的方法，绝对好使

• 读的时候：从左往右读，一般左边是某某的next域，右边是具体的结点
• 画的时候：在图中表示为等号左边指向等号右边

例子：

① node.next = prev.next;

② prev.next = node

读法：

①“node的next指向prev的下一个结点”

（用指针的概念通俗地说，其实就是prev的下一个结点的地址由prev的指针域里面赋值给了node的next指针域里面）

②“prev的next指向node这个结点”

（还可以这么说：将node赋值给prev的next，也就是说prev的下一个结点是node）

关注第一个元素节点是不是head，因为有的链表不声明头节点（head），直接就是第一个结点就是元素结点

关于p=L的理解

写代码的时候，还经常遇到下面的情况

p、L就是指向结点的指针类型，将L的值赋给p，也就是p、L指向同一个结点。具体理解可以用下面一个例子来说明：

下面图片这个函数就是在一个单链表中，功能就是指定i位置插入e值。下图箭头处如果TraverseList返回的是p那么得出的链表结果就是从插入的那个元素往后这样一个部分链表，返回的是L就是想要的结果，p的功能有点类似在L的中间做了手脚……

各种代码

实验报告代码

#include<bits/stdc++.h>

using namespace std;

typedef struct LNode {
int data;
struct LNode *next;
}Lnode, *LinkList;

LinkList L;

void InitList(LinkList &L) {
L = new LNode;
L->next = NULL;
}

void CreateList_H(LinkList &L) {
InitList(L);
int n;
cout << "请输入要使用前插法插入的元素个数：";
cin >> n;
for (int i = 0; i < n; i++){
LNode *p = new LNode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
void TraverseList(LinkList &L){
LNode *p = new LNode;
p = L->next;
cout << "此链表打印的结果为："<<"\n";
while (p != NULL){
cout << p->data << " ";
p = p->next;
}
cout << "\n";
}
void GetElem(LinkList &L) {
int n;
cout << "请输入要查询的链表中第 i 个数：";
cin >> n;
LNode *p = new LNode;
p = L;
for (int i = 0; i < n;i++){
p = p->next;
}
cout << "查询的结果为：" << p->data<<"\n";
}
void ListInsert(LinkList &L){
LNode *p = new LNode;
p = L;
int n;
int e;
cout << "请分别输入要在第 n 个位置插入的 e 值：";
cin >> n>> e ;
for (int i = 0; i < n;i++) {
if (n == i+1){
LNode *temp = new LNode;
temp->data = e;
temp->next = p->next;
p->next = temp;
break;
}
p = p->next;
}
TraverseList(L); // 直接返回 L 就可以了，之前返回 p 是不可以的！！！唉，大意了~
}
void ListDelete(LinkList &L){
cout << "请输入要删除的第 j 个位置的 j 值：";
LNode *p = new LNode;
p = L;
int j;
cin >> j;
for (int i = 0; i < j;i++) {
if (j == i+1) {
p->next = p->next->next;
break;
}
p = p->next;
}
TraverseList(L);
}
void ReverseList(LinkList &L) {
LNode *p = L->next;  
 L->next = NULL;  
 while(p)  
 {
LNode *q = p->next;  
 p->next = L->next;  
 L->next = p;  
 p = q;  
 }
cout << "通过逆置之后……";
TraverseList(L);
}

int main() {
LNode *test = new LNode;
CreateList_H(test);//1
TraverseList(test);//1
GetElem(test);//2
ListInsert(test);//3
ListDelete(test);//4
ReverseList(test);//5
}

单链表各种操作代码总结

• 单链表存储形式

typedef struct LNode {
int data; //数据域
struct LNode *next; //指针域
}Lnode, *LinkList; //LinkList 为指向结构体 LNode 的指针类型

• 初始化
• 创建：前插法
• 创建：后插法
• 取值
• 插值
• 删除
• 打印
• 逆置

逆置多用前插的思想

void ReverseList(LinkList &L) {
LNode *p = L->next;  
 L->next = NULL;  
 while(p) {
LinkList q = p->next;  
 p->next = L->next;  
 L->next = p;  
 p = q;  
 }
}

所有操作如下

#include<bits/stdc++.h>
using namespace std;

/\*\*

- 单链表
-
- 链表的基本操作：初始化、创建（前插、后插）、取值、查找、插值、删除、打印、逆置
  \*/

/_ 单链表的存储结构 _/
typedef struct LNode {
int data; //数据域
struct LNode *next; //指针域
}Lnode, *LinkList; //LinkList 为指向结构体 LNode 的指针类型

/_ 初始化链表 _/
void InitList(LinkList &L) {
L = new LNode;
L->next = NULL;
}

/_ 创建：前插 _/
void CreateList_H(LinkList &L, int n) {
InitList(L);
for (int i = 0; i < n; i++){
LNode \*p = new LNode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}

/_ 创建：后插 _/
void CreateList_R(LinkList &L, int n) {
cout << "请输入" << n << "个数字"<< "\n";
InitList(L);
// 定义一个在下面循环用来一直操作所加元素的结点 p 来指向头结点 L
LinkList p = L;
for (int i = 0; i < n;i++) {
LinkList q = new Lnode;
q->next = NULL;
cin >> q->data;
p->next = q;
p = q; //为了下一次
}
}

/_ 取值 _/
void GetElem(LinkList &L, int n) {
LinkList p = L;
for (int i = 0; i < n;i++){
p = p->next;
}
cout <<n<<"的值为：" << p->data<<"\n"<<"\n";
}

/_ 查找 _/
void SearchElem(LinkList &L, int ele) {
LinkList p = L;
int count = 0;
while (p->data != ele) {
p = p->next;
count++;
}
cout <<ele<<"这个值的索引位置是："<< count<<"\n";
}

/_ 插值：在第 n 个位置插入 ele 值_/
void ListInsert(LinkList &L, int n, int ele){
LinkList p = L;
for (int i = 0; i < n;i++) {
if (n == i+1){
LinkList temp = new LNode;
temp->data = ele;
temp->next = p->next;
p->next = temp;
break;
}
p = p->next;
}
TraverseList(L);
}

/_ 删除：删除第 j 个位置的值 _/
void ListDelete(LinkList &L, int j){
LinkList p = L;
for (int i = 0; i < j;i++) {
if (j == i+1) {
p->next = p->next->next;
break;
}
p = p->next;
}
TraverseList(L);
}

/_ 打印 _/
void TraverseList(LinkList & L){
LNode _p = new LNode;
p = L->next;
cout << "此链表打印的结果为："
<< "\n";
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << "\n";
}
/_ 逆置 */
void ReverseList(LinkList &L) {
LNode *p = L->next;  
 L->next = NULL;  
 while(p)  
 {
LNode \*q = p->next;  
 p->next = L->next;  
 L->next = p;  
 p = q;  
 }
cout << "通过逆置之后……";
TraverseList(L);
}

int main() {
// LNode *test = new LNode;
LinkList test;
// struct LNode *test;
CreateList_R(test,4);
SearchElem(test, 3);
// cout << GetEle(test, 2);
// TraverseList(test);
// GetElem(test,2);
// ListInsert(test);
// ListDelete(test);
// ReverseList(test);
}

循环链表代码

 * 循环链表其实只需要注意最后一个结点所指向的下一个结点为头结点 L 就好了

* 还要注意头结点存不存元素

\* 还有判断的时候条件不是单链表那样判断是否为空了，而是是否为头结点的值了

#include<bits/stdc++.h>
using namespace std;

/\*\*

- 循环链表
-
- 循环链表其实只需要注意最后一个结点所指向的下一个结点为头结点 L 就好了
- 还要注意头结点存不存元素
- 还有判断的时候条件不是单链表那样判断是否为空了，而是是否为头结点的值了
  \*/

/_ 定义一个单链表 _/
typedef struct LNode {
int data;
struct LNode *next;
}Lnode, *LinkList;

/\*\*

- 初始化单链表
  \*/
  void InitList(LinkList &L) {
  L = new LNode;
  L->next = NULL;
  }

/\*\*

- 初始化单链表并将其变成循环链表
  \*/

void CircleList(LinkList &L, int n) {
InitList(L);
// 初始化第一个结点的值
L->data = 1;
LinkList p = L;
for (int i = 2; i <= n; i++) {
LinkList temp = new Lnode;
temp->data = i;
if (i == n) {
temp->next = L;
p->next = temp;
break;
}
temp->next = NULL;
p->next = temp;
p = p->next;
}
}

/\*\*

- 打印输出用来测试是否为循环链表
  \*/
  void PrintList(LinkList &L, int n) {
  LinkList p = L;
  for (int i = 0; i < n;i++) {
  cout << p->data << " ";
  p = p->next;
  }
  }

int main() {
LinkList test;
CircleList(test,5);
PrintList(test, 12);
}

双向链表代码

• 双向链表从某种意义上来说，更加简单了，因为可操作的“指向更多了”，但正因为这样，所以每次指向操作之后，检查一下有没有“落单的指向”
• 删除某个结点的时候，一定要记得删除哪个结点，就操作哪个结点

#include<bits/stdc++.h>
using namespace std;

/\*\*

- 双向链表
  \*/

/_ 双向链表的存储结构 _/
typedef struct DuLNode {
int data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLnode, \*DuLinkList;

/_ 双向链表的初始化 _/
void InitDuLinkList(DuLinkList &L) {
L = new DuLNode;
L->prior = NULL;
L->next = NULL;
}

int main() {
DuLinkList L;
InitDuLinkList(L);
// 初始化初始节点值为 100
L->data = 100;
// 在 L 结点前面插值 50
DuLinkList L_prior;
L_prior->data = 50;
L_prior->next = L;
L->prior = NULL;
L->prior = L_prior;
// 在 L 结点后面插值 150
DuLinkList L_next;
L_next->data = 150;
L_next->prior = L;
L_next->next = NULL;
L->next = L_next;
cout << L_prior->data << " " << L_prior->next->data << " " << L_prior->next->next->data<<"\n";
// 在 50 和 100 之间插值 75（只操作 L 结点）
DuLinkList L_prior_L;
L_prior_L->data = 75;
L_prior_L->prior = L->prior;
L->prior->next = L_prior_L;
L_prior_L->next = L;
L->prior = L_prior_L;
cout << L->prior->prior->data << " " << L->prior->data << " " << L->data <<" "<< L->next->data<<"\n";
// 删除 75 这个值的结点(记住一点，删除哪个结点就操作哪个结点)
L_prior_L->next->prior = L_prior_L->prior;
L_prior_L->prior->next = L_prior_L->next;
cout << L->prior->data << " " << L->data << " " << L->next->data << "\n";
}

参考

• 链表 p->next=q->next,q->next=p,q=p;的一些解释
• p->next=q 与 q=p->next 区分
• 数据结构：链表