SDUTOJ 2116 数据结构实验之链表一：顺序建立链表

本文主要是介绍SDUTOJ 2116 数据结构实验之链表一：顺序建立链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近数据结构和c++相结合的实训正在进行，鉴于一些同学还不是太懂链表，写一篇博客讲解一下，若是哪里有问题，请不吝支出，在此谢过，若是过路的大神看见了，求轻喷。。。。

说白了，链表就是个特殊的结构体数组，只不过数组是用下标找到某个节点的后继节点，而链表使用一个指向他身类型的指针来记录下一个节点的地址，就比如你进入了一个村庄，你发现这里住的楼的楼号（1,2,3,4,等）都是连着的，这就是结构体数组，而链表就是你从第一楼开始，看到的是本楼的标号，然后标号下面还有一行字：下一个楼是XXX，他在某某某地方，当你找到XXX后，XXX的楼的标号下面也有一行字：下一个楼是YYY，他在另一个某某某地方，你每次都能从这个楼的标号上找到下一个楼在哪，直到最后一栋楼上标号下面没有下一个楼的信息，只有一个NULL，那么，你走到楼的最后了。。。链表遍历完了。。。。。

这里以SDUTOJ的2116题为例，讲解一下链表，另外，链表是写出来的，练出来的，不写，不编译运行，不调试，永远学不会链表，所以不要光看，要用编译器写，然后提交到OJ上去判，才能学会，这是这个题的链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2116

数据结构实验之链表一：顺序建立链表

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。

输入

第一行输入整数的个数N；
第二行依次输入每个整数。

输出

输出这组整数。

示例输入

8
12 56 4 6 55 15 33 62

示例输出

12 56 4 6 55 15 33 62

提示

不得使用数组！

来源

示例程序

#include <iostream>using namespace std;class List
{public:int data;//数据域，用来记录数据List *next;//指着域，用来记录它下一个节点的地址//访问这个变量能找到它的下一个节点
};void del(List *p)//递归释放内存
{if(p == NULL)//p为NULL说明p访问到链表结尾了return ;//访问到结尾返回del(p->next);//如果没访问到结尾，会在这里一直调用函数本身递归，直到遇见NULLdelete p;//遇到NULL返回到head的时候，从后向前删除节点，释放内存//如果从前面删除的话就会把本节点的next值也给删除了，就没办法访问到下一个节点了//如果定义一个临时变量先记录下一个节点地址然后再删除本节点也是可以解决这个问题的
}
//void del(List *head)
//{
//    List *p = head,*q;
//    while(p)
//    {
//        q = p;
//        p = p->next;
//        delete q;
//    }
//}//这样释放内存也是可以的
int main()
{List *head = new List;//new开辟内存，地址赋给head，head代表这个//链表的头，访问head能找到这个链表head->next = NULL;//初始状态下只有head链节，他没有后继结点，所以他的next值为NULL（空）List *p,*q;//p是游动指针，建立链表的时候永远指向最后一个链节//q是开新内存用的，也就是增加一个新的链节int n;//输入数的个数cin>>n;p = head;//初始状态下只有head一个链节，那么最后一个链节也是head，让p指向headfor(int i = 0;i < n;i++){q = new List;//增加新的链节qcin>>q->data;//给新链节的data赋值p->next = q;//把q挂在p（初始值是head）的后面q->next = NULL;//新链节是链表的最后一个链节，后面没有后继，那么，就把他的next值设为NULL（空）p = q;//q成为p的后继之后，q就是最后一个节点，我们规定p指向最后一个节点，这里就把q赋给p}//循环完成后，链表就建立完了，head是他们的头p = head->next;//p在上面是指向最后一个元素，以便于增加新的链节后能很快的放在它的后面，达到添加链节的目的//现在我们就发动他的游动特点，来访问整个链表，从上面看来，我们输入的第一个整数放在q->data//里面了，并没有放在head里面，那么，我们访问的话，head的下一个节点才是第一个存储节点，用p//访问head的next，判就指向了链表中的第一个存储输入数的节点(真正第一个节点是head，因为head//因为head的data没有值，所以，我们说head的后面第一个节点为有效节点)while(p != NULL)//当p访问不到NULL的时候，就会一直循环，NULL是链表结束的标志{cout<<p->data;//输出p访问到的每个节点的data值if(p->next != NULL)cout<<" ";//这两行是调格式的，为了能在最后不多输出空格，其实只是为了在OJ上ACp = p->next;//p访问把本节点的next值，p就指向下一个节点，相当于向后移动一个节点}cout<<endl;del(head);//释放内存return 0;
}

这篇关于SDUTOJ 2116 数据结构实验之链表一：顺序建立链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！