資料結構—連結串列、堆疊、佇列詳解
資料結構—連結串列、堆疊、佇列詳解

一、兩種儲存方式

1、順序儲存

2、鏈式儲存

二、順序表

顧名思義,順序表就是一段連續的儲存空間,知道首地址,可以訪問表中的任意元素;比如陣列;

                                                   

像這樣的一段儲存空間。

typedef struct
{
datatype data[MAXSIZE];
int len;
}sqlistnode, *sqlistlink; 

   sqlistnode結構體變數名;  sqlistlink結構體指標變數名;

我們在封裝表的時候這樣定義一個結構體,裡面存放順序表的每一個元素及表長(元素的個數,不是元素下標);

 1、建立表

我們用malloc函式:sqlistlink*sq= (sqlistlink)malloc(sizeof(sqlistnode))

這樣為結構體開闢一段空間,指標sq指向這段空間的首地址;

 2、插入元素

      
順序可以在表的任何地方進行插入和刪除;插入時要進行元素的移位,思想是先判斷順序表是否已滿,再確定待插入的位置,將帶插入位置的元素逐個向後移動,將要插入的元素插入,同時表長自加:

sq->data[j 1]= sq->data[j];      

sq->data[i-1] =x;

sq->len ;

3、元素的刪除

刪除時同樣要進行元素的移位,思想是先判斷順序表是否為空,在確定待刪除掉的元素位置,然後進行想前移位,在將表長減一;

sq->data[j-1]=sq->data[j];        

sq->len–;

具體程式碼檢視程式;

三、連結串列

連結串列在順序表的基礎上,增加了指向下一節點的地址,使得每個節點具有資料域和指標域;

一條連結串列有一個head指向的頭結點(資料域為-1是自己設定的,個人有人的想法),有一個指標域為NULL的未節點;其中空連結串列頭結點和未節點在一起;

                                       

typedef struct clist
{
datatype data;
struct clist *next;
}clistnode, *clistlink;

clistnode 結構體變數名; clistlink結構體指標變數名;

建立一個連結串列,具有指標域,資料域,在做操的過程中,頭結點始終不變。

1、建立連結串列

clistlink creat_clist_node(datatype x)//建立一個節點,資料域為x,指標域為NULL
{
clistlink q = (clistlink)malloc(sizeof(clistnode));
assert(q);     //判斷聲請的空間是否沒空
q->data = x;
q->next = NULL;
return q;
}
clistlink creat_clist(void)//建立空連結串列
{
clistlink head = creat_clist_node(-1);//將頭結點的資料域賦-1,以便後面做區別
return head;
}

2、插入節點

和順序表一樣,可以在任何地方插入,但頭結點不動;注意:連結串列沒有滿這一說,只有你記憶體足夠大;

先定義兩個指標,clistlink p = NULL, q =NULL;

讓其中一個指向表頭:p = head;

一個指向待插入節點q = creat_clist_node(x);

確定要插入的位置,然後將p指標指向要插入位置的前一個節點;

注意;指標不能在連結串列上後退;可以p = p->next這樣移動;現在p指向待插入位置

的前一個節點,現在讓帶插入節點指向後面的節點(資料域data3的這個節點):q->next
= p->next;

帶插入前一個節點指向帶插入節點;p->next = q;    這樣一個節點就插入到這條連結串列中去,

     說的有點羅素,其實明白了很簡單;

3、刪除節點

刪除連結串列思想就是:將待刪除前一個節點指向待刪除後一個節點即可;記著要釋放被刪除的空間,用malloc函式申請的空間必須要程式設計師手動釋放(free),不然造成記憶體耗光;

四、棧

我們經常接觸到的都是滿遞增的棧,滿:就是棧頂元素是滿的,相對,空就是站定元素是空的。 如下圖:棧是以一種先進後出的演算法,插入和刪除都在棧頂進行,

                                                                            

top是空時,進棧時先裝入元素,再top自加,而top是滿時,先裝入,再自加,

