当前位置：文档之家› 数据结构实验报告册

数据结构实验报告册

数据结构实验报告册

数据结构实验报告册

软件学院上机实验报告

第一次实验

实验题目：

单链表

实验要求：

1、掌握单链表基本结构定义；

2、实现基本操作；

3、熟悉单链表操作特点。

实验内容：

1、线性表的抽象数据类型定义；

2、单链表存储结构的C语言定义；

3、实现基本操作：

a.初始化

b.销毁

c.取数据元素

d.插入删除

e.创建

f.单链表的始用。

4、实验结果

5、实验小结

1、抽象数据类型定义:

ADT List {

数据对象：D＝{ a i | a i∈ElemSet, i=1,2,...,n, n≥0 }

数据关系：R1＝{ |a i-1 ,a i∈D, i=2,...,n }

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

结构销毁操作

DestroyList(&L )

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

操作结果：销毁线性表 L。

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

操作结果：L为空表返回TRUE，否则返回FALSE。

ListLength( L )

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

操作结果：返回L的表长。

GetElem( L, i, &e )

初始条件：线性表L已存在，且1≤i≤ListLength (L)。

操作结果：用e 返回L中第i 个数据元素的值。

LocateElem( L, e, compare( ) )

初始条件：线性表L已存在，e为给定值，compare( )是元素判定函数。

ListTraverse(L, visit( ))

初始条件：线性表L已存在，visit() 为某个访问函数。

操作结果：依次对L的每个元素调用函数visit( )，一旦visit( )失败，则操作失败。

NextElem( L, cur_e, &next_e )

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

操作结果：若cur_e是L的数据元素且不是最后一个，用next_e返回它的后继，否则操作失败。

PriorElem( L, cur_e, &pre_e )

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

操作结果：若cur_e是L的数据元素且不是第一个，用pre_e 返回它的前驱，否则操作失败。

ListInsert(&L, i, e )

初始条件：线性表L已存在，1≤i≤LengthList(L)+1

操作结果：在L的第i个位置（第i个元素之前)插入新的数据元素e，L的长度加1。

ListDelete(&L, i, &e)

初始条件：线性表L已存在且非空，1≤i≤LengthList(L)

操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。PutElem(&L, i, e )

初始条件：线性表L已存在，且1≤i≤LengthList(L)

操作结果：L中第i个数据元素赋值为e。

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

操作结果：将L重置为空表。

2、线性表的单链表存储结构：

Typedef struct LNode {

ElemType data; // 数据域

struct Lnode *next; // 指针域

} LNode, *LinkList;

3、实现基本操作：

实验设计如下：

#include //提供assert函数，assert(NULL)则会抛出异常。

#include //提供malloc函数和free函数。

typedef enum {OK, ERROR} Status; // OK == 0

typedef int ElemType;

struct node *next;

//创建单链表头结点

Status InitList (PNode *ps)

//创建头结点

(*ps) = (PNode)malloc(sizeof(Node));

(*ps)->next = NULL;

//销毁单链表

Status DestoryList (PNode s)

PNode p_node, p_last;

while(p_node != NULL)

p_last = p_node;

p_node = p_node->next;

Status InsertList (PNode s, int i, ElemType data) //i为位序{

PNode p_node = s, p_new;

//用p_node指针找到位序为i的前一个位置 while(p_node != NULL && j < i - 1)

p_node = p_node->next;

assert(p_node);

p_new = (PNode)malloc(sizeof(Node));

p_new->data = data;

p_new->next = p_node->next;

p_node->next = p_new;

