[已解决]C语言算法题（链队列）

Lycoriswu

延伸自东南大学96年考研题。10
悬赏C语言解决示例中要求的代码。10.13号截止。
欢迎鱼友们光临讨论

最佳答案

月排行榜 / 总排行榜

xieglt

2020-10-8 18:05:03

Lycoriswu 发表于 2020-10-9 23:21
利用带头节点和只设尾指针的循环链表可以实现吗?

看看我的代码是不是满足你的要求。用了尾指针和头节点，严格意义上说，还是两个指针。

跳转到最佳答案楼层

xieglt

Lycoriswu 发表于 2020-10-9 23:21
利用带头节点和只设尾指针的循环链表可以实现吗?

看看我的代码是不是满足你的要求。用了尾指针和头节点，严格意义上说，还是两个指针。

xieglt

队列要两个指针，一个队首指针，一个队尾指针，一个指针无法同时做到做到 addq和deleteq O(1)

xieglt

1. #include "stdafx.h"
   
2. #include<stdio.h>
   
3. #include<stdlib.h>
   
4. 
   
5. typedef struct tagLinkList
   
6. {
   
7.         int data;
   
8.         struct tagLinkList * pNext;
   
9. }LINKLIST,*LPLINKLIST;
   
10. 
    
11. void printDuque(LPLINKLIST head)
    
12. {
    
13.         LPLINKLIST ll = head->pNext;
    
14.        
    
15.         //循环输出队列所有元素
    
16.         while(ll != NULL)
    
17.         {
    
18.                 printf("%d\t",ll->data);
    
19.                 ll = ll->pNext;
    
20.         }
    
21.        
    
22.         printf("\n");
    
23. }
    
24. 
    
25. LPLINKLIST addq(LPLINKLIST tail, int data)
    
26. {
    
27.         //添加新节点到队列尾部
    
28.         LPLINKLIST ll = (LPLINKLIST)malloc(sizeof(LINKLIST));
    
29.         ll->data = data;
    
30.         ll->pNext = NULL;
    
31.         tail->pNext = ll;
    
32.         //返回新添加的节点返回作为尾节点
    
33.         return ll;
    
34. }
    
35. 
    
36. void deleteq(LPLINKLIST head, LPLINKLIST * tail,int * data)
    
37. {
    
38.         //队列头 == 队列尾时队列为空
    
39.         if(head != * tail)       
    
40.         {       
    
41.                 //head 之后的第一个节点为first in 节点
    
42.                 LPLINKLIST curr = head->pNext;
    
43.                 LPLINKLIST next = curr->pNext;
    
44.                
    
45.                 //返回节点数据
    
46.                 *data = curr->data;
    
47.                 //释放节点
    
48.                 free(curr);
    
49. 
    
50.                 head->pNext = next;
    
51.                
    
52.                 //队列为空时，设置队尾指针 = 队首指针
    
53.                 if(next == NULL)
    
54.                 {
    
55.                         *tail = head;
    
56.                 }
    
57. 
    
58.                 printDuque(head);
    
59.         }
    
60.         else
    
61.         {
    
62.                 printf("The duque is null...\n");
    
63.         }
    
64. }
    
65. 
    
66. void destoryLink(LPLINKLIST head)
    
67. {
    
68.         LPLINKLIST ll = head->pNext;
    
69.         while(ll != NULL)
    
70.         {
    
71.                 LPLINKLIST next = ll->pNext;
    
72.                 free(ll);
    
73.                 ll = next;
    
74.         }
    
75. }
    
76. 
    
77. int main(void)
    
78. {
    
79.         LINKLIST head;
    
80.         LPLINKLIST tail = &head;
    
81.         int data = 0;
    
82.         head.pNext = NULL;
    
83.        
    
84.         tail = addq(tail,1);
    
85.         tail = addq(tail,2);
    
86.         tail = addq(tail,3);
    
87.         tail = addq(tail,4);
    
88.         tail = addq(tail,5);
    
89.         printDuque(&head);
    
90.        
    
91.         deleteq(&head,&tail,&data);       
    
92.         deleteq(&head,&tail,&data);
    
93.         deleteq(&head,&tail,&data);
    
94.         deleteq(&head,&tail,&data);
    
95.         deleteq(&head,&tail,&data);
    
96.         deleteq(&head,&tail,&data);
    
97.        
    
98.         destoryLink(&head);
    
99.         return 0;
    
100. }

复制代码

Lycoriswu

xieglt 发表于 2020-10-9 17:09
队列要两个指针，一个队首指针，一个队尾指针，一个指针无法同时做到做到 addq和deleteq O(1)

利用带头节点和只设尾指针的循环链表可以实现吗?

Lycoriswu

xieglt 发表于 2020-10-10 08:34
看看我的代码是不是满足你的要求。用了尾指针和头节点，严格意义上说，还是两个指针。

给您设最佳答案吧。不过代码和题目想要的要求还有一些出入。每月能领一些鱼币但不多了。可以的话希望加一下q1281516242深入讨论一下。