vlambda博客
学习文章列表

一、认识链表

#include <stdio.h>

#include <stdlib.h>

//数据单独封装

struct MM

{

char name[20];

int age;

};

struct Node

{

int data;               //数据可以是任何类型

struct Node* next;  //指针域

};

int main()

{

//指针如何变成变量

int a = 1;

int *p = &a;

*p = 1003;

//2.动态内存申请

p = (int *)malloc(sizeof(int));

*p = 1004;

free(p);

p = NULL;

//无头链表  ：表头里面存放数据

struct Node Node1 = { 1, NULL };

struct Node Node2 = { 2, NULL };

struct Node Node3 = { 3, NULL };

Node1.next = &Node2;//Node1.next->&Node2;

Node2.next = &Node3;

struct Node* pMove = &Node1;

while (pMove != NULL)

{

printf("%d\t", pMove->data);

pMove = pMove->next;

}

system("pause");

return 0;

}

二、有头链表  ：表头里面没有存放任何数据

#include <stdio.h>

#include <stdlib.h>

//结构体的写法:某一种结构的单一个体

struct Node

{

int data;

struct Node* next;

};

//有表头的链表，创建表头--->创建结构体变量

struct Node* createHead()

{

//指针如何变成变量

struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));

//使用变量有一个规则:变量使用前必须要初始化

//结构体变量

//(*headNode).data//不做数据的初始化，因为第一个节点不存放数据

headNode->next = NULL;

return headNode;

}

//为插入做准备

//创建节点-->把别人的数据变成节点的模样

//节点模样-->结构体变量：和表头是一样的

struct Node* createNode(int data)

{

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

}

//表头插入

//想清楚表头插入是怎么插入

void insertByHead(struct Node* headNode,int data)

{

struct Node* newNode = createNode(data);

newNode->next = headNode->next;

headNode->next = newNode;

}

//指定位置删除

void deleteByAppoin(struct Node* headNode, int posData)   //posData：指定的数据

{

struct Node* posNodeLeft = headNode;

struct Node* posNode = headNode->next;

//两个条件顺序不能改变  NULL->data 会引发冲突

//posNode!=NULL 没有找到退出循环的条件

while (posNode != NULL&&posNode->data != posData)

{

//不等于，并排往下走

/*

//第一种写法

posNodeLeft=posNodeLeft->next;

posNode=posNode->next;

*/

posNodeLeft = posNode;

posNode = posNode->next;

}

//分析退出循环的条件

if (posNode == NULL)

{

printf("未找到指定位置,无法删除!\n");

return;

}

else

{

posNodeLeft->next = posNode->next;

free(posNode);

posNode = NULL;

printf("删除成功\n");

}

}

//查找结点

struct Node* searchByData(struct Node* headNode, int posData)

{

struct Node* pMove = headNode->next;

while (pMove != NULL&&pMove->data != posData)

{

pMove = pMove->next;

}

return pMove;

}

//删除所有的相同的数据

void deleteAll(struct Node* headNode, int posData)

{

while (searchByData(headNode, posData) != NULL)

{

deleteByAppoin(headNode, posData);

}

}

//打印函数封装

void printList(struct Node* headNode)

{

struct Node* pMove = headNode->next;//从第二个节点开始打印，因为第一个结点没有存数据

while (pMove != NULL)

{

printf("%d\t", pMove->data);

pMove = pMove->next;

}

printf("\n");

}

//表尾插入: 找到表尾：tailNode  tailNode->next=newNode;

void insertByTail(struct Node* headNode, int data)

{

struct Node* newNode = createNode(data);

struct Node* tailNode = headNode;

while (tailNode->next != NULL)//tailNode->next:表头里面没有数据，所以是下一个

{

tailNode = tailNode->next;

}

tailNode->next = newNode;

}

int main()

{

struct Node* list = createHead();

for (int i = 0; i < 3; i++)

{

insertByHead(list, i);

insertByHead(list, i);

}

printList(list);

deleteByAppoin(list, 1);  //只能删除第一个被找到的元素

printList(list);

deleteAll(list,2);

printList(list);

insertByTail(list, 100);

printList(list);

system("pause");

return 0;

}

三、有头链表再封装

#include <stdio.h>

#include <stdlib.h>

struct Node

{

int data;

struct Node* next;

};

struct Node* createHead()

{

struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));

headNode->next = NULL;

return headNode;

}

struct Node* createNode(int data)

