devbox
小舞很执着
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 链式存储 +

作者：小舞很执着 | 2024-08-01 08:03:52

赞

踩

数据结构 链式存储 +

int DeleteLinkList(LinkList *list, char *name);
int ReviseLinkList(LinkList *list, char *name, DATATYPE data);
int DestroyLinkList(LinkList *list);
int InsertTailLinkList(LinkList *list, DATATYPE data);

​​​​​​​删除

修改​​​​​​​

 

销毁

​​​​​​​

 插入

 完整代码展示

  1. #include <stdio.h>
  2. #include "doulink.h"
  3. #include <string.h>
  4. int findbyname(DATATYPE*data,void* arg)
  5. {
  6.     return (0 == strcmp(data->name,(char*)arg));
  7. }
  8. int findbyage(DATATYPE*data,void* arg)
  9. {
  10.     return data->age == *(int*)arg;
  11. }
  12. int main()
  13. {
  14.     DATATYPE data[5]={
  15.         {"zhangsan",'m',20,70},
  16.         {"lisi",'f',21,60},
  17.         {"wangmazi",'m',25,80},
  18.         {"liubei",'f',30,85},
  19.         {"caocao",'f',40,90},
  20.     };
  21.  
  22.     DouLinkList* dl = CreateDouLinkList();
  23.  
  24.     InsertHeadLinkList(dl,&data[0]);
  25.     InsertHeadLinkList(dl,&data[1]);
  26.     InsertHeadLinkList(dl,&data[2]);
  27.  
  28.     ShowDouLinkList(dl,DIR_FORWARD);
  29.     printf("-------------back---------------\n");
  30.     ShowDouLinkList(dl,DIR_BACKWARD);
  31.     printf("-------------find---------------\n");
  32.     //    char want_name[]="lisi";
  33.     //    //DouLinkNode* tmp = FindLinkList(dl,findbyname,want_name);
  34.     //    int want_age = 25;
  35.     //    DouLinkNode* tmp = FindLinkList(dl,findbyage,&want_age);
  36.     //    if(NULL == tmp)
  37.     //    {
  38.     //        printf("can't find person ,name:%s\n",want_name);
  39.     //    }
  40.     //    else
  41.     //    {
  42.  
  43.     //        printf("%s:%d\n",tmp->data.name,tmp->data.score);
  44.     //    }
  45.  
  46.     //    RevertDouLinkList(dl);
  47.     //    printf("-------------rev---------------\n");
  48.     //    ShowDouLinkList(dl,DIR_FORWARD);
  49.     //    DeleteLinkList(dl,findbyname,"lisi");
  50.     //    printf("-------------del forware---------------\n");
  51.     //    ShowDouLinkList(dl,DIR_FORWARD);
  52.     //    printf("-------------back---------------\n");
  53.     //    ShowDouLinkList(dl,DIR_BACKWARD);
  54.  
  55.     //    ModifyDouLinkList(dl,findbyname,"zhangsan",&data[3]);
  56.     //    printf("-------------modify---------------\n");
  57.     //    ShowDouLinkList(dl,DIR_FORWARD);
  58.  
  59.     InserPosDouLinkList(dl,&data[3],3);
  60.     printf("-------------pos---------------\n");
  61.     ShowDouLinkList(dl,DIR_FORWARD);
  62.     printf("-------------back---------------\n");
  63.     ShowDouLinkList(dl,DIR_BACKWARD);
  64.  
  65.  
  66.     DestroyDouLinkList(&dl);
  67.  
  68.     printf("Hello World!\n");
  69.     return 0;
  70. }
  1. #include "doulink.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. DouLinkList *CreateDouLinkList()
  7. {
  8.     //DouLinkList dl ;
  9.     DouLinkList* dl = (DouLinkList*)malloc(sizeof(DouLinkList));
  10.     if(NULL == dl)
  11.     {
  12.         perror("CreateDouLinkList malloc");
  13.         //exit(1);
  14.         return NULL;
  15.     }
  16.     dl->head =NULL;
  17.     dl->clen = 0 ;
  18.  
  19.     return dl;
  20. }
  21.  
  22. int InsertHeadLinkList(DouLinkList *list, DATATYPE *data)
  23. {
  24.     DouLinkNode*newnode = malloc(sizeof(DouLinkNode));
  25.     if(NULL == newnode)
  26.     {
  27.         perror("InsertHeadLinkList malloc");
  28.         return 1;
  29.     }
  30.     memcpy(&newnode->data,data,sizeof(DATATYPE));
  31.     newnode->next = NULL;
  32.     newnode->prev= NULL;
  33.  
  34.     if(0==list->clen)//empty
  35.     {
  36.         list->head = newnode;
  37.     }
  38.     else
  39.     {
  40.         newnode->next = list->head;
  41.         list->head->prev = newnode;
  42.         list->head = newnode;
  43.     }
  44.     list->clen++;
  45.     return 0;
  46.  
  47.  
  48. }
  49.  
  50. int ShowDouLinkList(DouLinkList *list, DIRECT direct)
  51. {
  52.     int i = 0 ;
  53.     DouLinkNode* tmp = list->head;
  54.     if(direct==DIR_FORWARD)
  55.     {
  56.         for(i=0;i<GetSizeDouLinkList(list);i++)
  57.         {
  58.             printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
  59.             tmp=tmp->next;
  60.         }
  61.     }
  62.     else
  63.     {
  64.         while(tmp->next)
  65.         {
  66.             tmp=tmp->next;
  67.         }
  68.         for(i=0;i<GetSizeDouLinkList(list);i++)
  69.         {
  70.             printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
  71.             tmp=tmp->prev;
  72.         }
  73.     }
  74.     return 0;
  75. }
  76.  
  77. int GetSizeDouLinkList(DouLinkList *list)
  78. {
  79.     return list->clen;
  80. }
  81.  
  82. DouLinkNode *FindLinkList(DouLinkList *list, PFUN fun, void *arg)
  83. {
  84.     DouLinkNode* tmp = list->head;
  85.     int size = GetSizeDouLinkList(list);
  86.     int i =  0;
  87.     for(i = 0 ;i<size;i++)
  88.     {
  89.         //if(0==strcmp(tmp->data.name))
  90.         if(fun(&tmp->data,arg))
  91.         {
  92.             return tmp;
  93.         }
  94.         tmp= tmp->next;
  95.     }
  96.     return NULL;
  97. }
  98.  
  99. int RevertDouLinkList(DouLinkList *list)
  100. {
  101.     int size = GetSizeDouLinkList(list);
  102.     if(size<2)
  103.     {
  104.         return 0;
  105.     }
  106.  
  107.     DouLinkNode* prev= NULL;
  108.     DouLinkNode* tmp = list->head;
  109.     DouLinkNode*next= tmp->next;
  110.     while(1)
  111.     {
  112.         tmp->next = prev;
  113.         tmp->prev = next;
  114.         prev= tmp;
  115.         tmp = next;
  116.         if(NULL == tmp)
  117.         {
  118.             break;
  119.         }
  120.         next =next->next;
  121.     }
  122.     list->head = prev;
  123.     return 0;
  124. }
  125.  
  126. int DeleteLinkList(DouLinkList *list, PFUN fun, void *arg)
  127. {
  128.     if(NULL == list)
  129.     {
  130.         fprintf(stderr,"DouLinkList is null");
  131.         return 1;
  132.     }
  133.     if(IsEmptyDouLinkList(list))
  134.     {
  135.         fprintf(stderr,"DouLinkList is empty");
  136.         return 1;
  137.     }
  138.     DouLinkNode* ret = FindLinkList(list,fun,arg);
  139.     if(NULL==ret)
  140.     {
  141.         fprintf(stderr,"DeleteLinkList error,cant find\n");
  142.         return 1;
  143.     }
  144.     if(ret == list->head)
  145.     {
  146.         list->head = ret->next;
  147.         list->head->prev = NULL;
  148.     }
  149.     else
  150.     {
  151.         if(ret->next)
  152.         ret->next->prev = ret->prev;
  153.         ret->prev->next = ret->next;
  154.     }
  155.  
  156.     free(ret);
  157.     list->clen--;
  158.     return 0;
  159. }
  160.  
  161. int IsEmptyDouLinkList(DouLinkList *list)
  162. {
  163.     return 0 == list->clen;
  164. }
  165.  
  166. int ModifyDouLinkList(DouLinkList *list, PFUN fun, void *arg, DATATYPE *data)
  167. {
  168.     DouLinkNode* ret = FindLinkList(list,fun,arg);
  169.     if(NULL == ret)
  170.     {
  171.         fprintf(stderr,"ModifyDouLinkList error,cant find\n");
  172.         return 1;
  173.     }
  174.     memcpy(&ret->data,data,sizeof(DATATYPE));
  175.     return 0;
  176. }
  177.  
  178. int DestroyDouLinkList(DouLinkList **list)
  179. {
  180.     DouLinkNode* tmp=(*list)->head;
  181.     while(tmp)
  182.     {
  183.     (*list)->head=(*list)->head->next;
  184.     free(tmp);
  185.     tmp = (*list)->head;
  186.  
  187.     }
  188.     free(*list);
  189.     (*list)= NULL;
  190.     return 0;
  191. }
  192.  
  193. int InserPosDouLinkList(DouLinkList *list, DATATYPE *data,int pos)
  194. {
  195.     if(pos<0 ||pos>GetSizeDouLinkList(list))
  196.     {
  197.         fprintf(stderr,"InserPosDouLinkList error,index error\n");
  198.         return 1;
  199.  
  200.     }
  201.     if(IsEmptyDouLinkList(list) || 0 == pos)
  202.     {
  203.         return InsertHeadLinkList(list,data);
  204.     }
  205.     else
  206.     {
  207.         DouLinkNode* tmp = list->head;
  208.         tmp= list->head;
  209.         DouLinkNode* newnode = (DouLinkNode*)malloc(sizeof(DouLinkNode));
  210.         if(NULL == newnode)
  211.         {
  212.             perror("InserPosDouLinkList malloc");
  213.             return 1;
  214.         }
  215.         memcpy(&newnode->data,data,sizeof(DATATYPE));
  216.         newnode->prev = NULL;
  217.         newnode->next = NULL;
  218.         int i = pos-1;
  219.         while(i--)
  220.         {
  221.             tmp=tmp->next;
  222.         }
  223.         newnode ->prev = tmp;
  224.         newnode->next = tmp->next;//这时候都是NULL，如果是尾插入不走if
  225.  
  226.         if(tmp->next)
  227.         {
  228.         tmp->next->prev = newnode;//中间插入
  229.         }
  230.         tmp->next = newnode;
  231.     }
  232.     list->clen++;
  233.     return 0;
  234. }
  1. #ifndef DOULINK_H
  2. #define DOULINK_H
  3. typedef struct{
  4.     char name[32];
  5.     char sex;
  6.     int age;
  7.     int score;
  8. }DATATYPE;
  9. typedef int (*PFUN)(DATATYPE*data,void* arg);//表示fun（）中的参数书形式
  10. typedef struct node {
  11.     DATATYPE data;
  12.     struct node *next,*prev;
  13. }DouLinkNode;
  14.  
  15. typedef struct{
  16.     DouLinkNode *head;
  17.     int clen;
  18. }DouLinkList;
  19. typedef enum{DIR_FORWARD,DIR_BACKWARD}DIRECT;
  20. DouLinkList* CreateDouLinkList();
  21. int InsertHeadLinkList(DouLinkList *list, DATATYPE *data);
  22. int ShowDouLinkList(DouLinkList *list,DIRECT direct);
  23. int GetSizeDouLinkList(DouLinkList *list);
  24. DouLinkNode *FindLinkList(DouLinkList *list, PFUN fun,void* arg);
  25. int RevertDouLinkList(DouLinkList *list);
  26. int DeleteLinkList(DouLinkList *list, PFUN fun,void* arg);
  27. int IsEmptyDouLinkList(DouLinkList *list);
  28. int ModifyDouLinkList(DouLinkList *list,PFUN fun,void* arg,DATATYPE *data);
  29. int DestroyDouLinkList(DouLinkList **list);
  30. int InserPosDouLinkList(DouLinkList *list,DATATYPE *data,int pos);
  31. #endif // DOULINK_H

