用C语言设计顺序表的相关函数库.doc

胡 洁 《用C语言设计顺序表的相关函数》 第16页 共16 页

用C语言设计顺序表的相关函数库

学生姓名：胡洁 指导老师：黄敏

摘 要 本课程设计主要是设计顺序表的相关函数库，以便在程序设计中调用。在此课程设计中，系统开发平台为Windows XP，程序设计语言采用面向过程的程序设计的C语言，程序运行平台为Visual C++ 6.0。在程序设计中，采用了结构化与面向过程两种解决问题的方法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。

关键词 顺序表；程序设计；函数库；Visual C++ 6.0

1 引 言

本课程设计主要解决的是设计顺序表的相关函数，以便在程序调用中调用，进行顺序表中元素的输入、查找、取出、删除等操作的课程设计。
顺序表是线性表的顺序存储，是指在内存中用一段地址连续的存储空间来依次顺序存放线性表中的各元素的存储方式。其逻辑上与物理上均相邻，不会增加额外的存储开销；顺序表具有按序号随机访问的特点，采取直接存取结构，若提供序号访问数据元素，则其算法简洁、快速、易读、易懂。[1][2]

1.1 课程设计目的
（1） 训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；
（2） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
（3） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
（4） 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
1.2 课程设计任务和要求
（1） 任务：
设计出顺序表结构的相关函数库，以便在程序设计中调用。
（2）要求：
①包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）；
②最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；
③给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。

2 数据库中的函数
2.1 函数库中函数清单
在此课程设计中主要是设计顺序表的函数库，以便于调用，其函数清单如表2-1所示。
表2-1 顺序表函数库清单
函数声明
功能声明
int Insert_Seqlist();
插入一个元素到顺序表中，若空间已满及插入位置无效报错，否则插入成功。
int Delete_Seqlist();
删除顺序表中的一个元素，若表为空及删除位置不合法报错，否则删除成功。
int Locate_Seqlist();
若查找元素存在，则返回元素存储位置。
int Get_Seqlist()；
若查找元素存在，则返回元素下标。
void print();
输出顺序表中的所有元素。

2.2 函数实现的具体算法列举

（1）插入函数：
int Insert_Seqlist(Seqlist *L,int i,datatype e)
{ int j;
if(L->len==MAXSIZE-1)
{printf("表满溢出\n");return -1;} /*表空间已满，不能插入*/
if(i<1||i>L->len+2) /*检查插入位置i是否有效*/
{ printf("位置错\n");return 0;}
for(j=L->len;j>=i-1;j--)
L->data[j+1]=L->data[j]; /*节点往后移动一个位置*/
L->data[i-1]=e; /*插入新元素e*/
L->len++; /*len仍指向最后一个元素*/
return 1; /*插入操作成功，返回*/
}

（2）删除函数：
int Delete_Seqlist(Seqlist *L,int i)
{
int j;
if(i<1||i>L->len+1) /*检查空表及删除位置的合法性*/
{ printf("不存在第d%个元素\n,i");return 0;}
for(j=i;j<L->len;j++)
L->data[j-1]=L->data[j]; /*向前移动一个位置*/
L->len--;
return 1; /*删除成功*/
}

（3）取出一个元素函数：
int Get_Seqlist(Seqlist *L,int i)
{
if(i<1||i>L->len+1) /*检查查找位置的合法性*/
{printf("不存在第d%个元素\n",i);return 0;} /*查找元素不存在*/
else return L->data[i-1]; /*查找成功，返回该元素下标*/
}

3 课程设计思路

一般地说，其过程如下：
a.分析顺序表特点
b.分析顺序表功能以及操作
c.设计函数库
d.制定调试计划：初步的调试计划
e.编写主函数，方面后面的测试
f.制定完整程序的测试计划
g.书写文档：系统说明
h.复核和审查:从技术的角度审查，从管理的角度审查。

3.1 分析顺序表
（1）顺序表的优点：
方法简单，各种高级语言中都有数组，容易实现；逻辑上相邻，物理上也相邻，所以不需要指针来体现数据元素间的逻辑关系，不增加额外的存储开销；顺序表具有按序号随机访问的特点，采取直接存取结构，若提供序号访问数据元素，则其算法简洁、快速。易读、易懂。

