数据结构程序设计课程设计报告.doc

贵州航天职业技术学院

数据结构程序设计课程设计

课题名称：链表操作

专 业： 计算机软件技术
班 级： 09软件二
学 号： A093GZ053020152
姓 名： 韦 治 成
指导老师： 陆 树 芬
时 间： 2011-6-2

摘要
此次课程设计主要是为了实现对链表的创建、查找、删除、插入操作，设计主要分为主程序（Main.cpp）、头文件（hh.h）、实现函数（view.cpp）三个多文件操作从而形成一个小型的链表操作系统。
小型系统初步实现了对链表创建、查找、删除、插入的基本功能，程序中运用程序模块设计思想将程序合理的进行模块化使得程序从空间、时间上进行了合理的设计。程序主要由以下函数组成：create（）、find（）、del（）、insert（）等，程序合理的通过函数调用以及合理的参数传递顺利的完成了链表的功能。一个好的程序还需要一个良好的用户界面，程序中制作了一个简单、大方、明了的界面是程序更加完善。

关键字：链表 数据 指针

目 录
摘要 2
目 录 3
需求分析 4
2.1系统需求分析 4
2.2 系统运行环境和开发平台分析 4
算法设计分析 4
3.1 功能分析 4
3.2 算法设计分析 4
系统分析流程图 5
4.1系统模块设计流程图 5
系统详细设计 6
5.1 链表创建界面 6
5.2 菜单界面 7
5.4删除界面 9
5.5 插入界面 10
5.6 退出操作 10
总结： 11
源代码清单： 12

一、课程设计的要求
利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。
需求分析
2.1系统需求分析
分析了数据结构中单链表的建立、查找、插入和删除运算的实现,并附以图示和相应的具体程序。
2.2 系统运行环境和开发平台分析
WindowsXP操作系统，VC++ 6.0
算法设计分析
3.1 功能分析
首先通过定义一个动态链表结点的结构体，然后根据结构体定义相应的操作：
（1）定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备工作。
（2） 定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个结点是否存在。
（3） 定义删除结点的操作，这个算法用于对链表中某个多余结点的删除工作。
（4） 定义插入结点的算法，通过定义这个算法并结合这查找前驱后继的算法便可以在链表的任何位置进行插入一个新的结点。
（5） 定义退出函数，通过调用这个函数，可以退出当前系统。
3.2 算法设计分析
1.建立链表：动态的申请新的结点，不断地将新的结点插入表尾，修改表尾指针；最后返回表头指针；
2.插入：此程序采用前插，需要*p的前趋*q，然后再完成在*q之后插入*s的后插。
3.删除：删除*p需要先找到*p的前趋结点*q,然后完成指针的变化操作即可；

4.查找：此程序采用按值查找法，从第一个结点起判断当前结点的值是否等于给定值，若找到则返回该结点地址，否则继续下一个结点；若整个表中未找到则返回NULL；
6.输出：类似求表长，设一个移动指针扫描整个链表，将扫描到的值逐个输出，并且在其余几个函数中可反复调用此函数；
系统分析流程图
4.1系统模块设计流程图

4.2主要算法和流程图及说明

系统详细设计
5.1 链表创建界面
输入要创建的链表，向链表键入数据，中间用空格分开，最后以问号为结束标记，按回车进入菜单，如图5.1。
图 5.1
5.2 菜单界面
进入菜单界面，按1-4选择菜单，按回车，进入函数功能块，实现功能的效果，如图5.2。

图5.2

5.3 查找界面
按1键进入查找结点界面，输入要查找结点的序号（input j），执行结果就是序号所对应的数据，如图5.3。
图5.3

5.4删除界面
按2键进入删除结点界面，输入要删除链表中已知数据，然后再输出删除后的链表，如图5.4
图 5.4
5.5 插入界面
按3键进入插入结点界面，输入要插入链表中的位置，然后再输入要插入的数据（后插方式），如图5.5
图5.5
5.6 退出操作
按4键直接退出系统。

总结：

