当前位置：文档之家› 线性顺序表——数据结构

线性顺序表——数据结构

//头文件

#include

//预定义常量和类型:函数结果状态代码

#define OK 1

#define ERROR 0

#define TURE 1

#define FALSE 0

#define INFEASIBLE -1

#define OVERFLOW -2

//---线性表的动态分配顺序存储结构---

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量

#define LINSTINCREMENT 10 //线性表存储空间的分配增量

//数据类型说明,其值是函数结果状态代码

typedef int Status;

typedef int ElemType;

typedef struct {

ElemType *elem; //存储空间基址

int length; //当前长度

int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位}SqList; //定义了一个线性表的数据类型

//-------函数基本操作---------

// 函数InitList的主要功能是初始化一个线性表,构造一个空的线性表L。Status InitList(SqList &L) {

L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)

{

printf("分配失败\n");

exit(OVERFLOW); //存储分配失败

}

L.length=0; //空表长度为0

L.listsize=LIST_INIT_SIZE; //初始存储容量

return OK;

} //InitList

//函数Exist的主要功能是判断线性表L是否存在。

Status exist(SqList &L) {

if((L.elem!=NULL)&&(L.listsize>=LIST_INIT_SIZE)) //检测线性表是否存在

return OK;

else

return ERROR;

}//若线性表存在返回OK，否则返回ERROR

//函数DestroyList的主要功能是销毁线性表L。

Status DestroyList(SqList &L){

if(exist(L))//判断线性表是否存在

{

free(L.elem); //释放空间

L.elem =NULL; //将指针赋值为空

L.length=-1; //当前长度赋值为-1，标志线性表不存在

L.listsize=0; //当前最大容量赋值为0

return OK;

}

else

return ERROR;

}//成功释放空间时返回OK，否则返回ERROR

//函数ClearList的主要功能是将L重置为空表。

Status ClearList(SqList &L){

if(!(L.elem=NULL)) //重置为空表

return OK;

else

return ERROR;

}//重置线性表，成功返回OK，失败返回ERROR

//函数ListEmpty的主要功能是判断线性表是否为空表。

Status ListEmpty(SqList L) {

if(!exist(L))

return ERROR;

else

{

if(ClearList(L))

return TURE;

else

return FALSE;

}

return OK;

}

//函数ListLength的主要功能是检测线性表的数据元素个数。

Status ListLength(SqList &L){

//返回数据元素个数

if(exist(L))//判断线性表是否存在

return L.length ;//返回元素个数

else

return -1;

}//检验线性表元素个数，成功返回数字，失败返回-1.

//函数GetElem的主要功能是返回线性表中指定位置的数据元素。

Status GetElem(SqList &L, int i, ElemType &e)

// 线性表已存在，用e返回线性表 L中第i个元素

{

if ( exist(L) && i > 0 && i < L.length+1) //判定线性表存在和元素位置 i是否合法

{

e = L.elem[i - 1]; //将指定位置元素赋给e

return OK;

}

else

return ERROR;

}////成功返回 OK, 失败返回ERROR

//函数compare的主要功能是判断线性表中有与输入元素相同的数值，函数默认程序

compare(ElemType e1, ElemType e2)

{

if(e1==e2)

return OK; //相等，返回OK

else

return ERROR;//不相等，返回ERROR

} //函数返回值是一个执行成功与否的状态标志

//函数LocateElem的主要功能是返回满足函数compare()的数据元素位序。

int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType,ElemType)){

int i;

ElemType *p;

i=1 ; //i的处值为第1个元素的位序

p=L.elem; //p的初值为第1个元素的存储位置

while(i<=L.length&&!(*compare)(*p++,e))

++i;

if(i<=L.length)

return i;

else

return ERROR;

}//在顺序线性表L中查找第一个与e满足compare()的元素的位序//若找到，则返回其在L中的位序，否则返回ERROR

