链表指一种数据结构，相对于数组来说，链表存储数据时，空间不连续，具有省空间的优点。
想要操作链表，需要先掌握手动开辟空间的 *** 。通过malloc可以手动开辟一个堆区空间
malloc函数功能如下：
malloc, free- allocate and free dynamic memory #include <stdlib.h> void *malloc(size_t size); size_t size:指定开辟空间的大小 The malloc() function allocates size bytes and returns a pointer to the allo‐ cated memory. The memory is not ini‐ tialized. If size is 0, then malloc() returns either NULL, void *：被称为空指针类型，可以理解为万能指针，可以转换为任何数据类型， 通过强制转换 用来接收malloc开辟空间返回的首地址 void free(void *ptr);
使用案例：
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Person { int age; char name[20]; }Per,*pPer; int main() { Per per; pPer p=NULL; p = (pPer)malloc(sizeof(Per)); scanf("%d%s", &per.age, per.name); printf("%s\t%d\n", per.name, per.age); scanf("%d%s", &p->age, p->name); printf("%s\t%d\n", p->name, p->age); system("pause"); return 0; }
单向链表操作：
1、先确定链表节点的数据结构
链表是结构体形式的数据结构
链表数据结构
typedef struct info{ char name[20]; int age; }Info,*pInfo; typedef struct Student{ Info msg; struct Student *next; }Stu,*pStu;
2、确定使用有头还是无头链表，创建链表头
有头和无头的区别就是链表头是否用来存储数据
创建表头
pStu CreatHead() { pStu head= (pStu)malloc(sizeof(Stu)); head->msg.age=0; strcpy(head->msg.name," "); head->next=NULL; return head; }
3、创建子节点
pStu CreateNode(Info msg) { pStu iNode=(pStu)malloc(sizeof(Stu)); iNode->msg = msg; iNode->next = NULL; return iNode ; }
4、将子节点插入到链表中
注意链表中的操作遵循四字法则“先连后断”
1)头插法
每次插入节点的时候都是将节点插入到头节点的后面，最终解过为逆序
void InserHead(pStu head,Info msg) { pStu NewNode=CreateNode (msg); NewNode->next=head->next; head ->next=NewNode; }
2)尾插法
每次插入节点的时候都是将节点插入到尾节点的后面，最终解过为顺序
void InserEnd(pStu head,Info msg) { pStu pMove=head; pStu NewNode=CreateNode (msg); if(head->next==NULL) head->next = NewNode; while(pMove->next!=NULL) { pMove =pMove->next; } pMove->next=NewNode; NewNode->next=NULL; }
3)中间插
void InserMid(pStu head,Info msg,int number) { int i=1; pStu pMove=head; pStu NewNode=CreateNode (msg); if(head->next==NULL) head->next = NewNode; while(i!=number) { i++; pMove =pMove->next; } NewNode->next=pMove->next; pMove->next=NewNode; }
4）查找
pStu SearchNode(pStu head,Info msg) { pStu pMove =head->next; if(head->next==NULL) printf("链表为空"); while(pMove->next!=NULL) { if(strcmp(pMove->msg.name,msg.name)==0) { return pMove; break; } pMove=pMove->next; if(pMove->next==NULL) { return NULL; } } }
5）修改
void ChangeNode(pStu head, Info msg) { pStu tmp = SearchNode(head, msg); if (tmp == NULL) { printf("查无此信息\n"); } else { printf("请输入修改信息：\n"); scanf("%s", tmp->msg.name); } }
6）删除
//删除信息 void DeletehNode(pStu head, Info msg) { pStu tmp = head; pStu pMove = head->next; if (head->next == NULL) { printf("链表为空\n"); } while (pMove->next != NULL) { if (strcmp(pMove->msg.name, msg.name) == 0) { break; } tmp = pMove; pMove = pMove->next; if (pMove == NULL) { printf("查无此信息\n"); return ; } } tmp->next = pMove->next; free(pMove); printf("free success\n"); }
7，遍历所有节点
//遍历所有节点 void Print(pStu head) { int i = 1; pStu pMove = head->next; while (pMove!= NULL) { printf("第%d个节点内的数据:name=%s\tage=%d\n", i,pMove->msg.name, pMove->msg.age); i++; pMove = pMove->next; } }
