《棧隊列》課程設(shè)計說明書

1、<p><b>　　《隊列》</b></p><p><b>　　課程設(shè)計說明書</b></p><p>　　學生姓名 </p><p>　　學 號 </p><p>　　所屬學院 信息工程學院 </p><p>

2、;　　專 業(yè) 計算機科學與技術(shù) </p><p>　　班 級 計算機 </p><p>　　指導教師 </p><p>　　教師職稱 講師 </p><p><b>　　目錄</b></p><p><b>　

3、　前言1</b></p><p><b>　　正文2</b></p><p>　　2.1設(shè)計的目的和意義2</p><p>　　2.2設(shè)計思路：2</p><p>　　2.2目標與總體方案2</p><p>　　2.3設(shè)計方法和內(nèi)容3</p><p>

4、;　　2.3.1隊列的定義3</p><p>　　2.3.2隊列的表示和實現(xiàn)4</p><p>　　2.3.3詳細設(shè)計5</p><p>　　2.3.4調(diào)試分析10</p><p>　　2.4設(shè)計創(chuàng)新和關(guān)鍵技術(shù)11</p><p>　　2.4.1設(shè)計創(chuàng)新11</p><p>　　2.

5、4.2關(guān)鍵技術(shù)12</p><p>　　2.5算法思想12</p><p><b>　　2.6小結(jié)12</b></p><p><b>　　參考文獻13</b></p><p><b>　　附錄13</b></p><p><b>　

6、　前言</b></p><p>　　“數(shù)據(jù)結(jié)構(gòu)”是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學科的核心課程，而且已成為其他理工專業(yè)的熱門選修課。本設(shè)計材料是為“數(shù)據(jù)結(jié)構(gòu)”課程編寫的教材，其內(nèi)容選取符合教學大綱要求，并兼顧學科的廣度和深度，適用面廣。</p><p>　　全部設(shè)計材料中采用類C語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言，在對數(shù)據(jù)的存儲結(jié)構(gòu)和算法進行描述時，盡量考慮C語

7、言的特色，如利用數(shù)組的動態(tài)分配實現(xiàn)順序存儲結(jié)構(gòu)等。從課程性質(zhì)上講，“數(shù)據(jù)結(jié)構(gòu)”是一門專業(yè)技術(shù)基礎(chǔ)課。它的教學要求是：學會分析研究計算機加工數(shù)據(jù)結(jié)構(gòu)的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。另一方面，本課程的學習過程也是復雜程序設(shè)計的訓練過程，要求學生編寫的程序結(jié)構(gòu)清楚和正確易讀，復合軟件工程的規(guī)范。如果說高級語言程序設(shè)計課程對學生進行了結(jié)構(gòu)化程序設(shè)計的初步訓練的話，

8、那么數(shù)據(jù)結(jié)構(gòu)課程就要培養(yǎng)他們的數(shù)據(jù)抽象能力。并用規(guī)范的數(shù)學語言描述數(shù)據(jù)結(jié)構(gòu)的定義，以突出其數(shù)學特性，同時，通過若干數(shù)據(jù)結(jié)構(gòu)應用實例，引導學生學習數(shù)據(jù)類型的使用，為今后學習面向?qū)ο蟮某绦蛟O(shè)計作一些鋪墊。</p><p>　　數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率的算法。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。</p><p>　

9、　在計算機科學中，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象（數(shù)據(jù)元素）以及它們之間的關(guān)系和運算等的學科，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。</p><p>　　選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因素。這種洞見導致了許多種軟件設(shè)計方法和程序設(shè)計語言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計語言就是其中之一。</p><p>　　數(shù)據(jù)是

10、計算機化的信息,它是計算機可以直接處理的最基本和最重要的對象。無論是進行科學計算或數(shù)據(jù)處理、過程控制以及對文件的存儲和檢索及數(shù)據(jù)庫技術(shù)應用等,都是對數(shù)據(jù)進行加工處理的過程。因此,要設(shè)計出一個結(jié)構(gòu)好效率高的程序,必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應的存儲表示,并利用這些特性結(jié)合相關(guān)編程技術(shù)，運用合適、熟練的方法，才能設(shè)計出符合要求、可操作性強、有利用價值的應用程序。</p><p>　　在日常生活中，我們經(jīng)

11、常會遇到許多為了維護社會正常秩序而需要排隊的情景。這樣一類活動的模擬程序通常需要用到隊列和線性表之類的數(shù)據(jù)結(jié)構(gòu)，因此是隊列的典型應用例子之一。在操作系統(tǒng)中的作業(yè)排隊，在允許多道程序運行的計算機系統(tǒng)中，同時有幾個作業(yè)運行。如果運行的結(jié)果都需要通過通道輸出，那就要按請求輸出的先后次序排隊。每當通道傳輸完畢可以接受新的輸出任務時，隊頭的作業(yè)先從隊列中退出作輸出操作。凡是申請輸出的作業(yè)都從隊尾進入隊列。</p><p>

