C語言隊列課件

1、C語言隊列課件C語言隊列課件隊列隊列只允許在表的一端進(jìn)行插入，而在另一端只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。進(jìn)行刪除。隊頭隊頭允許刪除的一端允許刪除的一端隊尾隊尾允許插入的一端允許插入的一端隊列的概念隊列的概念出隊出隊入隊入隊隊頭隊頭隊尾隊尾a1 a2 an . 隊列是先進(jìn)先出表隊列是先進(jìn)先出表3隊列的基本運(yùn)算：隊列的基本運(yùn)算： 創(chuàng)建一個空隊列創(chuàng)建一個空隊列Queue createEmptyQueue ( void ) 判隊列是否為空隊列判隊列是否為空隊列int isEmptyQueue ( Queue qu ) 往隊列中插入一個元素往隊列中插入一個元素void enQueue (

2、Queue qu, DataType x ) 從隊列中刪除一個元素從隊列中刪除一個元素void deQueue ( Queue qu ) 求隊列頭部元素的值求隊列頭部元素的值DataType frontQueue ( Queue qu ) 隊列的運(yùn)算隊列的運(yùn)算44.5 4.5 隊列的實(shí)現(xiàn)隊列的實(shí)現(xiàn)4.5.1. 順序隊列順序隊列4.5.2. 鏈隊列鏈隊列54.5.1 4.5.1 順序隊列順序隊列 隊列的順序存儲結(jié)構(gòu)簡稱為順序隊列。順序隊隊列的順序存儲結(jié)構(gòu)簡稱為順序隊列。順序隊列實(shí)際上是運(yùn)算受限的順序表。列實(shí)際上是運(yùn)算受限的順序表。 由于隊列的隊頭和隊尾的位置均是變化的，因由于隊列的隊頭和隊尾的位

3、置均是變化的，因而要設(shè)置兩個指針，分別指示當(dāng)前隊頭元素和隊尾而要設(shè)置兩個指針，分別指示當(dāng)前隊頭元素和隊尾元素在向量空間中的位置。元素在向量空間中的位置。6#define MAXNUM 100#define MAXNUM 100struct SeqQueuestruct SeqQueue datatype qMAXNUM; datatype qMAXNUM; int f,r; int f,r; ; ;typedef struct SeqQueue typedef struct SeqQueue * *PSeqQueue;PSeqQueue;PSeqQueue sq;PSeqQueue sq;順序

4、隊列的定義順序隊列的定義4.5.1 4.5.1 順序隊列順序隊列7fr76543210k1k2k3frrfk8k7隊列空隊列空隊列數(shù)組越界隊列數(shù)組越界順序隊列順序隊列約定約定隊列滿隊列滿k1k2k3fk8rk4k5k6k7開始：開始： sq-f=0;sq-f=0; sq-r=0; sq-r=0; 入隊：入隊： sq-datasq-r=x; sq-datasq-r=x; sq-r+; sq-r+; 出隊：出隊： sq-f+; sq-f+; 順序隊列的入隊和出隊順序隊列的入隊和出隊4.5.1 4.5.1 順序隊列順序隊列9元素個數(shù)（隊列長度）元素個數(shù)（隊列長度）: :（sq-r) - (sq-f)

5、sq-r) - (sq-f) 若（若（sq-r) - (sq-f)=0 sq-r) - (sq-f)=0 ，則隊列長度，則隊列長度為為0 0，即空隊列。再出隊會，即空隊列。再出隊會“下溢下溢” 若若 (sq-r)-(sq-f)=MAXNUM(sq-r)-(sq-f)=MAXNUM，則隊滿。，則隊滿。隊滿時再入隊會隊滿時再入隊會“上溢上溢”4.5.1 4.5.1 順序隊列順序隊列1076543210frk1k2k3frrfk6k5隊列空隊列空隊列數(shù)組越界隊列數(shù)組越界順序隊列順序隊列4.5.1 4.5.1 順序隊列順序隊列假上溢：當(dāng)前隊列并不滿，但不能入隊。假上溢：當(dāng)前隊列并不滿，但不能入隊。每次

