當前位置:首頁 » 服務存儲 » 鏈隊列存儲結構的定義
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

鏈隊列存儲結構的定義

發布時間: 2022-06-19 00:14:02

Ⅰ 隊列鏈式存儲結構的表示。 想問一下,這里分兩部分,是要先定義鏈表,再定義隊列嗎 還有就是每部分最

定義順序無所謂,但是因為隊列中有用到那個鏈表結構體類型,所以,如果定義隊列在前的話,要在隊列前先聲明鏈表。後面那些是結構體的名稱和指向結構體的指針,看到前面的typedef了嗎

Ⅱ 怎麼定義隊列的結構體!!!!

struct MyStruct{

// blabla...
}

queue ps; // OK 隊列中每個元素都是一個結構體,和基本類型int等一樣的用法,但是使用中會用到MyStruct的【拷貝構造】和【賦值運算符】,當MyStruct中存在指針變數時就需要非常小心避免出現野指針。
queue pps; // OK 隊列中每個元素都是一個指針,指針實際指向的結構體空間的分配與釋放都需要程序員進行維護。

Ⅲ 鏈式隊列存儲結構的定義及基本操作

鏈式隊列其實很簡單的。
其實就是一個鏈表,不過這個鏈表你只能從表尾插入,從表頭刪除。(單向隊列)
鏈表你肯定會吧,定義兩個指針,分別指向表頭和表尾,作為隊頭指針和隊尾指針。封裝起來。
這就是一個鏈式隊列了。
基本操作無非是入隊,出隊,刪除這些,跟基本鏈表操作一樣的。

Ⅳ @數據結構大神,鏈隊列的存儲結構,這里加struct幹啥求解釋

C語言要求使用結構體類型時,必須加struct關鍵字! 除非進行了宏定義(define)或是類型重定義(typedef)
然而,C++可以直接使用結構體名來進行變數定義。

Ⅳ 鏈式存儲隊列的數據結構(邏輯結構+存儲結構)分析、鏈式存儲隊列的基本C語言結構體分析與定義

鏈式隊列

鏈式存儲結構的隊列稱作鏈式隊列。

鏈式隊列的隊頭指針指在隊列的當前隊頭結點位置,隊尾指針指在隊列的當前隊尾結點位置。不帶頭結點的鏈式隊列時可直接刪除隊頭指針所指的結點。

鏈式隊列中結點的結構體可定義如下:

typedef struct qnode

{

DataType datal;

Struct qnode *next;

}LQNode;

為了方便參數調用,通常把鏈式隊列的隊頭指針front和隊尾指針rear也定義為如下的結構體類型LQueue:

typedef struct

{

LQNode *front;

LQNode *rear;

}LQueue;

鏈式隊列操作的實現

(1) 初始化QueueInitiate(LQueue *Q)

void QueueInitiate(LQueue *Q)

{

Q->rear=NULL;

Q->front=NULL;

}

(2)非空否QueueNotEmpty(LQueue Q)

int QueueNotEmpty(LQueue Q)

/*判斷鏈式隊列Q非空否,非空返回1,否則返回0*/

{

if(Q.front==NULL)return 0;

else return 1;

}

(3)入隊列QueueAppend(LQueue *Q,DataType x)

int QueueAppend(LQueue *Q,DataType x)

/*把數據元素x插入鏈式隊列Q隊列的隊尾,入隊列成功返回1,否則返回0*/

{

LQNode *p;

if((p=(LQNode*)malloc(sizeof(LQNode)))==NULL)

{

printf(「內存不足無法插入!\n);

return 0;

}

p->data=x;

p->next=NULL;

if(Q->rear!=NULL)Q->rear->next=p;

Q->rear=p;

if(Q->front==NULL)Q->front=p;

return 1;

}

(4)出隊列QueueDelete(LQueue *Q,DataType *d)

int QueueDelete(LQueue *Q,DataType *d)

