专门做动漫的网站,wordpress 移动端 提速,工作优化方案怎么写,网站制作用什么语言单链表操作的C/C实现详解
在数据结构中#xff0c;单链表是一种非常基础且重要的数据结构。它由一系列节点组成#xff0c;每个节点包含数据和指向下一个节点的指针。今天我们就来深入探讨用C/C实现的单链表及其各种操作。
一、单链表的定义
const int N 1e5;
//单链表
t…单链表操作的C/C实现详解
在数据结构中单链表是一种非常基础且重要的数据结构。它由一系列节点组成每个节点包含数据和指向下一个节点的指针。今天我们就来深入探讨用C/C实现的单链表及其各种操作。
一、单链表的定义
const int N 1e5;
//单链表
typedef struct node {int val; //当前链表值struct node* next; //链表后面的值域地址
}lst;这里定义了一个单链表节点的结构体lst。val用于存储节点的数据next是一个指针指向链表中的下一个节点。通过这种方式节点之间可以串联起来形成链表。const int N 1e5; 定义了一个常量N虽然在当前代码中没有直接使用但可以作为链表最大长度的一个限制在实际应用中可能会用于内存分配或边界检查等。
二、链表初始化
//链表初始化
lst* initlst()
{lst* head;head (lst*)malloc(sizeof (lst));//开辟空间head-next NULL; //指向空return head;
}initlst函数用于初始化一个单链表。首先使用malloc函数为头节点分配内存空间然后将头节点的next指针设置为NULL表示这是一个空链表。最后返回头节点指针后续对链表的操作都可以通过这个头节点来进行。
三、打印链表
//打印链表
void printlst(lst*l)
{lst* p l; //找到头指针while (p! NULL){if (p-val! NULL)cout p-val endl; //头指针不空p p-next; //一直取出next}
}printlst函数用于打印链表中的所有节点值。通过一个临时指针p从链表的头节点开始遍历只要p不为NULL就表示还没有到达链表末尾。在循环中检查当前节点的val值是否有效这里if (p-val! NULL)判断有误val是int类型不能与NULL比较应直接输出p-val然后输出当前节点的值并将p移动到下一个节点。
四、尾插法相关操作
一单个节点尾插
void insert2(lst* l, int x) //尾插法
{lst* s, * last;last l;while (last-next! NULL) //找到最后的值{last last-next;}s (lst*)malloc(sizeof(lst));s-val x;s-next NULL;last-next s;last s;puts(完成插入);
}insert2函数实现了将一个新节点尾插到链表中。首先找到链表的最后一个节点通过遍历到last-next为NULL然后为新节点分配内存设置新节点的值和next指针next为NULL表示这是链表的最后一个节点最后将新节点连接到链表的末尾并更新last指针。
二多个节点尾插初始化
void initinsert2(lst *l, int n) {//尾插法の初始化lst* s, * last;last l;puts(请输入);for (int i 1; i n; i) {int x;cin x;s (lst*)malloc(sizeof(lst));s-val x;s-next NULL;last-next s;last s;}puts(完成插入);
}initinsert2函数用于通过尾插法初始化链表一次性插入n个节点。它与insert2函数的原理类似通过循环多次执行尾插操作每次从用户输入中获取一个值创建新节点并插入到链表末尾。
五、头插法相关操作
一单个节点头插
void insert1(lst* l, int x) //头插法[记得要取地址]
{//1.c:lst *l//2.c:lst** llst* s;s (lst*)malloc(sizeof(lst));s-val x;s-next l;l s;
}insert1函数实现了头插法将一个新节点插入到链表的头部。这里lst* l表示传递的是头指针的引用这样在函数内部对l的修改会直接影响到函数外部的头指针。首先为新节点分配内存设置新节点的值然后将新节点的next指针指向原来的头节点最后更新头指针l使其指向新插入的节点。需要注意的是这里要用地址方便更新头结点
二多个节点头插初始化
void initinsert1(lst* l, int n) {//头插法の初始化lst* s;puts(请输入);for (int i 1; i n; i) {int x;cin x;s (lst*)malloc(sizeof(lst));s-val x;s-next l-next;l-next s;//l s;}puts(完成插入);
}六、求链表长度
//求长度
int get_len(lst* l)
{lst* p l-next;int len 0;while (p! NULL){p p-next;len;}return len;
}get_len函数用于计算链表的长度不包括头节点。通过一个临时指针p从链表头节点的下一个节点开始遍历每遍历一个节点长度计数器len就加1直到遍历完整个链表p为NULL最后返回链表的长度。
七、查找操作
一按值查找位置
//查找
void find_idex(lst* l, int x) //找x的位置
{lst* p l-next;int id 1;while (p! NULL p-val! x){p p-next;id;}if (p! NULL) cout 位置 id endl;
}find_idex函数用于查找值为x的节点在链表中的位置从1开始计数。从链表的第一个数据节点开始遍历同时记录当前节点的位置id如果找到值为x的节点就输出其位置如果遍历完链表都没有找到则不输出任何信息。
二按位置查找值
void find_val(lst* l, int x) //找x的位置上的值
{lst* p l-next;int j 1;while (p! NULL j x){p p-next;j;}if (x j) cout 值 p-val endl;
}find_val函数用于查找链表中第x个位置的节点的值。同样从链表的第一个数据节点开始遍历用j记录当前遍历到的节点位置当遍历到第x个节点时输出该节点的值。
八、插入操作
//插入
void insert(lst* l, int i, int x) //找i插入x
{lst* p, * s;int j 0;while (p-next! NULL j i - 1){p p-next;j;}if (p! NULL){s (lst*)malloc(sizeof(lst));s-val x;s-next p-next;p-next s;}
}insert函数用于在链表的第i个位置插入值为x的节点。首先找到第i - 1个节点通过遍历并计数j然后为新节点分配内存设置新节点的值和next指针使其插入到第i - 1个节点和第i个节点之间。需要注意的是这里代码存在问题while (p-next! NULL j i - 1) 中p未初始化应在循环前将p初始化为l。
九、删除操作
//删除
void insert(lst* l, int i)
{lst* p, * s;int j 0;while (p-next! NULL j i - 1){p p-next;j;}if (p! NULLj i - 1) //删除的位置要在i之前{s p-next; //这个是要删的地址p-next s-next;free(s); //释放空间}
}这里insert函数名错误应该改为deleteNode之类的名字。此函数用于删除链表中第i个节点。先找到第i - 1个节点然后将第i个节点从链表中移除通过修改指针并释放第i个节点的内存空间。同样这里也存在p未初始化的问题应在循环前将p初始化为l。
十、总结
通过以上对单链表各种操作的实现我们可以看到单链表在数据存储和操作上的灵活性。虽然代码中存在一些小问题如类型判断错误、指针未初始化等但通过理解这些操作的原理和逻辑我们可以更好地掌握单链表这一数据结构并且能够根据实际需求进行优化和改进。在实际应用中单链表常用于实现栈、队列等数据结构以及在需要动态分配内存和频繁插入删除操作的场景中发挥重要作用。