6、出隊時向前移一位置。每次出隊時向前移一位置。大量移動元素大量移動元素循環(huán)隊列循環(huán)隊列原因原因:被刪除元素的空間沒有再被使用被刪除元素的空間沒有再被使用解決解決:12采用循環(huán)隊列克服采用循環(huán)隊列克服“假上溢假上溢”。sq-rsq-fMAXNUM-101指針移動方向指針移動方向13入隊：入隊：if (sq-r+1=MAXNUM)if (sq-r+1=MAXNUM) sq-r=0; sq-r=0; else sq-r+; else sq-r+;利用模運(yùn)算利用模運(yùn)算 sq-r=(sq-r+1)%MAXNUM sq-r=(sq-r+1)%MAXNUM 出隊：出隊： sq-f=(sq-f+1)%MAXNU

7、Msq-f=(sq-f+1)%MAXNUM采用循環(huán)隊列克服采用循環(huán)隊列克服“假上溢假上溢”4.5.1 4.5.1 順序隊列順序隊列14 某一元素出隊后，若頭指針已從后面追上尾指針，某一元素出隊后，若頭指針已從后面追上尾指針，則當(dāng)前隊列為空：則當(dāng)前隊列為空： sq-f=sq-rsq-f=sq-r 某一元素入隊后，若尾指針已從后面追上頭指針，某一元素入隊后，若尾指針已從后面追上頭指針，則當(dāng)前隊列為滿：則當(dāng)前隊列為滿： sq-f=sq-rsq-f=sq-r 因此，僅憑因此，僅憑 sq-f=sq-r sq-f=sq-r 是無法區(qū)別是無法區(qū)別隊列空還是隊列滿。隊列空還是隊列滿。 判斷隊空和隊滿判斷隊空和

8、隊滿4.5.1 4.5.1 順序隊列順序隊列15解決辦法解決辦法標(biāo)志變量標(biāo)志變量測試尾指針在循環(huán)意義測試尾指針在循環(huán)意義下是否等于頭指針下是否等于頭指針 判別隊列滿的條件：判別隊列滿的條件： (sq-r+1)%MAXNUM=sq-f(sq-r+1)%MAXNUM=sq-f使使 sq-f=sq-r sq-f=sq-r 成為判斷隊列空的條件成為判斷隊列空的條件4.5.1 4.5.1 順序隊列順序隊列元素個數(shù)是元素個數(shù)是MAXNUM-116sq.rearsq.frontk1k2k7k6k5k4k3sq.frontsq.rear圖(a)空隊列圖(b)隊列滿 圖4.9 循環(huán)隊列4.5.1 4.5.1 順

9、序隊列順序隊列在循環(huán)隊列上實(shí)現(xiàn)五種基本運(yùn)算：在循環(huán)隊列上實(shí)現(xiàn)五種基本運(yùn)算： 1.1.置空隊置空隊 2.2.判隊空判隊空 3.3.取隊頭元素取隊頭元素 4.4.入隊入隊 5.5.出隊出隊18循環(huán)隊列front= n-3 an-3an-2012MaxQsize-1rear=n-1n-3rear= n-1an-3an-20.1.front=n-3n-2插入元素 ： rear順時針移動一位front=n-3 an-3an-2012MaxQsize-1rear=0 xn-3an-3rear=0an-20.1n-1.front=n-3n-2xrear = (rear+1) MOD MaxQSize刪除元素

10、：front順時針移動一位front = (front+1) MOD MaxQSize;rear0front=9.1.CD刪除刪除Crearfront=00.1.D循環(huán)隊列 front指定隊首位置，刪除一個元素就將front順 時針移動一位； rear指向元素要插入的位置，插入一個元素就將rear順時針移動一位； count存放隊列中元素的個數(shù)，當(dāng)count等于MaxQSize時，不可再向隊列中插入元素。 隊空：count=0 隊滿：count= MaxQSize數(shù)組隊列實(shí)現(xiàn)在隊列的頭部取出元素。普通的隊列由于空間利用率不高，所以我們一般都用循環(huán)隊列。循環(huán)隊列中最重要的的兩個操作就是判斷是否為

11、空和是否已滿。當(dāng)head=tail時，表示隊列為空。當(dāng)(tail+1)%MAX_SIZE = head，表示隊列已滿。我判斷隊滿的方法：犧牲一個單元來區(qū)分對空和隊滿，入隊時少用一個隊列單元，相當(dāng)于浪費(fèi)一個存儲空間?！瓣狀^指針的隊尾指針的下一位置作為隊滿的標(biāo)志”。進(jìn)隊列 EnQueue(int value) /要先判斷隊列是否已滿 if (tail + 1) % QUEUE_SIZE = head) printf(隊列已滿，無法從隊尾插入元素n); else queuetail = value; tail = (tail + 1) % QUEUE_SIZE; /出隊列 int DeQueue三

