我自定义的头文件如下。
#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 %dn ", 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("%dn", 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] : %dn", 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] ; %dn", 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 来构建和运行代码。
在函数 RemoveNode() 中，您没有检查参数Node* remove在访问它之前是否NULL。 因此，当您indexNumForOperation更新的列表计数时，RemoveNode(&list, GetNodeAt(list, indexNumForOperation))可能会传递NULL RemoveNode()。