c - 双向链表示例

Question

我自定义的头文件如下。

#ifndef DLinkedList_h
#define DLinkedList_h

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

typedef int ElementType;
typedef struct tagNode{
ElementType data, key;
struct tagNode* prevNode;
struct tagNode* nextNode;
char myName [30];
char telNum [30];
} Node;



Node* CreateNode(ElementType newData);
void DestroyNode(Node* node);
void AppendNode(Node** head, Node* newData);
void InsertAfter(Node* current, Node* newNode);
void InsertNewHead(Node** head, Node* newHead);
void RemoveNode(Node** head, Node* remove);
Node* GetNodeAt(Node* head, int location);
int GetNodeCount(Node* head);

#endif

至此，DLinkedList.h文件结束

#include "DLinkedList.h"
#include <time.h>
#include "Chaining.h"


int numbersInCache [] = {23, 22, 33, 44, 55, 77, 99, 20, 24, 67, 89, 90, 24, 43, 98, 63, 43, 96, 45, 43};

Node* CreateNode(ElementType newData){
Node* newNode = (Node*)malloc(sizeof(Node));

newNode->data = newData;
newNode->prevNode = NULL;
newNode->nextNode = NULL;



return newNode;

} 

//Node destroyed
void DestroyNode(Node* node){
free(node);
}

//To add a node
void AppendNode(Node** head, Node* newNode){
if(*head == NULL)
    *head = newNode;
else {
    Node* tail = *head;
    while(tail->nextNode != NULL)
        tail = tail->nextNode;

    tail->nextNode = newNode;
    //The current tail node is pointed by the preNode of the new node.
    newNode->prevNode = tail;
    }
}

void insertIntheFront(Node* newNode, Node** head){
if(*head == NULL)
    *head = newNode;
else{
    Node* tail = *head;
    while(tail->nextNode != NULL)
        tail = tail->nextNode;

    tail->prevNode = newNode;
    newNode->nextNode = tail;
 }
}


//Insert a new node
void InsertAfter(Node* current, Node* newNode){
newNode->prevNode = current;
newNode->nextNode = current->nextNode;

if(current->nextNode != NULL){
    current->nextNode->prevNode= newNode;
}

current->nextNode = newNode;
}




//Removal of a node
void RemoveNode(Node** head, Node* remove){
//if the head is identical to the one to remove
if(*head == remove){

    //head points to the address of the next node
    *head = remove->nextNode;

    //if the head still exists,
    if(*head != NULL)//Null is assigned because the previous node does not exist.
        (*head)->prevNode = NULL;


    remove->prevNode = NULL;
    remove->nextNode = NULL;
} else {
    Node* temp = remove;
    //If the node to remove still has the previous node address
    if(remove->prevNode != NULL)//The previous node is connected with the next node
        remove->prevNode->nextNode = temp->nextNode;
    //if the node to remove still has the next node address
    if(remove->nextNode != NULL)//the next node address and the previous node address     are connected together.
        remove->nextNode->prevNode = remove->prevNode;
    remove->prevNode = NULL;
    remove->nextNode = NULL;
    }
}


//Node searching
Node* GetNodeAt(Node* head, int location){
Node* current = head;

while(current != NULL && (--location) >= 0){
    current = current->nextNode;
}
return current;
}

//Count nodes
int GetNodeCount(Node* head){
int count = 0;
Node* current = head;

while(current != NULL){
    current = current->nextNode;
    count++;
}
return count;
}

int lookUpFunction(Node* head, int numInput){
int foundOrNot = 0;
int indexNum = -1;
for(int i=0; i<GetNodeCount(head); i++){
    int numData = GetNodeAt(head, i)->data;
    if(numInput == numData){
        indexNum = i;
        foundOrNot = 1;
    }
}

return indexNum;

}


void inputToCacheOperation(Node* list){


int numToSubmit = rand()%50;

printf("a generated number moving into the cache is %d\n ", numToSubmit);
Node * newNode = NULL;

int cacheElementCount = sizeof(numbersInCache)/sizeof(int);

int indexNumForOperation = lookUpFunction(list, numToSubmit);//returns an index    number, -1 is returned when it cannot find any.
if(indexNumForOperation == -1 ){
    AppendNode(&list, CreateNode(numToSubmit));

下面这部分是个大麻烦。

        if(cacheElementCount>19){
        Node* firstNode = GetNodeAt(list, 0);
        RemoveNode(&list, firstNode);
        DestroyNode(firstNode);
        //When the number of nodes exceeds the cache size, it deletes the very first   node to maintain its maximum capacity.

我很生气....

} else {

    RemoveNode(&list, GetNodeAt(list, indexNumForOperation));
    newNode = CreateNode(numToSubmit);
    AppendNode(&list, newNode);
    }
}


}




int main(int argc, const char * argv[]) {
int i = 0;
int count = 0;
Node* list = NULL;
Node* newNode = NULL;
Node* current = NULL;
Node* tempNodeStorage = NULL;
Node* firstNode = NULL;

srand(time(NULL));

int numInput;
numInput=0;
//Created 20 nodes
for(int i=0; i< sizeof(numbersInCache)/sizeof(int); i++){
    //scanf("%d", &numInput);

    printf("%d\n", numbersInCache[i]);
    newNode=CreateNode(numbersInCache[i]);
    AppendNode(&list, newNode);

}

//Printing out the list.
count = GetNodeCount(list);
for(i = 0; i < count; i++){
    current = GetNodeAt(list, i);
    printf("List[%d] : %d\n", i, current->data);
}




for(int i= 0; i< 10; i++){ //Cache operation to perform
    inputToCacheOperation(list);
}


//Printing the list
count = GetNodeCount(list);
for(i = 0; i<count; i++){
    current = GetNodeAt(list,i);
    printf("List[%d] ; %d\n", i, current->data);
}

// All nodes are removed in the memory
printf("\nDestroying List....\n");

for(i=0; i<count; i++){
    current = GetNodeAt(list, 0);

    if(current != NULL){
        RemoveNode(&list, current);
        DestroyNode(current);

    }
}

}

我正在编写一个模拟磁盘操作的简单双向链表示例。 当我修改“Node* firstNode = GetNodeAt(list, 0);”时到“Node* firstNode = GetNodeAt(list, 1);”它工作正常。但是，当我将参数值设置为“0”时，它会因内存错误而崩溃。你能给我任何改进吗？ 我使用 Xcode 构建和运行代码。

Answer 1

在函数 RemoveNode() 中，您在访问它之前没有检查参数 Node* remove 是否为 NULL。所以当你的 indexNumForOperation 更多当前列表计数。