《数据结构》实验报告

院系  应用科技学院专业电子信息工程           

姓名  ##         学号 

10 级 电信班 20## 年 10 月 11日

1.实验目的

       1.掌握线性表的基本运算。

       2.掌握顺序村存储的概念，学会对顺序存储数据结构进行操作。

       3.加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力。

2.需求分析

      要求用c语言编写一个演示程序，首先建立一个空表，然后根据用户选择，能够在线性表的任意位置实现插入元素、删除元素、初始化线性表、查找某一元素的在线性表中得位置。

       （1）建立线性表的功能

l  输入的形式和输入的范围：调用出入函数，输入插入的位置和数值，用逗号隔开

l  输出的形式：调用输出函数，按顺序输出线性表所插入的值，以及所对应功能的值。

（2）插入功能

l  输入的形式和输入值的范围：输入一个表示位置的正整数和一个表示插入元素值的正整数，两个正整数之间用逗号隔开，出入位置的和法取值范围是1

l  输出的形式：如果输入的参数合法，则按顺序显示插入后的线性表，否则显示错误。

（3）删除功能

l  输入的形式和输入值的范围：输入一个表示删除位置或要删除的元素值的正整数，删除位置或删除元素值的取值范围是1

l  输出的形式：如果输入参数合法，则按顺序显示删除后线性表中的各个元素值，否则显示参数错误的信息。

（4）查找功能

l  输入的形式和输入值的范围：输入一个要查找的元素值，元素值的合法取值范围是正整数。

l  输出的形式：如果存在要查找的元素，则显示要查找元素的位置，否则显示参数错误信息。

3.概要设计 

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

Typedef struct LinearList{

       Int *list;

       Int size;

       Int MAXSIZE;      

}List;

 基本操作：

l  初始化线性表ListInit (L)

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

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

l  向空表指定位置插入元素  ListInsert (L)

操作前提：L是一个还有位置的线性表

操作结果：将元素插入到指定位子并输出线性表

l  删除指定元素值  ListDelete_1（L）

操作前提：线性表L存在

操作结果：将线性表中指定的元素值删除，并输出线性表

l  删除指定位置的元素值  ListDelete_2（L）

操作前提：线性表L存在

操作结果：将线性表中指定位置的元素值删除，并输出线性表

l  查找线性表中的元素  ListFind（L）

操作前提：线性表L存在

操作结果：在线性表L中查找指定元素e，若存在该元素返回该元素在表中的位置，否则提示错误

l  输出线性表元素 OutputList(L)

操作前提：线性表存在

操作结果：输出整线性表L的所有元素值

       （2）本程序共有6函数：

l  主函数main()

l  初始化线性表函数InitList()

l  输出函数OutputList()

l  插入函数ListInsert()

l  删除函数ListDelete()

l  查找函数ListFind()

各函数的关系如下：

l  主函数Main()调用初始化线性表函数InitList()、插入函数ListInsert()、删除函数ListDelete()、查找函数ListFind()、查找函数ListFind()

l  插入函数ListInsert()调用输出函数OutputList(L)

l  删除函数ListDelete()调用输出函数OutputList(L)

l  查找函数ListFind()调用输出函数OutputList(L)

（3）主函数的伪码

              Main()

              {     定义一个字符参数 ch;

                     定义整形元素位置参数 i；

                     定义整形参数e,j=1;

                     说明一个线性表L;

                     循环做下面处理，直到读入的为‘y’时推出：

{

              根据具体选项，读入需要的数据，做下面的选择处理，知道循环结束：

{

      

根据所选择选项调用相关的函数进行处理，然后输出处理后的线性表以及所要执行的内容。

}

}

}

4.详细设计

            采用线性表实现概要设计中的定义的抽象数据类型，有关数据数据类型和伪码算法定义如下：

       （1）类型定义

                     typedef struct LinearList       

{

                            int *list;                       

int size;                              

                            int MAXSIZE;                           

}List;

       （2）基本操作的伪码算法

l  初始化

void InitList(List  &L)

{

       构造一个空表L；

           定义空表长度为0；

           初始存储空间的容量；

}

l  插入操作

void ListInsert(List &L, int i, int e)

{

       Int *p；

       判断位置i是否合法 不合法返回空；

       判断当前容量是否已满

              {

                     申请一个新的基止newbase;

                     L.list=newbase;

                     增加存储容量；

}

                       定义插入位置*q；

  p＞=q;

  --p) *(p+1) = *p; 

插入元素e；

表长加1；

}

l  删除操作

int ListDelete_1(List &L, int e, int &i)

{

       定义三个指针*p,*q,*m;

       P=L.list;;

       循环做下面处理

{

       If(*p=e);

{

       m=p;

       q=L.list+L.size-1;

       被删除元素之后的元素左移；

       表长减1；

     continue;

       p++;

} i++;

}  return 1；

}

