如何使用c中的结构数组创建排序链表

这里有一个包含一些信息的student.txt文件，我将它们带到数组中，并使用数组创建了一个排序的链表，但它没有列出任何信息。我不知道为什么会发生这种事！这是联机GDB会话。

谁能发现我在代码中的错误并解释它？

这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct studInfo {
int studNr;
char studName[12];
int grade;
};
struct node {
struct studInfo info;
struct node *link;
};
typedef struct node *NODEPTR;
NODEPTR getnode(void);
void fileIntoArray(struct studInfo allStudent[],int *num);
void sortByNum(struct studInfo allstudent[], NODEPTR *, int num);
void list(NODEPTR);
int main() {
struct studInfo allStudent[150];
NODEPTR headNum, headName;
int choice;
int num;

fileIntoArray(allStudent, &num);
sortByNum(allStudent, &headNum, num);
list(headNum);

return 0;
}
void fileIntoArray(struct studInfo allStudent[], int *num) {
FILE *ptr = fopen("student.txt", "r");
int i = 0;
while (!feof(ptr)) {
fscanf(ptr, "%d%s%d", &allStudent[i].studNr,
allStudent[i].studName, &allStudent[i].grade);
i++;
}
*num = i;
fclose(ptr);
}
void sortByNum(struct studInfo allStudent[], NODEPTR *headNum, int num) {
NODEPTR head, p, save, prev;
head = NULL;
for (int i = 0; i <= num; ++i)  {
p = getnode();
p->info = allStudent[i];
if (head = NULL) {
head = p;
p->link = NULL;
} else {
if (p->info.studNr < head->info.studNr) {
p->link = head;
head = p;
} else {
save = head;
while ((save->info.studNr < p->info.studNr) &&(save != NULL)) {
prev = save;
save = save->link;
if (save == NULL) {
prev->link = p;
p->link = NULL;
} else {
p->link = prev->link;
prev->link = p;
}
}
}
}
}
*headNum = head;
}
void list(NODEPTR headNum) {
NODEPTR p = headNum;
int line = 0;
while (p->link != NULL) {
line++;
if (line > 25) {
printf("Tab a buttonn");
getchar();
line = 1;
}
printf("%d %d  %s  %dn", line, p->info.studNr,
p->info.studName, p->info.grade);
p = p->link;
}
}
NODEPTR getnode() {
NODEPTR q;
q = (NODEPTR)malloc(sizeof(struct node));
return(q);
}

存在多个问题：

在sortByNum中，循环for (int i = 0; i <= num; ++i)运行一次迭代太远。您应该使用i < num来精确地迭代num次。
在sortByNum()中，测试if (head = NULL)不正确。你应该写：
```
if (head == NULL) 
```

while (!feof(ptr))也不正确。你应该写：

while (fscanf(ptr, "%d%s%d", &allStudent[i].studNr,
allStudent[i].studName, &allStudent[i].grade) == 3) {
i++;
}

您应该将数组长度传递给fileIntoArray，这样它就可以避免写入超出数组末尾的内容。
node结构应该具有指向数组中studInfo条目的指针，而不是副本。
节点插入代码过于复杂，可能不正确。
在list中，如果作为参数传递的列表为空，则测试while (p->link != NULL)将导致崩溃。
CCD_ 13和CCD_ 14应该返回一个结果，而不是通过指针将其存储到调用方变量。
不建议在诸如NODEPTR之类的typedef后面隐藏指针。使用struct node *ptr或可能将node定义为struct node的typedef并写入node *ptr。

