数据结构实验报告一

《数据结构》实验报告学院：计算机学院专业：计算机科学与技术指导教师：朱战立班级学号：计1201201207010117姓名：杜晓燕题目：单循环链表问题描述：设计一个单循环链表并对其进行简单的删除插入操作。基本要求：（1）设计单循环链表的操作，包括初始化、求元素个数、插入、删除等。（2）设计输出单循环链表中所有数据元素的输出函数。（3）设计一个测试主函数。其中数据元素的类型任意。测试数据：依次输入1,2,3,4,5,6,7,8,9,10，求链表元素个数，删除5，再依次输出数据元素。算法思想：主函数主要是在带头结点的循环单链表中（1）求元素个数，其主要思想是再循环前，指针变量p指向头结点，计数变量i=0；循环结束的条件为p-next=head,循环中，每次让指针p指向p-next，让计数变量i加1；最终返回计数值i。（2）删除第i个结点，其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。模块划分：（1）操作实现包括：结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取数据元素操作；（2）实现文件包含主函数voidmain(void)，其功能是测试所设计的循环单链表的正确性。数据结构：链表中的结点的结构体定义如下：typedefstructNode{DataTypedata;structNode*next;}SLNode;源程序：#includestdio.h#includemalloc.htypedefintDataType;typedefstructNode{DataTypedata;structNode*next;}SLNode;voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)-next=*head;}intListLength(SLNode*head){SLNode*p=head;inti=0;while(p-next!=head){p=p-next;i++;}return(i);}intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;while(p-next!=head&&ji-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!=head&&p-next-next!=head&&ji-1){p=p-next;j++;}if(j!=i-1){printf(删除元素位置参数错！);return0;}s=p-next;*x=s-data;p-next=p-next-next;free(s);return1;}intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;p=head;j=-1;while(p-next!=head&&ji){p=p-next;j++;}if(j!=i){printf(取元素位置参数错!);return0;}*x=p-data;return1}voidmain(void){SLNode*head;inti,x;ListInitiate(&head);/*初始化*/for(i=0;i10;i++){ListInsert(head,i,i+1);printf(%d,i+1);}printf(\n);ListLength(head);printf(%d\n,i);ListDelete(head,4,&x);/*删除数据元素5*/for(i=0;iListLength(head);i++){ListGet(head,i,&x);/*取元素*/printf(%d,x);/*显示数据元素*/}}测试情况：（1）程序运行结果为：（2）测试结果分析：程序运行结果与预测完全相同，说明设计的单循环链表是正确的。