/*刪除鏈式隊列Q的隊頭數據元素值到d,出隊列成功返回1,否則返回0*/

{

LQNode *p;

if(Q->front==NULL)

{

printf(「隊列已空無數據元素出隊列!\n」);

return 0;

}

else

{

*d=Q->front->data;

p=Q->front;

Q->front=Q->front->next;

if(Q->front==NULL)Q->rear=NULL;

free(p);

return 1;

}

}

(5)取隊頭數據元素QueueGet(LQueue *Q,DataType *d)

int QueueGet(LQueue *Q,DataType *d)

/*取鏈式隊列Q的當前隊頭數據元素值到d,成功返回1,否則返回0*/

{

if(Q.front==NULL)

{

printf(「隊列已空無數據元素出隊列!\n);

return 0;

}

else

{

*d=Q.front->data;

return 1;

}

}

(6)撤銷動態申請空間Destory(LQueue *head)

int Destory(LQueue *head)

{

LQNode *p,*p1;

p=Q.front;

while(p!=NULL)

{

p1=p;

p=p->next;

free(p1);

}

}
幫你轉的,我覺得他描述的很清楚。希望對你有幫助。

Ⅵ 試述隊列的鏈式存儲結構和順序存儲結構的優缺點

順序存儲結構是在內存中開辟一個連續的空間用來存儲數據,因此對於內存的需求和苛刻,必須是連續的空間.在數據查找(特別是不按照規律排列的數據),時間復雜度教少.效率高.
鏈式存儲結構是採取連表指針來指示數據的存儲位置,這就可以是在內存中隨意的存儲,沒有必須連續儲存空間的要求,對於內存的要求相對教容易.但是要是是從小到大順序排列的數據,鏈式存儲結構的時間復雜度教小,效率高.但是要是不規則排布的數據一般時間復雜度較高,效率更低

Ⅶ 求救:棧和隊列在程序設計中的作用

棧和隊列是兩種特殊的線性表,它們的邏輯結構和線性表相同,只是其運算規則較線性表有更多的限制,

故又稱它們為運算受限的線性表。棧和隊列被廣泛應用於各種程序設計中。

棧的定義及基本運算

1、棧的定義

棧(Stack)是限制僅在表的一端進行插入和刪除運算的線性表。

(1)通常稱插入、刪除的這一端為棧頂(Top),另一端稱為棧底(Bottom)。

(2)當表中沒有元素時稱為空棧。

(3)棧為後進先出(Last In First Out)的線性表,簡稱為LIFO 表。

棧的修改是按後進先出的原則進行。每次刪除(退棧)的總是當前棧中"最新"的元素,即最後插入

(進棧)的元素,而最先插入的是被放在棧的底部,要到最後才能刪除。

【示例】元素是以a1,a2,…,an 的順序進棧,退棧的次序卻是an,an-1,…,a1。

2、棧的基本運算

(1)InitStack(S)

構造一個空棧S。

(2)StackEmpty(S)

判棧空。若S 為空棧,則返回TRUE,否則返回FALSE。

(3)StackFull(S)

判棧滿。若S 為滿棧,則返回TRUE,否則返回FALSE。

注意:

該運算只適用於棧的順序存儲結構。

(4)Push(S,x)

進棧。若棧S 不滿,則將元素x 插入S 的棧頂。

(5)Pop(S)

退棧。若棧S 非空,則將S 的棧頂元素刪去,並返回該元素。

(6)StackTop(S)

取棧頂元素。若棧S 非空,則返回棧頂元素,但不改變棧的狀態。

順序棧

棧的順序存儲結構簡稱為順序棧,它是運算受限的順序表。

1、順序棧的類型定義

#define StackSize 100 //假定預分配的棧空間最多為100 個元素

typedef char DataType;//假定棧元素的數據類型為字元

typedef struct{

DataType data[StackSize];

int top;

}SeqStack;