12、　　本實驗設(shè)計運用了數(shù)據(jù)結(jié)構(gòu)的知識，主要涉及到了隊列的相關(guān)概念、原理、算法和操作等方面內(nèi)容。本實驗設(shè)計主要實現(xiàn)隊列的3個基本功能：建立新的鏈表隊列、入隊一個元素、出隊一個元素。應用到的原理是先進先出算法。主要內(nèi)容是使用C語言和C++語言相結(jié)合編寫程序，能夠順利通過鍵盤來操作該程序，完整實現(xiàn)上述要求。</p><p><b>　　正文</b></p><p>　　2.1

13、設(shè)計的目的和意義</p><p>　　課程設(shè)計目的是為學生提供了一個既動手又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結(jié)合起來，鍛煉學生的分析解決實際問題的能力。提高學生適應實際，實踐編程的能力。通過實踐讓學生理論和實際操作相結(jié)合，更好的理解書面知識，并在鞏固的基礎(chǔ)上融會所學認識。</p><p>　　課程設(shè)計的意思是培養(yǎng)學生運用所學課程的知識分析解決實際問題的能力；培養(yǎng)學生調(diào)查

14、研究、查閱技術(shù)文獻、資料、手冊以及編寫技術(shù)文獻的能力；通過課程設(shè)計，要求學生在指導教師的指導下，獨立完成設(shè)計課題的全部內(nèi)容，包括：</p><p>　　通過調(diào)查研究和上機實習，收集和調(diào)查有關(guān)技術(shù)資料。</p><p>　　掌握課程設(shè)計的基本步驟和方法。</p><p>　?。?）根據(jù)課題的要求進行上機實驗調(diào)試。</p><p><b&g

15、t;　　2.2設(shè)計思路：</b></p><p>　　棧的特點是先進后出，而隊列的特點是先進先出，這個程序主要是利用到棧和隊列的這兩個特點，根據(jù)需要編寫各個功能函數(shù)代碼，因為本程序中涉及到的功能較多，而且每個大的功能塊還包含了小功能，所以我使用了function1，function2，function3，function4這四個功能塊，分別調(diào)用所編寫的功能函數(shù)來實現(xiàn)所需要的四個大操作，然后再funct

16、ion塊中編寫功能菜單代碼，調(diào)用function1，F(xiàn)unction2，function3，function4，實現(xiàn)各個菜單。然后在main函數(shù)中編寫一個詢問用戶是否繼續(xù)該程序的功能代碼，這樣大體上就完成了這個程序的設(shè)置。</p><p>　　字符串的基本操作，我寫的是創(chuàng)建字符串，串的聯(lián)接，求串的長度，返回串第pos個位置長為len的字串，清空串，在做這一塊時我們可以先把他的各個基本操作的函數(shù)寫出來，然后在fun

17、ction4中調(diào)用它，這樣就可以實現(xiàn)了。</p><p>　　2.2目標與總體方案</p><p>　　本實驗設(shè)計的目標是分析隊列元素之間的關(guān)系，清楚元素進出隊列的先后順序和隊列實現(xiàn)“先進先出”算法的原理，運用C語言（或C++程序）編寫程序，實現(xiàn)隊列的建立、插入和刪除基本功能，在程序設(shè)計成功的基礎(chǔ)上，進一步深化理解隊列的作用和實現(xiàn)原理，并獨自撰寫設(shè)計論文。</p><p

18、>　　本實驗設(shè)計總體方案如圖2.2.1所示： </p><p>　　圖2.2.1設(shè)計總體方案圖</p><p>　　要求本設(shè)計嚴格按照方案進行，力求省時省力，提高設(shè)計效率，節(jié)約資源。</p><p>　　2.3設(shè)計方法和內(nèi)容</p><p>　　2.3.1隊列的定義</p><p>　　◇抽象數(shù)據(jù)類型隊列的定義&

19、lt;/p><p>　　和棧相反，隊列是一種先進先出的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。這和我們?nèi)粘Ｉ钪械呐抨犑且恢碌淖钤邕M入隊列的元素最早離開。在隊列中，允許插入的一端叫做隊尾，允許刪除的一端稱為隊頭。假設(shè)隊列為q=(a1,a2,…,an),那么，a1是隊頭元素，an則是隊尾元素。隊列中的元素是按照a1,a2,…,an的順序進入的，退出隊列也只能按照這個次序依次退出，也就是說，只有在a1,a

20、2,…,an-1都離開隊列之后，an才能退出隊列。圖2.3.1是隊列的示意圖</p><p>　　圖2.3.1 隊列的示意圖</p><p>　　隊列在程序設(shè)計中也經(jīng)常出現(xiàn)。一個最典型的例子就是操作系統(tǒng)中的作業(yè)排隊。在允許多道程序運行的計算機系統(tǒng)中，同時有幾個作業(yè)運行。如果運行的結(jié)果都需要通過通道輸出，那就要按請求輸出的先后次序排隊。每當通道傳輸完畢可以接受新的輸出任務時，隊頭的作業(yè)先從隊

21、列中作退出輸出操作。凡是申請輸出的作業(yè)都從隊尾進入隊列。</p><p>　　隊列的操作與棧的操作類似，也有8個，不同的是刪除是在表的頭部（即隊頭）進行。</p><p>　　除了隊列和棧之外，還有一種限定性數(shù)據(jù)結(jié)構(gòu)是雙端隊列（deque）。</p><p>　　雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。這兩端分別稱為端點1和端點2（如圖2.3.2（a）所