12、int temp; if (tail = head) printf(隊列為空，元素?zé)o法出隊列n); else temp = queuehead;head = (head + 1) % QUEUE_SIZE;printf(%dn,temp);return temp; /判斷隊列是否為空 int IsEmpty三 if (head = tail) printf(隊列為空n); return 1; printf(隊列不為空n); return 0; 判斷隊列是否已滿 /* * 我這里判斷隊滿的的方法： 犧牲一個單元來區(qū)分隊空和隊滿，入隊時少用一個隊列單元。如果數(shù)組的大小為Size,那么實(shí)際只能存放(

13、Size-1)個元素。（這是比較常用的判滿的方式） * */ int IsFull三 if (tail + 1) % QUEUE_SIZE = head) printf(隊列已滿n); return 1; printf(隊列未滿n); return 0; /打印出隊列元素 void PrintQueue三 for (int i = head; i tail; i+) printf(%d ,queuei); printf(n); #include #define QUEUE_SIZE 200 int queueQUEUE_SIZE;int head=0;/頭指針int tail=0;/尾指針 i

14、nt main講義 EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8); PrintQueue三; DeQueue三;DeQueue三; PrintQueue三; return 0; 1. 1. 置空隊置空隊PSeqQueue createEmptyQueue_seq( void ) PSeqQueue sq; sq = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (sq=NULL)printf(Out of space! n);else sq-f = 0; sq-r = 0;return

15、 (sq); 302. 2. 判隊空判隊空int isEmptyQueue_seq( PSeqQueue sq ) return (sq-f = sq-r); 313. 3. 取隊頭元素取隊頭元素DataType frontQueue_seq( PSeqQueue sq )/* 對非空隊列對非空隊列,求隊列頭部元素求隊列頭部元素 */ return (sq-qsq-f); 324. 4. 入隊入隊void enQueue_seq( PSeqQueue sq, DataType x )/* 在隊列中插入一元素在隊列中插入一元素x */ if( (sq-r + 1) % MAXNUM = sq-f

16、 ) printf( Full queue.n ); else sq-qsq-r = x; sq-r = (sq-r + 1) % MAXNUM; 335. 5. 出出隊隊void deQueue_seq( PSeqQueue sq )/* 刪除隊列頭部元素刪除隊列頭部元素 */ if( sq-f = sq-r )printf( Empty Queue.n ); elsesq-f = (sq-f + 1) % MAXNUM; 344.5.2 4.5.2 鏈隊列鏈隊列 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。表頭刪除和表

17、尾插入的單鏈表。 顯然僅有單鏈表的頭指針不便于在表尾做插入操作，顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表上的最后一個結(jié)點(diǎn)。為此再增加一個尾指針，指向鏈表上的最后一個結(jié)點(diǎn)。于是，一個鏈隊列由一個頭指針和一個尾指針唯一地確于是，一個鏈隊列由一個頭指針和一個尾指針唯一地確定。定。35 k0 k1 k2 kn-1. 圖圖4.10 隊列的鏈接表示隊列的鏈接表示plqu fr struct Node; typedef struct Node *pNode; struct Node DataType info; pNodelink; ; struct LinkQueue

18、PNodef; PNoder; ; typedef struct LinkQueue, *PLinkQueue;隊列的鏈接表示隊列的鏈接表示37 * *plquplqu頭結(jié)點(diǎn)頭結(jié)點(diǎn)plqu-fplqu-r 頭結(jié)點(diǎn)頭結(jié)點(diǎn) 隊頭結(jié)點(diǎn)隊頭結(jié)點(diǎn)plqu-fplqu-fplqu-rplqu-r空和非空的鏈隊列空和非空的鏈隊列. 384.5.2 4.5.2 鏈隊列鏈隊列在鏈隊列上實(shí)現(xiàn)的五種基本運(yùn)算如下：在鏈隊列上實(shí)現(xiàn)的五種基本運(yùn)算如下： 1. 1. 置空隊置空隊 2. 2. 判隊空判隊空 3. 3. 取隊頭結(jié)點(diǎn)數(shù)據(jù)取隊頭結(jié)點(diǎn)數(shù)據(jù) 4. 4. 入隊入隊 5. 5. 出隊出隊391. 1. 置空隊（算法）置空

