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

、查找算法的实现与应用实验类型基本型/基本型/综合型实验学时2/2/4班级学号姓名指导教师实验室名称实验时间20171127/1127/1204实验成绩编号过程表现预习部分实验报告小计总成绩123教师签字日期哈尔滨工程大学本科生院制实验1单链表的实现与应用------------------------------------------------------------------------------------------------------【预习部分】一、实验目的通过编程实验,进一步增强对单链表的理解和掌握。二、实验要求编写程序实现单链表的基本操作(初始化、撤销、插入、删除、取数据元素、求数据元素个数),并设计测试数据,能全面地测试所设计程序的功能。三、、由n(n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。单链表是线性表的一种。而单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点是逻辑上相邻的数据元素在物理上不一定相邻。①要在带头结点的单链表第i(0≤i≤size)个结点前插入一个存放数据元素x的结点,首先要在单链表中寻找到第i-1个结点并由指针p指示,然后动态申请一个结点存储空间并由指针q指示,并把数据元素x的值赋予新结点的数据元素域(即q->data=x),最后修改新结点的指针域指向ai结点(即q->next=p->next),并修改ai-1结点的指针域指向新结点q(即p->next=q)。②循环条件由两个子条件逻辑与组成,其中子条件p->next!=NULL保证指针所指结点存在,子条件j<i-1保证最终让指针p指向ai-1结点。(0≤i≤size-1)个结点,首先要在单链表中寻找到第i-1个结点并由指针p指示,然后让指针s指向ai结点(即s=p->next),并把数据元素ai的值赋予x(即*x=s->data),最后把ai结点脱链(即p->next=p->next->next),并动态释放ai结点的存储空间(即free(s))。删除过程如图2-14所示。图中的①对应算法中的删除语句。四、实验环境VisualStudio2010------------------------------------------------------------------------------------------------------五、实验步骤(程序代码)//:定义控制台应用程序的入口点//#include""int_tmain(intargc,_TCHAR*argv[]){ return0;}#include<> #include<> #include<>typedefintDataType;typedefstructNode{ DataTypedata; structNode*next;}SLNode;voidListInitiate(SLNode**head){ *head=(SLNode*)malloc(sizeof(SLNode)); (*head)->next=NULL; }voidDestroy(SLNode**head){ SLNode*p,*p1; p=*head;while(p!=NULL){ p1=p;p=p->next; free(p1); }*head=NULL;}intListInsert(SLNode*head,inti,DataTypex){ SLNode*p,*q; intj; p=head; j=-1; while(p->next!=NULL&&j<i-1){ p=p->next;j++; }if(j!=i-1){ printf("插入位置参数错!"); return0;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q; return1;}intListDelete(SLNode*head,inti,DataType*x){ SLNode*p,*s;intj; p=head;j=-1;while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){ p=p->next; j++;} if(j!=i-1) { printf("插入位置参数错!"); return0; } s=p->next;*x=s->data;p-