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

不带头结点的链表的建立和打印

程序员文章站 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种递归方式,程序看起来会简洁一些!