C++单向链表的简单实现
程序员文章站
2024-03-06 21:52:14
...
链表这个概念曾经困扰了我很久,在我刚接触指针的时候(那时学的Fortran)对指针这个概念理解的不到位导致链表也没学懂。但现在再来看已经可以想明白它的简单实现原理了。其实只需要理解清楚指针的概念实现链表没有想象中那么难。
- 首先需要创建一个简单的类
struct pointer {
int i;
pointer *p;
};
这个类看起来很简单,只有两个成员,一个整型,一个指向类的指针。但它是链表可以玩出花的关键。
- 需要一个实现添加新节点的函数
这个函数是必不可少的,我们需要用到malloc函数动态分配一个节点的空间,
函数输入表头和一个需要存储的数据,返回表头。我们应该把创建的节点加到链表的尾部,把待存储的数据赋值到节点。
pointer* newp(pointer* pp,int data) {
pointer* pa=nullptr, * pb = pp;
pa= (pointer*)malloc(sizeof(pointer));
if (pp == nullptr)
pp = pa;
else {
while (pb->p != nullptr) {
pb = pb->p;
}
pb->p = pa;
}
pa->i = data;
pa->p = nullptr;
return pp;
}
整个程序如下
#include<iostream>
using namespace std;
struct pointer {
int i;
pointer *p;
};
pointer* newp(pointer* pp,int data) {
pointer* pa=nullptr, * pb = pp;
pa= (pointer*)malloc(sizeof(pointer));
if (pp == nullptr)
pp = pa;
else {
while (pb->p != nullptr) {
pb = pb->p;
}
pb->p = pa;
}
pa->i = data;
pa->p = nullptr;
return pp;
}
int main() {
pointer* p1 = nullptr;
p1 = newp(p1, 1);
p1 = newp(p1, 2);
pointer* p4 = p1;
while (p4!= nullptr) {
cout << p4->i << endl;
p4 = p4->p;
}
free(p1);
return 0;
}
注意最后要用free函数释放动态分配的内存空间。