数据结构实验3王清华0907022107

《数据结构》实验报告实验序号：3实验项目名称：链式表的操作学号0907022107姓名

王青华专业、班11网络工程实验地点1#316指导教师林仙丽实验时间一、实验目的及要求1.通过实验理解单链表的逻辑结构；2.通过实验掌握单链表的基本操作和具体的函数实现。二、实验设备（环境）及要求微型计算机；windows操作系统；MicrosoftVisualStudio6.0集成开发环境。三、实验内容与步骤1.链式表表示和实现线性表的如下：#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode//定义结点{ 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函数，使得链表创建时为非降序排列，在上述链表中插入一个元素，使得链表依然升序；运行结果截图：四、实验结果与数据处理详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果（贴图）。五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：1.#include"stdio.h"#include"stdlib.h"typedefstructListNode{intdata;structListNode*next;}ListNode,*LinkList;voidInsertListNum(LinkListH){ListNode*p,*q;inti;charch=NULL;p=H;while(ch!='\n'){q=(LinkList)malloc(sizeof(ListNode));scanf("%d",&i);q->data=i;q->next=p->next;p->next=q;q=q->next;ch=getchar();}}intCountListSameNum(LinkListH,intx){ListNode*p;intcount=0;p=H->next;while(p){if(p->data==x)count++;p=p->next;}returncount;}voidPrintList(LinkListH){ListNode*p;p=H->next;while(p){printf("%d",p->data);p=p->next;}printf("\n");}main(){intn,x;LinkListH;H=(LinkList*)malloc(sizeof(ListNode));InsertListNum(H);PrintList(H);printf("EntertheNumberyoucount:\n");scanf("%d",&x);n=CountListSameNum(H,x);printf("n=%d",n);}2.#include"stdio.h"#include"stdlib.h"typedefstructListNode{intdata;structListNode*next;}ListNode,*LinkList;voidInsertListNum(LinkListH){ListNode*p,*q;inti;charch;p=H;printf("Enterthenumbers:\n");while(ch!='\n'){q=(LinkList)malloc(sizeof(ListNode));scanf("%d",&i);q->data=i;q->next=p->next;p->next=q;q=q->next;ch=getchar();}}intCountListSameNum(LinkListH,intx){ListNode*p;intcount=0;p=H->next;while(p){if(p->data==x)count++;p=p->next;}returncount;}voidDeleteListNum(LinkListH,intx){ListNode*p,*r;intn;p=H;n=CountListSameNum(H,x);if(n==0)printf("Nofounding!");else{while(p){if(p->data==x){r=p->next;p->next=r->next;free(r);break;//若将break去点，则可以删除所有的值为x的前驱结点}p=p->next;}while(p->next==NULL){printf("\nThisNO.1,NoHead!\n");break;}}}voidPrintList(LinkListH){ListNode*p;p=H->next;while(p){printf("%d",p->data);p=p->next;}printf("\n");}main(){intn,x1,x2;LinkListH;H=(LinkList*)malloc(sizeof(ListNode));InsertListNum(H);PrintList(H);printf("EntertheNumberyoucount:\n");scanf("%d",&x1);n=CountListSameNum(H,x1);printf("n=%d",n);printf("\n");printf("Enterthenumberyoudelete:\n");scanf("%d",&x2);DeleteListNum(H,x2);PrintList(H);}3.#include"stdio.h"#include"stdlib.h"typedefstructListNode{intdata;structListNode*next;}ListNode,*LinkList;voidInsertListNum(LinkListH){ListNode*p,*q;inti=0;charch=NULL;p=H;printf("Enterthenumbers:\n");while(ch!='\n'){q=(LinkList*)malloc(sizeof(ListNode));scanf("%d",&i);q->data=i;q->next=p->next;p->next=q;p=p->next;ch=getchar();}}voidSortListNum(LinkListH){ListNode*p,*q;p=H->next;H->next=NULL;while(p){q=p;p=p->next;q->next=H->next;H->next=q;}}voidPrintList(LinkListH){ListNode*p;p=H;printf("ThenewLinklistis:\n");p=p->next;while(p){printf("%d",p->data);p=p->next;}printf("\n");}main(){LinkListH;H=(LinkList*)malloc(sizeof(ListNode));InsertListNum(H);PrintList(H);SortListNum(H);PrintList(H);}4.#include"stdio.h"#include"stdlib.h"typedefstructListNode{intdata;structListNode*next;}ListNode,*LinkList;voidInsertListNum(LinkListH){ListNode*p,*q;inti;charch;p=H;printf("Enterthenumbers:\n");while(ch!='\n'){q=(LinkList)malloc(sizeof(ListNode));scanf("%d",&i);q->data=i;q->next=p->next;p->next=q;q=q->next;ch=getchar();}}voidPrintList(LinkListH){ListNode*p;p=H->next;while(p){printf("%d",p->data);p=p->next;}printf("\n");}intCountAllListNum(LinkListH){ListNode*p;inti=0;p=H->next;while(p){p=p->next;i++;}returni;}voidSortListNum(LinkListH){ ListNode*p,*s,*pt; p=H; s=p->next; while(p->next!=NULL){ while(s->next!=NULL){ if(p->next->data>s->next->d