精选文章

Android下使用TCPDUMP抓包Wireshark分析数据 如果想分析Android下某个APP的网络数据交互,需要在Android手机上抓包,最常用的抓包工具非tcpdump莫属,用tcpdump生成Wireshark识别的pcap文件,然后将pcap文件下载到电脑上,用电脑上的Wireshark加载pcap文件,通过Wireshark分析tcpdump抓取的数据。...

继续阅读

Mac下部署Android开发环境附加NDK 作为开发者,我们深有体会,不管是进行什么开发,为了部署开发环境,我们往往需要折腾很长时间、查阅很多资料才能完成,而且这次折腾完了,下次到了另一台新电脑上又得重新来过,整个部署过程记得还好,要是不记得又得重新开始,而且遇到Android这种GFW阻隔了开发资源下载链接的环境部署,又尤其浪费时间。所以这也是我写下这篇教程的初衷跟动力源泉,希望大家参考了这篇教程以后可以轻轻松松在Mac系统下将Android环境部署好。...

继续阅读

稍顯嚴肅的台中 坦白說,留在腦海中的台中影像並不多,來台灣之前在Booking上只訂到了台中的一家青旅,第一次住青旅有些不習慣,幹什麼都放不開。 同屋的一個男生是台灣人,不過一年中四分之三的時間在上海跟北京,這麼說來跟我還是比較有共同話題的。得之我準備花15天的時間環島,覺得太倉促了,他們大學時期花一個半月的時間也不見得能將台灣島給逛完。我只能無奈地表示,兩岸允許的簽證時間有限,自己的空閒時間更有限,只能用打卡式的旅行了,我深知正真地旅行應該慢下來,融入當地的環境,感受他們的風土人情,但第一次只能這樣作罷,以後換成民進黨上台,形勢會變成怎樣還不得而知,能否再過來還是個未知數。而我一向信奉的人生格言是秉燭夜遊,活在當下,所以,理解自己吧。...

继续阅读

為之留戀的新竹 來新竹之前本沒有對她有過高的期待,慢慢對她加分要從桃園火車站出發前往新竹開始。 在桃園火車站的候車月台上,有醒目的旅遊資料發放處,這上面的擺放的全是新竹的旅遊宣傳資料,關鍵的是資料做得非常簡潔易懂,而接下來一天的新竹之行就全部是依據這份寶典的指引來完成的。...

继续阅读

從桃園開始台灣之行 初到台灣恰逢華夏銀行系統升級,特意準備的華夏銀聯卡在桃園機場沒能派上用場,只好用建行在機場5000塊,算下來是很不划算的,但是沒辦法,誰叫我出機場就得花錢呢。 從機場打車到桃園的酒店,花了將近六百塊新台幣,到酒店時五點多,天已經漸亮了,洗漱完等到七點吃過早餐就開始補覺囉,一覺醒來已是中午,帶著換下來的衣服外出找自助洗衣店,順便覓食。...

继续阅读

  • Prev
  • Next

队列及其应用实例

文章分类 : C语言, 应用与编程, 数据结构

1、和栈相反,队列是一种先进先出(first in first out,缩写为FIFO)的线性表,它只允许在表的一端插入,在表的另一端删除元素。其中允许插入的一段称为队尾,允许删除的一端则称为对头。

2、用链表表示的队列称为链队列,一个链队列显然需要两个分别表示对头和队尾的指针(分别称为头指针跟尾指针)才能唯一确定。为了操作方便起见,我们也给链队列添加一个头结点,并令头指针指向头结点,由此,判断链队列为空的等价条件便是头指针跟尾指针均指向了头结点。

3、下面是链队列的存储表示以及基本操作的C语言算法描述伪代码:    

typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr; //队列结点
typedef struct {
    QueuePtr front; //对头指针
    QueuePtr rear; //队尾指针
}LinkQueue;

Status InitQueue(LinkQueue &CppLive)
{
    //构造一个空队列CppLive
    CppLive.front = CppLive.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!CppLive.front) exit(OVERFLOW);
    CppLive.front->next = NULL;
    return OK;
}
Status DestoryQueue(LinkQueue &CppLive)
{
    //销毁队列CppLive
    while (CppLive.front)
    {
        CppLive.rear = CppLive.front->next;
        free(CppLive.front);
        CppLive.front = CppLive.rear;
    }
    return OK;
}
Status EnQueue(LinkQueue &CppLive, QElemType e)
{
    //插入元素e为CppLive的新的队尾元素
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    CppLive.rear ->next = p;
    CppLive.rear = p;
    return OK;
}
Status DeQueue(LinkQueue &CppLive, QElemType &e)
{
    //若队列不空,则删除Q的队列头元素,用e返回其值,并返回OK
    //否则返回ERROR
    if (CppLive.front == CppLive.rear) return ERROR;
    p = CppLive.front->next;
    e = p->data;
    CppLive.front->next = p->next;
    if (CppLive.rear == p) CppLive.rear = CppLive.front;
    free(p);
    return OK;
}

4、和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,还需要附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。但是这种顺序表示的队列如果依靠纯粹的累加来实现入队出队,那样很可能出现数组越界的情况,但事实是数组中某些已经出队的区域仍然空闲而没法再利用,于是为了合理利用存储空间来实现顺序存储的队列,我们引入了循环队列这一概念。

5、判断循环队列空间是“空”还是“满”,有两种处理方式:其一是另设一个标志位一区别队列是否已满;其二是少用一个元素空间,约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。

6、若用户无法预估所用队列的最大长度,则不要采用循环队列,而宜采用链队列。

7、下面是循环队列的存储表示以及基本操作的C语言算法描述伪代码:

#define MAXQSIZE 100 //最大队列长度
typedef struct {
    QElemType *base; //初始化的动态分配存储空间
    int front; //头指针,若队列不空,指向队列头元素
    int rear; //尾指针,若队列不空,指向队列尾元素的下一位置
}SqQueue;
Status InitQueue(SqQueue &CppLive)
{
    //构造一个空队列
    CppLive.base = (QElemType *)malloc(MAXQSIZE * szieof(QElemType));
    if (!CppLive.base) exit(OVERFLOW); //存储分配失败
    CppLive.front = CppLive.rear = 0;
    return OK;
}
int QueueLength(SqQueue CppLive)
{
    //返回CppLive的元素个数,即队列的长度
    return (CppLive.rear - CppLive.front + MAXQSIZE) % MAXQSIZE;
}
Status EnQueue(SqQueue &CppLive, QElemType e)
{
    //插入元素e为CppLive的新的队尾元素
    if ((CppLive.rear + 1) % MAXQSIZE == CppLive.front) return ERROR; //队列满
    CppLive.base[CppLive.rear] = e;
    CppLive.rear = (CppLive.rear + 1) % MAXQSIZE;
    return OK;
}
Status DeQueue(SqQueue &CppLive, QElemType &e)
{
    //若队列不空,则删除Q的对头元素,用e返回其值,并返回OK
    //否则返回ERROR
    if (CppLive.front == CppLive.rear) return ERROR;
    e = CppLive.base[CppLive.front];
    CppLive.front = (CppLive.front + 1) % MAXQSIZE;
    return OK;
}

除非注明,文章均为CppLive 编程在线原创,转载请注明出处,谢谢。

本文地址:https://www.cpplive.com/html/1346.html

这里因为你的留言而存在!!!

You must be logged in to post a comment.