数据结构之动态链表

链表的概念

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

链表和数组的作用相同，都是用来存储数据。数组在C语言中是一种很常见的数据结构,它是用来存储数据的,但是数组是一次分配完全部内存，而链表则是在需要时再分配内存，每次只分配出一个节点(Node)的内存，链表是由多个节点组成的，而每个节点都有俩个部分：数据区和指针区。

数据区：数据区是用来存储数据。

指针区：指针区是用来存储指向下一节点的指针。

链表:

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。即图中第二部分图形。

头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。但此图没有定义头节点。

单链表中可以没有头结点，但是不能没有头指针，头指针是必须的。

一般有头节点的链表是这样的：

向链表中加入节点

有三种方法:

插入到链表的头部，也就是头结点和首元结点中间；
插入到链表中间的某个位置；
插入到链表最末端；

下方代码为第一种插入方式:

#include <stdio.h>
#include <stdlib.h>

struct Node {     //定义结构体
	int data;     //数据域
	struct Node* next;    //定义指向结构体变量的指针next       指针域
};


//创建列表(创建链表结构体指针)
struct Node* createList()
{
	//头节点指针动态申请内存变为头节点结构体变量
	struct Node* headNode = (struct Node*)malloc(sizeof(struct Node)); //malloc函数用于动态内存分配
	//headNode成为了结构体变量
	headNode->next = NULL;    //节点为NULL表示是尾节点
	return headNode;         //返回链表表头
}

//创建节点(创建结构体节点指针)
struct Node* createNode(int data)   //要传参数-数据域
{
	//新节点指针动态申请内存变为新节点结构体变量
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;        //结构体变量里的data给形参 即数据域
	newNode->next = NULL;    
	return newNode;  
}


//打印节点
void printList(struct Node* headNode)
{
	struct Node* pMove = headNode->next;      
	while (pMove) 
	{
		printf("%d\t", pMove->data);     //走一节点打印一节点 即遍历一节点
		pMove = pMove->next;      //走一节点,指向下一节点
	}
	printf("\n");
}


//表头法插入节点     参数用来判断,你要插入哪个链表,插入节点的数据是多少   以头指针判断
void insertNodeByHead(struct Node* headNode, int data)   
{
	//1.创建插入的节点
	struct Node* newNode = createNode(data);
	//newNode为要插入头节点后的节点,所以就取代了第二个节点的位置所以newNode的下一节点就指向了原来第二节点
	newNode->next = headNode->next;     
	headNode->next = newNode;           
}


//删除指定位置节点
void deleteNodeByAppoin(struct Node* headNode, int posData)
{
	struct Node* posNode = headNode->next;
	struct Node* posNodeFront = headNode;
	if (posNode == NULL) {
		printf("无法删除,列表为空\n");
	}
	else {
		while (posNode->data != posData) {
			posNodeFront = posNode;
			posNode = posNodeFront->next;
			if (posNode == NULL) {
				printf("未找到指定位置,无法删除\n");
				return;
			}
		}
		posNodeFront->next = posNode->next;
		free(posNode);    //释放内存,即删除节点
	}
}


int main()
{
	//创建链表结构体指针
	struct Node* list = createList();     //调用写好的结构体链表指针赋值给结构体指针list 
	insertNodeByHead(list, 1);
	insertNodeByHead(list, 2);      //给链表插入节点数据
	insertNodeByHead(list, 3);
	printList(list);     //调用打印列表的函数输出
	deleteNodeByAppoin(list, 2);    //删除数值为2的节点
	printList(list);     //打印删除指定节点后的链表
	system("pause");
	return 0;
}

打印结果:

因为是顺序插入的,所以3在最前面。