[已解决]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

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>

typedef struct tagLinkList
{
        int data;
        struct tagLinkList * pNext;
}LINKLIST,*LPLINKLIST;

void printDuque(LPLINKLIST head)
{
        LPLINKLIST ll = head->pNext;
        
        //循环输出队列所有元素
        while(ll != NULL)
        {
                printf("%d\t",ll->data);
                ll = ll->pNext;
        }
        
        printf("\n");
}

LPLINKLIST addq(LPLINKLIST tail, int data)
{
        //添加新节点到队列尾部
        LPLINKLIST ll = (LPLINKLIST)malloc(sizeof(LINKLIST));
        ll->data = data;
        ll->pNext = NULL;
        tail->pNext = ll;
        //返回新添加的节点返回作为尾节点
        return ll;
}

void deleteq(LPLINKLIST head, LPLINKLIST * tail,int * data)
{
        //队列头 == 队列尾时队列为空
        if(head != * tail)        
        {        
                //head 之后的第一个节点为first in 节点
                LPLINKLIST curr = head->pNext;
                LPLINKLIST next = curr->pNext;
                
                //返回节点数据
                *data = curr->data;
                //释放节点
                free(curr);

                head->pNext = next;
                
                //队列为空时，设置队尾指针 = 队首指针
                if(next == NULL)
                {
                        *tail = head;
                }

                printDuque(head);
        }
        else
        {
                printf("The duque is null...\n");
        }
}

void destoryLink(LPLINKLIST head)
{
        LPLINKLIST ll = head->pNext;
        while(ll != NULL)
        {
                LPLINKLIST next = ll->pNext;
                free(ll);
                ll = next;
        }
}

int main(void)
{
        LINKLIST head;
        LPLINKLIST tail = &head;
        int data = 0;
        head.pNext = NULL;
        
        tail = addq(tail,1);
        tail = addq(tail,2);
        tail = addq(tail,3);
        tail = addq(tail,4);
        tail = addq(tail,5);
        printDuque(&head);
        
        deleteq(&head,&tail,&data);        
        deleteq(&head,&tail,&data);
        deleteq(&head,&tail,&data);
        deleteq(&head,&tail,&data);
        deleteq(&head,&tail,&data);
        deleteq(&head,&tail,&data);
        
        destoryLink(&head);
        return 0;
}

Lycoriswu

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

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

Lycoriswu

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

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