19、隊（算法）PLinkQueue createEmptyQueue_link( ) PLinkQueue plqu; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue); if (plqu!=NULL) plqu-f = NULL; plqu-r = NULL; elseprintf(Out of space! n);return (plqu); 402. 2. 判隊空判隊空（算法）（算法）int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL); 413. 3. 取隊頭結(jié)點(diǎn)

20、數(shù)據(jù)取隊頭結(jié)點(diǎn)數(shù)據(jù)（算法）（算法）DataType frontQueue_link( PLinkQueue plqu )/* 在非空隊列中求隊頭元素在非空隊列中求隊頭元素 */ return (plqu-f-info); 424. 4. 入隊入隊（算法）（算法）void enQueue_link( PLinkQueue plqu, DataType x ) PNode p; p = (PNode )malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!); else p-info = x; p-link = NU

21、LL; if (plqu-f = NULL) plqu-f = p; plqu-r = p; else plqu-r-link = p; plqu-r = p; 435. 5. 出出隊隊（算法）（算法）void deQueue_link( PLinkQueue plqu ) PNode p; if( plqu-f = NULL ) printf( Empty queue.n ); else p = plqu-f; plqu-f = plqu-f-link; free(p);44農(nóng)夫過河問題農(nóng)夫過河問題 : : 一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河

22、的南岸。他要把這些東西全部運(yùn)到北岸。問題處河的南岸。他要把這些東西全部運(yùn)到北岸。問題是他面前只有一條小船，船小到只能容下他和一件是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農(nóng)夫能撐船。顯然，因?yàn)槔悄艹匝?，物品，另外只有農(nóng)夫能撐船。顯然，因?yàn)槔悄艹匝?，而羊愛吃白菜，所以農(nóng)夫不能留下羊和白菜自己離而羊愛吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開。好在狼屬于食肉開，也不能留下狼和羊自己離開。好在狼屬于食肉動物，它不吃白菜。請問農(nóng)夫該采取什么方案才能動物，它不吃白菜。請問農(nóng)夫該采取什么方案才能將所有的東西運(yùn)過河將所有的東西運(yùn)過河? ? 4.6 4.6 隊列的應(yīng)用隊

23、列的應(yīng)用農(nóng)夫過河問題農(nóng)夫過河問題* *45 用計算機(jī)實(shí)現(xiàn)上述求解的搜索過程可以采用兩種不同的用計算機(jī)實(shí)現(xiàn)上述求解的搜索過程可以采用兩種不同的策略：策略： 一種是廣度優(yōu)先一種是廣度優(yōu)先(breadth_first)(breadth_first)搜索，搜索， 另一種是深度優(yōu)先另一種是深度優(yōu)先(depth_first)(depth_first)。實(shí)現(xiàn)這兩種策略所依賴的數(shù)據(jù)結(jié)構(gòu)正好是前面介紹實(shí)現(xiàn)這兩種策略所依賴的數(shù)據(jù)結(jié)構(gòu)正好是前面介紹的隊列和棧。的隊列和棧。本節(jié)討論隊列的應(yīng)用，所以下面重點(diǎn)介紹廣度優(yōu)先的本節(jié)討論隊列的應(yīng)用，所以下面重點(diǎn)介紹廣度優(yōu)先的策略。策略。 4.6 4.6 隊列的應(yīng)用隊列的應(yīng)用農(nóng)夫

24、過河問題農(nóng)夫過河問題* *46模擬農(nóng)夫過河問題：用四位二進(jìn)制數(shù)分別順序表示農(nóng)模擬農(nóng)夫過河問題：用四位二進(jìn)制數(shù)分別順序表示農(nóng) 夫、狼、白菜和羊的位置。夫、狼、白菜和羊的位置。 0表示在南岸，表示在南岸，1表示在北岸表示在北岸Path：15，6，14，2，11，1，9，0從初始狀態(tài)從初始狀態(tài)0到最終狀態(tài)到最終狀態(tài)15的動作序列為：的動作序列為： 隊列的應(yīng)用 醫(yī)院門診部病人管理系統(tǒng) 工作過程：當(dāng)一病人進(jìn)入門診室時，負(fù)責(zé)掛號的義務(wù)人員就根據(jù)觀察和簡短詢問發(fā)給他一個從0（病危）到4（一般）變化的優(yōu)先數(shù)，讓他到相應(yīng)優(yōu)先數(shù)隊列中去排隊等待 。當(dāng)一醫(yī)生空閑時，就根據(jù)優(yōu)先數(shù)和等待時間，通知某候診病人就診。 原則

