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

双向链表

2015-04-04 Lover雪儿

1 #include 
   
      2 #include 
    
       3   4 #define OK        1  5 #define ERROR    0  6 #define TRUE    1  7 #define FALSE    0  8   9 typedef char    ElemType; 10 typedef int        Status; 11  12 //双向链表结构体定义 13 typedef struct DualNode 14 { 15     ElemType data; 16     struct DualNode *prior; 17     struct DualNode *next; 18 }DualNode, *DuLinkList; 19  20 /************************************************** 21         初始化链表 22 **************************************************/ 23 Status Init_List(DuLinkList *L) 24 { 25     DualNode *p, *q; 26     int i; 27     //生成 头结点 28     *L = (DuLinkList)malloc(sizeof(DualNode)); 29     if( !(*L) ){ 30         return ERROR; 31     } 32     (*L)->next = (*L)->prior = (*L); 33     p = (*L);    //头结点 34      35     //生成链表 36     for(i = 0; i<26; i++){ 37         q = (DualNode *)malloc(sizeof(DualNode)); 38         if(!q){ 39             return ERROR; 40         } 41         q->data = 'A' + i;  //依次给链表赋值 字符表 42  43         q->prior = p;   44         p->next = q; 45         q->next = (*L)->next; 46          47         p = q; 48     } 49     p->next = (*L)->next;    //让尾结点的后向指针指向头结点指向的地址，即第一个单元 50     (*L)->next->prior = p;    //让头结点的前向指针指向尾节点 51     return OK; 52 } 53 /************************************************** 54     判断空链表 55 **************************************************/ 56 Status List_Empty(DuLinkList *L){ 57     if((*L)->next == (*L) && (*L)->prior == (*L)) 58         return TRUE; 59     else 60         return FALSE; 61 } 62 /************************************************** 63     计算L中的个数 64 **************************************************/ 65 int List_Length(DuLinkList *L){ 66     int i = 0; 67     DuLinkList p = (*L)->next; 68     while(p != (*L))    //检测是否已经循环了一遍 69     { 70         p = p->next; 71         ++i; 72     } 73     i ++; 74     return i; 75 } 76  77 /************************************************** 78     排序算法，链表前后/后向移动i个结点 79 **************************************************/ 80 void Caesar(DuLinkList *L, int i){ 81     if(i > 0){ 82         do{ 83             (*L) = (*L)->next;  84         }while(--i); 85     } 86     if(i < 0){ 87         do{ 88             (*L) = (*L)->prior; 89         }while(++i); 90     } 91 } 92  93 /************************************************** 94     循环打印链表中的数据 95 **************************************************/ 96 void printf_list(DuLinkList *L){ 97     DuLinkList p = (*L)->next; 98     printf("%c ",(*L)->data); 99     while(p != (*L)){100         printf("%c ",p->data);101         p = p->next;102     }103     printf("\n\n");104 }105 106 /**************************************************107     向链表中插入数据108 **************************************************/109 Status List_Insert(DuLinkList *L,int i,ElemType dat){110     DuLinkList q, p = (*L),tmp;111     if(i < 1 || i>List_Length(L))112         return ERROR;113     while(--i){114         p = p->next;115     }116     q = (DuLinkList)malloc(sizeof(DualNode));117     q->data = dat;118         119     tmp = p->next;120     p->next = q;121     q->prior = p;122     q->next = tmp;123     tmp->prior = q;124     return OK;125 }126 127 /**************************************************128     从链表中删除数据129 **************************************************/130 Status List_delete(DuLinkList *L,int i){131     DuLinkList p = (*L);132     if(i < 1 || i>List_Length(L))133         return ERROR;134     if(i == 1){135         Caesar(L, 1);    //排序136         //printf_list(L);137         i = List_Length(L) + 1;138     }139     //printf_list(L);140     while(--i){141         p = p->next;142     }143     p->next->prior = p->prior;144     p->prior->next = p->next;145     free(p);146     147     return OK;148 }149 150 /**************************************************151         清空链表152 **************************************************/153 void Clear_List(DuLinkList *L){154     DuLinkList q, p=(*L)->next;155     while(p != (*L)){156         q = p->next;157         free(p);158         p = q;159     }160     (*L)->prior = (*L)->next = *L;161     printf("\n成功清空双向链表!\n");162 }163 164 /**************************************************165         删除链表166 **************************************************/167 void Destroy_List(DuLinkList *L){168     DuLinkList q, p=(*L)->next;169     while(p != (*L)->next){170         q = p->next;171         free(p);172         p = q;173     }174     free(*L);175     *L = NULL;176     printf("\n成功销毁双向链表!\n");177 }178 /**************************************************179         主循环180 **************************************************/181 int main(void)182 {183     DuLinkList L,p;184     int  n , m ;185     char k;186     187     Init_List(&L);  //初始化链表188     p = L->next;189 190     printf("双向链表总共有%d个元素:\n",List_Length(&p));191     printf_list(&p); //循环打印链表元素192 193     while(1){194         printf("0:退出并销毁链表\n1:打印出当前链表\n2:插入/删除结点\n3:链表有序移动\n\n");195         scanf("%d",&n);196         if(n == 0){197             break;198         }else if(n == 1){199             printf_list(&p); //循环打印链表元素200         }else if(n == 2){201             printf_list(&p); //循环打印链表元素202             while(1){203                 printf("0:退出\n1:插入数据\n2:删除数据\n");204                 scanf("%d",&n);205                 if(n == 0){206                     break;207                 }else if(n == 1){208                     printf("请输入要插入的位置、数据,格式:m k\n");209                     scanf("%d %c",&m,&k);210                     List_Insert(&p,m,k);211                     printf_list(&p); //循环打印链表元素212                 }else if(n == 2){213                     printf("请输入要删除的位置\n");214                     scanf("%d",&m);215                     List_delete(&p,m);216                     printf_list(&p); //循环打印链表元素217                 }else{218                     printf("请正确输入命令，谢谢!!!\n");219                 }220             }221         }else if(n == 3){222             while(1){223                 printf("请输入一个整数[正数(前向移动)/负数(后向移动)/0(退出)]：\n");224                 scanf("%d",&n);225                 if(n == 0)226                     break;    227                 Caesar(&p, n);    //排序228                 printf_list(&p); //循环打印链表元素229             }230         }else{231             printf("请正确输入命令，谢谢!!!\n");232         }233     }234     printf_list(&(L->next)); //循环打印链表元素235     Destroy_List(&L);236     return 0;237 }
    
   

转载地址：https://ciellee.blog.csdn.net/article/details/82599488 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！