数据结构实验报告

《数据结构》实验报告实验序号：3实验项目名称：链式表的操作一、实验目的及要求1.通过实验理解单链表的逻辑结构；2.通过实验掌握单链表的基本操作和具体的函数实现。二、实验设备（环境）及要求微型计算机；windows操作系统；MicrosoftVisualStudio6.0集成开发环境。三、实验内容与步骤1.链式表表示和实现线性表的如下：#includestdio.h#includestring.h#includestdlib.h#includectype.htypedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数，用尾插入法建立带头结点的单链表ListNode*LocateNode(LinkListhead,char*key);//函数，按值查找结点voidDeleteList(LinkListhead,char*key);//函数，删除指定值的结点voidprintlist(LinkListhead);//函数，打印链表中的所有值voidDeleteAll(LinkListhead);//函数，删除所有结点，释放内存//==========主函数==============voidmain(){char*ch,*num;num=newchar;ch=newchar[10];LinkListhead;head=CreatListR1();//用尾插入法建立单链表，返回头指针printlist(head);//遍历链表输出其值printf(Deletenode(y/n):);//输入y或n去选择是否删除结点scanf(%s,num);if(strcmp(num,y)==0||strcmp(num,Y)==0){printf(PleaseinputDelete_data:);scanf(%s,ch);//输入要删除的字符串DeleteList(head,ch);printlist(head);}DeleteAll(head);//删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkListCreatListR1(void){char*ch;ch=newchar[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成头结点ListNode*s,*r,*pp;r=head;r-next=NULL;printf(Input#toend);//输入#代表输入结束printf(PleaseinputNode_data:);scanf(%s,ch);//输入各结点的字符串while(strcmp(ch,#)!=0){s=(ListNode*)malloc(sizeof(ListNode));strcpy(s-data,ch);r-next=s;r=s;r-next=NULL;printf(Input#toend);printf(PleaseinputNode_data:);scanf(%s,ch);}returnhead;//返回头指针}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head-next;//从开始结点比较while(strcmp(p-data,key)!=0&&p)//直到p为NULL或p-data为key止p=p-next;//扫描下一个结点returnp;//若p=NULL则查找失败，否则p指向找到的值为key的结点}//==========删除带头结点的单链表中的指定结点=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=head;p=LocateNode(head,key);//按key值查找结点的if(p==NULL){//若没有找到结点，退出printf(positionerror);exit(0);}while(q-next!=p)//p为要删除的结点，q为p的前结点q=q-next;r=q-next;q-next=r-next;free(r);//释放结点}//===========打印链表=======voidprintlist(LinkListhead){ListNode*p=head-next;//从开始结点打印while(p){printf(%s,,p-data);p=p-next;}printf(\n);}//==========删除所有结点，释放空间===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p-next){r=p-next;free(p);p=r;}free(p);}改写以上程序，实现功能如下：1.编写一个函数计算值域为x的结点个数。2.编写一个删除链表中值为x的结点的直接前趋结点的算法，若有多个值为x的结点，则删除第一个x的直接前趋结点。3.写一个对单循环链表进行逆序遍历（打印每个结点的值）的算法。4．改写CreatListR1函数，使得链表创建时为非降序排列，在上述链表中插入一个元素，使得链表依然升序；四、实验结果与数据处理。五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：#includestdio.h#includestring.h#includestdlib.h#includectype.htypedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数，用尾插入法建立带头结点的单链表ListNode*LocateNode(LinkListhead,char*key);//函数，按值查找结点voidDeleteList(LinkListhead,char*key);//函数，删除指定值的结点voidprintlist(LinkListhead);//函数，打印链表中的所有值voidDeleteAll(LinkListhead);//函数，删除所有结点，释放内存voidsamelist(LinkListhead);voidDeletefront(LinkListhead);voidnixu_list(LinkListhead);voidpaixu(LinkListhead);//==========主函数==============voidmain(){char*ch,*num;num=newchar;ch=newchar[10];LinkListhead;head=CreatListR1();//用尾插入法建立单链表，返回头指针printlist(head);//遍历链表输出其值paixu(head);samelist(head);printf(删除节点(y/n):);//输入y或n去选择是否删除结点scanf(%s,num);if(strcmp(num,y)==0||strcmp(num,Y)==0){printf(请输入要删除的数据:);scanf(%s,ch);//输入要删除的字符串DeleteList(head,ch);printlist(head);}Deletefront(head);printf(逆序后的链表：\n);nixu_list(head);DeleteAll(head);//删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkListCreatListR1(void){char*ch;ch=newchar[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成头结点ListNode*s,*r;r=head;r-next=NULL;printf(输入#结束,);//输入#代表输入结束printf(输入数据:);scanf(%s,ch);//输入各结点的字符串while(strcmp(ch,#)!=0){s=(ListNode*)malloc(sizeof(ListNode));strcpy(s-data,ch);r-next=s;r=s;r-next=NULL;printf(输入#结束,);printf(输入数据:);scanf(%s,ch);}returnhead;//返回头指针}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head-next;//从开始结点比较while(strcmp(p-data,key)!=0&&p)//直到p为NULL或p-data为key止p=p-next;//扫描下一个结点returnp;//若p=NULL则查找失败，否则p指向找到的值为key的结点}//==========删除带头结点的单链表中的指定结点=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=head;p=LocateNode(head,key);//按key值查找结点的if(p==NULL){//若没有找到结点，退出printf(positionerror);exit(0);}while(q-next!=p)//p为要删除的结点，q为p的前结点q=q-next;r=q-next;q-next=r-next;free(r);//释放结点}//===========打印链表=======voidprintlist(LinkListhead){ListNode*p=head-next;//从开始结点打印while(p){printf(%s,,p-data);p=p-next;}printf(\n);}//==========删除所有结点，释放空间===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p-next){r=p-next;free(p);p=r;}free(p);}voidsamelist(LinkListhead){ListNode*q=head-next;intn=0;char*ch;ch=newchar[10];printf(输入要查找的数据:);scanf(%s,ch);while(q){if(strcmp(q-data,ch)==0)n++;q=q-next;}free(q);printf(查找的%s有%d个.,ch,n);printf(\n);}voidDeletefront(LinkListhead){char*a;ListNode*q,*p=head-next;//从开始结点比较a=newchar[10];printf(输入数据，你将删除它的前一个数：);scanf(%s,a);while(strcmp(p-data,a)!=0&&p)//直到p为NULL或p-data为key止{q=p;p=p-next;}//扫描下一个结点while(p)p=p-next;if(!q)printf(这是