0 Preview

👴写博客就没有日更两篇过，这好像还是头一次。还都是关于数据结构的。
开学要等到十月十号，国庆节以后了，终于有一次生日是在家过的了。
👴的生日本来就很奇妙，十月八日，刚好是七天国庆节假期结束的时候，开学就要检查作业。那段时光太悲催了。

这篇博客主要记录线性表。

1 线性表

1.1 线性表定义

线性表是一个具有相同特性的数据元素的 有限序列 。
线性表具有一下特点：

有限性：数据元素个数是有限的。
一致性：所有元素性质相同，即属于同一数据类型。
序列性：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。
逻辑关系：元素之间为1对1的关系。

线性表中所含元素的个数叫做线性表的长度，用 n 表示，n≥0。
n=0时，表示线性表是一个空表，即表中不包含任何元素。

1.2 线性表的逻辑表达

，，，，，，(a1，a2，…，ai，ai+1，…，an)

🍌ai（1≤i≤n）表示第 i（i表示逻辑位序）个元素。
🍌 a1 是 表头元素 a2 是 表尾元素

1.3 线性表的基本运算

1：初始化线性表InitList(&L)：构造一个空的线性表L。
2：销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。
3：判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。
4：求线性表的长度ListLength(L)：返回L中元素个数n。
5：输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。
6：求线性表L中指定位置的某个数据元素GetElem(L，i，&e)：用e返回L中第i（1≤i≤n）个元素的值。
7：定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。
8：插入一个数据元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）个元素之前插入新的元素e，L的长度增1。
9：删除数据元素ListDelete(&L，i，&e)：删除L的第i（1≤i≤n）个元素，并用e返回其值，L的长度减1。

抽象出来的数据类型：

1
2
3
4
5
6
7
8
9
10
11
C
ADT List
{
  数据对象：
     D={ ai | 1≤i≤n，n≥0，ai为ElemType类型} 
            //ElemType是自定义类型标识符
  数据关系：
     R={<ai，ai+1>| ai、ai+1∈D，i=1，…，n-1}
  基本运算：
     9个运算
}

image-20210908202415432

可以直接使用它来存放数据,作为存放数据的容器。
也可以直接使用它的基本运算,完成更复杂的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C
void unionList(List LA,List LB,List &LC)
{  int lena,i;  ElemType e;
   InitList(LC);				//初始化LC
   for (i=1;i<=ListLength(LA);i++)	//将LA的所有元素复制到LC中
   {  GetElem(LA,i,e);			//取LA中第i个元素赋给e
      ListInsert(LC,i,e);		//将元素e插入到LC中
   }
   lena=ListLength(LA);			//求线性表LA的长度
   for (i=1;i<=ListLength(LB);i++)	//循环处理LB的每一个元素
   {  GetElem(LB,i,e);			//取LB中第i个元素赋给e
      if (!LocateElem(LA,e))		//判断e是否在LA中
        ListInsert(LC,++lena,e);		//若e不在LA中,则将其插入到LC中
   }
}

image-20210908202543196

2 线性表的存储结构

2.1 线性表的顺序存储—顺序表

线性表顺序存储结构：把线性表中的所有元素按照顺序存储方法进行存储。image-20210908203056155

建立顺序表：

引用符号“ & ”放在形参 L 的前面。
输出型参数均为使用“&”，不论参数值是否改变。
引用参数 SqList *&L 将顺序表地址 L 回传给对应的实参

1
2
3
4
5
6
7
8
9
10
11
C
void CreateList(SqList * &L，ElemType a[]，int n)  //传递顺序表指针
　　//整体建立顺序表
{  int i=0,k=0;
   L=(SqList *)malloc(sizeof(SqList));
   while (i<n)		//i扫描a中元素
   {  L->data[k]=a[i];
      k++; i++;	//k记录插入到L中的元素个数
   }
   L->length=k;
 }

📙：采用指针传递的优点：

—更清楚看到顺序表创建和销毁过程（malloc/free）；
​ —在算法的函数之间传递更加节省空间（在函数体内不必创建值形参即整个顺序表的副本）。

2.1.1 插入算法

对于本算法来说，元素移动的次数不仅与表长L->length=n有关，而且与插入位置i有关：
当i=n+1时，移动次数为0；
当i=1时，移动次数为n，达到最大值。

1
2
3
4
5
6
7
8
9
10
11
12
C
bool ListInsert(SqList *&L，int i，ElemType e)
{  int j;
   if (i<1 || i>L->length+1 || L->length==MaxSize)
      return false;		//参数错误时返回false
   i--;				//将顺序表逻辑序号转化为物理序号
   for (j=L->length;j>i;j--)	//将data[i..n]元素后移一个位置
	L->data[j]=L->data[j-1];
   L->data[i]=e;			//插入元素e
   L->length++;			//顺序表长度增1
   return true;			//成功插入返回true
}

image-20210908204828687

2.1.2 删除算法

对于本算法来说，元素移动的次数也与表长n和删除元素的位置i有关：　　
当i=n时，移动次数为0；
当i=1时，移动次数为n-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C
//删除算法最好时间复杂度为O(1)
//删除算法最坏时间复杂度为O(n)

bool ListDelete(SqList *&L，int i，ElemType &e)
{  int j;
   if (i<1 || i>L->length)	　	//参数错误时返回false
      return false;
   i--;					//将顺序表逻辑序号转化为物理序号
   e=L->data[i];
   for (j=i;j<L->length-1;j++)  		//将data[i..n-1]元素前移
	L->data[j]=L->data[j+1];
   L->length--;				//顺序表长度减1
   return true;				//成功删除返回true
}

image-20210908205357918