注意:

①順序棧中元素用向量存放

②棧底位置是固定不變的,可設置在向量兩端的任意一個端點

③棧頂位置是隨著進棧和退棧操作而變化的,用一個整型量top(通常稱top 為棧頂指針)來指示

當前棧頂位置

2、順序棧的基本操作

前提條件:

設S 是SeqStack 類型的指針變數。若棧底位置在向量的低端,即S->data[0]是棧底元素。

(1) 進棧操作

進棧時,需要將S->top 加1

注意:

①S->top==StackSize-1 表示棧滿

②"上溢"現象--當棧滿時,再做進棧運算產生空間溢出的現象。

上溢是一種出錯狀態,應設法避免。

(2) 退棧操作

退棧時,需將S->top 減1

注意:

①S->top<0 表示空棧

②"下溢"現象——當棧空時,做退棧運算產生的溢出現象。

下溢是正常現象,常用作程序控制轉移的條件。

順序棧在進棧和退棧操作時的具體變化情況【參見動畫演示】

3、順序棧的基本運算

(1) 置棧空

void InitStack(SeqStack *S)

{//將順序棧置空

S->top=-1;

}

(2) 判棧空

int StackEmpty(SeqStack *S)

{

return S->top==-1;

}

(3) 判棧滿

int StackFull(SeqStack *SS)

{

return S->top==StackSize-1;

}

(4) 進棧

void Push(S,x)

{

if (StackFull(S))

Error("Stack overflow"); //上溢,退出運行

S->data[++S->top]=x;//棧頂指針加1 後將x 入棧

}

(5) 退棧

DataType Pop(S)

{

if(StackEmpty(S))

Error("Stack underflow"); //下溢,退出運行

return S->data[S->top--];//棧頂元素返回後將棧頂指針減1

}

(6) 取棧頂元素

DataType StackTop(S)

{

if(StackEmpty(S))

Error("Stack is empty");

return S->data[S->top];

}

4、兩個棧共享同一存儲空間

當程序中同時使用兩個棧時,可以將兩個棧的棧底設在向量空間的兩端,讓兩個棧各自向中間延伸。

當一個棧里的元素較多,超過向量空間的一半時,只要另一個棧的元素不多,那麼前者就可以佔用後者的

部分存儲空間。

只有當整個向量空間被兩個棧占滿(即兩個棧頂相遇)時,才會發生上溢。因此,兩個棧共享一個長

度為m 的向量空間和兩個棧分別佔用兩個長度為└ m/2┘和┌m/2┐的向量空間比較,前者發生上溢的概

率比後者要小得多。

鏈棧

棧的鏈式存儲結構稱為鏈棧。

1、鏈棧的類型定義

鏈棧是沒有附加頭結點的運算受限的單鏈表。棧頂指針就是鏈表的頭指針。

鏈棧的類型說明如下:

typedef struct stacknode{

DataType data

struct stacknode *next

}StackNode;

typedef struct{

StackNode *top; //棧頂指針

}LinkStack;

注意:

①LinkStack 結構類型的定義是為了方便在函數體中修改top 指針本身

②若要記錄棧中元素個數,可將元素個數屬性放在LinkStack 類型中定義。

2、鏈棧的基本運算

(1) 置棧空

Void InitStack(LinkStack *S)

{

S->top=NULL;

}

(2) 判棧空

int StackEmpty(LinkStack *S)

{

return S->top==NULL;

}

(3) 進棧

void Push(LinkStack *S,DataType x)

{//將元素x 插入鏈棧頭部

StackNode *p=(StackNode *)malloc(sizeof(StackNode));

p->data=x;

p->next=S->top;//將新結點*p 插入鏈棧頭部

S->top=p;

}

(4) 退棧

DataType Pop(LinkStack *S)

