单链表算法

    科技2023-01-25  2

    遍历:就是把单链表中的各个节点挨个拿出来,就叫遍历 遍历要点:不能遗漏,不能重复,追求效率 方法:从头指针+头节点 ,顺着链表挂接指针依次访问链表的各个节点,取出这个节点的数据,然后再往下一个节点,知道最后一个节点,结束返回

    #include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; struct node *creat_node(int data) { struct node *p=(struct node *)malloc(sizeof(struct node)); if(NULL==p) { printf("error\n"); return NULL; } bzero(p,sizeof(struct node)); p->data=data; p->pnext=NULL; return p; } //遍历单链表,ph为指向单链表的头指针,遍历的节点数据打印出来 void bianli(struct node *ph) { struct node *p = ph; //第一个节点 while(NULL != p->pnext) { printf("%d\n",p->data); p = p->pnext; //走到下一个节点 } printf("%d\n",p->data); printf(" 结束\n"); } int main(void) { struct node *header=NULL; header=creat_node(1); header->pnext=creat_node(2); header->pnext->pnext=creat_node(3); bianli(header); return 0; }

    删除节点 步骤:找到要删除的节点 删除节点 如果找到待删除的节点:通过遍历,从头指针+头节点开始,顺着链表依次将各个节点拿出来,比对,找到我们要删除的节点

    删除节点的情况: 删除的节点不是尾节点 删除的节点是尾节点 第一种:首先把待删除的节点的前一个节点的pnext指针指向待删除的节点的后一个节点的首地址,然后将摘出来的节点free掉 第二种:首先把待删除的尾节点的前一个节点的pnext指针指向null,然后将摘出来的节点free掉

    注意堆内存的释放

    #include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; struct node *creat_node(int data) { struct node *p=(struct node *)malloc(sizeof(struct node)); if(NULL==p) { printf("error\n"); return NULL; } bzero(p,sizeof(struct node)); p->data=data; p->pnext=NULL; return p; } void bianli(struct node *ph) { struct node *p = ph; //第一个节点 while(NULL != p->pnext) { printf("%d\n",p->data); p = p->pnext; //走到下一个节点 } printf("%d\n",p->data); printf(" 结束\n"); } //从链表ph中删除节点,待删除的节点的特征是数据区等于data //当我们找到删除了节点返回0 ,没找到返回-1 int delete_node(struct node *ph,int data) { //通过遍历链表来查找 struct node *p =ph; struct node *pnew = NULL; while(NULL !=p->pnext) { pnew = p; p = p->pnext; if(p->data == data) { //找到节点,处理节点 if(NULL == p->pnext) { //尾节点 pnew->pnext = NULL; //等同于原来尾节点的前一个节点变成新尾节点 free(p);//释放原来尾节点的内存 } else { pnew->pnext = p->pnext;//要删除的前一个节点和后一个节点连接 free(p); } return 0; } printf("未找到节点\n"); return -1; } } int main(void) { struct node *header=NULL; header=creat_node(1); header->pnext=creat_node(2); header->pnext->pnext=creat_node(3); bianli(header); delete_node(header,2); bianli(header); return 0; }

    逆序 逆序又叫反向,将链表中有所有的有效节点在链表中的顺序给反过来 逆序 = 遍历+头插入

    #include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; struct node *creat_node(int data) { struct node *p=(struct node *)malloc(sizeof(struct node)); if(NULL==p) { printf("error\n"); return NULL; } bzero(p,sizeof(struct node)); p->data=data; p->pnext=NULL; return p; } void bianli(struct node *ph) { struct node *p = ph; //第一个节点 while(NULL != p->pnext) { printf("%d\n",p->data); p = p->pnext; //走到下一个节点 } printf("%d\n",p->data); printf(" 结束\n"); } //将ph指向的链表逆序 void reverse(struct node *ph) { struct node *p=ph->pnext;//ph指向头节点,p指向第一个有效节点 struct node *pback; // 保存当前节点额后一个节点地址 //当链表没有有效节点或者只有一个有效节点时,逆序不需要做任何操作 if(NULL == p || NULL == p->pnext) return; ` //当有2个及以上节点时才需要真正进行逆序操作 while(NULL == p->pnext) //确定·是不是最后一个节点 { //原链表中第一个有效节点将是逆序后新链表的尾节点,尾节点的pnext指向NULL pback = p->pnext; //保存p节点后面一个节点地址 if(p == ph->pnext) { //原链表的第一个有效节点 p->pnext = NULL; } else { //原链表的第一个费有效节点 p->pnext = ph->pnext; } ph->pnext = p; p = pback; //走到下一个节点 } //循环结束,最后一个节点缺失 } int main(void) { struct node *header=NULL; header=creat_node(1); header->pnext=creat_node(2); header->pnext->pnext=creat_node(3); bianli(header); return 0; }
    Processed: 0.023, SQL: 9