数据结构课程设计单链表Word文档格式.docx
《数据结构课程设计单链表Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计单链表Word文档格式.docx（21页珍藏版）》请在冰点文库上搜索。
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表（SingleLinkedList）。
3、头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。
链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。
2.2实验的基本要求（软硬件）
用VC++6.0软件平台，操作系统：
WindowsXP硬件：
内存要求：
内存大小在256MB，其他配置一般就行。
2.3算法的设计思想
（a）定义一个创建链表的函数，通过该头插法创建一个带头结点的链表，在接下来的链表操作中使用。
（b）定义输出链表的算法，遍历结点的指针域判断是否为空，如果不为空则输出其数据域，直到指针域为空为止。
（c）定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进行比较，如果查找到则返回并输出，如入查找失败则返回错误提示信息。
（d）定义插入结点的算法，首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。
（e）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保留，查找到需删除的结点，将其删除，并将其后继结点连到其前驱结点。
2.4相关图例
2.4.1单链表的结点结构
如图2-1所示,为单链表的结点结构示意图：
图2-1单链表的结点结构
2.4.2算法流程图
如图2-2所示，为此算法流程图：
开始
定义结构体Node
构建各种对链表操作的函数（插入、删除、查找、输出），并写出相应的算法及实现过程
创建一个单链表，用于之前所定义的函数对其进行操作
按要求输出结果
结束
图2-2算法流程图
3实验结果
3.1链表的建立
图3-1链表的建立
3.2单链表的插入
图3-2单链表的插入
3.3单链表的输出
图3-3输出单链表元素
3.4查找元素
图3-4查找成功
图3-5查找失败
3.5单链表的删除
图3-6删除成功
图3-6删除失败
3.6显示链表中的元素个数（计数）
图3-7输出长度
4结果分析
4.1单链表的结构
一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此通常情况下用箭头来表示链域中的指针，于是链表就可以更直观的画成用箭头链接起来的结点序列，如下图所示：
A
B
C
D
E^
H
图4-1单链表的示例图
4.2单链表的操作特点
4.2.1顺链操作技术
从“头”开始，访问单链表L中的结点i（p指向该节点）时，由于第i个结点的地址在第i-1个结点（pre指向该结点，为p的前驱）的指针域中存放，查找必须从单链表的“首结点”开始（p=L）；
通过p=p->
next并辅助计数器来实现。
4.2.2指针保留技术
通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域进行链址操作（pre->
next），因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系，将这种技术称为“指针保留技术”。
4.3链表处理中的相关技术
1）单链表与多重链表的差别在于指针域的个数。
2）判断当前结点p是否为表尾。
一半链表中，p结点是表尾的条件是：
该节点的后继结点为空指针，即p->
next==NULL;
3）链表的长度并未显示保存。
由于链表是动态生成的结构，其长度要通过顺链查找到表尾得到。
因此在处理链表时，往往是以当前处理结点p是否为表尾作为控制条件，而不是长度n作为控制条件。
5设计体会及今后的改进意见
通过这次实验加深了我对于单链表的进一步了解，了解到了单链表在内存中的存储结构，最重要的是学会了如何运用C语言将单链表的建立，插入、删除、添加等操作。
在程序实现中也遇到了一些困难，在单链表初始化时，使用了0作为结束输入符，导致单链表不能存储数据0；
单链表中只能存储相同类型的数据，在存储不同类型的数据时需要改变输入结束标志，程序通用性比较差。
在进行程序设计的时候没有考虑好删除和查找的方式，只进行了输入元素的查找和删除，而且进行链表的插入时，只考虑了头插法在结尾插入，而没有考虑输入结点插入等，程序的灵活性比较低。
通过这次课程设计，让我充分认识到数据结构在编写程序方面的重要地位。
不仅仅是单链表的操作，还有栈和队列等特殊的单链表操作，以及其他一些常用的数据结构对于程序的效率和内存使用有很大的帮助。
我希望在接下来的学习中收获更多的东西。
参考文献
[1]耿国华.数据结构--用C语言描述[M].北京:
高等教育出版社,2011.6.
[2]谭浩强.C程序设计[M].北京:
清华大学出版社,2004.6.
附录代码：
结构体定义：
#pragmaonce
#include<
stdio.h>
stdlib.h>
enummy_enum
{
_EXIT,
_CREATE,
_INSERT,
_PRINT,
_SEARCH,
_DELETE,
_COUNT,
};
staticintcount=0;
typedefintElemtype;
typedefstructNode/*单链表结构体的定义*/
Elemtypedata;
structNode*next;
}
Node,*LinkList;
voidtest（）;
/*测试函数*/
voidmain_menu（）;
//主菜单函数
voidCreatFromHead（LinkList*l）;
/*头插法建立单链表*/
voidInsert（LinkListl）;
//单链表的插入
voidPrint（LinkListl）;
/*单链表的输出*/
intSearch（LinkListl,Elemtypee）;
//查找指定的元素
voidDeletelist（LinkListl,Elemtypee）;
//删除元素
voidCount（）;
//计数
voidCREATE（LinkList*head）;
voidINSERT（LinkList*head）;
voidPRINT（LinkList*head）;
voidSEARCH（LinkList*head）;
voidDELET（LinkList*head）;
voidCOUNT（）;
单链表操作函数：
#define_CRT_SECURE_NO_WARNINGS
#include"
linklist.h"
voidmain_menu（）
printf（"
\t单链表的简单操作\t\t\n\n"
）;
\t1单链表的建立\n"
\t2单链表的插入\n"
\t3单链表的输出\n"
\t4单链表的查找\n"
\t5单链表的删除\n"
\t6单链表的长度\n"
\t0退出\n"
voidCreatFromHead（LinkList*l）/*头插法建立单链表*/
Node*s;
intc=0;
intflag=1;
*l=（Node*）malloc（sizeof（Node））;
if（*l==NULL）
{
printf（"
申请空间失败！
！
\n"
return;
}
（*l）->
next=NULL;
while（flag）
scanf（"
%d"
&
c）;
if（c!
=0）
{
s=（Node*）malloc（sizeof（Node））;
if（s==NULL）
{
printf（"
return;
}
s->
data=c;
next=（*l）->
next;
（*l）->
next=s;
count++;
}
elseflag=0;
voidInsert（LinkListl）//单链表的插入
intinsert=0;
Node*s=NULL;
请输入需要插入的元素：
"
scanf（"
insert）;
s=（Node*）malloc（sizeof（Node））;
if（s==NULL）
while（l->
next!
=NULL）
l=l->
s->
data=insert;
next=l->
l->
count++;
voidPrint（LinkListl）/*单链表的遍历*/
Node*p;
p=l->
while（p!
%d"
p->
data）;
p=p->
intSearch（LinkListl,Elemtypee）//查找指定的元素
while（（l!
=NULL）&
&
（l->
data!
=e））
if（l==NULL）
return-1;
//查找失败
else
return1;
//查找成功
voidDeletelist（LinkListl,Elemtypee）//删除节点
Node*p,*r,*q;
q=l;
if（p->
data==e）
r=p;
p=r->
q->
next=p;
count--;
free（r）;
break;
else
q=p;
/*保留前驱节点*/
p=p->
if（p==NULL）
删除失败，没有找到相应的元素\n"
voidCount（）
单链表中一共有%d个元素\n"
count）;
voidCREATE（LinkList*head）
请建立单链表用“0”来结束输入\n"
CreatFromHead（head）;
初始化后的单链表为：
Print（*head）;
voidINSERT（LinkList*head）
Insert（*head）;
插入后的单链表为：
voidPRINT（LinkList*head）
单链表的输出为：
voidSEARCH（LinkList*head）
intsearch=0;
intret=0;
请输入需要查找的元素：
search）;
ret=Search（*head,search）;
if（1==ret）
查找成功\n"
查找失败\n"
voidDELET（LinkList*head）
intdelet=0;
请输入需要删除的元素：
delet）;
Deletelist（*head,delet）;
删除之后的单链表为：
voidCOUNT（）
Count（）;
主菜单函数：
intmain（）/*主函数*/
test（）;
return0;
voidtest（）//测试函数
intinput=1;
Node*head=NULL;
main_menu（）;
while（input!
=_EXIT）
input）;
switch（input）
case_CREATE:
CREATE（&
head）;
//创建
case_INSERT:
INSERT（&
//插入
case_PRINT:
PRINT（&
//输出
case_SEARCH:
SEARCH（&
//查找
case_DELETE:
DELET（&
//删除
case_COUNT:
COUNT（）;
case_EXIT:
exit（0）;
//退出
default:
main_menu（）;
free（head）;
升级会员 