{

DataType x;

StackNode *p=S->top;//保存棧頂指針

if(StackEmpty(S))

Error("Stack underflow."); //下溢

x=p->data; //保存棧頂結點數據

S->top=p->next; //將棧頂結點從鏈上摘下

free(p);

return x;

}

(5) 取棧頂元素

DataType StackTop(LinkStack *S)

{

if(StackEmpty(S))

Error("Stack is empty.")

return S->top->data;

}

注意:

鏈棧中的結點是動態分配的,所以可以不考慮上溢,無須定義StackFull 運算。

--------------------------------------------------------------------------------------------

-----------------

隊列的定義及基本運算

1、定義

隊列(Queue)是只允許在一端進行插入,而在另一端進行刪除的運算受限的線性表

(1)允許刪除的一端稱為隊頭(Front)。

(2)允許插入的一端稱為隊尾(Rear)。

(3)當隊列中沒有元素時稱為空隊列。

(4)隊列亦稱作先進先出(First In First Out)的線性表,簡稱為FIFO 表。

隊列的修改是依先進先出的原則進行的。新來的成員總是加入隊尾(即不允許"加塞"),每次離開的

成員總是隊列頭上的(不允許中途離隊),即當前"最老的"成員離隊。

【例】在隊列中依次加入元素a1,a2,… ,an 之後,a1 是隊頭元素,an 是隊尾元素。退出隊列的次序

只能是a1,a2,… ,an。

2、隊列的基本邏輯運算

(1)InitQueue(Q)

置空隊。構造一個空隊列Q。

(2)QueueEmpty(Q)

判隊空。若隊列Q 為空,則返回真值,否則返回假值。

(3) QueueFull(Q)

判隊滿。若隊列Q 為滿,則返回真值,否則返回假值。

注意:

此操作只適用於隊列的順序存儲結構。

(4) EnQueue(Q,x)

若隊列Q 非滿,則將元素x 插入Q 的隊尾。此操作簡稱入隊。

(5) DeQueue(Q)

若隊列Q 非空,則刪去Q 的隊頭元素,並返回該元素。此操作簡稱出隊。

(6) QueueFront(Q)

若隊列Q 非空,則返回隊頭元素,但不改變隊列Q 的狀態。

順序隊列

1、順序隊列

(1)順序隊列的定義

隊列的順序存儲結構稱為順序隊列,順序隊列實際上是運算受限的順序表。

(2) 順序隊列的表示

①和順序表一樣,順序隊列用一個向量空間來存放當前隊列中的元素。

②由於隊列的隊頭和隊尾的位置是變化的,設置兩個指針front 和rear 分別指示隊頭元素和隊尾元素

在向量空間中的位置,它們的初值在隊列初始化時均應置為0。

(3) 順序隊列的基本操作

①入隊時:將新元素插入rear 所指的位置,然後將rear 加1。

②出隊時:刪去front 所指的元素,然後將front 加1 並返回被刪元素。

注意:

①當頭尾指針相等時,隊列為空。

②在非空隊列里,隊頭指針始終指向隊頭元素,尾指針始終指向隊尾元素的下一位置。

順序隊列基本操作【參見動畫演示】

(4)順序隊列中的溢出現象

① "下溢"現象

當隊列為空時,做出隊運算產生的溢出現象。「下溢」是正常現象,常用作程序控制轉移的條件。

② "真上溢"現象

當隊列滿時,做進棧運算產生空間溢出的現象。「真上溢」是一種出錯狀態,應設法避免。

③ "假上溢"現象

由於入隊和出隊操作中,頭尾指針只增加不減小,致使被刪元素的空間永遠無法重新利用。當隊列中

實際的元素個數遠遠小於向量空間的規模時,也可能由於尾指針已超越向量空間的上界而不能做入隊操作。

該現象稱為"假上溢"現象。

【例】假設下述操作序列作用在初始為空的順序隊列上:

EnQueue,DeQueue,EnQueue,DeQueue,…

