线性表的定义

线性表是具有相同数据类型的N（N=>0）个数据元素的有限序列，N为表长，N=0 时 线性表为空表。

线性表的基本操作

initList（&L）：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList（&L）：销毁操作。销毁线性表，并释放线性表L所占的内存空间。

ListInsert（&L，i，e）：插入操作。在表L中的第i个位置上插入元素e。

ListDelete（&L，i，&e）：删除操作。删除表L中的第i个位置的元素，并用e返回删除元素的值。

locateElem（L，e）：按值查找操作，在表L中查找具有给定关键字值的元素。

其他常用操作：

Length（L）：求表长，返回线性表L的长度，即L中数据元素的个数。

PrintList（L）：输出操作。按前后顺序输出线性表L中的所有元素。

Empty（L）：判断是否为空操作。若L为空表，返回true，否则返回false。

顺序表的定义

用顺序存储的方式实现线性表。把逻辑上相邻的元素存储在物理位置上也相邻的位置。

由于每个数据元素所占空间大小一样，所有A1到A2 = A1+（数据元素的大小）=A2

|A1|A2|A3|

↑ ↑

L L+数据元素大小

顺序表的实现

静态分配

事先定义数组的最大长度，长度不可该变。

数组在内存中占用的是连续的空间

 #include<stdio.h>
#define MaxSize 10 //定义最大长度
typeof struct {
  ElementType data[MaxSize];// 元素的集合
  int Length;//顺序表的当前长度
}SqlList

//定义一个初始化顺序表的操作
void InitList(Sqllist& L)
{
  for(int i=0;i<MaxSize;i++)
	{
       L.data[i]=0;//如何不初始化为0，默认的内存中可能存储的是随机数据（也可能为之前遗留的脏数据）
	}
     L.Length=0;
}
void Main()
{
  SqlList L;//声明一个顺序表
  InitList（&L）;//初始化顺序表
}

动态分配

#define InitSize 10 //init Size of List
typedef struct{
 int * data ;//指向动态分配的数组的指针
 int MaxSize;//顺序表的最大容量
 int Length;//顺序表的当前元素个数（长度）
}
void initList(SeqList &L)
{
    L.data =(int*) malloc(InitSize*sizeof(int));
	L.length=0;
    L.MaxSize=InitSize;	
}
//实现动态增加数组的长度
void IncreaseSize(SeqList &L,int len)
{
  int *p=L.data;
  L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));//申请新的内存空间
    for(int i=0;i<L.length;i++)
	{
      L.data[i]=P[i]; //把旧的数据拷贝到新的内存空间
	}
    L.MaxSize=L.MaxSize=len;//更新大小
    free(p);//释放旧的内存空间
}
void Main()
{
   SeqList L;
   InitList(L);
 IncreaseSize)(&L,5);

}

顺序表的特点

1. 随机访问，可以在O（1）时间内找到第i个元素。
2. 存储密度高，每个节点只存储数据元素。（链表则要多存一个指针等）
3. 拓展容量不方便（即便用动态分配的方式，拓展长度的时间复杂度也高，因为要把旧的数据拷贝到新的内存）
4. 插入，删除不方便，需要移动大量的元素

顺序表的插入和删除

#define MaxSize 10
typeof struct {
 int data[MaxSize];
 int length;
}list;

void ListInsert(list& L,int index ,int e )
{

  for(int i=L.length;i>=index;i--)
	{
       L.data[i]=Ldata[i-1]; //将第Index个元素及之后的元素后移	
	}
    L.data[index-1]=e; //在index处放入e 
     L.lenght++;
}
//为了代码的健壮性，首先判断要判断要插入的下标不能越界。以及保证线性表的连续性：
比如有长度为7数组如下:
原始数组：[1][2][3][4][][][]
想在6或者7下标插入数据 [1][2][3][4][][5][]
我们不能直接在Length+1 往后的下标插入数据导致数据的不连续;
以及添加一个返回值 便于让使用者判断是否插入成功
//修改后的
bool ListInsert(list& L,int index ,int e )
{
    if(index<0||index>Length+1)//判断index的范围是否合法  
     return false;
    if(L.length >=MaxSize)//判断存储空间是否已满
     return false;
     
   for(int i=L.length;i>=index;i--)
	{
       L.data[i]=Ldata[i-1]; //将第Index个元素及之后的元素后移	
	}
     L.data[index-1]=e; //在index处放入e 
     L.lenght++;
    return true;
}

