用游戲串起程序員的基本功之五

2019-11-17 05:08:43

字體：大中小

來源：轉載

供稿：網友

　　游戲的細節部分快談完了，我們的這篇文章也即將結束。但這部分所談到得內容依然是數據結構方面的很主要的一部分內容。閑話少敘，回到我們的教程中。

　　細心的讀者可能發現了，這里我的所有例子都是基于數組這種結構來談的。所以我們先來看一看數組的一些特點。從前面的例子中,我們可以看到,數組是一種不僅在存儲地址上連續而且其中前后數據在邏輯上也連續的存儲數據的結構。它的優點是,讀取和修改其中的每一個數值都很方便。只要直接找到它的索引值就可以讀取和修改它的數值。即使要想讀取或修改數組中所有的數值,我們也只需要一個從頭到尾的循環.但是對于數組的插入,刪除,和排序卻是一件很繁瑣的事,比如我們在數組中間插入一個數值,就要將它所在的位置之后的所有數值后移一位,假如其后的數值很多,效率是極低的.示例如下:

用游戲串起程序員的基本功之五（圖一）

　　上面是待插入數值的數組.假如想在5的后面插入一個1,可以想到首先要找到5所在的位置,然后,從最后的9開始,向后移動一個位置,直到空出5后面的位置,最后將1插入其中.在這里我們只需移動四個數,但當數值越多,那么移動的數值也就會越多.

　　除此之外,數組還有一個不足之處.那就是我們在不知到數據多少時,為存儲下所有數據,必須建立很多空的數組,勢必造成存儲空間的浪費.

　　這里我們再介紹一種數據結構——鏈表。我們先來看個例子。

(圖片較大，請拉動滾動條觀看)

　　上面是存在內存中的數據，在存儲位置上，它們都是不連續的，但我們可以不考慮他們的實際位置，而在邏輯上讓他們形成一種前后相聯的關系。怎么做呢？

　　正如下圖所示：我們只要加一個“鏈”就可以將內存中不連續的單元連接起來。用c語言我們可以這樣做：
StrUCt jiegouming //結構名稱
{
　int shu； //用來存儲數據
　Struct list *next； //用來連接下一個
}
typedef struct jiegouming node；
typedef Node *link；
用游戲串起程序員的基本功之五（圖三）

　　這樣我們就可以用next這樣的一個指針，將多個這樣的結構聯系起來了。而且還可以在需要的時候，動態的建立，不需要的時候，再釋放掉，從而節省了，內存空間。

　　我們來看一看鏈表的建立和釋放。下面是源程序：

link creatlist（link head）//建立一個有10個節點的鏈表,并初始化為0
{
　link point;//聲明兩個接點
　link new;
　int num=10;//計數值設為10
　head = （link）malloc （sizeof（node））；
　if（head==NULL）
　　PRintf（” 內存建立失敗”）;
　else
　{
　　head->next=NULL;
　　printf(“建立成功”)
　}
　point = head;//將point 設為首節點
　while(num>0)
　{
　　new = (link) malloc (sizeof(node));
　　if(new==NULL)
　　　printf(“內存建立失敗”);
　　else
　　　new->shu=o;//將新建的節點中的數值設為0
　　　new->next=NULL;// 將新建的節點中的下一個節點設為NULL
　　　point->next=new;//將新建的節點連接到前一個節點上
　　　point=new;// 將新建節點設為當前節點
　　　num--; //計數值減一
　}//end while
}//end

void freelist(link head)//釋放鏈表
{
　link point; //聲明一個節點
　while(head !=NULL)//當節點為空,說明已到鏈表最后
　{
　　point=head;//保存節點頭
　　head=hesd->next; //向后移動倒下一個節點
　　free(point); //刪除頭一個節點
　}//end while
}//end
　　對于鏈表假如不能實現查詢,插入,刪除等功能,那么它也就沒有價值了,所以我們再來看看在鏈表中怎樣實現這些功能.

　　先來看看鏈表的查詢.因為鏈表在邏輯上也是有序排列的,所以,要找一個數值,我們同樣可以采用線性查找法挨個往下查找下去,直到找到所要查找的數值或者查找結束.

　　下面是例程:

int searchlist(int key,link head) //在鏈表head中查找key值
{
　link point;//聲明一個節點,指示當前位置
　int num=1;//記錄節點所在位置的數值
　point = head; // 指向頭一個節點
　while(point !=NULL)
　{
　　if(point->shu==key) //假如節點中的數值和要查找的數值相等
　　　return num;// 返回這個數值在鏈表中的位置
　　point = point->next; //假如節點中的數值和要查找的數值不相等,節點后移
　　num++;//計數值加一
　 }//end while
}//end
　　對于鏈表的插入方法,很靈活,不用象數組一樣插入后,還要向后移動其后面的數值.下面是一個示例圖:

用游戲串起程序員的基本功之五（圖四）

　　可見,鏈表的插入,只要修改節點的指向就可以了.

　　下面是源代碼 :

Link insertlist(link head,link new,int key)
//在鏈表head中插入數值為key的節點new
{
　link point;// 聲明一個節點,來指示當前節點
　point = head; //當前節點指向頭節點
　while(1)
　{
　　if(point==NULL)//假如鏈表head中只有一個節點
　　{ //插入到首節點的前面
　　　new->next=head;
　　　head=new;//新節點作為首節點
　　　break;
　　} //end if
　　if(point->shu==key)//假如在鏈表head中找到key值
　　{ //插入到這個數值的后面
　　　new->next=point->next;
　　　point->next=new;
　　　break;
　　} //end if
　　point=point->next;//當前節點后移
　}//end while
　return head;
}//end
　　最后是怎樣刪除一個節點.方法和插入類似.請看示例圖:

Link deletelist(link head,int key)
/在鏈表head中刪除數值key
{
　link point;//指示當前節點
　link back;//指示后一個節點
　point =head;//將頭節點設為當前節點
　while(1)
　{
　　if(point->next==NULL)//假如,沒有節點
　　{
　　　printf(“沒有節點可供刪除”);
　　　break;
　　}
　　if(head->shu ==key)//假如找到數值key所在的節點
　　{
　　　head=point->next;//將當前節點的下一個
　　　free(point);//釋放節點
　　　break;
　　}
　　back=point;//保存當前節點
　　point=point->next;//當前節點后移
　　if(point->shu==key)// 假如找到數值key所在的節點
　　{
　　　back->next=point->next;
　　　//將當前節點所連接的節點連接到當前節點的前一個節點上
　　　free(point);//釋放當前節點
　　　break;
　　}//end if
　}end while
　return head;
}//end
　　好了,就到這吧,相信大家已經體會到了數據結構著門課的重要性,我們的目的也就達到了.究竟只是一篇基礎教程.所以我們只講到了數據結構中的一些基礎性的知識.把它當作一篇入門的教程吧,有愛好的讀者可以學習一下相關的課程.一定會有所收獲的.

上一篇：活用 SetSelTextBuf

下一篇：偽隨機數生成及在VC++中的實現