链表的创建与遍历

ゝ一世哀愁。 2023-05-21 10:20 3阅读 0赞

编写一个能进行链表的创建与遍历的小程序。

#### 相关知识 ####

链表是一种动态数据结构，它的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。  
链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。  
可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。  
实际上，链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。  
在C++中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下：

struct Node
    {  
        int Data;   
        Node *next;
    };

定义一个结构类型，该结构包括学生的姓名、学号、英语成绩和数学成绩。编写一个程序，基于该结构创建一条包含多个学生信息结点的单向链表，并通过链表操作，找出平均分最高和最低的学生并输出。  
要求：  
学生数量n、以及每个学生的相关信息由键盘输入（提示：动态分配每个结点数据的存储空间），程序运行结果不少于3个学生。  
输出平均分最高和最低的学生的姓名、学号和平均分。  
输入： 人数 ，第一位同学的学号、名字、两门课程成绩，第二位、第三位以此类推。  
输出： 平均分最高和最低的学生姓名、学号、平均分。  
效果如下：  
输入：

3
    1
    aaa
    10 60
    2
    bbb
    50 70
     3
     ccc
     90 100

输出：

ccc 
    3 95
    aaa 1 35

//不使用链表
    #include <iostream>
    using namespace std;
    struct stud
    { 
     int m;
     string na;
     int yi;
     int ma;
    }st[10];
    int main()
    { 
     int n,j,k=0;;
     int maxs=0,mins=110;
     cin>>n;
     for(int i=0;i<n;i++)
     { 
      cin>>st[i].m>>st[i].na>>st[i].yi>>st[i].ma;
     }
     for(int i=0;i<n;i++)
     { 
      if(st[i].yi+st[i].ma>2*maxs)
      { 
       maxs=(st[i].yi+st[i].ma)/2;
       j=i;
      }
      if(st[i].yi+st[i].ma<2*mins)
      { 
       mins=(st[i].yi+st[i].ma)/2;
       k=i;
      }
     }
     cout<<st[j].na<<" "<<st[j].m<<" "<<maxs<<endl;
     cout<<st[k].na<<" "<<st[k].m<<" "<<mins<<endl;
    }

或

//使用链表+函数
    #include <iostream>
    using namespace std;
    struct student
    { 
        int number;
        char *name;
        float englishScore;
        float mathScore;
        student *nextStudent;
    };
    //创建链表，参数分别对应学生数量，学生学号，学生名字，学生英语成绩，学生数学成绩 
    student *createList(int stuCount,int *number, char **name,float englishScore[],float mathScore[]);
    //找到成绩最好的学生并返回
    student * findHighestScore(student *);
    //找到成绩最差的学生并返回
    student * findLowestScore(student *);
    int main()
    { 
        student *head;
        student *stuh,*stul;
        int num;
        cin>>num;
        head = new student;
        int *number;
        float *englishScore, *mathScore;
        char **name;
        number = new int[num];
        name = new char*[num];
        englishScore = new float[num];
        mathScore = new float[num];
        for(int i = 0; i < num; i++)
        { 
            name[i] = new char[30];
            cin>>number[i];
            cin>>name[i];
            cin>>englishScore[i];
            cin>>mathScore[i];
        }
        head = createList(num,number,name,englishScore,mathScore);
        stuh = findHighestScore(head);
        stul = findLowestScore(head);
        cout<<stuh->name<<" "<<stuh->number<<" "<<(stuh->englishScore + stuh->mathScore)/2<<endl;
        cout<<stul->name<<" "<<stul->number<<" "<<(stul->englishScore + stul->mathScore)/2<<endl;
        return 0;
    }
    student *createList(int stuCount,int *number, char **name,float englishScore[],float mathScore[])
    { 
        student *head, *p0, *p1;
        int i;
        head = p0 = p1 = new student;
        p0->name = *name;
        p0->number = *number;
        p0->mathScore = *mathScore;
        p0->englishScore = *englishScore;
        for (i=2;i<=stuCount;i++)
        { 
            p0 = new student;
            p0->name = name[i-1];
            p0->number = number[i-1];
            p0->mathScore = mathScore[i-1];
            p0->englishScore = englishScore[i-1];
            p1->nextStudent = p0;
            p1 = p0;
        }
        p1->nextStudent = NULL;
        return head;
    }
    student * findHighestScore(student *head)
    { 
        student *p, *p0, *p1;
        p = head;
        p0 = p->nextStudent;
        p1 = p;
        while (p0!=NULL)
        { 
            if ((p1->mathScore+p1->englishScore)<(p0->mathScore+p0->englishScore))
            { 
             p1 = p0;
      }    
            p0 = p0->nextStudent;
        }
        return (p1);
    }
    student * findLowestScore(student *head)
    { 
        student *p, *p0, *p1;
        p = head;
        p0 = p->nextStudent;
        p1 = p;
        while (p0!=NULL)
        { 
            if ((p1->mathScore+p1->englishScore)>(p0->mathScore+p0->englishScore))
      { 
       p1 = p0;
      }    
            p0 = p0->nextStudent;
        }
        return (p1);
    }