Status DeleteList (PNode s, int i, ElemType *data) {

PNode p_node = s, p_last;

//用p_node指针找到位序为i的前一个位置 while(p_node != NULL && j < i - 1)

p_node = p_node->next;

if(p_node == NULL && p_node->next == NULL) {

fprintf(stderr, "该元素不存在！");

p_last = p_node->next;

p_node->next = p_last->next;

*data = p_last->data;

//查找位序为i的结点

Status GetElem (PNode s, int i, ElemType *data)

PNode p_node = s;

//用p_node指针找到位序为i的前一个位置

while(p_node != NULL && j < i)

p_node = p_node->next;

if(p_node == NULL)

fprintf(stderr, "该元素不存在!\n"); //向错误流输入错误信息return ERROR;

*data = p_node->data;

//输出链表所有结点

Status DisplayList(PNode s)

p_node = s->next;

while(p_node != NULL)

printf("%d\t", p_node->data);

p_node = p_node->next;

putchar('\n') ;

int ListLength(PNode s)

PNode p_node = s;

assert(p_node);

while(p_node->next != NULL)

p_node = p_node->next;

PNode List_A, List_B, List_C;

int i, j, k, len_A, len_B;

int data_a, data_b;

//创建List_A 插入元素1,3,4,5,7

InitList (&List_A);

InsertList(List_A, 1, 5);

InsertList(List_A, 1, 3);

InsertList(List_A, 1, 1);

InsertList(List_A, 4, 7);

InsertList(List_A, 3, 4);

printf("List_A:\t");

DisplayList(List_A);

//创建List_B 插入元素2,4,6,8

InitList (&List_B);

InsertList(List_B, 1, 6);

InsertList(List_B, 1, 4);

InsertList(List_B, 1, 2);

InsertList(List_B, 4, 8);

printf("List_B:\t");

DisplayList(List_B);//求List_A与List_B的并集, 预期结果是: 1 2 3 4 5 6 7 8 InitList(&List_C);

len_A = ListLength (List_A);

len_B = ListLength (List_B);

GetElem(List_A, i, &data_a);

GetElem(List_B, j, &data_b);

while(i <= len_A && j <= len_B)

if(data_a < data_b)

InsertList(List_C, k, data_a);

GetElem(List_A, i, &data_a);

else if(data_a > data_b)

InsertList(List_C, k, data_b);

GetElem(List_B, j, &data_b);

{InsertList(List_C, k, data_a);

GetElem(List_A, i, &data_a);

GetElem(List_B, j, &data_b);

while(i <= len_A)

InsertList(List_C, k, data_a);

GetElem(List_A, i, &data_a);

while(j <= len_B)

InsertList(List_C, k, data_b);

GetElem(List_B, j, &data_a); }

DisplayList(List_C);

//销毁链表List_A，List_B

DestoryList(List_A);

DestoryList(List_B);

DestoryList(List_C);

4、实验结果：

6、实验小结：

1. 单链表的表长是一个隐含的值；

2. 在单链表的最后一个元素之后插入元素时，需遍历整个链表；

3. 在单链表中，元素的位序概念淡化，结点的位置概念加强。

第二次实验

实验题目：栈

实验要求：

1、了解栈后进后出的性质；

2、定义顺序栈；

3、掌握栈的基本应用；

4、学会使用递归。

实验内容：

1、抽象数据类型定义；

2、举例说明栈的后进先出；

3、顺序栈的定义，结构体定义

4、基本操作的实现

5、栈的应用：

a.说明为什么用栈；

b.栈中存放什么；

c.算法描述注释；

d.递归调用的例子。

1、抽象数据类型定义：

数据对象：

D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }

数据关系：

R1＝{ | ai-1, ai∈D, i=2,...,n }

约定an 端为栈顶，a1 端为栈底。n = 0 称为空栈。

基本操作：

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

DestroyList(&L )

初始条件：栈L 已存在。

操作结果：销毁栈L。

StackEmpty( S )

初始条件：栈S 已存在。

操作结果：若S 为空栈，则返回TRUE，否则返回FALSE。

StackLength( S )

初始条件：栈S 已存在。

操作结果：返回S 的长度(元素个数n)。

操作结果：用e 返回S 的栈顶元素(a n)。

StackTravers( S, visit ( ) )

初始条件：栈S 已存在且非空。

操作结果：从栈顶->栈底依次调用visit ( )遍历S 的每个数据元素。

一旦visit( )失败，则操作失败。

Push(&S, e) // 入栈

初始条件：栈S 已存在。

操作结果：插入元素e 为新的栈顶元素。

Pop(&S, &e) // 出栈

初始条件：栈S 已存在且非空。

操作结果：删除S 的栈顶元素，并用e返回其值。

ClearStack(&S )

初始条件：栈S 已存在。

操作结果：将S 清为空栈。

2、举例说明后进先出：

如火车的调度运行。火车一般头尾各一个车头，火车到达目的地后，需要返回时，不能扭转车身按进站时的车身排列出站，只能开动本来在车尾的车头，原本在后面的车厢成为整个车体“前”面的车厢，以与进站是相反的顺序返回。前面的车厢先进站却后出站，后面的车厢后进站却先出站。这正好类似于栈的后进先出。

3、顺序栈的定义，结构体定义

typedef struct {

SElemType *base; //栈底指针

SElemType *top; //栈顶指针

#define S_INIT_SIZE 100 // 存储空间初始分配量

#define SINCREMENT10// 存储空间分配增量

typedef struct {

SElemType *base; // 存储空间基址

SElemType *top; // 栈顶指针

int stacksize; // 已分配的存储空间，以元素为单位

4、基本操作的实现

#define MaxSize 100

typedef char ElemType;

typedef struct {

ElemType elem[MaxSize];

int top; /*栈指针*/

void InitStack(SqStack *&s){//初始化栈

s=(SqStack *)malloc(sizeof(SqStack));

void ClearStack(SqStack *&s){//销毁栈

int Push(SqStack *&s,ElemType e){//压入

if (s->top==MaxSize-1)

s->elem[s->top]=e;

int Pop(SqStack *&s,ElemType &e){//出栈

if (s->top==-1)

e=s->elem[s->top];

int GetTop(SqStack *s,ElemType &e){//获取栈顶元素if (s->top==-1)

e=s->elem[s->top];

void DispStack(SqStack *s){//打印栈中元素int i;

for (i=s->top;i>=0;i--)

printf("%c ",s->elem[i]);

int StackLength(SqStack *s){//栈长度

return(s->top+1);}

int StackEmpty(SqStack *s){//栈为空

return(s->top==-1);}

printf("(1)初始化栈s\n");

printf("(2)栈为%s\n",(StackEmpty(s)?"空":"非空"));

printf("(3)依次进栈元素a,b,c,d,e\n");

Push(s,'a');Push(s,'b');

Push(s,'c');Push(s,'d');

Push(s,'e');Push(s,'f');

printf("输出栈中元素:\n");

printf("(5)栈长度:%d\n",StackLength(s));

printf("(6)从栈顶到栈底元素:");DispStack(s);

printf("(7)出栈序列:");

while (!StackEmpty(s)){

printf("%c ",e);}

printf("(9)释放栈\n");

system("pause");}（为节省篇幅格式不甚严格）

输出结果：

实验小结：

1. 在写主函数时如果是用void main的形式那么可以不用有返回值如果是int main或|status main的话要有返回值既末尾要有return语句。

2. 分号的忘记那还是很经常的要加强注意。

3. 在定义栈的时候Num中的元素最好使用int类型的而不是char类型的。因为这样会简化char Operatecxz()的计算复杂度

4.在做表达式的计算的时候一定要注意何时入栈何时出栈。如果如栈与出栈的情况判断不清楚就无法得出答案。

第三次实验

实验题目：特殊矩阵的压缩存储

实验目的及要求：

①掌握特殊矩阵的压缩存储访问方法

②掌握稀疏矩阵的存储及访问方法

③掌握稀疏矩阵的快速转置

实验内容：

①抽象数据类型定义(数组及稀疏矩阵)

②存储结构的定义(数组及稀疏矩阵)（注：特殊矩阵采用一维数组压缩存储）

③稀疏矩阵（采用三元组顺序表进行实现，实验中包括输出稀疏矩阵转置前与后的三元组以及num数组cpot数组）。特殊矩阵（输出压缩存储后的数组，并任意给定一对i，j的值可找出相应的a[i][j]的值并输出a[i][j]的值）

1抽象数据类型定义：

2.基本操作的实现

对称矩阵压缩存储：

#include"DataStruct.h"

printf("1 NEW\n");

printf("2 SEEK\n");

printf("3 DISPLAY\n");

printf("5 EXIT\n");

int row,column;

TupNode tupnode[MAXSIZE];

int ROW,COLUMN;

printf("Please entry you chose:");

scanf("%d",&chose);

printf("Please enter the number of row:");

scanf("%d",&row);

printf("Please enter the number of column:");

scanf("%d",&column);

storage(tupnode,row,column);

printf("Please enter the ROW and COLUMN you want to seek:");

scanf("%d",&ROW);

scanf("%d",&COLUMN);

if(ROW>row||COLUMN>column)

printf("ERROR!!\n");

printf("The value IS:%d\n",SeekData(tupnode, ROW,COLUMN));

Output(tupnode,row,column);

}while(chose!=5);

实验结果：

2.对角矩阵的压缩存储：

typedef int TYPE;

#define MAXSIZE 100

//一个三元组存放一个ele[x][y]=value struct TupNode

} ;//tupnode[MAXSIZE];

//一维数组进行存储

//TupNode Array[MAXSIZE];

// 用一维数组根据矩阵中非零元素进行压缩存储

void storage(TupNode tupnod[],int m,int n)

printf("请输入主对角线上的%d个元素",m);

printf("(%d，%d):",i+1,i+1);

scanf("%d",&val);

TupNode node={i,i,val};

tupnod[LENGHT]=node;

printf("请输入主对角线上还有多少行元素：");

scanf("%d",&leave);

printf("开始输入主对角线上第%d行元素：\n",i+1);

printf("(%d，%d):",k+1,k+1+1+i);

scanf("%d",&val);

TupNode node={k,k+1+i,val};

tupnod[LENGHT]=node;

printf("其余的全是0哦，开始输入下三角中的元素：\n");

printf("开始输入主对角线上第%d行元素：\n",i+1);

printf("(%d，%d):",k+1+1+i,k+1);

scanf("%d",&val);

TupNode node={k+1+i,k,val};

tupnod[LENGHT]=node;

int SeekData(TupNode tupnod[],int x,int y)

if(tupnod[j].x==x-1&&tupnod[j].y==y-1)

a= tupnod[j].value;

void Output(TupNode tupnod[],int x,int y)

int a=SeekData(tupnod,i+1,j+1);

printf("%d\t",a);

printf("\n\n");

printf("展示性输出一维数组中的存储情况:\n");

printf("Element%d:%d\t",i+1,tupnod[i].value);

printf("1 NEW\n");

printf("2 SEEK\n");

printf("3 DISPLAY\n");

printf("5 EXIT\n");

int row,column;

TupNode tupnode[MAXSIZE];

int ROW,COLUMN;

printf("Please entry you chose:");

scanf("%d",&chose);

printf("Please enter the number of row:");

scanf("%d",&row);

storage(tupnode,row,column);

printf("Please enter the ROW and COLUMN you want to seek:");

scanf("%d",&ROW);

scanf("%d",&COLUMN);

if(ROW>row||COLUMN>column)

printf("ERROR!!\n");

printf("The value IS:%d\n",SeekData(tupnode, ROW,COLUMN));

Output(tupnode,row,column);

}while(chose!=5);

实验总结：

感受最深的一点是，以前用编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。现在编程感觉完全不同了。在编写一个程序之前，先对这个课程设计进行了一下分析，将每个要求都花了一下算法流程图，使得自己的思路更加的清晰了。

数据结构实验报告格式

《数据结构课程实验》大纲一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大的难度：（1）内容丰富，学习量大，给学习带来困难；（2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；（3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；（4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。二、《数据结构课程实验》的目的和要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。三、《数据结构课程实验》内容课程实验共18学时，要求完成以下六个题目：实习一约瑟夫环问题（2学时）

数据结构实验一顺序表问题及实验报告模板 - Copy

实验一顺序表问题【实验报告】《数据结构与算法》实验报告一学院：计算机与信息学院班级：学号：姓名：日期：程序名：一、上机实验的问题和要求：顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输出结点值。调试数据：9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到，则显示“找不到”。调试数据：第一次输入11，第二次输入3 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。调试数据：第一次insert "11" after "6" ，第二次insert "86" at "2" 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。调试数据：第一次delete the number at "2" ，第二次delete value "9" 注意：顺序表输出表现形式如下（实验报告上为截图）：顺序表：第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

(完整版)数据结构实验报告全集

数据结构实验报告全集实验一线性表基本操作和简单程序 1 ．实验目的（1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法；（2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求（1 ）认真阅读和掌握和本实验相关的教材内容。（2 ）认真阅读和掌握本章相关内容的程序。（3 ）上机运行程序。（4 ）保存和打印出程序的运行结果，并结合程序进行分析。（5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构实验报告

数据结构实验报告一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构图的遍历实验报告

实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。二、实验容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。三、实验仪器与设备计算机，Code::Blocks。四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

数据结构实验报告模板

2009级数据结构实验报告实验名称：约瑟夫问题学生姓名：李凯班级：21班班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数：主函数；结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验报告模板(验证型)

学期：2010-2011学年第一学期指导教师：杨华莉成绩：实验一顺序表的基本操作一、实验目的 1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义； 3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。二、实验要求 1．认真阅读和掌握本实验的示例程序。 2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如： i.查找并显示分数在区间[a，b）的学生信息； ii.查找并显示最高分或最低分学生信息； iii.统计不及格或及格人数及所占比例； iv.将信息表按学号、姓名或分数升序或降序排列； v.按学号顺序进行数据元素的插入； vi.删除指定学号或姓名的学生信息； vii.修改某个学生的信息； viii.其它。 4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。三、实验环境 1．台式计算机每人一台； 2．软件：Visual C++6.0 四、实验内容和实验结果

一．示例程序运行结果及说明

二．自己添加的新函数(至少2个)，要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空，无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L;

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数据结构实验报告七查找、

云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期任课教师: 实验题目: 查找算法设计与实现姓名: 王辉学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日

云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include

《数据结构实验》实验题目及实验报告模板

《数据结构实验》的实验题目及实验报告模板实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include #include #include //定义客房链表结点结构 typedef struct HNode { char roomN[7]; //客房名称 float Price; //标准价格 float PriceL; //入住价格(默认值=标准价格*80%) int Beds; //床位数Beds char State[5]; //入住状态(值域："空闲"、"入住"、"预订"，默认值为"空闲") struct HNode *next; //指针域 }Hotel, *HLink; (1)实现创建客房信息链表函数void Build(HLink &H)，输入（客房名称、标准价格、床位数），同时修改入住价格、入住状态为默认值，即入住价格=标准价格*80%，入住状态为”空闲”（提示：用strcpy()字符串拷贝函数）。为了提高程序调试效率，要求：用文件操作来输入客房信息（客房名称、标准价格、床位数）； (2)实现输出客房信息函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态； (3)函数int Find(HLink &H, char *roomN)，查找房间名称为roomN的客房。如果找到，则返回该客房在链表中的位置序号（>=1），否则返回0。提示：用strcmp()字符串比较函数； (4)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state。提示：用strcpy()字符串拷贝函数； (5)函数void Add(HLink &H)，将该链表中未入住的客房入住价格均加价20%； (6)求出入住价格最高的客房函数HLink FirstH(HLink &H)，该函数内return语句返回入住价格最高的客房结点指针，返回前将该结点在链表中删除； (7)函数void MoveK1(HLink &H, int k)，将单链表中倒数第k个结点移到第一个结点位置，注意：严禁采用先计算链表长度n再减k（即n-k）的方法；

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据：顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块：（1）主程序模块（2）无向图的邻接链表存储模块（3）深度优先遍历输出模块（4）广度优先遍历输出模块 3.模块调用图：三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析：（1）主程序模块 int main()

数据结构实验报告及心得体会

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;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;

数据结构实验报告

南京工程学院实验报告操作的函数程序清单，分别用顺序表和链表结构完成，并在首页上表明团队名称、成员及个人的工作（函数），未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、程序主要语句及作用（main函数程序清单）程序1的主要代码(附简要注释) #include #define MAXSIZE 1024 typedef int elemtype; typedef struct{ elemtype vec[MAXSIZE]; int len; }sequenlist; elemtype geti(sequenlist s, int i); elemtype deli(sequenlist *s,int i); elemtype insi(sequenlist *s,int i,int b); int main(int argc, char *argv[]){ int i,n,x; sequenlist a; printf("输入n(n>3)："); scanf("%d",&n);

数据结构实验报告

本科实验报告课程名称：数据结构（C语言版）实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号：学生姓名：指导教师：杨永强 2019 年 1 月10日

#include #include #include #define OK 1 typedef struct{//项的表示，多项式的项作为LinkList的数据元素float coef;//系数 int expn;//指数 }term,ElemType; typedef struct LNode{ //单链表节点结构 ElemType data; struct LNode *next; }LNode, *LinkList; typedef LinkList polynomial; int CreatLinkList(polynomial &P,int n){ //创建多项式P = (polynomial)malloc(sizeof(LNode)); polynomial q=P; q->next=NULL; polynomial s; for(int i = 0; i < n; i++){ s = (polynomial)malloc(sizeof(LNode)); scanf("%f%d",&(s->data.coef),&(s->data.expn)); q->next = s; s->next = NULL; q=q->next; } return OK; } 运行结果 2. void PrintfPolyn(polynomial P){ polynomial q; for(q=P->next;q;q=q->next){ if(q->data.coef!=1) printf("%g",q->data.coef);

数据结构实验报告

实验一约瑟夫问题实验学时：3学时实验类型：设计实验要求：必修一、实验目的熟练掌握线性链表的基础知识；能够使用C++或其他程序设计语言编程实现线性链表；能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题；锻炼程序设计能力。二、实验内容 M个教徒和N个非教徒在深海上遇险，必须将N个人投入海中，其余的人才能幸免于难，于是想了一个办法：所有人围成一圆圈，从第一个人开始依次报数，每数到第K个人就将他扔入大海，如此循环进行直到仅余M个人为止。设计一个算法，找出这样一个排序：使每次被扔进大海的都是非教徒。并用程序设计语言实现。三、实验原理、方法和手段使用循环单链表，将每个人作为一个结点，每个结点的指针域指向下一个人，采用循环链表的遍历对每隔N-1个结点的结点进行标记，直至标记出N个结点为止。该实验亦可用顺序表实现。四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验，有如下条件：（1）硬件：联想高性能PC机；（2）软件：VC++ 6.0、VC++.Net。六、实验步骤（1）编写循环链表构造函数Node *Create( )，使链表中每个结点的数据域值为0，并让最后一个结点的指针域指向第一个结点；（2）编写约瑟夫问题函数 Node *Move(Node *H,int n); void Insert(Node *H,int pos,int data); （5）主函数中调用Create，Move和Insert，采用具体数据计算，输出结果。七、实验程序 // stdafx.h : 标准系统包含文件的包含文件， // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include #include #include using namespace std;

数据结构实验报告 - 答案汇总

数据结构(C语言版) 实验报告

专业班级学号姓名实验1 实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序：（1）增加插入结点的功能。（2）将建立链表的方法改为头插入法。程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存

数据结构图实验报告

数据结构教程上机实验报告实验七、图算法上机实现一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct

{ char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge;

ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }

文本预览

相关文档

最新文档