当前位置：搜档网 › 3线性表及其顺序存储结构

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

aj= b j=i

a j-1i

在一般情况下，要在第i（1

置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度增加了1。

4.顺序表的删除运算

在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动表中的元素；但如果要删除线性表中的第1个元素，则需要运动表中的所有元素。在一般情况下，如果要删除第i个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。在平均情况下，要在线性表中删除一个元素，其较多的处理时间。

由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适，因为插入与删除的效率比较底。

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

实验项目名称：线性表的顺序存储结构上的基本运算（所属课程：数据结构--用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;

数据结构实验报告实验一线性表链式存储运算的算法实现

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称线性表链式存储运算的算法实现指导教师教师评语教师签名：年月日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束

pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点，退出 while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果：

线性表练习题(答案)

第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 ）；

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