#define MaxVertexNum 5 #define m 5 #define NULL 0
typedef struct node { int adjvex;
struct node *next; }JD;
typedef struct tnode { int vexdata; JD *firstarc; }TD;
typedef struct {
TD ag[m]; int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i); void creat(ALGRAPH *G) {int i,m1,j; JD *p,*p1;
printf(\scanf(\for(i=0;i
{printf(\scanf(\
printf(\ %d\scanf(\
printf(\p=(JD *)malloc(sizeof(JD)); scanf(\p->next=NULL; G->ag[i].firstarc=p; p1=p;
for(j=2 ;j<=m1;j++)
{printf(\p=(JD *)malloc(sizeof(JD)); scanf(\p->next=NULL; p1->next=p; p1=p;} } }
int visited[MaxVertexNum]; void DFSTraverse(ALGRAPH *G) { int i;
for(i=0;i
for(i=0;i
}/*DFSTraverse */
void DFS(ALGRAPH *G,int i){ JD *p;
printf(\visited[i]=1; /*标记vi已访问 */ p=G->ag[i].firstarc; /*取vi边表的头指针*/
while(p){/*依次搜索vi的邻接点vj，这里j=p->adjvex*/ if (!visited[p->adjvex])/*若vi尚未被访问 */ DFS(G,p->adjvex);/*则以Vj为出发点向纵深搜索 */ p=p->next; }
}/*DFS */
21
void main() { ALGRAPH *G;
printf(\下面以临接表存储一个图；\\n\ creat(G);
printf(\下面以深度优先遍历该图 \\n\DFSTraverse(G); getch(); }
四、 注意事项：
1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。
实验十 查找和排序
一、实验目的：
掌握运用数据结构两种基本运算查找和排序,并能通过其能解决应用问题。 二、实验要求：
1．认真阅读和掌握本实验的算法。 2．上机将本算法实现。
3．保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容：
为宿舍管理人员编写一个宿舍管理查询软件, 程序采用交互工作方式,其流程如下: 开 始
建立数据文件
数据文件按关键字（姓名、学号、房号）进行排序(任选一种) 查询菜单: (用二分查找实现以下操作) 1.按姓名查询 2.按学号查询 3.按房号查询
打印任一查询结果（可以连续操作）。 //Filename:exp10.cpp //data:6月28日 #include
#define TYPE struct student
#define LEN sizeof(struct student) typedef struct student {
float num; int room_num; char name;
struct student *next; }student; struct room {
int room_number; int count;
}room[4]={{101,0},{102,0},{201,0},{201,0}}; /* 创建一个含 n 个节点的链表 */ TYPE * creatlink(int n) { int i;
TYPE *head,*pf,*pb;
head=(TYPE*)malloc(sizeof(TYPE)); head->next=NULL; pf=head;
22
pb=head;
for(i=0;i pf=(TYPE*)malloc(sizeof(TYPE)); pf->next=NULL; printf(\请输入学生的相关信息:\\n\ printf(\学号:\ printf(\姓名:\ printf(\房间号:\ pf->room_num=(room[i/8].room_number); room[i/8].count++; pb->next=pf; pb=pf; } return(head); } TYPE * creatlink(int n); TYPE * deletelink(TYPE * head,int num); TYPE * insertlink(TYPE * head,TYPE * pi); void printlink(TYPE * head); void destroylink( TYPE * head ); void main() { TYPE *head=NULL,*pnum=NULL; int n=1,num; int x; int cord; printf(\主菜单 \\n\ printf(\学生入住 \\n\ printf(\学生退房 \\n\ printf(\学生插房 \\n\ printf(\查询学生信息 \\n\ printf(\结束程序运行 \\n\ printf(\ printf(\请输入您的选择(1, 2, 3, 4,0) \ scanf(\ /* 创建一个含 n 个节点的链表 */ switch(cord) { case 1: { printf(\请输入要入住的房间:\ scanf(\ head=creatlink(n); }break; /* 删除链表中值为 num 的节点 */ case 2: { printf(\请输入要办理退房手续学生的学号:\ scanf(\ head=deletelink(head,num); printlink(head); }break; /* 在链表中插入一个节点 */ case 3: { printf(\迟到学生插房\\n\ pnum=(TYPE *)malloc(LEN); if(pnum==NULL) printf(\没有学生入住\ printf(\请输入要插房学生的学号:\ scanf(\ printf(\请输入要插房学生的姓名:\ 23 scanf(\ head=insertlink(head,pnum); }break; case 4: { printlink(head); }break; case 0: { int exit(0); }break; } } /* 删除链表中值为 num 的节点 */ TYPE * deletelink(TYPE * head,int num) { TYPE *pf, *pb; if(head==NULL) { printf(\没有学生入住！\\n\ return NULL; } pb=head; while (pb->num!=num && pb->next!=NULL) { pf=pb; pb=pb->next; } if(pb->num==num) { if(pb==head) head=pb->next; else pf->next=pb->next; free(pb); printf(\已经成功办理退房手续\\n\ } else printf(\没有该学生!\\n\ return head; } /* 在链表中插入一个节点 */ TYPE * insertlink(TYPE * head,TYPE * pi) { TYPE *pb, *pf; pb=head; if(head==NULL) { head=pi; pi->next=NULL; } else { while((pi->num > pb->num)&&(pb->next!=NULL)) { pf=pb; pb=pb->next; } if(pi->num <= pb->num) { if(head==pb) head=pi; else 24 pf->next=pi; pi->next=pb; } else { pb->next=pi; pi->next=NULL; } } return head; } /* 打印链表中各节点信息 */ void printlink(TYPE * head) { int num; TYPE *pf; pf=head; while((pf->num!=num)&&(pf->next!=NULL)) pf=pf->next; if(pf->num==num) { printf(\该学生的信息为:\\n\ printf(\学号:%f\\n姓名:%s\\n\\nroom_num:%d\\n\ } else printf(\没有该学生！\ } /* 销毁链表, 释放动态分配的内存 */ void destroylink(TYPE * head) { TYPE *p, *q; p = head; while( p != NULL ) { q = p->next; free(p); p = q; } } 四、 注意事项： 1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 25