合肥学院 

计算机科学与技术系

课程设计报告

2003～20##学年第二学期

2014 年 9月

一、     问题分析和任务定义

1.1题    目：设计顺序表结构的相关函数库，以便在程序设计中调用。要求：（1）实现顺序表的各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

1.2要    求：实现顺序表的各种基本函数以及常用函数；给出1-2个例子，通过调用自己的库函数来实现问题的求解。

1.3具体任务：设计出顺序表结构的相关函数库，以便在程序设计中调用。

2、实现功能： 

    设计顺序表的相关函数，以便在程序调用中调用，进行顺序表中元素的插

入、查找、取出、删除等操作。

3、测试用例：

   3.1正确数据：请正确输入4个元素：1 2 3 4

                 请选择：

                 1：显示所有元素

                 2：增加一个元素

                 3：按数值删除某个元素

                 4：按位置删除某个元素

                 5：按位置更新

                 6：按数值更新

                 7：按位置查找某元素

                 8：按值查找某元素

                 9：退出程序

                 3

                 需要删除的元素：4

                 显示结果为：1 2 3

   3.2错误数据：请正确输入4个元素：1  5 4 2

               

 请选择：

                 1：显示所有元素

                 2：增加一个元素

                 3：按数值删除某个元素

                 4：按位置删除某个元素

                 5：按位置更新

                 6：按数值更新

                 7：按位置查找某元素

                 8：按值查找某元素

                 9：退出程序

                 4

                 需要输入删除的位置：2

                 显示结果为：1 5 4

  

问题分析: 本题用顺序表结构的相关函数库，以便在程序设计中调用。程序中主要是调用子函数来实现各种功能，同时用switch来进行选操作，从而实现题目说要求的各种功能。

二、数据结构的选择和概要设计

（1）      为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：

    基本操作：

      SqLsetnull (L)

        操作前提：L是一个未初始化的线性表

        操作结果：将L初始化为一个空的线性表

        操作前提：L是一个已初始化的空表

        操作结果：建立一个非空的线性表L

      SqLinsert (L,s,i)

        操作前提：线性表L已存在

        操作结果：将元素s插入到线性表L的i位置

      SqLdelete (L,i)

        操作前提：线性表L已存在

        操作结果：将线性表L中i位置的元素删除，

      SqLlocate (L,x)

        操作前提：线性表L已存在

        操作结果：在线性表L中查找元素x，

若存在，返回元素在表中的序号位置；

若不存在，返回-1

            SqLlength_L(L)

              初始条件：线性表L已存在

              操作结果：返回L中数据元素个数

           

SqLget (L,i)

              初始条件：线性表L已存在

              操作结果：判断第i个数据元素值是否存在，存在则返回1；否则，返回0；

（2）      本程序包含10个函数：

?   主函数main()

?   初始化顺序表函数SqLsetnull ()

?   显示顺序表内容函数print（）

?   插入元素函数SqLinsert ()

?   删除元素函数SqLdelete ()

?   查找元素函数SqLlocate ()

?   取值函数SqLget ()

?   判表满

各函数间调用关系如下：

 

( 3 ) 主函数的代码

main()

{ 说明一个单链表 L ；

初始化 L ；

  建立 L ；

  显示 L ；

}

顺序表函数库清单

3、详细设计和编码

详细设计：

1） 类型定义：

  typedef struct

{ Datatype data[maxlen];

  int last;

}Sequenlist; /*将data和len封装成一个结构体*/

2） 顺序表初始化：

Sequenlist  *SqLsetnull()

{

Sequenlist *L;

L=(Sequenlist*)malloc(sizeof(Sequenlist));

 L->last=-1;

 return(L);

}

3） 子函数

输出函数

void print(Sequenlist *L)

{

  int h;

  printf("显示结果为: ");

  for(h=0;h<L->last+1;h++)

  {

 printf("%d ",L->data[h]);

  }/*输出顺序表中所有元素*/

  printf("\n"); 

  }

判表满 

int SqLempty(Sequenlist *L)

{

    if(L->last+1>=50)

        return(1);

    else

        return(0);

}

插入函数

int SqLinsert(Sequenlist *L,Datatype s,int i)