顺序表的删除

bool ListInsert(List& L,int index ,int& e)
{
    if(index <0|| index >L.length)
    return false;
    if(index >= MaxSize )
    return false;
    *e=L.data[index -1];//可以将删除的数据返回
    for(int i=index-1 ;i<L.length;i++)
	{
       L.data[i]=L.data[i+1];
	}
    L.length--;
    return true;
}

顺序表的查找

按位查找 和 按值查找

按位查找

Element GetElement(List* L,int index )
{
   if(index<0||index >L.length-1)
   return NULL;
   return L.data[index];
}

按值查找元素的位序（从1开始数的第几个）

int GetElement(List* L,int value )
{
   for(int i=0;i<L.length ;i++)
    {
      if(L.data[i]==value )
      {
          return i+1;
      }
	}
  return -1;
}

单链表的定义

单链表的优点：不要求大片连续的空间，改变容量方便

缺点：不可随机存取，要耗费一定的空间存放指针

用代码定义一个单链表

tip: typedef 关键字 -- 给数据类型起别名 typedef <数据类型> <别名>

typedef struct LNode{  	//定义单链表节点类型
   elementType data; 	//每个节点存放一个数据类型
   struct LNode* Next;	//指针指向下一个节点
}LNode;

//链表的初始化
//不带头节点
void Main()
{
 LNode L;
  initList(L);
}
bool initList(LNode & L)
{
  L=NULL;//防止脏数据
  return true;
}
//判断单链表是否为空
bool Empty(LNode* Head )
{
  return Head==NULL;
}


//带头节点（Main函数不变）
bool initList(LNode &L)
{
  L=(LNode*)malloc(sizeof(LNode));//分配一个头节点
  if(L==NULL) //内存不足，分配失败
      return false ;
  L->Next=NULL;  //头节点之后暂时还没有节点
  return true;
}
//判断单链表是否为空(带头节点)
bool Empty(LNode * L)
{
  if(L->==NULL)   //因为头节点不存储数据，Next 才是第一个带数据的节点
      return true;
  else return false;
}

不带头节点和带头节点的区别：不带头结点，写代码更麻烦 。带头结点的写代码更方便

插入和删除

带头结点