（2） 顺序表的缺点：
等概率情况下做插入和删除操作时，需要平均移动大约表中一半的元素，所以如果n较大，则做插入和删除的效率较低；一般采用数组来定义顺序表，而数组是一种静态分配结构，不是执行时按需分配空间，所以为了操作方便，一般都会预先分配足够大的存储空间，但如果预先分配过大，则可能导致顺序表后部空间大量闲置，造成空间浪费，如果预先分配过小，则又会因空间不足造成溢出；由于数组需要占用连续的空间存储，所以一些累计数量虽然超过所需要存储空间，但不连续的零散空间并不能得到利用，造成“碎片”现象，从而导致整个内存空间利用率下降。[1][3][4]
而课程设计中，我们着重考虑的是顺序表的结构，对于顺序表，我们可以进行的操作有输入、插入、删除、取出等。

3.2 设计函数库
设计函数库不能随心所欲、想编写什么函数就编写什么函数，而是要根据分析顺序表所得结果，从分析结果入手。又分析我们知道顺序表可以进行的操作有：输入、输出、插入一个元素、删除一个元素、查找一个元素、取出一个元素。根据这些操作分别写出函数：
int Insert_Seqlist(); /*插入元素*/
int Delete_Seqlist(); /*删除元素*/
int Locate_Seqlist(); /*查找元素*/
int Get_Seqlist()； /*取出元素*/
void print(); /*输出元素*/

3.3 编写主函数
函数库设计完之后，还要进行调试，就需要编写一个主函数来测试函数的有效性与正确性。在主函数中调用函数库中的函数实现其功能，主函数中使用一个switch功能进行条件判断，当输入选项不一样的时候，调用的函数不一样，从而对顺序表中的元素实现不同的操作。

3.4 书写文档
按着格式编写文档并检查，保证论文没有错误。

4 程序运行结果

4.1 确定顺序表中元素个数
在程序中，顺序表元素的个数以及元素都是自己在运行时进行输入的，输入完后按Enter进入选项选择。其显示如图4-1：

4-1输入元素
4.2 显示顺序表中所有元素
利用switch的功能输入1显示所有元素，结果如图4-2:

4-2显示所有元素

4.3 在顺序表中插入一个元素
利用switch的功能输入2插入一个元素，结果如图4-3:

4-3插入一个元素
4.4 删除顺序表中一个元素
利用switch的功能输入3删除一个元素，结果如图4-4:

4-4删除一个元素
4.5 确定顺序表中元素个数
利用switch的功能输入4按值查找一个元素，结果如图4-5:

4-5按值查找一个元素

4.6 取出顺序表中一个元素
利用switch的功能输入5取出一个元素，结果如图4-6:

4-6取出一个元素
4.7 退出程序
利用switch功能输入6退出程序。

5 结束语

在课程设计中，使用C语言来设计顺序表的相关函数库，C语言是一门面向过程的高级语言。设计代码时，要尽量考虑完备，把可能出现的情况都想到。顺序表的函数库中，要考虑顺序表的结构，在物理上也是相邻，所以很容易查找到某个存在的数据的位置、下标，若已知序号，也很容易找到元素。将函数库写出来以后，在以后程序需要利用函数时，无须每次都写一次函数，可以节约精力与时间。
在之前的学习中，就了解了顺序表的特点以及功能，通过此次的课程设计，更加加深了我对顺序存储这种结构的认识，既回顾了以前的东西，也发现了很多以前都没遇见过的问题，收获很大。

参考文献
[1] 陈倩诒，邓红卫. 数据结构（C语言版）. 武汉：华中科技大学出版社，2013
[2] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，1997
[3] 许卓群，杨冬青，唐世渭，等.数据结构与算法[M]. 北京：高等教育出版社，2006
[4] 徐孝凯. 数据结构简明教程. 北京：清华大学出版社，1995年

