【链表】单向链表(一）

一、链表的定义

（1）链式储存，顺序访问的线性表。数组是顺序储存，随机访问。

（2）组成链表的元素：节点，节点包括数据域和指针域。

其数据结构的定义：

struct link

{
     int data;                         //数据域：储存节点数据信息

     struct link *next;            //指针域：储存直接后续节点的地址,下一个节点也是这样的类型

}

（3）单向链表 / 线性链表：由一个指针域和n个节点连接形成的链表

二、单向链表的建立

1.建立方式：向链表中添加节点

为建立新节点动态申请内存 -->  让指针变量p指向新节点  --> 将新节点添加到节点中  

//向链表添加节点数据的程序
 
#include<stdio.h>
#include<stdlib.h>

struct link*AppendNode(struct link*head);
void DisplayNode(struct link*head);
void DeleteMemory(struct link*head);

struct link
{
	int data;
	struct link*next;
}; 

int main()
{
	int i = 0;
	char c;
	struct link*head = NULL;           //链表头指针
	
	printf("Do you want to append a new node (Y/N)? ");
	scanf(" %c",&c);                    //%c前有一个空格 
	while(c == 'Y' || c == 'y')
	{
		head = AppendNode(head);
		DisplayNode(head);
		printf("Do you want to append a new node (Y/N)?");
		scanf(" %c",&c);
		i++;	
	} 
	printf("%d new node have been appended",i);
	DeleteMemory(head);
}

//新建一个节点并添加到链表末尾，返回添加节点后链表的头指针
struct link*AppendNode(struct link*head)
{
	struct link*p = NULL,*pr = head; 
	int data;                          //新建节点的数据 
	p = (struct link*)malloc(sizeof(struct link));//让P指向新建节点
	if(p == NULL)                      //新建节点失败 
	{
		printf("No enough memory to allocate!\n");
		exit(0);                       //正常退出程序	
	}  
	
	if(head == NULL)                   //若原链表为空
	{
		head = p;                      //将 p 设置为头节点 
    }
    else                               //若原链表非空,将新建节点添加到表尾
	{
		while(pr->next != NULL)        //若未到表尾，则移动Pr直到表尾 
		{
			pr = pr->next;
		} 
		pr->next = p;                  //让末节点的指针域指向新建节点，实现将新建节点添加到表尾
	}
	
	printf("Input node data:");
	scanf("%d",&data);                 //输入节点数据
	p->data = data;                    //将新建节点的数据域赋值为输入的节点数据值
	p->next = NULL;                    //将新建节点设置为表尾
	return head;
}

//显示链表中所有节点的节点号和该节点中的所有数据内容
void DisplayNode(struct link*head)
{
	struct link*p = head;
	int i = 1;  
	while(p != NULL)                   //不是表尾，则循环打印节点额值 
	{
		printf("%5d%10d\n",i,p->data); //打印第i个节点的数据 
		p = p->next;                   //让p指向下一个节点 
		i++; 
	}
} 

//释放head指向的链表中所有节点占用的内存
void DeleteMemory(struct link*head)
{
	struct link*p = head,*pr = NULL;
	while(p != NULL)                   //若不是表尾，则释放节点内存 
	{
		pr = p;                        //在pr中保存当前节点的指针
		p = p->next;                   //让p指向下一个节点
		free(pr);                      //释放pr指向的当前节点的内存		
	}
}