22、示）。也可像棧一樣，可以用一個鐵道轉(zhuǎn)軌網(wǎng)絡(luò)來比喻雙端隊列，如圖2.3.2（b）所示。在實際使用中，還可以有輸出受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許插入的雙端隊列）和輸入受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許刪除的雙端隊列）。而如果限定雙端隊列從某個端點插入的元素只能從該端點刪除，則該雙端隊列就蛻變?yōu)閮蓚€棧底相鄰接的棧了。</p><p>　　圖2.3.2 雙端隊列示意圖(

23、a)雙端隊列；(b)鐵道轉(zhuǎn)軌網(wǎng)</p><p>　　2.3.2隊列的表示和實現(xiàn)</p><p>　　◇鏈隊列——隊列的鏈式表示和實現(xiàn)</p><p>　　和線性表類似，隊列也可以有兩種存儲表示。</p><p>　　用鏈表表示的隊列簡稱為鏈隊列，如圖2.3.3所示。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為頭指針和尾指針）才能唯

24、一確定。這里，和線性表的單鏈表一樣，為了操作方便起見，我們也給鏈隊列添加一個頭結(jié)點，并令頭指針指向頭結(jié)點。由此，空的鏈隊列的判決條件為頭指針和尾指針均指向頭結(jié)點，如圖2.3.4（a）所示。</p><p>　　鏈隊列的操作即為單鏈表的插入和刪除操作的特殊情況，只是尚需修改尾指針或頭指針，圖2.3.4（b）～（d）展示了這兩種操作進行時指針變化的情況。</p><p>　　圖2.3.3 鏈隊

25、列示意圖 圖2.3.4 隊列運算指針變化狀況</p><p>　　◇循環(huán)隊列——隊列的順序表示和實現(xiàn)</p><p>　　和順序棧相似，在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素及隊列尾元素的位置。為了C語言中描述方便起見，在此我們約定，初

26、始化建空隊列時，令front=rear=0,每當插入新的隊列尾元素時，“尾指針增1”；每當刪除隊列頭元素時，“頭指針增1”。因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置，如圖2.3.5所示。</p><p>　　圖2.3.5 頭、尾指針和隊列中元素之間的關(guān)系 圖2.3.6循環(huán)隊列示意圖</p><p>　　假設(shè)

27、當前的為隊列分配的最大空間為6，則當隊列處于圖2.3.5（d）的狀態(tài)時不可再繼續(xù)插入心的隊尾元素，否則會因數(shù)組越界而遭致程序代碼被破壞。然而此時又不宜如順序棧那樣，進行存儲再分配擴大數(shù)組空間，因為隊列的實際可用空間并未占滿。一個較巧妙的辦法是將順序隊列臆造為一個環(huán)狀的空間，如圖2.3.6所示，稱之為循環(huán)隊列。指針和隊列元素之間的關(guān)系不變，如圖2.3.7(a)所示循環(huán)隊列中，隊列頭元素是J3，隊列為元素是J5，之后J6、J7和J8相繼插入

28、，則隊列空間均被占滿，如圖2.3.7(b)所示，此時Q.front=Q.rear；反之，若J3、J4和J5相繼從圖2.3.7(a)的隊列中刪除，使隊列呈“空”的狀態(tài)，如圖2.3.7(c)所示。此時也存在關(guān)系式Q.front=Q.rear，由此可見，只憑等式Q.front=Q.rear無法判別隊列空間是“空”還是“滿”?？捎袃煞N處理方法：其一是設(shè)一個標志位區(qū)別隊列是“空”還是“滿”；其二是少用一個元素空間，約定以“隊列頭指針在隊列尾指針的

29、下一位置上（指環(huán)狀的下一位置）上”作為隊列呈“滿”狀態(tài)的標志。</p><p>　　從上述分析可見，在C語言中不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列。如果用戶的應用程序中設(shè)有循環(huán)隊列，則必須為它設(shè)定一個最大隊列長度；若用戶無法預估所用隊列的最大長度，則宜采用鏈隊列。</p><p><b>　　2.3.3詳細設(shè)計</b></p><p>　　*

30、*#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　typedef struct Queue</p><p><b>　　{</b></p><p><b>　　int data;</b></p>

31、<p>　　struct Queue *next;</p><p>　　}Queue,*QueuePtr;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　QueuePtr front; //對頭指針</p><p>　

32、　QueuePtr rear; //隊尾指針</p><p>　　}LinkQueue;</p><p>　　/***************構(gòu)造隊列**************/</p><p>　　void InitQueu(LinkQueue &Q)</p><p><b>　　{</b></p&

33、gt;<p>　　Q.front=Q.rear=(QueuePtr)malloc(sizeof(Queue));</p><p>　　Q.front->next=NULL;</p><p>　　printf("構(gòu)造成功!\n");</p><p><b>　　}</b></p><p&

