当前位置：首页 > news >正文

数据结构--单链

news 2025/6/29 17:41:59

#include "link.h"
plink get_head()
{
   plink p=malloc(sizeof(Link));
   if(p==NULL)
   {
       printf("申情节点失败\n");
       return NULL;
   }
   p->len=0;
   p->next=NULL;
   return p;
}
void head_insert(plink L,int a)
{
   if(L==NULL)
   {
       printf("单链表不存在\n");
   }
   plink p=malloc(sizeof(Link));//申请新节点
   p->data=a;//新节点赋值
   p->next=L->next;//将第一个节点的地址放入新节点指针域
   L->next=p;//将新节点地址放入头结点指针域
   L->len++;
}
void node_output(plink L)

{
   if(L==NULL||L->len==0)
   {
       printf("单链表不存在或者为空\n");
   }
   plink t=L;
   for(int i=0;i<L->len;i++)
   {
       t=t->next;
       printf("%d\t",t->data);
   }
   putchar(10);
}
void tail_insert(plink L,int a)
{
   if(L==NULL)
   {
       printf("单链表不存在\n");
   }
   plink t=L;
   for(int i=0;i<L->len;i++)
   {
       t=t->next;
   }
   plink p=malloc(sizeof(Link));//申请新节点
   p->data=a;//新节点赋值
   t->next=p;
   p->next=NULL;
   L->len++;
}
void any_insert(plink L)
{
   if(NULL==L)
   {
       printf("插入失败\n");
   }
   int key,x;
   printf("请输入要插入的位置：");
   scanf("%d",&key);
   plink t=L;
   for(int i=0;i<key-1;i++)
   {
       t=t->next;
   }
   printf("请输入要插入的值：");
   scanf("%d",&x);
   plink p=malloc(sizeof(Link));//申请新节点
   p->data=x;//新节点赋值
   p->next=t->next;
   t->next=p;
   L->len++;
}
void head_dele(plink L)
{
   if(NULL==L)
   {
       printf("单链表不存在或者为空\n");
   }
   plink t=L->next;
   L->next=t->next;
   L->len--;
   free(t);
   t=NULL;
}
void tail_dele(plink L)
{
   if(NULL==L||L->len==0)
   {
       printf("单链表不存在或者为空\n");
   }
   plink t=L;
   for(int i=0;i<L->len-1;i++)
   {
       t=t->next;
   }
   plink q=t->next;
   t->next=NULL;
   L->len--;
   free(q);
   q=NULL;
}
void any_dele(plink L)
{
   if(L==NULL||L->len==0)
   {
       printf("单链表不存在或者为空\n");
   }
   int key;
   printf("请输入要删除的位置：");
   scanf("%d",&key);
   plink t=L;
   for(int i=0;i<key-1;i++)
   {
       t=t->next;
   }
   plink p=t->next;//申请新节点
   t->next=t->next->next;
   L->len--;
   free(p);
   p=NULL;
}
void find_change(plink L)
{
   int key,sub=-1,x;
   printf("请输入要查找的数：");
   scanf("%d",&key);
   printf("请输入要修改的值：");
   scanf("%d",&x);
   if(L==NULL||L->len==0)
   {
       printf("单链表不存在或为空\n");
   }
   plink t=L;
   for(int i=0;i<L->len;i++)
   {
       t=t->next;
       if(t->data==key)
       {
           sub=i;
           t->data=x;
       }
   }
   if(sub==-1)
   {
       printf("不存在该节点\n");
   }
}
void node_reverse(plink L)
{
   if(L==NULL||L->len==0)
   {
       printf("单链表不存在或为空\n");
   }
   plink q=L->next->next;
   plink t=L->next;
   while(q!=NULL)
   {
       t->next=q->next;
       q->next=L->next;
       L->next=q;
       q=t->next;
   }
}
void node_sort(plink L)//升序
{
   if(L==NULL||L->len==0)
   {
       printf("单链表不存在或为空\n");
   }
   for(int i=0;i<L->len-1;i++)
   {
       plink q=L->next->next;
       plink t=L->next;
       while(q!=NULL)
       {
           if(q->data<t->data)
           {
               t->next=q->next;
               q->next=L->next;
               L->next=q;
               q=t->next;
           }
           else
           {
               t=t->next;
               q=q->next;
           }
       }
   }
}
void node_cut(plink L)
{
   if(L==NULL||L->len==0)
   {
       printf("单链表不存在或为空\n");
   }
   plink t=L->next;
   plink q=L->next->next;
   while(q!=NULL)
   {
       L->next=q;
       free(t);
       t=q;
       q=t->next;
       L->len--;
   }
   free(t);
   t=NULL;
   L->len--;
}

#ifndef _LINK_H
#define _LINK_H
#include<myhead.h>
typedef struct node//节点结构体
{
   union
   {
       int len;//链表长度
       int data;//节点数据域，存储数据
   };//节省空间
   struct node *next;//指向下一个指针节点
}Link,*plink;//结构体普通类型
plink get_head();
void head_insert(plink,int);
void node_output(plink);
void tail_insert(plink,int);
void any_insert(plink);
void head_dele(plink);
void tail_dele(plink);
void any_dele(plink);
void find_change(plink);
void node_reverse(plink);
void node_sort(plink);
void node_cut(plink);

#endif

#include "link.h"

int main(int argc, const char *argv[])
{
   //申请头结点函数，返回头结点地址给L
   plink L=get_head();
   //头插法创建整个表
   int a[10]={10,20,30,40,50,60,70,80,90,95};
   for(int i=0;i<10;i++)
   {
       head_insert(L,a[i]);
   }
   //尾插法创建整个表
   for(int i=0;i<10;i++)
   {
       tail_insert(L,a[i]);
   }
   //单链表遍历
   node_output(L);
   putchar(10);
   any_insert(L);
   node_output(L);
   putchar(10);
   head_dele(L);
   node_output(L);
   putchar(10);
   tail_dele(L);
   node_output(L);
   any_dele(L);
   node_output(L);
   putchar(10);
   find_change(L);
   node_output(L);
   putchar(10);
   node_reverse(L);
   node_output(L);
   putchar(10);
   node_sort(L);
   node_output(L);
   putchar(10);
   node_cut(L);
   node_output(L);