首页 > 代码库 > 链表 其他操作

链表 其他操作

 1 实验4  链表其它操作 2 实验目的 3 1.熟悉对单链表的一些其它操作。 4 2.掌握循环链表和双链表的一些操作,理解与单链表操作的不同。 5 实验内容 6 程序1 7 设单链表L是一个非递减有序表,写一算法将x插入其中后仍保持L的有序性。 8 设计要求:在程序中构造三个子程序分别为 9 LinkedList  LinkedListCreat( )                     /*建立链表*/10 void InsertList(LinkedList L,int x)              /*插入结点*/11 void print(LinkedList L);                         /*输出链表中的结点*/12 程序213 利用原空间,将两个单链表合并成一个单链表。14 设计要求:在程序中构造三个子程序分别为15 LinkedList  LinkedListCreat( )                          /*建立链表*/16 LinkedList ListConcat(LinkedList La,LinkedList Lb)   /*合并链表*/17 void print(LinkedList L);                         /*输出链表中的结点*/18 程序319 已知两个非递减有序的单链表la和lb,将la和lb合并成一个线性表lc,lc也非递减有序。20 设计要求:在程序中构造三个子程序分别为21 LinkedList  LinkedListCreat( )                     /*建立链表*/22 LinkedList union(LinkedList La,Lb)                /*合并链表*/23 void print(LinkedList Lc);                         /*输出链表中的结点*/24 程序425 已知一个单链表,利用原表把单链表逆置。26 设计要求:在程序中构造三个子程序分别为27 LinkedList  LinkedListCreat( )                     /*建立链表*/28 void List_reverse(LinkedList L)                   /*逆置链表*/29 void print(LinkedList L);                         /*输出链表中的结点*/30 程序531 在计算机上先输入一串正整数的序列。请编写一个程序,首先用链表存储该序列。然后执行删除操作,即先从链表中找出最小的结点,删除它。然后再在剩余的链表中,找出最小的结点,再删除之。直至表空为止。32 设计要求:在程序中构造四个子程序分别为33 LinkedList  LinkedListCreat( )                 /*建立链表*/34 int min(LinkedList head);                      /*求链表中的最小结点*/35 LinkedList del(LinkedList head, int num);   /*删除结点*/36 void print(LinkedList L);                      /*输出链表中的结点*/37 程序638 利用单循环链表作为存储结构,实现实验二中的约瑟夫环问题。39 设计要求:在程序中构造三个子程序分别为40 CiLinkList  CiLinkListCreat( )              /*建立不带头结点的单循环链表*/41 void del(CiLinkList last, int N, int K)   /*依次输出符合要求的结点*/42 void print(CiLinkList L);                   /*输出链表中的结点*/43 程序744 在双向链表上实现线性表的下列运算:45 a)         建立 DLinkedList  creat()46 b)        插入void  DlistInsert(DLinkedList L,int x,int i)47 c)        删除void  DlistDelete(DLinkedList L,int i)48 程序849 设有一个双链表,每个结点中除有prior,next及data〔可设为正整数〕三个域之外,还有一个专门记录访问该结点次数的数据域freq,其值在初始化时为零。每当在链表中进行一次Search〔l,key〕时,则数据域data之值等于key的结点,其freq域之值将加一。并使该双链表中结点按freq之值的递减顺序排列,freq值越大的结点越靠近表头。请编写符合上述要求的Search〔l,key〕程序。50 设计要求:在程序中构造三个子程序分别为51 DLinkedList Creat()                          /*建立链表*/52 void Search(DLinkedList head,int key)    /*查找链表中符合要求的结点*/53 void print(DLinkedList head);              /*输出链表中的结点*/

 

 1 /*    程序1 2 设单链表L是一个非递减有序表,写一算法将x插入其中后仍保持L的有序性。 3 设计要求:在程序中构造三个子程序分别为 4 LinkedList  LinkedListCreat( )                     //建立链表 5 void InsertList(LinkedList L,int x)              //插入结点 6 void print(LinkedList L);                         //输出链表中的结点 7 */ 8 #include <stdio.h> 9 #include <malloc.h>10 /* 单链表的结点类型 */11 typedef struct LNode{12     int data;13     LNode* next;14 }LNode,*LinkedList;15 16 LinkedList  LinkedListCreat( )                     //建立链表17 {18     LinkedList head = (LNode*)malloc(sizeof(LNode));19     head->next = NULL;20     printf("请输入链表大小:(最多1000个)\n");21     int n,i,j,a[1001];22     scanf("%d",&n);23     printf("请输入链表的所有元素:\n");24     for(i=1;i<=n;i++)    //输入元素25         scanf("%d",&a[i]);26     //冒泡排序27     for(i=1;i<n;i++)28         for(j=1;j<=n-i;j++)29             if(a[j]>a[j+1]){30                 int t;31                 t=a[j];a[j]=a[j+1];a[j+1]=t;32             }33     //尾插法创建链表34     LinkedList p = head;35     for(i=1;i<=n;i++){36         LinkedList t =  (LNode*)malloc(sizeof(LNode));37         t->data =http://www.mamicode.com/ a[i];38         t->next = NULL;39         p->next = t;40         p = t;41     }42     return head;43 }44 void InsertList(LinkedList L,int x)              //插入结点45 {46     LinkedList p = L->next,pre = L;47     while(p){48         if(x < p->data){    //插在pre后面,p前面49             LinkedList t =  (LNode*)malloc(sizeof(LNode));50             t->data =http://www.mamicode.com/ x;51             t->next = p;52             pre->next = t;53             break;54         }55         pre = p;56         p = p->next;57     }58     if(p==NULL){    //如果这个数比链表中任何一个数都大59         LinkedList t =  (LNode*)malloc(sizeof(LNode));60         t->data =http://www.mamicode.com/ x;61         t->next = NULL;62         pre->next = t;63     }64 }65 66 void print(LinkedList L)                       //输出链表中的结点67 {68     LinkedList p=L->next;69     while(p){70         printf("%d ",p->data);71         p = p->next;72     }73     printf("\n");74 }75 int main()76 {77     int x;78     printf("设单链表L是一个非递减有序表,将x插入其中后仍保持L的有序性。\n");79     LinkedList head = LinkedListCreat();80     printf("请输入要插入的元素值:\n");81     while(scanf("%d",&x)!=EOF){82         InsertList(head,x);83         printf("插入之后的单链表:\n");84         print(head);85         printf("---------------------\n");86         printf("请输入要插入的元素值:\n");87     }88     return 0;89 }
 1 /* 程序2 2 利用原空间,将两个单链表合并成一个单链表。 3 设计要求:在程序中构造三个子程序分别为 4 LinkedList  LinkedListCreat( )                          //建立链表 5 LinkedList ListConcat(LinkedList La,LinkedList Lb)   //合并链表 6 void print(LinkedList L);                         //输出链表中的结点 7 */ 8 #include <stdio.h> 9 #include <malloc.h>10 /* 单链表的结点类型 */11 typedef struct LNode{12     int data;13     LNode* next;14 }LNode,*LinkedList;15 16 LinkedList  LinkedListCreat( )                     //建立链表17 {18     LinkedList head = (LNode*)malloc(sizeof(LNode));19     head->next = NULL;20     printf("请输入链表大小:(最多1000个)\n");21     int n,i,a[1001];22     scanf("%d",&n);23     printf("请输入链表的所有元素:\n");24     for(i=1;i<=n;i++)    //输入元素25         scanf("%d",&a[i]);26     //尾插法创建链表27     LinkedList p = head;28     for(i=1;i<=n;i++){29         LinkedList t =  (LNode*)malloc(sizeof(LNode));30         t->data =http://www.mamicode.com/ a[i];31         t->next = NULL;32         p->next = t;33         p = t;34     }35     return head;36 }37 38 LinkedList ListConcat(LinkedList La,LinkedList Lb)   //合并链表39 {40     LinkedList head = La;41     while(La->next){    //找到La的最后一个节点42         La = La->next;43     }44     La->next = Lb->next;    //把La的最后一个节点和La的第一个节点连接上45     return head;46 }47 48 void print(LinkedList L)                       //输出链表中的结点49 {50     LinkedList p=L->next;51     while(p){52         printf("%d ",p->data);53         p = p->next;54     }55     printf("\n");56 }57 58 int main()59 {60     printf("利用原空间,将两个单链表合并成一个单链表。\n");61     printf("1.创建单链表La\n");62     LinkedList La = LinkedListCreat();63     printf("2.创建单链表Lb\n");64     LinkedList Lb = LinkedListCreat();65     printf("3.合并单链表\n");66     LinkedList Lc = ListConcat(La,Lb);67     printf("合并成功!\n");68     printf("4.输出合并后的链表\n");69     print(Lc);70     return 0;71 }
  1 /* 程序3  2 已知两个非递减有序的单链表la和lb,将la和lb合并成一个线性表lc,lc也非递减有序。  3 设计要求:在程序中构造三个子程序分别为  4 LinkedList  LinkedListCreat( )                     //建立链表  5 LinkedList union(LinkedList La,Lb)                //合并链表  6 void print(LinkedList Lc);                         //输出链表中的结点  7 */  8 #include <stdio.h>  9 #include <malloc.h> 10 /* 单链表的结点类型 */ 11 typedef struct LNode{ 12     int data; 13     LNode* next; 14 }LNode,*LinkedList; 15  16 LinkedList  LinkedListCreat( )                     //按顺序建立链表 17 { 18     LinkedList head = (LNode*)malloc(sizeof(LNode)); 19     head->next = NULL; 20     printf("请输入链表大小:(最多1000个)\n"); 21     int n,i,j,a[1001]; 22     scanf("%d",&n); 23     printf("请输入链表的所有元素:\n"); 24     for(i=1;i<=n;i++)    //输入元素 25         scanf("%d",&a[i]); 26     //冒泡排序 27     for(i=1;i<n;i++) 28         for(j=1;j<=n-i;j++) 29             if(a[j]>a[j+1]){ 30                 int t; 31                 t=a[j];a[j]=a[j+1];a[j+1]=t; 32             } 33     //尾插法创建链表 34     LinkedList p = head; 35     for(i=1;i<=n;i++){ 36         LinkedList t =  (LNode*)malloc(sizeof(LNode)); 37         t->data =http://www.mamicode.com/ a[i]; 38         t->next = NULL; 39         p->next = t; 40         p = t; 41     } 42     return head; 43 } 44  45 LinkedList Union(LinkedList La,LinkedList Lb)                //合并链表 46 { 47     LinkedList head =  (LNode*)malloc(sizeof(LNode)); 48     LinkedList p = head; 49     La = La->next,Lb = Lb->next; 50     while(La && Lb){    //比较,直到其中一个链表比较完 51         if(La->data < Lb->data){ 52             LinkedList t =  (LNode*)malloc(sizeof(LNode)); 53             t->data = http://www.mamicode.com/La->data; 54             t->next = NULL; 55             p->next = t; 56             p = p->next; 57             La = La->next; 58         } 59         else { 60             LinkedList t =  (LNode*)malloc(sizeof(LNode)); 61             t->data = http://www.mamicode.com/Lb->data; 62             t->next = NULL; 63             p->next = t; 64             p = p->next; 65             Lb = Lb->next; 66         } 67     } 68     if(La){    //La还没比较完 69         while(La){ 70             LinkedList t =  (LNode*)malloc(sizeof(LNode)); 71             t->data = http://www.mamicode.com/La->data; 72             t->next = NULL; 73             p->next = t; 74             p = p->next; 75             La = La->next; 76         } 77     } 78     else if(Lb){    //Lb还没比较完 79         while(Lb){ 80             LinkedList t =  (LNode*)malloc(sizeof(LNode)); 81             t->data = http://www.mamicode.com/Lb->data; 82             t->next = NULL; 83             p->next = t; 84             p = p->next; 85             Lb = Lb->next; 86         } 87     } 88     return head; 89 } 90  91 void print(LinkedList Lc)                       //输出链表中的结点 92 { 93     LinkedList p=Lc->next; 94     while(p){ 95         printf("%d ",p->data); 96         p = p->next; 97     } 98     printf("\n"); 99 }100 101 int main()102 {103     printf("已知两个非递减有序的单链表la和lb,将la和lb合并成一个线性表lc,lc也非递减有序。\n");104     printf("1.创建单链表La\n");105     LinkedList La = LinkedListCreat();106     printf("2.创建单链表Lb\n");107     LinkedList Lb = LinkedListCreat();108     printf("3.顺序合并单链表\n");109     LinkedList Lc = Union(La,Lb);110     printf("合并成功!\n");111     printf("4.输出合并后的链表\n");112     print(Lc);113     return 0;114 }
 1 /* 程序4  2 已知一个单链表,利用原表把单链表逆置。 3 设计要求:在程序中构造三个子程序分别为 4 LinkedList  LinkedListCreat( )                     //建立链表 5 void List_reverse(LinkedList L)                   //逆置链表 6 void print(LinkedList L);                         //输出链表中的结点 7 */ 8  9 #include <stdio.h>10 #include <malloc.h>11 /* 单链表的结点类型 */12 typedef struct LNode{13     int data;14     LNode* next;15 }LNode,*LinkedList;16 17 LinkedList  LinkedListCreat( )                     //按顺序建立链表18 {19     LinkedList head = (LNode*)malloc(sizeof(LNode));20     head->next = NULL;21     printf("请输入链表大小:(最多1000个)\n");22     int n,i,a[1001];23     scanf("%d",&n);24     printf("请输入链表的所有元素:\n");25     for(i=1;i<=n;i++)    //输入元素26         scanf("%d",&a[i]);27     //尾插法创建链表28     LinkedList p = head;29     for(i=1;i<=n;i++){30         LinkedList t =  (LNode*)malloc(sizeof(LNode));31         t->data =http://www.mamicode.com/ a[i];32         t->next = NULL;33         p->next = t;34         p = t;35     }36     return head;37 }38 39 void List_reverse(LinkedList L)                   //逆置链表40 {41     LinkedList p = L->next;42     int data[1001],i;43     for(i=1;p;i++){44         data[i] = p->data;45         p = p->next;46     }47     p = L->next;48     while(p){49         p->data = http://www.mamicode.com/data[--i];50         p = p->next;51     }52 }53 54 void print(LinkedList L)                       //输出链表中的结点55 {56     LinkedList p=L->next;57     while(p){58         printf("%d ",p->data);59         p = p->next;60     }61     printf("\n");62 }63 64 int main()65 {66     printf("已知一个单链表,利用原表把单链表逆置。\n");67     printf("1.创建单链表L\n");68     LinkedList L = LinkedListCreat();69     printf("2.链表逆置\n");70     List_reverse(L);71     printf("逆置成功!\n");72     printf("3.输出合并后的链表\n");73     print(L);74     return 0;75 }
 1 /* 程序5 2 在计算机上先输入一串正整数的序列。请编写一个程序,首先用链表存储该序列。 3 然后执行删除操作,即先从链表中找出最小的结点,删除它。 4 然后再在剩余的链表中,找出最小的结点,再删除之。直至表空为止。 5 设计要求:在程序中构造四个子程序分别为 6 LinkedList  LinkedListCreat( )                 //建立链表 7 int min(LinkedList head);                      //求链表中的最小结点 8 LinkedList del(LinkedList head, int num);   //删除结点 9 void print(LinkedList L);                      //输出链表中的结点10 */11 12 #include <stdio.h>13 #include <malloc.h>14 /* 单链表的结点类型 */15 typedef struct LNode{16     int data;17     LNode* next;18 }LNode,*LinkedList;19 20 LinkedList  LinkedListCreat( )                     //按顺序建立链表21 {22     LinkedList head = (LNode*)malloc(sizeof(LNode));23     head->next = NULL;24     printf("请输入链表大小:(最多1000个)\n");25     int n,i,a[1001];26     scanf("%d",&n);27     printf("请输入链表的所有元素:\n");28     for(i=1;i<=n;i++)    //输入元素29         scanf("%d",&a[i]);30     //尾插法创建链表31     LinkedList p = head;32     for(i=1;i<=n;i++){33         LinkedList t =  (LNode*)malloc(sizeof(LNode));34         t->data =http://www.mamicode.com/ a[i];35         t->next = NULL;36         p->next = t;37         p = t;38     }39     return head;40 }41 42 43 int min(LinkedList head)     //求链表中的最小结点,返回其逻辑序号44 {45     head = head->next;46     int min=1,val=head->data,num=1;    47     while(head){48         if(head->data < val)    //如果 当前节点元素值 < 之前存储的最小值49             min = num,val = head->data;50         head = head->next;51         num++;52     }53     return min;54 }55 56 LinkedList del(LinkedList head, int num)  //删除结点57 {58     int count = 0;59     LinkedList p = head;60     while(count+1!=num){    //找到要删除节点的前一个节点61         p = p->next;62         count++;63     }64     LinkedList t = (LNode*)malloc(sizeof(LNode));65     t = p->next;    //存储要删除的节点66     p->next = t->next;67     free(t);    //释放该空间68     return head;69 }70 71 72 void print(LinkedList L)                       //输出链表中的结点73 {74     LinkedList p=L->next;75     while(p){76         printf("%d ",p->data);77         p = p->next;78     }79     printf("\n");80 }81 82 int main()83 {84     printf("创建一个单链表,依次删除其中值最小的节点\n");85     printf("1.创建单链表L\n");86     LinkedList L = LinkedListCreat();87     printf("2.依次删除链表中值最小的节点\n");88     getchar();89     printf("当前链表所有元素:\n");90     print(L);91     while(L->next){92         printf("请按回车执行删除操作");93         getchar();94         L = del(L,min(L));    //删除当前值最小的元素95         print(L);96     }97     printf("链表已空!\n");98     return 0;99 }

 

 1 /* 程序6 2 利用单循环链表作为存储结构,实现实验二中的约瑟夫环问题。 3 设计要求:在程序中构造三个子程序分别为 4 CiLinkList  CiLinkListCreat( )              //建立不带头结点的单循环链表 5 void del(CiLinkList last, int N, int K)     //依次输出符合要求的结点 6 void print(CiLinkList L);                   //输出链表中的结点 7 */ 8 #include <stdio.h> 9 #include <malloc.h>10 /* 循环链表的结点类型 */11 typedef struct LNode{12     int data;13     LNode* next;14 }LNode,*CiLinkList;15 16 CiLinkList  CiLinkListCreat( )              //建立不带头结点的单循环链表17 {18     CiLinkList p0,p;19     printf("请输入链表大小:(最多1000个)\n");20     int n,i,e;21     scanf("%d",&n);22     printf("请输入循环链表的所有元素:\n");23     for(i=1;i<=n;i++){    //输入元素24         scanf("%d",&e);25         CiLinkList t = (LNode*)malloc(sizeof(LNode));    //创建节点,与之前的相连26         t->data =http://www.mamicode.com/ e;27         t->next = NULL;28         if(i==1)    //第一个节点29             p0 = t,p = t;30         else{31             p->next = t;32             p = p->next;33         }34     }35     p->next = p0;    //首尾相连36     return p0;37 }38 void del(CiLinkList last, int N, int K)     //依次输出符合要求的结点39 {40     int num = 0;41     while(last!=last->next){    //直到循环链表为空42         while(num+1!=K-1){    //找到要删除节点的上一个节点43             last = last->next;44             num++;45         }46         //删除节点47         CiLinkList t = last->next;48         last->next = t->next;49         printf("%d ",t->data);50         free(t);51         last = last->next;    //跳到被删除节点的下一个节点,重新开始循环52         num = 0;53     }54     printf("%d ",last->data);55     printf("\n");56 }57 void print(CiLinkList L)                  //输出链表中的结点58 {59     CiLinkList p = L->next;60     printf("%d ",L->data);    //输出第一个元素61     while(p!=L){62         printf("%d ",p->data);    //输出剩下的元素63         p = p->next;64     }65     printf("\n");66 }67 68 int main()69 {70     CiLinkList L = CiLinkListCreat();    //创建循环链表71     printf("符合要求的顺序应为:\n");72     del(L, 10, 3) ;    //依次输出符合要求的结点73     return 0;74 }
  1 /* 程序7  2 在双向链表上实现线性表的下列运算:  3 a)        建立 DLinkedList  creat()  4 b)        插入void  DlistInsert(DLinkedList L,int x,int i)  5 c)        删除void  DlistDelete(DLinkedList L,int i)  6 */  7 #include <stdio.h>  8 #include <malloc.h>  9 #include <stdlib.h> 10 typedef struct LNode{ 11     int data; 12     LNode* pre; 13     LNode* next; 14 } LNode,*DLinkedList; 15 DLinkedList  creat() 16 { 17     DLinkedList head = (LNode*)malloc(sizeof(LNode)),p = head; 18     head->next = NULL; 19     head->pre = NULL; 20     printf("请输入链表大小:(最多1000个)\n"); 21     int n,i,e; 22     scanf("%d",&n); 23     if(n<=0 || n>1000){ 24         printf("请输入正确的链表大小!\n"); 25         head = NULL; 26         return head; 27     } 28     printf("请输入循环链表的所有元素:\n"); 29     for(i=1;i<=n;i++){    //输入元素 30         scanf("%d",&e); 31         DLinkedList t = (LNode*)malloc(sizeof(LNode));    //创建节点 32         t->data =http://www.mamicode.com/ e; 33         t->next = NULL; 34         t->pre = p; 35         p->next = t; 36         p = p->next; 37     } 38     return head; 39 } 40 void  DlistInsert(DLinkedList L,int x,int i) 41 { 42     int num = 0; 43     while(num<i && L){ 44         L = L->next; 45         num++; 46     } 47     if(!L){ 48         printf("插入失败,您要插入的位置已超过链表长度!\n"); 49         return ; 50     } 51     DLinkedList pre = L->pre; 52     DLinkedList t = (LNode*)malloc(sizeof(LNode)); 53     t->data =http://www.mamicode.com/ x; 54     t->next = L; 55     t->pre = pre; 56     L->pre = t; 57     pre->next = t; 58 } 59 void  DlistDelete(DLinkedList L,int i) 60 { 61     int num = 0; 62     while(num<i && L){    //找到要删除的位置 63         L = L->next; 64         num++; 65     } 66     if(!L){ 67         printf("删除失败,您要删除的位置已超过链表长度!\n"); 68         return ; 69     } 70     DLinkedList pre = L->pre; 71     pre->next = L->next; 72     if(L->next!=NULL) 73         L->next->pre = pre; 74     free(L); 75 } 76  77 void print(DLinkedList L)                  //输出链表中的结点 78 { 79     L = L->next; 80     while(L){ 81         printf("%d ",L->data);    //输出剩下的元素 82         L = L->next; 83     } 84     printf("\n"); 85 } 86 int menu() 87 { 88     int in; 89     printf("[1] 创建双链表\n"); 90     printf("[2] 插入元素\n"); 91     printf("[3] 删除元素\n"); 92     printf("[4] 输出链表\n"); 93     printf("[0] 按任意键退出\n"); 94     scanf("%d",&in); 95     return in; 96 } 97 DLinkedList work(DLinkedList head ,int in) 98 { 99     switch(in){100         case 1:101             head = creat();102             break;103         case 2:104             if(head==NULL){105                 printf("请先创建双链表!\n");106                 break;107             }108             int i,x;109             printf("你要在第几个位置插入元素?\n");110             scanf("%d",&i);111             printf("你要插入的元素值是?\n");112             scanf("%d",&x);113             DlistInsert(head,x,i);114             printf("当前链表:\n");115             print(head);116             break;117         case 3:118             if(head==NULL){119                 printf("请先创建双链表!\n");120                 break;121             }122             int n;123             printf("你要删除第几个节点?\n");124             scanf("%d",&n);125             DlistDelete(head,n);126             printf("当前链表:\n");127             print(head);128             break;129         case 4:130             if(head==NULL){131                 printf("请先创建双链表!\n");132                 break;133             }134             printf("当前链表:\n");135             print(head);136             break;137         default:138             exit(1);139     }140     system("pause");141     system("cls");142     return head;143 }144 int main()145 {146     DLinkedList head = NULL;147     while(1){148         int in;149         in = menu();150         head = work(head,in);151     }152     return 0;153 }
  1 /* 程序8  2 设有一个双链表,每个结点中除有prior,next及data〔可设为正整数〕三个域之外,还有一个专门记录访问该结点次数的数据域freq,其值在初始化时为零。  3 每当在链表中进行一次Search〔l,key〕时,则数据域data之值等于key的结点,其freq域之值将加一。  4 并使该双链表中结点按freq之值的递减顺序排列,freq值越大的结点越靠近表头。  5 请编写符合上述要求的Search〔l,key〕程序。  6 设计要求:在程序中构造三个子程序分别为  7 DLinkedList Creat()                          //建立链表  8 void Search(DLinkedList head,int key)    //查找链表中符合要求的结点  9 void print(DLinkedList head);              //输出链表中的结点 10 */ 11  12 #include <stdio.h> 13 #include <malloc.h> 14 #include <stdlib.h> 15 typedef struct LNode{ 16     int data; 17     int freq;    //访问次数 18     LNode* prior; 19     LNode* next; 20 } LNode,*DLinkedList; 21  22 DLinkedList  creat() 23 { 24     DLinkedList head = (LNode*)malloc(sizeof(LNode)),p = head; 25     head->data = http://www.mamicode.com/0; 26     head->next = NULL; 27     head->prior = NULL; 28     head->freq = 0; 29     printf("请输入链表大小:(最多1000个)\n"); 30     int n,i,e; 31     scanf("%d",&n); 32     if(n<=0 || n>1000){ 33         printf("请输入正确的链表大小!\n"); 34         head = NULL; 35         return head; 36     } 37     printf("请输入循环链表的所有元素:\n"); 38     for(i=1;i<=n;i++){    //输入元素 39         scanf("%d",&e); 40         DLinkedList t = (LNode*)malloc(sizeof(LNode));    //创建节点 41         t->data =http://www.mamicode.com/ e; 42         t->next = NULL; 43         t->prior = p; 44         t->freq = 0; 45         p->next = t; 46         p = p->next; 47     } 48     return head; 49 } 50 void Search(DLinkedList head,int key)    //查找链表中符合要求的结点 51 { 52     DLinkedList p = head->next; 53     head = head->next; 54     while(head){    //找到符合要求的节点 55         if(head->data =http://www.mamicode.com/= key){ 56             head->freq++; 57             break; 58         } 59         head = head->next; 60     } 61     while(p){ 62         if(head->freq >= p->freq){ 63             int t; 64             t = head->data;head->data = p->data;p->data =http://www.mamicode.com/ t; 65             t = head->freq;head->freq = p->freq;p->freq = t; 66             break; 67         } 68         p = p->next; 69     } 70 } 71  72 void print(DLinkedList L)                  //输出链表中的结点 73 { 74     DLinkedList p = L->next; 75     L = L->next; 76     while(L){ 77         printf("%d ",L->data);    //输出剩下的元素 78         L = L->next; 79     } 80     printf("\n"); 81     while(p){ 82         printf("%d ",p->freq);    //输出剩下的元素 83         p = p->next; 84     } 85     printf("\n"); 86 } 87 int menu() 88 { 89     int in; 90     printf("[1] 创建双链表\n"); 91     printf("[2] 查找链表中符合要求的节点\n"); 92     printf("[3] 输出链表\n"); 93     printf("[0] 按任意键退出\n"); 94     scanf("%d",&in); 95     return in; 96 } 97 DLinkedList work(DLinkedList head ,int in) 98 { 99     switch(in){100         case 1:101             head = creat();102             break;103         case 2:104             if(head==NULL){105                 printf("请先创建双链表!\n");106                 break;107             }108             int key;109             printf("请问你要查找的关键值(key)是?\n");110             scanf("%d",&key);111             Search(head,key);112             printf("查找结果:\n");113             print(head);114             break;115         case 3:116             if(head==NULL){117                 printf("请先创建双链表!\n");118                 break;119             }120             printf("当前链表:\n");121             print(head);122             break;123         default:124             exit(1);125     }126     system("pause");127     system("cls");128     return head;129 }130 int main()131 {132     DLinkedList head = NULL;133     while(1){134         int in;135         in = menu();136         head = work(head,in);137     }138     return 0;139 }

 

链表 其他操作