顺序存储结构线性表基本操作 纯C语言实现
/////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现
//
// a simple example of Sq_List by C language
//
// by wangweinoo1[PG]
//--------------------------------------------------------- ///////////////////////////////////////////////////////////
#include
#include
//以下为函数运行结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 5 //线性表存储空间的初始分配量
#define LISTINCREMENT 1 //线性表存储空间分配增量
typedef int Status; //函数类型，其值为为函数结果状态代码
typedef int ElemType; //假设数据元素为整型
typedef struct
{
ElemType*elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量
}Sqlist;
//实现线性表的顺序存储结构的类型定义
static Sqlist L;//为了引用方便，定义为全局变量
static ElemType element;
///////////////////////////////////////
//函数名：InitList()
//参数：SqList L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
// 存储分配成功：OK
///////////////////////////////////////
Status InitList(Sqlist L)
{
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(L.elem==NULL)
exit(OVERFLOW);
else
{
L.length=0;
L.listsize=LISTINCREMENT;
return OK;
}
}
///////////////////////////////////////
//函数名：DestroyList()
//参数：SqList L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：L.elem==NULL:ERROR
// L.elem!=NULL:OK
///////////////////////////////////////
Status DestroyList(Sqlist L)
{
if(L.elem==NULL)
return ERROR;
else
free(L.elem);
return OK;
}
///////////////////////////////////////
//函数名：ClearList()
//参数：SqList L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：L.elem==NULL:ERROR
// L.elem!=NULL:OK
///////////////////////////////////////
Status ClearList(Sqlist L)
{
if(L.elem==NULL)
exit(ERROR);
int i;
ElemType*p_elem=L.elem;
for(i=0;i { *L.elem=NULL; L.elem++; } L.elem=p_elem; return OK; } /////////////////////////////////////// //函数名：ListEmpty() //参数：SqList L //初始条件：线性表L已存在 //功能：判断线性表是否为空 //返回值：空：TRUE // 非空：FALSE /////////////////////////////////////// Status ListEmpty(Sqlist L) { int i; ElemType*p_elem=L.elem; for(i=0;i { if(*L.elem!=0) { L.elem=p_elem; return FALSE; } L.elem++; } return TRUE; } /////////////////////////////////////// //函数名：ListLength() //参数：SqList L //初始条件：线性表L已存在 //功能：返回线性表长度 //返回值：线性表长度(L.length) /////////////////////////////////////// int ListLength(Sqlist L) { return L.length; } /////////////////////////////////////// //函数名：GetElem() //参数：SqList L,int i,ElemType *element //初始条件：线性表L已存在，1<=i<=ListLength(L) //功能：用e返回线性表中第i个元素的值 //返回值：(i<1)||(i>ListLength(L))：OVERFLOW // 1<=i<=ListLength(L)：OK /////////////////////////////////////// Status GetElem(Sqlist L,int i) { int j; ElemType*p_elem=L.elem; if(i<1||i>L.length) return OVERFLOW; for(j=1;j<=i;j++) L.elem++; element=*L.elem; L.elem=p_elem; return OK; } /////////////////////////////////////// //函数名：LocateElem() //参数：Sqlist L,ElemType element //初始条件：线性表L已存在 //功能：返回顺序表L中第1个与element相等的元素 //返回值：若在L中存在于element相等的元素：其位序// 若在L中不存在与element相等的元素：0 /////////////////////////////////////// int LocationElem(Sqlist L,ElemType element) { int i; ElemType*p_elem=L.elem; for(i=1;i { if(*L.elem==element) { L.elem=p_elem; return i; } else L.elem++; } return0; } /////////////////////////////////////// //函数名：PriorElem() //参数：Sqlist L,ElemType cur_e,ElemType *pre_e //初始条件：线性表L已存在，i>1&&i<=L.length，LocationElem()存在//功能：用pre_e返回线性表中cur_e的前驱 //返回值：i<=1||i>L.length：OVERFLOW // i>1&&i<=L.length：OK /////////////////////////////////////// Status PriorElem(Sqlist L,ElemType cur_e,ElemType*pre_e) { ElemType*p_elem=L.elem; int i,j; i=LocationElem(L,cur_e); if(i<=1||i>L.length) exit(OVERFLOW); for(j=1;j { if(j==(i-1)) { pre_e=L.elem; L.elem=p_elem; return OK; } else L.elem++; } } /////////////////////////////////////// //函数名：NextElem() //参数：Sqlist L,ElemType cur_e,ElemType *next_e //初始条件：线性表L已存在，i>=1&&i //返回值：i<1||i>=L.length：OVERFLOW // i>=1&&i /////////////////////////////////////// Status NextElem(Sqlist L,ElemType cur_e,ElemType*next_e) { ElemType*p_elem; int i,j; i=LocationElem(L,cur_e); if(i<1||i>=L.length) exit(OVERFLOW); for(j=1;j { if(j==(i-1)) { next_e=L.elem; L.elem=p_elem; return OK; } else L.elem++; } } /////////////////////////////////////// //函数名：ListInsert() //参数：SqList L,int i,ElemType e //初始条件：线性表L已存在，1<=i<=ListLength(L)+1 //功能：在线性表中第i个数据元素之前插入数据元素e //返回值：失败：ERROR // 成功：OK /////////////////////////////////////// Status ListInsert(Sqlist L,int i,ElemType e) { int*q=&(L.elem[i-1]); ElemType*newbase,*p; if(i<1||i>(L.length+1)) return ERROR; if(L.length>=L.listsize) { newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT *sizeof(ElemType)); if(newbase==NULL) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } /////////////////////////////////////// //函数名：ListDelete() //参数：SqList L,int i,Elemtype e //初始条件：线性表L已存在，1<=i<=ListLength(L) //功能：将线性表L中第i个数据元素删除 //返回值：失败：ERROR // 成功：OK /////////////////////////////////////// Status ListDelet(Sqlist L,int i,ElemType e) { if(i<1||(i>L.length)) return ERROR; ElemType*p,*q; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; } 实验项目名称：线性表的顺序存储结构上的基本运算 （所属课程：数据结构--用C语言描述） 院系：计算机科学与信息工程学院专业班级：网络工程 姓名：000000 学号：0000000000 实验日期：2016.10.20 实验地点：A-06 406 合作者：指导教师：孙高飞 本实验项目成绩：教师签字：日期： （以下为实验报告正文） 一、实验目的 本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现；掌握动 态链表结构及相关算法设计 实验要求：输入和验证程序例题。正确调试程序，记录程序运行结果。完成实验报 告。 二、实验条件 Windows7系统的电脑，vc++6.0软件，书本《数据结构--用c语言描述》 三、实验内容 3.1 根据41页代码，用c语言定义线性表的顺序存储结构。 3.2 根据42页算法2.1实现顺序表的按内容查找。 3.3 根据43页算法2.2实现顺序表的插入运算。 3.4 根据45页算法2.3实现顺序表的删除运算。 四、实验步骤 3.2实验步骤 （1）编写头文件，创建ElemType。 （2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。 （3）根据42页算法2.1实现顺序表的按内容查找，创建Locate函数。 （4）创建main函数，输入SeqList L的数据元素。 （5）输入要查找的数据元素的值，调用Locate函数，输出结果。 3.3实验步骤 （1）编写头文件，创建ElemType。 （2）根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。 （3）根据43页算法2.2实现顺序表的插入运算，创建InsList函数。 （4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。 （5）创建main函数，输入插入的元素和其位置，调用printLinst函数输出顺序表，调用IntList函数，再次调用printLinst函数输出顺序表。 3.4实验步骤 （1）编写头文件，创建ElemType。 （2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。 （3）根据45页算法2.3实现顺序表的删除运算，创建DelList函数。 （4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。 （5）创建main函数，输入删除元素的位置，调用printLinst函数输出顺序表，调用DelList函数，再次调用printLinst函数输出顺序表。 五、实验结果 （1）实验3.2顺序表的按内容查找 # include 第四章C语言顺序结构 4.1 C语句概述 一般来说，程序设计语言中的流程控制结构分为3种：顺序结构、选择结构和循环结构。 表达式语句由表达式加上分号“；”组成，其一般形式为：表达式； 函数调用语句由函数名、实际参数加上分号“；”组成。其一般形式： 函数名（实际参数表） 控制语句用于控制程序的流程，以实现程序的各种结构方式。C语言中共有9种控制语句，可以将其分为如下3类： 复合语句：把多个语句用{}括起来组成的一个语句称为复合语句。在程序中应把复合语句看成是单条语句，而不是多条语句。 空语句：只有分号“；”组成的语句。 4.2 赋值语句 赋值语句是表达式语句的一种，是由赋值表达式再加上分号构成的表达式语句，其一般形式为：变量=表达式； 注意在变量声明中给变量赋初值和赋值语句的区别。给变量赋初值是变量声明的一部分，赋初值后的变量与其后的其它同类变量之间仍必须用逗号间隔，而赋值语句则必须用分号结尾。例如int a=1，b；是在变量声明中对变量a赋初值，其等效于如下两条语句; int a,b; /*定义整型变量a,b*/ a=1; /*为变量a赋值*/ 在变量声明中，不允许给多个连续变量赋初值。下列说明是错误的：int a=b=c=1；，必须写为int a=1,b=1,c=1; 4.3 格式输入输出 格式输入输出即向标准输出设备显示器输出数据的语句。 4.3.1 printf函数——格式输出 printf函数称为格式输出函数，其关键字最末一个字母“f”即为格式（format）之意。printf函数的功能是按用户指定的格式，把指定的数据显示到显示器屏幕上。printf函数是一个标准库函数，它的函数原型在头文件“stdio.h”中。但作为一个特例，不要求在使用printf函数之前必须包含stdio.h文件。 printf函数调用的一般形式为： printf（“格式控制字符串”，输出列表） 其中，格式字符串用于指定输出格式，可由格式字符串和非格式字符串两种组成。格式字符串是以%开头的字符串，在%后面跟有各种格式字符，以说明输出数据的类型、形式、长度、小数位等。例如：“%d”表示按十进制整型输出，“%f”表示按十进制浮点型输出，“%c”表示按字符型输出。 类型符类型意义 d 以十进制形式输出带符号整数（整数不输出符号） 第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）； 1.3线性表及其顺序存储结构 1.线性表的基本概念 线性表是由n个数据元素组成的一个有限序列，表中的每一个数据元素，除了每一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表。 显然线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。 非空线性表有如下一些结构特征： （1）有且只有一个根结点，它无前件； （2）有且只有一个根结点，它无后件； （3）除了根结点与终端结点外，其他所有结点有且只有一个前件，也只有且只有一个后件。 2.线性表的存储结构 线性表的顺序存储结构具有以下两个特征： （1）线性表中所有元素所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出，在线性表的顺序存储结构中，其前件和后件两个元素在存储空间中是紧邻的，且其前件元素一定存储在后件元素的前面。 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储看见。因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。 在线性表的顺序存储结构中，可以对线性表进行各种处理。主要的运算有如下几种： （1）在线性表的指定位置处加入一个新的元素； （2）在线性表中删除指定的元素； （3）在线性表中查找某个特定的元素； （4）对线性表中的元素进行整序； （5）按要求将一个线性表分解成多个线性表； （6）按要求将多个线性表合并成一个线性表； （7）复制一个线性表； （8）逆转一个线性表等。 3.顺序表的插入运算 设长度为n的线性表为 （a1,a2,a3,a4,…,ai, …,an） 现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为 （a1,a2,a3,a4,…,aj,aj+1, …,an,an+1） 则插入前后的两线性表中的元素满足如下关系： a j0 第四章C语言顺序结构 4、1 C语句概述 一般来说,程序设计语言中得流程控制结构分为3种:顺序结构、选择结构与循环结构。 表达式语句由表达式加上分号“;”组成,其一般形式为:表达式; 函数调用语句由函数名、实际参数加上分号“;”组成。其一般形式: 函数名(实际参数表) 控制语句用于控制程序得流程,以实现程序得各种结构方式。C语言中共有9种控制语句,可以将其分为如下3类: 复合语句:把多个语句用{}括起来组成得一个语句称为复合语句。在程序中应把复合语句瞧成就是单条语句,而不就是多条语句。 空语句:只有分号“;”组成得语句。 4、2 赋值语句 赋值语句就是表达式语句得一种,就是由赋值表达式再加上分号构成得表达式语句,其一般形式为: 变量=表达式; 注意在变量声明中给变量赋初值与赋值语句得区别。给变量赋初值就是变量声明得一部分,赋初值后得变量与其后得其它同类变量之间仍必须用逗号间隔,而赋值语句则必须用分号结尾。例如int a=1,b;就是在变量声明中对变量a赋初值,其等效于如下两条语句; int a,b; /*定义整型变量a,b*/ a=1; /*为变量a赋值*/ 在变量声明中,不允许给多个连续变量赋初值。下列说明就是错误得:int a=b=c=1;,必须写为int a=1,b=1,c=1; 4、3 格式输入输出 格式输入输出即向标准输出设备显示器输出数据得语句。 4、3、1 printf函数——格式输出 printf函数称为格式输出函数,其关键字最末一个字母“f”即为格式(format)之意。printf函数得功能就是按用户指定得格式,把指定得数据显示到显示器屏幕上。printf函数就是一个标准库函数,它得函数原型在头文件“stdio、h”中。但作为一个特例,不要求在使用printf函数之前必须包含stdio、h文件。 printf函数调用得一般形式为: printf(“格式控制字符串”,输出列表) 其中,格式字符串用于指定输出格式,可由格式字符串与非格式字符串两种组成。格式字符串就是以%开头得字符串,在%后面跟有各种格式字符,以说明输出数据得类型、形式、长度、小数位等。例如: “%d”表示按十进制整型输出,“%f”表示按十进制浮点型输出,“%c”表示按字符型输出。 表4-1 d 以十进制形式输出带符号整数(整数不输出符号) f 以小数形式输出单、双精度实数 /************线性表的顺序存储结构定义和基本操作算法实现************/ #include "stdio.h" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; 重庆交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)：B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最 大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部内容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项的项 实验二顺序结构与输入/输出方法 一实验目的 1 学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自增减运算 符的使用。 2 掌握C语言中赋值语句的使用。 3 掌握C语言中各种数据的输入/输出方法，能正确使用基本格式符。 二实验内容 1 输入下面的程序： #include 2 运行以下程序，并分析输出结果 #include 交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize （最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项 石家庄经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的顺序存储结构和实现 实验室：机房4 设备编号：10 完成日期：2012年03月25号 一、实验内容 1.熟悉C 语言的上机环境，掌握C 语言的基本结构。 2.会定义线性表的顺序存储结构。 3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基本算法。 三、实验的内容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求： (2)完成对线性表顺序存储结构的表示和实现。 (3)实现对线性表的建立和初始化。 (4)实现对线性表插入和删除部分元素。 2．概要设计 抽象数据类型线性表的定义： ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛ c语言顺序结构程序设计练习题 1、编写程序：输入一矩形的长和宽，计算该矩形的面积。 2、编程：输入求的半径R，计算并输出球的体积。 3、编程：输入三个数，求出这三个数的和以及平均值，并在屏幕上输出。 4、编程：输入一个三位整数x(999=>x>=100)，将其分解出百位、十位、各位，并求出各位之和以及各位之积 5、编程：已知三角形的三边a=3,b=4,c=5，求其面积s。（提示：假设有一个三角形，边长分别为a、b、c，三角形的面积S可由以下公式求得：S=sqrt(p(p-a)(p-b)(p-c)),而公式里的p 为半周长：p=(a+b+c)/2。 6、编写一个C程序,输出以下信息: ************************** Very Good! ************************** 7、编写一个程序,输入a、b、c三个值,输出其中最大值. 8、写出程序运行的结果： main() { int i,j,m,n; i=8; j=10; m=++i; n=j++; printf(“%d,%d,%d,%d”,i,j,m,n); } 9、写出程序运行的结果： main() { char a ,b, c1,c2; float x ,y; a = 3; b =7; x = 8.5; y = 71.82; c1 = ' A' ; c2 = 'a '; printf("a= %d b = %d/n",a,b); printf("x = %f y = %f",x,y); printf("c1= %c,c2 =%c",c1,c2); } 10、求ax2+bx+c=0方程的根，a,b,c由键盘输入，假设b2-4ac>0。 #include "" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; } 一、单选题 1、以下程序的功能是：给r输入数据后计算半径为r的圆面积s。程序编译时出错。main() /*Beginning */ { int r; float s; scanf("%d",&r); s=π*r*r; printf("s=%f\n",s); } 出错的原因是（）。 A.计算圆面积的赋值语句中使用了非法变量 B.存放圆半径的变量r不应该定义为整型 C.注释语句书写位置错误 D.输出语句中格式描述符非法 正确答案：A 解析： A、π这个符合不是C语言的合法标识符，应提前进行常量定义 2、有以下程序 main() { int m=12,n=34; printf("%d%d",m++,++n); printf("%d%d\n",n++,++m); } 程序运行后的输出结果是（）。 A.12343514 B.12353514 C.12343513 D.12353513 正确答案：B 解析： B、m++ ++在m后，先使用m的值输出，后给m增1 ++m，++在m前，先给m的值增1后，再输出m 3、有定义语句:int b;char c[10]; ,则正确的输入语句是（）。 A.scanf("%d%s",b,c); B.scanf("%d%s",&b,&c); C.scanf("%d%s",b,&c); D.scanf("%d%s",&b,c); 正确答案：D 解析： D、输入语句整型变量 b 需要取地址 &，c是数组名，本身就代表地址，所以不需要取地址符& 4、有以下程序 main() { int m,n,p; scanf("m=%dn=%dp=%d",&m,&n,&p); printf("%d%d%d\n",m,n,p); } 若想从键盘上输入数据,使变量m中的值为123,n中的值为456,p中的值为789,则正确的输入是（）。 A.123 456 789 B.m=123 n=456 p=789 C.m=123n=456p=789 D.m=123,n=456,p=789 正确答案：C 解析： C、输入语句中出现普通字符要按原样输入 5、有以下程序 顺序存储结构的线性表 线性表是最常用且比较简单的一种结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表（A，B，……Z）是一个线性表，表中每一个数据元素由单个字母组成数据项。又如表5.0.1也是一个线性表，表中含八个数据元素，每一个数据元素由n个选手在该项目的竞赛成绩组成。 线性表具有如下结构特征： （1）均匀性。即同一线性表的名数据元素的数据类型一致且数据项相同。 （2）有序性。表中数据元素之间的相对位置是线性的，即存在性一的“第一个”和“最后一个”数据元素。除第一个 和最后一个外，其他元素前面均只有一个数据元素（直接前趋）和后面均只有一个数据元素（直接后继）。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构两类线性表。 1、序存储结构 顺序存储结构是指用一组地址连续的存储单元依次线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）+位移来访问每一个元素。 设 loc(a[i])-----A数组中元素i的内存地址(c<=i<=d); loc(b[i,j])----Bo数组中（i,j）元素的内存地址 (c1<=I<=d1,c2<=j<=d2); loc(a[i])=loc(a[c])+(i-c)*la，la-------atype类型的长度； loc(b[i,j]=loc(b[c1,c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb，lb----atype 类型长度； 一维数组按照下标递增的顺序访问表中元素； a[c]->a[c+1]->……->a[d] 二维数按照先行后列的顺序访问表中元素： b[c1,c2]->b[c1,c+1]->……b[c1,d2]->……>b[i-1,d2]->b[i,c2]-> ……->b[d1,d2-1]->b[d1,d2] 在数组中，数据元素的下标间接反映了数据据元素的存储地址。而计算机内存是随机存储取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了，数组中任意一个元素的存取时间都相等。从这个意义上讲，数组的存储存储结构是一个随机存取的结构。 问题是，虽然数组的顺序分配结构比较简单，便于随机访问数组中的任一元素。但如果数组要保持线性表的特征的话（由下标指明元素间的有序性），其增删操作的效率比较低。特别，当数组很大时，插入与删除运算颇为费时。因此，比较小的数组或元素不常变（很少进行插入与删除运算）的数组可用作线性表，而对于大的线性表或元素经常变动的线性表，可以采链式存储结构。 2、链式存储结构 #include /////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include 福建农林大学金山学院实验报告 系（教研室）：专业：年级： 实验课程： C语言程序设计姓名：学号：实验室号：_ 计算机号：实验时间：指导教师签字：成绩： 实验1：顺序结构程序设计 一、实验目的和要求 1.了解Visual C++ DEV_C++的基本操作方法 2.掌握C程序设计的基本步骤：编辑、编译、连接和运行 3.掌握各种类型数据的输入输出方法 4.能够编写一个简单的程序 二、实验内容和原理 1. 输入并运行一个简单、正确的程序。 # include <> int main( ) { printf ("This is a c program!\n"); return 0; } 2. 要使下面程序的输出语句在屏幕上显示:A,B,34，则从键盘输入的数据格式应为AB34__________ 。 #include<> int main() { char a, b; int c; scanf("%c%c%d",&a,&b,&c); printf("%c,%c,%d\n",a,b,c); return0; 问题1：要使上面程序的键盘输入数据格式为a=A,b=B,34，输出语句在屏幕上显示的结果也为A,B,34，则应修改程序中的哪条语句怎样修改 scanf( “a=%c,b=%c,%d”,&a,&b,&c ); 问题 2：要使上面程序的键盘输入数据格式为A,B,34，而输出语句在屏幕上显示的结果为“A”，“B”，34，则应修改程序中的哪两条语句怎样修改 scanf( “%c,%c,%d”,&a,&b,&c); printf(“\”%c\”,\”%c\”,%d\n”,a,b,c); 3、编程求一个圆的周长和面积。用scanf输入圆半径，输出保留两位小数。 4、输入一个华氏温度F，要求输出摄氏温度C。公式为 c＝5/9(F－32),取两位小数。 5、编程序，用getchar函数读入两个字符给c1、c2，然后分别用putchar函数和printf 函数输出这两个字符。 6. 计算定期存款本利之和。 设银行定期存款的年利率rate为%，并已知存款期为n年，存款本金为capital元，试编程计算n年后的本利之和deposit。要求定期存款的年利率rate、存款期n和存款本金capital 均由键盘输入。(提示：pow为幂函数：pow(2,3)表示23)。 #include <> #include <> int main() { } 三、实验环境 重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作）（5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出线性表顺序存储结构上的基本运算
C语言顺序结构
线性表练习题(答案)
3线性表及其顺序存储结构
C语言顺序结构
线性表的顺序存储结构定义和基本操作算法实现
线性表的顺序储存结构
C语言实验二程序、总结 顺序结构与输入、输出方法
线性表的顺序储存结构
线性表的顺序存储结构和实现
c语言顺序结构程序设计练习题10道
线性表的顺序存储结构定义和基本操作算法实现
C语言(顺序结构)习题与答案
顺序存储结构的线性表
线性表顺序存储实现、插入、删除操作
顺序存储结构线性表基本操作 纯C语言实现
c语言程序设计实验报告1--顺序结构
线性表的顺序储存结构
相关文档
- 线性表的顺序储存结构
- 数据结构线性表的顺序存储结构C语言实现
- 线性表的链式存储结构实验报告
- 线性表顺序存储结构上的基本运算
- 线性表的顺序储存结构
- 数据结构实验报告——线性表顺序存储结构[1]
- DS：线性表的顺序存储结构实现学生记录表
- 线性表的顺序存储结构_实验报告样例
- 线性表顺序存储结构的11个基本操作函数
- 顺序存储结构线性表基本操作 纯C语言实现
- 线性表顺序存储结构插入,删除
- 线性表的顺序存储结构示意图an
- 线性表的链式存储结构和操作
- 线性表的顺序存储结构定义和基本操作算法实现
- 线性表的顺序存储结构 代码
- 线性表的顺序存储结构
- 实验报告线性表的顺序存储结构
- 实验报告 线性表的顺序存储结构
- 3线性表及其顺序存储结构
- 数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库