c - 插入节点，但输入的第一个节点从列表中删除

Question

嗨，我正在尝试创建一个存储整数或字符串元素的通用列表迭代器.当我将节点添加到列表中并将其打印为列表时，输入的第一个节点位于列表的最后一个，输入的最后一个节点位于列表的开头(就像在列表前面一样)(代码在下面的测试用例 2 中进行了测试)。但是，我面临的问题是它只是"忘记"输入的第一个节点。我什至尝试从列表的第一个元素移动并逐个打印，但似乎输入的第一个节点不存在

这是添加功能：

int  add(IteratorG it, void *vp){
Node *temp;
if ((temp = malloc(sizeof(Node))) == NULL) { 
return 0; 
}
temp->value = it->newElm(vp);

if(it->curr!=NULL)
{    
temp->next=it->curr;
it->curr->prev=temp;
it->curr=temp;
}
if(it->curr==NULL){
it->curr=temp;
it->curr->next=NULL;
}  
return 1;
}

我使用的是 Linux 环境，错误从结果中可以看出。这是整个程序的代码：

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "iteratorG.h"
typedef struct Node {
void *value;  // value of thee list item
struct Node *prev;
// pointer previous node in list
struct Node *next;
// pointer to next node in list
// implemented struct here .. 
} Node;
typedef struct IteratorGRep {
int  numofit;      // count of items in list
Node *head;         // first node in list
Node *curr;       // current node in list
Node *tail;       // last node in list
ElmCompareFp  cmpElm;
ElmNewFp  newElm;
ElmFreeFp freeElm;
// implemented struct here .. 
} IteratorGRep;

/*

//Your  functions below .... 
*/

IteratorG newIterator(ElmCompareFp cmpFp, ElmNewFp newFp, ElmFreeFp freeFp){
IteratorG newit;

if ((newit = malloc(sizeof (struct IteratorGRep)))==NULL)
{
printf("Error...! n");
}
//assert (newit != NULL);
newit->numofit = 0;
newit->head = NULL;
newit->tail = NULL;
newit->curr = NULL;
newit->cmpElm=cmpFp;
newit->newElm=newFp;
newit->freeElm=freeFp;
return newit;
// implemented function here and changed return value 
}

int  add(IteratorG it, void *vp){
Node *temp;
if ((temp = malloc(sizeof(Node))) == NULL) { 
return 0; 
}
temp->value = it->newElm(vp);
temp->next=NULL;
if(it->curr==NULL)
{
//temp->next=it->curr;
it->curr=temp;
it->tail=it->head=it->curr;
}  
temp->next=it->curr;
it->curr->prev=temp;
it->curr=temp;
it->head=it->curr;
//it->curr->prev=temp;
/*temp->next = it->curr;
it->curr = temp;
*/
// add node to list from front 
return 1;
}
int  hasNext(IteratorG it){
if(it->curr->next==NULL)
{
return 0;
}

// check if theres next element/node
return 1;
}
int  hasPrevious(IteratorG it){
if(it->curr->prev!=NULL)
{
return 1;
}
// check if theres previous element/node 
return 0;
}
void *next(IteratorG it){
Node *tempo;
if(it->curr->next==NULL)
{
return NULL;
}
tempo=it->curr;
it->curr=it->curr->next;
// implemented function here  
return tempo->value;
}
void *previous(IteratorG it){
Node *tempor;
tempor=it->curr;
if(tempor->prev==NULL)
{
return NULL;
}
tempor=it->curr->prev;
it->curr=it->curr->prev;
//tempor=it->curr;
// move to next node in list  
return tempor->value;
}
int  del(IteratorG it){
if(it->curr->prev!=NULL)
{
Node *temp_curr=it->curr;
Node *temp_prev=it->curr->prev->prev;
temp_curr->prev=temp_prev;
temp_prev->next=temp_curr;
return 1;
}// delete previous node  from list 
else
return 0;
}
int  set(IteratorG it, void *vp){
if(it->curr->prev!=NULL)
{
it->curr->prev->value=vp;

/*  
Node *wep;
if ((wep = malloc(sizeof(Node))) == NULL) { 
return 0; 
}  

wep->value=it->newElm(vp);  

store_next=it->curr;
store_prev=it->curr->prev->prev;
store_next->prev=wep;
wep->next=store_next;
store_prev->next=wep;
wep->prev=store_prev;
*/

return 1;
}
// change previous node value with new 
return 0;
}
IteratorG advance(IteratorG it, int n){

//To be implemented
//move forward by n times
return NULL;
}
void reverse(IteratorG it){
Node *curr = it->head;
Node *temp = NULL;
while(curr != NULL) {
temp = curr->next;
curr->next = curr->prev;
curr->prev = temp;
curr = temp;
}
temp = it->head;
it->head = it->tail;
it->tail = temp;// reverse elements of whole list
}
IteratorG find(IteratorG it, int (*fp) (void *vp) ){
// To be implemented 
// Find elements of vp in list after current position and put in new list.return the list.
return NULL;
}
int distanceFromStart(IteratorG it){
Node *c=it->curr;
int count=0;

while(c->prev!=NULL)
{
c=c->prev;
count++;
}
return count;
// count number of elements from start of list to current position 
}
int distanceToEnd(IteratorG it){
Node *cu=it->curr;
int count=0;
while(cu->next!=NULL)
{
cu=cu->next;
count++;
}
return count;
// count number of elements from end of list to current position
}
void reset(IteratorG it){

while(it->curr->prev!=NULL)
{
it->curr=it->curr->prev;
}
return;
// move current position to start of list
}
void freeIt(IteratorG it){
assert(it != NULL);
Node *curr, *prev;
curr = it->head;
while (curr != NULL) {
prev = curr;
curr = curr->next;
free(prev->value);
free(prev);
}
free(it); // free items  
}