34、gt;　　/***************進隊函數(shù)**************/</p><p>　　int EnQueue(LinkQueue &Q,int &e)</p><p><b>　　{</b></p><p>　　QueuePtr p;</p><p>　　p=(QueuePtr)mallo

35、c(sizeof(Queue));</p><p><b>　　if(!p)</b></p><p><b>　　return 0;</b></p><p>　　p->data=e;</p><p>　　p->next=NULL;</p><p>　　Q.rear

36、->next=p;</p><p><b>　　Q.rear=p;</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　/***************出隊函數(shù)**************/</

37、p><p>　　void DeQueue(LinkQueue &Q,int &e)</p><p><b>　　{</b></p><p>　　QueuePtr p;</p><p>　　if(Q.front==Q.rear)</p><p>　　printf("該隊列為空!

38、\n");</p><p>　　p=Q.front->next;</p><p>　　e=p->data;</p><p>　　Q.front->next=p->next;</p><p>　　if(Q.rear==p)</p><p>　　Q.rear=Q.front;</p&

39、gt;<p><b>　　free(p);</b></p><p>　　printf("出對成功!\n");</p><p><b>　　}</b></p><p>　　/***************取對頭函數(shù)**************/</p><p>　　v

40、oid GetQueue(LinkQueue &Q,int &e)</p><p><b>　　{</b></p><p>　　QueuePtr p;</p><p>　　if(Q.front==Q.rear)</p><p>　　printf("隊列為空，無對頭。\n");<

41、/p><p>　　p=Q.front->next;</p><p>　　e=p->data;</p><p><b>　　}</b></p><p>　　/***************輸出函數(shù)**************/</p><p>　　void OutQueue(LinkQueu

42、e Q)</p><p><b>　　{ </b></p><p>　　if(Q.rear ==Q.front ) </p><p>　　printf("隊列為空，無元素值。\n"); </p><p>　　Queue *head=Q.front->next ;</p><p

43、>　　while(head!=NULL)</p><p><b>　　{</b></p><p>　　printf("%d",head->data );</p><p>　　printf(" ");</p><p>　　head=head->next ;</

44、p><p><b>　　}</b></p><p>　　/***************主函數(shù)**************/</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></

45、p><p><b>　　char ch;</b></p><p><b>　　int e;</b></p><p>　　LinkQueue Q;</p><p><b>　　do</b></p><p><b>　　{</b></

46、p><p>　　printf("\t\t\t ---隊列操作--- ");</p><p>　　printf("\n\t\t\t******************************");</p><p>　　printf("\n\t\t\t* 0-----退出

47、 *");</p><p>　　printf("\n\t\t\t* 1-----初始化 *");</p><p>　　printf("\n\t\t\t* 2-----創(chuàng)建鏈隊列 *");</p><p>　　printf("\n\t\t\t* 3

48、-----進隊操作 *");</p><p>　　printf("\n\t\t\t* 4-----出對操作 *");</p><p>　　printf("\n\t\t\t* 5-----取對頭元素 *");</p><p>　　printf(&

49、quot;\n\t\t\t* 6-----輸出鏈隊列的元素 *");</p><p>　　printf("\n\t\t\t********************************\n");</p><p>　　printf("請選擇菜單號(0-6): "); </p><p>　　ch=getch

50、ar();</p><p>　　switch(ch)</p><p><b>　　{</b></p><p><b>　　case '0':</b></p><p>　　printf("您確定要退出嗎(y/n): ");</p><p>　

51、　scanf("%c",&ch);</p><p>　　ch=getchar();</p><p>　　if(ch=='y')</p><p>　　printf("退出程序!\n");</p><p><b>　　else</b></p>&l

52、t;p>　　printf("請繼續(xù)……\n");</p><p>　　getchar();</p><p><b>　　break;</b></p><p><b>　　case '1':</b></p><p>　　InitQueu(Q);getchar(

53、);break;</p><p><b>　　case '2':</b></p><p>　　printf("請輸入一個隊列以0結(jié)束: ");</p><p>　　scanf("%d",&e);</p><p>　　while(e!=0)</p>

54、<p><b>　　{</b></p><p>　　if(EnQueue(Q,e)!=0) </p><p>　　scanf("%d",&e);</p><p><b>　　}</b></p><p>　　printf("鏈隊的元素有: \n&qu

55、ot;);</p><p>　　OutQueue(Q);</p><p>　　getchar();</p><p><b>　　break;</b></p><p><b>　　case '3':</b></p><p>　　printf("請輸入

56、要進隊的元素e: ");</p><p>　　scanf("%d",&e);</p><p><b>　　if(e==0)</b></p><p>　　printf("進隊失敗!\n");</p><p><b>　　else</b><

57、/p><p><b>　　{</b></p><p>　　EnQueue(Q,e);</p><p>　　printf("進隊成功!\n");</p><p><b>　　}</b></p><p>　　printf("鏈隊的元素有: \n"

58、;);</p><p>　　OutQueue(Q);</p><p>　　getchar();</p><p><b>　　break;</b></p><p><b>　　case '4':</b></p><p>　　DeQueue(Q,e);</p

59、><p>　　printf("鏈隊的元素有: \n");</p><p>　　OutQueue(Q);</p><p>　　getchar();</p><p><b>　　break;</b></p><p><b>　　case '5':</b&

60、gt;</p><p>　　GetQueue(Q,e);</p><p>　　printf("對頭元素為：%d\n",e);</p><p>　　printf("鏈隊的元素有: ");</p><p>　　OutQueue(Q);</p><p>　　getchar();<

61、;/p><p><b>　　break;</b></p><p><b>　　case '6':</b></p><p>　　printf("鏈隊的元素有: \n");</p><p>　　OutQueue(Q);</p><p>　　

62、getchar();</p><p><b>　　break;</b></p><p><b>　　default :</b></p><p>　　getchar();</p><p>　　printf("輸入錯誤，請重新輸入……\n");</p><p>

63、;<b>　　}</b></p><p><b>　　}</b></p><p>　　while(ch!='y');</p><p><b>　　}</b></p><p><b>　　2.3.4調(diào)試分析</b></p>&l

64、t;p>　　2.4設(shè)計創(chuàng)新和關(guān)鍵技術(shù)</p><p><b>　　2.4.1設(shè)計創(chuàng)新</b></p><p>　　◆算法的設(shè)計取決于數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。數(shù)據(jù)的運算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法，如檢索、插入、刪除、更新的排序等。在本設(shè)計程序中，第一次把算法中的建立、插入、刪除等操作融合在一起，在一個程序中實現(xiàn)各自的功能，從而提

65、高整體的運行效率。</p><p>　　◆對每一個數(shù)據(jù)結(jié)構(gòu)而言，必定存在與它密切相關(guān)的一組操作。若操作的種類和數(shù)目不同，即使邏輯結(jié)構(gòu)相同，數(shù)據(jù)結(jié)構(gòu)能起的作用也不同。</p><p>　　不同的數(shù)據(jù)結(jié)構(gòu)其操作集不同，但下列操作必不可缺：</p><p><b>　　1. 結(jié)構(gòu)的生成；</b></p><p><b&g

66、t;　　2. 結(jié)構(gòu)的銷毀；</b></p><p>　　3. 在結(jié)構(gòu)中查找滿足規(guī)定條件的數(shù)據(jù)元素；</p><p>　　4. 在結(jié)構(gòu)中插入新的數(shù)據(jù)元素；</p><p>　　5. 刪除結(jié)構(gòu)中已經(jīng)存在的數(shù)據(jù)元素；</p><p><b>　　6. 遍歷。</b></p><p>　　在本

67、設(shè)計程序中，充分體現(xiàn)了上述的操作，雖然只是運用局部操作，但是仍然起到了關(guān)鍵作用。</p><p>　　◆使用C語言和C++相結(jié)合的方式，使得程序運行更靈活，處理更方便，在表現(xiàn)方式方面得到了創(chuàng)新。</p><p><b>　　2.4.2關(guān)鍵技術(shù)</b></p><p>　　◆數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)分別為邏輯

68、結(jié)構(gòu)、存儲結(jié)構(gòu)（物理結(jié)構(gòu)）和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，有時就把邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)形式地定義為（K，R）（或（D，S）），其中，K是數(shù)據(jù)元素的有限集，R是K上的關(guān)系的有限集。</p><p>　　在本設(shè)計程序中，我們首先定義全體實數(shù)為需要建立新的隊列的有限集，這樣就擴大了新隊列建立所需元素的取值范圍，減少了錯誤的發(fā)生。</p><p>　　◆數(shù)據(jù)元素相互

69、之間的關(guān)系稱為結(jié)構(gòu)。有四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。樹形結(jié)構(gòu)和圖形結(jié)構(gòu)全稱為非線性結(jié)構(gòu)。集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。在圖形結(jié)構(gòu)中每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。</p><p>　　在本設(shè)計程序中，我們定義隊列為線性的鏈表形式，這樣就更容易

70、操作，方便元素的插入或刪除。其中還借助了指針的作用，使得我們查找某個元素，尤其是方便了刪除或有序插入的操作。</p><p><b>　　2.5算法思想</b></p><p>　　1.（1）定義順序棧和鏈隊列及關(guān)于它們的基本操作，如定義棧和隊列、求棧和隊列的長度、入棧出棧、入隊列出隊列等。方便后面函數(shù)的調(diào)用，是實現(xiàn)程序的基石。（鏈棧和循環(huán)隊列也是如此）</p&

71、gt;<p>　　2.（2）編寫函數(shù)Palindrome_Test來實現(xiàn)字符串的回文判斷，回文是利用了棧的反序輸出原則而隊列則是順序輸出這個思想來實現(xiàn)的。往棧和隊列輸入同一組字符，再將它們一起輸出，這樣棧輸出的字符就與原來的順序相反了，而隊列輸出的字符與原來的順序仍然是一樣的，這樣比較它們輸出的字符是否相等就可以判斷是否是回文了。是則輸出1，不是則輸出0.</p><p>　?。?）編寫函數(shù)nzhi

72、來實現(xiàn)一段字符串的逆置。逆置是通過棧的反序輸出來實現(xiàn)的。通過它將隊列的一組字符串進行逆置。將隊列的字符串順序入棧然后出棧，這樣得到的字符串與原來的字符串就逆置過來了。</p><p>　　3.（1）定義車節(jié)點的類型及棧和隊列的相關(guān)操作。</p><p>　　（2）用棧的操作編寫一個停車場，隊列的操作編寫一個便車道。</p><p>　?。?）編寫函數(shù)Carrival

73、實現(xiàn)車輛入庫管理，若車庫滿則進入便車道，這個函數(shù)是利用棧的入棧等操作來實現(xiàn)的，并利用“t=localtime（&car.t）；”語句記錄入庫時間。</p><p>　　（4）編寫函數(shù)Carriva實現(xiàn)車輛出庫管理并利用“t=localtime（&car.t）；”語句記錄出庫時間，計算車輛的管理費用。若便車道內(nèi)有車等候，則進入停車場，并記錄此時時間，主要用到了棧的入棧和出棧及隊列中的入隊列等操作。用

74、“（car.t-car2.t）*charge”語句來計算車輛的管理費用。</p><p><b>　　2.6小結(jié)</b></p><p>　　為期十多天的課程設(shè)計中，吳老師幾乎都能準時，甚至提前到達教室。在同學遇到疑問時，能夠耐心地講解。雖然是講解，他不是直接告訴我們該怎么做，而是以啟發(fā)的形式鼓勵我們思考，充分的調(diào)動了我們的積極性，更重要的是使我們對不懂的知識點有了深

75、刻的了解。由于本人相關(guān)專業(yè)知識有限，在初始接觸階段遇到了許多的困難，致使程序編寫無法順利進行。在吳老師的大力指導下和各位同學們的大力幫助與支持下，同時通過本人大量查閱書籍資料，瀏覽相關(guān)網(wǎng)頁論壇之后，才順利編寫完畢，在此十分感謝大家！</p><p><b>　　參考文獻</b></p><p>　　[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.第1版.北京；清華大學出

76、版社，2005年；58-64.</p><p>　　[2] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.第1版.北京；清華大學出版社，2005年；96-105.</p><p>　　[3] 李春葆，章啟俊.C++程序設(shè)計.第1版.北京；清華大學出版社，2007年；56-31.</p><p>　　[4] 譚浩強.C程序設(shè)計（第二版）.第6版.北京；清華大學出版社，20

77、04年；9-15.</p><p>　　[5] 陳一華等編.數(shù)據(jù)結(jié)構(gòu)---使用C 語言.第一版.北京；電子科技大學出版社，1998年；12-14.</p><p>　　[6] 許卓群．數(shù)據(jù)結(jié)構(gòu)．第一版. 北京；高等教育出版社，1989年；14-18.</p><p>　　[7] 嚴蔚敏，吳偉民．數(shù)據(jù)結(jié)構(gòu)題集（C語言版）．第一版. 北京；清華大學出版社，1999；3-

78、10.</p><p>　　[8] 蔡明志．數(shù)據(jù)結(jié)構(gòu)（使用C語言）．第二版. 北京；科學出版社，1997年；12-15.</p><p>　　[9] 蔡自經(jīng)，施伯樂．數(shù)據(jù)結(jié)構(gòu)教程．第二版. 上海；復旦大學出版社，1984年，11-14.</p><p><b>　　附錄</b></p><p>　　棧（Stack）是限定

79、只能在表的一端進行插入和刪除操作的線性表。隊列（Queue）是限定只能在表的一端進行插入和在另一端進行刪除操作的線性表。從"數(shù)據(jù)結(jié)構(gòu)"的角度看，它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的"限定"。棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點在于基本操作的特殊性，棧必須按"后進先出&

80、quot;的規(guī)則進行操作，而隊列必須按"先進先出"的規(guī)則進行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。可將線性表和棧及隊列的插入和刪除操作對比如下：</p><p>　　線性表 Insert(L,i,x)(1≤i≤n+1) Delete(L,i)(1≤i≤n) 如線性表允許在表內(nèi)任一位置進行插入和刪除 </p><p>　　

81、棧 Insert(L,n+1,x) Delete(L,n) 而棧只允許在表尾一端進行插入和刪除 </p><p>　　隊列 Insert(L,n+1,x) Delete(L,1) 隊列只允許在表尾一端進行插入，在表頭一端進行刪除</p><p>　　#include<stdio.h></p><p>　　#define null 0</p>

82、<p>　　#define len sizeof(struct lnode)</p><p><b>　　int n;</b></p><p>　　struct lnode *creatlist();</p><p>　　struct lnode *listinsert();</p><p>　　struct

83、 lnode *listdel();</p><p>　　struct lnode{</p><p><b>　　int a;</b></p><p>　　struct lnode *next;</p><p><b>　　};</b></p><p>　　struct ln

84、ode *head;</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int n; </b></p><p><b>　　do{</b></p><p>　　printf("===

85、==鏈式表練習=====\n");</p><p>　　printf(" 請選擇操作：\n");</p><p>　　printf(" 1、建立鏈式表\n");</p><p>　　printf(" 2、插入新元素\n");</p><p>　　printf(&q

86、uot; 3、刪除元素\n");</p><p>　　printf("====================\n");</p><p>　　scanf("%d",&n);</p><p><b>　　switch(n)</b></p><p><b&g

87、t;　　{</b></p><p>　　case 1:creatlist();break;</p><p>　　case 2:listinsert();break;</p><p>　　case 3:listdel();break;</p><p>　　default:printf("選擇錯誤，請確認輸入！\n"

88、;);break;</p><p><b>　　}</b></p><p>　　}while(1);</p><p><b>　　}</b></p><p>　　struct lnode *creatlist()//建立鏈表</p><p><b>　　{</

89、b></p><p>　　struct lnode *p1,*p2,*p0;</p><p><b>　　n=0;</b></p><p>　　head=null;</p><p>　　p1=(struct lnode *)malloc(len);</p><p>　　printf(&quo

90、t;請輸入初始元素：\n");</p><p>　　scanf("%d",&p1->a);</p><p>　　p1->next=null;</p><p>　　while(p1->a!=0)</p><p><b>　　{</b></p><p

91、><b>　　++n;</b></p><p>　　if(n==1) head=p1;</p><p>　　else p2->next=p1;</p><p><b>　　p2=p1;</b></p><p>　　p1=(struct lnode *)malloc(len);</p

92、><p>　　scanf("%d",&p1->a);</p><p>　　p1->next=null;</p><p><b>　　}</b></p><p><b>　　free(p1);</b></p><p>　　printf(&qu

93、ot;建立鏈表成功！\n");</p><p>　　printf("建立的鏈表為：\n");</p><p><b>　　p0=head;</b></p><p><b>　　do</b></p><p><b>　　{</b></p>

94、<p>　　printf("%d ",p0->a);</p><p>　　p0=p0->next;</p><p>　　}while(p0!=null);</p><p>　　printf("\n");</p><p><b>　　free(p0);</b&g

95、t;</p><p>　　return(head);</p><p><b>　　}</b></p><p>　　struct lnode *listinsert()//插入鏈表元素</p><p><b>　　{</b></p><p>　　int i,j=1;</p

96、><p>　　struct lnode *p,*q,*p0;</p><p>　　p=p0=head;</p><p>　　q=(struct lnode *)malloc(len);</p><p>　　printf("請選擇插入的位置：\n");</p><p>　　scanf("%d&q

97、uot;,&i);</p><p>　　printf("請輸入要插入元素的值：\n");</p><p>　　scanf("%d",&q->a);</p><p>　　while(j<i-1)</p><p><b>　　{</b></p>

98、<p>　　p=p->next;</p><p><b>　　j++;</b></p><p><b>　　}</b></p><p>　　q->next=p->next;</p><p>　　p->next=q;</p><p>&l

99、t;b>　　free(p);</b></p><p>　　printf("插入成功！\n");</p><p>　　printf("插入后鏈表為：\n");</p><p><b>　　/*do</b></p><p><b>　　{</b>

100、</p><p>　　printf("%d ",p0->a);</p><p>　　p0=p0->next;</p><p>　　}while(p0!=null);</p><p>　　printf("\n");</p><p>　　free(p0);*/</

101、p><p>　　return(head);</p><p><b>　　}</b></p><p>　　struct lnode *listdel()//刪除鏈表元素</p><p><b>　　{</b></p><p><b>　　int j;</b>&

102、lt;/p><p>　　struct lnode *p,*q,*p0;</p><p>　　p=q=p0=head;</p><p>　　printf("請輸入要刪除的元素：\n");</p><p>　　scanf("%d",&j);</p><p>　　while(p-&

103、gt;a!=j)</p><p><b>　　{</b></p><p><b>　　q=p;</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　q->next=p->next

104、;</p><p><b>　　free(p);</b></p><p>　　printf("刪除成功！\n");</p><p>　　printf("刪除后鏈表為：\n");</p><p><b>　　do</b></p><p>

105、<b>　　{</b></p><p>　　printf("%d ",p0->a);</p><p>　　p0=p0->next;</p><p>　　} while(p0!=null);</p><p>　　printf("\n"); </p><

106、;p><b>　　free(q);</b></p><p><b>　　free(p0);</b></p><p>　　return(head);</p><p><b>　　}</b></p><p>　　#include<stdio.h></p>

107、;<p>　　#define null 0;</p><p>　　struct qnode{</p><p><b>　　int data;</b></p><p>　　struct qnode *next;</p><p><b>　　};</b></p><p&

108、gt;　　struct linkqueue{</p><p>　　struct qnode *front;</p><p>　　struct qnode *rear;</p><p><b>　　}q;</b></p><p>　　struct linknode *qinit();</p><p>

109、;　　struct linknode *qinsert();</p><p>　　struct linknode *qdel();</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int n;</b></p><p&

110、gt;<b>　　do{</b></p><p>　　printf("=====鏈隊列練習=====\n");</p><p>　　printf(" 請選擇操作：\n");</p><p>　　printf(" 1、建立鏈隊列\(zhòng)n");</p><p>　

111、　printf(" 2、插入新元素\n");</p><p>　　printf(" 3、刪除元素\n");</p><p>　　printf("====================\n");</p><p>　　scanf("%d",&n);</p>&

112、lt;p><b>　　switch(n)</b></p><p><b>　　{</b></p><p>　　case 1:qinit();break;</p><p>　　case 2:qinsert();break;</p><p>　　case 3:qdel();break;</p

113、><p>　　default:printf("選擇錯誤，請確認輸入！\n");break;</p><p><b>　　}</b></p><p>　　}while(1);</p><p><b>　　}</b></p><p>　　struct linkno