//在第i个位置插入元素e
bool ListInsert(LNode & head ,int i ,elementType e )
{
    if(i<1)
        return false ;
    LNode *p;	//指针p指向当前扫描的节点
    int j=0;	//挡墙p指针指向的是第几个节点
    P=L; 		//L指向头节点，头节点是第0个节点（不存储数据）
    while(P!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法
    {
        return false ;
    }
    LNode * s =(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next==p->next;
    p->next=s;
    return true;
}

不带头节点

bool ListInsert(LNode & head ,int i,ElementType e)
{
    if(i<1)
        return false ;
    if(i==1){ //插入第一个节点的操作与其他节点操作不同
        LNode *s =(LNode*) malloc (sizeof(LNode));
        s->data=e;
        s->Next=head;
        L=s;  //头指针指向新节点
        return true;   
    }
    LNode *p;
    int j=1;
    P=head;
    while(p!=NULL&& j<i-1)
    {
        p=p->Next;
        j++;
    }
    if(P==NUll)
        return false;
    LNode *s =(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->Next=p.Next;
    p.Next=s;
    return true;
}

指定节点的后插操作

bool InsertAfterNode(LNode& Node,ElementType e)
{
    if(Node==NULL)
        return false ;
    LNode* s =(LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false ;
    s->data=e;
    s->next=Node->next;
    Node->next =s;
    return true;
}

指定节点的前插操作

//由于单链表无法根据某个节点查找之前的的节点，所有只能传入头节点，从头往后找。时间复杂度O（n）
//其他解决办法：使用的是后插的方法，但是把新节点的数据和前一个节点的数据调换。就能实现逻辑上的前插。
bool InsertPriorNode(LNode *p,ElementType 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->data=p->data;//
    p->data=e;//
    return true;
}

按序删除（带头结点）

删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(LNode* head,int i,ElementType* e)
{
    if(head==NULL||head->Next==NULL)
        return false;
    LNode* p=head;
    int j=0;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(P->next==NULL)//没有的话可能会 free一个NULL节点
        return false;
    LNode* freeP=p->next;
    e=freep->data;
    p->next=freeP->next;
    free(freep);
    return true;
    
}

删除指定的节点

bool DeletNode(LNode *P)
{
    if(p==NULL)
        return ;
    if(p->Next==NULL)
    {
        free(p)
        return true;
    }
    LNode* s=p->next;
    p->data=s->data;
    p->next=s->next;
    free(s);
    return true;   
}

单链表的查找（带头节点）

按位查找 ，获取表L中第i个位置的元素的值

ElementType GetElement(LNode * head,int i )
{
    if(head==NULL)
        return NULL;
    if(i<0)
        return NULL;
    LNode* P=head ;
    int j=0;
    while(p!=NULL &&j<i)
    {
        P=p->next;
        j++;
    }
    if(p==NULL)
       return NULL;
    return p->data;
}

按值查找,在表L中查找具有给定关键字值的元素

LNode* LocateElement(LNode* head ,ElementType e )
{
    if(head==NULL)
        return NULL;
    LNode* P=head ;
    while(p!=NULL)
    {
        p=p->next;
        if(p->data==e )
            return p;
    }
    return NULL;
}

LNode* LocateElement(LNode* head ,ElementType e )
{
    LNode* p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p=>next;
    return p;
}

单链表的建立

如果给N个元素，如何建立一个单链表：

头插法：使用在表头插入的方法，也就是先进的元素在后面，后进的元素在前面

尾插法：每个元素在表尾插入，先插入的元素在前，后插入的元素在后

链表的逆置可以使用头插法

双链表

在单链表的基础上加上一个指向前一个节点的指针prior

双链表的初始化（带头结点）

typedef struct LNode{
    ElementType data;
    struct LNode* prior, * next;
}LNode;
//初始化双链表
bool initLinkList(LNode & head )
{
    head=(LNode*)malloc(sizeof(LNode));
    if(head ==NULL)
        return false;
    head->prior=NULL;
    head->next=NULL;
    return true;
}
void Main()
{
    LNode head;
    initLinkList(head);
}

双链表的插入

bool InsertNextLNode(LNode * p,LNode * s )
{
    s->next= p->next;
    p->next->prior=s;
    if(p->next !=NULL)//p 的后继节点可能是NULL
    s->prior=p;
    p->next=s;
    return true;
}

双链表的删除

bool Delete(LNode * head, int i)
{
    if(head ==NULL)
        return false;
    LNode* p=head ;
    int j=0;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(P->Next==NULL )
        return false;
    LNode* q= p->next;
    p->next=q->next;
    if(p->next!=NULL)
    q->next->prior=p;
    free(q);
}

循环链表

循环单链表

//初始化一个循环单链表
bool initList(LNode& head )
{
    head =(LNode *)malloc(sizeof(LNode));
    if(head ==NULL)
        return flase;
    head ->next=head;
    return true;
}

//判断循环单链表是否为空 

bool Empty(LNode & head )
{
   return head->next==NULL;//如果头结点的next指向的是自己那么就是空
}
//判断节点P 是否为循环单链表的表尾节点
bool isTail(LNode* head ,LNode *p)
{
    return p->next ==head ;
}

顺序表VS链表

都属于线性表，都是线性结构

在存储结构上：

顺序表：

优点：支持随机存取，存储密度高

缺点：大片连续空间分配不方便，改变容量不方便

链表：

优点：离散的小空间分配方便，改变容量方便

缺点：不可随机存储，存储密度低

本栏目推荐文章
• 线性表
• 【机器学习】多元线性回归
• 【算法】【线性表】【链表】删除排序链表中的重复元素 II
• 【算法】【线性表】【链表】删除排序链表中的重复元素
• 用C#使用NumSharp实现简单的线性回归
• 用C#实现简单的线性回归
• 【算法】【线性表】【链表】分隔链表
• 线性代数期末速通
• 非线性状态误差反馈NLSEF
• 【算法】【线性表】【链表】反转链表II

线性非线性 三线性 线性3.1 线性4.3 线性代数 线性mds 线性 算法 transformation线性 线性 办法 线性3.3