这是代码的头文件：

#ifndef LISTITERATORG_H
#define LISTITERATORG_H
#include <stdio.h>
typedef struct IteratorGRep *IteratorG;
typedef int   (*ElmCompareFp)(void const *e1, void const *e2);
typedef void *(*ElmNewFp)(void const *e1);
typedef void  (*ElmFreeFp)(void *e1);

IteratorG newIterator(ElmCompareFp cmpFp, ElmNewFp newFp, ElmFreeFp freeFp);
int  add(IteratorG it, void *vp);
int  hasNext(IteratorG it);
int  hasPrevious(IteratorG it);
void *next(IteratorG it);
void *previous(IteratorG it);
int  del(IteratorG it);
int  set(IteratorG it, void *vp);
IteratorG advance(IteratorG it, int n);
void reverse(IteratorG it);
IteratorG find(IteratorG it, int (*fp) (void *vp) );
int distanceFromStart(IteratorG it);
int distanceToEnd(IteratorG it);
void reset(IteratorG it);
void freeIt(IteratorG it);
#endif

其中一个函数尚未实现，并在代码本身中指示。但我想这可能不是问题的根源。我认为添加功能在这里没有得到正确利用。

编辑： 这是测试用例代码。仅在上面的程序中，测试用例代码中没有错误：

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "iteratorG.h"
#include "positiveIntType.h"
#include "stringType.h" 
#define MAXARRAY 5
/* Helper Functions Below */
/* Returns 1 if marks >= 50, 0 otherwise  */
int passMarks(void *marks){
return (*((int *) marks) >= 50); 
/* Easy to understand below .. 
int *ip = (int *) marks;
if(*ip >= 50) { return 1; }
else { return 0; } 
*/
}
/* Returns 1 if str starts with "jo" */
int prefixJo(void *str){
return (strncmp("jo", (char *) str, 2) == 0) ; 
}
/* A function to print a string from a void pointer */
void prnStr(void *vp){
assert(vp != NULL);
printf(" %s", (char *) vp );      
}
/* A function to print an integer from a void pointer */
void prnInt(void *vp){
assert(vp != NULL);
printf(" %d", *((int *) vp) );    
}
/* Prints previous element using the given function 'fp'
examples: prnPrev(it1, prnInt); prnPrev(it2, prnStr);
*/
void prnPrev(IteratorG it, void (*fp) (void *p) ){
void *prevP = previous(it);
assert(prevP != NULL);
printf("> Previous value is: "); 
fp(prevP);
printf("n"); 
}
/* Prints next element using the given function 'fp'
examples:   prnNext(it1, prnInt); prnNext(it2, prnStr);
*/
void prnNext(IteratorG it, void (*fp) (void *p) ){
void *nextP = next(it);
assert(nextP != NULL);
printf("> Next value is: "); 
fp(nextP);
printf("n"); 
}
/* Prints elements of 'it' from current to last position 
using the given function 'fp'. The current position 
of 'it' will change to the end of the list.
examples: prnIt(it1, prnInt); prnIt(it2, prnStr);
*/
void prnIt(IteratorG it, void (*fp) (void *p) ){
int count = 0;
while(hasNext(it)){
void *nextP = next(it); 
count++;
if(count > 1) { printf(", "); }
fp(nextP);      
}
printf("n"); 
}

/* Few Tests Below  */
void test1(){
printf("n--====  Test-01       ====------n");
IteratorG it1 = newIterator(positiveIntCompare, positiveIntNew,  positiveIntFree);
int a[MAXARRAY] = { 25, 78, 6, 82 , 11};
for(int i=0; i<MAXARRAY; i++){
int result = add(it1 , &a[i]); 
printf("> Inserting %d: %s n", a[i], (result==1 ? "Success" : "Failed") );
}
freeIt(it1);
printf("--====  End of Test-01 ====------n");
}
void test2(){
printf("n--====  Test-02       ====------n");
IteratorG it1 = newIterator(positiveIntCompare, positiveIntNew, positiveIntFree);
int a[MAXARRAY] = { 72, 14, 62, 8, 93};
for(int i=0; i<MAXARRAY; i++){
int result = add(it1 , &a[i]); 
printf("> Inserting %d: %s n", a[i], (result==1 ? "Success" : "Failed") );
}
prnNext(it1, prnInt);
prnNext(it1, prnInt);
prnPrev(it1, prnInt);
int newVal1 = 55;
int result1 = set(it1, &newVal1);
printf("> Set value: %d ; return val: %d n", newVal1,  result1 );  
prnPrev(it1, prnInt);
freeIt(it1);
printf("--====  End of Test-02 ====------n");
}

int main(int argc, char *argv[])
{

test1();
test2();
return EXIT_SUCCESS;
}

Answer 1

名为it->head的节点应使用第一个值初始化，因为假定it->curr是第一个节点。此外，为了防止与其他节点的连接丢失，应使用存储的节点初始化新节点。所以 add 函数应该如下所示：

int  add(IteratorG it, void *vp){
Node *temp;
if ((temp = malloc(sizeof(Node))) == NULL) { 
return 0; 
}
Node *tempe;
if ((temp = malloc(sizeof(Node))) == NULL) { 
return 0; 
}
temp->value = it->newElm(vp);
//temp->next=NULL;
if(it->curr==NULL)
{
//temp->next=it->curr;
it->head=it->tail=temp;
it->curr=temp;
}
else
{
tempe=it->curr;
tempe->prev=temp;
temp->next=tempe;
it->curr=tempe;
it->curr=temp;
it->head=temp;

} 
//it->tail=it->head=it->curr;
return 1;
}