【数据结构】课堂复习笔记1+2——线性表

学习的网课是青岛大学-王卓的数据结构与算法基础系列课程，可在bilibili上观看。并配合zjut课堂笔记整理，仅用于学习和复习

绪论

基本概念与术语

1.1.1

  • 数据：是能输入计算机且能被计算机处理的各种符号的集合
    • 信息的载体
    • 是对客观事物符号化的表示
    • 能够被计算机识别、存储和加工
  • 数据元素：是数据的基本单位，在计算机里通常作为一个整体进行考虑和处理。
    • 也称作元素、记录、结点、顶点
  • 数据项：构成数据元素不可分割的最小单位。
  • 数据对象：是性质相同的数据元素集合，是数据的一个子集

1.1.2

  • 数据结构：数据元素相互之间的关系称为结构。指相互之间存在一种或多种特定关系的数据元素集合
    • 数据元素之间的逻辑关系，也称逻辑结构
      • 逻辑结构的种类：（两种划分方式）
        • 线性结构和非线性结构
        • 集合结构、线性结构、树形结构、图状结构
    • 数据元素及其关系在计算机内存中的表示（映像），称物理结构或存储结构
      • 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由存储位置表示
      • 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
      • 索引存储结构：存储结点信息+索引表
      • 散列存储结构：根据结点关键字直接计算出该结点的存储地址
    • 数据的运算和实现
  • 数据类型：是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称
  • 抽象数据类型：是指一个数学模型以及定义在此数学模型上的一组操作。数据模型+抽象运算

算法与算法分析

  • 算法：对特定问题求解方法和步骤的一种描述，它是指令的有限序列

  • 程序=数据结构+算法

  • 算法特性：有穷性、确定性、可行性、输入、输出

  • 算法效率：时间效率+空间效率

    • 算法时间的度量：程序在计算机执行所消耗的时间
    • 时间=每条语句执行次数（语句频度）*该语句执行一次的时间
    • 时间复杂度O(f(n))：n趋于无穷大时，T(n)/f(n)为一个不为零的常数

  • 复杂度计算

    • 语句频度表达成T（n）
    • 有时与数据集有关：最坏/平均/最好时间复杂度
    • 分成两个容易估算部分，利用O的乘法和和加法法则计算时间复杂度

  • 算法时间效率比较：n取很大时，不同算法时间会非常悬殊

  • 渐进空间复杂度：算法存储所需空间的度量

二、线性表

2.1 线性表的定义和特点

  • 线性表：是具有相同特性的数据元素的一个有限序列
    • 起始结点、直接前趋、直接后继、终端结点
    • 数据元素的个数n定义为表的长度，n=0时为空表
    • 逻辑特征
      • 有且仅有一个开始/终端结点，没有直接前趋/后继，有且仅有一个直接后继/前趋
      • 内部结点，有且仅有一个直接前趋和直接后继

2.2 线性表的顺序存储表示

  • 顺序存储：把逻辑上相邻的数据元素存储在物理相邻的存储单元中的存储结构
    • 占用一片连续的存储空间
# define LIST_INIT_SIZE 100
typedef struct{
  ElemType elem[LIST_INIT_SIZE];
  int length;
}SqList;

(这里后续插一个例子)

线性表的初始化

Status InitList Sq(SqList &L){
  L.elem=new ElemType[MAXSIZE];
  if(!L.elem) exit(OVERFLOW);
  L.length=0;
  return OK;
}

线性表的销毁

void DestroyList(SqList &L){
  if(L.elem) delete L.elem;
}

线性表的清空

void ClearList(SqList &L){
  L.length=0;
}

线性表返回长度

int GetLength(SqList L){
  return (L.length);
}

线性表判断为空

int IsEmpty(SqList L){
  if(L.length==0) return 1;
  else return 0;
}
  • 平均查找长度ASL：（这里有一个公式）

2.3 线性表的链式存储表示

2.3.1 链式存储结构

  • 链式存储：用一组物理位置任意的存储单元来存放数据元素，逻辑次序和物理次序不一定相同
  • 相关术语：
    • 结点：数据元素的存储映像。由数据域和指针域两部分组成
    • 链表：n个结点由指针域组成一个链表
    • 单链表、双链表、循环链表
      • 只有一个指针域
      • 有两个指针域
      • 首尾相接的链表
    • 头指针、首元结点、头结点
      • 指向链表第一个结点的指针
      • 存储第一个数据元素a1的结点
      • 首元结点前附设的结点
    • 顺序表是随机存取，链表是顺序存取
  • 单链表：

2.3.2 单链表的基本操作

单链表的存储结构：

