不带头结点的链表的建立和打印
程序员文章站
2024-03-21 13:32:34
...
#include<iostream>
using namespace std;
#define NUM (4000) //打算生成一个含4000个结点的链表,你也可以任意改变
typedef int ElementType;//链表元素的类型,这里设置为int,你可以设置其他类型
/*定义链表的结点结构:包含结点的值和指向下一节点的指针*/
typedef struct listNode {
ElementType element;
struct listNode *next;
}*List;
/*注意:List L;等价于struct listNode *L;*/
void initList(List L);
void inputList(List L);
void printList(List L);
int main()
{
/*L是链表的第一个结点*/
List L = (List)malloc(sizeof(List));
initList(L);
inputList(L);
printList(L);
system("PAUSE");//VS中需要这一句使得程序在运行结束时窗口不关闭,在其他环境可能不需要
return 0;
}
void initList(List L)
{
L->next = NULL;
L->element = 0;//我把第一个结点的值初始化为0,是因为我想打印一段自然数(后面的tmpNode->element = i;也是为此)
}
void inputList(List L)
{
/*L用来记录第一个结点的位置,所以还需要声明一个结点P用于连接后面加入的结点*/
List P = L;
/*第1个结点的值在initList函数中已经输入了,所以这里i的初始值设为1,即从第2个结点开始*/
for (int i = 1; i < NUM; i++)
{
/*先建立一个临时结点,然后将这个结点加入到链表中去*/
List tmpNode = (List)malloc(sizeof(List));//malloc函数返回void*类型,所以要类型转换
tmpNode->element = i;
tmpNode->next = NULL;
P->next = tmpNode;//将tmpNode加入到链表中
P = P->next;//准备将下一个结点加入到链表中
}
}
void printList(List L)
{
/*第1种:循环方式*/
for (int i = 0; i <NUM; i++)
{
if (L->next != NULL)
{
cout << L->element << " ";
L = L->next;
}
}
cout << L->element << endl;
/*第2种:递归方式(含尾递归)超过5000就程序崩溃*/
//if (L != NULL)
//{
// cout << L->element << " ";
// printList(L->next);
//}
/*第3种:递归方式(消除尾递归)*/
//top:
// if (L != NULL)
// {
// cout << L->element << " ";
// L = L->next;
// goto top;
// }
}
打印链表的函数printList中给出了3中实现方式,第1种循环方式在数据量为100万时依然能很好的运行,第二种带尾递归的方式大约在数据量为4800左右时程序就会崩溃,第3种使用goto语句的方式也在数据量很大时也没有问题,但通常不建议使用goto语句,因此推荐使用第1种循环方式打印链表,但在数据量不大时可以使用第2种递归方式,程序看起来会简洁一些!
上一篇: PHP递归统计上下级
下一篇: 不带头结点的单链表的建立