// 单链表的操作
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
/////////////////////////////////////////////////////////////////////////////////
// 定义程序中的常量 //
/////////////////////////////////////////////////////////////////////////////////
//N___代表最多班级数
#define N 10
#define MenuCount 12
/////////////////////////////////////////////////////////////////////////////////
// 常量定义结束 //
/////////////////////////////////////////////////////////////////////////////////
//*****************************************************************************//
/////////////////////////////////////////////////////////////////////////////////
// 定义变量类型 //
/////////////////////////////////////////////////////////////////////////////////
typedef struct student{ //定义学生的数据类型,类型名为student
long no; //学号,最多10位整数
char name[10]; //姓名,最多3个汉字
char sex[3]; //性别:"男"或"女"
long birthday; //出生日期,例:19850615 表示1985年6月15日出生
float score; //高考成绩
} ElemType;
struct sNode{ //定义结点类型
ElemType data; //定义结点的数据域为 ElemType类型
struct sNode *link; //定义结点的指针域
};
/////////////////////////////////////////////////////////////////////////////////
// 变量类型定义结束 //
/////////////////////////////////////////////////////////////////////////////////
//*****************************************************************************//
/////////////////////////////////////////////////////////////////////////////////
// 函数原型声明区开始 //
/////////////////////////////////////////////////////////////////////////////////
//初始化线性表，即置单链表的表头指针为空
void InitList(struct sNode **HL);
// 显示功能菜单并输入用户的功能选择
int MenuChoice();
// 输入一个结点的数据存入xp所指的变量中
void InputNode(ElemType *xp);
//输出一个结点的数据
void OutputNode(ElemType x);
//得到一个班第i个学生的数据(i=0,1,2,……)存入xp所指的变量中
//得到第i个学生的数据则返回值为1，否则返回值为0
int GetNode(struct sNode L,int i,ElemType *xp);
//根据学号在一个班的链表中查找一个学生是该链表中的第几个结点
//找到该学号的学生，则返回该学生的结点序号(0,1,2,…… )，否则返回-1
int FindNode(struct sNode L,long no);
//遍历，输出链表中的每1个结点的数据
void TraverseList(struct sNode *L);
//向单链表的末尾添加一个值为x的结点
void InsertLastList(struct sNode **HL,ElemType x);
//向单链表中第POS(pos=0,1,2,……)个结点之前插入元素值为X的结点，若插入成功返回1，否则返回0
int InsertPosList(struct sNode **HL,int pos,ElemType x);
//向单链表的表头插入一个值为x的结点
void InsertFirstList(struct sNode **HL,ElemType x);
//删除学号为x的接点
void deletevaluelist(struct sNode **HL,int x);
//修改学号为no的学生的数据为结构体x
void updatanolist(struct sNode *HL,int no,ElemType x);
//学号找人
ElemType getelem(struct sNode *HL,int no);
//姓名找人
ElemType getelemname(struct sNode *HL,char *name_1);
//将CR填加到BC的后面
void copyList(struct sNode **CR,struct sNode **BC);
void zuhelink(struct sNode *HL1,struct sNode *HL,struct sNode **HL2);
/////////////////////////////////////////////////////////////////////////////////
// 函数原型声明区结束 //
/////////////////////////////////////////////////////////////////////////////////
//*****************************************************************************//
/////////////////////////////////////////////////////////////////////////////////
// 主函数开始 //
/////////////////////////////////////////////////////////////////////////////////
void main()
{
struct sNode *Class_List[N]; //定义班级链表数组,每一个元素都是一个指针变量,Class_List[i]用于存放第i个班的表指针
int choice; //用于存放用户对操作的选择
int i; //临时变量
int Class_no,Class_no1,Class_no2,Class_no3; //临时变量，用于存放操作中需要的临时的班级序号
ElemType newstudent; //临时变量，用于存放一个结点的数据域的数据
char wait;//临时变量
char name_1[10];
int no;
//初始化每1个班级的链表为空表
for(i=1;i<N;i++)
InitList(&Class_List[i]);
do{
choice=MenuChoice();
switch(choice){
case 1: //建立一个班级的链表
cout<<"\t当前执行的功能是：建立一个班级的链表"<<endl<<endl;
do{
cout<<"\n\n请输入班级序号(1,2,……,"<<N<<")：";
cin>>Class_no;
}while(Class_no<1 || Class_no>N);
//依次输入班级中每一个学生的信息
//输入第1个学生的信息
cout<<"\n\t输入一个学生的数据(学号为0，则表示结束)：\n\n";
InputNode(&newstudent);
while(newstudent.no!=0)
{
//如果输入的学生信息中的学号不等0，则将这个学生的信息加入到班级链表中
InsertLastList(&Class_List[Class_no],newstudent);
//输入下一个学生的信息
cout<<"\n\t输入一个学生的数据(学号为0，则表示结束)：\n\n";
InputNode(&newstudent);
}
//输出新建班级链表中所有结点的信息
cout<<"\n\t新建 "<<Class_no<<" 班级链表，该班所有学生的信息如下："<<endl;
TraverseList(Class_List[Class_no]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break; //完成建立一个班级链表操作
case 2: cout<<"请输入插入学生所在班级:";
cin>>Class_no;
cout<<"请输入插入数据\n";
InputNode(&newstudent);
InsertLastList(&Class_List[Class_no],newstudent);
cout<<Class_no<<" 班级链表，该班所有学生的信息如下："<<endl;
TraverseList(Class_List[Class_no]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 3: cout<<"请输入删除学生所在班级:";
cin>>Class_no;
TraverseList(Class_List[Class_no]);
cout<<"请输删除学生学号：\n";
cin>>no;
deletevaluelist(&Class_List[Class_no],no);
cout<<Class_no<<" 班级链表，该班所有学生的信息如下："<<endl;
TraverseList(Class_List[Class_no]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 4: cout<<"请输入修改学生所在班级:";
cin>>Class_no;
TraverseList(Class_List[Class_no]);
cout<<"请输修改学生学号：\n";
cin>>no;
cout<<"\n\t输入学生的数据：\n\n";
InputNode(&newstudent);
updatanolist(Class_List[Class_no],no,newstudent);
cout<<Class_no<<" 班级链表，该班所有学生的信息如下："<<endl;
TraverseList(Class_List[Class_no]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 5: cout<<"请输入该学生所在班级:";
cin>>Class_no;
cout<<"请输入改学生学号：";
cin>>no;
OutputNode(getelem(Class_List[Class_no],no));
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 6: cout<<"请输入班级:";
cin>>Class_no;
TraverseList(Class_List[Class_no]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
case 7: cout<<"请输入该学生所在班级:";
cin>>Class_no;
cout<<"请输入改学生学号：";
cin>>no;
OutputNode(getelem(Class_List[Class_no],no));
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
case 8: cout<<"请输入该学生所在班级:";
cin>>Class_no;
cout<<"请输入改学生姓名：";
cin>>name_1;
OutputNode(getelemname(Class_List[Class_no],name_1));
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
case 9:
cout<<"请输入该学生所在班级:";
cin>>Class_no;
cout<<"请输入改学生学号：";
cin>>no;
OutputNode(getelem(Class_List[Class_no],no));
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 10:cout<<"请输入该学生所在班级:";
cin>>Class_no;
cout<<"请输入改学生姓名：";
cin>>name_1;
OutputNode(getelemname(Class_List[Class_no],name_1));
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 11: cout<<"请输入插入班级:";
cin>>Class_no1;
cout<<"请输入被插入班级:";
cin>>Class_no2;
copyList(&Class_List[Class_no1],&Class_List[Class_no2]);
cout<<"被插入班级现在的数据：\n";
TraverseList(Class_List[Class_no2]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
case 12: cout<<"请输入第一个班级:";
cin>>Class_no1;
cout<<"请输入第二个班级:";
cin>>Class_no2;
cout<<"生成新班级班级:";
cin>>Class_no3;
zuhelink(Class_List[Class_no1],Class_List[Class_no2],&Class_List[Class_no3]);
cout<<"被插入班级现在的数据：\n";
TraverseList(Class_List[Class_no3]);
cout<<"\n\n本功能本次操作执行完毕！\n\n";
cout<<"输入任意字符并按回车键，继续……\n\n";
cin>>wait;
break;
}
}while(choice!=0);
cout<<"谢谢使用本系统，欢迎下次再使用本系统！！！\n\n";
}
/////////////////////////////////////////////////////////////////////////////////
// 主函数结束 //
/////////////////////////////////////////////////////////////////////////////////
//*****************************************************************************//
/////////////////////////////////////////////////////////////////////////////////
// 函数的实现代码开始 //
/////////////////////////////////////////////////////////////////////////////////
//初始化线性表，即置单链表的表头指针为空
void InitList(struct sNode **HL)
{
*HL=NULL;
}
// 显示功能菜单并输入用户的功能选择
int MenuChoice()
{
int choice;
cout<<" 功能菜单 "<<endl;
cout<<" 1: 建立一个班级的链表"<<endl;
cout<<" 2: 在一个班级链表中插入一个学生结点 "<<endl;
cout<<" 3: 在一个班级链表中删除一个学生结点 "<<endl;
cout<<" 4: 修改班级链表中一个学生的数据 "<<endl;
cout<<" 5: 得到班级链表中一个学生的数据 "<<endl;
cout<<" 6: 输出一个班级链表中所有学生的数据 "<<endl;
cout<<" 7: 输出一个已知学号的学生的数据 "<<endl;
cout<<" 8: 输出一个已知姓名的学生的数据 "<<endl;
cout<<" 9: 根据学号查询并输出一个学生的数据 "<<endl;
cout<<" 10: 根据姓名查询并输出一个学生的数据 "<<endl;
cout<<" 11: 将一个班的所有学生添加到另一班的后面 "<<endl;
cout<<" 12: 根据二个班所有学生数据生成一个新班的链表 "<<endl;
cout<<"\n 0: 结束程序 "<<endl;
cout<<"\n\n 请输入选择(输入数字0__13 ): ";
do{
cin>>choice;
if( (choice<0) || (choice>MenuCount) ) cout<<"输入的选择有误!!! 请重新输入选择";
}while ( (choice<0) || (choice>MenuCount) );
return choice;
}
// 输入一个结点的数据存入xp所指的变量中
void InputNode(ElemType *xp)
{
ElemType x;
cout<<"\t学号："; cin>>x.no;
cout<<"\t姓名："; cin>>x.name;
cout<<"\t性别："; cin>>x.sex;
cout<<"\t出生日期："; cin>>x.birthday;
cout<<"\t高考成绩："; cin>>x.score;
*xp=x;
}
//输出一个结点的数据
void OutputNode(ElemType x)
{
cout<<"\t学号："<<x.no;
cout<<"\t姓名："<<x.name;
cout<<"\t性别："<<x.sex;
cout<<"\t出生日期："<<x.birthday;
cout<<"\t高考成绩："<<x.score;
cout<<endl<<endl;
}
//得到一个班第i个学生的数据(i=0,1,2,……)存入xp所指的变量中
//得到第i个学生的数据则返回值为1，否则返回值为0
int GetNode(struct sNode *L,int i,ElemType *xp)
{
int j;
struct sNode *p;
if(i<0) return 0; //i值不合法
//使p指向L的第i个结点
p=L;
for(j=0; j<i; j++)
p=p->link;
if(p==NULL) return 0; //i值不合法，i值超过了链表L中元素的个数
*xp=p->data;
return 1; //说明正确得到了L中第i个结点的数据
}
//根据学号在一个班的链表中查找一个学生是该链表中的第几个结点
//找到该学号的学生，则返回该学生的结点序号(0,1,2,…… )，否则返回-1
int FindNode(struct sNode *L,long no)
{
int i;
struct sNode *p;
//查找
p=L; //使p指向L的第0号结点
i=0; //结点序号初始值为0
while(p!=NULL && p->data.no!=no)
{
p=p->link; //使p指向当前所指结点的后一个结点
i++; //结点序号加1
}
//判断是否找到
if(p==NULL)
return -1; //未找到，返回-1
else
return i; //找到，返回结点序号i
}
//遍历，输出链表中的每1个结点的数据
void TraverseList(struct sNode *L)
{
int i; //临时变量，记录L中有多少个结点
//输出表头
cout<<"\n\n";
cout<<"\t学号\t姓名\t性别\t出生日期\t高考成绩\n";
//输出表中结点数据
i=0;
while(L!=NULL)
{
cout<<'\t'<<L->data.no;
cout<<'\t'<<L->data.name;
cout<<'\t'<<L->data.sex;
cout<<'\t'<<L->data.birthday;
cout<<'\t'<<L->data.score;
cout<<endl;
i++; //结点数加1
L=L->link; //L指向当前结点的后继结点
}
cout<<"\n\n";
cout<<"\t链表中共有: "<<i<<" 个学生的数据。"<<endl;
cout<<"\n\n";
}
//向单链表的末尾添加一个值为x的结点
void InsertLastList(struct sNode **HL,ElemType x)
{
struct sNode *newp;
struct sNode *p;
// 申请新结点变量
newp=(sNode*)malloc(sizeof(struct sNode));
//判断申请是否成功
if(newp==NULL)
{
cout<<"内存动态空间用完，退出运行！\n";
exit(1);
}
//把x中的数据存入新结点的数据域(data域)
newp->data=x;
//把新结点插入到表尾
if(*HL==NULL) //如果原来的链表是一个空链表，则表头指针指向新结点
{
*HL=newp;
}
else //如果不是空链表，则查找链表的最后一个结点
{
//下面的循环使p从指向表头的第1个结点开始，依次移动。循环结束后，p指向链表的最后一个结点
p=*HL; //p指向链表的第1个对点
while(p->link != NULL) p=p->link; //如果p所指结点有后继结点，则p指向当前结点的后继结点
//使新结点添加到表尾结点之后
p->link=newp; //使表尾结点的指针域指向新结点
}
newp->link=NULL; //使新结点的链接域(link域)为NULL，说明该结点没有后继结点
}
//向单链表中第POS(pos=0,1,2,……)个结点之前插入元素值为X的结点，若插入成功返回1，否则返回0
int InsertPosList(struct sNode **HL,int pos,ElemType x)
{
int i=0;
struct sNode *newp;
struct sNode *cp,*ap;
if(pos<=0)
{
cout<<"pos值不正确，返回0表示插入插入失败! \n";
return 0;
}
//查找第pos个结点
cp=*HL; //使cp指向链表的第1个结点
ap=NULL;
while(cp!=NULL) //如果已到表尾，则结束查找。
{
i++; //i说明现在cp已指向了第几个结点
if(pos==i) break; //如果cp已指向了第pos个结点，则结束查找
else
{
ap=cp; //ap指向第i-1个结点
cp=cp->link; //cp指向第i个结点
}
}
//循环结束后，ap指向第pos-1个结点，cp指向第pos个结点
// 申请新结点变量
newp=(sNode*)malloc(sizeof(struct sNode));
//判断申请是否成功
if(newp==NULL)
{
cout<<"内存动态空间用完，退出运行！\n";
exit(1);
}
//把x中的数据存入新结点的数据域(data域)
newp->data=x;
newp->link=NULL;
//新结点插入到第pos个结点之前
//如果pos=1，即插入到链表的第1个结点之前，此时ap的值为NULL,cp指向第1个结点
if(ap==NULL)
{
newp->link=cp; //新结点的指针域，指向链表中原来第1个结点
*HL=newp; //链表的表指针指向新结点，新结点成为链表的第1个结点
}
else //如果pos不是第1个结点，把新结点添加到第pos结点之前
{
ap->link=newp; //使链表中原来的第pos-1个结点的指针域指向新结点
newp->link=cp; //使新结点的指针域指向链表中原来的第pos个结点
}
return 1; //插入成功，返回1
}
//向单链表的表头插入一个值为x的结点
void InsertFirstList(struct sNode **HL,ElemType x)
{
struct sNode *newp;
// 申请新结点变量
newp=(sNode*)malloc(sizeof(struct sNode));
//判断申请是否成功
if(newp==NULL)
{
cout<<"内存动态空间用完，退出运行！\n";
exit(1);
}
//把x中的数据存入新结点的数据域(data域)
newp->data=x;
//把新结点插入到表中原来第1个结点之前
newp->link=*HL; //新结点的指针域指向表中原来第1个结点
*HL=newp; //使表头指针指向新结点
}
//删除学号为i的接点
void deletevaluelist(struct sNode **HL,int x)
{
struct sNode *cp=*HL;
struct sNode *ap=NULL;
while(cp!=NULL)
{
if(cp->data.no==x)break;
ap=cp;
cp=cp->link;
}
if(ap==NULL)
{
*HL=(*HL)->link;
}else{
ap->link=cp->link;
}
free(cp);
}
//修改学号为no的学生的数据为结构体x
void updatanolist(struct sNode *HL,int no,ElemType x)
{ struct sNode *p=HL;
while(p!=NULL)
{
if(no==p->data.no)break;
p=p->link;
}
p->data=x;
}
//学号找人
ElemType getelem(struct sNode *HL,int no)
{bool flg;
struct sNode *p=HL;
while(p!=NULL)
{
if(no==p->data.no)
{
flg=true;
break;
}
p=p->link;
}
if(true==flg)
{ return p->data;
}else
{
cout<<"查无此人!";
exit(1);
}
}
//姓名找人
ElemType getelemname(struct sNode *HL,char *name_1)
{bool flg;
struct sNode *p=HL;
while(p!=NULL)
{
if(strcmp(name_1,p->data.name)==0)
{
flg=true;
break;
}
p=p->link;
}
if(true==flg)
{ return p->data;
}else
{
cout<<"查无此人!";
exit(1);
}
}
//11号功能
void copyList(struct sNode **CR,struct sNode **BC)
{
struct sNode *p=*BC;
while(p->link!=NULL)p=p->link;
p->link=*CR;
}
//12号功能
void zuhelink(struct sNode *HL1,struct sNode *HL,struct sNode **HL2)
{
struct sNode *newp;
struct sNode* newlist; //newlist一直指向新表的最后一个结点
if(HL1!=NULL)
{
newp=(sNode*)malloc(sizeof(struct sNode));
newp->data=HL1->data;
newp->link=NULL;
*HL2=newp;
newlist=*HL2;
HL1=HL1->link; //HL1指向第一个表现在需要复制的结点
while(HL1!=NULL){
newp=(sNode*)malloc(sizeof(struct sNode));
newp->data=HL1->data;
newp->link=NULL;
newlist->link=newp;
newlist=newp;
HL1=HL1->link;
}
}else{newp=(sNode*)malloc(sizeof(struct sNode));
newp->data=HL->data;
newp->link=NULL;
*HL2=newp;
newlist=*HL2;
HL=HL->link; //HL1指向第一个表现在需要复制的结点
}
while(HL!=NULL){
newp=(sNode*)malloc(sizeof(struct sNode));
newp->data=HL->data;
newp->link=NULL;
newlist->link=newp;
newlist=newp;
HL=HL->link;
}
}
/////////////////////////////////////////////////////////////////////////////////
// 函数的实现代码结束 //
/////////////////////////////////////////////////////////////////////////////////