l  查找操作

int ListFind(List L, int e)

/*在顺序线性表L中查找第1个值与e满足compare()的元素的位序。

  若找到，则返回其在L中的位序，否则返回0。*/

{    

定义第一元素的存储位置为1；

       P=首元素的地址；

       While（i不能超过表长）

                     ++I;

       if (i ＜= L.size)

         return i;

      else

         return 0;

}

5.使用说明

       程序名为实验1.exe，程序执行过程如下：

             

       运行程序显示如下菜单：

              printf("\t\t\t      ---线 性 表---         \n");

              printf("\n\t\t\t********************************");

              printf("\n\t\t\t*    1-----初 始 化            *");

              printf("\n\t\t\t*    2-----插入元数值          *");

              printf("\n\t\t\t*    3-----删除指定元素值      *");

              printf("\n\t\t\t*    4-----删除指定位置        *");

              printf("\n\t\t\t*    5-----查找线性表中的元素  *");

              printf("\n\t\t\t*    6-----输出线性表元素      *");

              printf("\n\t\t\t*    0-----退    出            *");

              printf("\n\t\t\t********************************\n");

              printf("请选择菜单号(0-6): "); 

       用户输入0~6的数字，选择执行相应的功能。

每执行一次功能，就会显示执行的结果以及执行后线性表的内容。

l  选择0：提示是否退出程序，输入y退出，输入n返回菜单。

l  选择1：初始化线性表

l  选择2：提示“请输入位置i和数值e：”，要求用户输入一个表示插入元素位置的

和一个表示插入元素的正整数，两个数之间用空格隔开。如果插入合法，按顺序输出线性表，否则提示错误！

l  选择3： 提示“请输入要删除的元素值e：”，要求用户输入一个表示删除元素的正

整数， 删除元素的合法范围是正整数。如果输入参数合法，按顺序输出线性表，否则提示错误！

l  选择4：提示“请输入要删除的指定位置i:”， 要求用户输入一个表示删除位置的

正整数， 删除位置的合法范围是1到当前线性表的长度。如果输入参数合法，按顺序输出线性表，否则提示错误！

l  选择5：提示“请输入线性表中要查找的元素e:”，要求用户输入一个要查找的元

素值，元素的合法范围是正整数。如果输入元素值合法，输出所查找元素值在线性表中的位置，否则提示错误！

l  选择6：直接输出整个线性表。

6.测试结果

      程序运行显示一下菜单：

         ---线性表---                 ********************************

           *    1-----初始化             *

           *    2-----插入元数值           *

           *    3-----删除指定元素值       *

           *    4-----删除指定位置         *

           *    5-----查找线性表中的元素   *

           *    6-----输出线性表元素       *

           *    0-----退    出             *

           ********************************

请选择菜单号(0-6):

（1）初始化操作：

l  选择1

初始化线性表

屏幕提示“初始化成功！”

再次提示选择菜单

       （2）插入操作：

l  选择2

屏幕提示“请输入位置i和数值e:”

输入1 1

屏幕显示输出线性表元素:1 插入成功！

屏幕显示选择菜单

l  选择2

屏幕提示“请输入位置i和数值e:”

输入2 2

屏幕显示输出线性表元素:1 插入成功！

屏幕显示选择菜单

l  选择2

屏幕提示“请输入位置i和数值e:”

输入3 3

屏幕显示输出线性表元素:1 插入成功！

屏幕显示选择菜单

l  选择2

屏幕提示“请输入位置i和数值e:”

输入5 5

屏幕显示插入位置错误！输出线性表元素:1

屏幕显示选择菜单

      （3）删除指定元素值操作：

l  选择    3

屏幕提示“请输入要删除的元素值e:” 

               输入2后，

            屏幕显示输出线性表：1 3删除成功！再次显示选择菜单   

l  选择4

屏幕提示“请输入要删除的指定位置i:”     

               输入1后，

               屏幕显示输出线性表：3删除成功！再次显示选择菜单

       （4）删除指定位置元素操作：

l   选择4

屏幕显示“请输入要删除的指定位置i:”

输入2

屏幕显示删除成功！

输出线性表元素有：1 3

    （5）查找操作：

l  选择5

屏幕显示“请输入线性表中要查找的元素e:”

输入3，

屏幕显示该元数值在线性表中第 3 位

输出线性表元素:1 2 3

输入 4，

屏幕显示该元素值不在线性表中，并输出线性表元素：1 2 3

再次回到选择菜单

       （6）显示：

l  选择6

屏幕显示线性表元素有:1 2 3

再次回到选择菜单

   （7）退出：

l  选择0，

屏幕提示“是否真的退出程序y/n:”

输入n，

屏幕显示请重新选择...:   再次显示程序选择菜单

输入y，

屏幕显示退出程序！Press any key to continue