1.线性表 (2)

数据结构与算法第二章线性表（二）

内容提要

z线性表的概念（逻辑结构）

z线性表的顺序表示和实现（顺序表）z线性表的链式表示和实现（链表）z线性表的应用

线性表的链式表示和实现

z单链表

z循环链表

z双向链表

单链表

z线性表的链式表示

z单链表的基本运算

z单链表的完整程序示例

z头结点的作用

数据域指针域

3143Zhou25

typedef struct Node *PLinkList ; /* 单链表指针类型*/

空表判断：plist->link == NULL

单链表

z线性表的链式表示

z单链表的基本运算

z单链表的完整程序示例

z头结点的作用

单链表基本运算及其实现

?创建空的单链表Plinklist createNullList_link(void)

?int insertPost link( PLinkList pllist, PNode p, DataType x)插入结点se os_(s p s,Node p,ype) int insertPre_link( PLinkList pllist, PNode p, DataType x)

int insert link( PLinkList pllist, int i, DataType x)

_(p,,yp)

?删除结点int deleteV_link(PLinkList pllist, DataType x)

int deleteP_link(PLinkList pllist, PNode p)

?定位运算PNode locate_link(PlinkList pllist, DataType x)

PNode locatePre_link(PlinkList pllist, DataType x)

PNode find_link( PLinkList pllist, int i)

?判空运算isNullList_Link(PLinkList pllist)

单链表的基本运算

z创建

z判空

z插入

z删除

z取值

z查找

链表的定义

z

运算的实现