typedef struct Lnode
{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;

定义链表L：Linklist L;

定义结点结点指针p：LNode *p=Linklist p;

单链表的初始化：1.生成新结点作头结点，L指向 2.头指针指针域置空

Status InitList_L(LinkList &L){ 
  L=new LNode;                    	
  L->next=NULL;　　　　　
  return OK; 
}

单链表的销毁：从头指针开始，依次释放所有结点

Status DestroyList_L(LinkList &L)
{
  LinkList p;
    while(L)
    {
      p=L;  
      L=L->next;
      delete p;  
    }
  return OK;
}

单链表的清空：头结点头指针仍然存在

Status ClearList(LinkList & L){
  // 将L重置为空表 
   LinkList p,q;
   p=L->next;   //p指向第一个结点
   while(p)       //没到表尾 
      {  q=p->next; delete p;     p=q;   }
   L->next=NULL;   //头结点指针域为空 
   return OK;
 }

求单链表的表长：

int  ListLength_L(LinkList L){
//返回L中数据元素个数
    LinkList p;
    p=L->next;  //p指向第一个结点
     i=0;             
     while(p){//遍历单链表,统计结点数
           i++;
           p=p->next;    } 
    return i;                             
 }

2.3.3 单链表的重要操作

取值：逐个扫描计数

Status GetElem_L(LinkList L, int i, ElemType &e){ 
  p=L->next;j=1; //初始化
    while(p&&j<i){	 
      p=p->next; ++j; //向后扫描，直到p指向第i个元素或p为空
    } 
    if(!p || j>i)return ERROR; //第i个元素不存在 
    e=p->data; //取第i个元素 
    return OK; 
}//GetElem_L

查找：依次比较

//在线性表L中查找值为e的数据元素
LNode *LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的地址，查找失败返回NULL
  p=L->next;
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	
} //查找值
int LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的位置序号，查找失败返回0 
  p=L->next; j=1;
  while(p &&p->data!=e)  
        {p=p->next;  j++;}          		
  if(p) return j; 
  else return 0;
} //查找位置

插入：找到位置，生成新结点，置值指针指向，指向新结点

Status ListInsert_L(LinkList &L,int i,ElemType e){ 
  p=L;j=0; 
  while(p&&j<i−1){p=p->next;++j;}	//寻找第i−1个结点 
  if(!p||j>i−1)return ERROR;	//i大于表长 + 1或者小于1  
  s=new LNode;			//生成新结点s 
  s->data=e;      		           //将结点s的数据域置为e 
  s->next=p->next;	   	          //将结点s插入L中 
  p->next=s; 
  return OK; 
}//ListInsert_L

删除：找到位置，保存删除值，指向后继结点，释放值

Status ListDelete_L(LinkList &L,int i,ElemType &e){
  p=L;j=0; 
  while(p->next &&j<i-1){                 
      p=p->next; ++j; //寻找第i个结点，并令p指向其前驱 
  } 
  if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 
  q=p->next;                                        //临时保存被删结点的地址以备释放 
  p->next=q->next; 	                  //改变删除结点前驱结点的指针域 
  e=q->data; 	                                //保存删除结点的数据域 
  delete q; 	                                //释放删除结点的空间 
 return OK; 
}//ListDelete_L

2.3.4 链表运算的时间效率分析

  • 查找：因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。
  • 插入和删除：因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
    • 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。

2.3.5 单链表的建立

  • 前插法：生成新结点，读入数据，插入链表前端
void CreateList_F(LinkList &L,int n){ 
     L=new LNode; 
      L->next=NULL; //先建立一个带头结点的单链表 
      for(i=n;i>0;--i){ 
        p=new LNode; //生成新结点 
        cin>>p->data; //输入元素值 
        p->next=L->next;L->next=p; 	//插入到表头 
     } 
}//CreateList_F
  • 尾插法：新结点逐个插入尾部，尾指针指向链表尾结点
void CreateList_L(LinkList &L,int n){ 
  //正位序输入n个元素的值，建立带表头结点的单链表L 
  L=new LNode; 
  L->next=NULL; 	
  r=L; 	                                //尾指针r指向头结点 
  for(i=0;i<n;++i){ 
    p=new LNode;    
    cin>>p->data;   		       //输入元素值 
    p->next=NULL; r->next=p;       //插入到表尾 
    r=p; 	                                  //r指向新的尾结点 
  } 
}//CreateList_L

2.3.6 循环链表

表的操作往往在首尾指针位置上进行

  • 尾指针：
    • 开始结点：rear->next->next
    • 终端结点：rear
    • 首尾结点复杂度都为O(1)。

带尾指针循环链表的合并：p存表头结点，b表头连接到a尾，释放b头结点，修改指针，时间复杂度：O(1)

LinkList Connect(LinkList Ta,LinkList Tb)
{
  p=Ta->next;
  Ta->next=Tb->next->next;
  delete Tb->next;
  Tb->next=p;
  return Tb;
}

2.3.7 双向链表

双向链表：增加指向前驱结点的指针 结构定义：

typedef struct DuLNode{
  ElemType   data;              
  struct DuLNode  *prior;  
  struct DuLNode  *next;  
}DuLNode, *DuLinkList

双向链表的插入：

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
  if(!(p=GetElemP_DuL(L,i))) return ERROR;
  s=new DuLNode; 
  s->data=e;
  s->prior=p->prior;  
  p->prior->next=s;
  s->next=p;  
  p->prior=s;
  return OK;
}

双向链表的删除：

Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e)
{
  if(!(p=GetElemP_DuL(L,i)))     return ERROR;
  e=p->data;
  p->prior->next=p->next;
  p->next->prior=p->prior;
  delete p; 
  return OK;
}

2.4 顺序表和链表比较

模型