博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
单链表的C实现
阅读量：4112 次
发布时间：2019-05-25

本文共 7316 字，大约阅读时间需要 24 分钟。

1.声明一节点p指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；

3.若到链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，在系统中生成一个空节点s;

5.将数据元素e赋给s->data；

6.单链表插入标准语句s->next=p->next;p->next=s;  不能写反了

s->next=p->next;这个p->next之前存的是p所指后面一个节点的地址，如果s想要插入p和p的下一个节点之间，

那么就s->next=p->next;也就是把之前p后面一个节点的地址给s的next,而p->next=s,就把s插入到了之前p和p下一个节点之间

7.p=p->next 的意思是指向下一个节点

7.返回成功。

插入实现代码算法如下：

[cpp] 
  1. //在L中第i个位置之前插入新的数据元素e，L的长度加1  
  2. int ListInsert(LinkList *L,int i,ElmeType e)  
  3. {  
  4.     int j;  
  5.     LinkList p,s;  
  6.     p = *L;  
  7.     j = 1;  
  8.     while(p && j<1)  
  9.     {  
  10.         p = p->next;  
  11.         ++j;  
  12.     }  
  13.     if(!p || j>=1)  
  14.         return ERROR;  
  15.     s = (LinkList)malloc(sizeof(Node)); //生成新节点  
  16.     s->data = e;  
  17.     s->next = p->next;  
  18.     p->next = s; //顺序绝对不变  
  19.     return OK;  
  20. }  

如何删除呢？其实只要q=p->next;p->next->q->next;

算法思路省略，直接给出代码：

