0 Preview

新时代 ctfer 破防瞬间：

那个告诉我大学就可以放开玩耍就可以找对象的老师快给 👴 爪巴！🙏
这篇笔记将在两天后被我半年内比赛的wp挤出这一页了。

1 线性表的链式存储结构

1.1 链表

📖线性表中每个元素有唯一的前驱元素和后继元素。

不难发现我们要存储这样的结构时候，需要存储元素和元素之间的关系。
设计链式存储结构时，每个逻辑元素用一个结点单独存储，为了表示逻辑关系，增加指针域。
所以也就有了单链表和双链表。

🔑每个物理结点增加一个指向后继结点的指针域 ➡️ 单链表。

🔑每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域 ➡️ 双链表。

1.2 链表的优点

最主要的优点还是引入了指针。

1.2.1 插入或删除操作

顺序表：需要平均移动半个表的元素。
链表：只需修改相关结点的指针域即可，这样既方便又省时。

1.2.2 随机存取特性

查找序号i的元素的时间为O(1)：

顺序表：具有随机存取特性。
链表：不具有随机存取特性。

1.2.3 存储密度

顺序表：存储密度高。
链表：存储密度相对较低。

存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比，即：

🔑存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1（100%），而链表的存储密度小于1。

2 单链表

单链表中结点类型LinkNode的声明如下:

C
typedef struct LNode       //声明单链表结点类型
{  ElemType data;
   struct LNode *next;     //指向后继结点
}  LinkNode;

2.1 头结点

优点：

🔑第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理。
🔑无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。

2.2 单链表的特点

当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。

p是指针，*p是p指向的结点，为了简单，称p指向的结点为p结点

2.3 插入结点和删除结点操作

插入操作：将值为x的新结点s插入到p结点之后。
特点：只需修改相关结点的指针域，不需要移动结点。

删除操作：删除p结点之后的一个结点。
特点：只需修改相关结点的指针域，不需要移动结点。

2.4 建立单链表（整体建立单链表）

这些算法设计都可以总结为一句话，先寻址再操作。

2.4.1 头插法建表

🏏 从一个空表开始，创建一个头结点。
🏏 依次读取字符数组a中的元素，生成新结点
🏏 将新结点插入到当前链表的表头上，直到结束为止。

C
void CreateListF(LinkNode *&L，ElemType a[]，int n)
{  LinkNode *s;
   int i;
   L=(LinkNode *)malloc(sizeof(LinkNode));
   L->next=NULL;		//创建头结点，其next域置为NULL
//第二部分：
   for (i=0;i<n;i++)		//循环建立数据结点
  {  s=(LinkNode *)malloc(sizeof(LinkNode));
     s->data=a[i];		//创建数据结点s
     s->next=L->next;		//将s插在原开始结点之前，头结点之后
     L->next=s;
  }
}

2.4.2 尾插法建表

增加了一个尾指针 r
注意：链表的结点顺序与逻辑次序相同。

🏏 从一个空表开始，创建一个头结点。
🏏 依次读取字符数组a中的元素，生成新结点
🏏 将新结点插入到当前链表的表尾上，直到结束为止。

C
void CreateListR(LinkNode *&L，ElemType a[]，int n)
{  LinkNode *s，*r;
   int i;
   L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
   r=L;			//r始终指向尾结点，开始时指向头结点   
//第二部分：
   for (i=0;i<n;i++)		//循环建立数据结点
   {	s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=a[i];		//创建数据结点s
	r->next=s;		//将s插入r之后
	r=s;
   }
   r->next=NULL;			//尾结点next域置为NULL
}

2.5 其他算法

2.5.1 初始化线性表InitList(&L)

C
void InitList(LinkNode *&L)
{
   L=(LinkNode *)malloc(sizeof(LinkNode));    //创建头结点
   L->next=NULL;
}

2.5.2 销毁线性表DestroyList(&L)

C
void DestroyList(LinkNode *&L)
{   
   LinkNode *pre=L， *p=L->next;    //pre指向p的前驱结点
        while (p!=NULL)	//扫描单链表L
   {  free(pre);		//释放pre结点
      pre=p;		//pre、p同步后移一个结点
      p=pre->next;
   }
   free(pre);     	//循环结束时，p为NULL，pre指向尾结点，释放它
}

2.5.3 判线性表是否为空表ListEmpty(L)

C
bool ListEmpty(LinkNode *L)
{
　　return(L->next==NULL);
}

2.5.4 求线性表的长度ListLength(L)

C
int ListLength(LinkNode *L)
{
  　int n=0;
　  LinkNode *p=L;	//p指向头结点，n置为0（即头结点的序号为0）
         while (p->next!=NULL)
   {	n++;
	p=p->next;
   }
   return(n);	//循环结束，p指向尾结点，其序号n为结点个数
}

2.5.5 输出线性表DispList(L)

C
void DispList(LinkNode *L)
{
   LinkNode *p=L->next;		//p指向开始结点
   while (p!=NULL)		//p不为NULL，输出p结点的data域
   {  printf("%d "，p->data);
      p=p->next;			//p移向下一个结点
   }
   printf("\n");
}

2.5.6 求线性表L中位置i的数据元素GetElem(L，i，&e)

在单链表L中从头开始找到第i个结点，若存在第i个数据结点，则将其data域值赋给变量e。

C
bool GetElem(LinkNode *L，int i，ElemType &e)
{  
   int j=0;
   LinkNode *p=L;	 //p指向头结点，j置为0（即头结点的序号为0）
//从这里开始表示的为第 i 个结点
   while (j<i && p!=NULL)
   {	j++;
	p=p->next;
   }
//回到判断
      if (p==NULL)		//不存在第i个数据结点，返回false
      return false;
   else			//存在第i个数据结点，返回true
   {  e=p->data;
      return true;
   }
}

2.5.7 按元素值查找LocateElem(L，e)

在单链表L中从头开始找第一个值域与e相等的结点，若存在这样的结点，则返回位置，否则返回0。

C
int LocateElem(LinkNode *L，ElemType e)
{
   int i=1;
   LinkNode *p=L->next;		//p指向开始结点，i置为1  

   while (p!=NULL && p->data!=e) 
   {  p=p->next;  		//查找data值为e的结点，其序号为i
      i++;
   }
        if (p==NULL)		//不存在元素值为e的结点，返回0
      return(0);
   else			//存在元素值为e的结点，返回其逻辑序号i
      return(i);
}

2.5.8 删除数据元素ListDelete(&L，i，&e)

C
bool ListDelete(LinkNode *&L，int i，ElemType &e)
{  int j=0;
   LinkNode *p=L，*q;		//p指向头结点，j置为0

   while (j<i-1 && p!=NULL)	//查找第i-1个结点
   {	j++;
	p=p->next;
   }

   if (p==NULL)			//未找到第i-1个结点，返回false
	return false;
   else				//找到第i-1个结点p
   {  q=p->next;			//q指向第i个结点
      if (q==NULL)		//若不存在第i个结点，返回false
	 return false;
      e=q->data;
      p->next=q->next;		//从单链表中删除q结点
      free(q);			//释放q结点
      return true;		//返回true表示成功删除第i个结点
   }
}