这是一个修改后的版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct studInfo {
int studNr;
char studName[32];
int grade;
};
struct node {
struct studInfo *info;
struct node *link;
};
struct node *getnode(void);
int fileIntoArray(struct studInfo allStudent[], int len);
struct node *sortByNum(struct studInfo allstudent[], int num);
struct node *sortByName(struct studInfo allstudent[], int num);
void list(const struct node *p);
int main() {
struct studInfo allStudent[150];
int num = fileIntoArray(allStudent, 150);
struct node *headNum = sortByNum(allStudent, num);
struct node *headName = sortByName(allStudent, num);
printf("nStudent list by ID:n");
list(headNum);
printf("nStudent list by name:n");
list(headName);
return 0;
}
int fileIntoArray(struct studInfo allStudent[], int len) {
int i = 0;
FILE *ptr = fopen("student.txt", "r");
if (ptr != NULL) {
while (i < len && fscanf(ptr, "%d%31s%d",
&allStudent[i].studNr,
allStudent[i].studName,
&allStudent[i].grade) == 3) {
i++;
}
fclose(ptr);
}
return i;
}
struct node *sortByNum(struct studInfo allStudent[], int num) {
struct node *head = NULL;
for (int i = 0; i < num; ++i) {
struct node *p = getnode();
p->info = &allStudent[i];
if (head == NULL || p->info->studNr < head->info->studNr) {
p->link = head;
head = p;
} else {
struct node *prev = head;
while (prev->link && prev->link->info->studNr < p->info->studNr) {
prev = prev->link;
}
p->link = prev->link;
prev->link = p;
}
}
return head;
}
struct node *sortByName(struct studInfo allStudent[], int num) {
struct node *head = NULL;
for (int i = 0; i < num; ++i) {
struct node *p = getnode();
p->info = &allStudent[i];
if (head == NULL || strcmp(p->info->studName, head->info->studName) < 0) {
p->link = head;
head = p;
} else {
struct node *prev = head;
while (prev->link && strcmp(prev->link->info->studName, p->info->studName) < 0) {
prev = prev->link;
}
p->link = prev->link;
prev->link = p;
}
}
return head;
}
void list(const struct node *p) {
int line = 0, c;
while (p != NULL) {
line++;
if (line > 25) {
printf("Press enter>");
fflush(stdout);
while ((c = getchar()) != EOF && c != 'n')
continue;
printf("r            r");
line = 1;
}
printf("%d %d  %s  %dn", line, p->info->studNr,
p->info->studName, p->info->grade);
p = p->link;
}
}
struct node *getnode(void) {
struct node *q = malloc(sizeof(*q));
if (q == NULL) {
perror("cannot allocate node");
exit(1);
}
return q;
}

修正了list函数，请参阅代码中的注释。

在给定的数据结构上提供了插入排序的实现。(还有一个更简洁的实现：维基百科上的插入排序。)

请注意，下面的代码已减少。它只是包含了说明排序所必需的内容。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
struct studInfo {
int studNr;
char studName[12];
int grade;
};
struct node {
struct studInfo info;
struct node *link;
};
typedef struct node *NODEPTR;
void list(NODEPTR headNum) {
NODEPTR p = headNum;
int line = 0;
while (p != NULL) { // corrected from  p->link != NULL
line++;
if (line > 25) {
printf("Tab a buttonn");
getchar();
line = 1;
}
printf("%d %d  %s t %dn", line, p->info.studNr,
p->info.studName, p->info.grade);
p = p->link;
}
}
// Insertion Sort
NODEPTR sort(NODEPTR root, bool sortByName) {
if (root == NULL || root->link == NULL) {
// All lists with less than two elements are already sorted.
return root;
}
// put first element into sorted list
NODEPTR sorted_root = root;
// start iteration with second element
NODEPTR iterator = root->link;
// set end of sorted list
sorted_root->link = NULL;
while (iterator != NULL) {
// trace position directly before insertion point
NODEPTR previous = NULL;
// iterate over already sorted list
NODEPTR sorted_iterator = sorted_root;
// determine insertion point in already sorted list
while (
// list end not reached
sorted_iterator != NULL
&&
// need to advance in sorted list for proper position
(sortByName ?
strcmp(sorted_iterator->info.studName, iterator->info.studName) <= 0
:
sorted_iterator->info.studNr < iterator->info.studNr)) {
previous = sorted_iterator;
sorted_iterator = sorted_iterator->link;
}
if (previous == NULL) {
// prepend sorted list with element
NODEPTR tmp = sorted_root;
sorted_root = iterator;
iterator = iterator->link;
sorted_root->link = tmp;
} else if (sorted_iterator == NULL) {
// append new last element in sorted list
previous->link = iterator;
NODEPTR tmp = iterator->link;
iterator->link = NULL;
iterator = tmp;
} else {
// insert element at correct position
NODEPTR tmp = iterator->link;
previous->link = iterator;
iterator->link = sorted_iterator;
iterator = tmp;                
}
}
return sorted_root;
}
int main() {
struct studInfo allStudent[3];
allStudent[0].studNr = 303; strcpy(allStudent[0].studName,"Bella");   allStudent[0].grade = 1;
allStudent[1].studNr = 202; strcpy(allStudent[1].studName,"Carla");   allStudent[1].grade = 2;
allStudent[2].studNr = 101; strcpy(allStudent[2].studName,"Adeline"); allStudent[2].grade = 3;
struct node links[3];
links[0].info = allStudent[0]; links[0].link = &links[1];
links[1].info = allStudent[1]; links[1].link = &links[2];
links[2].info = allStudent[2]; links[2].link = NULL;
NODEPTR head;
head = &links[0];
printf("Sort by student numbern");
head = sort(head, false);
list(head);
printf("Sort by student namen");
head = sort(head, true);
list(head);
return 0;
}

代码中的学生顺序相反，现在看看排序是否有效：

$ gcc students.c
$ ./a.out       
Sort by student number
1 101  Adeline   3
2 202  Carla     2
3 303  Bella     1
Sort by student name
1 101  Adeline   3
2 303  Bella     1
3 202  Carla     2
$

似乎工作得很好。：-)

相关内容

最新更新

热门标签：