25、：優(yōu)先級高的先考慮，同一優(yōu)先級中，則先來先考慮。48隊列的應(yīng)用 醫(yī)院門診部病人管理系統(tǒng) 組織數(shù)據(jù)的方式數(shù)據(jù)結(jié)構(gòu)分析： 系統(tǒng)中的數(shù)據(jù)：病人的姓名，優(yōu)先數(shù)，到達(dá)時間 49隊列的應(yīng)用 醫(yī)院門診部病人管理系統(tǒng)4組織方式一：若病人以其到達(dá)門診部的先后次序組織到一個隊列，則具體到達(dá)時間可不考慮。到達(dá)次序 優(yōu)先數(shù)姓名 1 2 3 4 5 6 7 2 3 0 3 0 2 1林文鄭江魯明陳真李軍王紅張兵這樣的單隊列對按就診原則來確這樣的單隊列對按就診原則來確定下一就診病人是很不方便的，定下一就診病人是很不方便的，還將破壞隊列的操作原則。還將破壞隊列的操作原則。50隊列的應(yīng)用 醫(yī)院門診部病人管理系統(tǒng)4組織方式二：

26、多個隊列（隊列數(shù)組）：隊列數(shù)組的第i個元素是優(yōu)先級為i的隊列。優(yōu)先數(shù)隱含在隊列的編號中。魯明魯明01234李軍李軍張兵張兵林文林文王紅王紅鄭江鄭江陳真陳真51隊列的應(yīng)用 醫(yī)院門診部病人管理系統(tǒng)就病人管理系統(tǒng)來說，功能菜單中至少有以下兩個功能：就病人管理系統(tǒng)來說，功能菜單中至少有以下兩個功能：（1）病人登記）病人登記AddPatient( ) 提示并讀入病人優(yōu)先數(shù)提示并讀入病人優(yōu)先數(shù)i； 提示并讀入病人名提示并讀入病人名 調(diào)用鏈隊列的入隊算法調(diào)用鏈隊列的入隊算法EnQueue三三 （2）確定下一個就診病人）確定下一個就診病人 GetPatient( ) 按就診原則確定和顯示下一個就診病人名按就診

27、原則確定和顯示下一個就診病人名 即：若優(yōu)先數(shù)即：若優(yōu)先數(shù)0的隊列非空，則下一就診病人為隊首元素，否則，考慮優(yōu)先數(shù)的隊列非空，則下一就診病人為隊首元素，否則，考慮優(yōu)先數(shù)1的隊列；的隊列；依次類推。依次類推。 52線線性性表表存儲結(jié)構(gòu)存儲結(jié)構(gòu) 運(yùn)運(yùn) 算算 隊列隊列 鏈鏈 表表順序表順序表 棧棧 順序棧順序棧 鏈鏈 棧棧 順序隊列順序隊列 鏈隊列鏈隊列 線性表小結(jié)線性表小結(jié)53順序表順序表typedef int datatype ;#define MAXNUM 1024typedef struct datatype dataMAXNUM ;int last ; sequenlist;54鏈鏈 表表t

28、ypedef int datatype;typedef struct node datatype data;struct node *next; linklist;linklist *head, *p;55 順序棧順序棧 typedef int datatype;typedef int datatype;#define MAXNUM 64#define MAXNUM 64typedef structtypedef struct datatype dataMAXNUM; datatype dataMAXNUM; int top; int top; PSeqStack; PSeqStack;PSe

29、qStack PSeqStack * *s;s;56 鏈鏈 棧棧 typedef int datatype;typedef int datatype;typedef struct nodetypedef struct node datatype data; datatype data; struct node struct node * *next;next; linkstack; linkstack;linkstack linkstack * *top;top;57 順序隊列順序隊列 typedef structtypedef struct datatype dataMAXNUM; data

30、type dataMAXNUM; int f,r; int f,r; sequeue; sequeue;sequeue sequeue * *sq;sq;58 鏈隊列鏈隊列 typedef structtypedef struct linklist linklist * *f , f , * *r;r; linkqueue; linkqueue;linkqueue linkqueue * *q;q;592.6 2.6 設(shè)計一算法，逆置帶頭結(jié)點(diǎn)的動態(tài)單鏈表設(shè)計一算法，逆置帶頭結(jié)點(diǎn)的動態(tài)單鏈表 L L。void reverse(linklist *L) /*假設(shè)鏈表帶有頭結(jié)點(diǎn)假設(shè)鏈表帶有頭結(jié)點(diǎn)*/

