有两张单调递增有序的线性表A和B,采用顺序存储结构,将这两张表合并成C表,要求C表单调递减有序。
/* Note:Your choice is C IDE */ #include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define OVERFLOW -2
typedef int status;
typedef int elemtype;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10 typedef struct{
elemtype *elem;
int length;
int listsize;
}SqList;
status InitList_Sq(SqList *L)/*构造一个空的顺序表*/ {
L->elem=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(el emtype));
if(!L->elem) exit(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
void shengcheng_Sq(SqList *L)/*建立一个顺序表，含有n个数据元素。*/
{
int m,n;
printf("please enter some data:");
scanf("%d",&n);
/*printf("请输入%d个元素：",n);*/
for(m=0;m { scanf("%d",&L->elem[m]); L->length++; } } void shuchu_Sq(SqList L)/*输出顺序表及顺序表的长度*/ { int i; /*printf("顺序表中的元素是：\n");*/ for(i=0;i< L.length;i++) { printf("%d", L.elem[i]); } printf("\n"); } void MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc)/*将两个顺序有序表A和B合并为一个有序表C。*/ { elemtype *pa,*pb,*pc,*pa_last,*pb_last; pa=La->elem;pb=Lb->elem; Lc->listsize =Lc->length =La->length +Lb->length ; pc=Lc->elem =(elemtype *)malloc(Lc->listsize *sizeof(elemtype)); if(!Lc->elem) exit(OVERFLOW); pa_last=La->elem+La->length-1; pb_last=Lb->elem+Lb->length-1; while(pa<=pa_last && pb<=pb_last){ if(*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa<=pa_last) *pc++=*pa++; while(pb<=pa_last) *pc++=*pb++; } void nizhi_Sq(SqList *La,SqList *Lb)/*将顺序表逆置，将结果保存到另外的顺序表中。*/ { int m,p; InitList_Sq(Lb); p=La->length-1; for(m=0;m<=p;m++) { Lb->elem[m]=La->elem[p-m]; Lb->length++; } } void main() { SqList La,Lb,Lc,Ld; InitList_Sq(&La); InitList_Sq(&Lb); InitList_Sq(&Lc); InitList_Sq(&Ld); shengcheng_Sq(&La); shuchu_Sq(La); shengcheng_Sq(&Lb); shuchu_Sq(Lb); MergeList_Sq(&La,&Lb,&Lc); shuchu_Sq(Lc); nizhi_Sq(&Lc,&Ld); shuchu_Sq(Ld); } 实验项目名称：线性表的顺序存储结构上的基本运算 （所属课程：数据结构--用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 第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 、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。 实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管 理系统 一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。 二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。 四、简要的需求分析与概要设计（本项为可选项，选作时参考课 五、详细的算法描述： 六、实验步骤（以下为参考程序，已经调试运行通过）#include char name[20]; int english; int math; }; typedef student elemtype; struct sqlist { elemtype *elem; int length; int listsize; int incrementsize; }; //初始化顺序表l void initlist(sqlist &l,int maxsize=LISTINITSIZE,int incresize=LISTINCREMENT) { l.elem=new elemtype[maxsize]; l.length=0; l.listsize=maxsize; l.incrementsize=incresize; /************线性表的顺序存储结构定义和基本操作算法实现************/ #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; //最大可容纳表项的项 第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 链表不具有的特点是（） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 6. 下面的叙述不正确的是（） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i） B．O（1） C．O（n） D．O（i-1） 10．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 11．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断 1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6．集合与线性表的区别在于是否按关键字排序。( ) 7. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术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=｛ 顺序存储结构的线性表 线性表是最常用且比较简单的一种结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如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 "" /***********************线性表的顺序存储结构定义*******************/ #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; } #include /////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #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();//输出 第二章线性表习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 4．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 6．循环链表的主要优点是( )。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 7．下面关于线性表的叙述错误的是( )。 (A)线性表采用顺序存储，必须占用一片地址连续的单元； 线性表顺序存储结构插入，删除 (数据结构) 一、实验目的 1.掌握顺序存储结构的特点。 2.掌握顺序存储结构的常见算法。 3.实现顺序表的插入，删除等操作。 二、实验要求 1、用vs6.0 进行线性表程序的编写，用c语言程序开发 三、实验内容 1、定义常量，变量等 2、定义主函数main 3、定义调用函数void Initlist(Sqlist &L)，void Creatlist(Sqlist &L)，void Insertlist(Sqlist &L,int j,int e)，void Deletelist(Sqlist &L,int j) #include int i; scanf("%d\n",&L.length); for(i=0;i 数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库.txt爱空空情空空，自己流浪在街中；人空空钱空空，单身苦命在打工；事空空业空空，想来想去就发疯；碗空空盆空空，生活所迫不轻松。总之，四大皆空！/* 数据结构C语言版线性表的动态分配顺序存储结构表示和实现 P22-26 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月9日 */ #include 线性表顺序存储结构上的基本运算
线性表练习题(答案)
3线性表及其顺序存储结构
线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)
线性表的顺序存储结构定义和基本操作算法实现
线性表的顺序储存结构
数据结构练习题-线性表
线性表的顺序储存结构
线性表的顺序存储结构和实现
顺序存储结构的线性表
线性表的顺序存储结构定义和基本操作算法实现
线性表顺序存储实现、插入、删除操作
顺序存储结构线性表基本操作 纯C语言实现
线性表的顺序储存结构
第2章-线性表习题及参考答案
线性表顺序存储结构插入-删除 (1)
数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库
- DS：线性表的顺序存储结构实现学生记录表
- 线性表的顺序存储结构_实验报告样例
- 线性表顺序存储结构的11个基本操作函数
- 顺序存储结构线性表基本操作 纯C语言实现
- 线性表顺序存储结构插入,删除
- 线性表的顺序存储结构示意图an
- 线性表的链式存储结构和操作
- 线性表的顺序存储结构定义和基本操作算法实现
- 线性表的顺序存储结构 代码
- 线性表的顺序存储结构
- 实验报告线性表的顺序存储结构
- 实验报告 线性表的顺序存储结构
- 3线性表及其顺序存储结构
- 数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库
- 线性表的顺序存储结构实验报告
- 线性表的顺序储存结构
- 数据结构线性表的顺序存储结构C语言实现
- 线性表的链式存储结构实验报告
- 线性表顺序存储结构上的基本运算
- 线性表的顺序储存结构