数据结构学习第一弹 线性表（2）

线性表的链式存储结构

前言：

采用链式存储结构的线性表称为链表，由n个结点链接而成

特点：

• 对于顺序表的使用，我们一般是根据最大需求来定义，然而这样常常会造成一定的存储空间的浪费，而链式存储结构可以根据需要来进行动态的调整
• 链表中逻辑上相邻的数据元素其物理存储位置不要求紧邻，即链表中结点的逻辑次序和物理次序不一定相同
• 比起顺序存储结构除了要存储其本身的信息外，还要存储一个指向其直接后继元素的存储位置的信息

链表是一种复杂的数据结构，其数据之间的相互关系可以分为三种：单链表，双向链表，循环链表

单链表：

一个线性表的链式存储结构当中每个结点如果只包含一个指针域，则这种线性表为单链表

结点：

每个结点的构成方式如下所示：

• 数据域：存储数据元素信息（该结点的值）的域称为数据域
• 指针域：存放结点的直接后继元素的地址（位置）的指针域（链域）

这两部分信息（即当前元素和指向后继元素的存储位置的指针）组成数据元素称为存储映像，称为结点（Node）

对于整个单链表的构成形式是，每个结点的存储地址是存放在其前驱结点的指针域（next）中的，由于第一个元素结点无前驱元素，所以为了使单链表中的第一个结点与其余各点的基本运算统一，通常在单链表前另加一个表头结点，表头结点的链域指针指向第一个结点。

因为头结点出现是为了规范操作，所以对于一个链表来说，头结点不一定是链表的必须元素。

单链表的描述：

typedef int Elemtype;   //存储的数据类型
typedef struct node     //结点类型定义
{
    Elemtype data;      //数据域
    struct node* next;  //指针域    
}Node;
typedef Node* LinkList;

• Node* 和LinkList是同一类型的指针变量，命名不同是为了便于区分概念
• Linklist类型的指针变量表示它是单链表的头指针
• Node* 类型变量表示它是指向某一结点的指针

单链表的运算：

建立单链表

动态建立单链表的的常用方法一般有两种：头插法，尾插法

• 头插法建单链表

  • 算法思路：
    顾名思义，也就是不断的生成一个新的结点来存储输入的 数据元素，然后把这个新的结点插入到当前链表的表头上， 直到遇到输入结束的标志就停止建表，不过这样生成的表中 结点次序，与输入数据次序相反

  • 代码实现

  LinkList CreatList(int end)
  {
      LinkList head;      //头指针
      Node* p;            //工作指针
      int x;             
      head = NULL;        //头指针初始化为空
      scanf("%d",&x);     //输入数据元素
      while(x!=end)       //读入的元素为end时，建表停止
      {
          p = (Node*)malloc(sizeof(Node*));//生成新的结点
          p->data = x;    //将读入的数据存入新结点的数据域中
          p->next = head; //新结点的链域指向头指针之前指向的结点
          head = p;       //头指针指向新的结点
          scanf("%d",&x);
      }
      return head;        //返回生成的单链表的头指针
  }
  

• 尾插法建立单链表

  • 算法思路：
    同理，只不过是把生成的新结点插入到当前链表的表尾上，所以这样生成的单链表结点次序是和输入的结点次序是一样的

  • 代码实现

  //第一种方法，不采用头结点
  LinkList CreatList(int end)
  {
      int x;
      LinkList head;
      //多用了一个尾指针，始终指向当前链表的尾结点
      Node *s,*r;     
      head = NULL;
      r = NULL;       //初始化为空
      scanf("%d",&x);
      while(x!=end)
      {
          p = (Node*)malloc(sizeof(Node*));
          p->data = x;
          //如果是第一个结点，则让头指针指向他
          if(head!=NULL)  
              head=s;
          else
              r->next = p;//否则则直接将新结点插入到*r的后面
          r=p;            //尾指针指向新表尾
          scanf("%d",&x);
      }
      r->next = NULL;
      return head;
  }
  //第二种方法，采用头结点
  LinkList CreatList(int end)
  {
      int x;
      //生成头结点
      LinkList head = (Node*)malloc(sizeof(Node*));
      Node *p,*r;
      r = head;           //尾指针初始化指向头结点
      scanf("%d",&x);
      while(x!=end)
      {
          p = (Node*)malloc(sizeof(Node*));
          p->data = x;
          r->next = p;
          r = p;
      }
      r->next = NULL;
      return head;
  }
  