{

    int j;

    if(SqLempty(L)==1)

    {

        printf("表满溢出\n");

        return(0);

    }

    else if(i<1||i>L->last+2)

    {

        printf("位置出错\n");

        return(0);

    }

    else

    {

    for(j=L->last;j>=i-1;j--)

       L->data[j+1]=L->data[j];/*节点往后移动一个位置*/

    L->data[i-1]=s;                       /*插入新元素s*/

    L->last++;                            /*last仍指向最后一个元素*/

    return (1); 

    }

取数函数

int SqLget(Sequenlist *L, int i)

{

    int x;

    if(i<1||i>L->last+1)

    {  

        printf("取数出错！");

        return (0);

    }

    else

        x=L->data[i-1];

    return (1) ;

}

更新函数

   int SqLupdate(Sequenlist *L,int i,int s)

{

    if(i<1||i>L->last+2)

    {

        printf("位置出错\n");

        return(0);

    }

    else

    {

      L->data[i-1]=s;

    return (1); 

    }

}

其中用switch来做选择操作，从而实现个子函数对应的功能。

4、上机调试

在调试过程中要特别注意函数调用时参数的传递问题，用数组名作为参数可进行传值调用，因而可将函数中的运行结果传递给主调函数，得出正确结果；再一个要注意的是输出结果时，循环结束的条件应为：i==’#’时退出循环。另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作少量调整和改动。

程序执行时出现越界的情况主要是编写程序时未考虑这方面，例如在按位置删除时超越了操作范围，必须做越界处理，后通过改正才能正确运行。还有些常见小错误，例如执行结果间没空格或空行导致执行结果看不清。

通过这些让我认识到编写程序必须严谨，否则会出现大量的错误，甚至你自己都难以发现，导致你会花更多的时间去修改，得不偿失。

5、测试结果及其分析

执行情况如下：请正确输入4个元素：1 2 3 4

                 请选择：

                 1：显示所有元素

                 2：增加一个元素

                 3：按数值删除某个元素

                 4：按位置删除某个元素

                 5：按位置更新

                 6：按数值更新

                 7：按位置查找某元素

                 8：按值查找某元素

                 9：退出程序

                 3

                 需要删除的元素：4

                 显示结果为：1 2 3

测试结果截图如下：

 

6、用户使用说明

程序执行后，首先输出：

“请输入表长：”n

输入表长后，输出：

“请输入n个元素值：”

输入n个元素值后，输出：

“请选择：”

任意选择指定操作的某一操作序号：如3

“输入需要删除的元素”

然后程序自动执行结果并显示出来

图5.运行结果

7、参考文献

1.王昆仑，李红。《数据结构与算法》。北京：中国铁道出版社，20##年9月第二版

2.马睿，孙丽云。《数据结构与算法(C语言版)》。北京：北京邮电大学出版社，20##年

3.陈文博，朱青《数据结构与算法》，机械工业出版社，1996年

4.许卓群，张乃孝，杨冬青，唐世渭《数据结构》，高等教育出版社，1988年

5.李廉治，姜文清，郭福顺《数据结构》，大连理工大学出版社，1989年

8、附录

#include<stdio.h>

#include<stdlib.h>

#include<kuhanshu.h>

main()

 {

 Sequenlist *L;

 int i,j,t,s,h,m,n,flag=1;

 L=SqLsetnull();

 printf("请输入表长：");

 scanf("%d",&i);L->last=i-1;

 printf("请输入%d个元素值：",i);            /*确定表长*/

 for(t=0;t<i;t++)

 scanf("%d",&L->data[t]);                 /*输入表中元素*/

 while(flag) /*使用标识flag*/

 {

     printf("请选择：\n");

 printf("1:显示所有元素\n");

 printf("2:增加一个元素\n");

 printf("3:按数值删除某个元素\n");

 printf("4:按位置删除某元素\n");

 printf("5:按位置更改\n");

 printf("6:按数值更改\n");

 printf("7:按位置查找（取）元素\n");

 printf("8:按值查找一个元素\n");

 printf("9:退出程序\n");                  /*输入顺序表元素之后显示选项*/

 scanf("%d",&j);

  switch(j)                     /*当输入数字j时自动调用函数库中的函数实现功能*/

 {

        case 1:{print(L);break;}

        case 2:

            {

                printf("输入需要插入的数值和位置：");

                scanf("%d %d",&s,&i);

                h=SqLinsert(L,s,i);

                if(h)

                {printf("插入之后的线性表：");               /*显示插入元素后的顺序表*/

                print(L);

                }

            break;

            }

         case 3:

             {

             printf("输入需要删除的元素：");

             scanf("%d",&s);

             Delete_x(L,s);               /*显示删除元素后的顺序表*/

             print(L);

             break;

                }

        case 4:

             {

                 printf("输入需要删除的数值位置：");

                 scanf("%d",&s);

                 h=SqLdelete(L,s);

                printf("\n");

                if(h)

                {

                 printf("删除之后的线性表：\n");                /*显示删除元素后的顺序表*/

                 print(L);

                }

              break;

                }

               

        case 5:{

               

                printf("输入需要更改的位置和更改后的数据：");

                scanf("%d %d",&m,&n);

                h=SqLupdate(L,m,n);

                if(h)

                {printf("插入之后的线性表：");               /*显示更新元素后的顺序表*/

                print(L);

                }

            break;

            }

        case 6:{

               

                printf("输入需要更改的数");

                scanf("%d",&m);

                Update_x(L,m);

                 print(L);

                 break;

            }

        case 7:{

                 printf("取出第n个元素:");

                 scanf("%d",&i);

                 h=SqLget(L,i);

                 if(h)

                 {

                     printf("所取的数据元素为：");

                     printf("%d\n",L->data[i-1]);              /*输出所取元素*/

                 }

                 else

                     printf("输入序号超出范围!\n");          /*输入不合法报错*/

                 break;

               }

         case 8:

             {

                 printf("输入需要查找的数值：");

                 scanf("%d",&s);

                 SqLlocate(L,s);

                 printf("\n");

                 break;

             }

         case 9:

             flag=0;

             printf("程序结束,按任意键退出!\n"); 

}

}

}

库函数：（kuhanshu.h）

typedef int Datatype;

typedef struct

{ Datatype data[50];

  int last;

}Sequenlist;

Sequenlist  *SqLsetnull()

{

 Sequenlist *L;

 L=(Sequenlist*)malloc(sizeof(Sequenlist));

 L->last=-1;

 return(L);

}

void print(Sequenlist *L)

{

 int h;

 printf("显示结果为: ");

 for(h=0;h<L->last+1;h++)

 {

 printf("%d ",L->data[h]);

 }/*输出顺序表中所有元素*/

 printf("\n"); 

 }

int SqLempty(Sequenlist *L)

{

    if(L->last+1>=50)

        return(1);

    else

        return(0);

}

int SqLinsert(Sequenlist *L,Datatype s,int i)

{

    int j;

    if(SqLempty(L)==1)

    {

        printf("表满溢出\n");

        return(0);

    }

    else if(i<1||i>L->last+2)

    {

        printf("位置出错\n");

        return(0);

    }

    else

    {

    for(j=L->last;j>=i-1;j--)

       L->data[j+1]=L->data[j];/*节点往后移动一个位置*/

    L->data[i-1]=s;                       /*插入新元素s*/

    L->last++;                            /*last仍指向最后一个元素*/

    return (1); 

    }

}

int SqLdelete(Sequenlist *L,int i)

{

    int j;

    if(L->last<0)

    {

        printf("顺序表空！");

        return(0);

    }

    else if(i<1||(i>L->last+1)) /*检查空表及删除位置的合法性*/

    {

        printf("参数出错！");

        return(0);

    }

    else

    {

        for(j=i;j<=L->last+1;j++)

            L->data[j-1]=L->data[j];

        L->last--;

        return(1);

    }

}

int SqLupdate(Sequenlist *L,int i,int s)

{

    if(i<1||i>L->last+2)

    {

        printf("位置出错\n");

        return(0);

    }

    else

    {

      L->data[i-1]=s;

    return (1); 

    }

}

int SqLget(Sequenlist *L, int i)

{

    int x;

    if(i<1||i>L->last+1)

    {  

        printf("取数出错！");

        return (0);

    }

    else

        x=L->data[i-1];

    return (1) ;

}

void SqLlocate(Sequenlist *L,int x)

{

   int i,z=0;

   for(i=0;i<L->last+1;i++)

   {

       if(L->data[i]==x)

       {

           printf("该元素的位置为：%d",i+1);

           z=1;

       }

   }

   if(z==0)

       printf("不存在此元素！");

}

void Delete_x(Sequenlist *L,int x)

{

     int j,k,z=0;

     for(j=0;j<L->last+1;j++){

         if(L->data[j]==x) {               

            for(k=j;k<L->last+1;k++){

                L->data[k]=L->data[k+1];  /*向前移动一个位置*/

                }

                L->last--;

                j--;  /*返回到删除的位置*/

                z=1;

            }

        }

    if(z==0)

       printf("不存在此元素！");   

}

void Update_x(Sequenlist *L,int x)

{

     int j,k,z=0,t=1;

     for(j=0;j<L->last+1;j++)

     {

         if(L->data[j]==x)

         {   

             printf("将第%d次出现的数%d更改为：",t,x);

             scanf("%d",&k);

             L->data[j]=k;

             z=1;

             t++;

   

         }

       

}

        if(z==0)

       printf("不存在此元素！");                   

}