`
wsql
  • 浏览: 11715337 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

顺序表

 
阅读更多

顺序表,简而言之就是基于顺序存储结构下的线性表。所谓顺序存储结构就是使用一组连续地址的内存单元来存储整张线性表的内容。

顺序表的定义方式常有两种,一种是静态定义,另一种是动态定义和生成。

顺序表静态定义代码如下所示:

//顺序表静态定义
#define MaxSize 100//顺序表的最大容量
typedef int ElemType;

ElemType SqList[MaxSize];
int length;//顺序表的长度

顺序表动态定义和初始化代码如下所示:

//顺序表动态定义
#define MaxSize 100
typdef int ElemType;
typedef struct {
   ElemType *elem;
   int length;//顺序表的实际长度
   int listSize;//顺序表的容量
}SqList;

/**
  *方法描述:顺序表初始化
  *输入参数:SqList *L
  *返回类型:void
  */
void initSqList(SqList *L) {
  L->elem = (ElemType *)malloc(MaxSize * sizeof(ElemType));
  if(! L->elem) {
    exit(0);
  }
  L->length = 0;
  L->listSize = MaxSize;
}

不管是静态定义的顺序表,又还是动态定义的顺序表,它们都具有一些相同的基本操作,例如,向顺序表的具体位置插入一个元素,删除具体位置上的元素,遍历顺序表上的内容。虽说定义方式有些差异,但是基本操作的实现方式思路较为类同。现分别以静态定义和动态定义下的插入操作为例。详细代码如下所示:

/**
 *方法描述:在静态定义的顺序表中的第i个位置插入元素
 *输入参数:ElemType sqlist[],int *len,int i,int iNum
 *返回类型:int 顺序表的长度
 */
int insertElem(ElemType sqlist[],int *len,int i,int iNum) {
	int t;
	if(*len == MaxSize || i<1 || i>*len+1) {
		printf("This insert is illlegal\n");
		return *len ;
	}

	for(t=*len-1;t>=i-1;t--) {
		sqlist[t+1] = sqlist[t];
	}
	sqlist[i-1] = iNum;
	*len = *len + 1;

	return *len;
}

/**
 *方法描述:向动态定义的顺序表中的第i个位置插入元素
 *输入参数:SqList *L,int i,ElemType item
 *返回类型:void
 */
void insertElem(SqList *L,int i,ElemType item) {
	ElemType *base, *insertPtr,*p;

	if(i<1 || i>L->length+1) {
		exit(0);
	}

	if(L->length >= L->listSize) {
		base = (ElemType *) realloc(L->elem,(L->listSize + 10) * sizeof(ElemType));
		L->elem = base;
		L->listSize += 100;
	}

	insertPtr = &(L->elem[i-1]);
	for(p=&(L->elem[L->length-1]);p>=insertPtr;p--) {
		*(p+1) = *p;
	}

	*insertPtr = item;
	L->length ++;

}

同一基本操作在不同的顺序表定义方式,细微差异在于动态定义可以追加开辟存储空间,从而不用担忧顺序容量的问题。

顺序表是最简单的一种数据结构,其优点:构造简单,操作方便,并且利用数组名(或者顺序表的首地址)就可以直接对表中的内容进行随机存取,从而存取速度快,系统开销小。但是,它也存在着缺点:有可能浪费存储空间,另外在进行插入和删除基本操作时,需要对插入或删除位置后面的所有元素逐个进行移动,从而导致操作效率较低。因此,顺序表适用于表的长度不经常发生变化的场合。

参考资料:

【1】杨峰 著.妙趣横生的算法(C语言实现).北京:清华大学出版社,2011

分享到:
评论

相关推荐

    数据结构中的顺序表代码

    /*构造一张新的顺序表*/ int ListLength_Sq(List l); /*求顺序表L的长度*/ void GetElem_Sq(List *L,int i,ElemType e); /*获取顺序表L的第i个元素*/ int EqualList(ElemType e1,ElemType e2); /*判断数据元素e1,e2...

    顺序表的各种基本运算

    编写一个程序,实现顺序表的各种基本运算,并在此基础上完成以下功能: 1) 初始化顺序表; 2) 依次采用尾插入法插入a,b,c,d,e元素; 3) 输出顺序表L; 4) 输出顺序表L的长度; 5) 判断顺序表L是否为空; 6) 输出顺序...

    编写一个完整顺序表的程序

    (1) 建立一个顺序表,含有n个数据元素。 (2) 输出顺序表及顺序表的长度。 (3) 在顺序表给定的位置i,插入一个值为x的结点。 (4) 在顺序表中删除值为x的结点或者删除给定位置i的结点。 (5) 将顺序表逆置,...

    顺序表的建立

    顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素...

    顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用

    顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用 顺序表及其应用

    用顺序表完成2个集合的交集与并集以及各个集合的情况

    1.有序顺序表的元素按照从小到大有序存储; 2.实现有序顺序表的类模板,它的操作如下: a)构造函数;b)拷贝构造函数;c)析构函数; d)计算表长度,并输出; e)定位函数:查找x在表中位置; f)判断x是否在表中;g) 向表...

    使用c++实现顺序表的基本操作:1、顺序表的初始化2、顺序表的长度3、顺序表插入元素4、删除顺序表元素5、遍历顺序表

    使用c++实现顺序表的基本操作: 1、顺序表的初始化 2、顺序表的长度 3、顺序表插入元素 4、删除顺序表元素 5、遍历顺序表 6、查找顺序表元素

    实现顺序表的基本运算:初始化、插入、删除、求表的长度、判空、释放。

    (1)初始化顺序表L (2)从标准输入(键盘)逐个数据输入a,b,c,d,e元素 ,建立顺序表 (3)输出顺序表L (4)输出顺序表L的长度 (5)判断顺序表L是否为空 (6)输出顺序表L的第3个元素 (7)输出元素a的位置...

    顺序表基本操作

    顺序表基本操作 顺序表实现 顺序表

    实用算法实验_顺序表的应用

    首先,逐行读取指定文件中的数据,并进行解析后保存在顺序表中。其中,文件中每行数据格式为“学号,姓名,年龄”,比如“SA10225048,[yyw1] 张三,24”。 (提示:采用顺序表结构时,顺序表中每个表元素包含三类信息...

    shunxubiao.rar_shunxubiao_输入一组整型元素序列,建立顺序表

    输入一组整型元素序列,建立顺序表。 (2).实现该顺序表的遍历。 (3).在该顺序表中顺序查找某一元素,查找成功返回1,否则返回0。 (4).判断该顺序表中元素是否对称,对称返回1,否则返回0。 (5).实现把该表中所有奇数...

    顺序表的C++程序实现

    用模板方式实现顺序表的合并 #include "stdafx.h" #include &lt;iostream.h&gt; #define MaxSize 100 template &lt;class T&gt; class SeqList { private: T * Mylist; int ListMaxSize; int Length; public: ...

    数据结构实验一(顺序表基本操作)题目和源程序

    1.编写程序实现顺序表的下列基本操作: (1)初始化顺序表La。 (2)将La置为空表。 (3)销毁La。 (4)在La中插入一个新的元素。 (5)删除La中的某一元素。 (6)在La中查找某元素,若找到,则返回它在La中第一次出现...

    两个有序顺序表合并成一个顺序表,还是有序的

    两个有序顺序表合并成一个顺序表,还是有序的

    顺序表的基本操作的实现

    1,利用顺序表的操作实现以下函数: (1)从顺序表中删除具有最小值的元素,并由函数返回被删除元素的值。空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息,并退出运行。 (2)在顺序表的第i个位置之后...

    实验一 顺序表的操作、插入与删除

    熟悉数据移动是顺序表的操作特点 掌握顺序表中元素的移动、插入和删除操作的特点 题1 设有一个用向量表示的线性表a[n],a[0]中不存放线性表的元素。要求写出将其中元素逆置的函数,并只允许用a[0]作附加的工作单元。...

    顺序表头文件顺序表头文件

    顺序表头文件顺序表头文件顺序表头文件顺序表头文件

    数据结构实验——顺序表

    [问题描述] 当我们要在顺序表的第i个位置上插入一个元素时,必须先将顺序表中第i个元素之后的所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置。若是欲删除第i个元素时,也必须把第i个元素之后...

    线性表之顺序表

    数据结构之顺序表,建表、查询、插入、删除,所有的过程

    创建一个静态的顺序表存放整数

    创建一个静态的顺序表存放整数。大小为10.完成以下的操作输入6个整数,1.打 印出顺序表中的内容,并显示表中剩余的空间个数。在顺序表中的第3个位置插入元素O.2.打印出顺序表中的内容,并显示表中剩余的空间个数。再...

Global site tag (gtag.js) - Google Analytics