数据结构入门-线性表

数据结构
数据结构
发布日期:   2022-09-06
更新日期:   2022-09-10
文章字数:   9.3k
阅读时长:   36 分
阅读次数:  

线性表

顺序表

  • 静态分配

    顺序表最简单的方法是使用一个定长数组data[]存储数据，最大空间为 Maxsize，用 length记录实际的元素个数，即顺序表的长度。

  • 动态分配

    在程序运行过程中，根据需要动态分配一段连续的空间（大小为 Maxsize），用 elem 记录该空间的基地址（首地址），用 length 记录实际的元素个数，即顺序表的长度。

    采用动态存储方法，在运算过程中，如果发生溢出，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的。

初始化：

分配Maxsize空间，注意判断分配失败的情况：

#include<iostream>
using namespace std;

#define  Maxsize 100  //最大空间

typedef struct{
	int *elem;
	int length; // 顺序表的长度
}SqList;

bool InitList(SqList &L) //构造一个空的顺序表L
{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效
//不加&内部改变，跳出函数后无效
    L.elem=new int[Maxsize];    //为顺序表分配Maxsize个空间
    if(!L.elem) return false;      //存储分配失败
    L.length=0;				//空表长度为0
    return true;
}

创建：

  1. 注意判断顺序表是否已满。
  2. 将数据 x 存入顺序表的第 i 个位置，即 L.elem[i]=x，然后 i++。
  3. 注意顺序表长度增加1。
bool CreateList(SqList &L) //创建一个顺序表L
{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效
//不加&内部改变，跳出函数后无效
    int a,i=0;
    cin>>a;
    while(a!=-1)
    {
	    if(L.length==Maxsize)
	    {
		    cout<<"顺序表已满！";
		    return false;
	    }
	    L.elem[i++]=a;
	    L.length++;
	    cin>>a;
	}
   return true;
}

取值：

顺序表中的任何一个元素都可以立即被找到，称为随机存取方式。

由于下标是从 0 开始的，因此第 i 个元素，其下标为 i−1，即对应元素为 L.elem[i−1]

注意：位序是指第几个元素，位序和下标差1。

注意判断i值的合理性。

image-20220906155828274

bool GetElem(SqList L,int i,int &e)
{
	if(i<1||i>L.length) return false;
	   //判断i值是否合理，若不合理，返回false
	e=L.elem[i-1];   //第i-1的单元存储着第i个数据
	return true;
}

查找：

在顺序表中查找一个元素 e，可以从第一个元素开始顺序查找，依次比较每一个元素值。如果相等，则返回元素位置（位序，即第几个元素）；如果查找整个顺序表都没找到，则返回−1。

int LocateELem(SqList L,int x)
{
	for(int i=0;i<L.length;i++)
	      if(L.elem[i]==x)
		  	return i+1; //第几个元素，例如第5个元素，下标其实为4
	return -1;
}
算法复杂度分析：

  • 最好情况：如果元素正好在第一个位置，比较一次查找成功，时间复杂度为 O(1)。

  • 最坏情况：如果元素正好在最后一个位置，比较 n 次查找成功，时间复杂度为 O(n)。

  • 平均情况：如果查找的元素在第一个位置需要比较 1 次，第二个位置需要比较 2次…最后一个位置需要比较 n 次。如果该元素在第 i 个位置，则需要比较 i 次，把每种情况比较次数乘以其查找概率 pi 并求和，即为平均时间复杂度。如果查找概率均等，即每个关键字的查找概率均为 1/n，则平均时间复杂度为：

    image-20220906160600617

    因此，假设每个关键字查找的概率均等，顺序表查找算法的平均时间复杂度为 O(n)。

插入：

在顺序表中第 i 个位置之前插入一个元素 e，需要从最后一个元素开始，后移一位，直到把第 i 个元素也后移一位，然后把 e 放入第 i 个位置。

  1. 注意判断位置i是否合法（1≤i≤L.length+1）。
  2. 注意判断顺序表的存储空间是否已满。
  3. 将第 L.length 至第 i 个元素依次向后移动一个位置，空出第 i 个位置并放入新元素。
  4. 注意表长加一。
  5. 时刻注意位序和下标的关系！
bool ListInsert_Sq(SqList &L,int i ,int e)
{
	if(i<1||i>L.length+1) return false;	 //i值不合法
	if(L.length==Maxsize) return false; //存储空间已满
	for(int j=L.length-1;j>=i-1;j--)
	       L.elem[j+1]=L.elem[j];   //从最后一个元素开始后移，直到第i个元素后移
	L.elem[i-1]=e;              //将新元素e放入第i个位置
	L.length++;		     	//表长增1
	return true;
}
算法复杂度分析：