也就是當空棧時,top始終指向棧頂前面一個元素,滿棧時,top指向棧頂,

順序棧也是順序表的一種,具有順序表同樣的儲存方法,由陣列定義。

typedef struct clist
{
datatype data;
struct clist *next;
}clistnode, *clistlink;

進棧程式碼:

st->top ;

st->data[st->top] = x;

出棧程式碼;

*ret = st->data[st->top];
st->top--;        //注意:進棧和出棧的程式碼很對稱;

五、鏈式棧

       鏈式棧不同連結串列的是插入和刪除都在表頭進行,資料域,指標域,表頭等資訊。 在這裡,棧有帶頭節點,不帶頭節點,相對來說,帶頭結點的棧要好操作;

1、有頭節點

          注意:棧頂與頭節點不是一個

typedef struct chainstackaa
{
datatype data;
struct chainstack *next;
}cstacknode, *cstacklink;  

入棧

先定義兩個指標q,一個指向我們新定義的節點,資料域為x,指標域為空;

cstacklink q = (cstacklink)malloc(sizeof(cstacknode));

   
q->data = x;

讓帶插入節點指向棧頂節點,q->next=top->next;然後將帶插入節點的地址付給top->next;top->next=q;這樣新插入的節點就是棧頂;

出棧

定義一個指標p指向棧頂:

q=p=top->next;

p=p->next;  p現在指向data2這個地方;

Top->next=p;

 就是讓頭節點指向棧頂下一個節點,已刪除棧頂節點,記著要釋放空間

        free(q);q=NULL;

六、佇列

是限制在兩端進行插入操作和刪除操作的線性表。插入在隊尾,刪除在對頭;特點:先進先出

1、順序佇列

基本定義:他是順序表的一種,具有順序表同樣的儲存結構,有陣列定義,配合用陣列下標表示的對頭指標和隊尾指標完成各種操作。對於順序佇列有兩個規則;

    規則1:front指向隊頭元素的前一個位置;rear指向隊尾元素所在的位

                                                                 

這樣,在入隊的時候,先給隊尾指標加1,在將帶插入元素插入到隊尾指標所指向的地址

在出對時,先將對頭指標向下移動一位,在取出其中的值儲存起來

規則2:front指向隊頭元素的位置;rear指向隊尾元素的下一個位置

                                                                  

這樣入隊的時候,向插入元素,再將rear向下移動一個位置

在出對時,先將頭指標向下移動一位,在取出其中的值儲存起來;

注意;1、在佇列操作過程中,為了提高效率,已調整指標代替佇列元素的移動,並將陣列作為迴圈佇列的操作空間,2、為區別隊和滿隊,滿隊元素的個數比陣列元素個數少一個;

typedef struct
{
datatype data[MAXSIZE];
int front, rear;
}squeuenode, *squeuelink;

⑴、空佇列的建立

void creat_squeue(squeuelink *sq)
{
*sq = (squeuelink)malloc(sizeof(squeuenode));
(*sq)->front = (*sq)->rear = 0;
}  //接著將對頭著隊尾指向同一個0地址;

⑵、入隊,在隊尾進行   先要判斷佇列是否有滿隊

void in_squeue(squeuelink sq, datatype x)
{
if(isfull_squeue(sq))
{
printf("squeue is full!\n");
return;
}
sq->rear = (sq->rear   1) % MAXSIZE;
sq->data[sq->rear] = x;
}

⑶、出對,在對頭進行   先要判斷佇列是否有元素

int out_squeue(squeuelink sq, datatype *ret)
{
if(isempty_squeue(sq))
{
printf("squeue is empty!\n");
return FALSE;
}
sq->front = (sq->front   1) % MAXSIZE;
*ret = sq->data[sq->front];
return TRUE;
}

2、鏈式隊

是連結串列的一種,具備鏈式表的所有特性,但是同樣插入操作在隊尾進行,刪除操作在對頭進行,由對頭指標和隊尾指標控制佇列的操作

   1、帶頭節點

                                 

   2、不帶頭節點