计算机科学与工程学院

《算法与数据结构》试验报告[一]

 

第二篇：单向环表实现约瑟夫环

《数据结构与算法设计》

实验报告

——实验1（选作）

学院：自动化学院

班级：自动化2班

学号：1320110130

姓名：赵帅

一、 实验目的：进一步加强对抽象数据类型的理解；掌握对顺

序表的各种操作；

二、实验内容

归并顺序表。

三、程序设计

1、概要设计：

（说明程序中用到的抽象数据类型定义，宏定义，主程序的流程以及各个程序模块之间的调用关系，给出主要流程图） 抽象数据类型定义：

ADT List{

数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }

基本操作：

initlist_Sq(SqList&L)

操作结果：构造一个空的线性表L。

ListEmpty( L )

初始条件：线性表L已存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSE。 ListInsert_Sq(SqList *L, inti,ElemType e)

初始条件：线性表L已存在。

操作结果：在第i个位置上插入一个元素。

Print_Sq(SqList L)

初始条件: 线性表已存在。

操作结果：输出顺序表。

}ADT List

宏定义：#define Length 10

#define LISTINCREMENT 10

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR -1

#define OVERFLOW -2

typedefint Status;

typedefintElemType;

流程图：

四、程序调试分析

（程序运行中遇到的问题与改正措施，以及对程序调试的体会与收获）

在c的环境下运行了程序，应该在c++的文件里运行；

声明变量i，在第一次使用后没有重新赋值为零，直接作为下次输入数据时的变量；

没有搞明白引用的关系；

五、用户使用说明

（说明如何使用你的程序，给出操作步骤）

双击应用程序，显示器上出现“请输入按升序排列的整数序列La=”时，输入用户想要输入的数据后并输入0做为结束标记，按“enter”结束;显示器上出现“请输入按升序排列的整数序列Lb=”时，输入用户想要输入的数据并输入0做为结束标记，按“enter”结束。即可得到想要的结果。

六、程序运行结果

（列出测试结果，包括输入和输出，最好给出2个测试结果） 1， 请输入按升序排列的整数序列La=3 4 5 6 0

请输入按升序排列的整数序列Lb=5 6 7 8 0

合并后的顺序表为：3 4 5 6 7 8

1， 2请输入按升序排列的整数序列La=1 2 3 4 5 6 7 8 9 0

请输入按升序排列的整数序列Lb=2 3 4 5 4 0

合并后的顺序表为：1 2 3 4 5 6 7 8 9

七、程序清单

（要求给函数加上注释）

/*顺序表的归并操作*/

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

#define Length 10

#define LISTINCREMENT 10

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR -1

#define OVERFLOW -2

typedefint Status;

typedefintElemType;

typedefstructlineorder{

int *elem;

int length;

intlistsize;

}SqList;

Status initlist_Sq(SqList&L) /*初始化顺序表*/

{ L.elem=(ElemType *)malloc(sizeof(ElemType)*Length); if(!L.elem) exit(OVERFLOW);

L.listsize=Length;

L.length=0;

return OK;

}

Status listempty_Sq(SqList c) /*测试顺序表是否为空*/ {

if(c.length!=0) return(FALSE);

return(TRUE);

}

Status ListInsert_Sq(SqList *L, inti,ElemType e) /*在第i个位置上插入一个元素*/

{ int j,*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) exit(OVERFLOW);

L->elem=newbase; L->listsize+=LISTINCREMENT; }

for (j=L->length ; j>=i ; --j)

L->elem[j]=L->elem[j-1];

L->elem[j]=e ; ++L->length ;

return OK;

}

void Print_Sq(SqList L) /*输出顺序表*/

{ inti;

if (listempty_Sq(L))

printf("\n It's empty!");

else

for(i=0;i<L.length;i++)

printf(" %d",L.elem[i]);

}

intLocateElem_Sq(SqList *L,ElemType e) /*返回元素e在顺序表中的位置*/

{ inti=1;

ElemType *p;

p=L->elem;

while(i<=L->length &&!(*p==e)) {i++; p++;}

if(i<=L->length) return i;

return FALSE;

}

MergeList(SqListLa,SqListLb,SqList&Lc)

{ inti=1,j=1,k=0,La_len=La.length,Lb_len=Lb.length;

ElemTypeai,bj;

while((i<=La_len)&&(j<=Lb_len))

{ ai=La.elem[i-1]; bj=Lb.elem[j-1];

if(ai<bj) {ListInsert_Sq(&Lc,++k,ai);i++;} else { if (ai==bj){ListInsert_Sq(&Lc,++k,bj);j++;i++;} else {ListInsert_Sq(&Lc,++k,bj);j++;} } } while(i<=La_len) {ai=La.elem[-1+i++];ListInsert_Sq(&Lc,++k,ai);} while(j<=Lb_len) {bj=Lb.elem[-1+j++];ListInsert_Sq(&Lc,++k,bj);} return OK;

}

void main()

{

SqListLa,Lb,Lc;

intn,m,i=0,flag1=1;

initlist_Sq(La);

initlist_Sq(Lb);

int flag2=1;

printf("\n请输入按升序排列的整数序列La=");

while (flag1) {

scanf("%d",&n);

} if(n!=0) ListInsert_Sq(&La,++i,n); else flag1=0;//标志位置零

printf("\n");

i=0;//变量置零为下次输入使用

printf("\n请输入按升序排列的整数序列Lb=");

while (flag2) { scanf("%d",&m); if(m!=0) ListInsert_Sq(&Lb,++i,m); else flag2=0;}

printf("\n");

initlist_Sq(Lc);

MergeList(La,Lb,Lc);

printf ("合并后的顺序表为："); Print_Sq(Lc);

printf("\n");

getch();

}