漳州网站建设优化推广,网站相对路径和绝对路径,长10米宽3米的店面设计,重心型网站一丶概念 链表又称单链表、链式存储结构#xff0c;用于存储逻辑关系为“一对一”的数据。 和顺序表不同同#xff0c;使用链表存储数据#xff0c;不强制要求数据在内存中集中存储#xff0c;各个元素可以分散存储在内存中。 二丶特点 特点#xff1a;内存不连续…一丶概念 链表又称单链表、链式存储结构用于存储逻辑关系为“一对一”的数据。 和顺序表不同同使用链表存储数据不强制要求数据在内存中集中存储各个元素可以分散存储在内存中。 二丶特点 特点内存不连续通过指针进行连接 解决: 长度固定的问题插入删除麻烦的问题 逻辑结构线性结构 存储结构链式存储 操作增删改查 struct node
{int data; //数据域存储数据struct node *next; //指针域存储下一个节点的地址
};三丶单向链表 1.分类 有头链表存在一个头节点头节点数据域无效指针域有效。 无头链表每一个节点的数据域和指针域都有效。 2.有头单向链表 存在一个头节点数据域无效指针域有效 #include stdio.h
#includestdlib.h
typedef int datatype;
typedef struct node
{int data;//数据域struct node *next;//指针域
} node_t, *node_p;
int main(int argc, char const *argv[])
{node_t A{1,NULL};//输入数据node_t B{2,NULL};node_t C{3,NULL};node_t D{4,NULL};A.nextB;B.nextC;C.nextD;node_p p;//头指针指向头节点node_t S {\0,A};pH.next;while(p!NULL){printf(%d ,p-data);pp-next;}printf(\n);return 0;
}3.无头单向链表 所有节点的指针域和数据域都有效 #include stdio.h
#include stdlib.h
typedef char datatype;
typedef struct node
{datatype data; //数据域用来存数据struct node *next; //指针域用来存下一个节点的地址
} node_t, *node_p;// node_t A; //等同于 struct node A;
// node_p p; //等同于 struct node *p;int main(int argc, char const *argv[])
{//1.定义4个节点node_t A {a, NULL};node_t B {b, NULL};node_t C {c, NULL};node_t D {d, NULL};//2.连接四个节点A.next B; //连接A和BB.next C;C.next D;//3.定义一个头指针指向第一个节点node_p p A;//4. 通过指针遍历无头单向链表while (p ! NULL){printf(%c , p-data); //打印节点中的数据域 a b c dp p-next; //让p指向下一个节点}printf(\n);return 0;
}链表尾插法练习 写一个有头单向链表用于保存输入的学生成绩实现一输入学生成绩就创建一个新的节点将成绩保存起来。再将该节点链接到链表的尾直到输入-1结束。 要求每个链表的节点由动态内存分配得到 , 也就是用malloc。 过程 1. malloc申请空间link_node_t大小作为头节点 2. 将新节点放到链表尾部 #include stdio.h
#include stdlib.h
typedef int datatype;
typedef struct node
{int data;//数据域存放数据struct node *next;//指针域记录下一个结点地址
} node_t, *node_p;
void ShowLinklist(node_p p)//打印数据
{while(p!NULL){printf(%d ,p-data);pp-next;}printf(\n);
}
int main(int argc, char const *argv[])
{int score 0;// 创建一个头节点node_p p_head (node_p)malloc(sizeof(node_t));if (NULL p_head)//容错判断{printf(malloc err);return -1;}//让头指针的指针域置空p_head-next NULL;//创建一个尾节点node_p p_tail (node_p)malloc(sizeof(node_t));if (NULL p_head){printf(p_tail malloc err);return -1;}p_tail p_head;//让尾节点指向头节点while (1){//循环输入成绩scanf(%d, score);//输入-1时停止结束循环if (score -1)break;//新建一个节点p_newnode_p p_new (node_p)malloc(sizeof(node_t));if (NULL p_new)//容错判断{printf(p_new malloc err);return -1;}p_new-data score; //将数据存入新的节点p_new-next NULL;//让新的节点的指针域置空p_tail-next p_new;//让尾节点连接到新的节点p_tailp_new;//更新尾节点}node_p p p_head-next;ShowLinklist(p);return 0;
}4.有头单向链表的函数操作 插入的思想 1. 先遍历找到要插入节点的前一个节点假设这个节点为AA的下一个节点为B将C插入A与B之间 2.先让C的指针域指向B 3.再让A的指针域指向C 注意顺序不可以调换 int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post 0 || post StrlenLinklist(p)){printf(Insert eerr);return -1;}for (int i 0; i post; i) // 让p指向插入位置post的前一个节点p p-next;node_p p_new (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL p_new) // 容错判断{printf(p_new malloc err);return -1;}p_new-data data; // 让新节点的数据域等于新的数据p_new-next p-next; // 指针域等于插入位置的地址p-next p_new; // 前一个节点的指针域等于新节点的地址return 0;
} 删除的思想 1.先遍历找到要删除节点的前一个节点假设为A 2、找一个临时指针指向要删除的节点 3、 将A的指针域指向删除节点的下一个节点 4、 释放被删除节点 int DeleteLinklist(node_p p, int post) // 删除函数
{if (post 0 || post StrlenLinklist(p)){printf(Insert eerr);return -1;}for (int i 0; i post; i) // 让p指向删除位置post的前一个节点p p-next; node_p p1 p-next; // 新定义一个结构体指针用来存放删除位置的地址p-next p1-next; // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1); // 将被删除指针释放指针置空p1 NULL;
} 转置的思想 (1) 将头节点与当前链表断开断开前保存下头节点的下一个节点保证后面链表能找得到定义一个q保存头节点的下一个节点断开后前面相当于一个空的链表后面是一个无头的单向链表(2) 遍历无头链表的所有节点将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置) void ReverseLinkList(node_p p)
{node_p temp NULL;//临时保存q下一个节点的地址//断开前保存头节点的下一个节点的地址node_p q p-next;//指向头节点的下一个节点相当于无头单向链表的头指针//1.断头断开链表p-next NULL;//2.遍历无头单向链表while (q ! NULL){//暂时存放q的下一个节点防止链表丢失temp q-next;//头插到有头单向链表头节点的后面q-next p-next;p-next q;//将q重新指向之前的无头单向链表指向此时的第一个节点qtemp;} 完整的单链表操作 #include stdio.h
#include stdlib.h
typedef int datatype;
typedef struct node
{int data; // 数据域存放数据struct node *next; // 指针域记录下一个结点地址
} node_t, *node_p;
node_p CreateEpLinkist() // 创建一个空的有头单向链表
{node_p p (node_p)malloc(sizeof(node_t)); // 开辟节点空间大小if (NULL p){printf(CreatEpLinklist err);return NULL;}p-next NULL; // 初始化头结点return p;
}
int StrlenLinklist(node_p p)//计算单链表长度
{int len 0;while (p-next ! NULL){p p-next;len;}return len;
}
int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post 0 || post StrlenLinklist(p)){printf(Insert eerr);return -1;}for (int i 0; i post; i) // 让p指向插入位置post的前一个节点p p-next;node_p p_new (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL p_new) // 容错判断{printf(p_new malloc err);return -1;}p_new-data data; // 让新节点的数据域等于新的数据p_new-next p-next; // 指针域等于插入位置的地址p-next p_new; // 前一个节点的指针域等于新节点的地址return 0;
}
int DeleteLinklist(node_p p, int post) // 删除函数
{if (post 0 || post StrlenLinklist(p)){printf(Insert eerr);return -1;}for (int i 0; i post; i) // 让p指向删除位置post的前一个节点p p-next; node_p p1 p-next; // 新定义一个结构体指针用来存放删除位置的地址p-next p1-next; // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1); // 将被删除指针释放指针置空p1 NULL;
}
void ModifyLinklist(node_p p, int post, int data) // 修改函数
{for (int i 0; i post; i) // 让指针指向要修改的节点位置p p-next;p-data data; // 指针域等于新的数据
}
void SearchLinklist(node_p p, int data)//查找数据
{int i 0;p p-next;while (p ! NULL){if (p-data data){printf(%d\n, i);//打印第一个相同数据的下标break;}p p-next;i;}
}
void ClearLinklist(node_p p)//清空链表
{while(StrlenLinklist(p)!0){DeleteLinklist(p,0);//删除第一个节点}
}
void ShowLinklist(node_p p)// 打印数据
{while (p-next)// 当指针p的指针域为空时停止循环{p p-next;printf(%d , p-data);}printf(\n);
}
void ReverseLinkList(node_p p)//链表转置
{node_p temp NULL;//临时保存q下一个节点的地址//断开前保存头节点的下一个节点的地址node_p q p-next;//指向头节点的下一个节点相当于无头单向链表的头指针//1.断头断开链表p-next NULL;//2.遍历无头单向链表while (q ! NULL){//暂时存放q的下一个节点防止链表丢失temp q-next;//头插到有头单向链表头节点的后面q-next p-next;p-next q;//将q重新指向之前的无头单向链表指向此时的第一个节点qtemp;}}
int IsEpLinklist(node_p p)
{return p-next NULL;
}
int main(int argc, char const *argv[])
{node_p p CreateEpLinkist(); // 创建一个空的有头单向链表InsertLinklist(p, 0, 1);// 进行插入数据InsertLinklist(p, 1, 2);InsertLinklist(p, 2, 3);InsertLinklist(p, 3, 4);InsertLinklist(p, 4, 5);InsertLinklist(p, 5, 6);ShowLinklist(p);// 打印数据DeleteLinklist(p, 0);// 删除数据ShowLinklist(p);// 打印数据ModifyLinklist(p, 0, 0); // 修改数据ShowLinklist(p);// 打印数据SearchLinklist(p, 2);ReverseLinkList(p);ShowLinklist(p);// 打印数据ClearLinklist(p);if(IsEpLinklist(p))printf(IsEpLinkList\n);free(p);p NULL;return 0;return 0;
} 5.单向循环链表 四丶总结 顺序表和单向链表比较 (1).顺序表在内存当中连续存储的(数组)但是链表在内存当中是不连续存储的通过指针将数据链接在一起 (2).顺序表的长度是固定的但是链表长度不固定 (3).顺序表查找方便但是插入和删除麻烦链表插入和删除方便查找麻烦
