线性表的顺序表示

2022.12.10

线性表的顺序表示顺序表的定义静态分配的顺序表定义动态分配的顺序表定义顺序表上基本操作的实现例题

顺序表的定义

静态分配的顺序表定义


// 静态分配的顺序表定义
#define MaxSize 15 // 定义最大数量
typedef struct 
{
  Elemtype data[MaxSize]; // 用静态数组存放数据元素
  int length;             // 当前表长
}SqList;

// 初始化
void InitList(SqList &L)
{
  // 默认初始值为0
  for(int i=0; i<MaxSize; i++)
    L.data[i] = 0;
  //长度为0
  L.length = 0;
}

存储的逻辑顺序与物理顺序相同
位序n的内存地址计算：LOA(A)+sizeof(Elemtype)*(n-1)
随机访问

动态分配的顺序表定义


// 动态分配的顺序表定义
#define InitSize 10 // 默认最大长度
typedef struct
{
  int* data;
  int MaxSize,length;
}SeqList;

// 初始化
void InitList(SeqList &L)
{
  // 创造空间(默认InitSize大小)
  L.data = (int*)malloc(sizeof(int)*InitSize); // C type
  // L.data = new int[InitSize]; // C++ type
  // 默认初始值为0
  for(int i=0; i<InitSize; i++)
    L.data[i] = 0;
  //长度为0
  L.length = 0;
  //最大容量
  L.MaxSize = InitSize;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len)
{
  // 寄存用的指针
  int* temp = L.data;
  // 申请新空间
  L.data = (int*)malloc(sizeof(int)*(len+L.MaxSize));
  // 复制数据
  for(int i=0;i<L.length;i++){
    L.data[i] = temp[i];
  }
  // 增加长度
  L.MaxSize = L.MaxSize+len;
  // 释放原内存
  free(temp);
}

动态的顺序表仍然是顺序！不是链式！
缺点：插入删除需要完成大量的移动

顺序表上基本操作的实现


// 插入操作
bool ListInsert(SqList &L, int i, int e)
{
  // 判断i是否有效
  if(i<1||i>L.length+1){
    printf("invaled i: i=%d,length=%d\n",i ,L.length);
    return false;
  }
  // 判断是否栈满
  if(L.length >= MaxSize){
    printf("full\n");
    return false;
  }
  // 进行元素后移
  for(int j=L.length; j>=i; j--){
    L.data[j] = L.data[j-1];
  }
  // 进行新元素插入
  L.data[i-1] = e;
  // 线性表长度加一
  L.length++;
  return true;
}

插入操作时间复杂度：最好O(1)，最坏O(n)，平均O(n)，平均移动次数=n/2。【0～n】


// 删除操作
// 删除顺序表中第i（ l<=i<=L.length ）个位置的元素，
// 若成功则返回 true ，否则返回 false
bool ListDelete(SqList &L, int i)
{
  // 判断i是否有效
  if(i<1||i>L.length+1){
    printf("invaled i\n");
    return false;
  }
  // 后面元素前移
  for(int j=i; j<L.length; j++){
    L.data[j-1] = L.data[j];
  }
  // 线性表长减一
  L.length--;
  return true;
}

删除操作时间复杂度：最好O(1)，最坏O(n)，平均O(n)，平均移动次数=(n-1)/2。【0～n-1】


// 按位查找
int GetItem(SqList L, int i)
{
  //判断i是否有效
  if(i<1||i>L.length){
    printf("invaled i\n");
    return 0;
  }
  return L.data[i-1];
}

// 按值查找 - 返回位序(下标+1)
int LocateElem(SqList &L, int num)
{
  for(int i=0;i<L.length; i++)
    // 注意如果比较结构类型不能用==
    // 但是考试时可以直接写==
    if(num==L.data[i])
      return i+1; // 注意返回的是位序(下标+1)
  return 0;
}

按值查找时间复杂度：最好O(1)，最坏O(n)，平均O(n)，平均比较次数(n+1)/2。【1～n】

例题

下述（）是顺序存储结构的优点。 A. 存储密度大 B. 插入运算方便 C. 删除运算方便 D. 方便地运用于各种逻辑结构的存储表示
【答案】：A
线性表的顺序存储结构是一种（）。 A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D. 散列存取的存储结构
【答案】：B->A
一个顺序表所占用的存储空间大小与（）无关。 A. 表的长度 B. 元素的存放顺序 C. 元素的类型 D. 元素中各字段的类型
【答案】：B
若线性表最常用的操作是存取第 i 个元素及其前驱和后继元素的值，为了提高效率，应来用（）的存储方式。 A. 单链表 B. 双向链表 C. 单循环链表 D. 顺序表
【答案】：B->D
我的理解：
“最省时间”这种表述是暗含着用空间换时间的意思。
一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入、删除操作，则利用（）存储方式可以节省时间。 A. 顺序表 B. 双链表 C. 带头结点的双循环链表 D. 单循环链表
【答案】：C->A，在最后进行！！
在n个元素的线性表的数组表示中，时间复杂度为 O(1) 的操作是（）。 I. 访问第 i(1≤i≤n) 个结点和求第 i(2≤i≤n) 个结点的直接前驱 II. 在最后一个结点后插入一个新的结点 III. 删除第1个结点 IV. 在第i（1≤i≤n）个结点后插入一个结点 A. I B. II、 III C. I、II D. I、II、III
【答案】：A->C
设线性表有n个元素，严格说来，以下操作中，（）在顺序表上实现要比在链表上实现的效率高。 I. 输出第 i(1≤i≤1) 个元素值 II. 交换第 3 个元素与第 4 个元素的值 III. 顺序输出这 n 个元素的值 A. I B. I、III C. I、II D. II、III
【答案】：C
在一个长度为n的顾序表中删除第i（1≤i≤n）个元素时，需向前移动（）个元素。 A. n B. i-1 C. n-i D n-i+1
【答案】：C
对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为（）。 A. O(n), O(n) B. O(n), O(1) C. O(1), O(n) D. O(1), O(1)
【答案】：C
若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，则i的合法值应该是( )。 A. 1≤i≤n B. 1≤i≤n+1 C. 0≤i≤n-1 D. 0≤i≤n
【答案】：B
顺序表的插入算法中，当n个空间已满时，可再申请增加分配 m 个空间，若申请失败，则说明系统没有（）可分配的存储空问。 A. m个 B. m个连续 C. n+m个 D. n+m个连续
【答案】：D

【2010 统考真题】设将n（n＞1）个整数存放到一维数组R中。设计一个在时问和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0＜p＜n）个位置，即将R中的数据由 X0,X1,...,Xn-1 变换为 Xp,Xp+1,...,Xn-1,X0,X1,...,Xp-1。要求： 1）给出算法的基本设计思想 2）根据设計思想，来用C或C++或Java 语言描述算法，关键之处给出注释。 3）说明你所设计算法的时问复杂度和时间复杂度。

【答案】：

首先将整个线性表逆序。然后将下标为n-1到p的序列逆序，下标为p-1到0的序列逆序。


void swap(int &a,int &b){
  int temp = b;
  b = a;
  a = temp;
}

void transform(int[] &R,int n,int p){
  for(int i=0;i<n/2;i++)
    swap(R[i],R[n-i]);
  for(int i=0;i<p/2;i++)
    swap(R[n-i],R[n-p+i]);
  for(int i=0;i<(n-p)/2;i++)
    swap(R[i],R[n-p-1-i]);
}

时间复杂度：O(n) 空间复杂度：O(1)

【2011 统考真题】一个长度为L(L≥1）的升序序列S，处在第⌈L/2⌉个位置的数称为 S 的中位数。例如，若序列S=(11,13,15,17,19），则S的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求： 1）给出算法的基本设计思想。 2）根据设计思想，来用C或 C++或Java的编程语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度和空间复杂度

【答案(老的，已淘汰)】：

中位数是排序后位序为⌈Length⌉的元素。只需要分别找出两个序列的中位数，比较这两个中位数的大小，记较小的为a1，较大的为a2。那么由比a1序列中大的一半与a1和a2序列中小的一半与a2构成新的两个序列。但要注意两个序列舍弃的数的数量要一样，以此类推，直到可以直接找到中位数。


#include <stdio.h>

/**
 * 计算四个数中的中位数
 */
int mid_of_four(int a,int b,int c,int d){
  printf("%d,%d,%d,%d\n",a,b,c,d);
  if(a<=c) // 丢弃a
    if(b<=d)// 丢弃a,d
      return b<=c ? b : c;
    else   // 丢弃a,b
      return d<=c ? d : c;
  else     // 丢弃c
    if(b<=d)// 丢弃c,d
      return b<=a ? b : a;
    else   // 丢弃c,b
      return d<=a ? d : a;
}

/**
 * 计算位序L的中位数位序
 */
int mid_index(int L){
  return L/2+(L%2!=0);
}

/**
 * 计算两个等长升序序列的中位数
 * a是S1开始的下标(初始为0）
 * b是S2开始的下标(初始为0)
 * L是序列长度
 */
int transform(int S1[],int a, int S2[], int b, int L){
  if(L==1)
    return S1[a]<=S2[b] ? S1[a] : S2[b];
  else if(L==2)
    return mid_of_four(S1[a],S1[a+1],S2[b],S2[b+1]);
  else{
    int m = mid_index(L);
    int l = m+(L%2==0);

    if(S1[a+m-1]<=S2[b+m-1]){
      printf("%d<=%d: %d,%d,[%d,%d]\n",S1[a+m-1],S2[b+m-1],S1[a+m-1],S2[b],m,l);
      return transform(S1,a+m-1,S2,b,l);
    }
    else{
      printf("%d>%d: %d,%d,[%d,%d]\n",S1[a+m-1],S2[b+m-1],S1[a],S2[b+m-1],m,l);
      return transform(S1,a,S2,b+m-1,l);
    }
  }
}

int transform2(int S1[],int a, int S2[], int b, int L){
  int m;
  while(1){
    if(L==1)
      return S1[a]<=S2[b] ? S1[a] : S2[b];
    else if(L==2)
      return mid_of_four(S1[a],S1[a+1],S2[b],S2[b+1]);
    else{
      m = mid_index(L);
      int l = m+(L%2==0);
      if(S1[a+m-1]==S2[b+m-1])
        return S2[b+m-1];
      else if(S1[a+m-1]<S2[b+m-1]){
        printf("%d<=%d: %d,%d,[%d,%d]\n",S1[a+m-1],S2[b+m-1],S1[a+m-1],S2[b],m,l);
        a = a+m-1;
      }
      else{
        printf("%d>%d: %d,%d,[%d,%d]\n",S1[a+m-1],S2[b+m-1],S1[a],S2[b+m-1],m,l);
        b = b+m-1;
      }
      L=l;
    }
  }
}

int main(){
  int S1[6] = {2,4,6,8,10,13}; // 2,[4],6,8  -> 4 [6] 8 -> [6] 8
  int S2[6] = {1,3,5,7,9,11}; //  5,[7],9,11 -> 5 [7] 9 -> [5] 7
  printf("%d\n\n",transform(S1,0,S2,0,6));
  printf("%d\n\n",transform2(S1,0,S2,0,6));

  int S3[5] = {11,13,15,17,19};
  int S4[5] = {2,4,6,8,20};
  printf("%d\n\n",transform(S3,0,S4,0,5));
  printf("%d\n\n",transform2(S3,0,S4,0,5));


  return 0;
}

transform2方案时间复杂度：O(log2 n) 空间复杂度：O(1)
[虽然和标答不一样，但是思路一样]

【答案（新的 2022.12.10）】：现在看来之前的答案思路繁琐。

i. 首先求A与B的中位数，a和b
ii. 如果a=b，a或b即为中位数
iii. 如果a<b(b>a时同理)，a左边有n个元素，b右边有m个元素，舍弃a左边与b右边的min(n,m)个元素，更新a与b，重复上述过程。


x
void transform(int A[], int B[], int lenA, int lenB){
  int As=0,Ae=lenA-1; // A的起止位置
  int Bs=0,Be=lenB-1; // A的起止位置
  int a = (As+Ae)/2; // A的中位数
  int b = (Bs+Be)/2; // B的中位数
  int lenL;
  int lenR;
  while(Ae!=As){
    a = (As+Ae)/2;
    b = (Bs+Be)/2;
    if(A[a]==B[b]) return A[a];
    lenL = b-Bs;
    lenR = Ae-a;
    if(A[a]<B[b]){
      if(lenL < LenR){
        As += LenL;
        Be -= lenL;
      }else{
        As += LenR;
        Be -= LenR;
      }
    }
    if(A[a]>B[b]){
      if(lenL < LenR){
        Bs += LenL;
        Ae -= lenL;
      }else{
        Bs += LenR;
        Ae -= LenR;
      }
    }
  }
  return A[As]<B[Bs]? A[s]:B[s];
}

时间复杂度：O(log2 n)
空间复杂度：O(1)

【2013统考真题】已如一个整数序列A=(a0,a1,...,an-1)，其中0≤ai≤n (0≤i≤n)。若存在ap1=ap2=...=apm=x 且 m＞n/2 (0≤pk≤n，l≤k≤m），則称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，則5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求： 1）给出算法的基本设计思想。 2）根据设计思想，来用C 或C++或Java语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度和空问复杂度。
【答案】：
1. 由于序列中的0≤ai≤n (0≤i≤n)，所以建立附属数组B[n+1]，进行存放每个数字出现的次数。并令建立一个变量记录目前频度最高的数。如果查找过程中发现，某个数的频度已经过半，则找到主元素。
2. ```
int B[n+1];
for(int i=0;i<n+1;i++)
  B[i]=0;
int current = 0;
int current_count = 0;
for(int i=0;i<n;i++){
  if(current_count>n/2) return current;
  if(++B[A[i]]>current_count) current=A[i];
}
if(current<=n/2) return -1;
```
3. 时间复杂度：O(n) 空间复杂度：O(n)
4. 更好的方法：https://www.bilibili.com/video/BV1aJ41177e9
【2018 統考真题】给定一个含n(n>1) 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4.要求： 1）给出算法的基本设计恩想。 2）根据设计思想，来用C 或C++语言描述算法，关键之处给出注释。 3）说明你所设计算法的时问复杂度和空问复杂度。
【答案】：
1. 构造一个大小为n的辅助数组，从头开始遍历数组，把正整数在辅助数组中标出。然后查看辅助数组，找出没出现过的最小正整数。
2. ```
int temp[n];
for(int i=0; i<n; i++)
  temp[i]=0;
for(int i=0; i<n; i++)
  if(A[i]>=0 && A[i]<n) temp[A[i]]++;
for(int i=0; i<n; i++)
  if(temp[i]==0) return i;
return n+1;
```
3. 时间复杂度：O(n) 空间复杂度：O(n)

【2020統考真题】定义三元组(a.b.c) (a、b、c均为正数）的距离D=|a-b|+|b-c|+|a-c|。给定3个非空整数集合 S1、S2,和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c) (a属于S1, b属于S2, c属于S3）中的最小距离。例如S1={-1,0,9},S2={-25,-10,10,11}，S3={2,9,17,30,41}，则最小距离为2，相应的三元组为(9,10,9)。要求： 1〕给出算法的基本设计思想 2）根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度和空间复杂度。

【答案】：

D=|a-b|+|b-c|+|a-c| = 2(max - min)。依次便利三个集合，找出三个数，然后更新三个数中最小的一个数。因为这样才有可能让距离下降，更新中间的不会改变距离，更新最大的只会让距离上升。


int abs(int a;int b)
  return a > b ? a-b : b-a;

int is_min(int a,int b,int c){
  return a<=b && a<=c;
}

int find(int &mini,int &minj, int &mink,int &min){
  int D;
  for(int i=0,j=0,k=0; i<p,j<q,k<r;){
    D = abs(a,b)+abs(b,c)+abs(a,c);
    if(D <min){
      mini = i;
      minj = j;
      mink = k;
      D = min;
    }
    if(is_min(a))  i++;
    else if(is_min(b)) j++;
    else  k++;
  }
}

时间复杂度：O(n) 空间复杂度：O(1)