当前位置：文档之家› 顺序存储结构的线性表

顺序存储结构的线性表

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

在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。其实现既可采用静态数组，亦可采用动态指针。为了扩大用户空间和更多地体现莲式存储结构的便利，实践中大都采用动态链表形式。

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

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

数据结构(含答案)

数据结构综合练习一、选择题 1．数据的存储结构包括顺序、链接、散列和（）4种基本类型。 A索引B数组C集合D向量 2．下面程序的时间复杂性的量级为（）。 inti=0，s1=0，s2=0； while（i++

A.查找 B.表尾插入和删除 C.按值插入和删除 D.表头的插入和删除 9. 线性表的顺序存储比链式存储更有利于进行（）操作。 A.查找 B.表尾插入和删除 C.按值插入和删除 D.表头的插入和删除 10. 在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。 A. ph=p; p->next=ph; B. p->next=ph; ph=p; C. p->next=ph; p=ph; D. p->next=ph->next; ph->next=p; 11. 在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。 A. q->next=p->next; p->next=q; B. p->next=q->next; q=p; C. q->next=p->next; p->next=q; D. p->next=q->next; q->next=p; 12.在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。 A. p=q->next; p->next=q->next; B. p=q->next; q->next=p; C. p=q->next; q->next=p->next; D. q->next=q->next->next; q->next=q; 13.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 14.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（）的情况。 A.3，2，1，4 B.2，1，4，3 C.4，3，2，1 D.1，4，2，3. 15. 假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。 A.f+1==r B.r+1==f C.f==0 D.f==r 16. 假定一个顺序循环队列存储于数组a[N]，其队首和队尾指针分别

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