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 程序2 13 利用原空间，将两个单链表合并成一个单链表。 14 设计要求：在程序中构造三个子程序分别为 15 LinkedList LinkedListCreat( ) /*建立链表*/ 16 LinkedList ListConcat(LinkedList La,LinkedList Lb) /*合并链表*/ 17 void print(LinkedList L); /*输出链表中的结点*/ 18 程序3 19 已知两个非递减有序的单链表la和lb，将la和lb合并成一个线性表lc，lc也非递减有序。 20 设计要求：在程序中构造三个子程序分别为 21 LinkedList LinkedListCreat( ) /*建立链表*/ 22 LinkedList union(LinkedList La,Lb) /*合并链表*/ 23 void print(LinkedList Lc); /*输出链表中的结点*/ 24 程序4 25 已知一个单链表，利用原表把单链表逆置。 26 设计要求：在程序中构造三个子程序分别为 27 LinkedList LinkedListCreat( ) /*建立链表*/ 28 void List_reverse(LinkedList L) /*逆置链表*/ 29 void print(LinkedList L); /*输出链表中的结点*/ 30 程序5 31 在计算机上先输入一串正整数的序列。请编写一个程序，首先用链表存储该序列。然后执行删除操作，即先从链表中找出最小的结点，删除它。然后再在剩余的链表中，找出最小的结点，再删除之。直至表空为止。 32 设计要求：在程序中构造四个子程序分别为 33 LinkedList LinkedListCreat( ) /*建立链表*/ 34 int min(LinkedList head); /*求链表中的最小结点*/ 35 LinkedList del(LinkedList head, int num); /*删除结点*/ 36 void print(LinkedList L); /*输出链表中的结点*/ 37 程序6 38 利用单循环链表作为存储结构，实现实验二中的约瑟夫环问题。 39 设计要求：在程序中构造三个子程序分别为 40 CiLinkList CiLinkListCreat( ) /*建立不带头结点的单循环链表*/ 41 void del(CiLinkList last, int N, int K) /*依次输出符合要求的结点*/ 42 void print(CiLinkList L); /*输出链表中的结点*/ 43 程序7 44 在双向链表上实现线性表的下列运算： 45 a) 建立 DLinkedList creat() 46 b) 插入void DlistInsert(DLinkedList L,int x,int i) 47 c) 删除void DlistDelete(DLinkedList L,int i) 48 程序8 49 设有一个双链表，每个结点中除有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个） "); 21 int n,i,j,a[1001]; 22 scanf("%d",&n); 23 printf("请输入链表的所有元素： "); 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 = 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 = 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 = 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(" "); 74 } 75 int main() 76 { 77 int x; 78 printf("设单链表L是一个非递减有序表，将x插入其中后仍保持L的有序性。 "); 79 LinkedList head = LinkedListCreat(); 80 printf("请输入要插入的元素值： "); 81 while(scanf("%d",&x)!=EOF){ 82 InsertList(head,x); 83 printf("插入之后的单链表： "); 84 print(head); 85 printf("--------------------- "); 86 printf("请输入要插入的元素值： "); 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个） "); 21 int n,i,a[1001]; 22 scanf("%d",&n); 23 printf("请输入链表的所有元素： "); 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 = 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(" "); 56 } 57 58 int main() 59 { 60 printf("利用原空间，将两个单链表合并成一个单链表。 "); 61 printf("1.创建单链表La "); 62 LinkedList La = LinkedListCreat(); 63 printf("2.创建单链表Lb "); 64 LinkedList Lb = LinkedListCreat(); 65 printf("3.合并单链表 "); 66 LinkedList Lc = ListConcat(La,Lb); 67 printf("合并成功! "); 68 printf("4.输出合并后的链表 "); 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个） "); 21 int n,i,j,a[1001]; 22 scanf("%d",&n); 23 printf("请输入链表的所有元素： "); 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 = 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 = 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 = 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 = 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 = 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(" "); 99 } 100 101 int main() 102 { 103 printf("已知两个非递减有序的单链表la和lb，将la和lb合并成一个线性表lc，lc也非递减有序。 "); 104 printf("1.创建单链表La "); 105 LinkedList La = LinkedListCreat(); 106 printf("2.创建单链表Lb "); 107 LinkedList Lb = LinkedListCreat(); 108 printf("3.顺序合并单链表 "); 109 LinkedList Lc = Union(La,Lb); 110 printf("合并成功! "); 111 printf("4.输出合并后的链表 "); 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个） "); 22 int n,i,a[1001]; 23 scanf("%d",&n); 24 printf("请输入链表的所有元素： "); 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 = 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 = 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(" "); 62 } 63 64 int main() 65 { 66 printf("已知一个单链表，利用原表把单链表逆置。 "); 67 printf("1.创建单链表L "); 68 LinkedList L = LinkedListCreat(); 69 printf("2.链表逆置 "); 70 List_reverse(L); 71 printf("逆置成功! "); 72 printf("3.输出合并后的链表 "); 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个） "); 25 int n,i,a[1001]; 26 scanf("%d",&n); 27 printf("请输入链表的所有元素： "); 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 = 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(" "); 80 } 81 82 int main() 83 { 84 printf("创建一个单链表，依次删除其中值最小的节点 "); 85 printf("1.创建单链表L "); 86 LinkedList L = LinkedListCreat(); 87 printf("2.依次删除链表中值最小的节点 "); 88 getchar(); 89 printf("当前链表所有元素： "); 90 print(L); 91 while(L->next){ 92 printf("请按回车执行删除操作"); 93 getchar(); 94 L = del(L,min(L)); //删除当前值最小的元素 95 print(L); 96 } 97 printf("链表已空! "); 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个） "); 20 int n,i,e; 21 scanf("%d",&n); 22 printf("请输入循环链表的所有元素： "); 23 for(i=1;i<=n;i++){ //输入元素 24 scanf("%d",&e); 25 CiLinkList t = (LNode*)malloc(sizeof(LNode)); //创建节点，与之前的相连 26 t->data = 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(" "); 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(" "); 66 } 67 68 int main() 69 { 70 CiLinkList L = CiLinkListCreat(); //创建循环链表 71 printf("符合要求的顺序应为： "); 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个） "); 21 int n,i,e; 22 scanf("%d",&n); 23 if(n<=0 || n>1000){ 24 printf("请输入正确的链表大小！ "); 25 head = NULL; 26 return head; 27 } 28 printf("请输入循环链表的所有元素： "); 29 for(i=1;i<=n;i++){ //输入元素 30 scanf("%d",&e); 31 DLinkedList t = (LNode*)malloc(sizeof(LNode)); //创建节点 32 t->data = 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("插入失败，您要插入的位置已超过链表长度！ "); 49 return ; 50 } 51 DLinkedList pre = L->pre; 52 DLinkedList t = (LNode*)malloc(sizeof(LNode)); 53 t->data = 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("删除失败，您要删除的位置已超过链表长度！ "); 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(" "); 85 } 86 int menu() 87 { 88 int in; 89 printf("[1] 创建双链表 "); 90 printf("[2] 插入元素 "); 91 printf("[3] 删除元素 "); 92 printf("[4] 输出链表 "); 93 printf("[0] 按任意键退出 "); 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("请先创建双链表！ "); 106 break; 107 } 108 int i,x; 109 printf("你要在第几个位置插入元素？ "); 110 scanf("%d",&i); 111 printf("你要插入的元素值是？ "); 112 scanf("%d",&x); 113 DlistInsert(head,x,i); 114 printf("当前链表： "); 115 print(head); 116 break; 117 case 3: 118 if(head==NULL){ 119 printf("请先创建双链表！ "); 120 break; 121 } 122 int n; 123 printf("你要删除第几个节点？ "); 124 scanf("%d",&n); 125 DlistDelete(head,n); 126 printf("当前链表： "); 127 print(head); 128 break; 129 case 4: 130 if(head==NULL){ 131 printf("请先创建双链表！ "); 132 break; 133 } 134 printf("当前链表： "); 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 = 0; 26 head->next = NULL; 27 head->prior = NULL; 28 head->freq = 0; 29 printf("请输入链表大小：（最多1000个） "); 30 int n,i,e; 31 scanf("%d",&n); 32 if(n<=0 || n>1000){ 33 printf("请输入正确的链表大小！ "); 34 head = NULL; 35 return head; 36 } 37 printf("请输入循环链表的所有元素： "); 38 for(i=1;i<=n;i++){ //输入元素 39 scanf("%d",&e); 40 DLinkedList t = (LNode*)malloc(sizeof(LNode)); //创建节点 41 t->data = 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 == 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 = 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(" "); 81 while(p){ 82 printf("%d ",p->freq); //输出剩下的元素 83 p = p->next; 84 } 85 printf(" "); 86 } 87 int menu() 88 { 89 int in; 90 printf("[1] 创建双链表 "); 91 printf("[2] 查找链表中符合要求的节点 "); 92 printf("[3] 输出链表 "); 93 printf("[0] 按任意键退出 "); 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("请先创建双链表！ "); 106 break; 107 } 108 int key; 109 printf("请问你要查找的关键值（key）是？ "); 110 scanf("%d",&key); 111 Search(head,key); 112 printf("查找结果： "); 113 print(head); 114 break; 115 case 3: 116 if(head==NULL){ 117 printf("请先创建双链表！ "); 118 break; 119 } 120 printf("当前链表： "); 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 }