//函数PriorElem的主要功能是返回指定元素的前驱。

Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e){

int i=0; //初始化元素下标

while(i

{

if(L.elem[i]==cur_e)//若L.elem[i]的元素值与cur_e相等

{

if(i>0)//判断i值是否合法

{

pre_e=L.elem[i-1];

return pre_e;//满足条件，用pre_e返回元素cur_e前驱的值

}

else

return -1;

}

i++;//循环条件不满足，继续循环

}

if(i>=L.length)

return ERROR;//不满足循环条件，无法继续实行

return OK;//操作成功，返回OK

}//返回给定元素的前驱，成功则返回OK,由pre_e带回前驱值，失败则返回ERROR

//函数NextElem的主要功能是返回元素元素的后继。

Status NextElem(SqList L,ElemType cur_e,ElemType &next_e){ int i=0;

while(i

{

if(L.elem[i]==cur_e)//若L.elem[i]的元素值与cur_e相等

{

if(i!=L.length-1)//判断i值是否合法

{

next_e=L.elem[i+1];

return next_e;//满足条件，用next_e返回元素cur_e后继的值

}

else

return -1;

}

i++;//循环条件不满足，继续循环

}

if(i>=L.length)

return ERROR;//不满足循环条件，无法继续实行

return OK;//操作成功，返回1

}//若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后继，若失败，则next_e无定义

//函数visit的主要功能是判断是依次输出线性表的元素的值

Status visit(ElemType e)

{ printf("%d ",e);

return OK;//输出完成，返回OK

}

//函数ListInsert的主要功能是向线性表中插入新的元素。

Status ListInsert(SqList &L, int i, ElemType e){

//参数L表示的是一个已经初始化的线性表变量

//e表示待插入的数据

//函数返回值是一个执行成功与否的状态标志

//i的合法值为1<=i<=ListLength_Sq(L)+1

ElemType *newbase,*q,*p;

if(i<1||i>L.length+1)

return ERROR; //i值不合法

if(L.length>=L.listsize){ //当前存储空间已满，增加分配

newbase=(ElemType *)realloc(L.elem,(L.listsize +LINSTINCREMENT)*sizeof(ElemType));

if(!newbase)

exit(OVERFLOW);//存储分配失败

L.elem=newbase;//新基址

L.listsize+=LINSTINCREMENT;//增加存储容量

}

q=&(L.elem [i-1]); //q为插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p; //插入位置及之后的元素后移

*q=e; //插入e

++L.length ;//表长增加1

return OK;//插入成功，返回OK

}//ListInsert

//函数ListDelete的主要功能是删除线性表中的元素。

Status ListDelete(SqList &L,int i,ElemType &e){

//线性表L已存在且非空，在顺序线性表L中删除第i个元素，并用e 返回其值，L的长度-1

//i的合法值为1<=i<=LIstLength_Sq(L)

ElemType *q,*p;

if((i<1)||(i>L.length))

return ERROR; //i值不合法

p=&(L.elem[i-1]); //p为被删除元素的位置

e=*p; //被删除元素的值赋给e

q=L.elem+L.length-1; //表尾元素的位置

for(++p;p<=q;++p)

*(p-1)=*p; //被删除之后的元素往前移

--L.length; //表长减一

return OK;

}//ListDelete

//函数ListTraverse的主要功能是对每个元素调用visit()函数测试。

Status ListTraverse(SqList L,Status(*visit)(ElemType)){

ElemType *p=L.elem; //p指向第1个元素

int i;

for(i=1;i<=L.length;i++) //从表L的第1个元素到最后1个元素

visit(*p++); //对每个数据元素调用visit()

return OK;//操作成功

} //顺序线性表L已存在,依次对L的每个数据元素调用函数visit(),一旦visit()失败，则操作失败

int main()

{

SqList L;

ElemType e,cur_e,pre_e,next_e;

int i,j,n;

InitList(L);

printf("输入元素的个数为:");

scanf("%d",&n);

while(n<=0)//n的合法值为n>0

{

printf("输入错误,请重新输入\n");

printf("输入元素的个数为:");

scanf("%d",&n);

}

printf("请输入%d个元素:",n);

//输入元素

for(i=1;i<=n;i++)

{

scanf("%d",&e);

ListInsert(L,i,e);

}//调用函数ListInsert输入

//显示线性表的元素个数,依次显示元素

printf("线性表共有%d个元素，线性表中的元素依次为:",ListLength(L)); for(i=0;i

printf("%d ",L.elem[i]);

printf("\n");

//函数GetElem的应用，返回线性表L中第i个元素的值

printf("请输入要返回数据元素的位序:");

scanf("%d",&i);

while(i<1||i>L.length)//i的合法值为0

{

printf("输入错误,请重新输入\n");

printf("请输入元素的序数为:");

scanf("%d",&i);

}

GetElem(L,i,e);

printf("第%d个的元素的值为%d\n",i,e);

printf("\n");

//函数LocateElem和函数compare()的应用，查找第一个与e满足函数compare()的元素的位序

printf("请输入数据元素e:");

scanf("%d",&e);

printf("第一个与e满足关系的元素的位序为:%d\n",LocateElem(L,e,(*compare)));

printf("\n");

//函数priorElem的应用，输出某数据元素的前驱

printf("请输入数据元素cur_e:");

scanf("%d",&cur_e);

if(PriorElem(L,cur_e,pre_e)!=-1)

printf("%d的前驱为:%d\n",cur_e,PriorElem(L,cur_e,pre_e));

else

printf("线性表L中没有数据元素%d的前驱\n",cur_e);

printf("\n");

//函数NextElem的应用,输出某元素的后继

printf("请输入数据元素cur_e:");

scanf("%d",&cur_e);

if(NextElem(L,cur_e,next_e)!=-1)

printf("%d的后继为:%d\n",cur_e,NextElem(L,cur_e,next_e));

else

printf("线性表L中没有数据元素%d的后继\n",cur_e);

printf("\n");

//函数ListInsert的应用，插入元素

printf("请输入要插入的数据元素的位置i:");

scanf("%d",&i);

printf("请输入要插入的数据元素e:");

scanf("%d",&e);

if(i>=1&&i<=L.length)

{ ListInsert(L,i,e);

printf("插入新的数据元素后的线性表L中的数据元素为:");

for(i=0;i

printf("%d ",L.elem[i]);

printf("\n");

}

printf("\n");

//函数ListDelete的应用，删除元素

printf("请输入要删除的数据元素的位置j:");

scanf("%d",&j);

ListDelete(L,j,e);

printf("删除数据元素后的线性表L中的数据元素为:");

for(i=0;i

printf("%d ",L.elem[i]);

printf("\n");

printf("删除的第%d个元素值为:%d",j,e);

printf("\n");

//函数ListTraverse和函数visit()的应用，L中的每个元素依次调用visit()

printf("此时线性表L中的元素的值为:");

ListTraverse(L,visit);

printf("\n");

//函数ClearList和函数ListEmpty的应用，将线性表L重置为空表，并且判断操作是否成功

printf("将线性表L重置为空表\n");

ClearList(L);

printf("\n");

i=ListEmpty(L);//将函数ListEmpty返回的值赋值给i

if(i==1)//如果函数ListEmpty_Sq返回TURE

printf("线性表L已重置为空表,此时长度length为:%d\n",L.length);

else //如果函数ListEmpty_Sq返回FALSE

printf("线性表重置失败\n");

printf("\n");

//函数DestoryList的应用,销毁线性表L

printf("销毁线性表\n");

DestroyList(L);

printf("此时线性表L已不存在\n");

return 0;

}

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

实验项目名称：线性表的顺序存储结构上的基本运算（所属课程：数据结构--用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、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放

该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i

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

昆明理工大学信息工程与自动化学院学生实验报告（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 } 四.程序运行结果：

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