序表和链表 优缺点


    存储方式：
        顺序表是一段连续的存储单元
        链表是逻辑结构连续物理结构（在内存中的表现形式）不连续
    时间性能，
        查找 顺序表O(1)
             链表  O(n)
        插入和删除
            顺序表 O(n)
            链表   O(1)
            
    空间性能
            顺序表 需要预先分配空间，大小固定
            链表， 不需要预先分配，大小可变，动态分配
            
            
    循环链表
        简单的来说，就是将原来单链表中最有一个元素的next指针指向第一个元素或头结点，链表就成了一个环，头尾相连，就成了循环链表。circultlar linker list.
        
        注意非空表，和空表。多数会加入头结点。
        原来结束的条件是
        p->next != NULL ------->>>>> p-next != Head 
        
    双向链表
    double link list。
    
    typedef struct DulNode
    {
    
        ElemType date;
        struct DulNode *pri;
        sturct DulNode *next；
    }DulNode,*DuLinkList;
    

 习题

1）双向链表逆序

2)实现mplay的播放列表

main.c

  1. #include <stdio.h>
  2. #include "doulink.h"
  3. #include <string.h>
  4. #include "func.h"
  5. #include <stdlib.h>
  6. void show_menu( DouLinkList* dl)
  7. {
  8.     printf("1.show_list\n");
  9.     printf("2.prev\n");
  10.     printf("3.next\n");
  11.     printf("4.end\n");
  12.     char buf[10]={0};
  13.     fgets(buf,sizeof(buf),stdin);
  14.     int num = atoi(buf);
  15.     switch (num) {
  16.     case 1:
  17.         ShowDouLinkList(dl,DIR_FORWARD);
  18.         break;
  19.     case 2:
  20.         GetPrev(dl);
  21.         break;
  22.     case 3:
  23.         Getnext(dl);
  24.         break;
  25.     case 4:
  26.         exit(1);
  27.         break;
  28.     default:
  29.         break;
  30.     }
  31. }
  32. int main()
  33. {
  34.     DouLinkList* dl = CreateDouLinkList();
  35.     do_ls("/home/linux",dl);
  36.  
  37.     ShowDouLinkList(dl,DIR_FORWARD);
  38.     char *pathname=NULL;
  39.     while(1)
  40.     {
  41.          show_menu(dl);
  42.          pathname = GetCurrent(dl);
  43.          printf("currnt play file:%s\n",pathname);
  44.  
  45.     }
  46.  
  47.  
  48.     //atexit();
  49.     printf("Hello World!\n");
  50.     return 0;
  51. }

