数据结构实验
实验1（C语言补充实验）
有顺序表A和B，其元素值均按从小到大的升序排列，要求将它们合并成一个顺序表C，且C的元素也是从小到大的升序排列。
#include
main()
{
int n,m,i=0,j=0,k=0,a[5],b[5],c[10];/*必须设个m做为数组的输入的计数器，不能用i，不然进行到while时i 直接为5*/
for(m=0;m<=4;m++) scanf("%d",&a[m]);//输入数组a
for(m=0;m<=4;m++) scanf("%d",&b[m]);//输入数组b
while(i<5&&j<5)
{if(a[i] else if(a[i]>b[j]){c[k]=b[j];k++;j++;} else{c[k]=a[i];k++;i++;j++;} //使输入的两组数组中相同的数只输出一个 } if(i<5) for(n=i;n<5;n++) {c[k]=a[n];k++;} else if(j<5) for(n=j;n<5;n++) {c[k]=b[n];k++;} for(i=0;i printf("%3d",c[i]); printf("\n"); } 求A∩B #include main() { int i,j,k=0,a[5],b[5],c[5]; //A=a[5],B=b[5],A∩B=c[5] for(i=0;i<5;i++) scanf("%d",&a[i]);//输入a数组 for(i=0;i<5;i++) scanf("%d",&b[i]);//输入b数组 for(i=0;i<5;i++) {for(j=0;j<5;j++) if(a[i]==b[j]){c[k]=a[i];k++;}//当有元素重复时，只取一个放入c中 } for(i=0;i printf("%3d",c[i]); printf("\n"); } 实验2（C语言补充实验） 已知一个有序整型数组，编程将一个整型数m插入到该数组中，使得插入后的数组任然有序。#include #define N 4 main() { int i,j,m,k,a[N+1];//k为最后输出数组的长度变量 printf("请输入有序整型数组a[%d]\n",N); for(i=0;i printf("请输入整型数m\n"); scanf("%d",&m); if(a[0] {for(i=0;i { if(m==a[i]){k=N; break;}//m和数组元素相同 if(m {for(j=N;j>i;j--) a[j]=a[j-1]; a[i]=m;k=N+1;break; } }if(i==N) {k=N+1;a[N]=m;}//m比所有元素大 } if(a[0]>a[1])//递减有序数组 {for(i=0;i { if(m==a[i]) {k=N;break;}//m和数组元素相同 if(m>a[i])//m比当前元素大，数组右移 {for(j=N;j>i;j--) a[j]=a[j-1]; a[i]=m;k=N+1;break; } } for(i=0;i printf("%3d",a[i]); printf("\n"); } 补充实验 已知线性表LA和LB中的数据元素按值非递减有序排序，现要求将LA和LB归并为一个新的线性表LC，且LC 中的数据元素仍按值非递减有序排列。 #include int Getelem(int a[], int t);//声明得到数组元素函数 void ListInsert(int b[], int p,int q );//声明插入数组函数 main() { int m,i=0,j=0,k=0,LA[5],LB[5],LC[10],ai,bj; for(m=0;m<5;m++) scanf("%d",&LA[m]);//输入La数组 for(m=0;m<5;m++) scanf("%d",&LB[m]);//输入Lb数组 while(i<5&&j<5) { ai=Getelem(LA,i);//通过函数得到数组元素 bj=Getelem(LB,j); if(ai { ListInsert(LC,k++,ai); i++;//将较小的元素赋给新的数组 } else if(ai>bj) { ListInsert(LC,k++,bj); j++;//将较小的元素赋给新的数组 } else//相同的元素只要取一个 { ListInsert(LC,k++,ai); i++; j++; } } while(i<5)//此时LB的元素都比LA小 { ai=Getelem(LA,i); ListInsert(LC,k++,ai); i++;//直接将LA整体插入LC } while(j<5)//此时LA的元素都比LB小 { bj=Getelem(LB,j); ListInsert(LC,k++,bj); j++;//直接将LA整体插入LC } for(i=0;i printf("%3d",LC[i]); printf("\n"); } int Getelem(int a[],int t) {return a[t];} void ListInsert(int b[],int p,int q) {b[p]=q;} 实验3 输入n个整型数据，用链表的方法存储这些数据并输出。 #include #include typedef struct LNode { int date; struct LNode *next; }LNode ,*LinkList;//此指针变量就是指LNode类型的结构体 void CreatList(LinkList *L,int n)//顺序输入n个元素的值，建立头结点L { int i; LinkList p,S;//S为暂存结点 (*L)=(LinkList)malloc(sizeof(LNode)); S=(LinkList)malloc(sizeof(LNode)); (*L)->next=NULL; S=(*L); for(i=0;i scanf("%d",&p->date); p->next=S->next; S->next=p; S=S->next;//S移向下一个 } } void PRINTF(LinkList L)//输出函数 { LinkList q; q=L->next; while(q){printf("%4d",q->date);q=q->next; } printf("\n"); } main() { LinkList M; int n;//n为插入数的个数 printf("请输入插入数的个数\n"); scanf("%d",&n); printf("请输入这%d个数\n",n); CreatList( &M,n); printf("该线性表顺序输出为\n"); PRINTF(M); } 实验4 约瑟夫环算法 /*约瑟夫环问题是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。*/ #include #include typedef struct Node { int date; struct Node *next; }LinkList; LinkList *CreatList(int n)//创建n个数的循环链表 { int i=1; LinkList *p,*q,*head; p=(LinkList*)malloc(sizeof(LinkList)); p->date=i; head=p; for(i=2;i<=n;i++) { p->next=q; p=q; } p->next=head; return head; } void Print(LinkList *L) //输出n个数 { LinkList *p; p=L; printf("%d ",p->date); p=p->next; while(p!=L) { printf("%d ",p->date);p=p->next;} printf("\n"); } void FreeNode(LinkList *L,int k,int m) //输出每个第m的数{ int i,j; LinkList *p,*q; p=L; for(i=1;i { q=p; p=p->next; } while(p->next!=p) { for(j=1;j { q=p; p=p->next; } printf("%d ",p->date); q->next=p->next; p=p->next; } printf("%d ",p->date); } void main() { LinkList *L; int n,k,m; printf("请输入人数，从第几个人数，数到几：n k m=\n"); L=CreatList(n); printf("n个数分别为"); Print(L); printf("每次出列数为"); FreeNode(L,k,m); printf("\n"); } 实验5 利用栈，判断输入的括号序列是否配对，若配对则将序列输出，否则输出ERROR。#include #include #define STACK_INIT_SIZE 100 typedef struct SqStack{ char *base; //在栈构造之前和销毁之后，base的值为NULL char *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单元 }SqStack; //建立栈 void InitStack(SqStack *S) //初始化栈 { (*S).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); (*S).top=(*S).base; (*S).stacksize = STACK_INIT_SIZE; //初始存储容量 } int StackEmpty(SqStack S) //判断栈是否为空 { if(S.top==S.base) return 1;//栈为空的条件的栈顶=栈尾 else return 0; } void Push(SqStack *S,char e) //插入元素e为第一个栈顶新的元素 { *((*S).top)=e; (*S).top++; } void Pop(SqStack *S,char *e) //删除S1的栈顶元素,并输出e { (*S).top--; *e=*((*S).top); } main() char a,e; //a为输入元素 SqStack p; InitStack(&p); //初始化栈p printf("请输入需要判断的括号\n"); a=getchar(); //输入a while(a!='\n') { //printf("+++%c\n",a); if(a=='('||a=='['||a=='{') Push(&p,a); else if(a==')'||a==']'||a=='}') { Pop(&p,&e); i=0; //printf("*****%c\n",e); switch(e) { case '(': if(a==')') i=1; break; case '[': if(a==']') i=1; break; case '{': if(a=='}') i=1; break;/*default不能用来判断字符*/ } //printf("$$$%d\n",i); if(i==0)break; } a=getchar(); } if(!StackEmpty(p)) printf("括号不匹配\n"); //栈不为空 else if(StackEmpty(p)) printf("括号匹配\n"); //栈为空 } 实验6 利用循环队列模拟舞伴配对问题：在舞会上，男女各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对的者等待下一轮舞曲，舞曲结束后，按照先配对的先分开进入各自的队列。假设初始男女人数及舞会的轮数由参数给出，模拟上述舞伴配对问题。输出第n个舞曲男女配对的序列。 #include #include #include #define SIZE 100 //最大队列长度 typedef struct NameQueue char GirlName[10]; }NameQueue; //定义名字结构体 typedef struct SqQueue { NameQueue *base; //初始化动态分配空间 int front; int rear; }SqQueue; //定义循环队列 void InitQueue(SqQueue *Q) //构造一个空队列 { Q->base=(NameQueue *)malloc(SIZE*sizeof(NameQueue)); Q->front=Q->rear=0; } int QueueEmpty(SqQueue Q) //判断队列是否为空 { if (Q.rear==Q.front) return 1; else return 0; } void EnQueue(SqQueue *Q,NameQueue e) //插入元素e为Q的新的队尾元素 { if ((Q->rear+1)%SIZE==Q->front) //队满 exit(0); else Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%SIZE; //入队 } void DeQueue(SqQueue *Q,NameQueue *e)// 删除Q的队头元素, 并用e返回其值 { if (Q->rear==Q->front) //队满 exit(0); else (*e)=Q->base[Q->front]; Q->front=(Q->front+1)%SIZE; //出队 } void main() { int i,time,BoyNum,GirlNum; //time为舞会曲数,BoyNum为男生人数，Girl为女生人数char name[10]; //name字符串数组储存姓名 SqQueue Boy,Girl,Dancer; //定义Boy,Girl,Dancer三个队列 NameQueue e1,e2; printf("请输入舞会曲数,男生人数,女生人数\n"); InitQueue(&Boy); InitQueue(&Girl); InitQueue(&Dancer); getchar(); printf("输入男生姓名\n"); for(i=1;i<=BoyNum;i++) { gets(e1.BoyName); //输入男生姓名 strcpy(e1.GirlName," "); EnQueue(&Boy,e1); } printf("输入女生姓名\n"); for(i=1;i<=GirlNum;i++) { gets(e1.GirlName); //输入女生姓名 strcpy(e1.BoyName," "); EnQueue(&Girl,e1); } printf("***舞会配对顺序***\n"); for(i=1;i<=time;i++) { printf("第%d配对结果为\n",i); while(!QueueEmpty(Boy)&&!QueueEmpty(Girl)) { DeQueue(&Boy,&e1); strcpy(name,e1.BoyName); //用name字符串存储男生姓名 DeQueue(&Girl,&e1); strcpy(e1.BoyName,name); //此时e1里存有男生和女生姓名 EnQueue(&Dancer,e1); printf(" %s--%s ",e1.BoyName,e1.GirlName); } while(!QueueEmpty(Dancer)) //当舞会配对完成输出舞会队列里的男女姓名{ DeQueue(&Dancer,&e1); strcpy(e2.BoyName,e1.BoyName); strcpy(e2.GirlName," "); EnQueue(&Boy,e2); strcpy(e1.BoyName," "); EnQueue(&Girl,e1); } printf("\n"); } } 实验7 已知一个M×N的稀疏矩阵A，用三元组的方法压缩存储该矩阵，输出该三元组及矩阵转置后的三元组。（用跳着找，顺着存方法） #include #define M 10 //数组A的行数 #define N 10 //数组A的列数 #define SIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //该非零元的行下标和列下标 int e; //该非零元素的值 }Three; //(三元组) typedef struct { Three data[SIZE+1]; //非零元三元组,data[0]不用 int mu,nu,tu; //矩阵的行数，列数和非零元个数 }TSMatrix;//（矩阵） void zhuanzhi(TSMatrix A,TSMatrix *T) //采用三元组表存储表示，求稀疏矩阵A的转置矩阵T { int p,q,col; // p为现在三元组下标，q为原三元组下标,col列数T->mu=A.nu; // 矩阵T的行数等于矩阵A的列数 T->nu=A.mu; // 矩阵T的列数等于矩阵A的行数 T->tu=A.tu; // 矩阵T的非零元素数等于矩阵A的非零元素数 if(A.tu) // 把A中每一个非零元素转换到T中相应位置 { q=0; for(col=0;col<=A.nu;col++) // 按列号作扫描，做col趟 for(p=0;p<=A.tu;p++) // 在数据中找列号为col的三元组 if(A.data[p].j == col) // 转置后的列数与col进行比较 { T->data[q].i= col; // 新三元组的行号 T->data[q].j= A.data[p].i; // 新三元组的列号 T->data[q].e= A.data[p].e; // 新三元组的值 q++; } } } void Create(TSMatrix *A) // 创建一个稀疏矩阵A { int a[M][N],i,j, k=0; // k为三元组的下标 int m,n; // m、n为A矩阵的行、列数 printf("请输入矩阵的行、列数:\n"); scanf("%d %d",&m,&n); printf("请输入数组a:\n"); for(i=0;i for(j=0;j scanf("%d",&a[i][j]); for(i=0;i if(a[i][j]!=0) // 找出非零元素 { A->data[k].i=i+1; // 该元素的行位置赋给三元组的i A->data[k].j=j+1; // 该元素的列位置赋给三元组的j A->data[k].e=a[i][j]; // 该元素的值赋给三元组的e k++; // 三元组下标加一 } A->mu=m;A->nu=n;A->tu=k; // 给稀疏矩阵的行数，列数和非零元个数赋值 } void PRINT(TSMatrix A) { int i; //k为计数器 for(i=0;i printf("%4d%4d%4d\n",A.data[i].i,A.data[i].j,A.data[i].e); // 依次输出三元组 printf("\n"); } main() { TSMatrix A,T; Create(&A); // 创建一个稀疏矩阵A printf("A的三元组表(下标从1开始):\n"); printf(" i j e\n"); PRINT(A); zhuanzhi(A,&T); // 采用三元组表存储表示，求稀疏矩阵A的转置矩阵T printf("转置后的三元组表(下标从1开始):\n"); printf(" i j e\n"); PRINT(T); } 实验8 已知一个M×N的稀疏矩阵A，用三元组的方法压缩存储该矩阵，输出该三元组及矩阵转置后的三元组。（用顺着找，跳着存方法） #include #define M 10 //数组A的行数 #define N 10 //数组A的列数 #define SIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //该非零元的行下标和列下标 int e; //该非零元素的值 }Triple; //(三元组) typedef struct { Triple data[SIZE+1]; //非零元三元组,data[0]不用 int mu,nu,tu; //矩阵的行数，列数和非零元个数 void FastTransposeSMatrix(TSMatrix A,TSMatrix *T) //采用三元组表存储表示，求稀疏矩阵A的转置矩阵T { int t,p,q,col,num[N],cpot[N]; T->mu=A.nu; T->nu=A.mu; T->tu=A.tu; if(T->tu) { for(col=0;col num[col]=0; for(t=0;t num[A.data[t].j]++; //求A中每一列含非零元个数 cpot[0]=0; //求第col列中第一个非零元在新的三元组里面的序号for(col=1;col cpot[col]=cpot[col-1]+num[col-1]; /*num[col]表示矩阵A中非零元的个数 cpot[col]表示A中第col列的第一个非零元在新的三元组中的位置*/ for(p=0;p { col=A.data[p].j; //把A中每一列的非零元赋给col q=cpot[col]; T->data[q].i=col; T->data[q].j=A.data[p].i; T->data[q].e=A.data[p].e; cpot[col]++; } } } void Create(TSMatrix *A) // 创建一个稀疏矩阵A { int a[M][N],i,j, k=0; // k为三元组的下标 int m,n; // m、n为M矩阵的行、列数 printf("请输入矩阵的行、列数:\n"); scanf("%d %d",&m,&n); printf("请输入行，列的数组a:\n"); for(i=0;i for(j=0;j scanf("%d",&a[i][j]); for(i=0;i for(j=0;j if(a[i][j]!=0) // 找出非零元素 { A->data[k].i=i; // 该元素的行下标赋给三元组的i A->data[k].j=j; // 该元素的列下标赋给三元组的j A->data[k].e=a[i][j]; // 该元素的值赋给三元组的e k++; // 三元组下标加一 A->mu=m;A->nu=n;A->tu=k; // 给稀疏矩阵的行数，列数和非零元个数赋值} void PRINT(TSMatrix A) { int k; for(k=0;k printf("%4d%4d%4d\n",A.data[k].i,A.data[k].j,A.data[k].e); // 依次输出三元组 printf("\n"); } main() { TSMatrix A,T; Create(&A); // 创建一个稀疏矩阵A printf("A的三元组表:\n"); printf(" i j e\n"); PRINT(A); FastTransposeSMatrix(A,&T); // 采用三元组表存储表示，求稀疏矩阵A的转置矩阵T printf("转置后的三元组表:\n"); printf(" i j e\n"); PRINT(T); } 实验9 已知有10个字符型数据，试将这十个字符按照从上到下、从左到右的次序建立一个二叉链表，并依次输出这10个字符。 （提示：链表存储二叉树通常用具有两个指针域的链表作为二叉树的存储结构，其中每个结点由数据域Data、左指针域和右指针域组成。两个指针域分别指向该结点的左、右孩子。若某结点没有左孩子或右孩子，则对应的指针域为空。最后，还需要一个链表的头指针指向根结点。）先序、后序遍历并输出（用递归方法）。 #include #include typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; //左右孩子指针 }BiTNode,*BiTree; BiTree CreateBiTree(BiTree T) { char a; //scanf("%c",&a); a=getchar(); if(a=='0') T=NULL; { T=(BiTree)malloc(sizeof(BiTNode)); T->data=a; //生成跟结点 T->lchild=CreateBiTree(T->lchild); //构造左子树 T->rchild=CreateBiTree(T->rchild); //构造右子树} return T; } void PreOrder(BiTree T) //先序遍历{ if(T) { printf("%c ",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T) //中序遍历{ if(T) { InOrder(T->lchild); printf("%c ",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T) //后序遍历{ if(T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ",T->data); } } void main() { BiTree L; printf("请输入二叉树序列\n"); L=(BiTree)malloc(sizeof(BiTNode)); L=CreateBiTree(L); printf("\n递归方法\n"); PreOrder(L); printf("\n"); printf("中序遍历二叉树序列为\n"); InOrder(L); printf("\n"); printf("后序遍历二叉树序列为\n"); PostOrder(L); printf("\n"); } 实验11 将一个已知二叉树，中序遍历并输出（用非递归方法）。 #include #include typedef struct BiTNode { char data; int flag; //标志变量 struct BiTNode *lchild, *rchild; //左右孩子指针 }BiTNode,*BiTree; #define SIZE 100 typedef struct SqStack { BiTree *base; //在栈构造之前和销毁之后，base的值为NULL BiTree *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单元 }SqStack; //建立栈 void InitStack(SqStack *S) //初始化栈 { S->base=(BiTree *)malloc(SIZE *sizeof(BiTNode)); S->top=S->base; S->stacksize = SIZE; //初始存储容量 } int StackEmpty(SqStack S) //判断栈是否为空 { if(S.top==S.base) return 1; //栈为空的条件的栈顶=栈尾 else return 0; } void Push(SqStack *S,BiTree e) //插入元素e为第一个栈顶新的元素 { *((*S).top)=e; void Pop(SqStack *S,BiTree *e) //删除S1的栈顶元素,并输出e { (*S).top--; *e=*((*S).top); } BiTree CreateBiTree(BiTree T) { char a; //scanf("%c",&a); a=getchar(); if(a=='0') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); T->data=a; //生成跟结点T->lchild=CreateBiTree(T->lchild); //构造左子树 T->rchild=CreateBiTree(T->rchild); //构造右子树 } return T; } void PreOrder(BiTree T) //先序非递归 { BiTree p; SqStack S; InitStack(&S); p=(BiTree)malloc(sizeof(BiTNode)); p=T; while(p||!StackEmpty(S)) { if(p) { printf("%c ",p->data); Push(&S,p); //预留p指针在栈中 p=p->lchild; } else { Pop(&S,&p); p=p->rchild; //左子树为空, 进右子树 } } } BiTree p; SqStack S; InitStack(&S); p=(BiTree)malloc(sizeof(BiTNode)); p=T; while(p||!StackEmpty(S)) { if(p) { Push(&S,p); //预留p指针在栈中 p=p->lchild; } else { Pop(&S,&p); printf("%c ",p->data); p=p->rchild; // 左子树为空, 进右子树 } } } void PostOrder(BiTree T) //后序非递归 { BiTree p; SqStack S; InitStack(&S); p=(BiTree)malloc(sizeof(BiTNode)); p=T; while(p||!StackEmpty(S)) { if(p) { p->flag=0; Push(&S,p); //将P指针以及flag压入栈 p=p->lchild; } else { Pop(&S,&p); if(p->flag==0) { p->flag=1; Push(&S,p); //再将P指针以及flag压入栈 p=p->rchild; } { printf("%c ",p->data); p=NULL;//把p赋为空是表示当前结点处理完毕需要从栈中弹出下个结点} } } } void main() { BiTree L; printf("请输入二叉树序列\n"); L=(BiTree)malloc(sizeof(BiTNode)); L=CreateBiTree(L); printf("\n非递归方法\n"); printf("先序遍历二叉树序列为\n"); PreOrder(L); printf("\n"); printf("中序遍历二叉树序列为\n"); InOrder(L); printf("\n"); printf("后序遍历二叉树序列为\n"); PostOrder(L); printf("\n"); } 实验12 将一个图用邻接矩阵的形式表示并输出，并输出每个顶点的度。 #include #define MAX 20 typedef struct ArcCell { int vexs[MAX]; //顶点向量 int arcs[MAX][MAX]; //邻接矩阵的元素and边 int vexnum,arcnum; //当前顶点数和边数 }MGraph; //邻接矩阵 CreateDG(MGraph *G) //构造有向图G { int i,k,j; printf("输入顶点和边数\n"); scanf("%d %d",&(G->vexnum),&(G->arcnum)); for(i=0;i printf("构造的顶点序列为\n"); for(i=0;i printf("%3d",G->vexs[i]); printf("\n"); for(i=0;i for(j=0;j G->arcs[i][j]=0; for(k=0;k { printf("输入一条边依附的顶点\n"); scanf("%d %d",&i,&j); G->arcs[i][j]=1; //有弧就为1 } } CreateUDG(MGraph *G) //构造无向图G { int i,k,j; printf("输入顶点和边数\n"); scanf("%d %d",&(G->vexnum),&(G->arcnum)); for(i=0;i G->vexs[i]=i; //构造顶点向量，用for循环给每个顶点向量赋值printf("构造的顶点序列为\n"); for(i=0;i printf("%3d",G->vexs[i]); printf("\n"); for(i=0;i for(j=0;j G->arcs[i][j]=0; for(k=0;k { printf("输入一条边依附的顶点\n"); scanf("%d %d",&i,&j); G->arcs[i][j]=G->arcs[j][i]=1; //对称矩阵的特征 } } void Output(MGraph G) //输出函数 { int i,j; for(i=0;i { for(j=0;j 上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.wendangku.net/doc/962198807.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 《数据结构》实验报告 实验序号：1 实验项目名称：概论 附源程序清单： 1. #include 2. #include 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 天津科技大学 2015—2016学年第2学期数据结构实验任务书 课程名称：数据结构实验学时： 2 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的： 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 实验内容： 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 实验提示： 学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int score; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 链表的定义： typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 以班为单位实验周周五上传源程序和实验报告。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如07081211薛力.rar。 精品文档数据结构 实 验 报 告 目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 一、实验目的 1.使学生熟悉最短路径算法实现。 2.掌握带权图的存储结构和处理方法。 二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； 2.软件：DOS或Windows操作系统 +Turbo c; 三、实验要求 1.能够独立完成带权图的存储和最短路径的生成。 四、实验内容 1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。 2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。 五、代码如下 #include 图的实验报告 班级：电子091 学号：0908140620 姓名：何洁编号：19 （一）实验要求 创建一个图。能够实现图的输入，插入顶点和边，利用队列进行深度和广度遍历。（二）需求分析 功能：1，输入图的信息；2，插入一个顶点；3插入一个边；4，删除一个顶点；5，删除一个边；6，深度优先遍历；7，广度优先遍历；8退出。 （三）概要设计 本程序采用的是模板类，抽象数据类型有：T,E。 类： template 计10--数据结构专题实验rev2
数据结构实验十一：图实验
数据结构实验
数据结构实验报告图实验
数据结构实验报告
数据结构实验
数据结构实验报告图实验
数据结构实验一 实验报告
数据结构实验报告
数据结构实验
数据结构实验1
数据结构实验报告(图)
数据结构图实验报告
数据结构实验报告及心得体会
数据结构实验1
数据结构实验—图实验报告
数据结构实验一 实验报告
数据结构实验十
数据结构--图的实验报告