数据结构与算法基础（青岛大学-王卓）(2)

第二弹火爆来袭中

这波是单链表的内容整理，废话不多说，上小龙虾呀(又到了龙虾季节了，哎，口水直流了~~)

---

beautiful的分割线

---

…

线性表的链式表示

定义

用一组物理位置任意的存储单元来存放线性表的数据元素，存储单元对连续性没要求，可零散分布，链表的每个节点由 数据+指针 组成

eg: 26个英文字母小写存储

链表种类

单链表，双链表，循环链表

链表的表示

• 头指针：是指向链表中第一个结点的指针

• 首元结点：是指链表中存储第一个数据元素a1的结点

• 头结点：是在链表的首元结点之前附设的一个结点；

  • 链表存储的时候可以选择带和不带头节点

  • 好处：

    • 便于首元结点的处理(链表的第一个数据也能有往前的指针，处理起来和后面的正常元素就一样了)
    • 便于空表和非空表的统一处理，如下(第二种方案)

    

  • 头结点的数据域可以为空，也可以放线性表长度等附加信息，但此节点不能计入链表长度值。

链表的特点

• 存储上位置任意，不需要相邻
• 访问元素时只能通过头指针进入链表，并扫描剩下每个节点直到找到目标，找到第一个节点和最后一个节点的时间不等
  • 顺序表–> 随机存取
  • 链表–> 顺序存取(找第i个元素时必须从第一个元素一直到i-1个元素再到元素i)

单链表

表示方法

单链表由表头唯一确定，可以用头指针的名字来命名，头指针为L则把链表称为表L.

存储结构

typedef struct Lnode{ //声明结点的类型和指向结点的指针类型ElemType data; //结点的数据域struct Lnode *next; //结点的指针域(嵌套了)
}Lnode,*LinkList; //LinkList为指向结构体Lnode的指针类型LinkList L; //定义链表L
Lnode *p; //定义节点指针p (可以用linkList p 但是不推荐)

例子：存储学生的学号，姓名，成绩的单链表

// 通常定义法
typedef Struct {char num[8]; //数据域char name[8]; //数据域int score; //数据域
} ElemType;typedef struct Lnode{ElemType data; //数据域struct Lnode *next; //指针域
}Lnode, *LinkList

Linklist L;

单链表的初始化

Status InitList_L(LinkList &L){L=new LNode; // C++ or C语言 L=(LinkList) malloc (sizeof (LNode))L->next=NULL;return OK;
}

判断链表是否为空

int ListEmpty(LinkList L){ //空表返回1，否则返回0if(L->next) //非空return 0;elsereturn 1;
}

单链表的销毁(头结点也不存在了)