[cpp] 
  1. //删除L第i个元素，并用e返回其值，L的长度减1  
  2. int ListInsert(LinkList *L,int i,ElmeType e)  
  3. {  
  4.     int j;  
  5.     LinkList p,s;  
  6.     p = *L;  
  7.     j = 1;  
  8.     while(p && j<1)  
  9.     {  
  10.         p = p->next;  
  11.         ++j;  
  12.     }  
  13.     if(!(p->next) || j>=1)  
  14.         return ERROR;  
  15.     q = p->next;  
  16.     p->next = q->next;  
  17.     *e = q->data;  
  18.     free(q);    //释放内存  
  19.     return OK;  
  20. }  

  21. 有的时候，处于内存中的数据并不是连续的。那么这时候，我们就需要在数据结构中添加一个属性，这个属性会记录下面一个数据的地址。有了这个地址之后，所有的数据就像一条链子一样串起来了，那么这个地址属性就起到了穿线连结的作用。

        相比较普通的线性结构，链表结构的优势是什么呢？我们可以总结一下：

        （1）单个节点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小

        （2）节点的删除非常方便，不需要像线性结构那样移动剩下的数据

        （3）节点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

        那么在实际应用中，链表是怎么设计的呢？我们可以以int数据类型作为基础，设计一个简单的int链表：

        （1）设计链表的数据结构

    [cpp] 
    1. typedef struct _LINK_NODE  
    2. {  
    3.     int data;  
    4.     struct _LINK_NODE* next;  
    5. }LINK_NODE;  

        （2）创建链表

    [cpp] 
    1. LINK_NODE* alloca_node(int value)  
    2. {  
    3.     LINK_NODE* pLinkNode = NULL;  
    4.     pLinkNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));  
    5.       
    6.     pLinkNode->data = value;  
    7.     pLinkNode->next = NULL;  
    8.     return pLinkNode;  
    9. }  

        （3）删除链表

    [cpp] 
    1. void delete_node(LINK_NODE** pNode)  
    2. {  
    3.     LINK_NODE** pNext;  
    4.     if(NULL == pNode || NULL == *pNode)  
    5.         return ;  
    6.           
    7.     pNext = &(*pNode)->next;  
    8.     free(*pNode);  
    9.     delete_node(pNext);   
    10. }  
        （4）链表插入数据

    [cpp] 
    1. STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)  
    2. {  
    3.     if(NULL == *pNode){  
    4.         *pNode = pDataNode;  
    5.         return TRUE;  
    6.     }  
    7.       
    8.     return _add_data(&(*pNode)->next, pDataNode);  
    9. }  
    10.   
    11. STATUS add_data(const LINK_NODE** pNode, int value)  
    12. {  
    13.     LINK_NODE* pDataNode;  
    14.     if(NULL == *pNode)  
    15.         return FALSE;  
    16.           
    17.     pDataNode = alloca_node(value);  
    18.     assert(NULL != pDataNode);  
    19.     return _add_data((LINK_NODE**)pNode, pDataNode);  
    20. }  
        （5）删除数据

    [cpp] 
    1. STATUS _delete_data(LINK_NODE** pNode, int value)  
    2. {  
    3.     LINK_NODE* pLinkNode;  
    4.     if(NULL == (*pNode)->next)  
    5.         return FALSE;  
    6.       
    7.     pLinkNode = (*pNode)->next;  
    8.     if(value == pLinkNode->data){  
    9.         (*pNode)->next = pLinkNode->next;  
    10.         free(pLinkNode);  
    11.         return TRUE;  
    12.     }else{  
    13.         return _delete_data(&(*pNode)->next, value);  
    14.     }  
    15. }  
    16.   
    17. STATUS delete_data(LINK_NODE** pNode, int value)  
    18. {  
    19.     LINK_NODE* pLinkNode;  
    20.     if(NULL == pNode || NULL == *pNode)  
    21.         return FALSE;  
    22.   
    23.     if(value == (*pNode)->data){  
    24.         pLinkNode = *pNode;  
    25.         *pNode = pLinkNode->next;  
    26.         free(pLinkNode);  
    27.         return TRUE;  
    28.     }         
    29.       
    30.     return _delete_data(pNode, value);  
    31. }  

        （6）查找数据

    [cpp] 
    1. LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)  
    2. {  
    3.     if(NULL == pLinkNode)  
    4.         return NULL;  
    5.       
    6.     if(value == pLinkNode->data)  
    7.         return (LINK_NODE*)pLinkNode;  
    8.       
    9.     return find_data(pLinkNode->next, value);  
    10. }  
        （7）打印数据

    [cpp] 
    1. void print_node(const LINK_NODE* pLinkNode)  
    2. {  
    3.     if(pLinkNode){  
    4.         printf("%d\n", pLinkNode->data);  
    5.         print_node(pLinkNode->next);  
    6.     }  
    7. }  
        （8）统计数据

    [cpp] 
    1. int count_node(const LINK_NODE* pLinkNode)  
    2. {  
    3.     if(NULL == pLinkNode)  
    4.         return 0;  
    5.           
    6.     return 1 + count_node(pLinkNode->next);  
    7. }  

    文件功能:实现了动态建立一个学生信息的链表包括链表的
    创建、插入、删除、和打印输出学生信息包括姓名和分数
    本链表是带有头结点的，头结点的内容为空内容
    -----------------------------------------------------------------------------*/
    /*-------------------------包含头文件------------------------------------*/
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>

    /*-------------------------结构体定义部分------------------------------*/
    struct Node
    {


     char name[10];
     int score;
     struct Node *next;
    };

    typedef struct Node ListNode;
    /*----------------------------函数声明部分------------------------------*/


    /*---------------------------函数实现部分-------------------------------*/
    /*-----------------------------创建链表---------------------------------*/
    /*在链表的末端插入新的节点，建立链表*/
    ListNode *CreateList(int n)
    {


     ListNode *head;//指向头结点指针
     ListNode *p,*pre;
     int i;
     head=(ListNode *)malloc(sizeof(ListNode));//为头节点分配内存空间
     head->next=NULL;//将头结点的指针域清空
     pre=head;//先将头结点首地址赋给中间变量pre
     for(i=1;i<=n;i++)//通过for循环不断加入新的结点
      {

       printf("input name of the %d student:",i);//打印出第几个人的名字
       p=(ListNode *)malloc(sizeof(ListNode));//为要插入的节点分配
       //内存空间p指向新插入结点的首地址
       scanf("%s",&p->name);//输入姓名
       printf("input score of the %d student:",i);
       scanf("%d",&p->score);//输入分数
       pre->next=p;//将p指向新结点插入链表也就是头结点指针域指向
       //下个结点
       //第一个结点就是p指向的，因为头结点内容为空
       pre=p;//这个起着指向下一个结点的作用
      }
     p->next=NULL;//最后将最后一个结点的指针域清空了
     return head;//返回这个链表的首地址
    }
    /*-------------------------输出链表-----------------------------------*/
    void PrintList(ListNode *h)
    {

     ListNode *p;
     p=h->next;
     while(p)
      {

       printf("%s,%d",p->name,p->score);
       p=p->next;
       printf("\n");
      }
    }
    /*----------------------插入链表结点--------------------------*/
    /*--------------------------------------------------------------------
    函数名称:InsertList(ListNode *h,int i,char name[],int e,int n)
    函数功能:插入链表结点
    入口参数: h: 头结点地址 i:插入到第几个结点 name:插入
    结点的姓名 e:插入结点的分数 n:
    链表中结点的个数
    除下头结点外的个数

    出口参数:
    --------------------------------------------------------------------*/
    void InsertList(ListNode *h,int i,char name[],int e,int n)
    {


     ListNode *q,*p;//先定义2个指向一个结点的指针
     int j;
     if(i<1 || i>n+1)
      printf("Error! Please input again.\n");
     else
      {

       j=0;
       p=h;//将指针p指向要链表的头结点
       while(j<i-1)
        {

         p=p->next;
         j++;
        }
       q=(ListNode *)malloc(sizeof(ListNode));/*为要插入的
       结点分配内存空间*/
        
       //----赋值操作--------- 
       strcpy(q->name,name); //将名字拷到要插入的节点内
       q->score=e; //将要插入的节点中分数赋值

       //调整指针域
       
       q->next = p->next; /*这个是将新插入的结点指针域指向
       上一个结点指针域指向的结点地址即为p->next*/
        
       p->next=q;/*将要插入结点位置前面的结点指针域
       指向现在插入的结点首地址*/
      }
    }

    /*--------------------------------------------------------------------
    函数名称:DeleteList(ListNode *h, int i, int n)
    函数功能:删除链表结点
    入口参数: h: 头结点地址 i:要删除的结点所在位置
    n:
    链表中结点的个数除下头结点外的个数

    出口参数:
    --------------------------------------------------------------------*/
    void DeleteList(ListNode *h, int i, int n)
    {


     ListNode *p,*q;//首先定义2个指向结点型结构体的指针
     int j;
     char name[10];
     int score;
     if(i<1 || i>n)//如果位置超出了1和n的范围的话则打印出错误信息
      printf("Error! Please input again.\n");
     else//没有超出除头结点外的1到n 的范围的话那么执行删除操作
      {

       j=0;
       p=h;//将指针指向链表的头结点首地址
       while(j<i-1)
        {

         p=p->next;
         j++;
        }
       q=p->next; /*q指向要删除的位置之前的那个结点指针域指向的
       地址q指向的结点就是要删除的结点*/
        
       p->next=q->next;/*这个就是将要删除的结点的前面那个结点
       的指针域指向要删除的结点指针域中存放的下个结点的
       首地址从而实现了删除第i个结点的作用*/

       strcpy(name,q->name);
       score=q->score;
       
       free(q);//释放q指向的结点
       printf("name=%s,score=%d\n",name,score);
      }
    }

    /*--------------------------主函数-------------------------------*/
    void main()
    {


     ListNode *h;//h指向结构体NODE
     int i = 1, n, score;
     char name [10];

     while ( i )
      {


       /*输入提示信息*/
       printf("1--建立新的链表\n");
       printf("2--添加元素\n");
       printf("3--删除元素\n");
       printf("4--输出当前表中的元素\n");
       printf("0--退出\n");

       scanf("%d",&i);
       switch(i)
        {


         case 1:
          printf("n=");   /*输入创建链表结点的个数*/
          scanf("%d",&n);
          h=CreateList(n);/*创建链表*/
          printf("list elements is : \n");
          PrintList(h);
          break;

         case 2:
          printf("input the position. of insert element:");
          scanf("%d",&i);
          printf("input name of the student:");
          scanf("%s",name);
          printf("input score of the student:");
          scanf("%d",&score);
          InsertList(h,i,name,score,n);
          printf("list elements is:\n");
          PrintList(h);
          break;

         case 3:
          printf("input the position of delete element:");
          scanf("%d",&i);
          DeleteList(h,i,name,score,n);
          printf("list elements in : \n");
          PrintList(h);
          break;

         case 4:
          printf("list element is : \n");
          PrintList(h);
          break;
         case 0:
          return;
          break;
         default:
          printf("ERROR!Try again!\n");
        }
      }
    }

     

转载地址：http://tyrsi.baihongyu.com/

你可能感兴趣的文章
python数字逆序输出及多个print输出在同一行
查看>>
ESP8266 WIFI数传 Pixhaw折腾笔记
查看>>
苏宁产品经理面经
查看>>
百度产品经理群面
查看>>
去哪儿一面+平安科技二面+hr面+贝贝一面+二面产品面经
查看>>
element ui 弹窗在IE11中关闭时闪现问题修复
查看>>
vue 遍历对象并动态绑定在下拉列表中
查看>>
Vue动态生成el-checkbox点击无法选中的解决方法
查看>>
python __future__
查看>>
MySQL Tricks1
查看>>
python 变量作用域问题（经典坑）
查看>>
pytorch
查看>>
pytorch（二）
查看>>
pytorch(三)
查看>>
pytorch(四）
查看>>
pytorch(5)
查看>>
pytorch(6)
查看>>
ubuntu相关
查看>>
C++ 调用json
查看>>
nano中设置脚本开机自启动
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-09-21 16:23:06   当前IP: 3.143.239.44   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我