欢迎关注我的微信公众号【万能的小江江】
视频教程来自:https://www.bilibili.com/video/BV11s41167h6
链表
typedef的用法
#include <stdio.h>
typeof int ZHANGSAN; //为int多取一个名字，ZHANGSAN等价于int
//用法1
typeof struct Student
{
int sid;
char name[100];
char sex;
}ST; //struct student现在也等价于ST了
int main(void)
{
int i = 10; //等价于ZHANGSAN i = 10
ZHANGSAN j = 20;
printf("%d \n",j); //输出20
struct Student st; //等价于ST st
struct Student *PS = &st; //等价于ST *PS
ST st2;
st.sid = 200;
return 0;
}
//用法2，指针
type of struct Student
{
int sid;
char name[100];
char sex;
}* PST; //PST等价于struct Student *
// }* PST,ST; //这种写法的话，*PST相当于struct Student *，ST相当于struct Student
int main(void)
{
ST st;
PST ps = &st;
ps -> sid = 99;
printf("%d \n",ps -> sid); //输出99
return 0;
}链表的定义（离散存储）
定义：
n个节点离散分配（不连续），彼此通过指针相连
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点，尾节点没有后续节点
专业术语：
首节点：第一个有效的节点（存放有效数据）
尾节点：最后一个有效节点（指针域是空的）
头节点：第一个有效节点之前的节点（不存放有效数据，也不存放个数，作用是确定首节点的位置，方便对链表的操作）
头指针：指向头节点的指针变量
尾指针：指向尾节点的指针变量
注：头节点的数据类型和后面有效节点的是一样的
确定一个链表需要的参数：
只需要头指针，因为通过头指针可以推算出链表的其他信息
一个节点的生成：
通过指针域，一定能找到后面那个节点整体的信息
#include <stdio.h>
struct Node
{
int data; //数据域
struct Node * pNext; //指针域，指向和本身数据类型一样的另外一个节点
}Node, * PNode; //Node等价于struct Node，PNode等价于struct Node *
int main(void)
{
return 0;
}
//以上主要是讲了一个节点的数据类型如何来表示分类：
单链表：
每个节点只有一个指针域
双链表：
每个节点有两个指针域（前一个，后一个）
循环链表：
能通过任何节点找到其他所有节点（最后一个节点的指针域指向第一个节点）
非循环链表：
算法：
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
非循环单链表插入节点伪算法：
//写法1
r = p -> pNext;
p -> pNext = q;
q ->pNext = r;
//写法2
q -> pNext = p -> pNext;
p -> pNext = q;
非循环单链表删除节点伪算法：
//错误写法，会导致内存泄漏
p -> pNext = p -> pNext -> pNext;内存泄露：
//正确写法
r = p -> pNext;
p -> pNext = p -> pNext -> pNext;
free(r); //删除p指向节点占用的内存，不是删除p本身的内存链表的优缺点：
链表的创建和遍历算法演示：
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
typedef struct Node
{
int data; //数据域
struct Node *PNext; //指针域
}NODE, * PNODE; //NODE等价于struct Node PNODE等价于struct Node *
//函数声明
PNODE create_list(void);
void traverse_list(PNODE pHead);
int main(void)
{
PNODE pHead = NULL; //等价于struct Node * pHead = NULL;
pHead = create_list(); //create_list()功能：创建一个非循环单链表，并将该链表的值赋给pHead
traverse_list(pHead);
return 0;
}
//
PNODE create_list(void)
{
int len; //用来存放有效节点的个数
int i;
int val; //用来临时存放用户输入的结点的值
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
printf("请输入您需要生成的链表节点的个数：len = ");
scanf_s("%d", &len);
for (i = 0; i<len; ++i)
{
printf("请输入第%d个节点的值：", i + 1);
scanf_s("%d", &val);
}
return pHead;
}
//
PNODE create_list()
{
int len = 0;
int i = 0;
int val = 0;
//生成一个头节点
PNODE pHead = (PNODE) malloc(sizeof(NODE));
if(NULL = pHead)
{
printf("分配失败\n");
exit(-1);
}
PNODE pTail = pHead ;
pHead -> pNext = NULL; // 尾结点的指针域永远为NULL
printf("请输入您需要生成的链表节点个数：len = ");
scanf("%d",len);
//数组的内存是连续的，所以可以直接 malloc
//链表的内存是离散的，所以需要一个循环
for (i = 0; i < len; i++)
{
//获取用户信息
printf("请输入第 1 个节点的值: val= ");
scanf("%d",&val);
//生成第一个节点的地址为 pNew
PNODE pNew = (PNODE)malloc(sizeof(NODE));
//将用户信息存放
pNew -> data = val;
//将这个节点的首地址，挂到上一个节点指针域
pTail -> pNext = pNew;
// 每次创建，将尾结点的指针域指向 NUll
pNew -> pNext = NULL;
// 将pTail 后移
pTail = pNew;
}
return pHead; // 返回头指针
}
void traverse_list(PNODE pHead)
{
PNODE p = pHead->PNext;
while (NULL != p)
{
printf("%d", p->data);
p = p->PNext;
}
printf("\n");
return;
}注：代码有不可预见之错误，尚未修复
####