doulink.c

  1. #include "doulink.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. DouLinkList *CreateDouLinkList()
  7. {
  8.     //DouLinkList dl ;
  9.     DouLinkList* dl = (DouLinkList*)malloc(sizeof(DouLinkList));
  10.     if(NULL == dl)
  11.     {
  12.         perror("CreateDouLinkList malloc");
  13.         //exit(1);
  14.         return NULL;
  15.     }
  16.     dl->head =NULL;
  17.     dl->clen = 0 ;
  18.     dl->currnet =NULL;
  19.  
  20.     return dl;
  21. }
  22.  
  23. int InsertHeadLinkList(DouLinkList *list, DATATYPE *data)
  24. {
  25.     DouLinkNode*newnode = malloc(sizeof(DouLinkNode));
  26.     if(NULL == newnode)
  27.     {
  28.         perror("InsertHeadLinkList malloc");
  29.         return 1;
  30.     }
  31.     memcpy(&newnode->data,data,sizeof(DATATYPE));
  32.     newnode->next = NULL;
  33.     newnode->prev= NULL;
  34.  
  35.     if(0==list->clen)//empty
  36.     {
  37.         list->head = newnode;
  38.     }
  39.     else
  40.     {
  41.         newnode->next = list->head;
  42.         list->head->prev = newnode;
  43.         list->head = newnode;
  44.     }
  45.     list->clen++;
  46.     return 0;
  47.  
  48.  
  49. }
  50.  
  51. int ShowDouLinkList(DouLinkList *list, DIRECT direct)
  52. {
  53.     int i = 0 ;
  54.     DouLinkNode* tmp = list->head;
  55.     if(direct==DIR_FORWARD)
  56.     {
  57.         for(i=0;i<GetSizeDouLinkList(list);i++)
  58.         {
  59.             printf("%d %s\n",i,tmp->data.pathname);
  60.             tmp=tmp->next;
  61.         }
  62.     }
  63.  
  64.     return 0;
  65. }
  66.  
  67. int GetSizeDouLinkList(DouLinkList *list)
  68. {
  69.     return list->clen;
  70. }
  71.  
  72. DouLinkNode *FindLinkList(DouLinkList *list, PFUN fun, void *arg)
  73. {
  74.     DouLinkNode* tmp = list->head;
  75.     int size = GetSizeDouLinkList(list);
  76.     int i =  0;
  77.     for(i = 0 ;i<size;i++)
  78.     {
  79.         //if(0==strcmp(tmp->data.name))
  80.         if(fun(&tmp->data,arg))
  81.         {
  82.             return tmp;
  83.         }
  84.         tmp= tmp->next;
  85.     }
  86.     return NULL;
  87. }
  88.  
  89. int RevertDouLinkList(DouLinkList *list)
  90. {
  91.     int size = GetSizeDouLinkList(list);
  92.     if(size<2)
  93.     {
  94.         return 0;
  95.     }
  96.  
  97.     DouLinkNode* prev= NULL;
  98.     DouLinkNode* tmp = list->head;
  99.     DouLinkNode*next= tmp->next;
  100.     while(1)
  101.     {
  102.         tmp->next = prev;
  103.         tmp->prev = next;
  104.         prev= tmp;
  105.         tmp = next;
  106.         if(NULL == tmp)
  107.         {
  108.             break;
  109.         }
  110.         next =next->next;
  111.     }
  112.     list->head = prev;
  113.     return 0;
  114. }
  115.  
  116.  
  117.  
  118. char *GetCurrent(DouLinkList *list)
  119. {
  120.     return list->currnet->data.pathname;
  121. }
  122.  
  123. int GetPrev(DouLinkList *list)
  124. {
  125.     list->currnet = list->currnet->prev;
  126.     if(NULL == list->currnet)
  127.     {
  128.  
  129.         list->currnet = list->head;
  130.         while(list->currnet->next)
  131.         {
  132.             list->currnet = list->currnet->next;
  133.         }
  134.  
  135.     }
  136.     return 0;
  137.  
  138. }
  139.  
  140. int Getnext(DouLinkList *list)
  141. {
  142.      list->currnet = list->currnet->next;
  143.      if(NULL == list->currnet)
  144.      {
  145.            list->currnet = list->head;
  146.  
  147.      }
  148.      return 0;
  149. }

