哈工程数据结构实验报告(八系)

《哈工程数据结构实验报告(八系)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程名称数据结构实验项目名称1．单链表的实现与应用2．堆栈的实现与应用3．排序、查找算法的实现与应用实验类型基本型/基本型/综合型实验学时2/2/4班级学号姓名指导教师实验室名称实验时间20171127/1127/1204实验成绩编号过程表现预习部分实验报告小计总成绩12324教师签字日期哈尔滨工程大学本科生院制24实验1单链表的实现与应用--------------------------------------------------------------------------------

2、----------------------【预习部分】一、实验目的通过编程实验，进一步增强对单链表的理解和掌握。二、实验要求编写程序实现单链表的基本操作（初始化、撤销、插入、删除、取数据元素、求数据元素个数），并设计测试数据，能全面地测试所设计程序的功能。三、实验原理1.单链表结构线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。单链表是线性表的一种。而单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点是逻辑上相邻的

3、数据元素在物理上不一定相邻。2.单链表数据插入原理①要在带头结点的单链表第i（0≤i≤24size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q->data=x），最后修改新结点的指针域指向ai结点（即q->next=p->next），并修改ai-1结点的指针域指向新结点q（即p->next=q）。②循环条件由两个子条件逻辑与组成，其中子条件p->next!=NULL保证

4、指针所指结点存在，子条件jnext），并把数据元素ai的值赋予x（即*x=s->data），最后把ai结点脱链（即p->next=p->next->next），并动态释放ai结点的存储空间（即free(s)）。删除过程如图2-14所示。图中的①对应算法中的删除语句。四、实验环境VisualSt

5、udio2010------------------------------------------------------------------------------------------------------五、实验步骤（程序代码）//5555.cpp:定义控制台应用程序的入口点//#include"stdafx.h"24int_tmain(intargc,_TCHAR*argv[]){return0;}#include#include#include

6、alloc.h>typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}SLNode;voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL;}24voidDestroy(SLNode**head){SLNode*p,*p1;p=*head;while(p!=NULL){p1=p;p=p->next;free(

7、p1);}*head=NULL;}intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;while(p->next!=NULL&&jnext;j++;}24if(j!=i-1){printf("插入位置参数错！");return0;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q;return1;}intL

8、istDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;j=-1;while(p->next!=NULL&&p->next->next!=NULL&&jnext;j++;}if(j!=i-1){printf("插入位置参数错！");24return0;}s=p->next;*x=s->data;p->next=p->next->next