线性表

技术探索
🗨️字数统计=2.6k字 ⏳阅读时长≈11分钟

一、线性表的定义

具有相同数据类型的 n 个数据元素的有限序列

线性表是一种逻辑结构，表示元素之间一对一的逻辑关系。

顺序表和链表是存储结构。


二、顺序表

1. 顺序表定义：

线性表的顺序存储

1
2
3
4
typedef struct{
    int data[50];
    int length;
} SqList;

逻辑上相邻的两个元素在物理位置上也相邻

特点：

  • 随机访问（通过首地址和元素序号可在时间O(1)内找到元素）
  • 插入和删除需要移动大量元素
  • 存储密度高，每个结点只存储数据元素

2. 顺序表基本操作

① 插入

在第i个位置(下标i-1)插入元素e

1
2
3
4
5
 //第i个元素及其之后的元素后移
for (int j = length; j >= i; j--)
    L[j] = L[j - 1];
L[i - 1] = e;
length++;
  • 最好情况：在表尾插入，时间复杂度 O(1)
  • 最坏情况：在表头插入，时间复杂度 O(n)
  • 平均情况：时间复杂度 O(n)

② 删除

删除第i个位置的元素，用e返回

1
2
3
4
5
e = L[i-1];
//从第i个位置元素前移
for(int j = i; j<length;j++) 
    L[j-1] = L[j];
length --;
  • 最好情况：删除表尾元素，O(1)
  • 最坏情况：删除表头元素，O(n)
  • 平均情况：O(n)

③ 按值查找

1
2
3
for (int i = 0; i < length; i++)
    if (L[i] == e)
        return i;
  • 最好情况：查找元素在表头，O(1)
  • 最坏情况：查找元素在表尾，O(n)
  • 平均情况：O(n)

3. 顺序表相关算法

① 删除线性表中所有值为x的数据元素

  • 用 k 记录顺序表中等于 x 的元素个数，边扫描边统计 k

  • 遍历结束后将不等于 x 的元素前移 k 个位置，最后修改 L 的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
void delete_x(int &a, int x)
{
    int i = 0;
    int k = 0; //记录当前查询到的x的个数
    while(i<len){
        if(a[i]==x)
            k++;
        else
            a[i-k] = a[i];
        i++;
    }
    len = len - k;
}

② 将两个有序顺序表合成一个有序顺序表

归并思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct{
    int data[50];
    int length;
} SqList;

bool merge(SqList a,SqList b,SqList &c){
    if(a.length+b.length>50)
        return false;
    int i=0,j=0,k=0;
    while(i<a.length && j<b.length){
        if(a.data[i]<b.data[j]){ //a表元素较小
            c.data[k++] = a.data[i++];
        }
        else //b表元素较小
            c.data[k++] = b.data[j++];
    }
    //若a表未比较完
    while(i<a.length){
        c.data[k++] = a.data[i++];
    }
    while(j<b.length){
        c.data[k++] = b.data[j++];
    }
    c.length = k;
    return true;
}

③ 将数组R中的n个元素循环左移p个位置

题目等同于将ab转变为ba（a为前p个元素）

XY —> (XTYT)T = YX

1
2
3
reverse(R,0,n-1);
reverse(R,0,p-1);
reverse(R,p,n-1);

④ 找出两个等长升序序列A，B的中位数（取上整）

A中位数a，B中位数b

  • 若a=b: 返回a或b

  • 若a>b: 舍弃a右边较大的部分，同时舍弃b左边较小的部分（不删除中位数）

  • 若a<b：舍弃a左边较小的部分，同时舍弃b右边较大的部分

  • 重复上述操作，直到两序列都只剩一个元素，较小值即为中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int Mid(int A[], int B[], int n)
{
    int s1 = 0, d1 = n - 1, m1; //首位数，末位数，中位数
    int s2 = 0, d2 = n - 1, m2;
    while (s1 != d1 || s2 != d2)
    { //表中不只一个元素
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == A[m2])
            return A[m1];
        else if (A[m1] > A[m2])
        { //舍弃A较大部分和B较小部分
            if ((s1 + d1) % 2 == 0)
            { //元素个数为奇数,保留中间点
                d1 = m1;
                s2 = m2;
            }
            else
            { //元素个数为偶数，B的中间点也舍弃
                d1 = m1;
                s2 = m2 + 1;
            }
        }
        else
        { //舍弃A较小部分和B较大部分
            if ((s1 + d1) % 2 == 0)
            { //元素个数为奇数,保留中间点
                d2 = m2;
                s1 = m1;
            }
            else
            { //元素个数为偶数，A的中间点也舍弃
                d2 = m2;
                s1 = m1 + 1;
            }
        }
    }
    return A[s1]<A[s2]?A[s1]:A[s2];
}

三、链表

链表分为：

  • 单链表
  • 双链表
  • 循环单链表（判空条件：表尾结点的next是否是等于头指针）
  • 循环双链表

1. 单链表

① 定义

1
2
3
4
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

单链表可以解决顺序表需要大量连续存储空间的缺点，但单链表附加指针域，也存在浪费存储空间的缺点

单链表是非随机存储的存储结构：即不能直接找到表中某个特点的结点。需要从头开始遍历。

单链表访问前驱的时间复杂度为O(n),访问后继O(1)

引入头节点的优点：

  • 链表的第一个元素位置上的操作与其他位置的元素操作一样，无须进行特殊处理

  • 无论链表是否为空，其头指针都是指向头节点的非空指针，空表和非空表的处理得到了统一

    （头指针始终指向第一个结点，有头节点则指向头节点，无头节点则指向第一个元素结点）

② 基本操作

