数学与信息技术学院2016~2017（下）学年 计科专业2015级《数据结构》实验报告 2
学号：2015201018 姓名：汪继超
实验名称 线性表的链式存储结构 完成时间 1．掌握单链表的概念及其各种运算的原理。 2．通过对单链表的建立及几种基本运算等的算法实现，掌一.实验目的 握线性表的链式存储结构、各种运算和指针的表示及应用等内容。初步掌握运用链式结构的编程和调试程序的能力。 3．用C语言实现并上机调试通过，认真填写实验报告 4．采用链式存储结构完成。 二.实验要求 5．注意类C和C的转换。 6．上机调试通过，认真书写实验报告。 链表是一种动态存储结构。线性表的链式存储结构的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。线性表的一个结点由两个域组成：存放自身的数据和存放直接后继结点存储位置的指针域 。用指针三.实验原理 相连接的 结点序列称为链表，若逻表中每个结点只包含一个指针域，则此链表为线性链表或单链表。通常链表中的每个结点可以有若干个数据域 和多个链域 。我们常用C语言中的“指针”类型来描述线性链表。 （1） 定义函数create_linklist(): 建立一个具有n个结点的单向链表L，要求返回表头指针； 四.实验内容 （2） 定义函数count_node():统计结点个数，要求以表头指针作为调用函数，返回结点个数； （3） 定义函数insert_node():在链表L的第I个结点前插入 完美WORD格式编辑
专业资料整理分享
一个结点，要求以表头指针作为调用函数，无返回值； （4） 定义函数delete_node():删除链表L的第I个元素，要求以表头指针作为调用函数，无返回值； （5） 定义函数print_node():输出单链表; （6） 以上每次操作结束，输出单链表，要求以表头指针作为调用函数，无返回值。 实验过程： #include 专业资料整理分享 q=p; } fflush(stdin);//清空在此前输入缓冲区 q->next=NULL; printf(\"\\n已创建数据：\"); print_node(L); color(10); return L; } void print_node(LinkList L)//打印 { Lnode *p; p=L->next; while(p) { printf(\"%5d\ p=p->next; } printf(\"\\n\"); } int count_node(LinkList L)//统计 { int count=0; Lnode *p; p=L->next; while(p) { p=p->next; count++; } color(13); printf(\"\\n统计得总共记录为：%d条\\n\ color(10); return count; } void insert_node(Lnode *L,int i,ElemType x,int count)//插入； { Lnode *p,*q; int k,s; count=count_node(L); color(13); 完美WORD格式编辑 专业资料整理分享 printf(\"\\n链表当前数据：\"); print_node(L); color(10); printf(\"\\n请输入插入的位置和元素，以空格隔开：\"); scanf(\"%d%d\ color(13); /*先判断位置是否合法，合法执行插入操作，反之则不执行。*/ if(k<1||k>count-1) { printf(\"\\n插入元素的位置不合法！\\n\"); } else { printf(\"\\n链表插入元素前：\"); print_node(L); p=(LinkList)malloc(sizeof(Lnode)); //为插入元素开辟新空间 p->data=s; for(q=L;k>1;k--) q=q->next; p->next=q->next; q->next=p; count++; printf(\"\\n链表插入元素后：\"); print_node(L); } color(10); } void delete_node(Lnode *L,int i,int count) { Lnode *p,*q; p=L; count=count_node(L); int k; color(13); printf(\"\\n链表当前数据：\"); print_node(L); color(10); printf(\"\\n请输入删除元素的位置：\"); scanf(\"%d\ color(13); if(k<1||k>count) printf(\"\\n您输入的元素位置不合法！\\n\"); else { 完美WORD格式编辑 专业资料整理分享 printf(\"\\n链表删除元素前：\"); print_node(L); while(--k>0) p=p->next; q=p->next; p->next=p->next->next; free(q); count--; printf(\"\\n链表删除元素后：\"); print_node(L); } color(10); } void LocateElem_node(Lnode *L,ElemType x)//查找操作 { Lnode *p; p=L->next; int j=1,flag=0; color(13); printf(\"\\n链表当前数据：\"); print_node(L); color(10); printf(\"\\n请输入要查找的元素：\"); scanf(\"%d\ color(13); while(p) { if(p->data==x) { flag=1; printf(\"\\n找到元素:%d 位置为%d \\n\ color(10); } j++; p=p->next; } if(flag==0) printf(\"\\n没有找到该元素\\n\"); color(10); } void modify_node(Lnode *L,ElemType e1,ElemType e2) //修改操作 { Lnode *p; p=L->next; 完美WORD格式编辑 专业资料整理分享 int j=1,n,flag=0; color(13); printf(\"\\n链表当前数据：\"); print_node(L); color(10); printf(\"\\n请输入要修改的元素：\"); scanf(\"%d\ color(13); while(p) { if(p->data==e1) { flag=1; printf(\"\\n找到元素:%d 位置为%d \\n\ printf(\"\\n\\n[ 1.修改 2.不修改] 请输入: \"); scanf(\"%d\ if(n!=1) break; if(n==1) { printf(\"\\n元素%d改为: \ scanf(\"%d\ p->data=e2; printf(\"\\n修改成功！\\n \"); printf(\"\\n修改后链表的数据：\"); print_node(L); break; } color(10); } j++; p=p->next; } if(flag==0) printf(\"\\n没有找到该元素\\n\"); color(10); } void Menu() { printf(\" 线性表的链式存储结构 \\n\\n\"); printf(\" ************************************菜单**************************************\\n\"); printf(\" * 1.建表 2.统计 *\\n\"); 完美WORD格式编辑 专业资料整理分享 printf(\" * 3.插入 4.删除 *\\n\"); printf(\" * 5.打印 6.修改 *\\n\"); printf(\" * 7.查找 0.退出 *\\n\"); printf(\" ******************************************************************************\\n\"); } void main() { int e1=0,e2=0,c=0,e=0,i=0,n,flag; /*c=count*/ char a; Lnode *L; L=(LinkList)malloc(sizeof(Lnode)); color(10); start: do { Menu(); printf(\"\\n请选择你需要操作的步骤(0--7): \"); fflush(stdin); /*清空在此前输入缓冲区*/ scanf(\"%d\ if(n>=0 && n<=7) { flag=1;break; } else { flag=0; system(\"cls\"); printf(\"您输入有误，请重新选择!\\n\"); } } while(flag==0); while(flag==1) { switch(n) { case 1:create_linklist(L);break; /*建表*/ case 2:count_node(L);break; /*统计*/ case 3:insert_node(L,i,e,c);break; /*插入*/ 完美WORD格式编辑 专业资料整理分享 } } case 4:delete_node(L,i,c);break; /*删除*/ case 5:printf(\"\\n链表当前数据：\");print_node(L);break; /*打印*/ case 6:modify_node(L,e1,e2);break; /*修改*/ case 7:LocateElem_node(L,e);break; /*查找*/ case 0:free(L);exit(0);break; default:system(\"cls\");goto start; } printf(\"\\n是否继续进行(y or n): \"); fflush(stdin);//清空在此前输入缓冲区 a=getchar(); if(a=='y'||a=='Y') { flag=1; system(\"cls\"); /*清屏*/ Menu(); /*调用菜单函数*/ printf(\"请再次选择你需要操作的步骤(0--7): \"); fflush(stdin); //清空在此前输入缓冲区 scanf(\"%d\} else { free(L);//释放链表 exit(0); } 完美WORD格式编辑 专业资料整理分享 实验结果： 1. 建表： 注：若以空格键隔开数据，多输入无影响，计算机读取完指定数目数据后，自动结束读取。 2.统计： 3-1.插入位置合法： 完美WORD格式编辑 专业资料整理分享 3-2.插入位置不合法： 4-1.删除位置合法： 4-1.删除位置不合法： 完美WORD格式编辑 专业资料整理分享 5.打印： 6-1.找到修改元素，并确定修改： 完美WORD格式编辑 专业资料整理分享 6-2.找到修改元素，不修改： 6-3.没找到修改元素： 完美WORD格式编辑 专业资料整理分享 7-1.查找成功： 7-2.查找-没有相应数据： 完美WORD格式编辑 专业资料整理分享 问题讨论： 1. 删除操作执行出错： 问题分析：找到位置，可能删除元素时链表指针指向出错。 问题解决：将上图中p=p->next->next改为p->next =p->next->next 2. 链表长度统计与调用中，注意各函数与统计函数的关系。例如：插入函数、删除函数等。 问题讨论与结论： （1） 插入、删除操作时同时增减已统计的链表长度 （2） 每次需用到链表长度时，重新调用统计函数统计链表长度 注：文件名为：学号+（次数） 完美WORD格式编辑 因篇幅问题不能全部显示，请点此查看更多更全内容