盡管在任何時刻,隊列元素的個數均不超過1,但是只要該序列足夠長,事先定義的向量空間無論多大

均會產生指針越界錯誤。

鏈隊列

1、鏈隊列的定義

隊列的鏈式存儲結構簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。

2、鏈隊列的結構類型說明

注意:

增加指向鏈表上的最後一個結點的尾指針,便於在表尾做插入操作。

鏈隊列示意圖見上圖,圖中Q 為LinkQueue 型的指針。

3、鏈隊列的基本運算

(1) 置空隊

void InitQueue(LinkQueue *Q)

{

Q->front=Q->rear=NULL;

}

(2) 判隊空

intQueueEmpty(LinkQueue *Q)

{

return Q->front==NULL&&Q->rear==Null;

//實際上只須判斷隊頭指針是否為空即可

}

(3) 入隊

void EnQueue(LinkQueue *Q,DataType x)

{//將元素x 插入鏈隊列尾部

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申請新結點

p->data=x; p->next=NULL;

if(QueueEmpty(Q))

Q->front=Q->rear=p; //將x 插入空隊列

else { //x 插入非空隊列的尾

Q->rear->next=p; //*p 鏈到原隊尾結點後

Q->rear=p; //隊尾指針指向新的尾

}

}

(4) 出隊

DataType DeQueue (LinkQueue *Q)

{

DataType x;

QueueNode *p;

if(QueueEmpty(Q))

Error("Queue underflow");//下溢

p=Q->front; //指向對頭結點

x=p->data; //保存對頭結點的數據

Q->front=p->next; //將對頭結點從鏈上摘下

if(Q->rear==p)//原隊中只有一個結點,刪去後隊列變空,此時隊頭指針已為空

Q->rear=NULL;

free(p); //釋放被刪隊頭結點

return x; //返回原隊頭數據

}

(5) 取隊頭元素

DataType QueueFront(LinkQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->front->data;

}

注意:

①和鏈棧類似,無須考慮判隊滿的運算及上溢。

②在出隊演算法中,一般只需修改隊頭指針。但當原隊中只有一個結點時,該結點既是隊頭也是隊尾,

故刪去此結點時亦需修改尾指針,且刪去此結點後隊列變空。

③以上討論的是無頭結點鏈隊列的基本運算。和單鏈表類似,為了簡化邊界條件的處理,在隊頭結點

前也可附加一個頭結點,增加頭結點的鏈隊列的基本運算【參見練習】

循環隊列

為充分利用向量空間,克服"假上溢"現象的方法是:將向量空間想像為一個首尾相接的圓環,並稱這

種向量為循環向量。存儲在其中的隊列稱為循環隊列(Circular Queue)。

(1) 循環隊列的基本操作

循環隊列中進行出隊、入隊操作時,頭尾指針仍要加1,朝前移動。只不過當頭尾指針指向向量上界

(QueueSize-1)時,其加1 操作的結果是指向向量的下界0。這種循環意義下的加1 操作可以描述為:

① 方法一:

if(i+1==QueueSize) //i 表示front 或rear

i=0;

else

i++;

② 方法二--利用"模運算"

i=(i+1)%QueueSize;

(2) 循環隊列邊界條件處理

循環隊列中,由於入隊時尾指針向前追趕頭指針;出隊時頭指針向前追趕尾指針,造成隊空和隊滿時

頭尾指針均相等。因此,無法通過條件front==rear 來判別隊列是"空"還是"滿"。【參見動畫演示】

解決這個問題的方法至少有三種:

① 另設一布爾變數以區別隊列的空和滿;

② 少用一個元素的空間。約定入隊前,測試尾指針在循環意義下加1 後是否等於頭指針,若相等則認

為隊滿(注意:rear 所指的單元始終為空);

③使用一個計數器記錄隊列中元素的總數(即隊列長度)。

(3) 循環隊列的類型定義

