结构之美:定义一个线性表

从最简单的线性表开始讲起
服务器君一共花费了162.255 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

在计算机中,数据并不是孤立的,而是具有一定内在联系的数据集合,这种联系就是数据结构,说明数据如何被组织在一起的。下面我们从最简单的线性表开始讲起。

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

线性表——List,零个或多个数据元素的有限序列。

首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。

当线性表元素的个数n(n>=0)定义为线性表的长度时,如果n=0,则说明该线性表是个空表。

线性表的抽象数据类型(ADT)定义

线性表的抽象数据类型定义如下:

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1,a2,....an},每个元素的类型均为DataType.其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系.
Operation
       InitList(*L):初始化操作,建立一个空的线性表
       ListEmpty(L):若线性表为空,返回true,否则返回false.
       ClearList(*L):将线性表清空.
       GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e
       LocateElem(L,e):在线性表L中查找给定值e相等的元素,若查找成功,返回该元素在表中的序号表示成功,否则,返回0表示失败.
       ListInsert(*L,i,e):在线性表L中的第i个位置插入元素e.
       ListDelete(*L,i,*e):删除线性表L中第i个位置元素,并用e返回其值.
       ListLength(L):返回线性表L的元素个数.
EndADT

对于不同的应用,线性表的基本操作是不同的,但是上述操作是最基本的,对于实际问题中涉及的关于线性表的更复杂的操作,完全可以用这些基本操作的组合来实现。

举个例子,假设La表示集合A,Lb表示集合B,现在要得到一个集合A使得A=AUB:

void unionL(SqList *La,SqList Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for (i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);
        if (!LocateElem(*La,e))
            ListInsert(La,++La_len,e);
    }
}

这里,union的操作用到了ListLength,GetElem,LocateElem,ListInsert等基本方法。

线性表的定义

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构的代码如下:

#define MAXSIZE 20      /* 存储空间初始分配量 */
typedef int ElemType;   /* ElemType类型根据实际情况而定,这里假设为int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 数组,存储数据元素,最大值为MAXSIZE */
    int length;             /* 线性表当前长度 */
}SqList;

这里,我们发现描述顺序存储结构需要三个属性:

  1. 存储空间的起始位置——数组data,它的存储位置就是存储空间的存储位置。
  2. 线性表的最大存储容量——数组长度MAXSIZE
  3. 线性表的当前长度length

注意:线性表的长度应该小于等于数组的长度。

下面的程序定义线性表并初始化一些随机数:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSIZE 20      /* 存储空间初始分配量 */
typedef int ElemType;   /* ElemType类型根据实际情况而定,这里假设为int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 数组,存储数据元素,最大值为MAXSIZE */
    int length;             /* 线性表当前长度 */
}SqList;

//顺序表的初始化
SqList Init()
{   //构造一个空的线性表L,时间复杂度O(1)
    SqList L;       //定义一个顺序表
    L.length = 0;   //顺序表的长度为0
    return L;       //返回空顺序表
}

//顺序表的建立
SqList Create(SqList L)
{
    int i;
    srand((unsigned)time(NULL));
	for(i=0; i < 10; i++)
	{
		L.data[i] = rand()%100;
        L.length++;
	}
    return L;
}

int main()
{
    SqList nmList;
    nmList = Init();
    nmList = Create(nmList);

    int i;
    for(i=0; i < nmList.length; i++)
	{
        printf("%d ", nmList.data[i]);
	}
}

延伸阅读

此文章所在专题列表如下:

  1. 结构之美:定义一个线性表
  2. 结构之美:线性表的查找、插入与删除操作
  3. 结构之美:线性表的链式存储结构——链表
  4. 结构之美:单链表的初始化、创建与遍历
  5. 结构之美:单链表的头结点与头指针
  6. 结构之美:使用头插法创建单链表
  7. 结构之美:使用尾插法创建单链表
  8. 结构之美:单链表的销毁删除
  9. 结构之美:查找单链表指定位置结点的数据
  10. 结构之美:在单链表指定位置插入数据
  11. 结构之美:删除单链表指定位置的数据
  12. 结构之美:单链表逆序
  13. 结构之美:判断单链表中是否有环
  14. 结构之美:获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美:双向循环链表的结构与定义

本文地址:http://www.nowamagic.net/librarys/veda/detail/1786,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1786

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《致加西亚的信》 阿尔伯特·哈伯德(Hubbard.E.) (作者), 赵立光 (译者), 艾柯 (译者)

《致加西亚的信(经典盒装版)》内容简介:美西战争爆发以后,美国必须立即与古巴起义军首领加西亚取得联系,并获得他的合作。但当时,加西亚身在古巴的深山里——没有人知道他的确切地点,所以没法与他取得联系。这时,有人向总统推荐一个名叫罗文的人,说他有办法找到加西亚,而且也只有他才能找得到。他们找来罗文,交给他一封写给加西亚的信。三周后,罗文徒步走过一个危机四伏的国家,最终把那封信交给了加西亚。 此后,罗文的事迹被传为佳话,“送信”成为了敬业、忠诚、勤奋的象征,罗文便成了每个领导都想找到的人和每个员工都应该学习和效仿的榜样。

更多计算机宝库...