数据结构上机实验白雷 - 图文

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

《计算机软件技术基础》

实验报告I—数据结构

班号： 0312207 学号： 031210335 姓名： 白雷

Email： leibai@nuaa.edu.cn 签名：

南京航空航天大学 2014年11月5日

第 1 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

目录

实验一：顺序表的定义、创建、插入和删除操作，将数据元素显示出来。………………………3

实验二：单链表的定义、创建、插入和删除操作，将数据元素显示出

来。………………………6

实验三：二叉树的链式存储结构的数据结构定义、创建、先序/中序/后序遍历，并将结

果序列输出。………………………10

实验四：图的邻接表数据结构的定义、创建；图的深度优先遍历、广度优先遍历。………………………14

实验五：邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍

历。………………………18

第 2 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

实验一 顺序表

一、简述每一部分的对象、目的和要求；

1、 对象：顺序表。

2、目的：将数据以顺序表形式存储并且进行各种操作。

3、要求：顺序表的定义、创建、插入和删除操作，将数据元素显示出来。

二、画出算法(程序)的流程图

图 一.1顺序表主函数流程图

图 一.2插入数据函数流程图

第 3 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

图 一.3删除数据函数流程图

三、程序的数据输入要求和输出结果的特点与结论

线性表元素通过调用函数 Insert_SeqList()来输入int型数据和位置i （int型）输入数据类型；在输入前必须对线性表进行初始化。线性表数据输入完成后在主函数有for循环对全表进行遍历并且显示全部数据。同时可利用 delete_seqlist（）函数输入位置i（int型）删除指定位置的元素。

结论： 线性表储存结构中各个元素可以通过位置下标查找，可以方便快速地找到所需元素。但是该结构占用连续的存储空间， 插入删除等修改操作运行时间复杂。 四、附源程序清单

#include #include //#include

#define MAXSIZE 1024

#define seqlist struct listtype seqlist

{ int data[MAXSIZE]; int last;

};//定义一个数据结构