#define Queur Size 100 //應根據具體情況定義該值

typedef char Queue DataType; //DataType 的類型依賴於具體的應用

typedef Sturet{ //頭指針,隊非空時指向隊頭元素

int front; //尾指針,隊非空時指向隊尾元素的下一位置

int rear; //計數器,記錄隊中元素總數

DataType data[QueueSize]

}CirQueue;

(4) 循環隊列的基本運算

用第三種方法,循環隊列的六種基本運算:

① 置隊空

void InitQueue(CirQueue *Q)

{

Q->front=Q->rear=0;

Q->count=0; //計數器置0

}

② 判隊空

int QueueEmpty(CirQueue *Q)

{

return Q->count==0; //隊列無元素為空

}

③ 判隊滿

int QueueFull(CirQueue *Q)

{

return Q->count==QueueSize; //隊中元素個數等於QueueSize 時隊滿

}

④ 入隊

void EnQueue(CirQueuq *Q,DataType x)

{

if(QueueFull((Q))

Error("Queue overflow"); //隊滿上溢

Q->count ++; //隊列元素個數加1

Q->data[Q->rear]=x; //新元素插入隊尾

Q->rear=(Q->rear+1)%QueueSize; //循環意義下將尾指針加1

⑤ 出隊

DataType DeQueue(CirQueue *Q)

{

DataType temp;

if(QueueEmpty((Q))

Error("Queue underflow"); //隊空下溢

temp=Q->data[Q->front];

Q->count--; //隊列元素個數減1

Q->front=(Q->front+1)&QueueSize; //循環意義下的頭指針加1

return temp;

}

⑥取隊頭元素

DataType QueueFront(CirQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->data[Q->front];

}

Ⅷ 數據結構隊列問題:為什麼鏈隊 要分兩個結構體來定義

因為鏈隊結構是一種運算受限的線性表,其限制是僅允許在表的一端進行插入,而在表的另一端進行刪除。每個元素必然按照進入的次序離隊,所以又把隊列稱為先進先出表。
鏈式隊列存儲結構也是通過由結點構成的單鏈表實現的。
在單鏈表中可以在表中的任何位置插入數據,不過在鏈隊中,只能從末尾插入數據,從起始處刪除。所以就需要一個結構來定義下一個節點的位置。
你可以將單鏈表理解為允許鬆散的隊伍,它是允許插隊的。
鏈隊是有人管理的隊伍,它有嚴格的要求,有一個管理者,不允許插隊,管理者控制著隊伍的進出。
一個結構體是管理者,一個結構體是隊伍的起始和結束位置。

Ⅸ C語言二級考試循環鏈表是循環隊列的鏈式存儲結構

循環隊列本身是一種順序存儲結構,而循環列表是一種鏈式存儲結構。兩者之間是平級關系。

線性鏈表是線性表的鏈式存儲結構,包括單鏈表,雙鏈表,循環鏈表等。

隊列的順序存儲結構一般採用循環隊列的形式。

循環隊列的操作是按數組取摸運算的,所以是順序存儲,而循環鏈表本身就是收尾相連的,所以循環鏈表不是循環隊列,兩種不同的存儲結構,雖然實現的功能是一樣的,實現循環兩種方式 順序存儲就是循環隊列,鏈式存儲就是循環鏈表。

(9)鏈隊列存儲結構的定義擴展閱讀:

1、比順序存儲結構的存儲密度小(鏈式存儲結構中每個結點都由數據域與指針域兩部分組成,相比順序存儲結構增加了存儲空間)。

2、邏輯上相鄰的節點物理上不必相鄰。

3、插入、刪除靈活 (不必移動節點,只要改變節點中的指針)。

4、查找節點時鏈式存儲要比順序存儲慢。

5、每個節點是由數據域和指針域組成。

6、由於簇是隨機分配的,這也使數據刪除後覆蓋幾率降低,恢復可能提高。