fun.c

  1. #include "func.h"
  2. #include <dirent.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. int do_ls(char *path,DouLinkList*dl)
  7. {
  8.     {
  9.  
  10.         DIR* dir = opendir(path);
  11.            if(NULL == dir)
  12.            {
  13.                printf("opendir");
  14.                return 1;
  15.            }
  16.             DATATYPE data;
  17.            while(1)
  18.            {
  19.                struct dirent *info =  readdir(dir);
  20.                //procintf("%s  %lu",info->d_name,info->d_ino);
  21.                if(NULL == info)
  22.                {
  23.                    break;
  24.                }
  25.                if(strlen(info->d_name ) >3)// 1.flv  /home/linux/1.flv
  26.                {
  27.                    if(0==strcmp(&info->d_name[strlen(info->d_name)-3],"mp3")
  28.                       ||0==strcmp(&info->d_name[strlen(info->d_name)-3],"flv")
  29.                       ||0==strcmp(&info->d_name[strlen(info->d_name)-3],"mp4"))
  30.                    {
  31.                        bzero(&data,sizeof(data));
  32.  
  33.                        sprintf(data.pathname,"%s/%s",path,info->d_name);
  34.                        //sprintf(song.songlist[song.total++],"%s/%s",path,info->d_name);
  35.                        InsertHeadLinkList(dl,&data);
  36.  
  37.  
  38.                    }
  39.                }
  40.                else
  41.                {
  42.                    continue;
  43.                }
  44.            }
  45.            closedir(dir);
  46.     }
  47.      dl->currnet = dl->head;
  48.     return 0;
  49. }

