实验二 单链表的基本算法.doc

《实验二 单链表的基本算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二单链表的基本算法一．实验目的：通过上机编程掌握1．生成单链表的基本算法；2．在单链表上的插入、删除运算。二．实验要求：1.给出程序设计的基本思想、原理和算法描述。2.画出程序流程图；根据数据结构有关知识编出算法程序；3.源程序给出注释；4.保存和打印出程序的运行结果，并结合程序进行分析。三．实验内容：1.编写函数实现单链表的基本运算：(1)单链表的生成(2)单链表的插入(3)单链表的删除2.编写主函数测试单链表的各种基本运算：(1)生成一个至少包含有5个元素的单链表,元素值由计算机输入(2)在表中的第5个位置上插入元素”7”(3)删除表中的第6个元素(4)显示(1)—(3)每一步的操

2、作结果(p->next!=NULL)&&(counternexti值不合法p->next==NULL)

3、

4、(counter>i-1)p=p->nextNODE*P,*SdatatypedataNYN删除SYprintf("")printf("%d",p->data)p!=NULLNODE*head,*pNY实验原理：首先建立头结点，形成一个单链表，通过malloc函数创建新的结点单元，将要读取的数据赋值给新结点。其次插入链表，从头结点开始依次延指针域查找需要插入的结点，为插入数据元素x生成一个新结点s，将x插入在s和s-1之间。最后链表结点删除，找到指定结点的前趋结

5、点通过改变连接完成删除。源程序：#include#includetypedefintdatatype;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(si

6、zeof(NODE));/*生成一个NODE型新结点并赋值给s*/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)&&(counternext;counter++;}if((p==NULL)

7、

8、(counter>i))printf("i值不合法

9、");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)&&(counternext;counter++;}if((p->next==NULL)

10、

11、(counter>i-1))printf("i值不合法");else{s=(NODE*)ma

12、lloc(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做结束符）：");head=creatlink();/*创建链表函数*/insert(head,5,7);/*插入函数*/delete(head,s);/*删除函数*/printf("在第三个位置插入58并删除第四个元素后的链表是：");p=head->next;while(p!=N

13、ULL){printf("%d",p->data);p=p->next;}printf("");}四．实验结果四．实验小结通过本次实验进一步了解了链表的知识，通过实际操作加强了使用链表的熟练程度。同时在本次试验中也发现了自己的一些问题，对于顺序表的语句还存在着一些不理解、不清楚的地方，在上机时间通过和同学的沟通解决。