可以在第 1 个位置之前插入，也可以在第 2 个位置之前…第 n 个位置之前，第 n+1 个位置之前插入，一共有 n+1 种情况，每种情况移动元素的个数是 n−i+1。把每种情况移动次数乘以其插入概率 p i 并求和，即为平均时间复杂度。如果插入概率均等，即每个位置的插入概率均为 1/(n+1)，则平均时间复杂度为：

image-20220906161747867

因此，假设每个位置插入的概率均等，顺序表插入算法平均时间复杂度为 O(n)。

删除：

在顺序表中删除第 i 个元素，需要把该元素暂存到变量 e 中，然后从 i+1 个元素开始前移.…直到把第 n 个元素也前移一位，即可完成删除操作。

  1. 注意判断位置i是否合法（1≤i≤L.length+1）。
  2. 将欲删除的元素保存在 e 中。
  3. 将第 i+1 至第 n 个元素依次向前移动一个位置。
  4. 注意表长减1。
  5. 时刻注意位序和下标的关系！
bool ListDelete_Sq(SqList &L,int i,int &e)
{
   if((i<1)||(i>L.length)) return false;	 //i值不合法
   e=L.elem[i-1];   //将欲删除的元素保留在e中
   for (int j=i;j<=L.length-1;j++)
		L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
   L.length--; //表长减1
   return true;
}
算法复杂度分析：

顺序表元素删除一共有 n 种情况，每种情况移动元素的个数是 n−i。把每种情况移动次数乘以其删除概率 p i 并求和，即为平均时间复杂度。假设删除每个元素的概率均等，即每个元素的删除概率均为 1/n，则平均时间复杂度为：

image-20220906162308243

因此，假设每个元素删除的概率均等，顺序表删除算法平均时间复杂度为 O(n)。

顺序表的优点和缺点：

优点：

操作简单，存储密度高，可以随机存取，只需要 O(1)的时间就可以取出第 i 个元素。

缺点：

需要预先分配最大空间，最大空间数估计过大或过小会造成空间浪费或溢出。插入和删除操作需要移动大量元素。

单链表

可以给每个元素附加一个指针域，指向下一个元素的存储位置，如图所示：

image-20220906165619151

每个节点包含两个域：数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。每个指针都指向下一个
节点，都是朝一个方向的，这样的链表称为单向链表或单链表。

只要给这个单链表设置一个头指针，这个链表中的每个节点就都可以找到了。有时为了操作方便，还会给链表增加一个不存放数据的头节点（也可以存放表长等信
息）。

初始化：

  1. 创建头节点，令其指针域为空。
  2. 注意判断生成节点失败的情况。
#include<iostream>
using namespace std;