31、 linklist *p,*s; p=L-next; /*用用p指向當(dāng)前結(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)*/ L-next=NULL; while (p) s=p; /*用用s保存當(dāng)前結(jié)點(diǎn)地址保存當(dāng)前結(jié)點(diǎn)地址*/ p=p-next; /*鏈表指針鏈表指針p后移后移*/ /*將當(dāng)前結(jié)點(diǎn)鏈到表頭將當(dāng)前結(jié)點(diǎn)鏈到表頭*/ s-next=L-next; L-next=s; /*reverse*/ 602.10 2.10 已知，由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素已知，由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其它字符），試編寫算法構(gòu)造三個以（如：字母字符、數(shù)字字符和其它字符），試

32、編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。表中的結(jié)點(diǎn)空間作為這三個表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。linklist *ra,*rb,*rc;void sort(linklist *head) linklist *s,*p=head; /*建立三個空的循環(huán)鏈表建立三個空的循環(huán)鏈表*/ ra=malloc(sizeof(linklist); ra-next=ra; rb=malloc(sizeof(linklist); rb-next=rb; rc=m

33、alloc(sizeof(linklist); rc-next=ra;61 while (p) s=p; p=p-next; if (s-data=0)&(s-datanext=ra-next; ra-next=s; ra=s; /*將數(shù)字字符結(jié)點(diǎn)鏈接到將數(shù)字字符結(jié)點(diǎn)鏈接到A表表*/ else if (s-data=a)&(s-datadata=A)&(s-datanext=rb-next; rb-next=s; rb=s; /*將字母字符結(jié)點(diǎn)鏈接到將字母字符結(jié)點(diǎn)鏈接到B表表*/ else s-next=rc-next; rc-next=s; rc=s; /*將其它字符

34、結(jié)點(diǎn)鏈接到將其它字符結(jié)點(diǎn)鏈接到C表表*/ /*while*/ /*sort*/623.3 設(shè)單鏈表中存放著設(shè)單鏈表中存放著n個字符，試編寫算法，判斷該字個字符，試編寫算法，判斷該字符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。int Judgement1(linklist *head)/*若對稱返回若對稱返回 1，否則返回，否則返回 0*/ PSeqStack *s; linklist *p; int i, n=0; /*n為計數(shù)器，記錄鏈表的長度為計數(shù)器，記錄鏈表的長度*/ p=head; /*先用循環(huán)求出鏈表的長度先用循環(huán)求出鏈表的長度

35、*/ while(p) n+ ; p=p-next ; 633.3 設(shè)單鏈表中存放著設(shè)單鏈表中存放著n個字符，試編寫算法，判斷該字個字符，試編寫算法，判斷該字符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。SETNULL(s); /*設(shè)置空棧設(shè)置空棧 s*/p=head;/*先將一半字符進(jìn)棧先將一半字符進(jìn)棧*for (i=1;idata); p=p-next; /*若字符個數(shù)為基數(shù)，則跳過中間的字符若字符個數(shù)為基數(shù)，則跳過中間的字符*if (n%2) p=p-next;643.3 設(shè)單鏈表中存放著設(shè)單鏈表中存放著n個字符，試編寫算法，判斷該字

36、個字符，試編寫算法，判斷該字符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。 /*當(dāng)字符串未掃描完畢且棧非空時進(jìn)行匹配當(dāng)字符串未掃描完畢且棧非空時進(jìn)行匹配*/ while(p&!EMPTY(s) if (p-data!=POP(s) break; else p=p-next; if (! p&EMPTY(s) return 1; else return 0;/*Judgement*/653.4 設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對Judgement2Judgement2三三 / /* *判斷表達(dá)式是否配對，表達(dá)式以判斷表達(dá)式是否配對，表達(dá)式以#結(jié)束結(jié)束* */ / PSeqStack sta; PSeqStack sta; char ch,chpop; char ch,chpop; int valid; int valid; SETNULL(&sta); SETNULL(&sta); PUSH(&sta,#); / PUSH(&sta,#); /* *把把#放在棧底放在棧底* */ / ch=getchar ch=getchar三三; ; valid=TRUE; valid=TRUE; / /* *validva