树与链表结合使用.txt

这是一个用c实现的将树与链表结合起来使用的算法。

#include <stdio.h>
#include <stdlib.h>
#define SIZE 30
/*定义链表结构*/
struct student_list {
       long number;
       struct student_list *next;
    };
/*定义树结点结构*/
typedef int keytype;
typedef struct node {
  keytype key;
  struct node *leftchild,*rightchild;
  struct student_list *head;
  }BSTnode;
typedef BSTnode *BSTree;


/*定义学生结构体*/
struct student {
  long number;
  int score;
  }stud[SIZE];


insertBST(BSTree *tptr,keytype key,struct student_list *stud) {
   BSTnode *temp,*current=*tptr;
   struct student_list *listnode;
   struct student_list *temp1;
   struct student_list *temp2;
   while(current){
         /*当关键字key的结点存在时，将其学号插入到已经建立好的链表中*/
         if(current->key==key){
            
            temp1=current->head;
            temp2=(struct student_list *)malloc(sizeof(struct student_list));
            temp2=stud;
            
            while(!(temp1->next==NULL)) 
            {
             temp1=temp1->next;
            }
            
             temp1->next=temp2;
             temp1->next->next=NULL;
           
            return;
         }
         temp=current;
         current=(key<current->key)?current->leftchild:current->rightchild;
         }
    /*没有关键字key的结点时建立该结点，并建立一个空的链表*/
    current=(BSTnode *)malloc(sizeof(BSTnode));
    listnode=(struct student_list *)malloc(sizeof(struct student_list));
    current->key=key;
    current->leftchild=NULL;
    current->rightchild=NULL;
    listnode=stud;
    current->head=listnode;
    current->head->next=NULL;
    
   
    /*printf("%ld ",listnode->number);*/
    
    if(*tptr==NULL)
         *tptr=current;
    else {
        if(key<temp->key)
           temp->leftchild=current;
        else
           temp->rightchild=current;
         }
     }


/*搜索关键字结点*/
BSTnode *searching(BSTree tree,keytype key) {
       if((tree==NULL)||(key==tree->key))
          return tree;
       if(key<tree->key)
          return searching(tree->leftchild,key);
       else
          return searching(tree->rightchild,key);
      }

/*输入学号成绩并保存到文件*/
void save() {
  FILE *fp;
  int i;
  if((fp=fopen("stu_list","wb"))==NULL)
    { 
      printf("can not open the file\n");
      return;
    }
  for(i=0;i<SIZE;i++)
    if(fwrite(&stud[i],sizeof(struct student),1,fp)!=1)
    printf("file write error\n");
}
main()
{   
    int i;
    FILE *fp;
    BSTree tree=NULL,q=NULL;
    struct student_list *temp;
    struct student_list list[SIZE];
    /* 此代码是用来输入学生学号和成绩并保存到文件stu_list，第一次使用该程序时需要使用
    for(i=0;i<SIZE;i++)
    scanf("%ld %d",&stud[i].number,&stud[i].score);
    save();
   */
    /*从文件stu_list读入学生的学号和成就信息并将其插入到树中*/
    fp=fopen("stu_list","rb");
    for(i=0;i<SIZE;i++)
    { 
      fread(&stud[i],sizeof(struct student),1,fp);
       /*printf("%d ", stud[i].score);*/
       list[i].number=stud[i].number;
       insertBST(&tree,stud[i].score,&list[i]);
    }
   printf("\n\\\\\\\\ The score of students and their NO \\\\\\\\ \n");
   printf("The number of students is 30\n");
   for(i=0;i<=100;i++){
       q=searching(tree,i);
       if(!(q==NULL)){
       printf("\n");
       printf("Score:%d --NO: ",q->key);
       temp=q->head;
       printf("%ld ",temp->number);

       while(!(temp->next==NULL)){
       temp=temp->next;
       printf("%ld ",temp->number);
       }
       }
      
       }
    getch();    /* 请不要删除此行 */


}