数据结构-第二章-线性表

graph LR
A[线性表] --> B(线性表的定义和基本操作)
A-->C(线性表的顺序表示)
C-->C.1[顺序表的定义]
C-->C.2[顺序表的基本操作]
A-->D(线性表的链式表示)
D-->D.1[单链表的定义]
D-->D.2[单链表的基本操作]
D-->D.3[几种常用的链表]
D.3-->D.3.1[双链表]
D.3-->D.3.2[循环链表]
D.3-->D.3.3[静态链表]

线性表

是具有相同类型的n(n>=0)个元素的有限序列，其中n为表长，当n=0时，该表为空表。

线性表的特点

• 表中元素有限
• 表中元素具有逻辑上的顺序性，在序列中各个元素排序有其先后次序
• 表中元素都是数据元素，每个元素都是单个元素
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
• 表中元素具有抽象性，即讨论元素间一对一的逻辑关系，而不考虑匀速究竟表示的内容
• 线性表是一种逻辑结构，表示元素之间一对一相邻的关系

线性表的九种基本操作

1. InitList(&L):初始化表。构造一个空的线性表。
2. DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
3. LocateElem(L,e):按值查找操作。在表中L查找具有给定关键字值的元素。
4. GetElem(L,i):按位置查找操作。获取表L中的第i个位置的元素的值。
5. ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素。
6. ListDelete(&L,i,&e):删除元素。删除表L中第i个位置元素，并用e返回删除元素的值。
7. PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
8. Empty(L):判空操作。若L为空表，则返回True，否则返回FALSE。
9. Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。

线性表的顺序表示

顺序表的定义

1. 线性表的顺序存储又称顺序表
2. 一组地址连续存放的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。即逻辑顺序与物理顺序相同。

顺序表的实现

1. 数组静态分配

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

2. 数组的动态分配

#define MaxSize 50
typedef struct{
   ElemType *data;
   int length;
}SqList;

动态分配语句

1. C语言中

L.data=(Elemtype*)molloc(sizeof(ElemType)*InitSize);

2. C++语言中

L.data=new ElemType[InitSize];

线性表-顺序表的基本操作

1. 插入操作

bool ListInsert(SqList &L,int i,ElemType e){
    if(i< 1||i> L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

2. 删除操作

bool ListDelete(SqList &L,int i,ElemType &e){
    if(i< 1||i> L.length)
        return true;
    e=L.data[i-1];
    for(int j=i;j< L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}

3. 按值查找(返回第一个相等的元素的下表 )

int LocateElem(SqList L, ElemType e){
    int i;
    for(i=0;i< L.length;i++)
        if(L.data[i]**e)
            return i+1;
    return 0;        
}

线性表-链式表示

单链表

1. 线性表的链式存储又称单链表
2. 通过一组任意的存储单元来存储线性表中的数据元素
3. 通过指针实现线性逻辑关系

定义单链表

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

单链表基本操作

1. 头插法建立

LinkList List_HeadInsert (LinkList &L){
  LNode *s; int x;
  L= (LinkList)malloc(sizeof(LNode));
  L->next=null;
  scanf("%d",&x);
  while(x!=9999){
      s=(LNode*)malloc(sizeof(LNode));
      s->data=x;
      s->next=L->next;
      L->next=s;
      scanf("%d",&x);
  }
  return L;
}

2. 尾插法建立

LinkList List_TailInsert (LinkList &L){
  int x;
  L = (LinkList)malloc(sizeof(LNode));
  LNode *s, *r = L;
  scanf("%d", &x);
  while(x!=9999){
      s=(LNode*)malloc(sizeof(LNode));
      s->data=x;
      r->next=s;
      r=s;
      scanf("%d", &x);
  }
  r->next=NULL;
  return L;
}

3. 按序号查找&按值查找

按序号查找

LNode *GetElem(LinkList L,int i){
    int j = 1;
    LNode *p=L->next;
    if(i**0)
        return L;
    if(i< 1)
        return NULL;
    while(p&&j< i){
        p=p->next;
        j++;
    }
    return p;
}

按值查找

LNode *LocateElem(LinkList L, ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    return p;
}

线性表-特殊链表

双链表

定义双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

1. 插入操作

s-> next =p->next;
p->next->prior=s;
s->prior =p;
p->next =s;

2. 删除操作

p->next=q->next;
q->next->prior =p;
free(q);

循环单链表

判空条件

 L->next**L;

循环双链表

判空条件

 L->next**L;
 L->prior**L;

静态链表

定义：

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

顺序表VS链表

• 存取方式

顺序表可以实现顺序存取和随机存取

单链表只能实现顺序存取

• 逻辑结构和物理结构

顺序表 逻辑相邻物理上也相邻，通过相邻表示逻辑关系

单链表 逻辑相邻物理上不一定相邻，通过指针表示逻辑关系

• 基本操作

插入&删除

单链表为O(1)(节点指针已知);O(n)(节点指针未知)，但操作时只需要修改指针

顺序表为O(n)且需要大量移动元素

查找

按值查找中单链表和顺序表(无序)都为O(n)

按序查找中单链表为O(n),顺序表为O(1)

• 内存空间

顺序存储

无论静态分配还是非静态分配都需要预先分配合适的内存空间。1. 静态分配时预分配空间太大会造成浪费，太小会造成溢出；2. 动态分配时虽然不会溢出但是扩充需要大量移动元素，操作效率低。

链式存储

在需要时分配节点空间即可，高效方便，但指针要使用额外空间

线性表三个常用操作

1. 最值

顺序表

int min = L[0];
int max = L[0];
for(int i = 0;i < n;i++){
    if(min>L[i])
        min = L[i];
    if(max < L[i])
        max = L[i];
}

链表

int min = p -> next -> data;
int max = p -> next -> data;
for(;p!=NULL;p=p->next){
    if(min > p -> data)
        min = p -> data;
    if(max < p -> data)
        max = p -> data;
}

2. 逆置

顺序表

int i = 0;
int j = n-1;
while(i < j){
    temp = L[i];
    L[i] = L[j];
    L[j] = temp;
}

链表

while(p->next!=r){
    temp = p -> next;
    p -> next = temp -> next;
    temp -> next = r -> next;
    r -> next = temp;
}

3. 归并

顺序表

int i = 0,j = 0;
int k = 0;
for(;i < L1-Size && j < L2-Size;k++){
   if(L1[i] < L2[j])
    L[k] = L1[i++];
   else
    L[k] = L2[j++];
}

while(i < L1-Size)
    L[k++] = L1[i++];
while(j < L2-Size)
    L[k++] = L2[j++];

链表

while(p -> next!=NULL&&q ->next!=NULL){
    if(p->next->data < q->next->data){
        r->next=p->next;
        p->next =p->next->next;
        r= r->next;
    }else{
        r->next=q->next;
        q->next= p->next->next;
        r = r->next;
    }
}
if(p->next!=NULL)
    r -> next = p -> next;
if(q->next!=NULL)
    r -> next = q-> next;
free(p);
free(q);