数据结构——顺序表-阿里云开发者社区

顺序表的原理

顺序表是简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以

快速定位第几个元素，中间不允许有空值，插入、删除时需要移动大量元素。

顺序表的三个要素：

 用 elems 记录存储位置的基地址

 分配一段连续的存储空间 size

 用 length 记录实际的元素个数，即顺序表的长度

结构体定义

#define MAX_SIZE 100 struct _SqList{

ElemType *elems; // 顺序表的基地址

int length; // 顺序表的长度

int size; // 顺序表总的空间大小

}

顺序表的算法实现（顺序表的初始化）

#define MAX_SIZE 100
typedef struct{
int *elems; // 顺序表的基地址 int length; // 顺序表的长度 int size;  // 顺序表的空间
}SqList;
bool initList(SqList &L) //构造一个空的顺序表L
{
L.elems=new int[MAX_SIZE];        //为顺序表分配Maxsize个空间
if(!L.elems) return false; //存储分配失败
L.length=0;                     //空表长度为0
L.size = MAX_SIZE; return true;
}

顺序表增加元素

bool listAppend(SqList &L, int e)
{ if(L.length==MAX_SIZE) return false; //存储空间已满
L.elems[L.length] = e;
L.length++;                 //表长增1
return true;
}

顺序表插入元素

bool listInsert(SqList &L,int i, int e)
{ if(i<0 || i>=L.length)return false; //i值不合法 if(L.length==MAX_SIZE) return false; //存储空间已满
for(int j=L.length-1; j>=i; j--){
L.elems[j+1]=L.elems[j];//从最后一个元素开始后移，直到第i个元素后移
}
L.elems[i]=e; //将新元素e放入第i个位置 L.length++; //表长增1
return true;
}

顺序表删除元素

bool listDelete(SqList &L,int i)
{ if(i<0 || i>=L.length) return false; //不合法
if(i == L.length-1){//删除最后一个元素，直接删除
L.length--; return true;
}
for (int j=i; j<L.length-1; j++){
L.elems[j] =L.elems[j+1]; //被删除元素之后的元素前移
}
L.length--; return true;
}

顺序表销毁

void destroyList(SqList &L)
{ if (L.elems) delete []L.elems;//释放存储空间
L.length = 0;
L.size = 0; }

完整代码实现

#include <iostream>
#include <Windows.h>
using namespace std;
#define MAX_SIZE  100
typedef struct
{
  int* elems;
  int length;
  int size;
}SqList;
bool initList(SqList& L)
{
  L.elems = new int[MAX_SIZE];
  if (!L.elems)
  {
    return false;
  }
  L.size = MAX_SIZE;
  L.length = 0;
  return true;
}
bool AppendList(SqList& L, int z)
{
  if (L.length == L.size)
  {
    return false;
  }
  L.elems[L.length] = z;
  L.length += 1;
  return true;
}
bool insertList(SqList& L, int z, int i)
{
  if (L.length == L.size || i<0)
  {
    return false;
  }
  //插入的数在顺序表末尾
  if (L.length - 1 == i)
  {
    L.elems[L.length] = z;
    L.length += 1;
    return true;
  }
  //插入的数没在顺序表末尾
  for (int j = L.length - 1; i <= j; j--)
  {
    L.elems[j + 1] = L.elems[j];
  }
  L.elems[i] = z;
  L.length += 1;
  return true;
}
bool deleteList(SqList& L, int z, int i)
{
  if (L.elems==NULL)
  {
    cout << "数据为空！" << endl;
    return false;
  }
  for (int j = i; j <= L.length-2 ; j++)
  {
    L.elems[j] = L.elems[j + 1];
  }
  L.length = L.length - 1;
  return true;
}
bool destroyList(SqList& L)
{
  if (L.elems)
  {
    delete[]L.elems;
  }
  L.length = 0;
  L.size = 0;
  return true;
}
void printList(SqList& L)
{
  cout << "数据有：" << endl;
  for (int i = 0; i < L.length; i++)
  {
    cout << L.elems[i] << " ";
  }
}
int main1(void)
{
  SqList list;
  int x = 0;
  //初始化顺序表
  initList(list);
  //追加数据
  for (int i = 0; i < 10; i++)
  {
    AppendList(list, i);
  }
  printList(list);
  cout << endl;
  cout << "请输入你要插入的数据和对应位置：";
  insertList(list, 9, 3);
  printList(list);
  cout << "请输入你要删除的数据和对应位置：";
  deleteList(list, 9, 3);
  printList(list);
  //销毁顺序表
  cout << "请销毁顺序表：";
  destroyList(list);
  system("pause");
  return 0;
}

顺序表的企业级应用案例：

高并发 WEB 服务器中顺序表的应用

高性能的 web 服务器 Squid 每秒可处理上万并发的请求，从网络连接到服务器的客户端与服务器端在交互时会保持一种会话（和电话通话的场景类似）。服务器端为了管理好所有的客户端连接，给每个连接都编了一个唯一的整数编号，叫做文件句柄，简称 fd.

为了防止某些恶意连接消耗系统资源，当某个客户端连接超时（在设定的一定时

