数据结构-线性表

线性表的定义和基本操作

线性表是具有相同数据类型的n个数据元素的有限序列，n为表长。

• 表中元素个数有限
• 元素有先后顺序
• 元素类型相同，意味元素占有相同大小的存储空间

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，勿混淆

InitList(&L) // 初始化表

Length(L) // 求表长

LocateElem(L,e) // 按值查找

GetElem(L,i) // 按位查找

ListInsert(&L, i, e) // 插入操作

ListDelete(&L, i, &e) // 删除操作

PrintList(L)  // 打印

Empty(L)  // 判空操作

Destroy(&L) // 销毁释放内存

线性表的顺序表示

顺序表的顺序存储又称为顺序表

#define MaxSize 50

typedef struct{

    ElemType data[MaxSize];

    int length;

}SqList;

#define InitSize 100

typedef struct{

    ElemType *data;

    int MaxSize, length;

}SeqList;

顺序表的基本操作实现

插入操作

在顺序表的第i个元素插入新元素e O(n)

删除操作

删除顺序表的第i个元素并用变量e返会 O(n)

按值查找

查找第一个值位e的元素并返回位序 O(n)

线性表的链式表示

单链表的定义

线性表的链式存储又称单链表

typedef struct LNode{

    ElemType data;

    struct LNode *next;

}LNode, *LinkList;

带头结点的单链表

• 不管带不带头结点，头指针都指向链表的第一个结点
  头结点的优点
• 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操收和在表的其他位置上的操作一致无须讲行特殊处理。
• 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一。

单链表上操作的实现

头插法建立单链表 O(n)

尾插法 O(n)

按序号查找结点值 O(n)

按值查找结点 O(n)

插入结点

查找到元素的插入位置的时间复杂度 O(n) 实际插入是O(1)

删除结点操作

双链表

typedef struct DNode{

    ElemType data;

    struct DNode *prior,*next;

}DNode, *DLinkList;

插入操作

删除操作

循环链表

• 循环单链表
  在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。·
  
• 循环双链表
  在循环双链表工中，某结点*p为尾结点时，p->next == L;当循环双链表为空表时，其头结点的prior域和next域都等于L。
  

  静态链表

  

  #define MaxSize 50
  
  typedef struct{
  
      ElemType data;
  
      int next;
  
  }SLinkList[MaxSize];