C语言中带有链表和计数器的队列

Question

我正在实现一个具有链表的队列，该链表将具有将在同一程序中使用简单命令发送和接收的数据，我想为队列中的每个数据添加一个计数器，值为新的，待处理或ack。那么我是将它存储在数组中还是有其他方法因为计数器的数量会很大?

#define TOTALPACKETS 100
#define WINDOW   5
#define ACK      2
#define PENDING  1
#define NEW      0 

typedef int Item ;
typedef struct node *link;  
struct node{                
    Item data;
    Item status;
    link next; 
};
int QUEUEempty(link head){
    return head==NULL;
}
void QUEUEput(link *head, link *tail, Item data, Item status){
    if (*head==NULL){
                    (*tail)=(link)malloc(sizeof(node)); 
                    (*tail)->data=data;
                    (*tail)->next=NULL;
                (*tail)->status=NEW;
                    *head=*tail;
                    return;}
    (*tail)->next=(link)malloc(sizeof(node));
    *tail=(*tail)->next;
    (*tail)->data=data;
    (*tail)->next=NULL;
    (*tail)->status=NEW;
    return;
}
Item QUEUEget(link *head){
    Item data=(*head)->data;
    Item status
    link t=*head;
    *head=(*head)->next;
    free(t);
    return data; 
}

Answer 1

我认为我很擅长读懂字里行间和猜测隐藏的意图，但我不能很好地理解你想要什么。我想把它做成注释，但是有太多的字不适合注释，而且格式也很有限。(这不是一个真正的答案——这就是为什么它是CW。)

你说的"计数器"有三个值(NEW, PENDING, ACK)之一。这听起来更像是一个状态或状态，而不是一个计数器。

让我们尝试一些设计;你可以说出哪里出了问题。这假定了一个非侵入式队列设计。

typedef struct Data Data;   /* This is the data that you're queueing - details TBS */
typedef struct QNode
{
    Data  *data;
    QNode *next;
    QNode *prev;
    ...possibly other data...status?
} QNode;
typedef struct Queue
{
    QNode *head;
    QNode *tail;
    ...possibly other data...counts?
} Queue;
extern int q_add(Queue *q, Data *d);    // Add datum d to queue per policy
extern int q_next(Queue *q, Data **dp); // Remove next datum from queue per policy

现在，基于这个大纲的系统至少有两个地方可以存储计数器或状态。一个地方将在struct Data，一个不透明的结构类型。另一个可能的地方是在struct QNode里面。如果这是你想要的，你也可以在struct Queue中使用汇总计数器来记录每个状态下有多少节点。

以这个为出发点，你想要什么?在这一点上，一切都是可变的，但没有具体的东西可以开始，我们无法提供更多的帮助。

Answer 2

在节点中已经有了状态"计数器"，但是(正如Jonathan Leffler建议的)让我们将其称为state或status。在选择性重复ARQ协议实现的ACK receive()中，存在访问节点(不仅是状态，而且在重传的情况下也是数据)的问题，该序列号与确认一起发送;我们必须遍历链表才能到达正确的节点，但在遍历过程中，我们也可以释放已确认的节点，所以这是无害的。

但是，您可以改进您的数据结构。我们不需要每个节点都有一个显式的状态变量，因为状态是严格有序的。从列表的头到尾，首先有0个ACK节点(如果不立即释放，则有更多ACK节点)，其次有0个或更多PENDING节点，最后有0个或更多NEW节点。因此，为了维护状态信息，一个指向第一个NEW(可能还有第一个PENDING)节点的索引或指针就足够了。