seqlist* init_seqlist() { seqlist* L; int num,i=0; L=(seqlist*)malloc(sizeof(seqlist)); L->last=-1;

printf(\input the data of list (if(-1) stop)\

scanf(\ while(num!=-1)

{ if(L->last>=MAXSIZE)

{ printf(\ return L;} L->last++;

L->data[L->last]=num;

printf(\stop) \

scanf(\ }

return L;

}//顺序表初始化

seqlist* Insert_seqlist(seqlist*L,int i,int x) { int j;

if(L->last==MAXSIZE) {printf(\is too much and the space is small!\\n\L;}

if(i<0||i>L->last+1) {printf(\place is wrong!\\n\

if(i==L->last+1) L->data[L->last+1]=x; else {for(j=L->last;j>=i-1;j--) L->data[j+1]=L->data[j];

第 4 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

L->data[i-1]=x;}

L->last++;

printf(\插入成功!\\n\\n\ return L;

}//插入操作 2 5 0 0 99 2 99 5 00

/*void selectsort(seqlist*L,int m) { int i,j,p,t;

for(i=0;ilast[m];i++) { p=i;

for(j=i+1;jlast[m]+1;j++) if(L->data[j]data[p]) p=j; if(p!=i) { t=L->data[p]; L->data[p]=L->data[i]; L->data[i]=t;} }

//L=sdelete(L,m);

}//排序函数

seqlist* merge(seqlist* L1,seqlist* L2) { int i,j,t,m,k;

if(L1->last[1]+1+L2->last[2]+1>=MAXSIZE)

{ printf(\space is small!\\n\ return ERROR;} selectsort(L1,1); selectsort(L2,2); /*for(i=0;i<=L1->last[1];i++) printf(\ for(j=0;j<=L2->last[2];j++) printf(\

for(i=0,j=0;i<=L1->last[1]&&j<=L2->last[2];)

{ if(L1->data[i]data[j]) i++;

else if(L1->data[i]==L2->data[j]) j++; else { for(k=L1->last[1];k>=i;k--)

L1->data[k+1]=L1->data[k]; L1->data[i]=L2->data[j]; L1->last[1]++; j++; i++; } } m=i;

if(i>L1->last[1]) for(t=j;t<=L2->last[2];t++)

{ L1->data[m]=L2->data[t];L1->last[1]++;m++;}

return L1; }*/

seqlist* Delete_seqlist(seqlist*L,int i) {

int j; if(i<0||i>L->last+1) {printf(\place is wrong!\\n\ for(j=i-1;j<=L->last-1;j++) L->data[j]=L->data[j+1]; L->last--;

printf(\删除成功!\\n\\n\ return L; }

void main() { int i,j,x,k; seqlist*L;

printf(\******************************************\\n\

printf(\ 实现对顺序表的定义、创建、删除、插入\\n\

printf(\ ———031210335 白雷\\n\

printf(\****************************************\\n\

第 5 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

L=init_seqlist();

printf(\original data of L1 is as follows: \

for(i=0;i<=L->last;i++) printf(\ printf(\

printf(\ 要实现的功能：\\n0:将某个元素删除!\\n1:插入某个元素到指定位置!\\nif(-1)stop\\n请输入要执行的操作序号： \ scanf(\ while(k!=-1) { switch(k) { case 0:

printf(\将某个元素删除!\\n请输入要删除的元素位置： \ scanf(\

L=Delete_seqlist(L,j);

printf(\data of L is as follows: \

for(i=0;i<=L->last;i++) printf(\ break; 五、实验的总结

case 1: printf(\插入某个元素到指定位置!\\n\ printf(\请输入要插入的元素： \ scanf(\ printf(\请输入元素插入位置： \ scanf(\

L=Insert_seqlist(L,j,x);

printf(\ for(i=0;i<=L->last;i++) printf(\ break; }

printf(\ 要实现的功能: \\n0:将某个元素删除!\\n1:插入某个元素到指定位置!\\nif(-1)stop\\n请输入要执行的操作序号： \ scanf(\ } }

在编写顺序表的实验中，个人认为此实验比较简单，但由于是本课程做的第一个实验对于大一学过的C语言有较多的遗忘，这主要通过上机带上C语言课本进行解决。同时遇到的更大的问题是软件教材代码理由类C程序给出，VC环境下不能直接运行，这主要通过查找C语言课本将非C部分改为C程序，并在调试过程中逐步排错解决。可见在编写过程中不仅需要仔细分析算法还需熟练掌握C语言的相关知识和上机素养。

实验二 单链表

一、简述每一部分的对象、目的和要求；

1、 对象：单链表表。

2、目的：将数据以单链表形式存储并且进行各种操作。

3、要求：单链表的定义、创建、插入和删除操作，将数据元素显示出来。

二、画出算法(程序)的流程图

第 6 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

图 二.1 主函数和插入结点函数流程图

图 二.2删除结点函数流程图

第 7 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

图 二.3初始化链表函数流程图

三、程序的数据输入要求和输出结果的特点与结论

元素通过调用函数 Insert_slnode ( )来输入链表头指针，插入int型数据和位置i（int型）输入数据；在输入前必须先调用 init_slnode ( )函数初始化新单链表，返回链表头结点指针。单链表数据在主函数中输入完成后对全表进行遍历。同时可利用 Delete_slnode( )函数输入链表头指针和位置i（int型）删除指定位置 i的元素。

结论： 单链表各个节点在物理上不需要连续储存， 因此插入删除时不需要移动数据元素。 运行较迅速。 但是该结构算法需要为逻辑关系准备额外存储开销，查找元素不方便。

四、附源程序清单

#include #include #define NULL 0

#define slnode struct listtype slnode

{ int data;

slnode* next; };//定义一个数据结构

slnode* init_slnode()//初始化单链表 { slnode* h,*p,*s; int num;

h=(slnode*)malloc(sizeof(slnode)); h->next=NULL; p=h;

printf(\input the data of list (if(-1) stop) \

scanf(\

while(num!=-1)

{ s=(slnode*)malloc(sizeof(slnode)); s->data=num; if(h->next==NULL) h->next=s; else p->next=s; p=s;

printf(\input the data of list (if(-1) stop) \

scanf(\ }

p->next=NULL; return h; }

slnode* Insert_slnode(slnode*h,int i,int x)//单链表中的第i个位置插入X { slnode*p,*s; int j=0; p=h;

第 8 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

while(p->next!=NULL&&jnext; j++; }

if(j!=i-1) { printf(\is invalid!\\n\h;}

else

{ s=(slnode*)malloc(sizeof(slnode)); s->data=x; s->next=p->next; p->next=s; printf(\插入成功!\\n\ return h; } }

slnode* Delete_slnode(slnode*h,int i)//删除链表中第i个结点 { slnode*p,*s; int j=0; p=h;

while(p->next!=NULL&&jnext; j++; }

if(j!=i-1) {printf(\is invalid!\\n\h;}

else

{ if(p->next==NULL) { printf(\第i个结点不存在！\\n\ else { s=p->next; p->next=s->next; free(s); return h; } } }

void main() { int x,k,j; slnode*h,*p;

printf(\******************************************\\n\

printf(\ 实现对单链表的定义、创建、删除、插入\\n\

printf(\ ———031210335 白雷\\n\

printf(\****************************************\\n\

h=init_slnode(); p=h->next;//如果写p=h，这下面输出是有一个乱码。 printf(\ while(p!=NULL) { printf(\ \ p=p->next; } p=h->next; printf(\

printf(\要实现的功能：\\n\\t\\t0:将某个元素删除!\\n\\t\\t1:插入某个元素到指定位置!\\n\\t\\tif(-1)stop\\n\\t\\t请输入要执行的操作序号： \ scanf(\ while(k!=-1) { switch(k)

{ case 0:

printf(\将某个元素删除!\\n\\t\\t请输入要删除的元素位置： \ scanf(\

h=Delete_slnode(h,j); p=h->next;

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

第 9 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

p=h->next; break; case 1: printf(\插入某个元素到指定位置!\\n\ printf(\请输入要插入的元素： \ scanf(\ printf(\请输入元素插入位置： \ scanf(\

h=Insert_slnode(h,j,x); p=h->next;

printf(\ while(p!=NULL) { printf(\ \五、实验的总结

p=p->next; } p=h->next; break; }

printf(\要实现的功能：\\n\\t\\t0:将某个元素删除!\\n\\t\\t1:插入某个元素到指定位置!\\n\\t\\tif(-1)stop\\n\\t\\t请输入要执行的操作序号： \ scanf(\ } }

在编写单链表过程中。在编写删除节点函数并测试时，输出结果与输入的位置 i 不相符。为找出该问题，我采用输入特殊位置（如头结点和尾节点），观察输出结果，最终发现问题出在位置参数 i 在运行中未考虑起始值应当为 0 这一点，经过修改，输出结果正确。可见在编写过程中需要仔细分析各个变量的作用以及与实际结构的关系。

实验三 二叉树 一、简述每一部分的对象、目的和要求； 1、 对象：二叉树。

2、 目的：将数据以二叉树链式结构储存，并进行操作。

3、 要求： 对二叉树的链式存储结构进行定义、 创建、 先序/中序/后序遍历， 并将结果序列输出。

二、画出算法(程序)的流程图

图 三.1主函数流程图

第 10 页 共 22 页

本文来源：https://www.bwwdw.com/article/a4jd.html