头插法：(读入顺序和生成顺序相反）

1
2
s->next = L->next;
L->next = s;

尾插法：(读入顺序和生成顺序相同）

1
2
3
//尾指针r
r->next = s;
r = s;

按序号查找

按值查找

插入结点：

p之后插入s (p的位置需要自行查找)

1
2
s->next = p->next;
p->next = s;

删除结点：

1
2
3
4
//删除p之后的q
q = p->next;
p->next = q->next;
free(q); //释放结点的存储空间

求表长

2. 双链表

① 定义

就是同时具有前驱指针和后继指针的链表

访问前驱和后继结点时间复杂度都是O(1)

1
2
3
4
typedef struct DNode{
    int data;
    struct DNode* next,*prior;
}DNode,*DinkList;

② 基本操作

插入：

p之后插入s


1
2
3
4
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;

删除：

1
2
3
4
//删除p之后的s
p->next = s->next;
s->next->prior = p;
free(s);

3. 循环单链表

判空条件：表尾结点的next是否是等于头指针

4. 循环双链表


四、顺序表和链表的比较


五、链表的相关算法

1. 递归删除不带头节点的单链表L中所有值为x的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
void Del(LinkList &L,int x){
    LNode *p;
    if(L==NULL)
        return;
    else if(L->data == x){
        p=L;
        L=L->next;
        free(p);
        Del(L,x);
    }
    else 
        Del(L->next,x);
}

2. 反向输出单链表中每个结点的值

1
2
3
4
5
void rprint(LinkList L){
    if(L->next!=NULL)
        rprint(L->next);
    cout<<L->data<<" ";
}

3. 带头结点的单链表就地逆置

1
2
3
4
5
6
7
8
9
10
11
12
//摘下头结点，同头插法
LinkList Reverse(LinkList &L){
    LNode *p=L->next, *r=L;//r为后继结点，防止断链
    L->next = NULL; //摘下头节点
    while(p){
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r; //继续插入
    }
    return L;
}

4. 找出两个链表的公共结点

算法思想：两个链表公共结点之后的所有结点都重合，呈现Y型；

先走完较长链表的多出来的一部分，到达同样长度后再同步比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LinkList Search_Common(LinkList L1, LinkList L2)
{
    int len1 = L1.length;
    int len2 = L2.length;
    int longlist, shortlist;
    if (len1 > len2)
        longlist = L1->next;
    shortlist = L2->next;
    dist = len1 - len2;
    else longlist = L2;
    shortlist = L1;
    dist = len2 - len1;
    while (dist--)
        longlist = longlist->next;
    while (longlist != Null)
    {
        if (longlist == shortlist)
            return longlist;
        else
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }
}

5. 在一个递增有序的单链表中，删除数值相同的元素，使表中不再有重复的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Del_Same(LinkList &L){
    LNode *p=L->next, *r; //后继结点r
    if(p==NULL)
        return;
    while(p->next!=NULL){ 
        r = p->next;
        if(p->data == r->data){
            p->next = r->next;
            free(r);
        }
        else
            p = p->next;
    }
}

6. 查找链表中倒数第K个位置的结点

算法思想：快慢指针法；

快指针先走k步，随后快慢指针同时依次后移，快指针到达链表尾部时，慢指针正好访问倒数第k个位置结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Search_k(LinkList L, int k){
  LNode *p = L->next, *q = L->next;
  int count = 0;
  while(p!=Null){
    if(conut < k){
      p = p->next;
      count++;
    }
    else{
      p = p->next;
      q = q->next;
    }
  }
  if(count > k) //k值超过了线性表长度
    return 0;
  else 
    return 1;
}

7. 查找单链表的中间结点

此题可应用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，前面的指针每次走两步，后面的指针每次走一步，前面的指针走到最后一个结点时，后面的指针所指结点就是中间结点，即第（n/2+1）个结点。注意链表为空、链表结点个数为1和2的情况。时间复杂度O（n）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 获取单链表中间结点，若链表长度为n(n>0)，则返回第n/2+1个结点  
ListNode * GetMiddleNode(ListNode * pHead)  {  
      if(pHead == NULL || pHead->m_pNext == NULL) // 链表为空或只有一个结点，返回头指针  
          return pHead;  
    
      ListNode * pAhead = pHead;  
      ListNode * pBehind = pHead;  
      while(pAhead->m_pNext != NULL) // 前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步 
      {  
           pAhead = pAhead->m_pNext;  
      	   pBehind = pBehind->m_pNext;  
           if(pAhead->m_pNext != NULL)  
            	pAhead = pAhead->m_pNext;  
       }  
       return pBehind; // 后面的指针所指结点即为中间结点  
 }

8. 如何判断单链表是否有环以及环的入口

假设一个单链表有环，他就是下面这种情况：

判断是否有环：使用二指针法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。

如存在环，则两者相遇；如不存在环，fast遇到NULL退出

1
2
3
4
5
6
7
while (slow != NULL&& fast != NULL && fast -> next != NULL)  {  
      slow = slow -> next ;  
      fast = fast -> next -> next ;  
      if (slow == fast)  
          return true ;  
}  
return false;

环的入口：头结点到入口的距离 = slow 和 fast 指针相遇点到入口的距离。设定一个start指针指向头结点，meet指针指向slow和fast指针相遇处，将start指针和meet指针遍历，start指针和meet指针相等时，则该地址为环的入口地址。

1
2
3
4
5
6
7
8
9
//环的入口节点
   start=head;
   meet=fast;//meet=slow
   while(start!= meet)//遍历指针，直到start指针和meet指针相等
   {
       start = start->next;
       meet = meet->next;
   }
   return start;//return meet
分享到