数据结构课程设计报告-4

1/1数据结构课程设计报告数据结构课程设计报告书

学校青岛科技高校

学号

姓名

指导老师刘勇

课程设计的名称：同学成果管理

1.问题描述：

同学成果管理是学校教务管理的重要组成部分，其处理信息量很大，该题目是对同学的成

绩管理作一个简洁的模拟，其中同学信息包括：学号、姓名与成果。成果分为课程1成果、课程2成果、课程3成果和总成果。要求设计一个简易的成果管理系统，输入各门功课的

成果后能自动求出总成果，并通过菜单选择操作方式完成下列功能：

①登记同学成果；

②②查询同学成果；

③插入同学成果；

④④删除同学成果；

⑤按总成果降序排序。

2.基本要求：

该题目涉及到单链表的各种操作，包括单链表的建立、结点的查找、插入、删除等基本运算。首先建立同学成果单链表，链表中每个结点由4个域组成，分别为：学号、姓名、成果、存放下一个结点地址的next域。然后将要求完成的四项功能写成四个函数，登记同学

成果对应建立同学单链表的功能，后三个功能分别对应单链表的查询、插入与删除三大基

本操作。

3.算法思想：

Creat函数算法思想：从0至n循环输入n个同学的三科成果，并且计算总成果。

Inquiry函数算法思想：将学号与已输入的全部学号做比较，一旦相同则输出该学号信息，否则显示没有该同学信息。

Insert函数算法思想：生成一个新节点，然后将其接到原有链表尾部。

Delete函数算法思想：通过ID找到该节点，并删去该节点。

