单链表参考答案.docx
- 文档编号:11709783
- 上传时间:2023-06-02
- 格式:DOCX
- 页数:15
- 大小:40.21KB
单链表参考答案.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);//逆置链表 四、课程设计体会 对链表的基本操作的了解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单链表 参考答案