中南大学数据结构实验报告(一)

中南大学数据结构试验报告题目实验一学生姓名王云鹏学号8213180228指导老师郑瑾学院计算机学院专业班级物联网1802完成时间2020.6指导老师评定签名实验一1.需求分析1．单向链表操作的实现（验证性实验）问题描述(1)用头插法（或尾插法）建立带头结点的单向链表。(2)对已建立的单向链表实现插入、删除、查找等基本操作。2．城市链表（设计性实验）问题描述将若干城市的信息存入一个带头结点的单向链表。结点中的城市信息包括城市名、城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。基本要求(1)给定一个城市名，返回其位置坐标。(2)给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据4．长整数运算（综合性实验）问题描述设计一个程序实现两个任意长的整数求和运算。基本要求利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是−(215−1)～(215−1)。输入和输出形式：每4位一组，组间用逗号隔开。测试数据(1)0和0，应输出“0”。(2)−2345,6789，−7654,3211，应输出“−1,0000,0000”。(3)−9999,9999，1,0000,0000,0000，应输出“9999,0000,0001”。362附录(4)1,0001,000，−1,0001,0001，应输出“0”。(5)1,0001,0001，−1,0001,0000，应输出“1”。实现提示(1)每个结点中可以存放的最大整数为215−1＝32767，这样才能保证两数相加不会溢出。但若按32768进制数存放，在十进制数与32768进制数之间的转换十分不方便，故可以在每个结点中仅存放十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。(2)可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。2.概要设计验证性实验函数：设计性实验函数：综合性实验函数：3.详细设计验证性实验#includestdio.h#includestdlib.htypedefstructnode//节点{intdata;structnode*next;}node;intlength(node*head){//返回链表长度，算上头节点intlen=0;node*p=head;while(p!=NULL){len++;p=p-next;}returnlen;}voidInit(node*head){//带头节点if(head==NULL){printf(mallocfailinmain\n);return;}head-data=0;//头节点存链长，且头节点不计入链长//printf(%d,head-data);head-next=NULL;}voidInsert(node*head,inte,intpos){//在第pos个节点后插入新节点if(poslength(head)||pos0)//不合法位置{printf(illegalpositioninInsert\n);return;}node*p=head;for(inti=pos;i1;i--)//找到插入位置{p=p-next;}node*x=(node*)malloc(sizeof(node));//要插入的节点if(x==NULL){printf(mallocfailinInsert);return;}x-data=e;x-next=p-next;p-next=x;head-data++;}voidDelete(node*head,int*e,intpos){//删除第pos个节点if(poslength(head)||pos0)//非法位置{printf(illegalpositioninDelete\n);return;}node*p=head;//当前指针node*p_pre;//当前指针的前驱for(inti=pos;i=1;i--)//找到位置{p_pre=p;p=p-next;}p_pre-next=p-next;//将当前节点从链表中断开*e=p-data;//用e带出删掉的值free(p);head-data--;}voidInquire(node*head,int*e,intpos)//查询第pos个节点位置{if(poslength(head)||pos0){printf(illegalpositioninInquire\n);return;}node*p=head;for(inti=pos;i=1;i--)//找位置{p=p-next;//下一个}*e=p-data;//用e带出查询结果printf(查询结果————第%d个节点的值为：%d,pos,*e);}voidprint(node*head)//将链表从头到尾打印{node*p=head;printf(当前链表有节点：%d个\n,head-data);printf(链表节点从头到尾分别为：\n);while(p-next!=NULL){p=p-next;printf(%d\n,p-data);}}voidmain()设计性实验{node*head=(node*)malloc(sizeof(node));//在主函数中申请头节点Init(head);//初始化int*e;Insert(head,10,1);//插入Insert(head,28,2);Insert(head,30,1);//printf(hh);print(head);Delete(head,e,2);//删除print(head);Inquire(head,e,2);//查询}#includestdio.h#includestdlib.h#includestring.h#includemath.htypedefstructinfo//节点中的信息{char*name;doublex;doubley;}info;typedefstructnode//节点{infocity;structnode*next;}node;intlength(node*head)//返回链长度{intlen=0;node*p=head;while(p!=NULL){len++;p=p-next;}returnlen;}voidInit(node*head){//带头节点head-next=NULL;}voidInsert(node*head,infocity,intpos){//在第pos个节点后插入新节点if(poslength(head)||pos0)//非法位置{printf(illegalpositioninInsert\n);return;}node*p=head;for(inti=pos;i1;i--)//找到位置{p=p-next;}node*x=(node*)malloc(sizeof(node));//申请节点if(x==NULL){printf(mallocfailinInsert);return;}x-city=city;x-next=p-next;p-next=x;}voidDelete(node*head,info*city,intpos){//删除第pos个节点if(poslength(head)||pos0)//非法位置{printf(illegalpositioninDelete\n);return;}node*p=head;node*p_pre=head;for(inti=pos;i0;i--)//找到位置{p_pre=p;p=p-next;}p_pre-next=p-next;*city=p-city;free(p);}voidInquire(node*head,info*city,intpos)//查询第pos个节点的信息{if(poslength(head)||pos0)//非法位置{printf(illegalpositioninInquire\n);return;}node*p=head;for(inti=pos;i0;i--)//找到位置{p=p-next;}*city=p-city;printf(theresultofInquireis:name:%sx:%fy:%f\n,city-name,city-x,city-y);}voidInquire2(node*head,info*city)//returnx,yaccordingtonameincity{node*p=head;while(p!=NULL)//遍历链表{if(strcmp(city-name,p-city.name)==0)//判断当前节点城市名与传入参数city中的城市名是否相同{city-x=p-city.x;city-y=p-city.y;printf(theaddressofthe%sis(%f,%f)\n,city-name,city-x,city-y);return;}p=p-next;}printf(failtofind%s\n,city-name);//还没返回说明没找到}voidprint(node*head)//从头到尾打印该链表{node*p=head;printf(当前链表有节点：%d个\n,length(head)-1);printf(链表节点从头到尾分别为：\n);while(p-next!=NULL)//遍历{p=p-next;printf(name:%s,p-city.name);printf(x:%f,p-city.x);printf(y:%f\n,p-city.y);}}doubledis(infocity1,infocity2){//返回两城市间距离returnsqrt(pow((city1.x-city2.x),2)+pow((city1.y-city2.y),2));}voidInquire_all(node*head,infopoint,doubledistance,node*new_head){//查询所有与point的距离在distance范围内的城市node*p=head;while(p-next!=NULL){//遍历p=p-next;doubledisReal=dis(point,p-city);if(disRealdistance){//判断是否在distance范围内Insert(new_head,p-city,1);}}}voidmain(){node*head=(node*)malloc(sizeof(node));//在主函数内申请头节点if(head==NULL){printf(mallocfailinmain\n);return;}Init(head);//初始化infocity1={hefei,1,1};Insert(head,city1,1);//插入infocity2={nanjing,2,2};Insert(head,city2,2);infocity3={shanghai,3,3};Insert(head,city3,3);print(head);//打印infocity4;Delete(head,&city4,2);//删除print(head);Inquire(head,&city4,2);//查询infocity={hefei};Inquire2(head,&city);//根据城市名查询infopoint={NULL,0,0};node*new_head=(node*)malloc(sizeof(node));//用头节点为new_he