出于教学原因，我目前正在用 C 实现一个 LinkedList。 我快完成了，但现在很挣扎，因为它并没有完全按照预期的方式去做。
长话短说，输出不是我对代码的期望 - 现在我在脑子里盘旋着这个问题，有点累了。
这里是整个实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/********** GLOBALS *******************************/
#define DEBUG 0
/********** STRUCT AND TYPES DEFINTIONS ***********/
/* a node with key, data and reference to next node*/
typedef struct Node {
int key;
char string[1024];
struct Node *next; // pointer to next node
} Node;
/* the actual linked list: ref to first and last Node, size attribute */
typedef struct LinkedList {
struct Node *first;
struct Node *last;
int size;
} LinkedList;
/********** FUNCTION HEADERS **********************/
LinkedList init_list();
void insert_end(LinkedList *list, int key, char string[]);
void insert_beginning(LinkedList *list, int key, char string[]);
int remove_end(LinkedList *list);
int remove_beginning(LinkedList *list);
int print_list(LinkedList *list);
void free_list(LinkedList *list);
char * get_string(LinkedList *list, int key);
/*********** FUNCTION DEFINITIONS ***************/
/* init_list Returns an appropriately (for an empty list) initialized struct List*/
LinkedList init_list() {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
LinkedList list;
list.first = NULL;
list.last = NULL;
list.size = 0;
return list;
}
/* Given a List, a key and a string adds a Node containing this
information at the end of the list*/
void insert_end(LinkedList *list, int key, char string[]) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
list->size++; // increment size of list
// intialize the new Node
Node* newN = malloc(sizeof(Node));
newN->key = key;
strcpy(newN->string, string);
newN->next = NULL;
Node* oldLast = list->last; // get the old last
oldLast->next = newN; // make new Node the next Node for oldlast
list->last = newN; // set the new last in the list
printf("new Node at end: %d %s %p \n", newN->key, newN->string, newN->next);
}
/* Given a List, a key and a string adds a Node, containing
this information at the beginning of the list */
void insert_beginning(LinkedList *list, int key, char string[]) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
list->size++; // increment size of list
Node* oldFirst = list->first; //get the old first node
// intialize the new Node
Node* newN = malloc(sizeof(Node));
newN->key = key;
strcpy(newN->string,string);
newN->next = oldFirst;
list->first = newN; // set the new first
//special case: if list size == 1, then this new one is also the last one
if(list->size == 1)
list->last = newN;
printf("new Node at beginning: '%d' '%s' '%p' \n", newN->key, newN->string, newN->next);
}
/* Removes the first Node from the list*/
int remove_beginning(LinkedList *list) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
if(list->size <= 0)
return -1;
list->size--;
Node * oldFirst = list->first;
list->first = oldFirst->next;
oldFirst = NULL;
return 0;
}
/* Removes the last Node from the list.*/
int remove_end(LinkedList *list) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
if(list->size <= 0)
return -1;
list->size--; // decrement list size
//Node * oldLast = list->last; // get ref to old last
//oldLast = NULL; // set it null
//free(oldLast);
Node * startNode = list->first;
list->last = NULL; // set listref last to null
//find the now new last node..
Node * newLast = NULL;
while(startNode->next != NULL) {
newLast=startNode;
}
// if list is not empty now..
if(list->size > 0)
list->last = newLast;
return 0;
}
/* Given a List prints all key/string pairs contained in the list to
the screen*/
int print_list(LinkedList *list) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
if(list->size <=0)
return -1;
printf("List.size = %d \n", list->size);
Node *startN = list->first; //get first
printf("Node#%d.string = '%s', .next = '%d' \n",list->first->key, list->first->string, list->first->next->key);
//iterate through list
while(startN->next != NULL) {
printf("Node#%d.string = '%s', .next = '%d' \n",startN->key, startN->string, startN->next->key);
startN = startN->next;
}
return 0;
}
/* Given a List, frees all memory associated with this list. */
void free_list(LinkedList *list) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
if(list != NULL)
free(list);
}
/* Given a List and a key, iterates through the whole List and returns
the string of the first node which contains the key */
char * get_string(LinkedList *list, int key) {
if(DEBUG)
printf("%s:%d called \n", __FUNCTION__, __LINE__);
Node *startN = list->first; //get first
//iterate through list
while(startN->next != NULL) {
if(startN->key == key)
return startN->string;
else
startN = startN->next;
}
return NULL;
}
/*************** MAIN **************/
int main(void)
{
LinkedList list = init_list();
insert_beginning(&list, 1,"im the first" );
insert_beginning(&list, 2,"im the second" );
insert_beginning(&list, 3,"im the third" );
//insert_end(&list, 2, "im the second");
//insert_end(&list, 3,"im the third");
//insert_end(&list, 4, "forth here");
//insert_end(&list, 5, "...and i am last");
//insert_end(&list, 6, "END");
print_list(&list);
// remove_end(&list);
// remove_beginning(&list);
// print_list(&list);
// free_list(&list);
}
这是输出，与预期不同(但代码编译正常):
new Node at beginning: '1' 'im the first' '00000000'
new Node at beginning: '2' 'im the second' '00762EF8'
new Node at beginning: '3' 'im the third' '00764330'
List.size = 3
Node#3.string = 'im the third', .next = '2'
Node#3.string = 'im the third', .next = '2'
Node#2.string = 'im the second', .next = '1'
如您所见，print_list 要么没有正确打印列表，要么列表本身不正确。
- 我哪里失败了？
一如既往，非常欢迎最佳实践提示，来源是公共(public)领域。
最佳答案
您的队列实际上是一个堆栈，因为您按照先到后出的顺序将内容推到头部。
我只是按如下方式更改了您的 print_list 函数；
//iterate through list
do {
printf("Node#%d.string = '%s', .next = '%p' \n",startN->key, startN->string, startN->next);
startN = startN->next;
}while(startN != NULL);
我通过此更改获得的输出是；
new Node at beginning: '1' 'im the first' '0x0'
new Node at beginning: '2' 'im the second' '0x2003ac40'
new Node at beginning: '3' 'im the third' '0x2004b088'
List.size = 3
Node#3.string = 'im the third', .next = '0x2004b088'
Node#2.string = 'im the second', .next = '0x2003ac40'
Node#1.string = 'im the first', .next = '0x0'
关于c - LinkedList - C 中的类型 - 访问函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44115777/