Status DestroyList_L(LinkList &L){Lnode *p;while(L){p=L;L=L->next;delete p; // C++ 用法 or C用法： free p;}return OK;
}

清空单链表(头指针和头结点还在)

依次从首元结点开始释放所有节点，最后将头结点的指针域设为空

Status EmptyList_L(LinkList &L){Lnode *p,*q;p=L->next;while (p){q=p->next;delete p;p=q;}L->next=NULL;return OK;
}

求单链表的表长

int List_Length(LinkList L){Lnode *p;p=L->next; //p指向第一个节点（首元结点）i=0;while (p){  //遍历单链表，统计节点数i++;p=p->next}return OK;
}

取单链表中第i个元素的内容

思路：从头指针触发，顺着链域next逐个往下搜索，直到搜索到第i个节点为止，因此链表不是随机存取结构，需判断找不到的情况和i的正确取值情况。

Status GetElem_L(LinkList L, int i, ElemType &e){p=L->next;j=1; //初始化，p指向首元结点，j来累计遍历过的位置while (!p && j<i){ //向后扫描直到p指向第i个元素或者p为空时p=p->next;++j; //注意这里是前加加，返回的是自增后的j, j++ 后加加是返回自增前的j}if (!p || j > i) return ERROR; //p指向空节点或者i各元素不存在时，返回ERRORe=p->data;return OK;
}//GetElem_L

单链表中的按值查找

• 返回该数据所在位置(改数据地址)

  Lnode *LocateElem_L(LinkList L, ElemType e){
  //在单链表中查找元素为e的数据元素，找到后返回e的地址，未找到返回NULLp=L->next;while (p && p->data!=e){p=p->next;}return p;
  }
  

• 返回该数据所在的位置序号(第几个元素)

  int LocateElem_L(LinkList L, ElemType e){
  // 使用计数器i返回查找到的位置p=L->next;j=1;while (p && p->data!=e){p=p->next;j++;}if (p) return j; //p非空情况下的i才有意义else return 0;
  }
  

单链表的插入操作

在第i个节点前插入值为e的新节点 - 找前趋

//单链表的插入操作，在第i个位置插入元素数据域为e的元素
Status ListInset_L(LinkList &L, int i, ElemType e){p=L;j=0 //初始化p指向头结点，计数器为0while (p && j<i-1) {p=p->next; ++j;} //寻找i-1节点if (!p || j>i-1) return ERROR; //当p为空时，p已经指向了表长+1的节点位置，此时插入位置变为表长+2，这种情况不允许，所以这里排除掉了插入位置大于表长+1位置和i小于1的不合理情况。s=new Lnode;s->data=e; // 创建即将插入的新节点ss->next=p->next; // s指向原来的i节点p->next=s; //i-1节点指向新节点sreturn OK;
}//ListInset_L

单链表的删除操作

删除第i各元素 - 找前趋

Status List_Delete_L(LinkList &L, int i, ElemType &e){p=L;j=0; Lnode *q; //初始化，p指向头结点，计数器清零while(p->next && j<i-1) {p=p->next; ++j;} //寻找i-1元素，注意此处判定改为了p->next, 当p->next为NULL时，说明i-1个元素已经是表的最后一个元素,那么要删除的i元素就是表长+1的元素，而它是不存在的if(!p->next || j>i-1) return ERROR; // 排除不合理的i元素q=p->next; e=q->data; //将待删除元素信息做保留p->next=q->next; // i-1元素指向i+1元素delete q; //删除指针return OK;
}//ListDelete_L

单链表的查找、插入、删除时间效率

• 查找 - 时间效率为O(n)

• 插入/删除：

  • 单个操作并不会移动元素，只是动指针，时间效率为O(1)

  • 查找并操作时，时间效率为O(n)

单链表的建立

• 头插法 - 元素倒序依次插入链表头结点后面

  • 从一个空表开始，重复读入数据

  • 生成新节点，将读入数据放入新节点的数据域中

  • 从最后一个节点开始，依次将各节点插入到链表的前端

  • 算法时间复杂度O(n)

    

    

   //头插法创建单链表Void CreateList_H(LinkList &L, int n){L=new Lnode; L->next=NULL; //建立一个带头结点的单链表for (i=n;i>0;--i){ //循环倒序插入所有元素p=new Lnode; //生成(C)新节点p=(Lnode*)malloc(sizeof(Lnode));cin>>p->data; //输入(C)元素值scanf(&p->data)p->next=L->next;L->next=p;}}//CreateList_H
  

• 尾插法 - 新元素正序依次插入末尾

  • 从一个空链表L开始，新节点依次插入链表尾部，尾指针r指向链表尾结点

  • 初始时，r/L都指向头结点。每读取一个数据元素则申请一个新节点并插入尾结点后，r指向新的尾结点。

  • 算法时间复杂度O(n)

    

   //尾插法创建单链表Void CreateList_R(LinkList &L, int n){L=new Lnode; L->next=NULL; //创建空单链表r=L; // 尾指针初始化等于头结点for (i=0;i<n;++i){ //依次正序添加节点p=new Lnode; cin>>p->data;p->next=NULL; //新节点的指针域置空作为新的尾结点 r->next=p; //新节点链接前一个节点r=p; //尾指针移动到新尾结点}}//CreateList_R
  

…

TO BE CONTINUED…