C链接列表错误
我需要一些认真的帮助来理解C ++中的链接列表我想要采用我几周前使用数组结构编写的程序并将它们转换为链接列表并添加几个新函数。 我最担心的是我对链接列表没有信心，并且花时间在这里和其他网站获取有关它们的知识。 但我找不到一个可以帮助我解决我现在遇到的问题的来源。
这是我的原始代码：
#include #include #include #include #define MAX 100 struct YouTubeVideo { char video_name[1024]; // YouTube video name int video_ranking; // Number of viewer hits char video_url[1024]; // YouTube URL }; struct YouTubeVideo Collection[MAX]; int tail = 0; //-- Forward Declaration --// void printall(); void insertion(); void sort(); void branching(char option); void menu(); void load_file(); void save_file(); int main() { char ch; load_file(); printf("\n\nWelcome to CSE240: YouTube Classic Hits\n"); do { menu(); fflush(stdin); // Flush the standard input buffer ch = tolower(getchar()); // read a char, convert to lower case branching(ch); } while (ch != 'q'); return 0; } void menu() { printf("\nMenu Options\n"); printf("------------------------------------------------------\n"); printf("i: Insert a new favorite\n"); printf("p: Review your list\n"); printf("q: Save and quit\n"); printf("\n\nPlease enter a choice (i, p, or q) ---> "); } void branching(char option) { switch(option) { case 'i': insertion(); sort(); break; case 'p': printall(); break; case 'q': save_file(); break; default: printf("\nError: Invalid Input. Please try again..."); break; } } void insertion() { if(tail < MAX) { printf("\nWhat is the name of the video? (No spaces characters allowed)\n"); scanf("%s", Collection[tail].video_name); printf("\nHow many viewer hits does this video have?\n"); scanf("%d", &Collection[tail].video_ranking); printf("\nPlease enter the URL: "); scanf("%s", Collection[tail].video_url); tail++; } else { printf("\nERROR: Your collection is full. Cannot add new entries.\n"); } } void sort() { int i = 0, j = 0; struct YouTubeVideo temp; for(i = 0; i < tail; i++) { for(j = i+1; j < tail; j++) { if(Collection[i].video_ranking < Collection[j].video_ranking) { temp = Collection[i]; Collection[i] = Collection[j]; Collection[j] = temp; } } } //RA: I think it's easier (and faster) to assume your current list is already // sorted and then insert your new element into the correct position. (You // can show this maintains a sorted list by induction.) printf("\nSorting Complete...\n"); } void printall() { int i; printf("\nCollections: \n"); for(i = 0; i < tail; i++) { printf("\nVideo Name: %s", Collection[i].video_name); printf("\nRanking (Hits): %d", Collection[i].video_ranking); printf("\nURL: %s", Collection[i].video_url); printf("\n"); } } void save_file() { FILE *fileName; // declare a pointer to File type char ch; int index = 0; fileName = fopen("ranking.dbm", "wb"); // "b" for binary mode // ìwî for write if(fileName != NULL) { fwrite(&tail, sizeof(int), 1, fileName); // Write tail to the file for later retrieval. for(index = 0; index < tail; index++) { fwrite(&Collection[index].video_name, 1024, 1, fileName); fwrite(&Collection[index].video_ranking, sizeof(int), 1, fileName); fwrite(&Collection[index].video_url, 1024, 1, fileName); } fclose(fileName); } else printf ("ERROR: Could not open file for saving data !\n"); } void load_file() { FILE *fileName; // declare a pointer to File type int index = 0; fileName = fopen("ranking.dbm", "rb"); // "b" for binary mode // ìrî for read if(fileName != NULL) { fread(&tail, sizeof(int), 1, fileName); for(index = 0; index < tail; index++) { fread(Collection[index].video_name, 1024, 1, fileName); fread(&Collection[index].video_ranking, sizeof(int), 1, fileName); fread(Collection[index].video_url, 1024, 1, fileName); } fclose(fileName); } else printf ("ERROR: Could not open file for loading data !\n"); } 这些是我想要做的确切说明：
Convert the “YouTubeVideo” array structure (Collection) into a linked-list. The program must sort (by “video_name”) the entries as they are inserted into the linked-list. [30 points] (*Note: You will lose 10 points if the linked list is not sorted.)
现在，我认为我可以用现在的理解做好，但我现在遇到了问题。
以下是我尝试解决方案的代码：
#include #include #include #include #include using namespace std; #define MAX 100 struct YouTubeVideo { char name[1024]; // YouTube video name int ranking; // Number of viewer hits char url[1024]; // YouTube URL }; struct YouTubeVideo Collection[MAX]; int tail = 0; //-- Forward Declaration --// void printall(); void insertion(); void branching(char option); void menu(); int main() { char ch; // TODO: Add code to load save data from file cout <> ch; // read a char, convert to lower case cin.ignore(); ch = tolower(ch); branching(ch); } while (ch != 'q'); return 0; } void menu() { cout << "\nMenu Options\n"; cout << "------------------------------------------------------\n"; cout << "i: Insert a new favorite\n"; cout << "p: Review your list\n"; cout << "s: Search\n"; cout << "d: Delete an entry\n"; cout << "q: Save and quit\n"; cout < "; } void branching(char option) { switch(option) { case 'i': insertion(); break; case 'p': printall(); break; case 's': // TODO: Add code to search for a particular node by name break; case 'd': // TODO: Add code to remove a node break; case 'q': // TODO: Add code to save data into a file break; default: cout <name); // p->name is array scanf("%d", &p->phone); scanf("%s", p->ranking); temp = head; if ((head == NULL)||(strcmp(p->name, temp->name) next = head; head = p; } else { while (temp->next != NULL) { if (stricmp(p->name, temp->next->name) next = temp->next; temp->next = p; return; } else temp = temp->next; } p->next = NULL; temp->next = p; } } void printall() { int i; cout << "\nCollections: \n"; for(i = 0; i < tail; i++) { cout << "\nVideo Name: " << Collection[i].name << "\n"; cout << "\nRanking (Hits): " << Collection[i].ranking << "\n"; cout << "\nURL: " << Collection[i].url << "\n"; cout << "\n"; } }
我遇到的问题是我的insertion我得到错误undeclared identifier head并且no member named next in YouTubeVideo 。 我尝试在一堆地方放置并声明它们但似乎无法解决这些错误。
我真的很感激你能提供的一些帮助和任何可能的知识。 我真的给了这个很大的帮助，但我只是暂时停下来。
您需要实际实现链接列表。 这看起来像是一个家庭作业，所以我想知道你的c ++有多远。 如果你还没有真正做类和面向对象的编程，解决这个问题最简单的方法就是在youtubevideo结构中添加下一个和前一个对象。 像这样：
struct YouTubeVideo { char video_name[1024]; // YouTube video name int video_ranking; // Number of viewer hits char video_url[1024]; // YouTube URL YouTubeVideo* next; YouTubeVideo* previous; };
接下来，您需要添加头部声明。 这将是YouTubeVideo *的类型。 添加第一个video时，将头部设置为指向该video。 然后，每当您在此之后添加新video时，将头部video的下一个指针设置为指向新video，并且新video上的前一个指针应指向头部video。 这是你的链表的开始，但你的解决方案仍然非常混乱。
如果我是你，我会看一下如何实现一些Linked List类。 这是我写的第一个Linked List类的头文件：
#ifndef LINKEDLIST_H #define LINKEDLIST_H #include "List.h" class LinkedList : public List { public: LinkedList(); virtual double get(int index) const; virtual void add(double item); virtual void insert(int index, double item); virtual double delete_item(int index); virtual int size() const; private: class Node; Node* first; Node* last; int listsize; }; class LinkedList::Node{ public: double value; Node* next; }; #endif
您可以看到此列表中包含一个类Node，并且此类包含值double value 。 如果您想使用此代码，则必须使您的节点类具有YouTubeVideo *值的字段。
好的，我会尽力让您快速了解C ++中链接列表的内容，同时让您自己完成任务。 你的代码几乎是C，这将是更多的C ++风格，虽然我会避免使用模板，并且有时可以解决C ++兽医可能会让事情更糟糕的事情。
这是一个包含整数的单链表的典型简单节点结构：
struct LinkedListNode { int value; LinkedListNode* next; };
该节点保存一个整数，并且它保存指向列表中下一个节点的指针。
对于这样的链表，这将是一个愚蠢的界面：
struct LinkedList { public: LinkedList(); bool isEmpty() const; int valueAtBeginning() const; void insertAtBeginning(int newValue); private: LinkedListNode* head; };
这个类提供了一个构造函数（一种创建链表的方法），一种将新项插入列表的方法，一种获取列表中第一个值的方法，以及一种检查列表是否为空的方法。 它还保留（供其自己参考）指向列表中第一个节点的指针。
让我们来实现这些。
这是构造函数：
LinkedList::LinkedList(): head(NULL) { }
此函数将“第一项”指针初始化为NULL。 这将是“没有第一项，因为列表为空”的代码。 说到：
bool LinkedList::isEmpty() const { return (head == NULL); }
这个函数说“如果头指针是空的，那么列表是空的。否则它不是”。 请注意该方法如何标记为const ，这使得此代码不会修改列表的任何部分。
下一个也很简单：
int LinkedList::valueAtBeginning() const { assert(!isEmpty()); return head->value; }
此函数只是跟随指向列表中第一项的指针，并取出其value成员并返回它。 它还断言该列表不为空。 这样可以很容易地找出你是否犯了从空列表中要求某些东西的错误。 再次，请注意该方法如何标记为const因为它不会更改列表。
最后，在开头添加新内容：
void LinkedList::insertAtBeginning(int newValue) { LinkedListNode* oldHead = head; LinkedListNode* newHead = new LinkedListNode(); newHead->value = newValue; newHead->next = oldHead; head = newHead; }
这在概念上很简单。 我们创建一个新节点，并将其粘贴在列表的前面。 旧的第一项成为第二项。 另外，请注意我在这里使用C ++ new而不是C malloc 。 测验：如果列表为空，这会有效吗？
好的，现在我要把它留给你存储的不仅仅是整数。 另外，尝试弄清楚如何编写从列表中删除第一项的方法（使用C ++ delete ，而不是C free ）。 然后尝试编写一个“遍历”列表的方法，打印出每个整数。 一旦你理解了这一点，尝试编写方法在最后或中间添加/删除。
简单来说，您需要将数组（类型为struct）转换为具有相同字段的链接列表。
#include #include struct LL { char name[1024]; // YouTube video name int ranking; // Number of viewer hits char url[1024]; // YouTube URL struct LL *next; // pointer to the next element }; // this is from your code #define MAX 100 struct YouTubeVideo { char name[1024]; // YouTube video name int ranking; // Number of viewer hits char url[1024]; // YouTube URL }; // now you have an array of those structs struct YouTubeVideo Collection[MAX]; // and you can fill it up as you wish int main(int argc, char**argv) { struct LL *ll = NULL; for (int i = 0; i < MaxElements; i++) { // we have a blob of memo to store your stuff x=(struct LL*)calloc(1, sizeof(struct LL)); if (x != NULL) { // just run out of memory // so handle the error } else { // nothing to do just copy fields of Collection[i] // to the newly allocated space x->name = strdup(Collection[i].name); x->ranking = Collectionp[i].ranking; x->url = strdup(Collection[i].name); x->next = NULL; // since you want your result sorted we need to find its // location in the linked list if (ll == NULL) // if the list is empty { ll=x; // and nothing else to do since a list with a single element // is always sorted } else { struct LL *p = ll, *q = ll; // need to find where in the list should x be inserted // p is not null (see the assignment above) so we // always can call strcmp on it. also for x while (p!=NULL && strcmp(p->name, x->name) < 0) // p can become null if your struct is to become the last // in the linked list: the order of comparisons are // important { q=p; // we need q, the parent node because it is // the parent node's next pointer needs to be modified p=p->next; } // once we get here p points to an LL structure or NULL if // the element to be inserted will be the last in the list // q points to the element before p // one more trick: if element being inserted is comes earlier than // the first element we need to modify ll if (q == ll) { x->next = ll; ll = x; } else { x->next=q->next; q->next=x; // these lines don't fiddle with p } } }
}
您可能希望将代码放入函数中。 请注意，插入单个链表比插入双链表更棘手，但它保存了一个指针。 并提醒一句：我没有对此进行过测试，只是键入了它的逻辑。