我已经通过@Keith Randall 和lserni 的帮助解决了这个问题,我已经实现了二叉搜索树和结构数组。
第一种方式,使用 qsort 对数组进行排序:
我必须创建一个比较函数:
int compare(const void *p1, const void *p2){
return (* (struct student **) p1)->id - (* (struct student **) p2)->id;
}
还有我的其他辅助功能;
void get_studentList(struct student **listp,int size){
int id,i;
struct student *ansp[size];
for(i=0;i<size;i++){
printf("Enter student's id to exit enter -1> ");
scanf("%d", &id);
ansp[i] = malloc(sizeof(courseList_node_t));
ansp[i]->id = id;
ansp[i]->restp = NULL;
}
qsort (ansp, size, sizeof(struct student *), compare);
for(i=0;i<size;i++){
listp[i] = ansp[i];
}
}
courseList_node_t * insert_studentSchedule(courseList_node_t *headp, int size){
courseList_node_t *cur_nodep;
if(headp == NULL){
cur_nodep = scan_course();
headp = cur_nodep;
} else {
headp->restp = insert_studentSchedule(headp->restp,size);
}
return (headp);
}
还有我的显示功能;
void display_schedule(struct student **headp, int size){
courseList_node_t *cur_nodep;
int i = 0;
while(i< size){
cur_nodep = headp[i]->restp;
printf("Student id > %d\n", headp[i]->id);
while(cur_nodep != NULL){
printf("Course name> %s\t", cur_nodep->course);
printf("Course credit> %d\t", cur_nodep->credit);
printf("Course section> %d\n", cur_nodep->section);
cur_nodep = cur_nodep->restp;
}
i++;
}
}
第二种方式,二叉搜索树:
我将头文件的 typedef 部分更改为:
typedef struct tree_node_s{
int id;
struct courseList_node_s *restp;
struct tree_node_s *leftp, *rightp;
}tree_node_t;
和我的宏来形式化节点动态分配的标准模式:
#define TYPED_ALLOC(type) (type *)malloc(sizeof(type))
还有我创建二叉搜索树的实现:
/*
* Insert a new id in a binary search tree.
* Pre: rootp points to the root node of a binary search tree
*/
tree_node_t * get_studentTree(tree_node_t *rootp, int newId)
{
if (rootp == NULL){
rootp = TYPED_ALLOC(tree_node_t);
rootp->id = newId;
rootp->restp = NULL;
rootp->leftp = NULL;
rootp->rightp = NULL;
} else if ( newId == rootp->id){
/* */
} else if (newId < rootp->id){
rootp->leftp = get_studentTree(rootp->leftp, newId);
} else {
rootp->rightp = get_studentTree(rootp->rightp, newId);
}
return (rootp);
}
这部分与这个问题无关。我给他们是因为我想分享真实问题的部分解决方案。
/*
* Its aim to add courses to restp component of subtree
* It may have some problems. And you can omit it. Because it not related with this question
* Pre: elementp not empty
*/
courseList_node_t * add_course(courseList_node_t *nextp, courseList_node_t *elementp){
if(nextp->restp == NULL){
nextp->restp = elementp;
} else {
nextp->restp = add_course(nextp->restp,elementp);
}
return (nextp);
}
/*
* It is not neccessary to first call get_studentTree function. It simply creates a linked list which consist of student class/lecture schedule.
* Pre: ele and id not empty
* Post: Tree returned includes all schedule and retains binary search tree properties.
*/
tree_node_t * insert_studentSchedule(tree_node_t *rootp,courseList_node_t *ele, int id){
if (rootp == NULL){
rootp = get_studentTree(rootp, id);
rootp->restp = TYPED_ALLOC(courseList_node_t);
strcpy(rootp->restp->course, ele->course);
rootp->restp->credit = ele->credit;
rootp->restp->section = ele->section;
}
else if(rootp->id == id){
if ( rootp->restp == NULL ){
rootp->restp = TYPED_ALLOC(courseList_node_t);
strcpy(rootp->restp->course, ele->course);
rootp->restp->credit = ele->credit;
rootp->restp->section = ele->section;
} else {
rootp->restp = add_course(rootp->restp, ele);
}
} else if ( id < rootp->id ){
if ( rootp->leftp != NULL )
rootp->leftp = insert_studentSchedule(rootp->leftp, ele, id);
} else if ( id > rootp->id ) {
if ( rootp->rightp != NULL )
rootp->rightp = insert_studentSchedule(rootp->rightp, ele, id);
}
return (rootp);
}
/*
* Course scanning function
*/
courseList_node_t * scan_course(void){
courseList_node_t *cur_coursep;
char courseName[6];
cur_coursep = (courseList_node_t *)malloc(sizeof(courseList_node_t));
printf("Welcome to course scanning part>\n");
printf("Enter the name of course> ");
scanf("%s", courseName);
strcpy(cur_coursep->course, courseName);
printf("Enter the credit of course> ");
scanf("%d", &cur_coursep->credit);
printf("Enter the section of course> ");
scanf("%d", &cur_coursep->section);
cur_coursep->restp = NULL;
return (cur_coursep);
}
/*
* My way to print binary search tree with all elements
*/
void display_schedule(tree_node_t *rootp){
courseList_node_t *cur_course;
if(rootp == NULL)
return;
display_schedule(rootp->leftp);
if (rootp->restp == NULL)
printf("Tree with id: %d element has no member!", rootp->id);
else {
cur_course = rootp->restp;
while (cur_course != NULL){
printf("Student Id> %d\n", rootp->id);
printf("Course name> %s\t", rootp->restp->course);
printf("Course credit> %d\t", rootp->restp->credit);
printf("Course section> %d\n", rootp->restp->section);
cur_course = cur_course->restp;
}
}
display_schedule(rootp->rightp);
}
它可能无法完全解决书本问题,但在您的帮助下,它是基本部分的解决方案。如果你发现了错误。随意添加评论。