链表的创建和遍历

前言

链表是数据结构中非常重要的一种线性结构，它在线性结构中是离散存储的。在讲链表之前，先谈下typedef(为数据类型取别名)的用法，因为typedef在定义结构体时经常用到，可以起到很好的简化数据类型书写的作用。

实例说明：

#include<stdio.h>
typedef struct Student
{
	int sno;//学号
	char name[20];//姓名
}*PST,ST;//PST代表了struct Student *，ST代表了struct Student，即分别为其数据类型取别名
int main()
{
	ST s={1001,"张三"};
	PST pst=&s;
	printf("学号：%d\n姓名：%s\n",pst->sno,pst->name);
	return 0;
}

链表

链表可理解为n个结点(由数据域和指针域两部分组成)离散分配，彼此通过指针相连，每个结点只有一个前驱结点(除首节点外)，每个结点只有一个后继结点(除尾结点外)，且每个结点的数据类型相同。

链表中常见的专业术语有：首节点(第一个有效结点，即存放了有效数据)，尾结点(最后一个有效结点，指针域为NULL)，头结点(是在首结点前附加的一个节点，它没有存放有效数据，也没有存放有效结点个数。在首结点前加一个实际含义的头结点，可以方便我们对链表进行操作)，头指针(存放了头结点的地址，即指向了头结点)，尾指针(指向结点的地址)。我们通常只需要头指针通过一个函数来对链表进行处理，通过头指针就可以推算出链表的其他信息。链表的分类有：单链表(每个结点指针只能指向后一个结点--尾结点除外)，双链表(每个结点有两个指针域，前一个指针域指向前驱结点，后一个指针域指向后继结点)，循环链表(能通过任何一个结点找到其它结点--尾结点可以指向头结点)，还有非循环链表等；

结点的表示

typedef struct Node
{
    int data;//数据域
    struct Node *pNext;//指针域，指向本身和它一样的结构体(数据类型)
}NODE,*PNODE;//NODE等价于struct Node，PNODE等价于struct Node*

链表的创建和遍历

实例说明：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
	int data;//数据域
	struct Node *pNext;//指针域
}NODE,*PNODE;
PNODE CreateList(void);//void表示无形参
void TraverseList(PNODE);//此处省略形参名
int main()
{
    PNODE pHead=NULL;
    pHead=CreateList();//创建链表，并将返回的头结点的地址赋给pHead
    TraverseList(pHead);//遍历链表
	return 0;
}
PNODE CreateList(void)
{
	int len;//用来存放有效结点的个数
	int i;
	int val;//用来临时存放用户输入结点的值
    PNODE pHead=(PNODE)malloc(sizeof(NODE));//动态分配一个块内存，该内存用来存放头结点
    PNODE pNew;
	PNODE pTail=pHead;
    pTail->pNext=NULL;
	if(NULL==pHead)
	{
		printf("分配失败，程序终止！\n");
		exit(-1);//终止程序运行
	}
	printf("请输入您要创建链表的结点个数：len=");
	scanf("%d",&len);
	for(i=0;i<len;i++)
	{
		printf("请输入第%d个结点的值：",i+1);
		scanf("%d",&val);
        pNew=(PNODE)malloc(sizeof(NODE));//每循环一次，动态分配一个新临时结点
        if(NULL==pNew)
		{
			printf("分配失败，程序终止！\n");
			exit(-1);
		} 
        pNew->data=val;//为新节点数据域赋值
        pTail->pNext=pNew;//将新节点挂到尾结点后面
        pNew->pNext=NULL;//将新节点的指针域设为空
        pTail=pNew;//每次循环，让新节点成为尾节点
	}
	return pHead;	
}
void TraverseList(PNODE pHead)
{
	PNODE p=pHead->pNext;//此时p指向首节点
	while(p!=NULL)
	{
		printf("%d  ",p->data);
		p=p->pNext;//将p的指针域指向下一个结点（指针域为空时，说明已经到了尾结点）
	}
	printf("\n");
}

注意

1. 第一个结点的指针域指向下一个结点(地址)的整体信息。

2.若p指针指向某个结点(头结点和尾结点除外)，则p本身没有指针域，p指向的那个结构体变量(结点)才有指针域。