fun.h

  1. #ifndef FUNC_H
  2. #define FUNC_H
  3. #include "doulink.h"
  4. int do_ls(char *path,DouLinkList*dl);
  5.  
  6. #endif // FUNC_H

doulink.h

  1. #ifndef DOULINK_H
  2. #define DOULINK_H
  3. typedef struct{
  4.     char pathname[512];
  5. }DATATYPE;
  6. typedef int (*PFUN)(DATATYPE*data,void* arg);
  7. typedef struct node {
  8.     DATATYPE data;
  9.     struct node *next,*prev;
  10.  
  11. }DouLinkNode;
  12.  
  13. typedef struct{
  14.     DouLinkNode *head;
  15.     struct node *currnet;
  16.     int clen;
  17. }DouLinkList;
  18. typedef enum{DIR_FORWARD,DIR_BACKWARD}DIRECT;
  19. DouLinkList* CreateDouLinkList();
  20. int InsertHeadLinkList(DouLinkList *list, DATATYPE *data);
  21. int ShowDouLinkList(DouLinkList *list,DIRECT direct);
  22. int GetSizeDouLinkList(DouLinkList *list);
  23. DouLinkNode *FindLinkList(DouLinkList *list, PFUN fun,void* arg);
  24. int RevertDouLinkList(DouLinkList *list);
  25. char* GetCurrent(DouLinkList *list);
  26.  int GetPrev(DouLinkList *list);
  27.  int Getnext(DouLinkList *list);
  28. #endif // DOULINK_H

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/913092
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号