顺序表

顺序表是简单的一种线性结构，逻辑上相邻的数据在计算机中内的存储位置也是相邻的，可以快速定位第几个元素，中间允许有空值，插入、删除时需要移动大量元素。

顺序表的三个要素

  • 用elems记录存储位置的基地址。
  • 分配一段连续的存储空间size（可以存放的元素个数）。
  • 用length记录实际的元素个数，即顺序表的长度（现在实际存放的元素个数）。

图示

image-20211002221204434

代码实现

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#define MAX_SIZE 100

typedef int ElemsType;

typedef struct _SqList
{
	ElemsType* elems;
	int length;//长度
	int size;//容量
}SqList;

//初始化
bool initSqList(SqList &sqlist)
{
	sqlist.elems = new int[MAX_SIZE];
	if (!sqlist.elems)//开辟失败直接返回
	{
		return false;
	}
	sqlist.length = 0;
	sqlist.size = MAX_SIZE;
	return true;
}
//打印整个list
void printSqList(SqList &sqlist)
{
	for (int i = 0; i < sqlist.length; i++)
	{
		cout << sqlist.elems[i] << " ";
	}
	cout << endl;
}
//顺序表增加元素
bool addSqList(SqList& sqlist,int e)
{
	if (sqlist.length == sqlist.size)
	{
		return false;
	}
	sqlist.elems[sqlist.length] = e;
	sqlist.length++;
	return true;
}

//指定位置插入元素
bool insertSqList(SqList& sqlist,int index,int e)
{
	//合法性判断
	if (index < 0 || index >= sqlist.length)
	{
		return false;
	}
	if (sqlist.length == sqlist.size)
	{
		return false;
	}
	for (int j= sqlist.length-1; j >= index; j--)
	{
		sqlist.elems[j + 1] = sqlist.elems[j];
	}
	sqlist.elems[index] = e;
	sqlist.length++;
	return true;
}
//删除指定位置元素
bool deleteSqList(SqList& sqlist, int index)
{
	if (index < 0 || index >= sqlist.length)
	{
		return false;
	}
	if (index == sqlist.length)
	{
		sqlist.length--;
		return true;
	}
	for (int j = index; j < sqlist.length; j++)
	{
		sqlist.elems[j] = sqlist.elems[j + 1];
	}
	sqlist.length--;
	return true;
}
//销毁整个表
void destorySqList(SqList& sqlist)
{
	if (sqlist.elems)
	{
		delete[]sqlist.elems;
	}
	sqlist.length = 0;
	sqlist.size = 0; 
}

实际应用

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

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

为了防止某些恶意连接消耗系统资源，当某个客户端连接超时（在设定的一定时间内没有发送数据）时，服务器就需要关闭这些客户端的连接。

具体实现方案:

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

1
2
3
4
5
补充:
	求当前的时间戳
    time_t now;
    time(&now);
    cout << "当前时间戳:" << now << endl;

其结构体定义如下： 

1
2
3
4
typedef struct { 
	int fd; 
	time_t timeout; // 使用超时时刻的时间戳表示
}ConnTimeout;

2.服务器程序每隔一秒钟扫描一次所有的连接，检查是否超时，如果存在超时的 连接，就关闭连接，结束服务，同时将顺序表中的记录清除!

大致实现过程(相关接口并未实现)

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
static void checkTimeOut(TimeOutSqList& list,time_t now)
{
   int fd,i;
    cout<<"检查超时"<<endl;
    for(int i = 0 ; i  < list.length;i++)
    {
        if(list.emels[i].timeout > now)
        {
            continue;
        }
        //超时 清理
        fd = list.emels[i].fd;
        //关闭链接---模拟
        cout<<"关闭链接"<<ednl;
		listDelete(list,i);//注意顺序表会移动，注意漏删情况
        i--;
    }
}
int main(void)
{
    time_t now,end;
    time_t last_timeout;//每秒执行一次超时检测
    TimeOutSqList list;
    
    time(&now);
    end  = now+60;//就处理一分钟，60s后退出循环
    
    initList(list);
    //通过频率限制模块通过判断分析，增加恶意连接到顺序表中
    for(int i = 0;i< 10;i++)
    {
        ConnectTimeOut e;
        e.df = i;
        e.timeout = now + i *2;
		listAdd(list,e);
    }
    listPrint(list);
    
    do
    {
        //控制 1（几）秒钟做一次事情
        if(last_timeout + 0.999 < now)
        {
            checkTimeOut(list,now);	
            last_timeout = now;
		}
        Sleep(10);
        time(&now);//读取现在时间
	}while(end > now);
    
    
    return 0;
}

(理解顺序表在这其中的作用即可。)