单链表参考答案.docx
《单链表参考答案.docx》由会员分享，可在线阅读，更多相关《单链表参考答案.docx（15页珍藏版）》请在冰点文库上搜索。
单链表参考答案
《算法与数据结构》课程设计报告
题目：
单链表
专业：
软件工程
班级：
淘宝
学号：
店铺号530213
姓名：
套套
指导教师：
完成日期：
2014年1月4日
一、课程设计目的
本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。
二、课程设计内容
编制一个单链表的插入、删除、排序、逆置、遍历、求表长的程序。
关注淘宝店：
530213
三、课程设计过程
1．需求分析
本程序运用vc++6.0编写，完成单链表的生成，任意位置插入，删除，对链表内部数据进行排序，以及求链表的总长度。
（1）输入的形式和输入值的范围：
链表生成时要输入链表的种长度，再依次的输入链表内部的元素；插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；在所有输入中，元素的值都是整数。
（2）输出的形式：
若正确操作则会输出操作后的整个链表，若操作错误则会提示失败。
（3）程序所能达到的功能：
完成单链表的生成，删除、插入、和排序、计算操作后的链表长度。
（4）测试数据：
A链表的生成：
输入要输入几个数据I=5，然后依次输入1，2，5，3.、4。
B删除操作：
输入要删除的位置sit=2，然后遍历链表得1，5,3,4；操作错误时会提示输入位置不对，操作失败。
C插入操作：
输入要删除的位置sit=2然后输入要插入的值tem=2，遍历链表得1，2，5，3，4；操作错误时会提示输入位置不对，操作失败。
D排序操作：
直接调用排序函数的排序结果为1，2，3，4，5。
E逆置操作：
直接调用逆置函数，结果5，4，3，2，1。
2．概要设计
make_list（PNODEPHEAD）;//创建链表
traveres_list（PNODEPHEAD）;//遍历链表
delete_list（PNODEPHEAD）;//删除链表中的元素
get_length（PNODEPHEAD）;//求表长
insert_list（PNODEPHEAD）;//插入新元素
sort_list（PNODEPHEAD）;//用冒泡排序将链表中的元素按大小排序
reverse_list（PNODEPHEAD）;//逆置链表
3．详细设计
1）节点：
typedefstructnode
{
intdata;//数据域
structnode*PNEXT;//指针域
}NODE,*PNODE;
2）单链表的操作：
①make_list（PNODEPHEAD）;//创建链表
{
生成一个新的节点，接在前一个节点上
}
②traveres_list（PNODEPHEAD）;//遍历链表
{
读取一个节点中的值，然后指向下一个节点。
}
③delete_list（PNODEPHEAD）;//删除链表中的元素
{
通过类似于遍历的方法到要删除的节点上，将其指针域指向下一个节点，然后释放该跳过的节点的内存空间。
}
④get_length（PNODEPHEAD）;//求表长
{
由头结点开始指向下一个节点，然后自增变量加一，直到结束。
}
⑤insert_list（PNODEPHEAD）;//插入新元素
{
生成一个新的节点，然后遍历到你要插入的位置，将该节点的指针指向新生成的节点，然后新生成的节点指向该节点的下一个节点。
}
⑥sort_list（PNODEPHEAD）;//用冒泡排序将链表中的元素按大小排序
{
运用类似冒泡排序数组的方式对链表中的数据进行排序。
}
⑦reverse_list（PNODEPHEAD）;//逆置链表
{
链表逆置。
}
设计如下：
#include
#include
#include
//************结点的结构体*************************************************
typedefstructnode
{
intdata;
structnode*PNEXT;
}NODE,*PNODE;
//*************************函数声明****************************************
voidmake_list（PNODEPHEAD）;//创建链表
voidtraveres_list（PNODEPHEAD）;//遍历链表
voiddelete_list（PNODEPHEAD）;//删除链表中的元素
intget_length（PNODEPHEAD）;//求表长
voidinsert_list（PNODEPHEAD）;//插入新元素
voidsort_list（PNODEPHEAD）;//用冒泡排序将链表中的元素按大小排序
voidreverse_list（PNODEPHEAD）;//逆置链表
//*************************************************************************
//主函数，用于测试函数是否正确
voidmain（）
{
PNODEPHEAD=（PNODE）malloc（sizeof（NODE））;
if（NULL==PHEAD）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
printf（"（建立链表）\n"）;
make_list（PHEAD）;
traveres_list（PHEAD）;
printf（"\n"）;
printf（"（删除链表中的元素）\n"）;
delete_list（PHEAD）;
traveres_list（PHEAD）;
printf（"\n"）;
printf（"（插入新的元素）\n"）;
insert_list（PHEAD）;
traveres_list（PHEAD）;
printf（"\n"）;
printf（"（对链表进行排序）\n"）;
sort_list（PHEAD）;
traveres_list（PHEAD）;
printf（"\n"）;
printf（"（逆置链表）\n"）;
reverse_list（PHEAD）;
traveres_list（PHEAD）;
printf（"\n"）;
intlength=get_length（PHEAD）;
printf（"链表的最终长度为length=%d\n",length）;
}
//********************函数体*********************************************
voidmake_list（PNODEPHEAD）
{
inti=0;
inttem=0;//临时储存数据的变量
PNODEPMOVE=PHEAD;
PMOVE->PNEXT=NULL;
printf（"请输入有几个数据i="）;
scanf（"%d",&i）;
for（inta=0;a{
PNODEPNEW=（PNODE）malloc（sizeof（NODE））;
if（NULL==PNEW）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
printf（"输入第%d个数据tem=",a+1）;
scanf（"%d",&tem）;
PNEW->data=tem;
PNEW->PNEXT=NULL;
PMOVE->PNEXT=PNEW;
PMOVE=PMOVE->PNEXT;
}
}
voidtraveres_list（PNODEPHEAD）
{
PNODEPMOVE=（PNODE）malloc（sizeof（NODE））;
if（NULL==PMOVE）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
PMOVE=PHEAD->PNEXT;
while（NULL!
=PMOVE）
{
printf（"%d",PMOVE->data）;
PMOVE=PMOVE->PNEXT;
}
printf（"遍历结束。
\n"）;
}
intget_length（PNODEPHEAD）
{
PNODEPMOVE=（PNODE）malloc（sizeof（NODE））;
if（NULL==PMOVE）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
intlength=0;
PMOVE=PHEAD->PNEXT;
while（NULL!
=PMOVE）
{
length++;
PMOVE=PMOVE->PNEXT;
}
returnlength;
}
voiddelete_list（PNODEPHEAD）
{
PNODEPMOVE=（PNODE）malloc（sizeof（NODE））;
if（NULL==PMOVE）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
PMOVE=PHEAD;
inti;
printf（"请输入要删除的结点的位置sit="）;
scanf（"%d",&i）;
intlength=get_length（PHEAD）;
if（i<1||i>length）
{
printf（"输入的位置不对，删除失败。
\n"）;
return;
}
else
{
for（inta=0;a{
PMOVE=PMOVE->PNEXT;
}
PNODEPTEM=PMOVE->PNEXT;
PMOVE->PNEXT=PMOVE->PNEXT->PNEXT;
free（PTEM）;
}
}
voidinsert_list（PNODEPHEAD）
{
PNODEPMOVE=（PNODE）malloc（sizeof（NODE））;
if（NULL==PMOVE）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
PMOVE=PHEAD;
inti;
printf（"请输入要插入结点到的位置sit="）;
scanf（"%d",&i）;
intlength=get_length（PHEAD）;
if（i<0||i>length+1）
{
printf（"输入的位置不对，删除失败。
\n"）;
return;
}
else
{
for（inta=0;a{
PMOVE=PMOVE->PNEXT;
}
}
PNODEPTEM=PMOVE->PNEXT;
PNODEPNEW=（PNODE）malloc（sizeof（NODE））;
if（NULL==PNEW）
{
printf（"内存分配失败，程序结束。
\n"）;
exit（-1）;
}
printf（"输入新结点的数据tem="）;
scanf（"%d",&（PNEW->data））;
PMOVE->PNEXT=PNEW;
PNEW->PNEXT=PTEM;
}
voidsort_list（PNODEPHEAD）
{
inti,b,tem;
PNODEPMOVE=PHEAD;
for（i=get_length（PHEAD）;i>0;i--）
{
PMOVE=PHEAD;
for（b=0;b{
if（PMOVE->data>PMOVE->PNEXT->data）
{
tem=PMOVE->PNEXT->data;
PMOVE->PNEXT->data=PMOVE->data;
PMOVE->data=tem;
}
PMOVE=PMOVE->PNEXT;
}
}
}
voidreverse_list（PNODEPHEAD）
{
PNODEPMOVE_1,PMOVE_2;
PMOVE_1=PHEAD->PNEXT;
PHEAD->PNEXT=NULL;
while（NULL!
=PMOVE_1）
{
PMOVE_2=PMOVE_1;
PMOVE_1=PMOVE_1->PNEXT;
PMOVE_2->PNEXT=PHEAD->PNEXT;
PHEAD->PNEXT=PMOVE_2;
}
}
/*
************运行结果************
（建立链表）
请输入有几个数据i=3
输入第1个数据tem=1
输入第2个数据tem=2
输入第3个数据tem=3
123遍历结束。
（删除链表中的元素）
请输入要删除的结点的位置sit=2
13遍历结束。
（插入新的元素）
请输入要插入结点到的位置sit=2
输入新结点的数据tem=5
153遍历结束。
（对链表进行排序）
135遍历结束。
（逆置链表）
531遍历结束。
链表的最终长度为length=3
Pressanykeytocontinue
*********************************
*/
4．调试分析
如果遇到用vc进行程序检查时没有错误，但是会运行会弹出白框，则是说明你程序中有指针有指向不明确的地方，程序不行进行的不准确而报错。
5．用户使用说明
程序名为list_all.exe运行为dos，根据相应中的提示输入既可。
6．测试结果
7．附录
文件list_all.cpp为该程序的软件包。
make_list（PNODEPHEAD）;//创建链表
traveres_list（PNODEPHEAD）;//遍历链表
delete_list（PNODEPHEAD）;//删除链表中的元素
get_length（PNODEPHEAD）;//求表长
insert_list（PNODEPHEAD）;//插入新元素
sort_list（PNODEPHEAD）;//用冒泡排序将链表中的元素按大小排序
reverse_list（PNODEPHEAD）;//逆置链表
四、课程设计体会
对链表的基本操作的了解。
升级会员 