单链表的基本操作

</br>

//在建表方式不同的情况下，操作会略有改变
//因为头结点是否存在会影响其代码的实现，不过思路大体相同
//状态码
#define OK 1
#define ERROR 0
typedef int Status;
//初始化单链表
Status InitList(LinkList L)
{
    L->next = NULL;     //头结点指针域置为空
    return OK;
}
//清空单链表
//即把除头结点之外的所有结点空间释放，并把头结点的指针与置为NULL
Status ClearList(LinkList L)
{
    Node *q,*p;             //工作指针
    p = L->next;            //p指向第一个结点
    while(p)                
    {
        q = p;              
        p = p->next;        //p指向下一个结点
        free(q);            //释放q（即上一个结点）的空间
    }
    L->next = NULL;
    return OK;
}
//判断链表是否为空
int ListEmpty(LinkList L)
{
    return (L->next == NULL)//只需要判断头指针是否指向空即可
}
//计算链表长度
int ListLength(LinkList L)
{
    int count = 1;
    Node *p;
    p = L->next;            //从第一个结点开始计数，来计算元素个数
    while(p)
    {
        count++;
        p = p->next;
    }
    return count;           //返回元素个数
}
//GetElem的具体操作
Status GetElem(LinkList L,int i,Elemtype *e)
{
    int j = 1;
    Node *p;
    p = L;
    while(p && j<i)
    {
        p = p->next;
        j++;
    }
    if(!p || j>i)           //找不到此位置，返回错误
        return ERROR;
    *e = p->data;           //通过e来返回第i个位置的元素
    return OK;
}
//LocateElem操作
int LocateElem(LinkList L,Elemtype e)
{
    int i = 1;              //记录该元素的位置
    Node *p;
    p = L;
    while(p && p->data !=e)
    {
        p = p->next;
        i++;
    }
    if(!p)
        return ERROR;       //查找失败
    else return i;          //返回该元素的位置
}
//ListInsert操作
Status ListInsert(LinkList L,int i,Elemtype e)
{
    Node *p,*s;
    int k = 1;
    p = L;                  //指向头指针
    while(k<i && p)         //将指针移向第i个元素的前驱元素
    {
        k++;
        p = p->next;
    }
    if(k>i || !p)           //插入的位置不合理
        return ERROR;
    s = (Node*)malloc(sizeof(Node*));//生成新结点
    if(!s)                  //内存分配失败
        return ERROR;
    s->data = e;            //将e赋给新结点的数据域
    s->next = p->next;      //新结点的指针域指向第i个结点
    p->next = s;            //第i-1个结点指向新结点
    return OK;
}
//ListDelete操作
Status ListDelete(LinkList L,int i,Elemtype *e)
{
    Node *p,*q;
    int k = 1;
    p = L;                  
    while(k<i && p)
    {
        k++;
        p = p->next;
    }
    if(k>i || !p)           //删除的位置不合理
        return ERROR;
    q = p->next;            //q指向第i个结点
    p->next = q->next;      //p指向q的下一个结点
    *e = q->data;           //将删除结点的数据元素保存在e
    free(q);                //释放结点q
    return OK;
}
//销毁链表操作
Status DestroyList(LinkList L)
{
    Node *p;                //用来指向当前要释放的结点
    while(L)
    {
        p = L;              //p指向当前要释放的结点
        L = L->next;        //L指向下一个要释放的结点
        free(p);            //释放结点p
    }
    return OK;
}

顺序表与单链表的对比

• 存储分配方式

+ 顺序表存储结构采用一段连续的存储单元依次存储线性表的元素
+ 单链表则用一组任意的存储单元来存放线性表元素

• 时间性能
  • 查找
    • 顺序表O(1)
    • 单链表O(n)
  • 插入和删除
    • 顺序表O(n)
    • 单链表本身的插入和删除操作是O(1)，但由于要确定插入和删除的位置，所以是O(n)
• 空间性能
  • 顺序表容易造成存储空间的浪费
  • 单链表不需要提前分配好空间，只有需要就给分配，元素个数也不受限制

数据结构学习第一弹线性表（1）