Sort(函数算法思想：利用排序算法对每一个节点作比较并更换其在链表中的位置挨次。

4.模块划分

（1）LinkListCreat(LinkListT,intn)其功能是制造节点，录入成果。

（2）voidInquiry(LinkListT)其功能是查询与已知ID全都的同学信息并展现出来。（3）voidInsert(LinkListT,intn)其功能是添加若干个同学的成果信息。

（4）voidDelete(LinkListT)其功能是删除若干个同学的成果信息。

（5）voidSort(LNode*p)其功能是排序并展现若干个同学的成果信息。

5.数据结构：

数据类型LNode定义如下：

typedefstructLNode

{

intID;

charname[20];

intscore1;

intscore2;

intscore3;

inttotal;

structLNode*next;

}LNode,*LinkList;

6.源程序：

源代码

//main.c

#include

#include

typedefstructLNode

{

intID;

charname[20];

intscore1;

intscore2;

intscore3;

inttotal;

structLNode*next;

}LNode,*LinkList;

LinkListCreat(LinkListT,intn);voidDelete(LinkListT);

voidInquiry(LinkListT);

voidInsert(LinkListT,intn);voidSort(LNode*p);

voidInsert(LinkListT,intn)

{

inti;

LNode*r=T,*p;

while((r->next)!=NULL)

{

r=r->next;

}

for(i=0;iname);

printf("Pleaseenterthestudent'sscore1:");

scanf("%d",

printf("Pleaseenterthestudent'sscore2:");

scanf("%d",

printf("Pleaseenterthestudent'sscore3:");

scanf("%d",

p->total=p->score1+p->score2+p->score3;

printf("Thetotalscoreis%d\n",p->total);

p->next=NULL;

r->next=p;

r=p;

}

printf("\nInsertiscomplete!");

}

voidInquiry(LinkListT)

{

intid;

printf("PleaseenterthestudentIDyouwanttoinquireabout:");

scanf("%d",

LNode*p=T;

p=p->next;

while(p!=NULL)

{

if(p->ID==id)

{

printf("\nThestudentscoresinformationhasbeensuccessfullyinquired!\n");

printf("ID:%d\nName:%s\nScore1:%d\nScore2:%d\nScore3:

%d\n",p->ID,p->name,p->score1,p->score2,p->score3);

break;

}

else

{

p=p->next;

}

}

if(!p)

printf("Sorry!Didnotinquirythestudentscoresinformation!");

}

voidDelete(LinkListT)

{

intid,flag=1;

printf("PleaseenterthestudentIDyouwanttodeleteabout:");

scanf("%d",

LNode*p=T;

//LNode*q;

while((p->next)!=NULL)

{

if(p->next->ID==id)

{

//q=p->next;

p->next=p->next->next;

//deleteq;

printf("\nThestudentscoresinformationhasbeensuccessfullydeleted!\n");

flag=0;

break;

}

else

{

p=p->next;

}

}

if(flag)

printf("Sorry!Didnotdeletethestudentscoresinformationyouwanttodelete!");

}

voidSort(LNode*p)

{

LNode*r,*qian,*hou;

qian=p->next;

hou=qian->next;

while(hou)

if(qian->total>=hou->total)

{

qian=hou;

hou=hou->next;

}//if

else

{

r=p;

while(r->next->total>hou->total)

r=r->next;

qian->next=hou->next;

hou->next=r->next;

r->next=hou;

hou=qian->next;

}//else

p=p->next;

inti=1;

while(p)

{

printf("Num:%d\nID:%d\nName:%s\nScore1:%d\nScore2:%d\nScore3:%d\ntotal:%d\n\n",i,p->ID,p->name,p->score1,p->score2,p->score3,p->total);

p=p->next;

i++;

}

}

LinkListCreat(LinkListT,intn)

{

LNode*p,*r;

inti;

T=(LNode*)malloc(sizeof(LNode));

T->next=NULL;

r=T;

for(i=0;iname);

printf("Pleaseenterthestudent'sscore1:");

scanf("%d",

printf("Pleaseenterthestudent'sscore2:");

scanf("%d",

printf("Pleaseenterthestudent'sscore3:");

scanf("%d",

p->total=p->score1+p->score2+p->score3;

printf("Thetotalscoreis%d\n",p->total);

p->next=NULL;

r->next=p;

r=p;

}

returnT;

}

intmain

{

LNode*p;

intn;

while(1)

{

system("cls");

printf("StudentScoresManagement\n\n");

printf("1-Enterthestudent'sscore\n");

printf("2-Querythestudent'sscore\n");

printf("3-Insertthestudent'sscore\n");

printf("4-Deletethestudent'sscore\n");

printf("5-Sortthestudent'sscore\n");

printf("0-Exitsystem\n\n");

printf("Pleaseenteranumberselection(0-5):");

intchoice;

scanf("%d",

system("cls");

if(choice==0)

exit(0);

switch(choice)

{

case1:printf("Pleaseenterthenumberofstudentsyouwantto

enteryourstudent'sscores:");scanf("%d",

p=Creat(p,n);printf("\n\nPleaseenteryourchoice(1):");printf("1-Esc");scanf("%d",if(n)break;

case2:printf("Pleaseenterthenumberofstudentsyouwanttoqueryyourstudent'sscores:");

scanf("%d",

inti=0;while(i

#include

#include

#defineprice0.15

#definemax2

//=================================================================================================

intflag;

//=================================================================================================

typedefstructtime

{

inthour;

intmin;

}Time;

typedefstructnode

longnum;

Timereach;

Timeleave;

}CarNode;//车辆信息结点

typedefstructNODE

{

CarNode*stack[10];

inttop;

}SeqStackCar;//模拟车场

typedefstructcar

{

CarNode*data;

structcar*next;

}QueueNode;

typedefstructNode

{

QueueNode*head;

QueueNode*rear;

}LinkQueueCar;//模拟通道

//=================================================================================================

voidInitStack(SeqStackCar*s)//初始化栈

{

inti;

s->top=0;

for(i=0;istack[s->top]=NULL;

}

voidInitQueue(LinkQueueCar*Q)//初始化便道

{

Q->head=(QueueNode*)malloc(sizeof(QueueNode));

if(Q->head!=NULL)

{

Q->head->next=NULL;

Q->rear=Q->head;

return(1);

}

else

return(-1);

voidPRINT(CarNode*p,introom)//打印出场车的信息

{

intA1,A2,B1,B2;

printf("\n请输入离开的时间:/**:**/");

scanf("%d:%d",

printf("离开车辆的车牌号为:%ld\n",p->num);

printf("其到达时间为:%d:%d\n",p->reach.hour,p->reach.min);

printf("离开时间为:%d:%d\n",p->leave.hour,p->leave.min);

A1=p->reach.hour;

A2=p->reach.min;

B1=p->leave.hour;

B2=p->leave.min;

printf("应交费用为:%2.1fRMB\n",((B1-A1)*60+(B2-A2))*price);

free(p);

}

//=================================================================================================arrive

voidArrive(SeqStackCar*Enter,LinkQueueCar*W)

{

CarNode*p;

QueueNode*t;

p=(CarNode*)malloc(sizeof(CarNode));

//flushall;

printf("请输入车牌号(例:12345):\n");

scanf("%ld",

if(Enter->toptop++;

printf("车辆请停在第%d位置.\n",Enter->top);

printf("请输入到达时间:\n");

scanf("%d:%d",

Enter->stack[Enter->top]=p;

}

else//车辆已满

{

printf("该车须在便道等待！.\n");

t=(QueueNode*)malloc(sizeof(QueueNode));

t->data=p;

t->next=NULL;

W->rear->next=t;

W->rear=t;

}

printf("Returnmainmeun(1.return0.quit)\n");

scanf("%d",

switch(flag)

{

case0:

system("cls");

printf("Thanks,Welcometousenext\n");

exit(0);

case1:

system("cls");

}

}

//=================================================================================================leave

voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)

{

inti,room;

CarNode*p,*t;

QueueNode*q;

if(Enter->top>0)//盼断车场内是否有车

{

while(1)

{

printf("请输入车在车场的位置/1--%d/:\n",Enter->top);//请输入车在车场的位置

scanf("%d",

if(room>=1

}

while(Enter->top>room)//车辆离开

{

Temp->top++;

Temp->stack[Temp->top]=Enter->stack[Enter->top];

Enter->stack[Enter->top]=NULL;

Enter->top--;

}

p=Enter->stack[Enter->top];

Enter->stack[Enter->top]=NULL;

Enter->top--;

while(Temp->top>=1)

{

Enter->top++;

Enter->stack[Enter->top]=Temp->stack[Temp->top];

Temp->stack[Temp->top]=NULL;

Temp->top--;

}

PRINT(p,room);//推断通道上是否有车及车场是否已满

if((W->head!=W->rear)

t=q->data;

Enter->top++;

printf("便道的%s号车进入车场第%d位置.\n",t->num,Enter->top);

printf("请输入现在的时间/**:**/:\n");

scanf("%d:%d",

W->head->next=q->next;

if(q==W->rear)

W->rear=W->head;

Enter->stack[Enter->top]=t;

free(q);

}

else

printf("便道；里没有车.\n");

}

else

printf("车场里没有车.\n");//车场里没有车

printf("Returnmainmeun(1.return0.quit)\n");

scanf("%d",

switch(flag)

{

case0:

system("cls");

printf("Thanks,Welcometousenext\n");

exit(0);

case1:

system("cls");

}

}

//=================================================================================================show

voidList1(SeqStackCar*S)//显示存车信息

{

inti;

if(S->top>0)//推断车场内是否有车

{

printf("车场\n");

for(i=1;itop;i++)

{

printf("位置%d\到达时间:%d:%d\t号码:%ld\n",i,S->stack[i]->reach.hour,S->stack[i]->reach.min,S->stack[i]->num);

}

}

else

printf("车场里没有车.\n");

printf("Returnmainmeun(1.return0.quit)\n");

scanf("%d",

switch(flag)

{

case0:

system("cls");

printf("Thanks,Welcometousenext\n");

exit(0);

case1:

system("cls");

}

}

voidList2(LinkQueueCar*W)

{

QueueNode*p;

p=W->head->next;

if(W->head!=W->rear)

{

printf("等待车辆的号码为:");

while(p!=NULL)

{

printf("%ld\n",p->data->num);

p=p->next;

}

}

else

printf("便道里没有车.\n");

printf("Returnmainmeun(1.return0.quit)\n");

scanf("%d",

switch(flag)

{

case0:

system("cls");

printf("Thanks,Welcometousenext\n");

exit(0);

case1:

system("cls");

}

}

voidList(SeqStackCarS,LinkQueueCarW)

{

inttag;

printf("1.车场\n");

printf("2.便道\n");

printf("0.返回\n");

scanf("%d",

system("cls");

switch(tag)

{

case0:

break;

case1:

List1(

break;

case2:

List2(

break;

}

}

//=================================================================================================main

intmain

{

SeqStackCarEnter,Temp;

LinkQueueCarWait;

intch;

InitStack(

InitStack(

InitQueue(

AA:printf("停车场\n");

printf("\n1.车辆到达\n");

printf("2.车辆离开\n");

printf("3.列表显示\n");

printf("0.退出系统\n");

scanf("%d",

system("cls");

switch(flag)

{

case0:

printf("Thanks,Welcometousenext\n");

return0;

case1:

Arrive(

gotoAA;

case2:

Leave(

gotoAA;

case3:

List(Enter,Wait);

gotoAA;

}

return0;

}

//=================================================================================================

7．测试状况：

截图：

程序输出为：

TheSystemofparking

1.cararrive

2.carleave

3.showcar

0.quitsystem

ParkingLot

place:1arrivedtime:5:45number:2

place:2arrivedtime:9:14number:1

Returnmainmeun(1.return0.quit)

课程设计的名称：二叉树的基本操作的实现

1.问题描述：

?在主程序中编写一个简洁的菜单，将有关二叉树的操作?建立一棵二叉树的存储结构

?遍历一棵二叉树（包括层次遍历）

?统计二叉树叶子结点的个数

?求二叉树的深度

?子树交换

2.基本要求：

?建立一棵二叉树的存储结构

?遍历一棵二叉树（包括层次遍历）

?统计二叉树叶子结点的个数

?求二叉树的深度

?子树交换

3.算法思想：

CreatBiTree运用递归制造二叉树的每一个节点；Exchange通过递归交换左右子树；

Depth通过递归计算二叉树的深度。

InorderTraverse递归中序遍历二叉树。PreOrderTraverse递归先续遍历二叉树。PostOrderTraverse递归后续遍历二叉树。

4.模块划分：

（1）BiTreeCreatBiTree(BiTreeT)其功能是制造一颗二叉树；（2）intDepth(BiTreeT)其功能是计算一颗二叉树的深度（3）voidExchange(BiTreeT)其功能是交换左右子树

（4）voidInorderTraverse(BiTreeT)其功能是中序遍历（5）voidPreOrderTraverse(BiTreeT)其功能是前序遍历（6）voidPostOrderTraverse(BiTreeT)其功能是后序遍历

5.数据结构：

（1）数据类型BiTNode定义如下：

typedefstructBiTNode

{

chardata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

6.源程序：

源代码

//main.c

#include

#include

#include

typedefstructBiTNode

{

chardata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

voidLevelOrder(BiTreeT);

voidInorderTraverse(BiTreeT);

BiTreeCreatBiTree(BiTreeT);

intDepth(BiTreeT);

voidExchange(BiTreeT);

intNodeCount(BiTreeTi);

voidPostOrderTraverse(BiTreeT);

voidPreOrderTraverse(BiTreeT);

BiTreeCreatBiTree(BiTreeT)

{

charch;

scanf("%c",

if(ch=='#')

T=NULL;

else

{

T=(BiTNode*)malloc(sizeof(BiTNode));

if(!T)

{exit(0);printf("error");}

T->data=ch;

T->lchild=CreatBiTree(T->lchild);

T->rchild=CreatBiTree(T->rchild);

}

returnT;

}

intDepth(BiTreeT)

{

intLNum,RNum;

if(T==NULL)

{

return0;

}

else

{

LNum=Depth(T->lchild);

RNum=Depth(T->rchild);

if(LNum>RNum)

return(LNum+1);

else

return(RNum+1);

}

}

voidExchange(BiTreeT)

{

BiTNode*p;

if(T)

{

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

Exchange(T->lchild);

Exchange(T->rchild);

}

}

voidInorderTraverse(BiTreeT)

{

if(T)

{

InorderTraverse(T->lchild);

printf("%c",T->data);

InorderTraverse(T->rchild);

}

}

voidLevelOrder(BiTreeT)

{

BiTreeQueue[20],b;

intfront,rear;

front=rear=0;

if(T)

{

printf("LevelOrder:");

Queue[rear++]=T;

while(front!=rear)

{

b=Queue[front++];

printf("%2c",b->data);

if(b->lchild!=NULL)

Queue[rear++]=b->lchild;

if(b->rchild!=NULL)

Queue[rear++]=b->rchild;

}

}

}

intNodeCount(BiTreeTi)

{

if(Ti==NULL)

return0;

else

returnNodeCount(Ti->lchild)+NodeCount(Ti->rchild)+1;}

voidPostOrderTraverse(BiTreeT)

{

if(T)

{

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

printf("%c",T->data);

}

}

voidPreOrderTraverse(BiTreeT)

{

if(T)

{

printf("%c",T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

}

}

intmain

{

BiTreeT=NULL;

intchoice;

while(1)

{

printf("1-CreatBiTree.\n");

printf("2-PreOrderTraverse.\n");

printf("3-InorderTraverse.\n");

printf("4-PostOrderTraverse.\n");

printf("5-LevelOrderTraverse.\n");

printf("6-NodeCount.\n");

printf("7-BiTreeDepth.\n");

printf("8-BiTreeExchange.\n");

printf("0-exit\n");

printf("Pleaseinputthenumofyourchoice:");

scanf("%d",

fflush(stdin);

switch(choice)

{

case1:

{

T=CreatBiTree(T);

printf("CreatSucessful");

break;

}

case2:

{

PreOrderTraverse(T);

break;

}

case3:

{

InorderTraverse(T);

break;

}

case4:

{

PostOrderTraverse(T);

break;

}

case5:

{

LevelOrder(T);

break;

}

case6:

{

printf("TheNodeCountis%d",NodeCount(T));

break;

}

case7:

{

printf("Depthis%d",Depth(T));

break;

}

case8:

{

Exchange(T);

break;

}

case0:exit(0);break;

default:break;

}

if(getchar)

system("cls");

}

return0;

}

7.测试状况：

截图：

程序输出为：

Pleaseinputthenumofyourchoice:5LevelOrder:ACBED

Pleaseinputthenumofyourchoice:7Depthis3

Pleaseinputthenumofyourchoice:6

TheNodeCountis5

课程设计的名称：图的基本操作的实现

1.问题描述：

在主程序中建立一个菜单，实现图的基本操作

2.基本要求：

图的基本操作，包括：

建立图的存储结构，

实现图的深度优先搜寻遍历，

广度优先搜寻遍历

利用图的拓扑排序验证图中是否存在环

3.算法思想：

createGraph通过for循环利用链表结构录入点和边的数据。

BFS和DFS以及TopologicalSort利用递归思想实现遍历和排序。

4.模块划分：

voidcreateGraph其功能为录入点和边以及其关系的数据。

voidBFS(ALGraph

intarcs[40][40];

intvexnum,arcnum;

intkind;

}MGRAPH;

（2）数据类型LNode定义如下：typedefstruct

{

intadjvex;

structnode3*next;

}EDGENODE;

（3）数据类型LNode定义如下：typedefstruct

{

intvertex;

EDGENODE*link;

intid;

}VEXNODE;

（4）数据类型LNode定义如下：typedefstruct

{

VEXNODEadjlist[40];

intvexnum,arcnum;

intkind;

}ADJGRAPH;

6.源程序：

源代码：

#include

#include

#include

#include

#include

#include

#defineMaxsize30

#defineINFINITY99999

usingnamespacestd;

intvisited[100];

typedefstructArcNode

{

intadjvex;

structArcNode*nextarc;

}ArcNode;

typedefstructVnode

{

intdata;

ArcNode*firstarc;

}VNode;

typedefVNodeAdjLis[100];

typedefstructadjlist

{

charname[10];

intindegree;

ArcNode*firstarc;

}adjlist;

typedefstruct

{

intn,e;

intvexnum,arcnum;

adjlistver[Maxsize];

}ALGraph;

voidFindInDegree(ALGraph

ArcNode*p;

for(i=0;iadjvex==i)

indeg++;

p=p->nextarc;

}//while

}//if

}//for

G.ver[i].indegree=indeg;

}//for

}

voidTopologicalSort(ALGraph

stacks;

ArcNode*p;

FindInDegree(G);

for(i=0;inextarc)

{

if(!(--G.ver[p->adjvex].indegree))

s.push(p->adjvex);

}//for

}//while

if(countadjvex]==0)

{

DFS(G,p->adjvex);

}

p=p->nextarc;

}

}

voidBFS(ALGraph

intqueue[100],front=0,rear=0;

intvisited[100];

intw,i;

for(i=0;iadjvex]==0)

{

printf("%3d",p->adjvex);

visited[p->adjvex]=1;

rear=(rear+1)%100;

queue[rear]=p->adjvex;

}

p=p->nextarc;

}

}

cout>G.vexnum;

cout>G.arcnum;

for(inti=0;i>G.ver[i].name;

G.ver[i].indegree=0;

G.ver[i].firstarc=NULL;

}

intn,m;

charv1[10],v2[10];

for(intj=0;j>v1>>v2;

n=Locatecity(G,v1);m=Locatecity(G,v2);

ArcNode*p,*q,*t;

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=m;

p->nextarc=NULL;

if(G.ver[n].firstarc==NULL)

G.ver[n].firstarc=p;

else

{

q=G.ver[n].firstarc;

while(q->nextarc)

q=q->nextarc;

q->nextarc=p;

}

}

cout

#include

typedefstructHashTable

{

intkey;

char*data;

intcount;

}HashTable[100];

intInsertHT(HashTableha,intn,intk,intp)//将关键字插入到哈希表中{

inti,adr;

adr=k%p;

if(ha[adr].key==-1||ha[adr].key==-2)

{

ha[adr].key=k;

ha[adr].count=1;

}

else

{

i=1;//该Key发生冲突的次数（已经发生了冲突1次）

do

{

adr=(adr+1)%p;

i++;

}while(ha[adr].key!=-1

ha[adr].key=k;

ha[adr].count=i;

}

n++;

returnn;

}

voidCreatHT(HashTableha,intx,intn,intm,intp)//创建哈希表

{

inti,n1=0;

for(i=0;i<m;i++)//哈希表置初值

{

ha[i].key=-1;

ha[i].count=0;

}

for(i=0;i<n;