数据结构课程设计-单链表.doc

数据结构课程设计
目录
1 选题背景2
2 方案与论证3
2.1 链表的概念和作用3
2。3 算法的设计思想4
2.4 相关图例5
2。4。1 单链表的结点结构5
2。4.2 算法流程图5
3 实验结果6
3。1 链表的建立6
3。2 单链表的插入6
3。3 单链表的输出7
3。4 查找元素7
3.5 单链表的删除8
3。6 显示链表中的元素个数(计数）9
4 结果分析10
4。1 单链表的结构10
4。2 单链表的操作特点10
4.2。1 顺链操作技术10
4。2.2 指针保留技术10
4。3 链表处理中的相关技术10
5 设计体会及今后的改进意见11
参考文献12
附录代码：13
1 选题背景
陈火旺院士把计算机60多年的发展成就概括为五个“一"：开辟一个新时代-——-信息时代，形成一个新产业————信息产业，产生一个新科学—--—计算机科学与技术，开创一种新的科研方法--—-计算方法，开辟一种新文化————计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。
数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。
2 方案与论证
2。1 链表的概念和作用
链表是一种链式存储结构，链表属于线性表,采用链式存储结构,也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针（指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
以“结点的序列”表示线性表称作线性链表(单链表)
单链表是链式存取的结构,为找第 i 个数据元素，必须先找到第 i-1 个数据元素.
因此,查找第 i 个数据元素的基本操作为：移动指针,比较 j 和 i
单链表
1、链接存储方法
链接方式存储的线性表简称为链表(Linked List)。
链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
② 链表中结点的逻辑次序和物理次序不一定相同.为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址(或位置）信息(称为指针(pointer)或链(link））
注意：
链式存储是最常用的存储方式之一,它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构.
2、链表的结点结构
┌───┬───┐
│data │next │
└───┴───┘
data域—-存放结点值的数据域
next域——存放结点的直接后继的地址(位置）的指针域（链域)
注意:
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的.
②每个结点只有一个链域的链表称为单链表（Single Linked List）.
3、头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。
注意:
链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空,即NULL.
2。2 实验的基本要求（软硬件）
用VC++6.0软件平台,操作系统：Windows XP 硬件:内存要求：内存大小在256MB，其他配置一般就行。
2。3 算法的设计思想
(a）定义一个创建链表的函数,通过该头插法创建一个带头结点的链表，在接下来的链表操作中使用.
(b）定义输出链表的算法 ，遍历结点的指针域判断是否为空,如果不为空则输出其数据域，直到指针域为空为止。
（c)定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进行比较，如果查找到则返回并输出，如入查找失败则返回错误提示信息.
(d）定义插入结点的算法,首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。
（e）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保留，查找到需删除的结点，将其删除,并将其后继结点连到其前驱结点.
2。4 相关图例
2。4。1 单链表的结点结构
如图2—1所示,为单链表的结点结构示意图:
Data域 Next域

图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〉
#include〈stdlib.h〉
enummy_enum
{
_EXIT,
_CREATE，
_INSERT，
_PRINT,
_SEARCH，
_DELETE,
_COUNT，
｝；
staticint count = 0；
typedefintElemtype；
typedefstructNode/＊单链表结构体的定义＊/
｛
Elemtype data;
structNode ＊next;
}
Node, *LinkList;
void test()；/＊测试函数＊/
void main_menu（）;//主菜单函数
void CreatFromHead(LinkList ＊l）；/＊头插法建立单链表＊/
void Insert（LinkList l）;//单链表的插入
void Print（LinkList l）;/＊单链表的输出*/
int Search(LinkList l， Elemtype e）；//查找指定的元素
void Deletelist（LinkList l, Elemtype e）；//删除元素
void Count（）；//计数
void CREATE（LinkList *head)；
void INSERT(LinkList *head）；
void PRINT（LinkList *head）；
void SEARCH（LinkList* head)；
void DELET（LinkList ＊head);
void COUNT(）；
单链表操作函数：
＃define_CRT_SECURE_NO_WARNINGS
#include"linklist。h"
void main_menu(）
｛
printf（"\t 单链表的简单操作\t\t\n\n”）；
printf（”\t 1 单链表的建立\n"）；
printf("\t 2 单链表的插入\n”);
printf("\t 3 单链表的输出\n”）；
printf（"\t 4 单链表的查找\n”）；
printf(”\t 5 单链表的删除\n")；
printf（"\t 6 单链表的长度\n"）；
printf（”\t 0 退出\n”）；
}
void CreatFromHead(LinkList ＊l）/*头插法建立单链表＊/
{
Node *s；
int c = 0；
int flag = 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(”申请空间失败！！\n”）;
return;
}
s->data = c;
s—>next = (*l）->next；
（＊l）-〉next = s；
count++;
}
else flag = 0；
｝
｝
void Insert(LinkListl)//单链表的插入
｛
int insert = 0；
Node ＊ s = NULL；
printf（"请输入需要插入的元素:”）；
scanf（”％d"， &insert）；
s = （Node＊）malloc（sizeof（Node）)；
if （s == NULL）
｛
printf（"申请空间失败！！\n"）；
return；
}
while (l—〉next ！= NULL）
｛
l = l-〉next；
｝
s—>data = insert;
s—>next = l—>next;
l-〉next = s;
count++；
｝
void Print(LinkListl)/*单链表的遍历＊/
｛
Node ＊p;
p = l—>next；
while （p ！= NULL)
｛
printf（"％d ", p-〉data）；
p = p—〉next；
｝
printf(”\n"）;
｝
int Search(LinkListl, Elemtypee）//查找指定的元素
｛
while (（l ！= NULL） ＆& (l->data ！= e)）
{
l = l->next;
}
if (l == NULL）
{
return —1;//查找失败
｝
else
｛
return 1;//查找成功
｝
｝
void Deletelist（LinkListl, Elemtypee）//删除节点
｛
Node ＊p， ＊r， *q；
p = l—〉next； q = l;
while （p ！= NULL）
{
if （p->data == e）
｛
r = p；
p = r—〉next；
q—〉next = p；
count-—；
free（r）;
break;
}
else
{
q = p;/＊保留前驱节点*/
p = p—〉next；
｝
｝
if （p == NULL)
｛
printf（"删除失败，没有找到相应的元素\n”）;
}
}
void Count（）
｛
printf（"单链表中一共有％d个元素\n”, count）;
｝
void CREATE（LinkList *head)
｛
printf(”请建立单链表用“0”来结束输入\n")；
CreatFromHead(head）；
printf（"初始化后的单链表为:”)；
Print（＊head)；
}
void INSERT（LinkList ＊head)
{
Insert（＊head）;
printf("插入后的单链表为:”）；
Print（＊head）;
}
void PRINT（LinkList ＊head）
{
printf（"单链表的输出为：")；
Print(*head）;
｝
void SEARCH（LinkList ＊head)
{
int search = 0;
int ret = 0；
printf（”请输入需要查找的元素："）；
scanf（"％d”, ＆search）；
ret = Search(＊head， search）;
if （1 == ret）
｛
printf(”查找成功\n”)；
}
else
｛
printf（"查找失败\n”）；
｝
｝
void DELET（LinkList ＊head）
{
int delet = 0；
printf（"请输入需要删除的元素：”)；
scanf（”%d”， ＆delet)；
Deletelist(＊head, delet）;
printf（"删除之后的单链表为:”）；
Print(*head)；
｝
void COUNT（）
{
Count（）；
｝
主菜单函数:
#define_CRT_SECURE_NO_WARNINGS
＃include"linklist.h"
int main（)/*主函数＊/
｛
test(）;
return 0；
}
void test（）//测试函数
{
int input = 1；
Node ＊ head = NULL；
main_menu（）;
while （input ！= _EXIT）
｛
scanf("％d”, &input)；
switch （input）
｛
case _CREATE：
｛
CREATE（&head)；//创建
break;
｝
case _INSERT：
｛
INSERT(＆head）；//插入
break；
｝
case _PRINT：
{
PRINT(&head）；//输出
break;
}
case _SEARCH：
{
SEARCH(＆head);//查找
break；
｝
case _DELETE：
{
DELET（＆head)；//删除
break；
}
case _COUNT:
｛
COUNT(）;//计数
break；
｝
case _EXIT：
｛
exit(0）;//退出
break;
｝
default:
｛
break;
｝
｝
main_menu（）；
｝
free（head）；
｝
11