谈顺序存储与链式存储的异同

线性表顺序存储结构上的基本运算

实验项目名称：线性表的顺序存储结构上的基本运算 （所属课程：数据结构--用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 typedef int Elemtype; typedef struct{ Elemtype elem[100]; int last; }SeqList; int Locate(SeqList L,Elemtype e){ int i; i=0;

顺序存储结构和链式存储结构

第二次作业 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 3.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a．在P结点后插入S结点的语句序列是-----------。 b．在P结点前插入S结点的语句序列是-----------。 c．删除P结点的直接后继结点的语句序列是----------。 d．删除P结点的直接前驱结点的语句序列是----------。 e．删除P结点的语句序列是------------。 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=p->next; (18)free(Q); 4. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。

线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)

、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。 实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管 理系统 一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。 二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。 四、简要的需求分析与概要设计（本项为可选项，选作时参考课

五、详细的算法描述： 六、实验步骤（以下为参考程序，已经调试运行通过）#include #include using namespace std; const int LISTINITSIZE=100; const int LISTINCREMENT=10; struct student { char no[20];

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;

3线性表及其顺序存储结构

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

数据结构练习题-线性表

第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. 线性表的特点是每个元素都有一个前驱和一个后继。( )

数据结构—线性表的两种存储结构的比较

在两种存储结构下实现线性表的创建,插入,删除,按值查找 一、使用线性表的链式存储结构实现 #include #include typedef struct LNode{ int data; //链表数据 struct LNode* next; //链表指针 }LNode,*LinkList; /*头插法-建立单链表*/ LinkList HeadCreate(LinkList la) { int num; la=(LinkList)malloc(sizeof(LNode)); //建立头结点 la->next=NULL; scanf("%d",&num); while(num!=10) { LNode *p=(LinkList)malloc(sizeof(LNode)); p->data=num; p->next=la->next; la->next=p; scanf("%d",&num); } return la; } /*尾插法-建立单链表*/ LinkList TailCreate(LinkList la) { int num; la=(LinkList)malloc(sizeof(LNode)); la->next=NULL; LinkList s,r=la; scanf("%d",&num); while(num!=10) { s=(LinkList)malloc(sizeof(LNode)); s->data=num; r->next=s;

r=s; scanf("%d",num); } r->next=NULL; return la; } /*单链表遍历*/ void TravelList(LinkList la) { LinkList p=la->next; while(p!=NULL) { printf("%d->",p->data); p=p->next; } printf("\n"); } /*单链表的按位查找*/ LinkList GetElem(LinkList la,int i) { int j=1; LNode* p=la->next; if(i<1) return NULL; while(p && jnext; j++; } return p; } /*单链表的按值查找*/ LinkList LocalElem(LinkList la,int e) { LNode* p=la->next; while(p!=NULL && p->data!=e) p=p->next; return p; }

四种基本的存储结构

数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 ???该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 ???由此得到的存储表示称为顺序存储结构（SequentialStorageStructure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 ???该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（LinkedStorageStructure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 ???该方法通常在储存结点信息的同时，还建立附加的索引表。 ???索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(SpareIndex)。索引项的一般形式是：

