【单链表创建】C语言


1、什么是单链表:


1、单链表是一种链式存取的数据结构,链表中的数据是用结点表示。每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表(单链表),单链表是链式存取的结构。
2、 整个链表的存取从头指针开始,最后结点指针为空(NULL)。

1.1单链表结点结构:
在这里插入图片描述
定义结点类型:

//定义结点类型
typedef struct Node{
	int data;//数据域
	struct Node *next;//指针域
}Node,*LinkList; //Node表示结点的类型,LinkedList表示指向Node结点类型的指针类型

2.单链表初始化:

LinkList listinit()
{
    Node *L;
    L=(LinkList)malloc(sizeof(Node));//开辟空间,申请新结点
    if(L==NULL)
    {   //判断是否开辟空间失败,这一步很有必要
        printf("申请空间失败");
        //exit(0);  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL; //指针指向空
}

3、单链表建立:

(1)头插法建立单链表:

头插入法最终得到的结果是逆序的。

LinkList LinkListCreatH(LinkList &L)
{
	L=(LinkList)malloc(sizeof(Node));
	L->next=NULL;//头结点 
	int n;
	
	printf("请输入链表的长度,即元素个数:");
	scanf("%d",&n);
	printf("请输入数据: ");
	while(n)
	{
		Node *p;
		p=(LinkList)malloc(sizeof(Node));//生成新结点
		scanf("%d",&p->data);//输入元素值
		p->next=L->next;//插入到表头
		L->next=p;
		n--;
	}
	return L;
}

在这里插入图片描述
(2)尾插法建立单链表:

该方法是将新结点逐个插入到当前链表的表尾上,为此必须增加一个尾指针 r, 使其始终指向当前链表的尾结点,否则就无法正确的表达链表。

LinkList LinkListCreatT() 
{
    L = (LinkList)malloc(sizeof(Node)); //申请头结点空间
    L->next = NULL; //初始化一个空链表
    Node *r;//尾指针
    r = L; //r始终指向终端结点,开始时指向头结点
    int n; //x为链表数据域中的数据
    printf("请输入链表的长度,即元素个数:");
	scanf("%d",&n);
	printf("请输入数据: ");
    while(n) 
    {
        Node *p;
        p = (LinkList)malloc(sizeof(Node)); //申请新的结点
        scanf("%d",&p->data); //结点数据域赋值
        r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
        n--;
    }
    r->next = NULL;
    return L;
}

在这里插入图片描述

4、完整代码:

#include<stdio.h>
#include<stdlib.h>//malloc的头文件 

//定义结点类型
typedef struct Node{
	int data;
	struct Node *next;
}Node,*LinkList; 

LinkList listinit(LinkList &L)
{
    L=(Node*)malloc(sizeof(Node));      //开辟空间 
    if(L==NULL)
	{                     //判断是否开辟空间失败,这一步很有必要
        printf("申请空间失败");
        //exit(0);                  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL;       //指针指向空
    return L;
}

//头插法,建立单链表 
LinkList LinkListCreatH(LinkList &L)
{
	L=(LinkList)malloc(sizeof(Node));
	L->next=NULL;//头结点 
	int n;
	
	printf("请输入链表的长度,即元素个数:");
	scanf("%d",&n);
	printf("请输入数据: ");
	while(n)
	{
		Node *p;
		p=(LinkList)malloc(sizeof(Node));
		scanf("%d",&p->data);
		p->next=L->next;
		L->next=p;
		n--;
	}
	return L;
}

尾插法
//LinkList LinkListCreatT(LinkList &L) 
//{
//    L = (LinkList)malloc(sizeof(Node)); //申请头结点空间
//    L->next = NULL; //初始化一个空链表
//    Node *r;//尾指针
//    r = L; //r始终指向终端结点,开始时指向头结点
//    int n; //x为链表数据域中的数据
//    printf("请输入链表的长度,即元素个数:");
//	scanf("%d",&n);
//	printf("请输入数据: ");
//    while(n) 
//    {
//        Node *p;
//        p = (LinkList)malloc(sizeof(Node)); //申请新的结点
//        scanf("%d",&p->data); //结点数据域赋值
//        r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL
//        r = p;
//        n--;
//    }
//    r->next = NULL;
//    return L;
//} 
//输出单链表 
void PrintList(LinkList &L)
{
	Node *q;
	int i=1;
	q=L->next;
	printf("链表元素:");
	while(q)
	{
		printf("[元素%d:%d] ",i,q->data);
		i++;
		q=q->next;
	}
	printf("n");
}

int main()
{
	LinkList L;
	//建立单链表 
	LinkListCreatH(L);
	PrintList(L);
}