杭州电商网站建设,品牌网络推广公司,找谁做网站比较好,深圳工业设计薪资#x1f354;链表基础知识
1.概念#xff1a;链表是由多个节点链接构成的#xff0c;节点包含数据域和指针域#xff0c;指针域上存放的指针指向下一个节点 2.链表的种类#xff1a;按单向或双向、带头或不带头、循环或不循环分为多个种类 3.特点#xff1a;无法直接找到…链表基础知识
1.概念链表是由多个节点链接构成的节点包含数据域和指针域指针域上存放的指针指向下一个节点 2.链表的种类按单向或双向、带头或不带头、循环或不循环分为多个种类 3.特点无法直接找到结点但可以快速插入、删除节点尤其适用于头插效率块于其它方式 4.应用p2p网络文件系统作为其他数据结构的基础数据结构
本篇文章是关于带头单向链表的
带头单链表
头可以理解为哨兵位。哨兵不用干其他活放好哨就行而哨兵位不存储有效数据只提供指向下一个节点即存放有效数据的第一个节点的指针。
以一个学生信息表为例用单链表存储学生信息
定义部分
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdlib.h
typedef struct {int age;int height;double weight;
}Student;
typedef struct node {Student stu;struct node* next;
}Node;函数部分
一、辅助操作函数
1.结点的拷贝函数
//节点的拷贝函数
void CopyValue(Student* s1, Student* s2){s1-age s2-age;s1-height s2-height;s1-weight s2-weight;
}
2.输入学生信息函数
//输入学生信息
void InputValue(Student* stu) {if (!stu)return;printf(学生的年龄身高体重\n);scanf(%d%d%lf, stu-age, stu-height, stu-weight);
}3.打印信息函数
//输出每个节点的信息
void DisplayNode(Student* stu) {printf(年龄%-5d 身高%-5d 体重%-5lf\n, stu-age, stu-height, stu-weight);
}4.打印单链表
//打印单链表
void DisplayLink(Node* head) {//1.判断链表是否为空为空直接返回if (!head)return;//2.打印每个节点信息Node* p head-next;while (p ! NULL) {DisplayNode(p-stu);p p-next;}
}二、创建节点创建、销毁链表
1.创建节点
//创建节点
Node* CreateNode(Student* stu){//1.申请一份空间Node* node (Node*)malloc(sizeof(Node));//2.判断空间是否申请成功if (!node) {printf(内存不足\n);return NULL;}//3.初始化结节中的数据域即学生信息CopyValue(node-stu, stu);node-next NULL;//4.返回创建的结点return node;
}2.创建链表
//创建链表
Node* CreateLink() {Student stu { 0,0,0 };//该组数据不是有效数据//1.创建头结点Node* head CreateNode(stu);if (!head) exit(-1);//2.创建其他结点连接到头结点构成链表int tag 0;Node* pnew, * tail head;printf(是否创建新结点继续添加输入1否则输入0\n);scanf(%d, tag);while (tag ! 0) {InputValue(stu);pnewCreateNode(stu);tail-next pnew;tail pnew;printf(是否创建新结点继续添加输入1否则输入0\n);scanf(%d, tag);}return head;
}3.销毁链表
//销毁链表
void FreeLink(Node* head) {//1.判断链表是否为空为空则返回if (head NULL)return;//如果非空则逐个结点释放Node* p, * q;p head;while (p-next ! NULL) {q p-next;p-next q-next;free(q);}free(head);
}三、增删查改——增
在指定节点后面插入节点
//在指定位置插入节点
void InsertNode(Node* head, Node* pnew,int i) {//1.判断链表是否为空为空拒绝插入if (!head)return;//2.判断结点是否为空为空拒绝插入if (!pnew)return;//3.遍历链表插入指定位置Node* p head;for (int n 0;n i;n) {p p-next;}pnew-next p-next;p-next pnew;
}只能对当前指针所在节点处的后面的结点进行操作 如果想在指定节点前面插入节点只需要改变for循环中的初始值让指针停留在指定节点的前置节点处就可以插入到指定节点的前面了
四、增删查改——删
删除指定位置节点
//删除指定位置节点
void DeleteNode(Node* head, int i) {//1.判断链表是否为空为空直接返回if (!head)return;//2.遍历链表找到要删除的位置Node *phead,*q;for (int n 1;n ip-next!NULL;n) {p p-next;//当p等于NULL了说明把整条链表都遍历完了还没有找到}//3.如果找到了该位置删除找不到就返回if (!p)return;q p-next;p-next q-next;free(q);
}只能对当前指针所在节点处的后面的结点进行操作 n从1开始指针停留位置就是被删除节点的前置节点从而可以删除掉指定节点如果n从0开始指针停留位置是指定节点此时就无法删除该位置了此时的指针只能掌控住指向节点之后的节点。
五、增删查改——查与改
比较两节点内容
//比较两节点内容
int Compare(Student* s1, Student* s2) {if (s1 NULL || !s2)return -1;if (s1-age s2-age s1-height s2-height s1-weight s2-weight)return 1;return 0;
}根据指定信息查找结点
//根据指定信息查找节点
int CheckNode(Node* head, Student* stu) {//1.链表与查找的节点不为空if (!head || !stu)return 0;//2.遍历单链表找到是否有相同的节点Node* p head-next;int ret 1;int m 0;while (p!NULL) {m Compare(p-stu, stu);if (m 1)return ret;p p-next;ret;}return 0;
}改变指定位置的节点信息
//改变指定位置的节点信息
void ModifyValue(Node* head,Student*stu, int input) {//1.判断第一个节点是否存在if (!head || head-next NULL)return;//2.遍历链表找到节点位置Node* p head-next;for (int i 1;i input;i) {p p-next;}//3.改变信息p-stu.age stu-age;p-stu.height stu-height;p-stu.weight stu-weight;
}测试带头单链表完整程序
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdlib.h
typedef struct {int age;int height;double weight;
}Student;
typedef struct node {Student stu;struct node* next;
}Node;
//节点的拷贝函数
void CopyValue(Student* s1, Student* s2){s1-age s2-age;s1-height s2-height;s1-weight s2-weight;
}
//输入学生信息
void InputValue(Student* stu) {if (!stu)return;printf(学生的年龄身高体重\n);scanf(%d%d%lf, stu-age, stu-height, stu-weight);
}
//输出每个节点的信息
void DisplayNode(Student* stu) {printf(年龄%-5d 身高%-5d 体重%-5lf\n, stu-age, stu-height, stu-weight);
}
//创建节点
Node* CreateNode(Student* stu){//1.申请一份空间Node* node (Node*)malloc(sizeof(Node));//2.判断空间是否申请成功if (!node) {printf(内存不足\n);return NULL;}//3.初始化节点中的数据域即学生信息CopyValue(node-stu, stu);node-next NULL;//4.返回创建的节点return node;
}//创建链表
Node* CreateLink() {Student stu { 0,0,0 };//1.创建头节点Node* head CreateNode(stu);if (!head) exit(-1);//2.创建其他节点连接到头节点构成链表int tag 0;Node* pnew, * tail head;printf(是否创建新结点继续添加输入1否则输入0\n);scanf(%d, tag);while (tag ! 0) {InputValue(stu);pnewCreateNode(stu);tail-next pnew;tail pnew;printf(是否创建新结点继续添加输入1否则输入0\n);scanf(%d, tag);}return head;
}
//销毁链表
void FreeLink(Node* head) {//1.判断链表是否为空为空则返回if (head NULL)return;//如果非空则逐个节点释放Node* p, * q;p head;while (p-next ! NULL) {q p-next;p-next q-next;free(q);}free(head);
}//打印单链表
void DisplayLink(Node* head) {//1.判断链表是否为空为空直接返回if (!head)return;//2.打印每个节点信息Node* p head-next;while (p ! NULL) {DisplayNode(p-stu);p p-next;}
}
//在指定位置插入节点
void InsertNode(Node* head, Node* pnew,int i) {//1.判断链表是否为空为空拒绝插入if (!head)return;//2.判断结点是否为空为空拒绝插入if (!pnew)return;//3.遍历链表插入指定位置Node* p head;for (int n 0;n i;n) {p p-next;}pnew-next p-next;p-next pnew;
}
//在指定位置删除结点
void DeleteNode(Node* head, int i) {//1.判断链表是否为空为空直接返回if (!head)return;//2.遍历链表找到要删除的位置Node *phead,*q;for (int n 1;n ip-next!NULL;n) {p p-next;//当p等于NULL了说明把整条链表都遍历完了还没有找到}//3.如果找到了该位置删除找不到就返回if (!p)return;q p-next;p-next q-next;free(q);
}
//比较两节点内容
int Compare(Student* s1, Student* s2) {if (s1 NULL || !s2)return -1;if (s1-age s2-age s1-height s2-height s1-weight s2-weight)return 1;return 0;
}
//根据指定信息查找节点
int CheckNode(Node* head, Student* stu) {//1.链表与查找的节点不为空if (!head || !stu)return 0;//2.遍历单链表找到是否有相同的节点Node* p head-next;int ret 1;int m 0;while (p!NULL) {m Compare(p-stu, stu);if (m 1)return ret;p p-next;ret;}return 0;
}//改变指定位置的节点信息
void ModifyValue(Node* head,Student*stu, int input) {//1.判断第一个节点是否存在if (!head || head-next NULL)return;//2.遍历链表找到节点位置Node* p head-next;for (int i 1;i input;i) {p p-next;}//3.改变信息p-stu.age stu-age;p-stu.height stu-height;p-stu.weight stu-weight;
}int main() {//1.初步创建链表并插入初始信息最终打印Node* head CreateLink();DisplayLink(head);//2.插入新节点printf(请输入要插入的位置\n);int input 0;scanf(%d, input);//得到位置Student stu;printf(请输入学生信息\n);InputValue(stu);//得到信息Node* pnew CreateNode(stu);//得到新的结点InsertNode(head, pnew, input);printf(以下是插入信息后的信息表\n);DisplayLink(head);//3.在指定位置删除结点printf(请输入要删除的位置\n);int input2 0;scanf(%d, input2);DeleteNode(head, input2);printf(以下是删除信息后的信息表\n);DisplayLink(head);//4.根据指定信息查找结点int input3;do{if (head-next NULL) {printf(表中已无信息\n);break;}printf(请输入要查找的学生信息\n);Student stu2;InputValue(stu2);int ret CheckNode(head, stu2);if (ret ! 0)printf(找到了该学生编号为%d\n, ret);elseprintf(无该学生信息\n);printf(是否继续查找是输1否输0);input3 0;scanf(%d, input3);} while (input3 1);//5.改变指定位置的节点信息printf(请输入要改变的结点位置);int input4 0;scanf(%d, input4);printf(请输入改变后的信息\n);Student stu3;InputValue(stu3);ModifyValue(head,stu3,input4);printf(以下是改变信息后的信息表\n);DisplayLink(head);//销毁链表FreeLink(head);
}测试结果 如有错误请指正哦感谢❤️