源代码清单：
Main.cpp
#include<stdio.h> /*头文件操作*/
#include<stdlib.h>
#include<iostream.h>
#include"hh.h"
void main() /*主程序*/
{
int i; /*定义参数*/
int j,x,position,m=0,n=0,y;
NODE *a,*b,*d,*e;
a=create();
/*菜单制作*/
do
{
cout<<"**********************链表的操作************************"<<endl;
cout<<"* *"<<endl;
cout<<"* 1.查找结点 *"<<endl;
cout<<"* *"<<endl;
cout<<"* 2.删除结点 *"<<endl;
cout<<"* *"<<endl;
cout<<"* 3.插入结点 *"<<endl;
cout<<"* *"<<endl;
cout<<"* 4.退出操作 *"<<endl;
cout<<"* *"<<endl;
cout<<"********************************************************"<<endl;
scanf("%d",&i);
switch(i)
{
case 1:printf("\nInput j:"); /*查找函数相关参数*/
scanf("%d",&j);
b=find(a,j);
if(b!=NULL)
{
printf("find:");
printf("%5d",b->data);
printf("\n");
}
else
{printf("error!");
printf("\n");}
break;
case 2:printf("\nInput y:"); /*删除函数相关参数*/
scanf("%5d",&y);
del(a,y);
e=a;
e=e->next;
printf("\nOutput the list:");
while(e!=NULL)
{
printf("%5d",e->data);
e=e->next;
}printf("\n");break;
case 3:d=a->next; /*插入函数相关参数*/
while(d!=NULL)
{
d=d->next;
n++;
}
d=a;
do
{
printf("\nInput position (again):");
scanf("%d",&position);
}while((position>n)||position<0);
printf("\nInput x:");
scanf("%d",&x);
while(m!=position)
{
d=d->next;
m++;
}
insert(d,x);
printf("\nOutput the list:");
while(a->next!=NULL)
{
a=a->next;
printf("%5d",a->data);
}printf("\n");printf("插入成功！！");
printf("\n");break;
case 4:exit(0);break;

default :cout<<"\ninput is error!!"<<endl;
}
}
while(i<5);
}

view.cpp
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include"hh.h"

NODE *create() /*此函数采用后插入方式建立链表，并返回一个指向链表表头的指针*/
{
NODE *head,*q,*p; /*定义指针变量*/
char ch;
int a;
head=(NODE *)malloc(sizeof(NODE)); /*申请新的存储空间，建立表头结点*/
q=head;
ch='*';
printf("\nInput the list:(?为结束标记)");
while(ch!='?') /*“ch”为是否建立新结点的标志，若“ch”为“？”则输入结束*/
{
scanf("%d",&a); /*输入新元素*/
p=(NODE *)malloc(sizeof(NODE));
p->data=a;
q->next=p;
q=p;
ch=getchar(); /*读入输入与否的标志*/
}
q->next=NULL;
return(head); /*返回表头指针*/
}

void insert(NODE *d,int x) /*在链表的d结点位置后插入给定元素x*/
{
NODE *q;
q=(NODE *)malloc(sizeof(NODE)); /*申请新的存储空间*/
q->data=x;
q->next=d->next;
d->next=q;
}

NODE *find(NODE *head,int i) /*在已知链表中查找序号为i的结点*/
{
int j=1;
NODE *p;
p=head->next;
while((p!=NULL)&&(j<i)) /*未到表尾且未找到序号为i的结点*/
{
p=p->next; /*指向下一个元素*/
j++;
}
return(p);
}

void del(NODE *head,int x) /*删除链表中的给定元素x*/
{
NODE *p,*q;
q=head;
p=q->next;
while((p!=NULL)&&(p->data!=x)) /*查找要删除的函数*/
{
q=p;
p=p->next;
}
if(p==NULL)
printf("%d not found.\n",x); /*x结点为找到*/
else
{
q->next=p->next; /*链接x直接后继结点*/
free(p); /*删除x结点，释放x结点空间*/
}
}

hh.h
typedef struct node /*定义结点的存储结构*/
{
int data;
struct node *next;
}NODE;
NODE *create(); /*创建函数*/
void insert(NODE *P,int x); /*插入函数*/
NODE *find(NODE *head,int i); /*查找函数*/
void del(NODE *head,int x); /*删除函数*/