02黑马数据结构笔记之单向链表搭建(list)
1 思路：以STL的容器list类似，将各个数据节点存放在链表当中。实现是靠一个结构体来管理各个数据节点 。
//定义一个节点类型
typedef struct Node{
//接收任何数据
void* data;
struct Node *next;
}SNode;
//定义一个结构体管理链表
typedef struct LinkList{
SNode *head;
int size; //链表大小
}SList; //和动态数组比，需要容量吗？ 不需要，动态且内存不连续，在关系上线性
代码实现：
1）头文件.h:
#ifndef MYLIST_H
#define MYLIST_H
#include<stdio.h>
#include<stdlib.h>
//定义一个节点类型
typedef struct Node{
//接收任何数据
void* data;
struct Node *next;
}SNode;
//定义一个结构体管理链表
typedef struct LinkList{
SNode *head;
int size; //链表大小
}SList; //和动态数组比，需要容量吗？ 不需要，动态且内存不连续，在关系上线性
//使用函数指针对万能数据打印
typedef void(*PrintList)(void* data);
//链表初始化
SList *List_Init();
//链表的打印
int Print_List(SList *l,PrintList print);
//插入链表
int Insert_List(SList *l,int pos,void* data);
//删除一个指定位置链表节点
int Del_List_One(SList *l,int pos);
//查找链表
int Find_List(SList *l,void* data);
//返回第一个节点
void *Get_Effitive_First(SList *l);
//返回链表大小
int Get_Size(SList *l);
//销毁内存
int Destory_List(SList *l);
#endif
2).cpp文件：
#include"MyList.h"
//链表初始化
SList *List_Init(){
//给结构体赋值
SList *list=(SList *)malloc(sizeof(SList));
list->head=(SNode *)malloc(sizeof(SNode));
list->size=0;
//给头结点赋值
list->head->data=NULL;
list->head->next=NULL;
return list;
}
//链表的打印
int Print_List(SList *l,PrintList print){
if(l==NULL){
return -1;
}
SNode *pCur=l->head->next;
while(pCur!=NULL){
print(pCur->data); //将参数传给自定义函数打印
pCur=pCur->next;
}
return 0;
}
//利用下标插入链表
int Insert_List(SList *l,int pos,void* data){
//链表为空，直接返回
if(l==NULL ){
return -1;
}
//如果下标越界，则插入尾部
if(pos<0 || pos >= l->size){
pos=l->size;
}
//插入
//1.先找到插入点的前一节点——————与C语言用两个节点插入的有点差别，但道理是一样的
SNode *pCur=l->head;
for(int i=0;i<pos-1;i++){
pCur=pCur->next;
}
//2.创建新节点
SNode *New=(SNode*)malloc(sizeof(SNode));
New->data=data;
New->next=NULL;
//3.与链表建立关系
New->next=pCur->next;
pCur->next=New;
l->size++;
return 0;
}
//删除一个指定位置链表节点
int Del_List_One(SList *l,int pos){
if(l==NULL){
return -1;
}
if(pos<0|| pos >= l->size){
return -1;
}
//找到要删除的节点的前一节点
SNode *pPre=l->head;
for(int i=0;i<pos-1;i++){
pPre=pPre->next;
}
//使用临时变量删除pos节点
SNode *pCur=pPre->next;
//删除
pPre->next=pCur->next;
free(pCur);
pCur->next=NULL;
l->size--;
return 0;
}
//查找链表 返回第一个相等数据的下标
int Find_List(SList *l,void* data){
if(l==NULL){
return -1;
}
//计算节点的返回值下标
int count=0;
SNode *pCur=l->head->next;
while(pCur!=NULL){
if(pCur->data==data){
break;
}
pCur=pCur->next;
count++;
}
//判断是否找到
if(count==l->size){
printf("找到链表尾部,没找到\n");
return -1;
}
return count;
}
//返回第一个节点
void *Get_Effitive_First(SList *l){
return l->head->next->data;
}
//返回链表大小
int Get_Size(SList *l){
return l->size;
}
//销毁内存
int Destory_List(SList *l){
if(l==NULL){
return -1;
}
//销毁内存
while(l->head!=NULL){
SNode *pCur=l->head->next;
free(l->head);
//l->head->next=NULL; //可以不要
l->head=pCur;
}
//最后释放管理链表的结构体内存
free(l);
return 0;
}
3）主函数测试：
#include"MyList.h"
//自定义数据类型
typedef struct Student{
char name[64];
int age;
int score;
}Stu;
//回调打印函数 打印时需要用户自定义一个打印函数传进来
void MyPrint(void *data){
//将void*数据转成用户自定义数据
Stu *s=(Stu*)data;
printf("名字：%s 年龄：%d 分数：%d\n",s->name,s->age,s->score);
}
void test01(){
//创建链表
SList *list=List_Init();
//创建数据
Stu s1={"aaa",18,100};
Stu s2={"bbb",19,77};
Stu s3={"ccc",20,88};
Stu s4={"ddd",22,99};
Stu s5={"eee",12,59};
//插入数据 因为是void*,所以要传地址
Insert_List(list,0,&s1);
Insert_List(list,0,&s2);
Insert_List(list,0,&s3);
Insert_List(list,0,&s4);
Insert_List(list,0,&s5);
//打印数据 需要给函数指针传函数名调用该自定义函数
Print_List(list,MyPrint);
printf("============\n");
//删除
Del_List_One(list,3);
Print_List(list,MyPrint);
//返回第一个有效节点
printf("============\n");
Stu *s=(Stu*)Get_Effitive_First(list);
printf("名字：%s 年龄：%d 分数：%d\n",s->name,s->age,s->score);
printf("============\n");
//查找
int pos=Find_List(list,&s2);
printf("查找到的节点下标：%d\n",pos);
Del_List_One(list,pos);
Print_List(list,MyPrint);
//返回链表大小
int size=Get_Size(list);
printf("链表大小为：%d\n",size);
//销毁内存
Destory_List(list);
}
int main(){
test01();
return 0;
}
