顺序表
动态星空制作
#include <iostream>
#include <graphics.h>
#include <Windows.h>
using namespace std;#define MAX_START 100 //星星数
#define MAX_MARGIN 80 //随机地
#define WIN_WIDTH 640 //窗口宽
#define WIN_HEIGHT 480 //窗口高
#define T_NUM 2
#define RADIO 5 //半径
#define STEP 5 //步长
//设置乌龟图片
IMAGE TORIOSE[T_NUM];
//定义一个枚举表示星星的状态
enum StartStatus {up, //向上down, //向下right, //向右left, //向左all //一共
};//定义一个星星的结构体
struct START {int x; //x坐标int y; //y坐标enum StartStatus stat;//状态unsigned raduio;//半径int color; //颜色int step; //不长
};
struct START start[MAX_START];void moveStart(int i) {//if (start[i].stat = stop)return;setfillcolor(BLACK);solidcircle(start[i].x, start[i].y, start[i].raduio);if (start[i].stat == up) {start[i].y -= start[i].step;if (start[i].y<0) {start[i].y = WIN_HEIGHT-50;}}/*else if (start[i].stat == down) {start[i].y -= start[i].step;Sleep(0.001);}else if (start[i].stat ==right) {start[i].y -= start[i].step;Sleep(40);}else if (start[i].stat == left) {start[i].y -= start[i].step;Sleep(40);}*/setfillcolor(start[i].color);solidcircle(start[i].x, start[i].y, start[i].raduio);
}void initStart(int i) {if (i<0&&i>MAX_START) {//合法性检查cout << "数据错误" << endl;}start[i].x = rand() % WIN_WIDTH;start[i].y = rand() % WIN_HEIGHT - MAX_MARGIN;start[i].stat = up;// (enum StartStatus)(1 + rand() % all);start[i].raduio = 1+ rand() % RADIO;start[i].step = 1 + rand() % STEP;//1-5的随机数int color1 = rand()%255;//0-255int color2 = rand() % 255;int color3 = rand() % 255;start[i].color = RGB(color1, color2, color3);
}
void init() {bool quit = false;//初始化窗口initgraph(WIN_WIDTH, WIN_HEIGHT);for (int i = 0; i < MAX_START; i++) {initStart(i);}for (int i = 0; i < MAX_START; i++) {setfillcolor(start[i].color);solidcircle(start[i].x, start[i].y, start[i].raduio);}char name[128];for (int i = 0; i < T_NUM; i++) {sprintf_s(name, "t%d.png", i + 1);loadimage(&TORIOSE[i], name,40,40,true);}//放乌龟照片putimage(WIN_WIDTH / 2 - 60, WIN_HEIGHT-40, &TORIOSE[1]);putimage(WIN_WIDTH / 2 + 60, WIN_HEIGHT-40, &TORIOSE[0]);//while (quit==false) {for (int i = 0; i < MAX_START; i++) {moveStart(i);}Sleep(50);}
}int main(void) {init();system("pause");return 0;}
顺序表的引入
顺序表是简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以
快速定位第几个元素,中间不允许有空值,插入、删除时需要移动大量元素
顺序表的三个要素:
用 elems 记录存储位置的基地址分配一段连续的存储空间 size用 length 记录实际的元素个数,即顺序表的长度
结构体定义
#define MAX_SIZE 100struct _SqList{ElemType *elems; // 顺序表的基地址int length; // 顺序表的长度int size; // 顺序表总的空间大小}
初始化:
bool initList(SqList& L) {
L.elem = new int[MAX_SIZE];
if (!L.elem) {
std::cout << "初始化内存失败!" << std::endl;
return false;
}
L.length = 0;
L.size = MAX_SIZE;
return true;
}
顺序添加元素:
//添加元素
bool addList(SqList& L, int e) {
if (L.length == MAX_SIZE)return false;//超出内存了
L.elem[L.length] = e;
L.length++;
return true;
}
插入元素
bool inserList(SqList& L, int pos, int e) {
if (L.length > MAX_SIZE)return false;//判断内存满了没有
if (pos<0 || pos>L.length)return false;//对插入的位置进行合法判断
for (int i = L.length-1; i >=pos; i--) {
L.elem[i + 1] = L.elem[i];
}
L.elem[pos] = e;
L.length++;
return true;
}
删除元素
bool deleteList(SqList& L, int pos) {
if (pos < 0 && pos >= L.length)return false;//对删除的位置进行合法判断
if (pos == L.length - 1) {//如果是最后一个位置直接删除即可
L.length--;
return true;
}
for (int i = pos; i < L.length; i++) {
L.elem[i] = L.elem[i + 1];//中间删除的需要将后续元素依次推向前面
}
L.length--;
return true;
}
摧毁表
{
if (list.elem) {
delete[] list.elem;//释放存储空间
std::cout << "摧毁表成功" << std::endl;
}
list.length = 0;
list.size = 0;
}
#include <iostream>
#define MAX_SIZE 100/*struct Sql_list {int* elem; //元素的基地址int length; //顺序表的长度int size; //顺序表表示的总空间
};typedef struct Sql_list SqList;*/
typedef struct {int* elem; //元素的基地址int length; //顺序表的长度int size; //顺序表表示的总空间
}SqList;bool initList(SqList& L) {L.elem = new int[MAX_SIZE];if (!L.elem) {std::cout << "初始化内存失败!" << std::endl;return false;}L.length = 0;L.size = MAX_SIZE;return true;
}
void printList(SqList& L) {std::cout << "顺序表的长度: " << L.length << std::endl;std::cout << "顺序表的空间: " << L.size << std::endl;for (int i = 0; i < L.length; i++) {std::cout << L.elem[i] << " ";}
}//添加元素
bool addList(SqList& L, int e) {if (L.length == MAX_SIZE)return false;//超出内存了L.elem[L.length] = e;L.length++;return true;
}
//插入元素
bool inserList(SqList& L, int pos, int e) {if (L.length > MAX_SIZE)return false;//判断内存满了没有if (pos<0 || pos>L.length)return false;//对插入的位置进行合法判断for (int i = L.length-1; i >=pos; i--) {L.elem[i + 1] = L.elem[i];}L.elem[pos] = e;L.length++;return true;
}
//删除元素
bool deleteList(SqList& L, int pos) {if (pos < 0 && pos >= L.length)return false;//对删除的位置进行合法判断if (pos == L.length - 1) {//如果是最后一个位置直接删除即可L.length--;return true;}for (int i = pos; i < L.length; i++) {L.elem[i] = L.elem[i + 1];//中间删除的需要将后续元素依次推向前面}L.length--;return true;
}
int main(void) {SqList list;if (initList(list)) {std::cout << "初始化成功" << std::endl;}//添加元素int e,count;std::cout << "请输入需要添加的个数: " ;std::cin >> count;for (int i = 0; i < count; i++) {std::cout << "请输入元素: ";std::cin >> e;if (addList(list ,e)) {std::cout << "添加元素: " << e << "成功"<<std::endl;}else {std::cout << "添加元素: " << e << "失败" << std::endl;}}//打印顺序表printList(list);std::cout << std::endl;//插入元素int i;std::cout << "请输入你要插入的位置和元素:";std::cin >> i >> e;if (inserList(list,i,e)) {std::cout << "插入元素: " << e << "成功" << std::endl;}else {std::cout << "插入元素: " << e << "失败" << std::endl;}//打印顺序表printList(list);std::cout << std::endl;std::cout << "请输入你需要删除的元素的位置:";std::cin >> i;if (deleteList(list,i)) {std::cout << "删除成功" << std::endl;}else {std::cout << "删除失败" << std::endl;}//打印顺序表printList(list);std::cout << std::endl;{if (list.elem) {delete[] list.elem;//释放存储空间std::cout << "摧毁表成功" << std::endl;}list.length = 0;list.size = 0;}return 0;
}
使用顺序表优化星空图
当星星离开边界之后依次删除星星在顺序表中的位置
顺序表的设计
#include <iostream>
#include "star.h"
using namespace std;
bool initList(SqList& L) {L.elems = new struct STAR[MAX_STAR];if (!L.elems) return false;L.length = 0;L.size = MAX_STAR;return true;
}
bool listAppend(SqList& L, struct STAR e) {if (L.length == L.size) return false; //存储空间已满L.elems[L.length] = e;L.length++; //表长加 1return 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;
}
void listPrint(SqList& L) {cout << "顺序表容量 size: " << L.size << ", 已保存元素的个数 length: "<<L.length<<endl;for (int i = 0; i < L.length; i++) {cout << "第" << i + 1 << " 颗星星: x=" << L.elems[i].x << ", y = "<<L.elems[i].y<<", radius = "<<L.elems[i].radius<<endl;}cout << endl;
}
头文件
#ifndef _STAR_H__
#define _STAR_H__
#define MAX_STAR 100
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define MAX_STEP 5
#define MAX_RADIUS 3
#define BOTTOM_MARGIN 100
//星星状态
enum STATUS {STOP = 0,UP,DOWN,LEFT,RIGHT,RANDOM,ALL_STATUS
};
struct STAR {int x; //星星的 x 坐标int y; //星星的 y 坐标enum STATUS stat; //状态unsigned radius; //星星的半径int step; //每次跳跃的间隔int color; //星星的颜色
};
typedef struct {struct STAR* elems; // 顺序表的基地址int length; // 顺序表的长度int size; // 顺序表的空间
}SqList;
//顺序表的接口
bool initList(SqList& L);
bool listAppend(SqList& L, struct STAR e);
bool listDelete(SqList& L, int i);
void destroyList(SqList& L);
#endif
实现文件
#include <graphics.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include "star.h"
using namespace std;
void MoveStar(SqList& L, int i) {if (L.elems[i].stat == STOP) return;//擦除原来的星星setfillcolor(BLACK);solidcircle(L.elems[i].x, L.elems[i].y, L.elems[i].radius);if (L.elems[i].stat == DOWN) {L.elems[i].y = L.elems[i].y + L.elems[i].step;if (L.elems[i].y > SCREEN_HEIGHT) listDelete(L, i);}else if (L.elems[i].stat == UP) {L.elems[i].y -= L.elems[i].step;if (L.elems[i].y < 0) listDelete(L, i);}else if (L.elems[i].stat == LEFT) {L.elems[i].x -= L.elems[i].step;if (L.elems[i].x < 0) listDelete(L, i);}else if (L.elems[i].stat == RIGHT) {L.elems[i].x += L.elems[i].step;if (L.elems[i].x > SCREEN_WIDTH) listDelete(L, i);}setfillcolor(L.elems[i].color);solidcircle(L.elems[i].x, L.elems[i].y, L.elems[i].radius);
}
/************************************
* 功能:初始化星星
* 输入参数:
* i - 星星在全局数组中的下标
* 返回值:无
************************************/
void initStar(struct STAR& _star) {int rgb = 0;//rand() 得到随机数范围 0 - 32767 RAND_MAX_star.x = rand() % SCREEN_WIDTH; // x 范围 0 -639_star.y = rand() % (SCREEN_HEIGHT - BOTTOM_MARGIN);// y 范围 0 - 379_star.stat = UP;_star.radius = 1 + rand() % MAX_RADIUS; //半径控制 1 - 3_star.step = rand() % MAX_STEP + 1; //步长 1 - 5rgb = 255 * _star.step / MAX_STEP; // 0 - 255_star.color = RGB(rgb, rgb, rgb);
}
int main() {bool quit = false;struct STAR star;SqList starList;//初始化保存星星状态的顺序表initList(starList);initgraph(SCREEN_WIDTH, SCREEN_HEIGHT);for (int i = 0; i < MAX_STAR; i++) {initStar(star);listAppend(starList, star);}for (int i = 0; i < starList.length; i++) {setfillcolor(starList.elems[i].color);solidcircle(starList.elems[i].x, starList.elems[i].y,starList.elems[i].radius);}IMAGE TORIOSE[2];//王八图片char name[128];for (int i = 0; i < 2; i++) {sprintf_s(name, "t%d.png", i + 1);loadimage(&TORIOSE[i], name,40,40,true);}//放乌龟照片putimage(SCREEN_WIDTH / 2 - 30, SCREEN_WIDTH -40, &TORIOSE[1]);putimage(SCREEN_HEIGHT / 2 + 30, SCREEN_HEIGHT -40, &TORIOSE[0]);while (quit == false) {for (int i = 0; i < starList.length; i++) {MoveStar(starList, i);}/*if(isQuit()){quit = true;}*/if (starList.length == 0) {quit = true;}Sleep(50);}system("pause");closegraph();return 0;
}
顺序表在高并发服务器的时间戳应用
头文件
#pragma once
#include <time.h>
#include <iostream>
#define MAX_SIZE 100
typedef struct {int fd;time_t timeout;
}ConnectTimeout;typedef struct {ConnectTimeout* e;int length;int size;
}SqListTimeout;bool initList(SqListTimeout& L);
bool insertList(SqListTimeout& L,int i, ConnectTimeout e);
bool deleteList(SqListTimeout& L, int pos);
void printList(SqListTimeout& L);
.cpp文件
#include "timeList.h"
using namespace std;
bool initList(SqListTimeout& L) {L.e = new ConnectTimeout[MAX_SIZE];if (!L.e) {cout << "初始化顺序表失败" << endl;return false;}L.length = 0;L.size = MAX_SIZE;
}
bool insertList(SqListTimeout& L,int i, ConnectTimeout e) {if (L.length<0||L.length>MAX_SIZE) {return false;}L.e[i] = e;L.length++;return true;
}
bool deleteList(SqListTimeout &L,int pos){if (pos<0 || pos>MAX_SIZE)return false;if (pos==L.length-1) {L.length--; return true;}for (int i = pos; i < L.length; i++) {L.e[i] = L.e[i + 1];}L.length--;return true;
}
void printList(SqListTimeout& L) {for (int i = 0; i < L.length; i++) {cout << L.e[i].fd << " " << L.e[i].timeout << endl;;}
}
实现文件
#include "timeList.h"
#include "Windows.h"
using namespace std;
void checkTimeout(SqListTimeout &L, time_t now) {int fd ,i;cout << "正在检查超时fd...."<<endl;for (i = 0; i < L.length; i++) {if (L.e->timeout > now) {//超时值大于现在的时间就还没有超时continue;}fd = L.e[i].fd;cout << "fd[" << fd << "]已经超时, 正在清理..." << endl;deleteList(L, i);i--;//复位}}
int main(void) {SqListTimeout list;time_t now ,end;time_t timeout;time(&now);end = now + 60;//60s后退出循环timeout = now;initList(list);for (int i = 0; i < 10; i++) {ConnectTimeout e;e.fd = i;e.timeout = now + 5 + 2 * i;insertList(list, i, e);}printList(list);do {if (timeout+0.999<now) {checkTimeout(list, now);timeout = now;}Sleep(10);time(&now);} while (end>now);
}