链表的概述，节点的定义，链表的创建，链表的遍历

目录

链表概述

链表创建

        节点的定义

        头节点的创建

        后续节点的创建并连接形成链表——头插法

        后续节点的创建并连接形成链表——尾插法

        链表的遍历——输出链表数据域内容

链表概述

        链表，别名 链式存储结构 或 单链表 ，用于存储逻辑关系为  一对一  的 同类型 的数据。 与顺序表不同，链表不限制数据的物理存储状态，物理存储空间可以不连续。换句话说，链表存储的数据元素，其物理存储位置是随机的分散的，由其指针域指向后续节点的地址来连接形成线性表的一种存储方式，像用链子把不同的物体连接在一起一样。

链表创建

        链表一般为单链表，由于需要同时记录数据和地址，故需要用到结构体来进行链表节点的数据类型定义。

        节点的定义

//节点的定义
struct Node{
    int data;    //数据域
    struct Node *next;    //指针域
};

//struct 关键词
//用于自定义数据类型

此时我们已经定义了数据类型，此类型用于创建链表的节点使用。

        头节点的创建

//主函数 
int main(){
	
    //定义节点类型的指针head，申请节点类型的空间大小，用作头节点。
	struct Node *head = (struct Node *)malloc(sizeof(struct Node));

    //此时只存在头节点，所以他的指针域指向为空。
	head->next = NULL;
	
	return 0;
} 

头节点数据域大部分情况下不做数据的存储，故不向其数据域存储内容。

        后续节点的创建并连接形成链表——头插法

//创建链表————头插法
void fun(struct Node *head) {
    
    //传参传的是头节点的地址，所以用指针接收地址
    if(head == NULL){
		printf("头指针未指向头节点");
		return;
	}
    
    printf("请输入链表长度");
	int len;
	scanf("%d",&len);

	//指针p指向头节点
	struct Node *p=head;
	struct Node *q;//临时节点

	for(int i=0; i<len; i++) {
        //临时指针申请空间
		q=(struct Node *)malloc(sizeof(struct Node));
        
		printf("请输入数据域元素:");//数据域存入内容
		scanf("%d",&q->data);

		q->next=p->next;//新节点q指向p的地址
		p->next=q;//p指向q
	}
}

创建的新节点连接在头节点后一个位置
导致链表内容被倒置
如    录入数据域内容： 1 2 3 4 5
        输出数据域内容： 5 4 3 2 1

        后续节点的创建并连接形成链表——尾插法

//创建链表————尾插法
void fun2(struct Node *head) {
	
    //传参传的是头节点的地址，所以用指针接收地址
	if(head == NULL){
		printf("头指针未指向头节点");
		return;
	}
	
	//指针p指向头节点
	struct Node *p=head;
	struct Node *q;//临时节点
	
	printf("请输入链表长度");
	int len;
	scanf("%d",&len);

	for(int i=0; i<len; i++) {
        //临时指针申请空间
		q=(struct Node *)malloc(sizeof(struct Node));
		printf("请输入元素:");
		scanf("%d",&q->data);

		q->next=NULL;//新节点q指针域指向空
		p->next=q;//p指向新节点q
		p=q;//p位置更新到q位置
	}
}

创建的新节点永远在链表的最后一位
输入顺序就是输出顺序
如    录入数据域内容： 1 2 3 4 5
        输出数据域内容： 1 2 3 4 5

        链表的遍历——输出链表数据域内容

//遍历链表
void shuchu(struct Node *head) {
	
    //传参传的是头节点的地址，所以用指针接收地址
	if(head == NULL){
		printf("头指针未指向头节点");
		return;
	}

	struct Node *p=head->next;    //结构体指针指向头节点的第一个节点

	//指针不为空进行循环
	while(p) {    //等价于 p != NULL;
		printf("%d  ",p->data);    //输出数据域内容
		p=p->next;    //指针后移指向下一个节点
	}
}

由于头节点的数据域不进行内容存储
故指针p直接指向头节点的下一个节点，即首元节点

2023年3月20日
持续更新