{

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

}

//再封装的方式描述有头链表

struct list

{

//描述结构属性

struct Node* headNode;//表头

//万金油参数--->计数

int listSize;//记录当前链表中的节点个数

};

struct list* createList()

{

//创建过程就是描述最初的状态

struct list* List = (struct list *)malloc(sizeof(struct list));

List->headNode = createHead();

List->listSize = 0;

return List;

}

void insertByHead(struct list* List, int data)

{

if (List != NULL)

{

struct Node* newNode = createNode(data);

newNode->next = List->headNode->next;

List->headNode->next = newNode;

List->listSize++;

}

}

//万金油函数

int empty(struct list* List)//判断List是否为空

{

return List->listSize == 0;

}

int size(struct list* List)

{

return List->listSize;

}

void  printList(struct list* List)

{

if (List != NULL)

{

struct Node* pMove = List->headNode->next;

while (pMove != NULL)

{

printf("%d\t", pMove->data);

pMove = pMove->next;

}

}

printf("\n");

}

int main()

{

struct list* List = createList();

for (int i = 0; i < 3; i++)

{

insertByHead(List, i);

}

printList(List);

printf("%d", size(List));

system("pause");

return 0;

}

四、无头链表

//无头链表:一般采用再封装的方式

//二级指针写法

#include <stdio.h>

#include <stdlib.h>

struct Node

{

int data;

struct Node* next;

};

struct Node* createNode(int data)

{

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

}

struct List

{

struct Node* frontNode;//永远指向表头

struct Node* tailNode;//永远都指向表尾

int listSize;

};

//创建过程就是描述最初状态

struct List* createList()

{

struct  List*  list = (struct List*)malloc(sizeof(struct List));

list->listSize = 0;

list->frontNode = NULL;

list->tailNode = NULL;

return list;

}

void insertByHead(struct List* list, int data)

{

struct Node* newNode = createNode(data);

if (list->listSize == 0)

{

list->frontNode = newNode;

list->tailNode = newNode;

}

else

{

newNode->next = list->frontNode;

list->frontNode = newNode;//原来表头的标记移到新的头部

}

list->listSize++;

}

void insertByTail(struct List* list, int data)

{

struct Node* newNode = createNode(data);

if (list->listSize == 0)

{

list->frontNode = newNode;

list->tailNode = newNode;

}

else

{

list->tailNode->next = newNode;

list->tailNode = newNode;//表尾要移动到新的尾部

}

list->listSize++;

}

//表头删除

void deleteByHead(struct List* list)

{

if (list->listSize != 0)

{

struct Node* nextNode = list->frontNode->next;

free(list->frontNode);

list->frontNode = nextNode;

if (nextNode == NULL)

list->tailNode = NULL;

list->listSize--;

}

}

//1.表尾删除

//2.指定位置删除-->有坑

//3.指定位置插入-->有坑

void printList(struct List* list)

{

struct Node* pMove = list->frontNode;

while (pMove != NULL)

{

printf("%d\t", pMove->data);

pMove = pMove->next;

}

printf("\n");

}

//容器-->链表--->数组

//有序链表创建

//按照序号的方式操作链表

int main()

{

struct List* list = createList();

for (int i = 0; i < 3; i++)

{

insertByHead(list, i);

}

printList(list);

deleteByHead(list);

deleteByHead(list);

deleteByHead(list);

insertByTail(list, 34);

insertByHead(list, 33);

printList(list);

system("pause");

return 0;

}

五、无头链表二级指针

#include <stdio.h>

#include <stdlib.h>

struct Node

{

int data;

struct Node* next;

};

//没有返回值的写法

struct Node* createNode(int data)

{

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); 

newNode->data = data;

newNode->next = NULL;

return newNode;

}

void insertByNode(struct Node** headNode, int data)

{

struct Node* newNode = createNode(data);

if (*headNode == NULL)//表示当前结点就是表头

{

*headNode = newNode;

}

else

{

newNode->next = *headNode;

*headNode = newNode;

}

}

void printList(struct Node* headNode)

{

struct Node* pMove = headNode;

while (pMove!=NULL)

{

printf("%d\t", pMove->data);

pMove = pMove->next;

}

printf("\n");

}

int main()

{

struct Node* headNode = NULL;

for (int i = 0; i < 3; i++)

{

insertByNode(&headNode, i);

}

printList(headNode);

system("pause");

return 0;

}