间内没有发送数据）时，服务器就需要关闭这些客户端的连接具体

实现方案：

1. 当有新的请求连到服务器时，如果经过服务器频率限制模块判断，貌似恶意连接，则使用顺序表来保存此连接的超时数据，超时值使用时间戳来表示,时间戳是指格林威治时间 1970 年 01 月 01 日 00 时 00 分 00 秒(相当于北京时间 1970 年 01 月 01 日

08 时 00 分 00 秒)起至现在的总秒数，其结构体定义如下：

typedef struct {

int fd ;

time_t timeout; // 使用超时时刻的时间戳表示

}ConnTimeout;

2. 服务器程序每隔一秒钟扫描一次所有的连接，检查是否超时，如果存在超时的

连接，就关闭连接，结束服务，同时将顺序表中的记录清除！

代码如下：

webServer.cpp

#include <iostream>
#include <time.h>
#include <Windows.h>
#include "webServer.h"
using namespace std;
static void checkTimeouts(TimeoutSqList& list, time_t now);
int main(void)
{
  time_t now, end;
  time_t last_timeout;
  TimeoutSqList list;
  time(&now);
  end = now + 60;
  last_timeout = now;
  initList(list);
  //1.模拟频率限制模块通过判断分析，增加恶意连接到顺序表中
  for (int i = 0; i < 10; i++)
  {
    ConnTimeout e;
    e.fd = i;
    e.timeout = now + 5 + 2 * i; 
    AppendList(list, e);
  }
  printList(list);
  do
  {
    if (last_timeout + 0.999 < now)
    {
      checkTimeouts(list, now);//检查超时的连接
      last_timeout = now;
    }
    Sleep(10);//防止cpu空转
    time(&now);
  } while (now < end);
  /*time_t now;
  time(&now);
  cout << "当前的时间戳 - timestamp:" << now << endl;
  Sleep(2000);
  time(&now);
  cout << "两秒以后的时间戳 - timestamp:" << now << endl;*/
  system("pause");
  return 0;
}
void checkTimeouts(TimeoutSqList& list, time_t now)
{
  int fd, i;
  cout << "检查超时fd……\n";
  for (i = 0; i < list.length; i++)
  {
    if (list.elems[i].timeout > now)
    {
      continue;
    }
    //超时，清理连接
    fd = list.elems[i].fd;
    //关闭连接
    printf("连接[fd=%d] 已经超时，关闭连接!\n", fd);
    //删除顺序表中的元素
    i--;
    deleteList(list, i);
  }
}

TimeoutSqList.cpp

#include "webServer.h"
#include <iostream>
#include <Windows.h>
using namespace std;
bool initList(TimeoutSqList& L)
{
  L.elems = new ConnTimeout[MAX_SIZE];
  if (!L.elems)
  {
    return false;
  }
  L.size = MAX_SIZE;
  L.length = 0;
  return true;
}
bool AppendList(TimeoutSqList& L, ConnTimeout z)
{
  if (L.length == L.size)
  {
    return false;
  }
  L.elems[L.length] = z;
  L.length += 1;
  return true;
}
bool insertList(TimeoutSqList& L, ConnTimeout z, int i)
{
  if (L.length == L.size || i < 0)
  {
    return false;
  }
  //插入的数在顺序表末尾
  if (L.length - 1 == i)
  {
    L.elems[L.length] = z;
    L.length += 1;
    return true;
  }
  //插入的数没在顺序表末尾
  for (int j = L.length - 1; i <= j; j--)
  {
    L.elems[j + 1] = L.elems[j];
  }
  L.elems[i] = z;
  L.length += 1;
  return true;
}
bool deleteList(TimeoutSqList& L, int i)
{
  if (L.elems == NULL)
  {
    cout << "数据为空！" << endl;
    return false;
  }
  for (int j = i; j <= L.length - 2; j++)
  {
    L.elems[j] = L.elems[j + 1];
  }
  L.length = L.length - 1;
  return true;
}
bool destroyList(TimeoutSqList& L)
{
  if (L.elems)
  {
    delete[]L.elems;
  }
  L.length = 0;
  L.size = 0;
  return true;
}
void printList(TimeoutSqList& L)
{
  cout << "当前：" << L.size << "，已保存元素的个数 length：" << L.length << endl;
  for (int i = 0; i < L.length; i++)
  {
    cout << "fd：" << L.elems[i].fd << "，timeout：" << L.elems[i].timeout << endl;
  }
}

webServer.h

#ifndef _WEB_SERVER_H_
#define _WEB_SERVER_H_
#include <time.h>
#define MAX_SIZE 100
typedef struct
{
  int fd;
  time_t timeout;//使用超时时刻的时间戳表示
}ConnTimeout;
typedef struct
{
  ConnTimeout* elems; //顺序表的基地址
  int length;     //顺序表的长度
  int size;     //顺序表的大小
}TimeoutSqList;
//顺序表的接口
bool initList(TimeoutSqList& L);
bool AppendList(TimeoutSqList& L, ConnTimeout z);
bool deleteList(TimeoutSqList& L, int i);
bool destroyList(TimeoutSqList& L);
void printList(TimeoutSqList& L);
#endif

数据结构——顺序表