114、de *qinit()</p><p><b>　　{</b></p><p>　　q.front=q.rear=(int *)malloc(sizeof(int));</p><p>　　q.front->next=null;</p><p>　　printf("建立空隊列成功！\n");&l

115、t;/p><p><b>　　}</b></p><p>　　struct linknode *qinsert()</p><p><b>　　{</b></p><p>　　int e,n,i;</p><p>　　struct qnode *p; </p>

116、<p>　　p=(int *)malloc(sizeof(int));</p><p>　　printf("請輸入要插入元素的個數(shù)：");</p><p>　　scanf("%d",&n);</p><p>　　for(i=0;i<n;i++)</p><p><b>

117、　　{</b></p><p>　　printf("請輸入要插入元素的值：");</p><p>　　scanf("%d",&e);</p><p>　　p->data=e;</p><p>　　p->next=null;</p><p>　　q.

118、rear->next=p;</p><p>　　printf("插入%d成功，還剩%d個元素為插入！\n",e,n-1);</p><p><b>　　}</b></p><p>　　printf("插入完成！\n");</p><p><b>　　}</b&

119、gt;</p><p>　　struct linknode *qdel()</p><p><b>　　{</b></p><p><b>　　int e;</b></p><p>　　struct qnode *p;</p><p>　　p=q.front->next

120、;</p><p>　　e=p->data;</p><p>　　q.front->next=p->next;</p><p><b>　　free(p);</b></p><p>　　printf("刪除元素%d成功！\n",e);</p><p><

121、b>　　}</b></p><p>　　#include<stdio.h></p><p>　　int creat();</p><p>　　int insert();</p><p>　　int del();</p><p>　　int a[20];</p><p&g

