本科实验报告
课程名称： 数据结构
实验项目：线性结构，树形结构，图的应用，查找，排序
实验地点： 行远楼A102
专业班级： 软件1334 学号：
学生姓名：
指导教师： 杨崇艳
20##年 12月 14 日
第二篇：太原理工数据结构实验报告 实验一 顺序表
实验报告
课程名称： 数据结构B
实验项目： 顺序表
实验地点： 实验楼110
专业班级：计科1301班 学号： 2013001989
学生姓名： 杨喆
指导教师： 孟亮
20##年 1 月 1 日
一、实验目的和要求
本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。
要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。
二、实验内容和原理
1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。
2．用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。
三、主要仪器设备
1.设备: PC微机;
2.实验环境: windows操作系统；VC++6.0,
四、实验结果与分析（必填）
（1）程序清单：
实验1_1:
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 80
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList *L) //构造一个空的线性表
{
L->elem=(ElemType*) malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L->elem)
return(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq(SqList *L,int i,ElemType e) //插入x
{
ElemType *q,*p,*newbase;
if (i<1 || i>L->length+1)
return ERROR;
if (L->length>=L->listsize)
{
newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
if (!newbase) return(OVERFLOW);
L->elem=newbase;
L->listsize+=LISTINCREMENT;
}
q=&(L->elem[i-1]); //插入位置
for(p=&(L->elem[L->length-1]);p>=q;--p)
*(p+1)=*p; //插入位置之后的元素后移一位
*q=e; //插入e
++L->length; //表长加一
return OK;
}
//将x插入到顺序表（递增有序）的适当位置上
Status InsertOrderList_Sq(SqList *L,ElemType x)
{
int i=1;
ElemType *q,*p;
for(i=L->length; i<=0; i++)
{
printf("%d",i);
if(x >= L->elem[i-1])
{
q=&(L->elem[i-1]);
break;
}
}
for(p=&(L->elem[L->length-1]);p>=q;--p)
*(p+1)=*p; //插入位置之后的元素后移一位
if(i >= L->length) q=&(L->elem[i]);
*q=x; //插入x
++L->length; //表长加一
return OK;
}
Status CreatList_sq(SqList &Lst)
{
int i,n;
printf("请输入你要创建的顺序表的长度");
scanf("%d",&n);
if (InitList_Sq(&Lst)==OK)
{
for(i=n;i>=0;i--) //循环输入一个顺序数组
{
if(ListInsert_Sq(&Lst,1,i)!=OK)
break;
}
printf("\n顺序表已建立:");
for (i=0;i<Lst.length;i++)
printf("%d ",Lst.elem[i]);
}
return 0;
}
Status InsertOrderList_Sq_1(SqList &Lst)
{
int i,n;
printf("\n请输入你要插入的元素");
scanf("%d",&n);
InsertOrderList_Sq(&Lst,n);
printf("\n插入后的顺序表为");
for (i=0;i<Lst.length;i++)
printf("%d ",Lst.elem[i]);
return OK;
}
Status menu_select()
{
int sn;
for(;;)
{
printf("\n请输入您要进行的功能选项");
scanf("%d",&sn);
if(sn<1||sn>3)
printf("\n\t输入错误，请重新输入\n");
else
break;
}
return sn;
}
void main()
{
SqList Lst;
int i;
printf("1.建立一个顺序表;\n2.输入你要插入的元素\n3.结束\n");
while(1)
{
switch(menu_select())
{
case 1:
CreatList_sq(Lst);
printf("\n");
break;
case 2:
InsertOrderList_Sq_1(Lst);
printf("\n");
break;
case 3:
printf("end\n");
return;
}
}
}
实验1_2:
#include<stdio.h>
#include<malloc.h>
#define Ture 1
#define False 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 80
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
Status InitList_L(LinkList &L)
{
L = (Lnode *)malloc(sizeof(Lnode));
if (L)
{
L->next = NULL;
return OK;
}
else
return ERROR;
}
Status ListInsert_Link(LinkList &L, int i, ElemType e)
{
LinkList p,q;
int j=0;
p = L;
while( p && j<i-1)
{
p = p->next;
j++;
//printf("****");
// printf("%d",j);
}
q = (Lnode *)malloc(sizeof(Lnode));
if(!q)
return OVERFLOW;
q->data = e;
q->next = p->next;
p->next = q;
//printf("%d",q->data);
return OK;
}
Status InputFormula(LinkList &L)
{
int b=0,n=0,i;
LinkList p,q;
p = L;
q = L;
printf("您要输入_____项式");
printf("\n");
scanf("%d",&n);
if(n <= 0)
{
printf("请输入正确的内容");
printf("/n");
}
printf("Input a figure according your formula:");
printf("\n");
for(i=1;i<=n;i++)
{
scanf("%d",&b);
//printf("%d",b);
ListInsert_Link(p,i,b);
}
printf("您输入的二项式系数如下，请确认\n");
for(i;i>1;i--)
{
q = q->next;
printf("%d",q->data);
printf(",");
}
printf("\n");
return OK;
}
Status AdditionA_BToClink(LinkList &A, LinkList &B, LinkList &C)
//要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
{
LinkList p=A, q=B,s=C;
int i=1,j,c;
p = p->next;
q = q->next;
while(p && q)
{
c = p->data + q->data;
ListInsert_Link(s,i,c);
p = p->next;
q = q->next;
i++;
}
while(p)
{
c = p->data;
p = p->next;
ListInsert_Link(s,i,c);
i++;
printf("%d",i);
printf("c的值%d",i);
}
while(q)
{
c = q->data;
q = q->next;
ListInsert_Link(s,i,c);
i++;
}
printf("\n得到C项式项数为：%d",i-1);
if(i<=1)
return ERROR;
printf("\n得到C项式为：");
for(i;i>1;i--)
{
s = s->next;
c = s->data;
printf("%d",c);
printf(",");
}
return OK;
}
Status menu_select()
{
int sn;
for(;;)
{
printf("\n请输入您要进行的功能选项");
scanf("%d",&sn);
if(sn<1||sn>4)
printf("\n\t输入错误，请重新输入\n");
else
break;
}
return sn;
}
void main()
{
LinkList A,B,C;
InitList_L(A);
InitList_L(B);
InitList_L(C);
printf("1.输入A项式;\n2.输入B项式;\n3.合并A，B为C;\n4.结束;\n");
while(1)
{
switch(menu_select())
{
case 1:
InputFormula(A);
printf("\n");
break;
case 2:
InputFormula(B);
printf("\n");
break;
case 3:
AdditionA_BToClink(A,B,C);
printf("\n\n");
break;
case 4:
printf("end\n");
return;
}
}
}
实验1_3
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define MAXQSIZE 100
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
typedef struct
{
QElemType *base;
int front;
int rear;
}SqQueue;
//队列
Status InitQueue(SqQueue &Q) //*************------------SqQueue &Q 引用
{
Q.base = (QElemType *)malloc(MAXQSIZE *sizeof(QElemType));
if(!Q.base)
return OVERFLOW;
Q.front = Q.rear = 0;
return OK;
}
Status EnQueue(SqQueue &Q, QElemType e)
{
if( (Q.rear+1) % MAXQSIZE == Q.front)
return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}
Status DeQueue (SqQueue &Q, QElemType &e) //*******---------这里用&是不是为了返回一个e
{
if(Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
//线性表
Status InitList_Sq(SqList& L) //构造一个空的线性表
{
L.elem=(ElemType*) malloc(100*sizeof(ElemType));
if (!L.elem)
return OVERFLOW;
L.length=0;
return OK;
}
Status ListInsert_Sq(SqList& L,int i,ElemType e) //插入x
{
ElemType *q,*p;
if (i<1 || i>L.length+1)
{
return ERROR;
}
q=&(L.elem[i-1]);
for( p=&( L.elem[L.length-1] ); p>=q; --p )
*(p+1) = *p;
*q = e;
++L.length;
return OK;
}
Status AcquireSqlist(SqQueue &Q,SqList& M,int n,int m, int s);//报数输出新线性表
void main()
{
SqQueue R;
SqList M;
InitQueue(R);
InitList_Sq(M);
int n,s,m;
printf("该圆桌有n人，从第s个人开始报数，数到m出列，\n然后从出列的下一个人重新开始报数，数到m的人又出列，\n如此重复，直到所有的人全部出列为止。\n 请输入n,s,m的值\n");
printf("n=");scanf("%d",&n);
printf("s=");scanf("%d",&s);
printf("m=");scanf("%d",&m);
AcquireSqlist(R,M,n,s,m);
}
Status AcquireSqlist(SqQueue &Q,SqList& M,int n,int s, int m)
{
int i,j=1,f,g,k=1,a;
if(n > MAXQSIZE)
return ERROR;
for(i=1;i<=n;i++)
{
EnQueue(Q,i);
}
for(i=1;i<=s;i++)
{
DeQueue(Q,a);
EnQueue(Q,a);
}
while(k<=n)
{
for(i=1; i<=m-1; i++)
{
DeQueue(Q,a);
EnQueue(Q,a);
}
DeQueue(Q,a);
ListInsert_Sq(M,j,a);
j++;
k++;
}
printf("\n您得到的顺序表为");
for(g=0;g<n;g++)
{
printf("%d ",M.elem[g]);
}
printf("\nend");
return OK;
}
（2）运行结果
实验1_1:
实验1_2：
实验1_3
四、实验感想
学习并掌握了线性结构的各类储存方式及其应用