数据结构实验源代码.docx
《数据结构实验源代码.docx》由会员分享，可在线阅读，更多相关《数据结构实验源代码.docx（113页珍藏版）》请在冰点文库上搜索。
数据结构实验源代码
数据结构实验源代码
第二章线性表
标题：
约瑟夫环
描述：
约瑟夫环
编号为1，2，3，……，n的n个人按顺时针方向围坐一圈。
任选一个正整数作为报数上限m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
设计程序输出出列顺序。
输入：
人数n报数上限m
人员记录1（格式为：
姓名学号性别年龄班级健康状况）
人员记录2
…
人员记录n
输出：
第1次报数出列的人员记录
第2次报数出列的人员记录
…
第n次报数出列的人员记录
输入样例：
53
安弥邵10000001女28计43一般
宰觅10000002男23计79健康
顾健10000003男27计29一般
宓顽芳10000004女20计17健康
能纸垄10000005男18计11健康
输出样例：
顾健 10000003 男 27 计29 一般
安弥邵 10000001 女 28 计43 一般
能纸垄 10000005 男 18 计11 健康
宰觅 10000002 男 23 计79 健康
宓顽芳 10000004 女 20 计17 健康
提示：
循环表
#include
#include
#include//malloc（）等
#include//INT_MAX等
#include//EOF（=^Z或F6）,NULL
#include//atoi（）
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等
typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE
structstud
{
charname[12];
charnum[12];
charsex[4];
intage;
charclas[10];
charhealth[16];
};
typedefstudElemType;
typedefstructLNode
{
ElemTypedate;
structLNode*next;
}LNode,*LinkList;
voidCreateList2（LinkList&L,intn）
{//正位序（插在表尾）输入n个元素的值，建立带表头结构的单链线性表
inti;
LinkListp,q;
L=（LinkList）malloc（sizeof（LNode））;//生成头结点
q=L;
scanf（"%s%s%s%d%s%s",L->date.name,L->date.num,L->date.sex,&L->date.age,L->date.clas,L->date.health）;
for（i=1;i{
p=（LinkList）malloc（sizeof（LNode））;
scanf（"%s%s%s%d%s%s",p->date.name,p->date.num,p->date.sex,&p->date.age,p->date.clas,p->date.health）;
q->next=p;
q=q->next;
}
p->next=L;
}
voidrun（LinkListL,intm）
{
inti;
LinkListp,q;
p=L;
while（p）
{
for（i=1;i{
q=p;
p=p->next;
}
printf（"%s%s%s%d%s%s\n",p->date.name,p->date.num,p->date.sex,p->date.age,p->date.clas,p->date.health）;
q->next=p->next;
free（p）;
p=q->next;
if（p==p->next）
{
break;
}
}
printf（"%s%s%s%d%s%s",p->date.name,p->date.num,p->date.sex,p->date.age,p->date.clas,p->date.health）;
printf（"\n"）;
free（p）;//要将P释放掉，应为在前面L已经被释放掉
}
intmain（）
{
intn,m;
LinkListLa;
标题：
学生信息管理
描述：
用链式存储结构实现对一个班级学生信息管理。
设计程序求出每个人的平均成绩并按平均成绩由高到底排序后输出学生记录。
输入：
人数n
人员记录1（格式为：
学号姓名成绩1 成绩2 成绩3）
人员记录2
输出：
人员记录x 1
人员记录y 2
…
人员记录z n
输入样例：
3
1孙俪莉 76 78 89
2章子怡 72 56 67
3刘德华 56 84 90
输出样例：
1孙俪莉 76 78 89 81.00 1
3刘德华56 84 90 76.67 2
2章子怡72 56 67 65.00 3
#include
#include
#defineMaxSize1000
typedefstructStudent
{
longnum;
charname[10];
floatscore_1;
floatscore_2;
floatscore_3;
floatave_score;
longrank;
}StudentType;
typedefStudentTypeDataType;
typedefstructNode
{
DataTypedata;
structNode*next;
}SLNode;
voidListInitiate（SLNode**L）
{
if（（*L=（SLNode*）malloc（sizeof（SLNode）））==NULL）exit
（1）;
（*L）->next=NULL;
}
intListInsert（SLNode*L,inti,DataTypex）
{
SLNode*p,*q;
intj;
p=L;
j=0;
while（p->next!
=NULL&&j{
p=p->next;
j++;
}
if（j!
=i-1）
{
printf（"error"）;
return0;
}
if（（q=（SLNode*）malloc（sizeof（SLNode）））==NULL）exit
（1）;
q->data=x;
q->next=p->next;
p->next=q;
return0;
}
voidRanking（SLNode*L）
{
SLNode*p,*q,*s;
longi=0;
p=L;
while（p->next!
=NULL）
{
p=p->next;
p->data.ave_score=（p->data.score_1+p->data.score_2+p->data.score_3）/3;
i++;
}
p=L;
while（i--）
{
p=L;
s=p;
p=p->next;
q=p->next;
while（p->next!
=NULL）
{
if（p->data.ave_scoredata.ave_score）
{
if（q->next!
=NULL）
p->next=q->next;
else
p->next=NULL;
q->next=p;
s->next=q;
q=p->next;
s=s->next;
}
else//后移
{
s=p;
p=p->next;
q=p->next;
}
}
}
p=L;
i=1;
while（p->next!
=NULL）
{
p=p->next;
p->data.rank=i++;
}
}
voidDestroy（SLNode**L）
{
SLNode*p,*p1;
p=*L;
while（p!
=NULL）
{
p1=p;
p=p->next;
free（p1）;
}
*L=NULL;
}
intmain（void）
{
SLNode*L,*p;
StudentTypex[MaxSize];
intn;
inti;
ListInitiate（&L）;
p=L;
scanf（"%d",&n）;//班级人数
for（i=1;i<=n;i++）
{
scanf（"%ld",&x[i].num）;
scanf（"%s",x[i].name）;
scanf（"%f",&x[i].score_1）;
scanf（"%f",&x[i].score_2）;
scanf（"%f",&x[i].score_3）;
ListInsert（L,i,x[i]）;
}
Ranking（L）;
while（p->next!
=NULL）
{
p=p->next;
printf（"%ld",p->data.num）;
printf（"%s",p->data.name）;
printf（"%.2f",p->data.score_1）;
printf（"%.2f",p->data.score_2）;
printf（"%.2f",p->data.score_3）;
printf（"%.2f",p->data.ave_score）;
printf（"%ld\n",p->data.rank）;
}
Destroy（&L）;
return0;
}
标题：
链表上的基本操作实现
描述：
在单链表存储结构上实现基本操作：
初始化、创建、插入、删除、查找、遍历、逆置、合并运算。
输入：
线性表长度n
a1a2a3...an（数值有序，为降序）
要插入到线性表中的数字x和插入的位置i
要删除的数字的位置i
要查找的数字x
线性表长度m
b1b2...bm（数值有序，为升序）
输出：
创建的线性表a1a2...an
插入一个数字后的线性表a1a2...an+1
删除一个数字后的线性表a1a2...an
查找一个输入的数字后如果找到，输出该数字的位置i,如果没有找到，输出“没有找到x”的信息。
逆置a1a2...an后的线性表anan-1...a1
合并两个线性表后的线性表
输入样例：
请输入线性表La的长度：
6
请输入线性表La中的元素：
151310 9 85
请输入要插入到线性表La中的数字x和要插入的位置：
76
线性表La=151310 9 875（输出）
请输入要删除的数字的位置：
4
线性表La=151310 875（输出）
请输入要查找的数字：
10
找到，10在第3个位置
逆置线性表La=578101315
请输入线性表Lb的长度：
4
请输入线性表Lb中的元素：
1369
合并La和Lb后的线性表为：
1356789101315
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintElemType;
typedefintStatus;
#defineLIST_INIT_SIZE4//线性表存储空间的初始分配量
#defineLISTINCREMENT2//线性表存储空间的分配增量
structSqList
{
ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量（以sizeof（ElemType）为单位）
}Sqlist;
StatusInitList_Sq（SqList&L）
{
//操作结果：
构造一个空的顺序线性表
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）
exit（OVERFLOW）;//存储分配失败
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{
//初始条件：
顺序线性表L已存在，1≤i≤ListLength（L）+1
//操作结果：
在L中第i个位置之前插入新的数据元素e，L的长度加1
ElemType*newbase,*q,*p;
if（i<1||i>L.length+1）//i值不合法
returnERROR;
if（L.length>=L.listsize）//当前存储空间已满,增加分配
{
if（!
（newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））））
exit（OVERFLOW）;//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
q=L.elem+i-1;//q为插入位置
for（p=L.elem+L.length-1;p>=q;--p）//插入位置及之后的元素右移
{
*（p+1）=*p;
}
*q=e;//插入eListInsert（Lb,）
++L.length;//表长增1
returnOK;
}
StatusListprint_Sq（SqList&L）
{
inti;
for（i=0;i<=L.length-1;i++）
{
printf（"%d",L.elem[i]）;
}
printf（"\n"）;
returnOK;
}
StatusListDelete_Sq（SqList&L,inti,ElemType&e）
{
ElemType*p,*q;
if（（i<1）||（i>L.length））
returnERROR;
p=L.elem+i-1;
e=*p;
q=L.elem+L.length-1;
for（p=L.elem+i;p<=q;++p）
{
*（p-1）=*p;
}
--L.length;
returnOK;
}
intLocateElem_Sq（SqListL,ElemTypee）
{
inti=1;
ElemType*p,*q;
q=L.elem+L.length-1;
for（p=L.elem;p<=q;p++）
{
if（*p==e）
{
returni;
break;
}
i++;
}
returnERROR;
}
StatusListNiZhi_Sq（SqList&L）
{
ElemTypee;
ElemType*p,*q;
q=&L.elem[L.length-1];
for（p=L.elem;p{
e=*p;
*p=*q;
*q=e;
q--;
}
returnOK;
}
voidMergeList_Sq（SqListLa,SqListLb,SqList&Lc）
{
ElemType*pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=（ElemType*）malloc（Lc.listsize*sizeof（ElemType））;
if（!
Lc.elem）
exit（OVERFLOW）;
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while（pa<=pa_last&&pb<=pb_last）
{
if（*pa<=*pb）
*pc++=*pa++;
else
*pc++=*pb++;
}
while（pa<=pa_last）
*pc++=*pa++;
while（pb<=pb_last）
*pc++=*pb++;
}
intmain（）
{
SqListLa;//建立线性表La
InitList_Sq（La）;
intj,n,c,i,x;
scanf（"%d",&n）;
for（j=0;j{
scanf（"%d",&c）;
ListInsert_Sq（La,j+1,c）;
}
printf（"创建好的线性表La="）;
Listprint_Sq（La）;
scanf（"%d%d",&x,&i）;
ListInsert_Sq（La,i,x）;
printf（"插入一个元素后的线性表La="）;
Listprint_Sq（La）;
ElemTypee;
intm;
scanf（"%d",&m）;
ListDelete_Sq（La,m,e）;
printf（"删除一个元素后的线性表La="）;
Listprint_Sq（La）;
ElemTypea;
intt;
scanf（"%d",&a）;
t=LocateElem_Sq（La,a）;
if（t）
printf（"找到，%d在第%d个位置\n",a,t）;
else
printf（"没找到\n"）;
ListNiZhi_Sq（La）;
printf（"逆置后的线性表La="）;//逆置线性表La
Listprint_Sq（La）;
SqListLb,Lc;
intl,C;
InitList_Sq（Lb）;//建立线性表Lb
scanf（"%d",&l）;
for（j=0;j{
scanf（"%d",&C）;
ListInsert_Sq（Lb,j+1,C）;
}
InitList_Sq（Lc）;
MergeList_Sq（La,Lb,Lc）;
printf（"合并La和Lb后的线性表="）;//合并线性表La和Lb
Listprint_Sq（Lc）;
return0;
}
标题：
顺序表上的基本操作实现
描述：
在顺序存储结构实现基本操作：
初始化、创建、插入、删除、查找、遍历、逆置、合并运算。
输入：
请输入线性表La的长度:
n
a1a2a3...an（数值有序，为降序）
请输入要插入到线性表La中的数字x和插入的位置i:
xi
请输入要删除数字的位置:
i
请输入要查找的数字:
x
请输入线性表长度:
m
b1b2...bm（数值有序，为升序）
输出：
创建好的线性表La=a1a2...an
插入一个数字后的线性表a1a2...an+1
删除一个数字后的线性表a1a2...an
查找一个输入的数字后如果找到，输出该数字的位置i,如果没有找到，输出"没有找到x"的信息。
逆置a1a2...an后的线性表anan-1...a1
合并两个线性表后的线性表
输入样例：
请输入线性表La的长度：
5
请输入线性表La中的元素：
14111095
请输入要插入到线性表La中的数字x和插入的位置i：
84
线性表La=141110 8 95
请输入要删除的数字的位置：
4
线性表La=141110 95
请输入要查找的数字：
10
找到，10在第3个位置
逆置后的线性表La=5 9101114
请输入线性表Lb的长度：
4
请输入线性表Lb中的元素：
1369
合并La和Lb后的线性表为：
1356 99101114
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintElemType;
typedefintStatus;
#defineLIST_INIT_SIZE4//线性表存储空间的初始分配量
#defineLISTINCREMENT2//线性表存储空间的分配增量
structSqList
{
ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量（以sizeof（ElemType）为单位）
}Sqlist;
StatusInitList_Sq（SqList&L）
{
//操作结果：
构造一个空的顺序
升级会员 