欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++单向链表的简单实现

程序员文章站 2024-03-06 21:52:14
...

链表这个概念曾经困扰了我很久,在我刚接触指针的时候(那时学的Fortran)对指针这个概念理解的不到位导致链表也没学懂。但现在再来看已经可以想明白它的简单实现原理了。其实只需要理解清楚指针的概念实现链表没有想象中那么难。

  1. 首先需要创建一个简单的类
struct pointer {
	int i;
	pointer *p;
};

这个类看起来很简单,只有两个成员,一个整型,一个指向类的指针。但它是链表可以玩出花的关键。

  1. 需要一个实现添加新节点的函数
    这个函数是必不可少的,我们需要用到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函数释放动态分配的内存空间。