C++实验设计(二)--单向链表的设计

这一次是有关链表的总结 许多人对链表很陌生 链表是数据结构的核心内容 我们学的只是其中的一点 多余的内容我也不太清楚 有兴趣的话可以查看有关数据结构的书 下面主要谈谈创建简单的链表是怎么实现的 一 链表是由节点通过指针连在一块的 所以节点是其基本元素 首先创建节点 1 struct Node int a Node next 链表的节点和一般的结构体有点区别 包含两个部分 1 数据域 2 指针域 数据域是根据自己的需要所设计的 上例中 int a 就是数据域的内容 Node next 是指针域的内容 我这个链表是模拟整型数据进栈出栈的过程 书上有个 内容 一般情况下 结构体是不含有本身结构体的变量 例如 struct Node int a Node next 这样就不正确了 具体原因是因为这个结构体没创建成功 不知道其所占空间 系统无法为之分配空间 但是可以使自身的指针型数据 因为无论是何种类型 的指针 其所占空间大小都是 4 个字节 所占空间大小就很明确了 下面我们就具体来实现这个创建链表的过程 添加节点 2 void creat Node cin p a p next Head Head p 数据结构中成这种添加节点的方法叫头插法 自然有对应的尾插法 这里不说 了 注意几个细节吧 1 void creat Node Node next include using namespace std void creat Node cout p a p next Head Head p int main Node head NULL creat head cout a endl return 0 具体可以体验一下 但是由上面我们可以看到 其实在主函数中创建的链表只 有一个节点 算不上链表 那么要想真正的成为一条链 该怎么办 其实在主函数中用 for 循环语句控制即可 例如这样 int main Node head NULL for int i 0 i 5 i creat head cout a endl return 0 这样就可以添加许多数据了 这个创建的是具有 5 个节点的链表 这样真正实 现了链状 好像少了点东西 即遍历链表 我们要把 5 个数据表现出来 这时需要另外设计一个遍历链表的函数 虽然这是个链表 但是你怎么能知道每个数据存放在何处 其实由于是链表 我们只需要知道头节点的位置即可 这就回到结构体的设计 Node next 的 作用就是连接下一个节点 用它来记录下一个节点的地址值 这样我们就清楚 了 主函数中 head 是记录头节点位置的 刚开始时 head 是指向 NULL 的 后 来进入到 creat head 函数中 其指向就改变了 编程指向链表的头节点的位置 这就是引用传递的效果 void creat Node while Head NULL cout a next 这样就可以实现你想查看的数据了 在主函数中这样就可以实现 int main Node head NULL for int i 0 inext delete Head Head p 在主函数中只需要这样实现即可 int main Node head NULL for int i 0 i 5 i creat head show head deletehead head show head return 0 整个代码 struct Node int a Node next include using namespace std void creat Node cout p a p next Head Head p void show const Node Head if Head NULL cout 链表是空 n while Head NULL cout a next cout next delete Head Head p int main Node head NULL for int i 0 i 5 i creat head show head deletehead head show head return 0 这就是一个简单的链表 上面说的不是很清晰 有点模糊 其实理解一下函数 的引用传递就行了 这个是很关键的 补充一点 添加多个节点也可以不用在主函数中用 for 循环语句 只需要这样设计创建链 表的函数就好了 如下 void creat Node i p a p next Head Head p 主函数中调用就可以使这个样子 int main Node head