????????????????????(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法 ???该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。

线性表的顺序储存结构

交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术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; //最大可容纳表项

顺序存储结构的线性表

顺序存储结构的线性表 线性表是最常用且比较简单的一种结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如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、链式存储结构

比较顺序存储结构和链式存储结构 (1)

1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用 存储单元的地址必须是连续的。 优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值， 另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 顺序表与链表的比较 基于空间的比较 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的 存储密度= 结点数据本身所占的存储量/结点结构所占的存储总量 顺序表的存储密度= 1 链表的存储密度< 1 基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 顺序表和链表的比较顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：┌───┬───────────────┬───────────────┐││ 顺序表│链表│├─┬─┼───────────────┼───────────────┤│基│分│静态分配。程序执行之前必须明确│动态分配只要内存空间尚有空闲，││于│配│规定存储规模。若线性表长度n变│就不会产生溢出。因此，当线性表││空│方│化较大，则存储规模难于预先确定│的长度变化较大，难以估计其存储││间│式│估计过大将造成空间浪费，估计太│规模时，以采用动态链表作为存储││考││小又将使空间溢出机会增多。│结构为好。 ││虑├─┼───────────────┼───────────────┤││存│为1。当线性表的长

线性表顺序存储实现、插入、删除操作

#include #include #define list_init_size 100 #define listincrement 10 #define ok 1 #define overflow -1 #define elemtype int #define error -1 elemtype *q; elemtype *p; typedef struct{ elemtype *elem; int length; int listsize; }sqlist; int initlist_sq(sqlist &l)//线性表动态分配存储结构// { l.elem=(elemtype*)malloc(list_init_size*sizeof(elemtype)); if(!l.elem) { cout<<"the list have no space"<>m;

数据结构简答题复习过程

数据结构简答题

试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 一棵度为2的有序树与一棵二叉树有何区别? 答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序. 而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。

简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

顺序存储结构线性表基本操作 纯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

第2章-线性表习题及参考答案

第二章线性表习题 一判断题 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)线性表采用顺序存储，必须占用一片地址连续的单元；

线性表的链式存储结构实验报告

实验报告 课程名称：数据结构与算法分析 实验名称：链表的实现与应用 实验日期：班级：数媒1401 姓名：范业嘉学号 08 一、实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 二、实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用 线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。 三、数据结构设计 1.按所用指针的类型、个数、方法等的不同，又可分为： 线性链表（单链表） 静态链表 循环链表 双向链表 双向循环链表 2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。 四、算法设计 1.定义一个链表 void creatlist(Linklist &L,int n) { int i; Linklist p,s; L=(Linklist)malloc(sizeof(Lnode)); p=L; L->next=NULL; for(i=0;idata); s->next=NULL; p->next=s; p=s; }

线性表的顺序储存结构

重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术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语言版 线性表的动态分配顺序存储结构表示和实现文库

数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库.txt爱空空情空空，自己流浪在街中；人空空钱空空，单身苦命在打工；事空空业空空，想来想去就发疯；碗空空盆空空，生活所迫不轻松。总之，四大皆空！/* 数据结构C语言版线性表的动态分配顺序存储结构表示和实现 P22-26 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月9日 */ #include #include #include typedef int ElemType; // 定义数据结构元素的数据类型 #define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量 #define LISTINCREMENT 5 // 线性表存储空间的分配增量 // 线性表的动态分配顺序存储结构 typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) }SqList; // 算法2.3，P23 // 构造一个空的顺序线性表即对顺序表结构体中的所有元素 // 进行初始化。 int InitList(SqList *L) { // 分配指定大小的存储空间给顺序表 (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if( !(*L).elem ) // 存储分配失败 exit(0); (*L).length = 0; // 当前长度初始化为0 // 指定分配的存储容量 (*L).listsize = LIST_INIT_SIZE; return 1; } // 销毁顺序线性表L即将顺序表结构体中的所有成员销毁（空间释放，

线性表的顺序存储结构定义和基本操作算法实现

/************线性表的顺序存储结构定义和基本操作算法实现************/ #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;

线性表_顺序(打印)_习题

线性表作业 学号姓名分数 一选择题（14分） 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．非空的循环单链表head的尾结点p满足（）。 A．p－＞next=head B．p－＞next =NULL C．p=NULL D．p= head 11．循环链表H的尾结点P的特点是（）。 A．P－＞NEXT=H B．P－＞NEXT= H－＞NEXT C．P=H D．P=H－＞NEXT 12．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（） A. p－＞next=h B. p－＞next=NULL C. p－＞next. －＞next=h D. p－＞data=-1 13．在单链表指针为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; 14．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断（10分） 1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 4. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 5. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 6. 取线性表的第i个元素的时间同i的大小有关. ( ) 7. 线性表只能用顺序存储结构实现。( ) 8. 线性表就是顺序存储的表。( ) 9. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )