「数据结构」线性表

Posted on by hackdl

定义和基本操作

  1. 定义：相同数据类型的

    n

    (

    n

    ≥

    0

    )

    n(n ge 0)

    n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表

  2. 一般表示：

    L

    =

    (

    a

    1

    ,

    a

    2

    ,

    …

    …

    ,

    a

    i

    ,

    a

    i

    +

    1

    ,

    a

    n

    )

    L=(a_1,a_2,……,a_i,a_{i+1},a_n)

    L=(a1​,a2​,……,ai​,ai+1​,an​)

    1. a

      1

      a_1

      a1​是表头元素，

      a

      n

      a_n

      an​是表尾元素

  3. 除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继

基本操作

  1. InitList(&L)；初始化表。构造一个空的线性表L，分配内存空间
  2. DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间
  3. ListInsert(&L,i,e)：插入操作。在表L中的第i个位置插入指定元素e
  4. ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
  5. LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
  6. GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

其他常用操作

  1. Length(L)：求表长。返回线性表L中数据元素的个数
  2. PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值
  3. Empty(L)：判空操作。若L为空表，返回true，否则返回false

顺序表

定义

  1. 顺序表：用顺序存储的方式实现线性表的顺序存储。把逻辑上相邻的元素存储在物理位置也相邻的存储单元中
  2. 顺序表的实现-静态分配
#define MaxSize 50		//线性表的最大长度

typedef struct {
	ElemType data[MaxSize];	//顺序表的元素
	int length;			//顺序表的当前长度
}SqList;				//顺序表的类型定义
  1. 顺序表的实现-动态分配
    1. 时间开销大
#define InitSize 50		//顺序表的初始长度
//动态分配
typedef struct {
	ElemType* data;	//指针动态分配数组的指针
	int maxsize;	//顺序表的最大容量
	int length;	//顺序表的当前长度
}SeqList;
  1. 动态申请和释放内存空间
    1. C：malloc、free函数

