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

昆明理工大学信息工程与自动化学院学生上机报告

（ 2012 — 2013 学年 第 一 学期 ）

课程名称：数据结构 开课实验室：信自楼444 2012 年 10 月8日 年级、专业、物联网111 学号 201110410119 姓名 雷林尚 成绩 班 实验项目名称 线性表顺序存储运算的算法实现 指导教师 姜瑛 教师评语 教师签名： 年 月 日 上机（一）

一、上机目的：

1、掌握线性表顺序存储结构的C语言描述； 2、体会last域在算法实现所起的作用；

3、理解合理的存储结构设计与算法实现的存在的关系 二、上机要求： 1、程序功能：

（1）.（菜单）主程序； （2）.表的建立及初始化； （3）.表的数据插入； （4）.表的数据删除； （4）.表的数据输出； 2、 实验报告：

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

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

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

- 1 -

为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\

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

输*/

- 2 -

return c; }

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

int n,j=1;

if(L->length>=maxlen) {

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

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

for(int i=0;iprintf(\"Data[%d]:\ scanf(\"%d\ L->length++; }

return(n-1); }

int insert(seqlist *L,datatype x,int i) { int j;

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

if(L->length>=maxlen)

- 3 -

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

{

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 int n;

- 4 -

printf(\"表中的元素为：\\n\"); for(n=0;nlength;n++) {

printf(\"%d \ }

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\");

break;

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

- 5 -

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

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

scanf(\"%d\

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

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

scanf(\"%d\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）.总结合理的数据结构设计与算法实现存在的关系；

- 6 -