实验二_单链表的实现及测试.doc

《实验二_单链表的实现及测试.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.上海电力学院计算机软件技术实验实验报告实验题目：单链表的实现及测试院　　系：自动化工程学院专业年级：自动化2013级学生姓名：晁文涛学号20131529实验二单链表的基本算法Word文档.一．实验目的：通过上机编程掌握1．生成单链表的基本算法；2．在单链表上的插入、删除运算。二．实验要求：1.给出程序设计的基本思想、原理和算法描述。2.画出程序流程图；根据数据结构有关知识编出算法程序；3.源程序给出注释；4.保存和打印出程序的运行结果，并结合程序进行分析。三．实验内容：1.编写函数实现单链表的基本运算：(1)单链表的生成反向建立链表（头插法）思想：首先生成头结点，形成一个空链表

2、，然后在表中逐一读入新的结点，反复执行下列步骤：使用malloc函数开辟新结点的存储单元；将读入数据存放到新结点的数据域中；将新结点插入到当前链表的表头上，直到读入结束标志为止。流程图为：具体算法如下：NODE*creatlink1()//头插法{NODE*head,*s;intx;head=(NODE*)malloc(sizeof(NODE));//生成头结点head->next=NULL;scanf("%d",&x);//读入第一个结点值while(x!=0){s=(NODE*)malloc(sizeof(NODE));s->data=x;s->next=head->next

3、;head->next=s;//将新节点插入到表头上scanf("%d",&x);}returnhead;}正向建立单链表（尾插法）Word文档.思想：首先生成头结点，依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点之后。流程图为：具体算法为：NODE*creatlink2()//尾插法{NODE*head,*p,*s;intnum;head=(NODE*)malloc(sizeof(NODE));//生成头结点scanf("%d",&num);//读入第一个结点值p=head;//头指针等于尾指针while(num!=0)//输入0作为结束符{s=(NODE

4、*)malloc(sizeof(NODE));//生成新节点s->data=num;//新结点上填入输入值p->next=s;//新结点*s插入到尾结点*p之后p=s;//尾指针指向新的表尾scanf("%d",&num);//读入下一个结点值}p->next=NULL;//将尾结点的指针置空returnhead;//返回单链表表头指针}（2）单链表的插入思想：首先要搜索单链表以找到指定插入结点的前趋结点p；然后改变链接，即只要是将待插入结点的指针域内容赋予p结点的指针域即可。Word文档.流程图为：具体算法为：NODE*get(NODE*head,inti)//查找第i个元素的

5、位置{NODE*p;intcounter=1;p=head->next;while((p!=NULL)&&(counternext;counter++;}if((p!=NULL)&&(counter==i))//找到，1<=i<=nreturnp;elsereturnNULL;//找不到，i>n或i<=n}voidinsertafter(NODE*p,intx){NODE*s;s=(NODE*)malloc(sizeof(NODE));//修改i-1结点的尾指针s->data=x;s->next=p->next;p->next=s;}voidinsert(NO

6、DE*head,inti,intx)//在i个位置插入x{NODE*p;intj=i-1;p=get(head,j);//调用查找函数找到i-1的结点位置if(p==NULL)printf("error");elseinsertafter(p,x);//调用insertafter函数}(1)单链表的删除思想：首先要搜索单链表以找到指定删除结点的前趋结点p；然后改变链接，即只要是将待删除结点的指针域内容赋予p结点的指针域即可。Word文档.流程图为：具体算法为：voiddelete(NODE*head,inti)//删除第i个位置的元素{NODE*p,*s;intj=0;p=hea

7、d;while((p->next!=NULL)&&(jnext;j++;}if((p->next==NULL)

8、

9、(j>i-1))printf("i值不合法");else{s=p->next;//修改p->next，使指向s->nextp->next=s->next;//删除s结点free(s);}}1.编写主函数测试单链表的各种基本运算：(1)生成一个至少包含有5个元素的单链表,元素值由计算机输入(2)在表中的第5个位置上插入