这很乱,所以如果你没有时间不要打扰。我试图解释我的代码中的每个函数如何尽可能最好地工作。所以我的问题是功能Q_drop
,我无法工作,其他一切(代码的所有其他部分)工作正常。
因此Q_drop
函数需要执行以下操作:
实现从队列中删除给定特定成员(由Q_drop
标识)的函数ID
,并释放为其分配的内存。该队列成员可以位于队列中的任何位置,并且在移除之后,队列应该保持可操作,即,应该相应地更新所有指针。并且My_Queue-> last指针需要指向最后一个成员。
如果找到并删除了匹配ID
的物种,则该函数返回1;如果没有匹配,则返回0,并且没有删除任何内容。每个调用应该只删除一个队列成员:如果一个物种在队列中多次,则只删除第一个条目。
所以我的问题是如果匹配节点是最后一个节点,如何将指针移动到前一个节点?我得到的检查错误是“My_Queue->最后一个指针不指向最后一个成员”。
我的代码:
struct animal {
char id[7]; // animal ID: 6 characters + '\0'
char *species; // species of animal, allocated dynamically
struct animal *next; // next animal in linked list
};
/* For storing the first and last item in linked list
* If list is empty, both <first> and <last> are NULL
* If list has one element, <first> and <last> point to the same place
*/
struct my_queue {
struct animal *first;
struct animal *last;
};
const struct zoo {
const char *id;
const char *species;
} animals[] = {
{"123456", "Dog" },
{"234567", "Bear" },
{"777777", "Pink Fairy Armadillo" },
{"aaaaaaaaa", "Chlamyphorus truncatus" },
{"666666", "Mosquito" }
};
/* Drops the given animal with animal ID <id> from queue <q>.
* Only the first instance with matching ID is dropped.
*
* Returns: 1 if something was removed,
* 0 if nothing was removed, i.e., matching animal ID was not found.
*/
int Q_drop(My_Queue *q, const char *id)
{
struct animal *prev = NULL;
struct animal *curr = q->first;
while (curr != NULL) {
if (!strcmp(curr->id, id)) {
if (prev == NULL) {
q->first = curr->next;
}
if(curr->next == NULL){
//here I cant figure out what to write here tried q->last=prev
}
else {
prev->next = curr->next;
}
free(curr->species);
free(curr);
return 1;
}
else {
prev = curr;
curr = curr->next;
}
}
return 0;
}
/* Allocates and initializes a new queue.
*
* Returns: pointer to an empty queue
*/
My_Queue *Q_init(void)
{
My_Queue *q = calloc(1, sizeof(My_Queue));
return q;
}
/* Adds a new member with given animal ID <id> and species <species> to the
* end of queue <q>.
*
* Returns: 1 if addition was successful, 0 if addition failed. Addition
fails,
* for example if animal ID has more than 6 characters.
*/
int Q_enqueue(My_Queue *q, const char *id, const char *species)
{
int n = strlen(id);
if (n < 7){
struct animal *new = malloc(sizeof(struct animal));
strcpy(new->id, id);
new->species = malloc(strlen(species) + 1);
strcpy(new->species, species);
new->next = NULL;
if(q->first == NULL && q->last == NULL){
q->first = new;
q->last = new;
}
else{
q->last->next = new;
q->last = new;
}
return 1;
}
else{
return 0;
}
}
int main()
{
/* testing exercise. Feel free to modify this function */
My_Queue *q = Q_init();
for (unsigned int i = 0; i < sizeof(animals) / sizeof(struct zoo); i++)
{
if (Q_enqueue(q, animals[i].id, animals[i].species))
printf("i = %d, firstspecies: %s\n", i, Q_firstSpecies(q));
}
Q_drop(q, "777777");
好吧,在这一点上
if (!strcmp(curr->id, id)) {
if (prev == NULL) {
q->first = curr->next;
} else {
prev->next = curr->next;
}
你找到了你想要释放的节点,但是你做到了
curr = curr->next;
在你做之前
free(curr->species);
free(curr);
所以在我看来你没有释放正确的节点,而是在它之后释放节点。你的代码缩进有点偏,但我认为你可以删除那个curr = curr->next;
,因为你之后在else
部分中有一个对应于没有找到正确的节点。
int Q_drop(My_Queue *q, const char *id) {
struct animal *prev = NULL;
struct animal *curr = q->first;
while (curr != NULL) {
if (!strcmp(curr->id, id)) {
if (prev == NULL) {
q->first = curr->next;
} else {
prev->next = curr->next;
}
free(curr->species);
free(curr);
return 1;
}
else {
prev = curr;
curr = curr->next;
}
}
return 0;
}
在匹配是列表的最后一个成员的所有情况下,该函数不会处理。您应该检查匹配节点是否是最后一个节点(curr->next == NULL
)并将q->last
设置为相应于前一节点。还记得将新的最后一项的next
指针设置为NULL
并检查删除的成员是否是列表中唯一的一个,在这种情况下你不能引用prev
并且必须将first
和last
指针设置为NULL
。
这是一个小代码示例:
p = NULL;
c = li->first;
while(c != NULL) {
if(c->id != id) {
p = c;
c = c->next;
continue;
}
/* Only member */
if(p == NULL && c->next == NULL) {
li->first = NULL;
li->last = NULL;
free(c);
return;
}
/* First member */
if(p == NULL)
li->first = c->next;
else
p->next = c->next;
/* Last member */
if(c->next == NULL) {
li->last = p;
p->next = NULL;
}
free(c);
return;
}