typedef struct LNode{
	int data; //结点的数据域
	struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

bool InitList_L(LinkList &L)//构造一个空的单链表L
{
    L=new LNode;     //生成新结点作为头结点，用头指针L指向头结点
	if(!L)
      return false;  //生成结点失败
	L->next=NULL;   //头结点的指针域置空
	return true;
}

创建：

头插法：

头插法是指每次把新节点插到头节点之后，其创建的单链表和数据输入顺序正好相反，因此也称为逆序建表。

  1. 初始化链表后，创建新节点，把元素1放入新节点数据域：

    image-20220906170511493

  2. 头插操作，插入 头节点的后面：

    image-20220906170546723

  3. 同理插入元素2，插入头节点的后面：

    image-20220906170601300

    赋值语句的两端：等号的右侧是节点的地址，等号的左侧是节点的指针域。

    1. s->next=L->next：L->next 存储的是下一个节点地址“9630”，将该地址赋值给 s->next指针域，即 s 节点的 next 指针指向 1 节点。
    2. L->next=s：将 s 节点的地址“2046”赋值给 L->next 指针域，即 L 节点的 next 指针指向 s 节点。

    为什么要先修改后面那个指针呢？

    因为一旦修改了 L 节点的指针域指向 s，那么原来 L 节点后面的节点就找不到了，因此修改指针是有顺序的。

    修改指针的顺序原则：先修改没有指针标记的那一端

    image-20220906171402128

    如果要插入节点的两端都有标记，例如，再定义一个指针 q 指向 L 节点后面的节点，那么先修改哪个指针都无所谓了：

    image-20220906171436712

void CreateList_H(LinkList &L)//前插法创建单链表
{
	//输入n个元素的值，建立到头结点的单链表L
	int n;
	LinkList s; //定义一个指针变量
	L=new LNode;
	L->next=NULL; //先建立一个带头结点的空链表
	cout<<"请输入元素个数n："<<endl;
	cin>>n;
	cout<<"请依次输入n个元素："<<endl;
	cout<<"前插法创建单链表..."<<endl;
	while(n--)
    {
		s=new LNode; //生成新结点s
		cin>>s->data; //输入元素值赋给新结点的数据域
		s->next=L->next;
		L->next=s; //将新结点s插入到头结点之后
	}
}
尾插法：

尾插法每次把新节点链接到链表的尾部，其创建的单链表和数据输入顺序一致。

  1. 初始化链表后，创建新节点，把元素1放入新节点数据域并插入到尾结点的后面：

    image-20220906201103508

    1. s->next=NULL：s 节点的指针域置空。
    2. r->next=s：将 s 节点的地址赋值给 r 节点的指针域，即将新节点 s 插入尾节点 r 之后。
    3. r=s：将 s 节点的地址赋值给 r，即 r 指向新的尾节点 s。

  2. 输入数据元素 2，创建新节点，把元素 2 放入新节点数据域，插入到尾节点的后面：

    image-20220906201742129

void CreateList_R(LinkList &L)//尾插法创建单链表
{
	//输入n个元素的值，建立带表头结点的单链表L
	int n;
	LinkList s, r;
	L=new LNode;
	L->next=NULL; //先建立一个带头结点的空链表
	r=L; //尾指针r指向头结点
	cout<<"请输入元素个数n："<<endl;
	cin>>n;
	cout<<"请依次输入n个元素："<<endl;
	cout<<"尾插法创建单链表..."<<endl;
	while(n--)
    {
		s=new LNode;//生成新结点
		cin>>s->data; //输入元素值赋给新结点的数据域
		s->next=NULL;
		r->next=s;//将新结点s插入尾结点*r之后
		r=s;//r指向新的尾结点s
	}
}

取值：

单链表的取值不像顺序表那样可以随机访问任何一个元素，单链表只有头指针，各个节点的物理地址是不连续的。

要想找到第 i 个节点，就必须从第一个节点开始按顺序向后找，一直找到第 i 个节点。

注意：**链表的头指针不可随意改动！**一个链表是由头指针来标识的，一旦头指针改动或丢失，这个链表就不完整或找不到了。如果需要用指针移动，可定义一个指针变量进行移动。

  1. 先定义一个 p 指针，指向第一个元素节点，用 j 作为计数器，j=1。

    image-20220906203132220

  2. 如果 p 不为空且 j<i，则 p 指向 p 的下一个节点，然后 j 加 1，即：p=p->next; j++。

    image-20220906203150910

  3. 直到 p 为空或者 j=i 停止。p 为空，说明没有数到 i，链表就结束了，即不存在第 i个节点；j=i，说明找到了第 i 个节点。

    image-20220906203203024

  4. 如果i值不合法，也需要进行判断。

  5. 注意每一步的条件因素。

bool GetElem_L(LinkList L,int i,int &e)//单链表的取值
{
	//在带头结点的单链表L中查找第i个元素
	//用e记录L中第i个数据元素的值
	int j;
	LinkList p;
	p=L->next;//p指向第一个结点，
	j=1; //j为计数器
	while(j<i&&p) //顺链域向后扫描，直到p指向第i个元素或p为空
    {
		p=p->next; //p指向下一个结点
		j++; //计数器j相应加1
	}
	if(!p||j>i)
		return false; //i值不合法i＞n或i<=0
	e=p->data; //取第i个结点的数据域
	return true;
}

查找：

在一个单链表中查找是否存在元素 e，可以定义一个 p 指针，指向第一个元素节点，比较 p 指向节点的数据域是否等于 e。

bool LocateElem_L(LinkList L, int e) //按值查找
{
	//在带头结点的单链表L中查找值为e的元素
	LinkList p;
	p=L->next;
	while(p&&p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
		p=p->next; //p指向下一个结点
	if(!p)
        return false; //查找失败p为NULL
    return true;
}

插入：

如果要在第 i 个节点之前插入一个元素，则必须先找到第 i−1 个节点。

单链表只有一个指针域，是向后操作的，不可以向前操作。如果直接找到第 i 个节点，就无法向前操作，把新节点插入第 i 个节点之前。

实际上，在第 i 个节点之前插入一个元素相当于在第 i−1 个节点之后插入一个元素，因此先找到第 i−1 个节点，然后将新节点插在其后面即可。

  1. 定义一个 p 指针，指向头节点，用 j 作为计数器，j=0。

  2. 如果 p 不为空且 j<i−1，则 p 指向 p 的下一个节点，然后 j 加 1，即：p=p->next; j++。

  3. 直到 p 为空或 j >=i−1 停止。

  4. p 为空，说明没有数到 i−1，链表就结束了，即 i＞n+1，i 值不合法；j >i−1 说明 i＜1，此时 i 值不合法，返回 false。如果 j=i−1，说明找到了第 i−1 个节点。

  5. 将新节点插到第 i−1 个节点之后。

    image-20220906204151314

    1. s->next=p->next：将 p 节点后面的节点地址赋值给 s 节点的指针域，即 s 节点的 next 指针指向 p 后面的节点。
    2. p->next=s：将 s 节点的地址赋值给 p 节点的指针域，即 p 节点的 next 指针指向 s 节点。

    前面讲的前插法建链表，就是每次将新节点插到头节点之后，现在是将新节点插到第 i−1 个节点之后。

bool ListInsert_L(LinkList &L,int i,int &e)//单链表的插入
{
	//在带头结点的单链表L中第i个位置插入值为e的新结点
	int j;
	LinkList p,s;
	p=L;
	j=0;
	while(p&&j<i-1) //查找第i-1个结点，p指向该结点
    {
		p=p->next;
		j++;
	}
	if(!p||j>i-1)//i＞n+1或者i＜1
		return false;
	s=new LNode;     //生成新结点
	s->data=e;       //将新结点的数据域置为e
	s->next=p->next; //将新结点的指针域指向结点ai
	p->next=s;       //将结点p的指针域指向结点s
	return true;
}

删除：

删除一个节点，实际上是把这个节点跳过去。根据单向链表向后操作的特性，要想跳过第 i 个节点，就必须先找到第 i−1 个节点，否则是无法跳过去的。

image-20220906204522573

  • 注意保存被删节点。
  • 注意释放空间。
bool ListDelete_L(LinkList &L,int i) //单链表的删除
{
	//在带头结点的单链表L中，删除第i个位置
	LinkList p, q;
	int j;
	p=L;
	j=0;
	while((p->next)&&(j<i-1)) //查找第i?1个结点，p指向该结点
	{
		p=p->next;
		j++;
	}
	if(!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
		return false;
	q=p->next;        //临时保存被删结点的地址以备释放空间
	p->next=q->next; //改变删除结点前驱结点的指针域
	delete q;        //释放被删除结点的空间
	return true;
}

双向链表：

单链表只能向后操作，不可以向前操作。为了向前、向后操作方便，可以给每个元素附加两个指针域，一个存储前一个元素的地址，另一个存储下一个元素的地址。

image-20220909215632955

初始化：

  1. 创建头节点，不存储数据。
  2. 令头节点前后两个指针域均为空。
#include<iostream>
using namespace std;

typedef struct DuLNode{
	int data; //结点的数据域
	struct DuLNode *prior,*next; //结点的指针域
}DuLNode,*DuLinkList; //LinkList为指向结构体LNode的指针类型

bool InitDuList_L(DuLinkList &L)//构造一个空的双向链表L
{
    L=new DuLNode;     //生成新结点作为头结点，用头指针L指向头结点
	if(!L)
      return false;     //生成结点失败
	L->prior=L->next=NULL;   //头结点的两个指针域置空
	return true;
}

创建：

头插法：

  1. 将新节点插入到头节点的后面：

    image-20220909220959282

  2. 创建新节点并继续插入到头节点的后面：

    image-20220909221129893

    1. s->next=L->next：将 L 节点后面的节点（后继）地址赋值给 s 节点的指针域，即 s 节点的 next 指针指向 L 的后继节点。

    2. L->next->prior=s：将 s 节点的地址赋值给 L 的后继节点的 prior 指针域，即 L 的后继节点的 prior 指针指向 s 节点。
      注意这一步要先判断L-next是否为null。

    3. s->prior=L：将 L 节点的地址赋值给 s 节点的 prior 指针域，即 s 节点的 prior 指针指向 L 节点。

    4. L->next=s：将 s 节点的地址赋值给 L 节点的指针域，即 L 节点的 next 指针指向 s 节点。

      实际上，只需要将④语句放在最后修改即可，①②③语句顺序无要求。

void CreateDuList_H(DuLinkList &L)//前插法创建双向链表
{
	//输入n个元素的值，建立到头结点的单链表L
	int n;
	DuLinkList s; //定义一个指针变量
	L=new DuLNode;
	L->prior=L->next=NULL; //先建立一个带头结点的空链表
	cout<<"请输入元素个数n："<<endl;
	cin>>n;
	cout<<"请依次输入n个元素："<<endl;
	cout<<"前插法创建单链表..."<<endl;
	while(n--)
    {
		s=new DuLNode; //生成新结点s
		cin>>s->data; //输入元素值赋给新结点的数据域
		if(L->next)
            L->next->prior=s;
        s->next=L->next;
        s->prior=L;
        L->next=s; //将新结点s插入到头结点之后
	}
}
尾插法：

尾插法建双向链表和尾插法建单链表类似，需要有一个尾指针，不再赘述。

取值：

双向链表的取值、查找和单链表的一样，此处不再赘述。

bool GetElem_L(DuLinkList L,int i,int &e)//双向链表的取值
{
	//在带头结点的双向链表L中查找第i个元素
	//用e记录L中第i个数据元素的值
	int j;
	DuLinkList p;
	p=L->next;//p指向第一个结点，
	j=1; //j为计数器
	while(j<i&&p) //顺链域向后扫描，直到p指向第i个元素或p为空
    {
		p=p->next; //p指向下一个结点
		j++; //计数器j相应加1
	}
	if(!p||j>i)
		return false; //i值不合法i＞n或i<=0
	e=p->data; //取第i个结点的数据域
	return true;
}

查找：

bool LocateElem_L(DuLinkList L,int e) //按值查找
{
	//在带头结点的双向链表L中查找值为e的元素
	DuLinkList p;
	p=L->next;
	while(p&&p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
		p=p->next; //p指向下一个结点
	if(!p)
        return false; //查找失败p为NULL
    return true;
}

插入：

双向链表因为有两个指针，可以向前后两个方向操作，直接找到第 i 个节点，就可以把新节点插入第 i 个节点之前。

注意：这里假设第 i 个节点是存在的，如果第 i 个节点不存在，而第 i−1 个节点存在，还是需要找到第 i−1 个节点，将新节点插入第 i−1 个节点之后，

image-20220909223237857

  1. p->prior->next=s：s 节点的地址赋值给 p 的前驱节点的 next 指针域，即 p 的前驱的next 指针指向 s。
  2. s->prior=p->prior：p 的前驱的地址赋值给 s 节点的 prior 指针域，即 s 节点的 prior 指针指向 p 的前驱。
  3. s->next=p：p 节点的地址赋值给 s 节点的 next 指针域，即 s 节点的 next 指针指向 p 节点。
  4. p->prior=s：s 节点的地址赋值给 p 节点的 prior 指针域，即 p 节点的 prior 指针指向 s 节点。

因为 p 的前驱无标记，一旦修改了 p 节点的 prior 指针，p 的前驱就找不到了，因此，最后修改这个指针。只需要将④语句放在最后修改即可，①②③语句顺序无要求。

原则：先修改没有指针标记的那一端。

bool ListInsert_L(DuLinkList &L,int i,int &e)//双向链表的插入
{
	//在带头结点的单链表L中第i个位置之前插入值为e的新结点
	int j;
	DuLinkList p, s;
	p=L;
	j=0;
	while(p&&j<i) //查找第i个结点，p指向该结点
    {
		p=p->next;
		j++;
	}
	if(!p||j>i)//i＞n+1或者i＜1
		return false;
	s=new DuLNode;     //生成新结点
	s->data=e;       //将新结点的数据域置为e
	p->prior->next=s;
	s->prior=p->prior;
	s->next=p;
	p->prior=s;
	return true;
}

删除：

双向链表只要直接找到第 i 个节点，然后修改指针即可：

image-20220909224117840

  1. p->prior->next=p->next：将 p 的后继节点的地址赋值给 p 的前驱节点的 next 指针域。即 p 的前驱节点的 next 指针指向 p 的后继节点。

  2. p->next->prior =p->prior：将 p 的前驱节点的地址赋值给 p 的后继节点的 prior 指针域，即 p 的后继节点的 prior 指针指向 p 的前驱节点。此项修改的前提是 p 的后继节点存在，如果不存在，则不需要此项修改。

    删除节点修改指针没有顺序，先修改哪个都可以。

bool ListDelete_L(DuLinkList &L,int i) //双向链表的删除
{
	//在带头结点的双向链表L中，删除第i个位置
	DuLinkList p;
	int j;
	p=L;
	j=0;
	while(p&&(j<i)) //查找第i个结点，p指向该结点
	{
		p=p->next;
		j++;
	}
	if(!p||(j>i))//当i>n或i<1时，删除位置不合理
		return false;
    if(p->next) //如果p的直接后继结点存在
        p->next->prior=p->prior;
	p->prior->next=p->next;
	delete p;        //释放被删除结点的空间
	return true;
}

循环链表：

如果从当前节点开始，无法访问该节点前面的节点，而最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问所有的节点，这就是循环链表。

循环链表和普通链表的区别就是最后一个节点的后继指向了头节点，还要让头节点的前驱指向最后一个节点。

链表的优点和缺点：

优点：

链表是动态存储，不需要预先分配最大空间；插入删除不需要移动元素。

缺点：

每次动态分配一个节点，每个节点的地址是不连续的，需要有指针域记录下一个节点的地址，指针域需要占用一个 int 的空间，因此存储密度低（数据所占空间/节点所占总空间）。

存取元素必须从头到尾按顺序查找，属于顺序存取。

线性表的应用

合并有序顺序表：

**题目：**将两个有序（非递减）顺序表 La 和 Lb 合并为一个新的有序（非递减）顺序表。

思路：

  1. 首先创建一个顺序表 Lc，其长度为 La 和 Lb 的长度之和。
  2. 然后从 La 和 Lb 中分别取数，比较其大小，将较小者放入 Lc 中，一直进行下去，直到其中一个顺序表 La 或 Lb 中的数取完为止。
  3. 把未取完的数再依次取出放入 Lc 中即可。

解题：

  1. 设置 3 个工作指针：i、j、k（其实是整型数）。其中，i 和 j 分别指向 La 和 Lb 中当前待比较的元素，k 指向 Lc 中待放置元素的位置

    image-20220910095920854

  2. 比较 La.elem[i]和 Lb.elem[j]，将较小的赋值给 Lc.elem[k]，同时相应指针向后移动。如此反复，直到顺序表 La 或 Lb 中的数取完为止。

    image-20220910100100150

  3. 把 La 或 Lb中未取完的数依次取出，放入 Lc 中即可

#include<iostream>
#include"sqlist.h"//引入自定义头文件,源码目录下名为sqlist.h的文件 
using namespace std;

void MergeSqlist(SqList La,SqList Lb,SqList &Lc)//顺序有序表的合并
{
	//已知顺序有序表La和Lb的元素按值非递减排列
	//La和Lb合并得到新的顺序有序表Lc，Lc的元素也按值非递减排列
	int i,j,k;
	i=j=k=0;
	Lc.length=La.length+Lb.length; //新表长度为待合并两表的长度之和
	Lc.elem=new int[Lc.length]; //为合并后的新表分配一段空间
	while(i<La.length&&j<Lb.length) //两个表都非空
	{
		if(La.elem[i]<=Lb.elem[j]) //依次取出两表中值较小放入到Lc表中
			Lc.elem[k++]=La.elem[i++];
		else
			Lc.elem[k++]=Lb.elem[j++];
	}
	while(i<La.length) //La有剩余，依次将La的剩余元素插入Lc表的最后
		Lc.elem[k++]=La.elem[i++];
	while(j<Lb.length) //Lb有剩余，依次将Lb的剩余元素插入Lc表的最后
		Lc.elem[k++]=Lb.elem[j++];
}

算法复杂度分析：

合并操作需要将 La 和 Lb 中的每一个元素取出放入 Lc 中，如果 La 和 Lb 的长度分别为 m、n，那么合并操作时间复杂度为 O(m+n) 空间复杂度也为 O(m+n)

合并有序链表：

**题目：**将两个有序（非递减）单链表 La 和 Lb 合并为一个新的有序（非递减）单链表。

思路：

链表合并不需要再创建空间，只需要“穿针引线”，把两个单链表中的节点按非递减的顺序串联起来即可。

注意：单链表的头指针不可以移动，一旦头指针丢失，就找不到该单链表了，因此需要辅助指针。

解题：

  1. 设置 3 个辅助指针 p、q、r，p 和 q 分别指向 La 和 Lb 链表的当前比较位置，新链表头指针 Lc 指向 La，当作合并后的头节点。r 指向 Lc 的当前最后一个节点，利用 r 指针“穿针引线”：

    image-20220910102955699

  2. 穿针引线。比较元素大小，将较小元素用 r 指针串起来。

  3. 第 1 次比较，p->data=4 > q->data=2，用 r 指针将 q 节点串起来。串联剩余部分，直到其中一个指针为空。

    r->next=q; //把 q 节点的地址赋值给 r 的 next 指针域，即 r 的 next 指针指向 q
r=q; //r 指针指向 Lc 的当前尾节点
q=q->next; //q 指针向后移动，等待处理下一个节点

  4. 若 p 指针不为空，用 r 指针将 p 串连起来，即 r->next=p;。注意这里只是把这个指针连上即可，剩余的节点不需要再处理。释放 Lb 节点空间，即 delete Lb。

void mergelinklist(LinkList La,LinkList Lb,LinkList &Lc)
{
    LinkList p,q,r;
    p=La->next; //p指向La的第一个元素
    q=Lb->next; //q指向Lb的第一个元素
    Lc=La;      //Lc指向La的头结点
    r=Lc;       //r指向Lc的尾部
    while(p&&q)
    {
        if(p->data<=q->data)//把p指向的结点串起来
        {
            r->next=p;
            r=p;
            p=p->next;
        }
        else             //把q指向的结点串起来
        {
            r->next=q;
            r=q;
            q=q->next;
        }
    }
    r->next=p?p:q;//相当于if(p) r->next=p; else r->next=q;
    delete Lb;
}

算法复杂度分析：

链表合并不需要再创建空间，只需要穿针引线，把两个单链表中的节点按非递减的顺序串联起来即可。因此在最坏的情况下，需要串联每一个节点，如果 La 和 Lb 的长度分别为 m、n 时间复杂度为 O(m+n) 空间复杂度为 O(1)

就地逆置单链表：

**题目：**将带有头节点的单链表就地逆置。即元素的顺序逆转，而辅助空间复杂度为 O(1)。

思路：

头插法创建单链表得到的序列正好是逆序，那么我们就利用头插法建表的思路，实现就地逆置。

注意：在修改指针之前，一定要用一个辅助指针记录断点，否则后面这一部分就会遗失，再也找不到了。

解题：

  1. 首先用 p 指针指向第一个元素节点，然后将头节点的 next 域置空。

  2. 将 p 节点用头插法插入链表 L 中，插入之前用 q 指针记录断点。

    q=p->next; // q 指向 p 的下一个节点，记录断点
p->next=L->next; //将 L 的下一个节点地址赋值给 p 的 next 域
L->next=p; //将 p 节点地址赋值给 L 的 next 域
p=q; //p 指向 q

  3. p 指针为空，算法停止，单链表就地逆置完毕。

void reverselinklist(LinkList &L)
{
    LinkList p,q;
    p=L->next; //p指向L的第一个元素
    L->next=NULL; //头结点的next域置空：
    while(p)
    {
        q=p->next;//q指向p的下一个结点，记录断点；
        p->next=L->next; //头插法，将L的下一个结点地址赋值给p的next域
        L->next=p; //将p结点地址赋值给L的next域
        p=q;//指针后移，p指向q；
    }
}

算法复杂度分析：

算法对单链表进行了一趟扫描，如果 L 的长度为 n，则时间复杂度为 O(n) 没有使用其他辅助空间，只是几个辅助指针变量，因此空间复杂度为 O(1)

查找链表的中间节点：

**题目：**带有头节点的单链表 L，设计一个尽可能高效的算法求 L 中的中间节点。

思路：

此类题型可以使用快慢指针来解决。一个快指针，一个慢指针，快指针走两步，慢指针走一步。当快指针指向结尾的时候，慢指针刚好指向中间节点。

解题：

放置两个小青蛙，一个跳得远，一次走两块石头；一个跳得近，一次走一块石头。当快青蛙走到终点时，慢青蛙正好走到中间。

LinkList findmiddle(LinkList L)
{
    LinkList p,q;
    p=L; //p为快指针，初始时指向L
    q=L; //q为慢指针，初始时指向L
    while(p!=NULL&&p->next!=NULL)
    {
        p=p->next->next;//p为快指针一次走两步；
        q=q->next; //q为慢指针一次走一步
    }
    return q;//返回中间结点指针
}

算法复杂度分析：

算法对单链表进行了一趟扫描，如果 L 的长度为 n，则时间复杂度为 O(n) 没有使用其他辅助空间，只是几个辅助指针变量，因此空间复杂度为 O(1)

思考：

如何在单链表中查找倒数第 k 个节点？

仍然可以使用快慢指针，慢指针不要动，快指针先走 k−1 步，然后两个指针一起以同样的速度走。当快指针走到终点时，慢指针正好停留在倒数第 k 个节点，为什么呢？
因为它们之间的距离始终保持 k−1。

LinkList findk(LinkList L,int k)
{
    LinkList p,q;
    p=L->next; //p为快指针，初始时指向第一个数据结点
    q=L->next; //q为慢指针，初始时指向第一个数据结点
    while(p->next!=NULL)
    {
        if(--k<=0) //k减到0时，慢指针开始走
            q=q->next;//q为慢指针
        p=p->next; //p为快指针，先走 k - 1步；
    }
    if(k>0)
        return NULL;
    else
        return q;//返回中间结点指针
}

算法复杂度分析：

算法对单链表进行了一趟扫描，如果 L 的长度为 n，则时间复杂度为 O(n) 没有使用其他辅助空间，只是几个辅助指针变量，因此空间复杂度为 O(1)

用快慢指针还可以解决很多问题，例如判断链表是否有环，判断两个链表是否相交等。

删除链表中的重复元素：

**题目：**用单链表保存 m 个整数，节点的结构为(data,next)，且|data|≤n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。

思路：

本题数据大小有范围限制，因此可以设置一个辅助数组记录该数据是否已出现，如果已出现，则删除；如果未出现，则标记。一趟扫描即可完成。

解题：

  1. 设置一个辅助数组 flag[]，因为 n 为正整数，不包括 0，所以 0 空间不用。需要分配 n+1 个辅助空间，初始化时都为 0，表示这些数还未出现过，
  2. 设置 p 指针指向头节点，检查第一个数据元素是否已出现过。令 x=abs(p->next->data)，如果已出现过（flag[x]=1），则删除该节点；如果该节点数据元素未出现过，则标记 flag[x]=1，p 指针向后移动，直到处理完毕。
  3. abs(p->next->data)=5，读取 flag[5]=0，说明该节点数据元素未出现过，标记 flag[5]=1，p 指针向后移动。
  4. p->next 为空，算法停止。对于链表中 data 的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
void Deleterep(LinkList &L)//删除重复元素
{
    LinkList p,q;
    int x;
    int *flag=new int[n+1]; //定义flag数组，分配n+1个空间
    for(int i=0;i<n+1;i++) //初始化
        flag[i]=0;
    p=L; //指向头结点
    while(p->next!=NULL)
    {
        x=abs(p->next->data);
        if(flag[x]==0)//未出现过
        {
            flag[x]=1; //标记出现
            p=p->next;           //指针后移
        }
        else
        {
            q=p->next;
            p->next=q->next;//删除重复元素
            delete q;

        }
    }
    delete []flag;
}

算法复杂度分析：

根据题意，单链表中保存 m 个绝对值小于等于 n 的整数，因此链表元素个数为 m，算法从头到尾扫描了一遍链表，时间复杂度为 O(m) 采用了辅助数组 flag[]，因为 n 为正整数，不包括 0，所以 0 空间不用，需要分配 n+1 个辅助空间，因此空间时间复杂度为 O(n)

线性表学习技巧

顺序表和链表的比较：

image-20220910113841323

顺序表解题技巧：

  • 位序和下标差 1，第 i 个元素的下标为 i−1。
  • 交换元素、有序合并需要借助辅助空间。
  • 交换元素、有序合并需要借助辅助空间。

链表解题技巧：

  • 赋值语句两端的含义：等号的右侧是节点的地址，等号的左侧是节点的指针域
  • 修改指针的顺序：先修改没有指针标记的那一端
  • 建立链表的两种方法：头插法、尾插法。头插法是逆序建表，尾插法是正序建表
  • 链表逆置、归并不需要额外空间，属于就地操作。
  • 快慢指针法：快慢指针可以解决很多问题，如链表中间节点、倒数第 k 个节点、判断链表是否有环、环的起点、公共部分的起点等。
文章作者: QT-7274
文章链接: https://qt-7274.github.io/2022/09/06/shu-ju-jie-gou-ru-men-xian-xing-biao/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 QT-7274 !
数据结构
赏
评论
  目录