一.typedef

typedef struct Student{
    int sid;
    int age;
}ST;

struct Student student;//<==>ST student;

typedef struct Student{
    int sid;
    int age;
}*PST;
struct Student *p;//<==>PST *p;
//PST<==>struct Student *

typedef struct Student{
    int sid;
    int age;
}*PST,ST;
//效果是上面的整合

二.链表

1.定义

n个节点离散分配
批次通过指针相连
每隔节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点，尾节点没有后续节点
[离散存储]

2.专业术语

首节点：第一个有效的节点
尾节点：最后一个有效节点
头结点：第一个有效节点之前的节点
- 没有存放有效数据
头指针：指向头节点的指针变量
尾指针：指向尾节点的指针变量

3.确定一个链表需要的参数

只需要一个头指针

👉为什么不用头结点

因为头结点的数据类型和后面有数据域的节点的数据类型是一样的(虽然头结点没有数据域，但是他会有垃圾值，会占内存)
头指针只占四个字节来存放头结点的地址

4.节点

都要有一个指针域和数据域
结构体的某一个成员指向的是跟它一摸一样的数据类型的数据
要为创建的每一个节点申请空间

struct Node
{
    int data;//数据域
    struct Node *pNext;//指针域
};

5.分类

单链表
双链表：每个节点有两个指针域
循环链表：能通过任何一个节点找到其他节点
非循环链表

三.作用

1.创建/初始化

需要用到的变量：最初创建的链表的长度len、每个结构体数据域的数据val、头节点pHead、尾节点pTail

int len;
for(int i=0;i<len;i++)
{
   //xxxxxxx
}

pNew->data=val;

pTail=pHead
- 可以理解为用尾指针是针线，把原有链表最后一个节点和新加入的节点连接起来

2.插入

需要用到的参数：头结点，新插入的结构体的位置，新插入的结构体的数据域中的数值
需要考虑的问题：要怎么通过输入的pos找到要指向新插入结构体位置的结构体指针

PNODE p=pHead;
while(p!=NULL && i<pos-1)	//i<p-1就是让p指向要插入位置的上一个结构体 
	{
		p=p->pNext;
		i++;
	}
/*
条件①：确保是在一个不是空的结构体后插入的
条件②：p要指向即将要插入的位置的前一个结构体
*/

我们要通过遍历的方式找到目标结构体，假设我们要插入到pos=3

i<pos=1这里 i=0时 p=第一个有效结构体
i=1时，p=第二个有效结构体
i=2不符合循环条件
所以while结束后，p就是第二个有效结构体的指针变量

3.删除

删除是通过修改前一个结构体指针的指向来删除的
所以删除的位置的前一个指针的指向不能是NULL
如果要删除的对象的下一个已经是NULL了，那么就不会继续遍历下去
vs插入，如果要插入的位置是最后一个，即p->

四.全部代码

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

typedef struct Node{
	int data;
	struct Node *pNext;
}NODE,*PNODE;

//函数声明
PNODE creatList(void);
void traverseList(PNODE pHead);
bool isEmpty(PNODE pHead);
int lengthList(PNODE pHead);
bool insertList(PNODE pHead,int pos,int val);
bool deleteList(PNODE pHead,int pos,int *pVal);
void sortList(PNODE pHead);
int lengthList(PNODE pHead);

int main(void)
{
	int val;
	PNODE pHead=NULL;
	
	pHead=creatList();
	
	//traverseList(pHead);
/*	
	if(isEmpty(pHead))
		printf("链表为空！\n");
	else
		printf("链表不空！\n");
	return 0;
*/
/*
	int len=lengthList(pHead);	
	printf("长链表的长度是%d",len);	
*/
	
	//sortList(pHead);
	//traverseList(pHead);
	
	//insertList(pHead,4,23);
	//traverseList(pHead);
	
	deleteList(pHead,4,&val);
	traverseList(pHead);
	
	return 0;
}

PNODE creatList(void)
{
	int len;
	int i;
	int val;

	PNODE pHead=(PNODE)malloc(sizeof(NODE));
	if(pHead==NULL)
	{
		printf("内存分配失败！\n");
		exit(-1);
	}
	PNODE pTail=pHead;
	pTail->pNext=NULL;
	
	printf("请输入您需要生成的链表节点的个数：len=");
	scanf("%d",&len);
	
	for(i=0;i<len;i++)
	{
		printf("%请输入第%d个节点的值",i+1);
		scanf("%d",&val);
		
		PNODE pNew=(PNODE)malloc(sizeof(NODE));
		if(pNew==NULL)
		{
			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;
	while(p!=NULL)
	{	
		printf("%d\t",p->data);
		p=p->pNext;
	} 
}

bool isEmpty(PNODE pHead)
{
	if(NULL==pHead->pNext)
	{
		return true;
	}
	else
		return false;
}

int lengthList(PNODE pHead)
{
	PNODE p=pHead->pNext;
	int len=0;
	
	while(p!=NULL)
	{
		++len;
		p=p->pNext;
	}
	return len;
}

void sortList(PNODE pHead)
{
	PNODE p=pHead->pNext;
	PNODE q;
	
	int i=0,j=0;
	int temp;
	int len=lengthList(pHead);
	
	for(i=0;i<len-1;i++)
	{
		for(j=i+1,q=p->pNext;j<len;j++)
		{
			if(p->data > q->data)
			{
				temp=p->data;
				p->data=q->data;
				q->data=temp;	
			}
			q=q->pNext;
		}
		p=p->pNext;
	} 
	return;
}

bool insertList(PNODE pHead,int pos,int val)
{
	int i=0;
	PNODE p=pHead;
	
	while(p!=NULL && i<pos-1)	//i<p-1就是让p指向要插入位置的上一个结构体 
	{
		p=p->pNext;
		i++;
	}
	if(i>pos-1||NULL==p)
		return false;
	
	PNODE pNew=(PNODE)malloc(sizeof(NODE));
	if(pNew==NULL)
	{
		printf("分配失败！\n");
		exit(-1);
	} 
	pNew->data=val;
	PNODE q=p->pNext;
	p->pNext=pNew;
	pNew->pNext=q;
	return;
} 

bool deleteList(PNODE pHead,int pos,int *pVal)
{
	int i=0;
	PNODE p=pHead;
	
	while(p->pNext!=NULL && i<pos-1)	//i<p-1就是让p指向要删除位置的上一个结构体 
	{
		p=p->pNext;
		i++;
	}
	if(i>pos-1||NULL==p->pNext)
		return false;
	
	PNODE pNew=(PNODE)malloc(sizeof(NODE));
	if(pNew==NULL)
	{
		printf("分配失败！\n");
		exit(-1);
	} 
	PNODE q=p->pNext;
	*pVal=q->data;
	p->pNext=p->pNext->pNext;
	q=NULL;
	return;
}