实验一C

更新时间：2024-05-07 17:45:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

算法与数据结构实验报告

专业：电子信息科学与技术班级：2007050202 姓名：王力轩学号：200605020240

实验一 C++语言编程

一、实验目的：

复习、巩固C++语言上机操作的基本技能和方法，熟悉：框图（或流程图）――代码――调试――修改――运行这一基本上机过程。二、实验要求：

1．认真阅读和掌握本实验的程序。 2. 上机运行程序。

3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照操作需要，打印出文件清单和运行结果。三、实验内容：

编写一个程序实现下列目标:

1. 从键盘输入集合A、B，长度随机，以-9999表示输入结束，集合A、B的并集和交集，从

大到小输出，不能有同样的。 //Filename:exp1-1.cpp //date:04-12

#include

void intersection(int a[],int b[],int m,int n) //求交集 {

for(int i=0;i

for(int j=0;j

cout<

void Union(int a[],int b[],int m,int n) //求并集 {

int i=0,j=0; while(i

if(a[i]==b[j]) {

cout<

else if(a[i]>b[j]) {

cout<

int main() {

int a[100]={0},b[100]={0},m,n,i,j;

cout<<\请输入第一个数组中一共有多少元素:\ cin>>m;

cout<<\请输入第一个数组中的元素:\ for(i=0;i

cin>>a[i];

if(a[i]==-9999) break; }

cout<<\请输入第二个数组中一共有多少元素:\

cin>>n;

cout<<\请输入第二个数组中的元素:\ for(j=0;j

cin>>b[j];

if(b[j]==-9999) break; }

for(i=0;i

for(j=i+1;j

if(a[i]

int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } } }

for(i=0;i

for(j=i+1;j

if(b[i]

int temp; temp=b[i]; b[i]=b[j]; b[j]=temp; } } }

cout<<\交集：\

intersection(a,b,m,n); cout<

2. 分别输入圆柱体的半径和高，求其体积；输入球半径，求其表面积；输入长方体的长、宽、高，求其体积。 //Filename:exp1-2.cpp //Creator:杨成龙 //date:04-12

#include int main() { const double pi=3.1415926; double r1,h,v1,r2,area,length,wide,height,v2; cout<<\请输入圆柱体的高和半径:\ cin>>h; cin>>r1; v1=pi*r1*r1*h; cout<<\圆柱体的体积:\ cout<<\请输入球的半径:\ cin>>r2; area=4*pi*r2*r2;

}

cout<<\球的表面积:\cout<<\请输入长方体的长、宽、高:\cin>>length; cin>>wide; cin>>height;

v2=length*wide*height;

cout<<\长方体的体积:\return 0;

实验二线性表的应用

一、实验目的：

掌握线性表的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。二、实验要求：

1．认真阅读和掌握本实验的程序。 2. 上机运行程序。

3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照操作需要，打印出文件清单和运行结果。三、实验内容：

1. 运行下述程序。说明它所实现的功能。

程序如下：

//Filename:exp2-1.cpp //date:04-19 #include #include /*顺序表的定义：*/ #define ListSize 100 typedef struct

{ int data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main()

{ void CreateList(SeqList *L,int n); void PrintList(SeqList *L,int n); int LocateList(SeqList *L,int x); void InsertList(SeqList *L,int x,int i); void DeleteList(SeqList *L,int i); SeqList L; int i,x; int n=10; /*THE LENGTH OF LIST*/ L.length=0; CreateList(&L,n); /*CREAT THE LIST*/ PrintList(&L,n); /*PRINT THE LIST*/ printf(\ scanf(\ i=LocateList(&L,x); printf(\ /*顺序表查找*/ printf(\ scanf(\ printf(\ scanf(\ InsertList(&L,x,i); /*顺序表插入*/ PrintList(&L, L.length); /*打印顺序表*/ printf(\ scanf(\ DeleteList(&L,i); /*顺序表删除*/ PrintList(&L,n); getchar();/*打印顺序表*/

}

/*顺序表的建立：*/

void CreateList(SeqList *L,int n) {int i;

printf(\for(i=1;i<=n;i++)

{scanf(\}

L->length=n; }

/*顺序表的打印：*/

void PrintList(SeqList *L,int n) {int i;

printf(\for(i=1;i<=n;i++)

printf(\}

/*顺序表的查找：*/

int LocateList(SeqList *L,int x) {int i;

for(i=1;i<=10;i++) if((L->data[i])==x) {return(i); break;} return(0); }

/*顺序表的插入：*/

void InsertList(SeqList *L,int x,int i) {int j;

for(j=L->length;j>=i;j--) L->data[j+1]=L->data[j]; L->data[i]=x; L->length++; }

/*顺序表的删除：*/

void DeleteList(SeqList *L,int i) { int j;

for(j=i;j<=(L->length)-1;j++) L->data[j]=L->data[j+1]; }

2. 设计一个100位以内的长整数加减运算的程序。 //Filename:exp2-2.cpp //date:04-19

#include #include int getlength(char *ch) {

int i;

for(i=0;i<100;i++) if(ch[i]=='\\0')break; return i; }

void plusdata(int *dt,int *pdt,int k,int kk) {

int i;

for(i=0;i

dt[i]=dt[i]+pdt[i]; if(dt[i]>9) {

dt[i]-=10; dt[i+1]++; } }

if(dt[i]>9) {

dt[i]-=10; dt[i+1]++; }

if(dt[kk]!=0) i=kk;

else i=kk-1; for(;i>=0;i--) cout<

void minusdata(int *dt,int *mdt,int k,int kk,int signal) {

int i;

for(i=0;i

dt[i]=dt[i]-mdt[i]; if(dt[i]<0) {

dt[i]+=10; dt[i+1]--; } }

if(dt[i]<0) {

dt[i]+=10; dt[i+1]--; }

while(dt[kk]==0) kk--; if(signal==0) cout<<'-'; for(i=kk;i>=0;i--) cout<

void main() {

char ch1[100],ch2[100],ch0[2],ch; int data1[100],data2[100]; int i,j,k1,k2,flag=0; for(i=0;i<100;i++) {

data1[i]=0; data2[i]=0; }

cout<<\ cin>>ch1;

cout<<\ cin>>ch2;

cout<<\ cin>>ch; ch0[1]='\\0'; j=0;

while(ch1[j]=='0') j++;

for(i=0;i<99-j;i++) ch1[i]=ch1[i+j]; j=0;

while(ch2[j]=='0') j++;

for(i=0;i<99-j;i++) ch2[i]=ch2[i+j]; k1=getlength(ch1); k2=getlength(ch2); j=k1;

for(i=0;i

j--;

ch0[0]=ch1[j]; data1[i]=atoi(ch0);

if((ch1[i]<'0')||(ch1[i]>'9')) flag=1; } j=k2;

for(i=0;i

j--;

ch0[0]=ch2[j]; data2[i]=atoi(ch0);

if((ch2[i]<'0')||(ch2[i]>'9')) flag=1; }

if(flag==0) {

if(ch=='+') {

if(k1

plusdata(data2,data1,k1,k2); else

plusdata(data1,data2,k2,k1); }

if(ch=='-') {

if(k1==k2) {

while(data1[k1-1]==data2[k1-1]) k1-=1;

if(data1[k1-1]>data2[k1-1])

minusdata(data1,data2,k2,k2,1); else

minusdata(data2,data1,k2,k2,0); } else {

if(k1>k2)

minusdata(data1,data2,k2,k1,1); else

minusdata(data2,data1,k1,k2,0); } } } else

cout<<\}

四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序； 2. 输入输出要求：每四位一组，组间用逗号分隔；

3. 加和减分别用不同的程序实现； 4. 程序应考虑输入数据的符号。

实验三单链表操作

一、实验目的：

掌握握单链表的基本操作：插入、删除、查找等运算。二、实验要求：

1．认真阅读和掌握本实验的程序。 2. 上机运行程序。

3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照操作需要，打印出文件清单和运行结果。三、实验内容：

1. 运行下述程序。说明它所实现的功能。 //Filename:exp3-1.cpp //date:04-26 #include #include #include #include typedef struct node{ int data;

struct node *next; } NODE;

/******************************************/ NODE *Create(){ NODE *p,*head; int x; head=(NODE *)malloc(sizeof(NODE)); head->next=NULL; printf(\ scanf(\ while(x!=-1){ p=(NODE *)malloc(sizeof(NODE)); p->data=x; p->next=head->next; head->next=p; scanf(\ } return(head); }

/******************************************/ void Output(NODE *head){ NODE *p; p=head;

printf(\ while(p->next!=NULL){ printf(\ p=p->next; }

printf(\}

/******************************************/ int Listlen(NODE *head){ int i=0;

NODE *p=head;

while(p->next!=NULL){ i++;

p=p->next;

}

return(i); }

/******************************************/ int Get(NODE *head,int i){ int j=0;

NODE *p=head;

while(p->next&&j

p=p->next; }

if(!p->next||j>i) return(0); else return(p->data); }

/******************************************/ void Del(NODE *head,int i){ NODE *p=head; int j=0;

while(p->next&&j

p=p->next; }

if(!p->next||j>i-1) printf(\else

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

/******************************************/ void Ins(NODE *head,int i,int e){ NODE *p=head,*q; int j=0;

while(p->next&&j

p=p->next; }

if(!p->next&&j>i-1) printf(\else{

q=(NODE *)malloc(sizeof(NODE)); q->data=e;

q->next=p->next; p->next=q; } }

/******************************************/ Void main(){ NODE *head; int length; int i,element; head=Create(); Output(head);

length=Listlen(head);

printf(\ printf(\ scanf(\

element=Get(head,i);

printf(\ printf(\ scanf(\ Del(head,i);

Output(head);

printf(\ and element:\\n\ scanf(\ Ins(head,i,element); Output(head); getchar(); }

2. 编写一个程序实现下列目标:

1) 建立一个链表，用于存放成绩（整型）；

2) 输出链表中的所有数据、平均成绩和最高成绩。 //Filename:exp3-2.cpp //date:04-26

#include using namespace std; struct node { int ID; int score; node* next; };

void display(const node*); node* create(); void main() { node* head = NULL; head = create(); if(head != NULL) display(head); else cout<<\学生人数为0\}

node* create() { node *head, *temp; int n; cout<<\请输入学生人数：\ cin>>n; if(n == 0) return NULL; head = new node; temp = head; for(int i = 1; i <= n; i++) { cout<<\请输入第\个学生学号: \ cin>>temp->ID;

cout<<\请输入第\个学生成绩: \ cin>>temp->score; if(i != n) {temp->next = new node; temp = temp->next; } } temp->next = NULL; return head; }

//display函数

void display(const node* head) { int i = 1; int sum = 0; int max = head->score; cout<score; if(head->score > max) max = head->score; head = head->next; i++; } cout<<\平均分：\ cout<<\最高分：\}

四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 2. 数据个数和数据从键盘输入，每个结点包括学号和成绩。

实验四栈的基本操作

一、实验目的：

掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。二、实验要求：

1．认真阅读和掌握本实验的算法； 2．上机将本算法实现；

3．保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容：

利用栈的基本操作实现将任意一个十进制整数转化为R进制整数。算法为：

1．定义栈的顺序存取结构

2．分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3．定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈

只要Ｘ不为０重复做下列动作将Ｘ％Ｒ入栈 X=X/R

只要栈不为空重复做下列动作

栈顶出栈输出栈顶元素四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 //Filename:exp4.cpp //date:05-10

#include #define MAXSIZE 100 #include struct stack{

int data[MAXSIZE]; int top; };

void init(struct stack *s){ s->top=-1; }

int empty(struct stack *s){ if(s->top==-1) return 1; else

return 0; }

void push(struct stack *s,int i){ if(s->top==MAXSIZE-1){ printf(\ return; }

s->top++;

s->data[s->top]=i; }

int pop(struct stack *s){ if(empty(s)){

printf(\ return -1; }

return(s->data[s->top--]); }

void trans(int num){ struct stack s; int k; int(&s); while(num){ k=num; push(&s,k); num=num/16; }

while(!empty(&s)){ k=pop(&s); if(k<10)

printf(\

else

printf(\ }

printf(\}

void main(){ int num; int r;

printf(\ scanf(\ //clrscr();

printf(\ scanf(\ while(num!=-1){ trans(num);

scanf(\ } }

实验五数组的基本操作

一、实验目的：

回顾c++语言中数组的定义和基本应用；二、实验要求：

1．认真阅读和掌握本实验的程序。 2．上机运行本程序。

3．保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容：

有M个学生，学习N门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩。四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 //Filename:exp5.cpp //date:05-17 #define M 5 #define N 4 #include \void main() { int i,j;

static float score[M+1][N+1]={{78,85,83,65}, {88,91,89,93}, {72,65,54,75},{86,88,75,60}, {69,60,50,72}}; for(i=0;i

{for(j=0;j

score[i][N] /= N; }

for(j=0;j

score[M][j] /= M; //clrscr();

printf(\学生编号课程1 课程2 课程3 课程4 个人平均\\n\for(i=0;i

{ printf(\学生%d\\t\ for(j=0;j

printf(\ printf(\ }

for(j=0;j<8*(N+2);j++) printf(\

printf(\课程平均\ for(j=0;j

printf(\ printf(\ getchar(); }

阵运算

一、实验目的：

掌握三元组法存储稀疏矩阵的方法及相关的基本操作。二、实验要求：

1．认真阅读和掌握本实验的程序。 2．上机运行本程序。

3．保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容：

编写一个程序实现下列目标。 1，用三元组法存放稀疏矩阵； 2，求出矩阵相乘结果； 3，输出结果矩阵。 //Filename:exp6.cpp //date:05-24

#include #include #define OK 1 #define ERROR 0

#define MAXSIZE 100 //最多非0元素的个数 #define MAXR 50 //rpos所能处理的最大行数

#define MAXC 50 //系数矩阵相乘时，保留临时列结果的数组temp[MAXC] typedef struct NODE{ //定义稀疏矩阵结点 int i; int j; int data; } Node;

typedef struct MATRIX{ //定义稀疏矩阵（可以快速访问） int mu, nu, tu;

Node matrix[MAXSIZE+1]; int rpos[MAXR+1]; } Matrix;

int CreatSMatrix( Matrix* M ); //创建一个矩阵（由用户输入原始矩阵，转化为稀疏矩阵方式

实验六稀疏矩

储存）

int Print( Matrix M ); //打印一个稀疏矩阵

int Mul_SMatrix( Matrix M, Matrix N, Matrix *Q); //两个稀疏矩阵相乘 int main() { Matrix A1, A2, A3; //定义矩阵 CreatSMatrix( &A1 ); CreatSMatrix( &A2 ); if( A1.nu==A2.mu ) { //判断能否相乘 Mul_SMatrix( A1, A2, &A3 ); printf(\两矩阵相乘得：\\n\ Print(A3); }

system(\ return 0; }

//构建稀疏矩阵

int CreatSMatrix( Matrix* M ) { int temp, i,j;

printf(\输入矩阵的行列数：\ scanf(\ M->tu=0;

printf(\按行序输入矩阵：\\n\ for( i=1; i<=M->mu; i++) { M->rpos[i]=M->tu+1; //每计算完一行，给rpos[]赋值 for( j=1; j<=M->nu; j++) { scanf(\ if( temp ) { //非0值保存 M->matrix[M->tu+1].i= i; M->matrix[M->tu+1].j= j;

M->matrix[M->tu+1].data=temp; M->tu++; } } }

return OK; }

//打印稀疏矩阵 int Print( Matrix M) { int i;

if(M.tu==0) { printf(\空矩阵\\n\\n\ return ERROR; }

printf(\ for( i=1; i<=M.tu; i++ ) printf(\ }

//稀疏矩阵相乘

int Mul_SMatrix( Matrix M, Matrix N, Matrix *Q) {

int i,Mj; int arow, Mlim, Nlim, Mcol, Nrow; int ctemp[MAXC]; Q->tu=0;//初始化Q Q->mu=M.mu; Q->nu=M.nu; if(M.tu*N.tu!=0) { //非零矩阵 for(arow=1; arow<=M.mu; arow++) { for(i=1; i<=M.nu; i++)//清空累加器 ctemp[i]=0; Q->rpos[arow]=Q->tu+1; //给Q->rpos[]数组赋值

Mlim = arow

for( Mcol=M.rpos[arow]; Mcol

Nlim = Mj

for(i=1; i<=Q->nu; i++) {//列号对应元素不为零，赋值 if( ctemp[i] ) { if( ++Q->tu > MAXSIZE ) return 0; Q->matrix[Q->tu].i = arow; Q->matrix[Q->tu].j = i;

Q->matrix[Q->tu].data = ctemp[i]; } } } }

return 1; }

四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序；

2. 用数组存放矩阵的三元组，矩阵的行数和列数及非0数据从键盘输入； 3. 若两个矩阵不能相乘则输出“Error”

实验七二叉树1

一、实验目的：

1．进一步掌握指针变量的含义。

2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3．掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求：

1．认真阅读和掌握本实验的程序。 2．上机运行本程序。

3．保存和打印出程序的运行结果，并结合程序进行分析。

4．按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、实验内容：

编写一个程序实现下列目标。

1，根据输入的数据建立一个二叉树

2，输出二叉树（输出的结果应为树型结构） 3，输出其前序、中序和后序遍历的结果 //Filename:exp7.cpp //date:05-31

#include #include #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode;

void CreateBTNode(BTNode *&b,char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break; case')':top--;break; case',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch; p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } }

void DispBTNode(BTNode *b) { if(b!=NULL) { printf(\ if(b->lchild!=NULL||b->rchild!=NULL) { printf(\ DispBTNode(b->lchild); if(b->rchild!=NULL) printf(\ DispBTNode(b->rchild); printf(\ } } }

void PreOrder(BTNode *b) { if(b!=NULL) { printf(\ PreOrder(b->lchild); PreOrder(b->rchild); } }

void InOrder(BTNode *b) { if(b!=NULL) { InOrder(b->lchild); printf(\ InOrder(b->rchild); } }

void PostOrder(BTNode *b) { if(b!=NULL) { PostOrder(b->lchild); PostOrder(b->rchild); printf(\ } }

void main() { BTNode *b; CreateBTNode(b,\ printf(\二叉树b:\ printf(\先序遍历序列:\\n\ PreOrder(b);printf(\ printf(\中序遍历序列:\\n\ InOrder(b);printf(\ printf(\后序遍历序列:\\n\ PostOrder(b);printf(\}

四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。

实验八二叉树2

一、实验目的：

1．进一步掌握指针变量的含义。

2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3．掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求：

1．认真阅读和掌握本实验的程序。 2．上机运行本程序。

3．保存和打印出程序的运行结果，并结合程序进行分析。

4．按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、实验内容：

按先序次序输入二叉树中结点的值（一个字符），`0`表示空树，生成二叉树的二叉链表存储结构， a为指向根结点的指针。然后按中序顺序遍历二叉树。算法思想：先访问左子树,再访问根结点,最后访问右子树。四、注意事项：

1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。

**参考程序如下：

//Filename:exp8.cpp //date:06-07

#include #include #define NULL 0 typedef struct stu { char data;

struct stu *left,*right; }sn;

sn *Create(sn *a) { char ch;

scanf(\ if(ch==' ')a=NULL; else{a=(sn *)malloc(sizeof(sn)); if (!a) printf(\ a->data=ch;

a->left=Create(a->left); a->right=Create(a->right); } return(a); }

void inc(sn *b) { if(b){ inc(b->left); printf(\ inc(b->right);} }

void main( ) {

sn *t,*q; q=NULL; t=Create(q); inc(t);

printf(\//getch(); }

实验数据：abc00de0g00f000(0表示空格)

实验九图的操作

一、实验目的：

1．掌握图的基本存储方法。

2．掌握有关图的操作算法并用高级语言编程实现； 3．熟练掌握图的两种搜索路径的遍历方法。二．实验要求：

1．认真阅读和掌握本实验的算法； 2．上机将本算法实现；

3．保存和打印出程序的运行结果，并结合程序进行分析；

4．按照对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。二、实验内容：

以邻接矩阵和邻接表的方式存储连通图。然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。算法如下：

深度优先遍历的递归算法（1）深度优先遍历算法

int visited[MaxVertexNum]； //访问标志向量是全局量 void DFSTraverse(ALGraph *G)

{ //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同 int i；

for(i=0;in;i++)

visited[i]=FALSE； //标志向量初始化 for(i=0;in；i++)

if(!visited[i]) //vi未访问过

DFS(G，i)； //以vi为源点开始DFS搜索 }//DFSTraverse

（2）邻接表表示的深度优先搜索算法 void DFS(ALGraph *G，int i){

//以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p；

printf(\：％c\，G->adjlist[i].vertex)；//访问顶点vi visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针

while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex if (!visited[p->adjvex])//若vi尚未被访问

DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索 p=p->next； //找vi的下一邻接点 }

}//DFS

//文件名:exp9.cpp //date:06-21

#include #include #include #include

#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;in;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;in;i++) visited[i]=0;

for(i=0;in;i++) if(!visited[i]) DFS(G,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 */

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 #include #define NULL 0

#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;

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(\