L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize); //C语言初始动态分配

	2. C++：new、delete关键字
	```C++
L.data = new int[InitSize];
  1. 顺序表的特点
    1. 随机访问，可以在O(1)时间内找到第i个元素
    2. 存储密度高
    3. 拓展容量不方便
    4. 插入、删除操作不方便，需要移动大量元素

插入和删除

插入

  1. ListInsert(&L,i,e)：插入操作。在表L中第i个位置上插入指定元素
bool ListInsert(SqList& L, int i, int e){
	if (iL.length + 1) {	//判断i的范围是否有效
		return false;
	}
	if (L.length >= MaxSize) {	//当前存储空间已满，不能插入
		return false;
	}
	for (int j = L.length; j >= i; j--) {	//将第i个元素及之后的元素后移
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;	//在位置i处放e
	L.length++;	//长度加1
	return true;
}
  1. 时间复杂度
    1. 最好情况：在表尾插入（即i=n+1），不需要移动元素，时间复杂度为O(1)
    2. 最坏情况：在表头插入（即i=1），元素后移语句执行n次，时间复杂度为O(n)
    3. 平均情况：移动结点的平均次数

      n

      2

      frac{n}{2}

      2n​，时间复杂度O(n)

删除

bool ListDelete(SqList& L, int i, int& e){
	if (iL.length + 1) {	//判断i的范围是否有效
		return false;
	}
	e = L.data[i - 1];	//将被删除的元素赋值给e
	for (int j = i; j
  1. 时间复杂度
    1. 最好情况：删除表尾元素（即i=n）,时间复杂度为O(1)
    2. 最坏情况：删除表头元素（即i=1），时间复杂度为O(n)
    3. 平均情况：移动结点的平均次数

      服务器托管网

      n

      −

      1

      2

      frac{n-1}{2}

      2n−1​，时间复杂度O(n)

查找

按位查找

  1. GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值
int GetElem(SqList L, int i){
	return L.data[i - 1];
}

int GetElem(SeqList L, int i){
	return L.data[i - 1];
}
  1. 时间复杂度O(1)
    1. 随机存取特性

按值查找

  1. LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
int LoacteElem(SqList L, int e){
	int i;
	for (i = 0; i
  1. 时间复杂度
    1. 最好情况：查找的元素在表头，时间复杂度为O(1)
    2. 最坏情况：查找的元素在表尾（或不存在），时间复杂度为O(n)
    3. 平均情况：平均比较次数

      n

      +

      1

      2

      frac{n+1}{2}

      2n+1​，时间复杂度为O(n)

单链表

定义

typedef struct LNode {	//定义单链表结点类型
	int data;	//每个结点存放一个指针元素
	struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;
  1. 不带头结点的单链表
bool InitList(LinkList& L){
	L = NULL;	//空表，暂时没有任何结点
	return true;
}
  1. 带头结点的单链表
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));	//分配一个头结点
	if (L == NULL) {
		return false;
	}
	L -> next = NULL;	//头结点之后暂时还没有结点
	return true;
}

插入和删除

按位序插入（带头结点）

  1. ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
bool ListInsert(LinkList &L, int i, ElemType e){
	if(inext;
		j++;
	}
	if(p==NULL){    //i值不合法
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p-next=s;    //将结点s连到p之后
	return true;    //插入成功
}

按位序插入（不带头结点）

  1. ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
bool ListInsert(LinkList &L, int i, ElemType e){
	if(idata=e;
		s->next=L;
		L=s;    //头指针指向新结点
		return true;    //插入成功
	}
	LNode *p;    //指针p指向当前扫描的结点
	int j=1;    //当前p指向的是第几个结点
	p=L;    //p指向第1个结点（不是头结点）
	while(p!=NULL && jnext;
		j++;
	}
	if(p==NULL){    //i值不合法
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p-next=s;    //将结点s连到p之后
	return true;    //插入成功
}

指定结点的后插操作

//在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL){    //内存分配失败
		return false;
	}
	s->data=e;    //用结点s保存数据元素e
	s->next=p->next;
	p->next=s;    //将结点s连接到p之后
	return true;
}

指定元素的前插操作

//在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL){    //内存分配失败
		return false;
	}
	s->next=p->next;
	p->next=s;    //将结点s连接到p之后
	s->data=p->data;    //将p中的元素复制到s中
	p->data=e;    //p中元素覆盖为e
	return true;
}

按位序删除（带头结点）

  1. ListDelete(&L,i,&e)；删除操作，删除表L中第i个位置的元素，并用e返回元素的值
bool ListDelete(LinkList &L，int i,ElemType &e){
	if(inext;
		j++;
	}
    if(p==NULL){    //i值不合法
	    return false;
	}
    if(p->next == NULL){    //第i-1个结点之后已无其他结点
        return false;
    }
	LNode *q=p->next;    //令q指向被删除结点
	e = q->data;    //用e返回元素的值
	p->next=q->next;    //将*q结点从链中“断开”
	free(q);    //释放结点的存储空间
	return true;    //删除成功
}

指定结点的删除

//删除指定结点p
bool DeleteNode (LNode *p){
	if (p==NULL){
		return false;
	}
	LNode *q=p->next;    //令q指向*p的后继结点
	p->data=p->next->data;    //和后继结点交换数据域
	p->next=q->next;    //将*q结点从链中“断开”
	free(q);    //释放后继结点的存储空间
	return true;
}

如果p是最后一个结点，只能从表头开始寻找p的前驱，时间复杂度O(n)

查找

按位查找

  1. GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值
//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList, int i){
	if(inext;
	    j++;
	}
	return p;
}
  1. 平均时间复杂度O(n)

按值查找

  1. LocateElem(L,i)：按值查找操作。在表L中查找具有给定关键字值的元素
//按值查找，找到数据域==e 的结点
LNode * LocateElem(LinkList L,ElemType e){
	LNode *p = L->next;
	//从第1个结点开始查找数据域为e的结点
	while (p != NULL && p->data != e)
		p = p->next;
	return p;    //找到后返回该结点指针，否则返回NULL
}
  1. 时间复杂度O(n)

求表的长度

//求表的长度
int Length(LinkList L){
	int len = 0;    //统计表长
	LNode *p = L;
	while (p->next != NULL){
		p = p->next;
		len++;
	}
	return len;
  1. 时间复杂度O(n)

建立

  1. 尾插法
  2. 头插法

双链表

  1. 初始化
  2. 插入
  3. 删除
  4. 遍历

循环链表

  1. 循环单链表：表尾结点的next指针指向头结点
    1. 从一个结点出发可以找到其他任何一个结点
  2. 循环双链表

静态链表

  1. 概念：分配一整连续的内存空间，各个结点集中安置

顺序表和链表的比较

  1. 逻辑结构
    1. 都属于线性表，都是线性结构
  2. 物理结构/存储结构
    1. 顺序表
      1. 优点：支持随机存取、存取密度高
      2. 缺点：大片连续空间分配不方便，改变容量不方便
    2. 链表
      1. 优点：离散的小空间分配方便、改变容量方便
      2. 缺点：不可随机存取、存取密度低
  3. 数据的运算/基本操作
    1. 初始化
      1. 顺序表：需要预分配大片连续空间若分配空间过小，则之后不方便拓展容量;若分配空间过大，则浪费内存资源
        1. 静态分配：静态数组，容量不可改变
        2. 动态分配：动态数组（malloc、free），容量可改变，但需要移动大量元素，时间代价高
      2. 链表：只需分配一个头结点 (也可以不要头结点，只声明一个头指针) ，之后方便拓展
    2. 销毁
      1. 顺序表：修改Length=0
        1. 静态分配：系统自动回收空间
        2. 动态分配：需要手动free
      2. 链表：依次删除各个结点(free)
    3. 插入和删除
      1. 顺序表：需要把后续元素后移/前移，若数据元素很大，则移动的时间代价很大
      2. 链表：修改指针
    4. 查找
      1. 顺序表
        1. 按位查找：O(1)
        2. 按值查找：O(n)
          1. 若表内元素有序，可在

            O

            (

            l

            o

            g

            2

            n

            )
            服务器托管网

            O(log_2n)

            O(log2​n)时间内找到

      2. 链表
        1. 按位查找：O(n)
        2. 按值查找：O(n)

开放式问题回答思路

问题： 请描述顺序表和链表的 bla bla bla… 实现线性表时，用顺序表还是链表好?

顺序表和链表的逻辑结构都是线性结构，都属于线性表但是二者的存储结构不同，顺序表采用顺序存储…(特点，带来的优点缺点): 链表采用链式存储…(特点、导致的优缺点)。由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…; 当查找一个数据元素时…

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: