顺序表的应用

2024-02-24 11:17:42

顺序表划分

将顺序表（a1，a2，……an）重新排列为以 a1 为界限的两部分，a1 前面的均比 a1 小，a1后面的值均比 a1 大，这一操作称为划分，a1 也称为基准。

算法思路：

从第二个元素开始向后扫描到最后一个元素。当前元素 ai 比 a1 小，将前面的元素依次向后移动，然后将 a1 放到第一个。ai 比 a1 大，则不动，继续比较下一个。

void ListPart(SeqList *L){
  int x,y;
  x=L->data[0]; /* 存储基准 */
  for (int i = 1; i < L->length; i++)
  {
    if (L->data[i]<x) /* 当前元素小于基准 */
    {
      y=L->data[i];
      for (int j = i-1; j >= 0; j--)  /* 移动 */
      {
        L->data[j+1] = L->data[j];
      }
      L->data[0] = y;
    }
  }
}

时间复杂度 O(n2)

顺序表的应用
#include "stdio.h"
#include <stdlib.h>
#define MAX 40

typedef struct LNode
{
  int data[MAX];
  int length;
}SeqList;

/* 显示顺序表 */
void displayList(SeqList *L){
  printf("\n链表C的内容：");
  for (int i = 0; i < L->length; i++)
  {
    printf("%d ",L->data[i]);
  }
  printf("\n");
}

/* 初始化顺序表 */
SeqList *CreatList(int *arr,int n){
  printf("------开始初始化------\n");
  SeqList *L;
  L=(SeqList *)malloc(sizeof(SeqList));
  for (int i = 0; i < n; i++){ /* 向data填入arr中的数据 */
    L->data[i] = arr[i];
    printf("%d ",L->data[i]);
  }
  L->length=n;
  printf("\n------初始化结束------\n");

  return L;
}

void ListPart(SeqList *L){
  int x,y;
  x=L->data[0]; /* 存储基准 */
  for (int i = 1; i < L->length; i++)
  {
    if (L->data[i]<x) /* 当前元素小于基准 */
    {
      y=L->data[i];
      for (int j = i-1; j >= 0; j--)  /* 移动 */
      {
        L->data[j+1] = L->data[j];
      }
      L->data[0] = y;
    }
  }
}

int main(){
  int arr1[]={72,6,8,12,66,98,75,33,78,54,1,3,10,102};
  SeqList *L = CreatList(arr1,sizeof(arr1)/4);/* 初始化顺序表填充数据arr1 */
  ListPart(L); /* 对arr1进行划分 */
  displayList(L); /* 显示划分后的arr1 */
}
顺序表划分完整代码

顺序表的合并

有顺序表 A 和 B，其元素均按从小到大的升序排列，编写一个算法将他们合并成一个新的顺序表 C，要求 C 的元素也是从小到大的升序排列。

算法思路：

依次扫描 A 和 B 的元素，比较当前元素的值，将较小值的元素赋值给 C，如此知道一个线性表扫描完毕

然后将未完的那个顺序表中余下的部分赋给 C。C的大小要能够容纳 A、B 两个线性表相加的长度

void ArrMerge(SeqList *A,SeqList *B, SeqList *C){
  int i,j,k;
  i=0;j=0;k=0;
  while (i<A->length && j<B->length)
  {
    if(A->data[i]<B->data[j])
      C->data[k++]=A->data[i++];
    else C->data[k++] = B->data[j++];
  }
  while (i<A->length)
  {
    C->data[k++] = A->data[i++];
  }
  while (j<B->length)
  {
    C->data[k++] = B->data[j++];
  }
  C->length=k;
}

 

时间复杂度：O(m+n)，m、n分别为 A、B 表长。

顺序表的应用
#include "stdio.h"
#include <stdlib.h>
#define MAX 40

typedef struct LNode
{
  int data[MAX];
  int length;
}SeqList;

/* 初始化顺序表 */
SeqList *CreatList(int *arr,int n){
  printf("------开始填充数据------\n");
  SeqList *L;
  L=(SeqList *)malloc(sizeof(SeqList));
  for (int i = 0; i < n; i++){ /* 向data填入arr中的数据 */
    L->data[i] = arr[i];
    printf("%d ",L->data[i]);
  }
  L->length=n;
  printf("\n------填充数据结束------\n");

  return L;
}

/* 冒泡排序 */
void SortArr(int *arr, int n){
  printf("------开始排序------\n");
  int temp;
  for (int i = 0; i < n-1; i++){
    for (int j = 0; j < n-1-i; j++){
      if (arr[j]>arr[j+1])
      {
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  for (int i = 0; i < n; i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\n------排序结束------\n");
}

/* 初始化 C 表 */
SeqList *ListInit(){
  SeqList *L;
  L=(SeqList *)malloc(sizeof(SeqList));
  L->length=0;
  return L;
}

/* 显示顺序表 */
void displayList(SeqList *L){
  printf("\n链表C的内容：");
  for (int i = 0; i < L->length; i++)
  {
    printf("%d ",L->data[i]);
  }
  printf("\n");
}

/* 合并顺序表 */
void ArrMerge(SeqList *A,SeqList *B, SeqList *C){
  int i,j,k;
  i=0;j=0;k=0;
  while (i<A->length && j<B->length)
  {
    if(A->data[i]<B->data[j])
      C->data[k++]=A->data[i++];
    else C->data[k++] = B->data[j++];
  }
  while (i<A->length)
  {
    C->data[k++] = A->data[i++];
  }
  while (j<B->length)
  {
    C->data[k++] = B->data[j++];
  }
  C->length=k;
}

int main(){
  /* 定义两个数组 */
  int arr1[]={6,8,12,66,98,75,33,78,54,1,3,10,102};
  int arr2[]={5,9,7,4,2};

  /* 数组排序 */
  SortArr(arr1,sizeof(arr1)/4);
  SortArr(arr2,sizeof(arr2)/4);

  /* 顺序表数组赋值 */
  SeqList *A = CreatList(arr1,sizeof(arr1)/4);
  SeqList *B = CreatList(arr2,sizeof(arr2)/4);
  SeqList *C = ListInit();
  ArrMerge(A,B,C); /* 合并数组 */
  displayList(C);

  system("pause");
}
顺序表的合并完整代码

 两个顺序表的比较

A、B 两个线性表，表厂分别为 m 和 n。A' 和 B' 分别为除去最大共同前缀的子表。

例如 A=（1，2，3，7，8），B=（1，2，3，4，5，6），两表共同前缀为（1，2，3）.

则 A' =(7，8)，B' =（4，5，6）。

如果 A' = B' = 空表，则 A = B；若A' = 空表 且 B' ≠ 空表，或者两者均不空且 A' 首元素小于 B' 首元素，则A < B；否则，A>B。

算法思路

首先找出 A、B 共同最大前缀，之后再按照规则进行比较，若 A=B，返回 0；若 A < B，返回 -1；若 A > B，返回1。

int ListCompare(SeqList *A, SeqList *B){
  int i,m,n,ms,ns; /* m、n为 A、B 长度，ms、ns 为 A' B'的长度*/
  i=0;ms=0;ns=0;
  m = A->length;
  n = B->length;
  while (i<m && i<n && A->data[i] == B->data[i]) i++; /* 找共同最大前缀 */
  ms = m-i; /* 求 A' 的长度 */
  ns = n-i; /* 求 B' 的长度 */
  if(ms==ns&&ns==0) return 0;
  else if(ms==0&&ns>0 || ms>0&&ns>0 &&A->data[i]<B->data[i]) return -1;
  else return 1;
}
顺序表的应用
#include "stdio.h"
#include "stdlib.h"
#define MAX 40 /* 定义数组最大长度 */

typedef struct LNode{
  int data[MAX];
  int length;
}SeqList;

SeqList *InitList(int *arr,int n){
  SeqList *L = (SeqList *)malloc(sizeof(SeqList));
  for (int i = 0; i < n; i++){
    L->data[i] = arr[i];  /* 数组赋值 */
    printf("%d ",L->data[i]);
  }
  L->length = n;
  printf("\n%d \n",L->length);
  return L;
}
/* 数组对比 */
int ListCompare(SeqList *A, SeqList *B){
  int i,m,n,ms,ns; /* m、n为 A、B 长度，ms、ns 为 A' B'的长度*/
  i=0;ms=0;ns=0;
  m = A->length;
  n = B->length;
  while (i<m && i<n && A->data[i] == B->data[i]) i++; /* 找共同最大前缀 */
  ms = m-i; /* 求 A' 的长度 */
  ns = n-i; /* 求 B' 的长度 */
  if(ms==ns&&ns==0) return 0;
  else if(ms==0&&ns>0 || ms>0&&ns>0 &&A->data[i]<B->data[i]) return -1;
  else return 1;
}

int main(){
  int ArrA[] = {72,6,8,12,66};
  int ArrB[] = {72,6,8,12,66,98,75,33,78,54,1};
  int lenB = sizeof(ArrB)/4;
  SeqList *ListA = InitList(ArrA,sizeof(ArrA)/4); /* 初始化顺序表 */
  SeqList *ListB = InitList(ArrB,sizeof(ArrB)/4); /* 初始化顺序表 */

  printf("\n%d",ListCompare(ListA,ListB));
}
顺序表比较完整代码

 

上一篇：【数据结构】动态顺序表


下一篇：编程基础(1) - 数据结构:顺序表示例代码