实验二 单链表的基本算法

实验二单链表的基本算法一．实验目的：通过上机编程掌握1．生成单链表的基本算法；2．在单链表上的插入、删除运算。二．实验要求：1.给出程序设计的基本思想、原理和算法描述。2.画出程序流程图；根据数据结构有关知识编出算法程序；3.源程序给出注释；4.保存和打印出程序的运行结果，并结合程序进行分析。三．实验内容：1.编写函数实现单链表的基本运算：(1)单链表的生成(2)单链表的插入(3)单链表的删除2.编写主函数测试单链表的各种基本运算：(1)生成一个至少包含有5个元素的单链表,元素值由计算机输入(2)在表中的第5个位置上插入元素”7”(3)删除表中的第6个元素(4)显示(1)—(3)每一步的操作结果NYNYdatatypedataNODE*P,*S(p-next!=NULL)&&(counteri-1)p=p-nextp-next==NULL)||(counteri-1)i值不合法s=p-next删除SNY实验原理：首先建立头结点，形成一个单链表，通过malloc函数创建新的结点单元，将要读取的数据赋值给新结点。其次插入链表，从头结点开始依次延指针域查找需要插入的结点，为插入数据元素x生成一个新结点s，将x插入在s和s-1之间。最后链表结点删除，找到指定结点的前趋结点通过改变连接完成删除。源程序：#includestdio.h#includestdlib.htypedefintdatatype;typedefstructnode/*结构体更名为NODE*/{datatypedata;structnode*next;}NODE;NODE*creatlink()/*建立带头结点的单链表*/{NODE*head,*s,*p;intx;head=(NODE*)malloc(sizeof(NODE));/*生成一个NODE型新结点并赋值给head*/p=head;scanf(%d,&x);while(x!=0){s=(NODE*)malloc(sizeof(NODE));/*生成一个NODE型新结点并赋值给s*/NODE*head,*pp!=NULLprintf(%d,p-data)printf(\n)s-data=x;s-next=head-next;head-next=s;scanf(%d,&x);}p-next=NULL;returnhead;/*返还给head*/}voidinsert(NODE*head,inti，intx);/*单链表的插入*/{NODE*p,*s;intcounter=0;/*计数器*/p=head;while((p!=NULL)&&(counteri))p=p-next;counter++;}if((p==NULL)||(counteri))printf(i值不合法\n);else{s=(NODE*)malloc(sizeof(NODE));/*生成一个NODE型新结点并赋值给s*/s-data=x;s-next=p-next;p-next=s;}}voiddelete(NODE*head,inti)/*单链表的删除*/{NODE*P,*S;intcounter=0;/*计数器*/p=head;while((p-next!=NULL)&&(counteri-1)){p=p-next;counter++;}if((p-next==NULL)||(counteri-1))printf(i值不合法\n);else{s=(NODE*)malloc(sizeof(NODE));/*生成一个NODE型新结点并赋值给s*/s=p-next;p-next=s-next;free(s);/*删除s*/}}main(){NODE*head,*p;head=(NODE*)malloc(sizeof(NODE));printf(输入元素值（用0做结束符）：\n);head=creatlink();/*创建链表函数*/insert(head,5,7);/*插入函数*/delete(head,s);/*删除函数*/printf(在第三个位置插入58并删除第四个元素后的链表是：\n);p=head-next;while(p!=NULL){printf(%d,p-data);p=p-next;}printf(\n);}四．实验结果四．实验小结通过本次实验进一步了解了链表的知识，通过实际操作加强了使用链表的熟练程度。同时在本次试验中也发现了自己的一些问题，对于顺序表的语句还存在着一些不理解、不清楚的地方，在上机时间通过和同学的沟通解决。