122、t;<b>　　int m;</b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　int n; </b></p><p><b>　　do{</b></p><p>

123、　　printf("=====順序表練習=====\n");</p><p>　　printf(" 請選擇操作：\n");</p><p>　　printf(" 1、建立順序表\n");</p><p>　　printf(" 2、插入新元素\n");</p>&l

124、t;p>　　printf(" 3、刪除元素\n");</p><p>　　printf("====================\n");</p><p>　　scanf("%d",&n);</p><p><b>　　switch(n)</b></p>

125、<p><b>　　{</b></p><p>　　case 1:creat();break;</p><p>　　case 2:insert();break;</p><p>　　case 3:del();break;</p><p>　　default:printf("選擇錯誤，請確認輸入！&

126、quot;);break;</p><p><b>　　}</b></p><p>　　}while(1);</p><p><b>　　}</b></p><p>　　int creat()</p><p><b>　　{</b></p>

127、<p><b>　　int i;</b></p><p>　　printf("請輸入順序表長度：");</p><p>　　scanf("%d",&m);</p><p>　　printf("請初始化順序表：");</p><p>　　for

128、(i=0;i<m;i++)</p><p>　　scanf("%d",&a[i]);</p><p>　　printf("您建立的數(shù)組如下：\n");</p><p>　　for(i=0;i<m;i++)</p><p>　　printf("a[%d]=%d "

129、,i,a[i]);</p><p>　　printf("\n");</p><p>　　return(0);</p><p><b>　　}</b></p><p>　　int insert()</p><p><b>　　{</b></p>

130、<p>　　int i,j,x; </p><p>　　printf("請選擇插入的位置及元素：");</p><p>　　scanf("%d%d",&i,&x);</p><p>　　for(j=m;j>i-1;j--)</p><p>　　a[j]=a[j-1];&

131、lt;/p><p><b>　　a[i-1]=x;</b></p><p>　　printf("您插入后的數(shù)組如下：\n");</p><p>　　for(i=0;i<m+1;i++)</p><p>　　printf("%d ",a[i]);</p><p

132、>　　printf("\n");</p><p>　　return(0);</p><p><b>　　}</b></p><p><b>　　int del()</b></p><p><b>　　{</b></p><p>

133、<b>　　int i,j;</b></p><p>　　printf("請選擇要刪除位置的元素：");</p><p>　　scanf("%d",&i);</p><p>　　for(j=i-1;j<m;j++)</p><p>　　a[j]=a[j+1];<

134、/p><p>　　printf("您刪除后的數(shù)組如下：\n");</p><p>　　for(i=0;i<m;i++)</p><p>　　printf("%d ",a[i]);</p><p>　　printf("\n");</p><p>　　retu

135、rn(0);</p><p><b>　　}</b></p><p>　　#include<stdio.h></p><p>　　#define stack_init_size 100;</p><p>　　#define stackincrement 10;</p><p>　　#d

136、efine len sizeof(int); </p><p>　　struct sqstack{</p><p>　　int *base;</p><p><b>　　int *top;</b></p><p>　　int stacksize;</p><p><b>　　};<

137、/b></p><p>　　struct sqstack s;</p><p>　　struct sqstack *initstack();</p><p>　　struct sqstack *push();</p><p>　　struct sqstack *pop();</p><p>　　void main