郑州科技学院
数据结构课程设计
设计题目:单链表的基本算法应用
所在院系: 信息工程学院
专业班级:16级计算机科学与技术3班
学生姓名:黄 桂 亚
学 号: 201642304696
指导教师:李 瑞 霞
2018年3月13号
目录
l 单链表的简介
l 课题题目要求
l 需求分析
l 概要设计
l 详细设计
l 调试分析
l 测试结果
l 总结思考
l 附件
一、单链表的简介
链表中的数据是以结点来表示的，每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
以"结点的序列"表示线性表称作线性链表(单链表)
单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
因此，查找第 i 个数据元素的基本操作为:移动指针，比较 j 和 i
1、链接存储方法
链接方式存储的线性表简称为链表(Linked List)。
链表的具体存储表示为:
① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的，也可以是不连续的)
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))
注意:
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
2、链表的结点结构
┌───┬───┐
│data │ next│
└───┴───┘
data域--存放结点值的数据域
next域--存放结点的直接后继的地址(位置)的指针域(链域)
注意:
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表(Single Linked List)。
【例】线性表(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示如示意图
3、头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。
注意:
链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。
4、单链表的一般图示法
由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表(bat，cat，fat，hat，jat，lat，mat)的单链表就可以表示为下图形式。
5、单链表类型描述
typedef char DataType; //假设结点的数据域类型为字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
6、指针变量和结点变量
①生成结点变量的标准函数
p=( ListNode *)malloc(sizeof(ListNode));
//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中
②释放结点变量空间的标准函数
free(p);//释放p所指的结点变量空间
③结点分量的访问
利用结点变量的名字*p访问结点分量
方法一:(*p).data和(*p).next
方法二:p->data和p->next
④指针变量p和结点变量*p的关系
指针变量p的值--结点地址
结点变量*p的值--结点内容
(*p).data的值--p指针所指结点的data域的值
(*p).next的值--*p后继结点的地址
*((*p).next)--*p后继结点
链表操作中动态存储分配要使用标准函数，先介绍一下这些函数。
(1)malloc(size)
在内存的动态存储区申请一个长度为size字节的连续空间。
(2)calloc(n，size)
在内存的动态存储区申请n个长度为size字节的连续空间，函数返回值为分配空间的首地址。若此函数未被成功执行，函数返回值为0。
(3)free(p)
释放由指针p所指向的存储单元，而存储单元的大小是最近一次调用malloc()或calloc()函数时所申请的存储空间。
在头文件\"stdlib.h"中包含了这些函数的信息，使用这些函数时需在程序开头用文件包含指令#include"stdlib.h"指明。
另请读者注意，调用动态存储分配函数返回的指针是指向void类型或char类型的指针，在具体使用时，要根据所指向的数据进行强制类型转换。
单链表的建立有头插法、尾插法两种方法。
1.头插法
单链表是用户不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的左边称为链头，右边称为链尾。头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。
由于链表的长度是随机的，故用一个while循环来控制链表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。申请存储空间可使用malloc()函数实现，需设立一申请单元指针，但malloc()函数得到的指针并不是指向结构体的指针，需使用强制类型转换，将其转换成结构体型指针。刚开始时，链表还没建立，是一空链表，head指针为NULL。
链表建立的过程是申请空间、得到数据、建立链接的循环处理过程。
2.尾插法
若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针p2、申请单元指针pl。尾插法最先得到的是头结点。
二、课题题目要求
（1）编写一个程序，实现单链表的各种基本运算.
（2）编辑平台选用MicrosoftVisual++6.0
（3）在设计过程中，按功能定义函数或书写多个文件，进行板块设计，各个功能模块用函数的形式实现。
三、需求分析
建立一个单链表，实现单链表的初始化，插入，输出等功能，以确定某个元素在单链表中的位置
（1）初始化单链表L；
（2）依次采用尾插法插入a,b,c,d,e元素；
（3）输出单链表L；
（4）输出单链表L的长度；
（5）判断单链表L是否为空；
（6）输出单链表L的第3个元素；
（7）输出元素a的位置；
（8）在第4个元素位置上插入f元素；
（9）输出单链表L；
函数的调用关系
四、概要设计
（1）为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：
ADT LinearList {
数据对象：D={i|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
结构关系：R={<ai,ai+1>|ai,ai+1 ∈D}
基本操作：InitList_L(L)
操作前提：L是一个未初始化的线性表
操作结果：将L初始化为一个空的线性表
CreateList_L(L)
操作前提：L是一个已初始化的空表
操作结果：建立一个非空的线性表L
ListInsert_L(L,pos,e)
操作前提：线性表L已存在
操作结果：将元素e插入到线性表L的pos位置
ListDelete_L(L,pos,e)
操作前提：线性表L已存在
操作结果：将线性表L中pos位置的元素删除，
删除的元素值通过e返回
LocateList_L(L,e)
操作前提：线性表L已存在
操作结果：在线性表L中查找元素e，
若存在，返回元素在表中的序号位置；
若不存在，返回-1
DestroyList_L(&L)
初始条件：线性表L已存在
操作结果：销毁线性表
ListEmpty_L(L)
初始条件：线性表已存在
操作结果：若L为空表，则返回ERROR，否则返回FALSE
ListLength_L(L)
初始条件：线性表L已存在
操作结果：返回L中数据元素个数
GetElem_L(L,I,&e)
初始条件：线性表L已存在
操作结果：用e返回L中第i个数据元素值
}
（2） 本程序包含10个函数：
• 主函数main()
• 初始化单链表函数InitList_L()
• 显示单链表内容函数DispList_L()
• 插入元素函数ListInsert_L()
• 删除元素函数ListDelete_L()
• 查找元素函数LocateList_L()
• 创建链表函数CreateList_L()
• 链表元素长度函数ListLength_L()
• 判断链表是否为空函数ListEmpty_L()
• 取值函数GetElem_L()
各函数间调用关系如下：
( 3) 主函数的伪码
{ 说明一个单链表 L ；
初始化 L ；
建立L ；
显示L ；
}
五、详细设计
采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义如下：
（1） 类型定义
typedef int ElemType;
typedef struct LNode
{ ElemType data; //数据域
struct LNode *next; //指针域
} LNode,* LinkList;
（2） 基本操作的伪码算法
● 初始化
Bool InitLinkList(LinkList *L)
{ *L=申请新结点;
如果申请失败，返回失败标志；
(*L)->next=NULL;
返回成功标志；
}
● 建立单链表
Bool CrtLinkList(LinkList L)
/* L是已经初始化好的空链表的头指针，通过键盘输入元素值，
利用尾插法建单链表L */
{ rear=L;
打印输入提示：“请输入若干个正整数（用空格分隔），并用 -1 结束：”
读入一个数x;
当x不是结束标志时，循环做如下处理：
{
申请一个新结点s；
如果申请失败，返回失败标志；
将x送到s的data域;
rear->next=s;
rear=s;
读入下一个数x;
}
rear->next=NULL;
返回成功标志；
}
● 显示单链表（输出）
void DispLinkList(LinkList L)
{
p=首元素结点地址;
while ( p不空 )
{
打印结点p 的元素值；
p=下一个结点地址;
}
}
● 插入操作
bool InsLinkList(LinkList L, intpos, ElemType e)
/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/
{
从“头”开始，查找第i-1个结点 pre ;
if (查找失败)
{ 显示参数错误信息;
return ERROR;
}
else
{
申请一个新的结点s ;
将e放入s的数据域;
将s 插到pre 后面;
return OK;
}● 查找操作
int LocLinkList(LinkList L, ElemType e)
/ * 在带头结点的单链表L中查找其结点值等于e的结点，
若找到则返回该结点的序号位置k，否则返回 -1 */
{
p=首元素结点地址;
while ( p不空 )
if (p->data!=e)
{ p=p->next; k++; }
else break;
if ( p 不空 ) return k;
else return -1;
}
六、调试分析
开始运行时会出现Debug Error，DAMAGE:After Normal block， 搜索后了解到是内存越界操作，检查后发现内存分配L和S=(LinkList)malloc(sizeof(LNode))写成了=(LinkList)malloc(sizeof(LinkList))，修改后正常。
七、测试结果
I=4插入元素f
八、总结思考
1、LinkList和ListNode是不同名字的同一个指针类型(命名的不同是为了概念上更明确)
2、*LinkList类型的指针变量head表示它是单链表的头指针
3、ListNode类型的指针变量p表示它是指向某一结点的指针
4、若指针变量p的值为空(NULL)，则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。
5、有关指针类型的意义和说明方式的详细解释
可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
因此，在单链表中第 i 个结点之前进行插入的基本操作为:
找到线性表中第i-1个结点，然后修改其指向后继的指针。
6、插入时，当i在合理范围时，元素能够准确插入；当i超出下限时，元素能够插入，但总是插入第一个位置；当i超出上限时，元素不能插入。
八、附件
#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode,*LinkList;
Status InitList_L(LinkList &L) { //初始化线性表
L=(LinkList)malloc(sizeof(LNode)); //L指向头节点，头节点数据域为空
L->next=NULL;
return OK;
}// InitList_L
Status DispList_L(LinkList &L) { //输出线性表
LinkList p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
return OK;
} // DispList_L
Status CreateList_L(LinkList &L,ElemType a[],int n) { //尾插法建表
LinkList s,r;int i;
L=(LinkList)malloc(sizeof(LNode));
r=L;
for(i=0;i<n;i++)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=a;
r->next=s;
r=s;
}
r->next=NULL;
return OK;
}// CreateList_L
Status ListLength_L(LinkList L) { //求线性表的长度
LinkList p=L;int n=0;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return(n);
}// ListLength_L
Status ListEmpty_L(LinkList L) { //判断单链表是否为空
return(L->next==NULL);
}// ListEmpty_L
Status DestroyList_L(LinkList &L) { //销毁线性表
LinkListp=L,q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
return OK;
}// DestroyList_L
Status GetElem_L(LinkList L, int i, ElemType &e) {
// L为带头节点的单链表的头指针。
// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j=0;
LinkList p=L;
while(j<i&&p!=NULL)
{
j++;p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
e=p->data;
return OK;
}
}// GetElem_L
Status ListInsert_L(LinkList &L, int i, ElemType e) { //插入数据元素
int j=0;
LinkList p=L,s;
/*
找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素
*/
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
}// ListInsret_L
Status ListDelete_L(LinkList &L, int i, ElemType &e){ //删除数据元素
int j=0;
LinkList p=L,q;
while(j<i-1&&p!=NULL) //查找删除元素的前一个节点
{
j++;
p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
q=p->next; //q为要删除的元素节点
if(q==NULL)
{
return ERROR;
}
e=q->data; //e为删除节点的数据区域
p->next=q->next;
free(q);
return OK;
}
}// ListDelete_L
int LocateElem_L(LinkList L, ElemType e) { //按元素值查找元素
LinkList p=L->next;
int i=1;
while(p!=NULL&&p->data!=e)
{
p=p->next;i++;
}
//如果要插入的节点为头节点，则退出
if(p==NULL)
{
return ERROR;
}
else
{
return(i);
}
}// LocateElem_L
int main() {
ElemTypee,a[5]={'a','b','c','d','e'};
LinkList L;
printf("(1)初始化单链表L\n");
InitList_L(L); //初始化单链表L
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
CreateList_L(L,&a[0],5); //依次采用尾插入法插入a，b，c，d，e元素
printf("(3)输出单链表L：");
DispList_L(L); //输出单链表L
printf("\n");
printf("(4)单链表L的长度为：");
printf("%d",ListLength_L(L)); //输出单链表L的长度
printf("\n");
if(ListEmpty_L(L))
{
printf("(5)该单链表为空\n");
}
else
{
printf("(5)该单链表不为空\n"); //判断单链表L是否为空
}
GetElem_L(L,3,e);
printf("(6)单链表L的第三个元素为：");
printf("%c",e); printf("\n"); //输出单链表L的第3个元素
printf("(7)单链表L中a的位置为：");
printf("%d",LocateElem_L(L,'a')); //输出元素'a'的位置
printf("\n");
ListInsert_L(L,4,'f'); //在第4个元素位置插入'f'元素
printf("(8)在第4个元素位置上插入 f 元素\n");
printf("(9)输出单链表L：");
DispList_L(L); //输出单链表L
printf("\n");
return 0;
}
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