{数据域可以有多个信息。

{数据说明

struct Node;/* 单链表结点类型*/

typedef struct Node *PNode;/* 结点指针类型*/ struct Node /* 单链表结点结构*/

{ DataType info;

PNode link; };

typedef struct Node *PLinkList ; /* 单链表指针类型*/

建立带有头节点的空链表z函数名：createNulllist_link

z功能: 建立带有头节点的空链表

z程序：

PLinkList createNulllist link

PLinkList createNulllist_link(void)

{ PLinkList pllist;

pllist =(PLinkList) malloc (sizeof(struct Node) );

/*申请表头结点空间*/

if(pllist ! = NULL) pllist ->link = NULL;

if(pllist ! = NULL) pllist >

else printf(“out of space!\n”);

t (lli t)

return (pllist);

}

单链表的基本运算

z创建

z判空

z插入

z删除

z取值

z查找

判断单链表是否为空

z函数名：isNulllist_link

z功能: 判断带头结点的单链表pllist是否为空链

lli t

表。

z程序：

int isNulllist_link(PLinklist pllist)

int isNulllist link

{ return (pllist->link==NULL);

}

单链表的基本运算

z创建

z判空

z插入

z删除

z取值

z查找

ld

在单链表中插入值为x 的元素-old z 函数名：insertPre_link

z 功能:在pllist 带头结点的单链表中下标为i(第i+1个)的结点前插入一个值为ｘ的元素，并返回插入成功与否的标志。程序

z 程序：int insert_link( PLinkList pllist, int i, DataType x) a b

p

a

b p

>inf x;

单链表

q->info=x;q->link = p-> link;p > link = q;x

q

p-> link = q;

int insertPre_link(PLinkList pllist,int i,DataType x)

p q;{PNode p,q;p =pllist;int j=0;while(p!=null &&j

{p=p->link;j++;}if(j!=i)/*查找失败*/

j {printf(“i=%d is not reasonable.\n”,i);return 0;}

/**/q =(PNode)malloc(sizeof(struct Node ));/申请新节点/

if (q ==null )

/*申请失败*/{printf("Out of space!!!\n");return 0;}

else /*插入链表中*/

{

q->info =x;q->link =p->link;p->link =q;

a p

return 1;

}

}a

b

演示

在单链表中插入值为x的元素-new z函数名：insertPost_link

数名

p p

z功能:在pllist带头结点的单链表中,在所指结点后面插入一个值为ｘ的新结点，并返回插入成功与否的标志。

z程序：int insertPost_link( PLinkList pllist, PNode p,

_(p,p, DataType x){

PNode q(PNode)malloc(sizeof(struct Node));

q=(PNode)malloc(sizeof(struct

if(q==NULL){ printf(“out of sapce!!!\n”);return(0);}

else {q>info=x;q>link=p>link;p>link=q;return(1);} else {q->info=x;q->link=p->link;p->link=q;return(1);} }p

a b

线性表逆置(顺序表)实验报告

实验一：线性表逆置（顺序表）实验报告 （一）问题的描述： 实现顺序表的逆置算法 （二）数据结构的设计： 顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; （三）函数功能、参数说明及概要设计： 1.函数Status InitList(SqList *L) 功能说明：实现顺序表L的初始化 算法设计：为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明：返回顺序表L长度 算法设计：返回顺序表中的length变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明：将元素e插入到顺序表L中的第i个节点 算法设计：判断顺序表是否已满，已满则加空间，未满则继续，将元素e插入到第i个元素之前，并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明：依次对L的每个数据元素调用函数vi() 算法设计：依次对L的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明：实现顺序表L的逆置 算法设计：用for循环将顺序表L中的第i个元素依次与第（i+length）个元素交换6.函数void print(ElemType *c) 功能说明：打印元素c 算法设计：打印元素c 2. （四）具体程序的实现

数据结构 线性表 课后答案

第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B

实验一 线性表的顺序表示和实现

实验一 线性表的顺序表示和实现 实验内容 1.线性表的顺序存储结构 C 语言中的顺序表存储结构描述： —————线性表的顺序存储结构———————— #define MAXSIZE 100 /*顺序表允许的最大空间量*/ typedef struct { ElemType elem[MAXSIZE]; /* ElemType 为抽象数据类型*/ int length; /*当前顺序表长度*/ } SqList; 2.顺序表的基本操作 （1）初始化操作：为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度length 设为0。 （2）清空操作：将顺序表的长度设为0，是表为空表 （3）销毁操作：将顺序表所占用的空间释放 （4）定位操作：根据给定的数据元素e ，在顺序表中找出和e 相等的数据元素的位序，如果这样的数据元 素不存在，则返回0 （5）插入操作：在顺序表的第i 个数据元素前插入一个新的数据元素e ，注意，在插入前必须判断i 的值 域)1)(1(+≤≤L ListLength i ，而在插入操作后必须使顺序表的长度增1. （6）删除操作：删除顺序表中第i 个数据元素，并且用e 返回其值。注意，在删除操作前必须判断i 的值 域)1)(1(+≤≤L ListLength i ，而在删除操作后必须使顺序表的长度减1。 （7）输出操作：即将顺序表中各个元素按下标次序输出。 3.顺序表操作实现的操作步骤 （1）实现将顺序表的存储结构和基本操作程序代码。 （2）实现main 主函数。 4.程序代码完整清单 #include #include #define MaxSize 50 /*顺序表允许的最大空间量*/ typedef char ElemType; /*顺序表中元素类型为char*/ typedef struct { ElemType elem[MaxSize]; int length; } SqList; /*顺序表结构定义 */ //基本操作函数声明 void InitList(SqList *&L); /*初始化线性表*/ void DestroyList(SqList *L); /*销毁线性表*/

实验一 线性表(顺序表与链表)

实验一顺序表与链表 一、实验目的 1、掌握线性表中元素的前驱、后续的概念。 2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。 3、对线性表相应算法的时间复杂度进行分析。 4、理解顺序表、链表数据结构的特点（优缺点）。 二、实验预习 说明以下概念 1、线性表： 2、顺序表： 3、链表： 三、实验内容和要求 1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include #include #define ERROR 0 #define OK 1 #define INIT_SIZE 100 /*初始分配的顺序表长度*/ #define INCREM 5 /*溢出时，顺序表长度的增量*/ typedef int ElemType; /*定义表元素的类型*/ typedef struct Sqlist{ ElemType *slist; /*存储空间的基地址*/ int length; /*顺序表的当前长度*/ int listsize; /*当前分配的存储空间*/ }Sqlist; int InitList_sq(Sqlist *L); /* */ int CreateList_sq(Sqlist *L,int n); /* */ int ListInsert_sq(Sqlist *L,int i,ElemType e);/* */ int PrintList_sq(Sqlist *L); /*输出顺序表的元素*/ int ListDelete_sq(Sqlist *L,int i); /*删除第i个元素*/ int ListLocate(Sqlist *L,ElemType e); /*查找值为e的元素*/ int InitList_sq(Sqlist *L){ L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));

实验1(1) 线性表-顺序表及其应用-16

实验一线性表 班级: 姓名: 学号： 一、实验目的 1．掌握线性表的顺序存储结构的含义； 2．掌握动态内存分配方式和顺序表的类型定义； 3．掌握顺序表的基本操作的实现算法； 4．通过上机实践加强利用数据结构解决实际问题的能力。 二、实验要求 1．实验前做好充分准备，包括复习第一章、第二章所学内容，事先预习好本次实验内容； 2．实验时记录实验结果，按要求完成各题； 3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。 三、实验题目与要求 1．实验题目一：顺序表的类型定义及其相关操作算法的实现 要求：编程实现顺序表的类型定义及顺序表的初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。 2．实验题目二：顺序表的应用实例 结合课上讲过的顺序表的逆向删除操作的例子以及顺序表的逆置问题，编程实现。 四、实验内容 本指导书所给出的示例程序均为DEV C++环境下完成的，若使用其它C开发环境，则部分语句要进行少许修改。 1．实验题目一：顺序表的类型定义及其相关操作算法的实现 #include "stdio.h" #include "stdlib.h" //预定义常量及类型 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; //顺序表类型及其基本操作函数的定义 #define ListSpaceIncr 20 typedef int LElemType; typedef struct SqList { LElemType *base; int length; int listSize; }SqList; //SqList类型为顺序表类型 Status initList(SqList &L, int initSize) //初始化操作函数定义 { L.base=(LElemType*)malloc(InitSize*sizeof(LEl emType));//申请初始指定大小的存储空间 if(!L.base) return(OVERFLOW); L.length=0; L.listSize=InitSize; return OK; } Status listInsert(SqList &L, int i, LElemType e){ //顺序表的插入操作 LElemType *newBase; int j; if(i<1||i>L.length+1) return ERROR; if( L.length==L.listSize){ //补齐代码，若存储空间已满，则追加存储空间 newBase=(LElemType*)realloc(L.base, (L.listSize+ListSpaceIncr)*sizeof(LElemType) ); if(!newBase) return OVERFLOW; L.base=newBase; L.listSize+=ListSpaceIncr; } for(j= L.length-1; j>= i-1 ; j--) L.base[j+1]=L.base[j]; L.base[i-1]=e; L.length++; return OK; } Status listDelete(SqList &L, int i, LElemType &e){ //顺序表的删除操作 int j; if(i<1||i>L.length) return ERROR; e=L.base[i-1]; for(j= i ; j< L.length; j++) L.base[j-1]=L.base[j]; L.length--; return OK; }

线性表之顺序表与单链表的区别及优缺点

线性表之顺序表与单链表的区别及优缺点 线性表主要有顺序表和链表两种存储形式，贴主想问的，应该是将线性表la和l b头尾连接,要求时间复杂度为o(1),且占用辅助空间尽量小.应该使用哪种存储形式对吧？答案是应当采用链表。具体理由看文章。 这里比较的是基于C语言实现的顺序表与单链表，与其他语言的实现可能会有差异，但我相信语言是相通的，它们的实现机制应该也差不多。 1、What 什么是顺序表和单链表 ①顺序表： 顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L 是元素占用存储单元的长度。 ②单链表： 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。它的数据是以结点（类型一般为结构体）来表示的，每个结点的构成：数据（类型为要存储的数据的类型）+ 指针（结构体指针），数据就是链表里具体要存储的东西，指针就是用来把每个节点都连接起来，使它们形成一个链状。 结点： 链表：

2、Compare 二者的优缺点比较 ①空间上的比较（Space） a. 空间的开辟： 顺序表的实现一般是实现连续开辟一段空间，然后在进行数据的增删查改（静态顺序表），所以顺序表一般是固定空间大小的；而单链表则是一次只开辟一个结点的空间，用来存储当前要保存的数据及指向下一个结点或NULL的指针，所以单链表的空间大小时动态变化的。（当然，顺序表也可以在初始化时利用mallo c函数来开辟一块空间，每当空间不够用时，再用realloc来把当前空间扩容成2倍，从而也能实现空间的动态变化（动态顺序表））。

数据结构实验报告-2-1-线性表(顺序表实现)

实验2.1 线性表（顺序表实现）的基本操作及其应用 一、实验目的 1、帮助读者复习C语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在顺序表结构上的实现。 4、掌握顺序表的存储结构形式及其描述和基本运算的实现。 二、实验内容 [问题描述] 实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。[基本要求] （1）实现顺序表初始化操作； （2）实现插入元素的操作； （3）实现删除元素的操作； （4）实现更改元素的操作； （5）实现获取顺序表长度的操作； （6）实现获取元素的操作。 [代码模板] 1.顺序表数据类型： #define ListSize 10 typedef int DataType; typedef struct{ DataType data[ListSize]; int length; }SeqList; 三、源代码 void initList(SeqList * L) { L=(SeqList*)malloc(sizeof(SeqList)); L->length=0; } void insertList(SeqList * L, DataType x, int i) { int j; for (j=L->length-1; j>=i-1; --j) L->data[j+1]=L->data[j]; L->data[i-1]=x; ++L->length; } void deleteList(SeqList * L, int i)

{ int j; for (j=i; jlength; ++j) L->data[j-1]=L->data[j]; --L->length; } void updateList(SeqList * L, DataType x, int i) { L->data[i-1]=x; } int getLength(SeqList * L) { return L->length; } DataType getElem(SeqList * L, int i) { return L->data[i-1]; } 四、测试结果

数据结构 实验1 线性表(顺序表)

实验1 线性表（顺序表） 一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的顺序存储结构。通常称为顺序表。 2. 重点是线性表的基本操作在顺序存储结构上的实现；其中以插入和删除的操作为侧重点；并进一步学习结构化的程序设计方法。 3. 掌握使用 C语言中顺序表的程序设计方法，掌握阅读与补充源程序的方法。 二、实例 1. 线性表的顺序存储表示（结构）及实现。 （1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i ，在 存储地址中也是相邻的,既地址连续。顺序存储结构也称“向量（vector）”。在下列类设计中，采用静态一维数组elem[]表示向量,同时用length表示线性表长度。 ElemType elem[MAXSIZE]; int length; 有时可以采用动态一维数组来表示向量。 ElemType *elem; int length; int MAXSIZE 这要求在类的构造函数中，为其elem动态分配存储空间，而在析构函数中释放内存空间。 在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。同时用户必须自己编写一段主函数main()，在主函数中创建声明类的具体对象，通过这些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。 （2）下面是一个不太完整的的源程序，目的为学生提供一个示范，供学生参考。 线性表的顺序存储结构，顺序表类。本程序的特点是，数据元素的类型不再是简单类型（int,char,float），而是更加接近使实用的比较复杂的结构体类型。在数据元素输入输出时，情况比较复杂一些。 #include #include #define MAXSIZE 10000 typedef int ElemType; typedef struct list { ElemType *elem; int listsize;

数据结构线性表实验报告

一、实验目的和要求 （1）理解线性表的逻辑结构特性。 （2）深入掌握线性表的两种存储方法，即顺序表和链表。体会这两种存储结构之间的差异。 （3）重点掌握顺序表和链表上各种基本运算的实现。 （4）综合运用线性表解决一些复杂的实际问题。 二、实验内容 实验2.1 编写一个程序algo2-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char）,并在此基础上设计一个程序exp2-1.cpp，完成如下功能： （1）初始化顺序表L； （2）采用尾插法依次插入元素a，b，c，d，e； （3）输出顺序表L; （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第三个元素； （7）输出元素a的位置； （8）在第4个元素位置上插入元素f； （9）输出顺序表L； （10）删除L的第3个元素； （11）输出顺序表L； （12）释放顺序表L。 实验2.2 编写一个程序algo2-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序exp2-2.cpp，完成如下功能： （1）初始化单链表h； （2）采用尾插法依次插入元素a，b，c，d，e； （3）输出单链表h; （4）输出单链表h长度； （5）判断单链表h是否为空； （6）输出单链表h的第三个元素； （7）输出元素a的位置； （8）在第4个元素位置上插入元素f； （9）输出单链表h； （10）删除L的第3个元素； （11）输出单链表h；、 （12）释放单链表h。 释放顺序表L。 实验2.3 编写一个程序algo2-3.cpp，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序exp2-3.cpp，完成如下功能： （1）初始化双链表h； （2）采用尾插法依次插入元素a，b，c，d，e； （3）输出双链表h;

数据结构 线性表 顺序表 源代码C

#define MAXSIZE 100 //MAXSIZE 为线性表可能的最大长度 #include #include typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; // length为线性表的长度 } SqList; SqList l; //线性表定义 void InitList(SqList &L) //初始化操作，将线性表L置空 { L.length = 0;//g给顺序表长度初始化为0 } void CreatSqlist(SqList &L,int n) //建立一个顺序存储的线性表 { printf("请输入节点"); int i; for(i=0;iL.length)//删除位置错误 {printf("error");return 0;} else { for(j=i;j

《数据结构Java版》线性表之顺序表的建立及操作

《数据结构Java版》线性表之顺序表的建立及操作 package sjjg2; 1、LList.java接口 public interface LList { // 线性表接口，泛型参数T表示数据元素的数据类型 boolean isEmpty(); // 判断线性表是否空 int length(); // 返回线性表长度 T get(int i); // 返回第i（i≥0）个元素 void set(int i, T x); // 设置第i个元素值为x int insert(int i, T x); // 插入x作为第i个元素 int append(T x); // 在线性表最后插入x元素 T remove(int i); // 删除第i个元素并返回被删除对象 void removeAll(); // 删除线性表所有元素 int search(T key); // 查找，返回首次出现的关键字为key的元素的位序 } 2、SeqList.Java public class SeqList implements LList { protected Object[] element; protected int n; public SeqList(int length) //构造容量为length的空表 { this.element = new Object[length]; //申请数组的存储空间,元素为null.//若length<0，Java抛出负数组长度异常 https://www.doczj.com/doc/cd2810714.html,ng.NegativeArraySizeException this.n = 0; } public SeqList() //创建默认容量的空表，构造方法重载 { this(64); //调用本类已声明的指定参数列表的构造方法 } public SeqList(T[] values) //构造顺序表，由values数组提供元素，忽略其中空对象 { this(values.length*2); //创建2倍values数组容量的空表//若values==null，用空对象调用方法，Java抛出空对象异常NullPointerException for (int i=0; i=0 && i

实验报告(线性顺序表 )-模板

沈阳工程学院 学生实验报告 （课程名称：数据结构与算法） 实验题目：线性顺序表 班级软件151 学号2015417110 姓名杨红伟 地点F606 指导教师 实验日期: 2016 年9 月7 日

一、实验目的 1．了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2．掌握线性表的顺序存储结构的定义及其C语言的实现。 3．掌握线性表的链式存储结构——单链表的定义及其C语言的实现。 4．掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5．掌握线性表在链式存储结构——单链表的各种基本操作。 二、实验环境 Turbo C或是Visual C++ 三、实验内容与要求 实验顺序表的操作 请编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行表的创建，数据的插入删除并在插入和删除数据后再输出线性表；最后在屏幕菜单中选择0，即可结束程序的运行。 分析：当我们要在顺序表的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素一次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。当要删除第i个元素时，也只需将第i个元素之后的所有元素前移一个位置。 算法描述：对每个算法，都要写出算法的中文描述。本实验中要求分别写出在第i个（从1开始计数）结点前插入数据为x的结点、删除指定结点、创建一个线性表。打印线性表等的算法描述。 四、实验过程及结果分析 1.顺序表的输入算法如下，运行结果如图1所示： case 1: if(InitList(L)) printf("初始化成功！"); else printf("初始化失败！"); printf("请输入顺序表的内容！\n"); for(i=0;i<10;i++) { scanf("%d",&L.elem[i]); L.length++; }

第二章 线性表-顺序表

第二章线性表—顺序表 一、单项选择题 1、线性表是具有n个（ C ）的有限序列。 A、数据表 B、字符 C、数据元素 D、数据项 2、以下（ A ）是一个线性表。 A、由n个实数组成的集合； B、由n个字符组成的序列； C、所有整数组成的序列； D、邻接表 3、线性表的顺序存储结构是一种（B ） A、随机存取的存储结构 B、顺序存取的存储结构 C、索引存取的存储结构 D、散列存取的存储结构 4、一个顺序表所占用的存储空间大小与（B）无关。 A、表的长度 B、元素的存放顺序 C、元素的类型 D、元素中各字段的类型 5、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（ B ）的存储结构。 A、单链表 B、双向链表 C、单循环链表 D、顺序表 二、应用题 1、从有序顺序表中删除所有其值重复的元素，使得表中所有元素的值均不同。void DelListaelem (List L ) { if ( L.length<=0 ) { printf( “List is empty!”); exit(1); } int i = 0, j, k; elemType temp; while ( i <= L.length) {//循环检测 j = i + 1; temp = L.data[i]; while ( j <= L.length ) { //对于每一个i, 重复检测一遍后续元素 if ( temp == L.data[j] ) {//如果相等, 后续元素前移

for ( k = j+1; k <= L.length; k++ ) L.data[k-1] =L. data[k]; L.length--; //表最后元素位置减1 } else j++; } i++; //检测完L.data[i], 检测下一个 } } 2、设将n（n>1）个整数存放到一维数组R中。试设计一个算法：将R中保存的序列循环左移p（00 && p

线性表逆置(顺序表)实验报告

实验一：线性表逆置(顺序表)实验报告 (一)问题的描述：实现顺序表的逆置算法 (二)数据结构的设计：顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表：typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType) 为单位) */ }SqList; (三)函数功能、参数说明及概要设计： 1.函数Status InitList(SqList *L) 功能说明：实现顺序表L 的初始化算法设计：为顺序表分配 一块大小为LIST_INIT_SIZE 的储存空间 2.函数int ListLength(SqList L) 功能说明：返回顺序表L 长度算法设计：返回顺序表中的 length 变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明：将元素e插入到顺序表L中的第i个节点 算法设计：判断顺序表是否已满，已满则加空间，未满则继续，将元素e插入到第i个元素之前，并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明：依次对L 的每个数据元素调用函数vi() 算法设计：依次对L 的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明：实现顺序表L 的逆置 算法设计：用for 循环将顺序表L 中的第i 个元素依次与第( i+length )个元素交换 6.函数void print(ElemType *c) 功能说明：打印元素 c 算法设计：打印元素 c 2. (四)具体程序的实现