附录1：结构化设计源程序清单
// 程序名称：SXB.CPP
// 程序功能：利用C语言设计顺序表的函数库，以便于调用函数时调用。
// 程序作者：胡洁
// 最后修改日期：2013-7-7

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int datatype;
typedef struct
{ datatype data[MAXSIZE];
int len;
}Seqlist; /*将data和len封装成一个结构体*/
Seqlist *Init_Seqlist()
{ Seqlist *L;
L=(Seqlist*)malloc(sizeof(Seqlist));
L->len=-1;
return L;
} /*顺序表初始化*/
int Insert_Seqlist(Seqlist *L,int i,datatype e)
{ int j;
if(L->len==MAXSIZE-1)
{printf("表满溢出\n");return -1;} /*表空间已满，不能插入*/
if(i<1||i>L->len+2) /*检查插入位置i是否有效*/
{ printf("位置错\n");return 0;}
for(j=L->len;j>=i-1;j--)
L->data[j+1]=L->data[j]; /*节点往后移动一个位置*/
L->data[i-1]=e; /*插入新元素e*/
L->len++; /*len仍指向最后一个元素*/
return 1; /*插入操作成功，返回*/
}
int Delete_Seqlist(Seqlist *L,int i)
{
int j;
if(i<1||i>L->len+1) /*检查空表及删除位置的合法性*/
{ printf("不存在第d%个元素\n,i");return 0;}
for(j=i;j<L->len;j++)
L->data[j-1]=L->data[j]; /*向前移动一个位置*/
L->len--;
return 1; /*删除成功*/
}
int Locate_Seqlist(Seqlist *L,datatype e)
{
int i=0;
while(i<=L->len && L->data[i]!=e)
i++;
if(i>L->len) return -1; /*查找失败*/
else return i; /*返回存储位置*/
}
int Get_Seqlist(Seqlist *L,int i)
{
if(i<1||i>L->len+1) /*检查查找位置的合法性*/
{printf("不存在第d%个元素\n",i);return 0;} /*查找元素不存在*/
else return L->data[i-1]; /*查找成功，返回该元素下标*/
}
void print(Seqlist *L)
{
int s;for(s=0;s<L->len;s++)
printf("%d ",L->data[s]); /*输出顺序表中所有元素*/
printf("\n");
}
main()
{
Seqlist *L;
int i,j,s,e,m,flag=1;
L=Init_Seqlist();
printf("请输入表长：");
scanf("%d",&i);L->len=i;
printf("请输入%d个元素值：",i); /*确定表长*/
for(s=0;s<i;s++)
scanf("%d",&L->data[s]); /*输入表中元素*/
while(flag) /*使用标识flag*/
{
printf("请选择：\n");
printf("1:显示所有元素\n");
printf("2:加入一个元素\n");
printf("3:删除一个元素\n");
printf("4:按值查找一个元素\n");
printf("5:取出一个元素\n");
printf("6:退出程序\n"); /*输入顺序表元素之后显示选项*/
scanf("%d",&j);
switch(j) /*当输入数字j时自动调用函数库中的函数实现功能*/
{
case 1:{print(L);break;}
case 2:{printf("输入需要插入的位置和数值：");
scanf("%d %d",&i,&e);
m=Insert_Seqlist(L,i,e);
if(m)
{printf("插入之后的线性表："); /*显示插入元素后的顺序表*/
print(L);
}
break;
}
case 3:{printf("输入需要删除的位置：");
scanf("%d",&i);
m=Delete_Seqlist(L,i);
if(m)
{printf("删除之后的线性表："); /*显示删除元素后的顺序表*/
print(L);
}
break;
}
case 4:{printf("输入需要查找的数值：");
scanf("%d",&e);
m=Locate_Seqlist(L,e);
if(m!=-1)
{
printf("存在该数据元素,它在表中的下标为:");
printf("%d\n",m); /*输出元素在表中的下标*/
}
else printf("所查找的元素不存在!\n"); /*不存在报错*/
break;
}
case 5:{printf("取出第n个元素:");
scanf("%d",&i);
m=Get_Seqlist(L,i);
if(m)
{
printf("所取的数据元素为：");
printf("%d\n",L->data[i-1]); /*输出所取元素*/
}
else printf("输入序号超出范围!\n"); /*输入不合法报错*/
break;
}
case 6:flag=0;printf("程序结束,按任意键退出!\n"); /*按条件选择功能*/
}
}
return 0;
}