线性表顺序存储结构的C语言描述

（ 2012  — 2013 学年 第  一  学期 ）

课程名称：数据结构      开课实验室：信自楼444    2012 年 10 月8日

一、上机目的：

       1、掌握线性表顺序存储结构的C语言描述；

       2、体会last域在算法实现所起的作用；

       3、理解合理的存储结构设计与算法实现的存在的关系

二、上机要求：

       1、程序功能：

        （1）.（菜单）主程序；

        （2）.表的建立及初始化；

        （3）.表的数据插入；

        （4）.表的数据删除；

        （4）.表的数据输出；

       2、 实验报告：

（1）.上机通过的程序（清单）；

#include

#include

#define maxlen 1024 /* 线性表的最大长度设为1024*/

typedef int datatype; /* 设typedef(定义)datatype（数据类型）为int */

typedef struct

{

 datatype data[maxlen];

 int length;

} seqlist; 

/*菜单函数*/

int show()

{

   int

       c=0;                               /*定义变量*/

printf("\\n   **************************顺序表的基本操作运算****************************\\n\\n\\n");

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

   printf("                1.初始化线性表      2.线性表的插入      \\n\\n");

   printf("                3.线性表的删除      4.线性表的输出      \\n\\n");

   printf("                0.退出系统                              \\n\\n");

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

   printf("\\n请输入选项(0-4)选择您所需要对线性表的操作:");      

 do

   {   scanf("%c",&c);   }          

 while(!(c>='0'&&c<'5'));        /*验证选项是否合法,若否则重输*/

 return c;

}

int initializa(seqlist *L,datatype x)    //构造一个空的线性表。

{

   int n,j=1;

if(L->length>=maxlen)

    {

        printf("顺序表格已满，请退出运行");    

    }

   printf("\\n请输入顺序表的长度:");

   scanf("%d",&n);

for(int i=0;i    {

    printf("Data[%d]:",j);

scanf("%d",&L->data[i]);

L->length++;

    }  

   return(n-1);

}

int  insert(seqlist *L,datatype x,int i)

{

    int j;

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

    {

        printf("选择插入的位置错误，请退出运行");        

    }

if(L->length>=maxlen)

    {

        printf("顺序表格已满，请退出运行"); 

    }

 for(j=L->length-1;j>=i-1;j--)//从第i个结点开始后移

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

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

L->length++;

return 0;

}

void deleter(seqlist *L,int i)

{

  int j;

if(i<1||i>L->length)

  {

    printf("位置非法，退出运行！");

    exit(0);

  }

  for(j=i;jlength;j++)//从第i个结点开始前移

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

L->length--;

}

void output(seqlist *L)

{

    system("CLS");//清屏

    printf("\\n顺序表的内容为：\n\\n");

    printf("表长为:%d\\n",L->length);//表长为L->length

    int n;

    printf("表中的元素为：\n");

for(n=0;nlength;n++)

    {

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

    }

    printf("\\n");

}

int main()

{ 

seqlist *L;

int key=1;

int i=1,t;

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

L->length=0;

  while(key)

     switch(show())

        {

            case  '1':   {   printf("\\n\\n\\n"); initializa(L,i);output(L); }   break;

            case  '2':   {   printf("\\n\\n\\n"); 

                                printf("输入插入位置：\n");

                                scanf("%d",&i);

                                printf("输入插入元素：\n");

                                scanf("%d",&t);

                                insert(L,t,i);output(L);}    break;

            case  '3':   {   printf("\\n\\n\\n"); 

                                        printf("输入删除位置：\n");

                                            scanf("%d",&i);

                                            deleter(L,i); output(L);   }    break;

         case  '4':   {   printf("\\n\\n\\n"); output(L);  }      break;

            case  '0':    key=0;

         }    

return 0;

}

（2）.分析程序的空间复杂度和插入和删除的时间复杂度；

        （3）.说明last域在算法实现所起的作用；

        （4）.总结合理的数据结构设计与算法实现存在的关系；