棧和隊列
這兩者都是重要的數據結構，都是線性結構。它們在日後的軟件開發中有著重大作用。後面會有實例講解。
兩者區別和聯系，其實總結起來就一句。棧，後進先出；隊列，先進先出。
可以將棧與隊列的存儲空間比作一個只夠一個身位的水管。
棧的水管，有一頭被堵住了。所以當人們進去後，想出來就只能讓最靠近出口的那位先出去，依次推出。（後進先出）。
隊列的水管，類似單向車道。所以當人們進去後，想出來就只能一直向前，走出來，不可以從入口出來。（先進先出）。
所以，道理還是很簡單的。接下來就是學習一些專屬函數就ok了。
實例090 應用棧實現進制轉換
問題：應用棧實現進制轉換，可以將十進制數轉換為其他進制數。
邏輯：首先我們來想一下進制轉換的算法，就如之前提到的，不斷地取余，求商。依次循環進行，再按順序輸出，獲取最終結果。
代碼：
1 #include<stdio.h>
2 typedef struct
3 {
4 DataType *base;
5 //有人問DataType是什麼東東。
6 //DataType是一種數據類型，是數據結構專屬。采取的是類C的語言。所以需要將其映射為C數據類型。
7 DataType *top;
8 int stacksize;
9 //提醒一句，stack是棧的英文。
10 }SeqStack;
11
12
13 //************接下來就是重點
14 void Initial(SeqStack *s)
15 //棧的初始化函數，構造一個空棧S。
16 {
17 s->base=(DataType *)malloc(STACK_SIZE *sizeof(DataType));
18 //類似於鏈表的獲取存儲空間，連使用的函數都一樣。
19 //注意，我這裡使用的是base。所以，這個棧是“向上生長”的棧。
20 if(!s->base)
21 exit(-1);
22 //exit()是一個退出函數，其參數是退出狀態代碼。（0是正常退出狀態碼）
23 s->top=s->base;
24 //初始化時，棧內為空。從而可以這樣初始化其中的top變量。
25 s->stacksize=STACK_SIZE;
26 //獲取存儲空間大小。
27 }
28 int IsEmpty(SeqStack *S)
29 //判斷棧是否為空的函數
30 {
31 return S->top==S->base;
32 //返回值為判斷結果。
33 }
34 int IsFull(SeqStack *S)
35 //判斷棧是否滿了。
36 {
37 return S->top-S->base==STACK_SIZE-1;
38 //注意看，中間那個是減號。
39 }
40 void Push(SeqStack *S,DataType x)
41 //棧的入棧函數
42 {
43 if(IsFull(S))
44 {
45 printf("棧上溢出");
46 exit(1);
47 }
48 *S->top++=x;
49 //入棧時，切記 棧指針top，“先壓後加”。
50 }
51 DataType Pop(SeqStack *S)
52 //棧的出棧函數
53 {
54 if(IsEmpty(S))
55 {
56 printf("棧為空");
57 exit(1);
58 }
59 return *--S->top;
60 //注意上面是*(--s),別問我*--是什麼。出棧時，切記 棧指針to[，“先減後彈”。
61 }
62 DataType Top(SeqStack *S)
63 //棧頂變化函數。
64 //因為這個棧是從棧底構建的，所以棧底不變。變化的是棧頂。
65 {
66 if(IsEmpty(S))
67 {
68 printf("棧為空");
69 exit(1);
70 }
71 return *(S->top-1);
72 //改變棧頂地址。
73 }
74 //************以上是重點
75
76
77
78 void conversion(int N,int B)
79 //解決問題的進制轉換函數
80 {
81 int i;
82 SeqStack *S;
83 Initial(S);
84 //初始化棧S
85 while(N)
86 {
87 Push(S,N%B);
88 N=N/B;
89 }
90 //這個循環不用我講了吧。就知平時進制轉化的循環。
91 while(!IsEmpty(S))
92 {
93 i=Pop(S);
94 printf("%d",i);
95 //依次輸出棧中元素，其實就是我們的結果了。
96 }
97 }
98 void main()
99 //主函數不用細講。就是完成輸入，輸出，調用變換函數。
100 {
101 int n,d;
102 printf("Input the integer you want to transform:");
103 scanf("%d",&n);
104 printf("Input the integer of the system:");
105 scanf("%d",&d);
106 printf("result:");
107 conversion(n,d);
108 getch();
109 }
反思：棧的應用主要就是初始化、判斷空、判斷滿、入棧、出棧、棧頂六個函數。懂了這六個函數，應用就沒什麼了。
其中的技巧，代碼備注也提到了，比如：“先壓後加”等。不過這是針對這個棧的，一個“向上生長”的棧。
ps:其實還有用棧設置密碼、實現編輯程序等。但其中關於棧的部分基本大同小異，所以不再贅述。
如果，還有不懂，可以看看視屏。比如，張洪瑞與嚴蔚敏老師的視屏講解。（我不會告訴你，計算機考研的專業課可是要求嚴蔚敏老師的書。不過建議張洪瑞老師的視屏。主要嚴蔚敏老師講的。總感覺和我不是一個時代，事實上，也確實不是一個時代的。）
實例095 鏈隊列
問題：采取鏈式存儲法編程實現元素入隊、出隊以及將隊列中的元素顯示出來，要求整個過程以菜單選擇的形式實現。
邏輯：邏輯與棧沒有太多區別。將隊列的主要操作：創建、入隊、出隊、展示等功能分為多個函數進行。最後主函數實現題目要求的界面功能，及輸入，調用等功能。
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 typedef int ElemType;
4 //怕你們不懂之前說的DataType到底怎麼弄。這個就是一個例子。如果沒有這句話，你們會發現在VC裡，這個程序報錯報炸了。
5 typedef struct node
6 //這個結構體是用來存儲節點的。
7 {
8 ElemType data;
9 //節點數據
10 struct node *next;
11 //節點指向下一個節點地址
12 }quenode;
13 //這個節點結構體名稱。
14 struct quefr
15 //這個結構體用來存放隊列的隊首、隊尾地址指針。
16 {
17 quenode *front,*rear;
18 //quenode是什麼？額，就是我們之前定義的節點結構體。
19 };
20 void creat(struct quefr *q)
21 //定義函數creat，用來創建、初始化隊列。
22 {
23 quenode *h;
24 h=(quenode*)malloc(sizeof(quenode));
25 //獲取存儲空間，空間大小與quenode同步。
26 h->next=NULL;
27 //初始化h->next，為空。
28 q->front=h;
29 q->rear=h;
30 //初始化相關的quefr中數據，均為h。（隊列剛剛建立，那麼隊首，隊尾當然是同一個元素（結構體quenode的h））。
31 }
32 void enqueue(struct quefr *q,int x)
33 //定義入隊函數enqueue，用來實現元素x進入隊列q。
34 {
35 quenode *s;
36 //建立一個新的節點s，用來存儲新的入隊元素x。
37 s=(quenode*)malloc(sizeof(quenode));
38 //依舊是獲取存儲空間
39 s->data=x;
40 //向quenode結構體s導入新的入隊元素x。
41 s->next=NULL;
42 //s的指針域設置為空，作為初始化。
43 //也許，有人就問了。這裡設置為空，那麼隊列還怎麼連接起來啊。
44 //嗯。其實，有關連接方面的數據處理統一交給了quefr處理了。看下面就知道了。
45 q->rear->next=s;
46 //這裡實現了隊列元素的連接。切記，其中rear指針的數據類型可是quenode，所以可以實現調用next，可以實現連接。
47 q->rear=s;
48 //這時隊尾指針地址改變，因為增加了新的元素了。（這個程序設定是隊首地址不變的，向隊尾添加元素。）
49 //我這個程序設定的是隊尾入隊，隊首出隊。
50 }
51 ElemType dequeue(struct quefr *q)
52 //定義出隊函數dequeue，用來實現元素離開隊列q。（由於，之前提到的隊列性質，所以離開隊列的函數必然是隊首元素。）
53 {
54 quenode *p;
55 ElemType x;
56 //初始化，詳細參考上面的。
57 p=(quenode*)malloc(sizeof(quenode));
58 //有人說，初始化，入隊要獲取存儲空間就算了。為什麼出隊還要獲取存儲空間呢？
59 //其實，不是沒有道理。但是，1，我們對數據處理部分采用的一直都是結構體quenode，出隊是便於數據處理，當然還是得建立結構體，自然就要獲取存儲空間；2.很簡單一句，便於模塊化操作。
60 if(q->front==q->rear)
61 //判斷原隊列是否為空
62 {
63 printf("queue is NULL\n");
64 x=0;
65 }
66 else
67 {
68 p=q->front->next;
69 //賦值指針p，為q指針的下一個地址。
70 q->front->next=p->next;
71 //重新定位q->front->next，從而重新定位了q。
72 //這兩句也許有些人會看得有點暈，可以自己畫畫圖，或者參考一些之前的鏈表。主要就是把原來q的地址遺失了。重新定位q。
73 if(p->next==NULL)
74 //判斷原隊列是否就一個元素
75 q->rear=q->front;
76 //重新定位。很好奇這步有沒有必要。
77 x=p->data;
78 //獲取出隊列元素
79 free(p);
80 //釋放空白空間。
81 }
82 return(x);
83 //返回出隊元素
84 }
85 void display(struct quefr dq)
86 //定義函數display，用於展示隊列內的所有元素
87 {
88 quenode *p;
89 p=(quenode*)malloc(sizeof(quenode));
90 //為p分配存儲空間
91 p=dq.front->next;
92 //賦值p
93 while(p!=NULL)
94 //等同於判斷dq.front->next是否不為空
95 {
96 printf("data=%d\n",p->data);
97 //展示元素
98 p=p->next;
99 //將計數器指向下一個元素地址。
100 }
101 printf("end\n");
102 //最終輸出end，表示元素展示完畢。
103 }
104 main()
105 //建立主函數作為程序入口，實現題目要求的界面，以及輸入，調用，輸出。
106 {
107 struct quefr *que;
108 //定義*que的數據類型為struct quefr。
109 int n,i,x,sel;
110 void display();
111 void creat();
112 void enqueue();
113 ElemType dequeue();
114 do
115 {
116 printf("\n");
117 printf(" 1 creat queue \n");
118 printf(" 2 into the queue \n");
119 printf(" 3 delete from queue \n");
120 printf(" 4 display \n");
121 printf(" 5 exit \n");
122 printf("--------------------------------------------\n");
123 printf("please choose(1,2,3,4,5)\n");
124 scanf("%d",&sel);
125 switch(sel)
126 //采用switch判斷語句。
127 {
128 case 1:
129 que=(struct quefr*)malloc(sizeof(struct quefr));
130 creat(que);
131 printf(
132 "please input the number of element which do you want to creat:");
133 scanf("%d",&n);
134 for(i=1;i<=n;i++)
135 {
136 scanf("%d",&x);
137 enqueue(que,x);
138 }
139 break;
140 case 2:
141 printf("please input the element:");
142 scanf("%d",&x);
143 enqueue(que,x);
144 break;
145 case 3:
146 printf("x=%d\n",dequeue(que));
147 break;
148 case 4:
149 display(*que);
150 break;
151 case 5:
152 exit(0);
153 }
154 }
155 while(sel<=4);
156 //使用了do while循環。當sel為5時，sel>4，跳出循環。
157 }
反思：之所以將隊列的問題分為多個函數分別解決，是為了更好地模塊化操作。越發地感受到編程中模塊化操作的重要性，及好處。
實例096 循環緩沖區問題
ps：這個問題原本想將代碼打出來的，但我覺得之前隊列程序已經將主要架構顯現出來了。所以這個問題只會簡單一提，如果有人有需要，可以找我要。
邏輯：隊列的這個實例主要采用了循環隊列。可以很好地解決順序隊列“假溢出“的現象。這裡的循環隊列和之前循環鏈表一樣，就是將順序隊列構建成一個首尾相連的循環表。這樣可以更好地解決我之前在循環鏈表提到的循環存儲問題。
總結：到此為止，棧與隊列隊列的問題就差不多了。你會發現，這兩個就是差不多的東西。事實上，也就兩種特殊的順序表。操作思想是一致的。更重要的是體會到其中越發明顯的模塊化操作的思想。
串與廣義表
編程中的數據處理，無非數值處理與非數值處理，而非數值處理基本上是字符串數據。而現在計算機的硬件及其架構更多地是為了數值計算，所以相對而言，處理字符串數據就更為復雜了。其中廣義表是線性表的推廣，目前多用於人工智能等領域的表處理語言中。所以，有這方面興趣的可以多多關注。
實例098 簡單的文本編輯器
問題：要求實現三個功能：第一，要求對指定行輸入字符串；第二，刪除指定行的字符串；第三，顯示輸入的字符串的內容。
邏輯： 串其實就是由零個，或多個字符串組成的有限序列。
串的存儲方式由兩種：靜態存儲與動態存儲。 其中動態存儲結構又有兩種：鏈式存儲結構與堆結構存儲。這個問題的解決采用了鏈式存儲結構。
串的鏈式存儲結構是包含數據域和指針域的節點結構（是不是感覺很眼熟，和鏈表好像啊）。
由於每個節點只存放一個字符，太過浪費空間，為節省空間，故令每個節點存放若干個字符（題目中采用了50個字符為一塊），這種結構叫塊鏈結構。（題目中采用了這種結構）。
代碼：
1 #include<stdio.h>
2 #include<stdlib.h>
3 #define MAX 100
4 void Init();
5 void input();
6 void Delline();
7 void List();
8 int Menu();
9 //僅僅是函數聲明，由於主函數位於最後面，所以這五個語句去掉也可以。
10
11 typedef struct node
12 //定義存放字符串的節點。
13 {
14 char data[50];
15 struct node *next;
16 }strnode;
17
18 typedef struct head
19 //定義每行的頭結點。
20 {
21 int number;
22 int length;
23 strnode *next;
24 }headnode;
25 //如之前的一樣，兩個結構體，前者作為數據節點，存儲數據，後者則負責存儲的位置等數據以外的事情。
26
27 headnode Head[MAX];
28 //定義有100行。
29
30 void Init()
31 //定義函數Init，用來初始化串。
32 {
33 int i;
34 for(i=0;i<MAX;i++)
35 {
36 Head[i].length=0;
37 //設定長度均為0
38 }
39 }
40
41 int Menu()
42 //定義函數Menu，用來控制函數的人機交互界面。
43 {
44 int i;
45 i=0;
46 printf("1.Input\n");
47 printf("2.Delete\n");
48 printf("3.List\n");
49 printf("4.Exit\n");
50 while(i<=0||i>4)
51 {
52 printf("please choose\n");
53 scanf("%d",&i);
54 }
55 return i;
56 //返還用戶的輸入函數
57 }
58
59 void input()
60 //定義函數input，作為串的輸入函數。
61 {
62 strnode *p,*find();
63 int i,j,LineNum;
64 char ch;
65 while(1)
66 {
67 j=-1;
68 //這裡j=-1，其實，由於采用的是while(1)循環。計數器的增加在開頭 j++。所以，其實還是從j=0開始的。
69 printf("input the number of line(0-100),101-exit:\n");
70 scanf("%d",&LineNum);
71 //輸入要輸入字符串的所在行數。
72 if(LineNum<0||LineNum>=MAX)
73 return;
74 //超出可能的行數，即直接返回。
75 printf("please input,#-end\n");
76 i=LineNum;
77 Head[i].number=LineNum;
78 Head[i].next=(strnode*)malloc(sizeof(strnode));
79 //申請存儲空間。
80 p=Head[i].next;
81 //p就是我們將要存儲字符串的頭結點（字符串的第一個字符的地址）
82 ch=getchar();
83 while(ch!='#')
84 {
85 j++;
86 //驗證前面所說的j問題
87 if(j>=50)
88 //這裡采用了50為一行字符串的上限。
89 {
90 p->next=(strnode*)malloc(sizeof(strnode));
91 p=p->next;
92 //大於50了，就會重新申請存儲空間，繼續存儲字符串。所以一個head節點只存儲50字符串長度的數據。
93 //但是，由於我們並沒有修改number，所以在其表現來看，我們輸入的超過50字符的字符串還是同一個字符串。
94 //這裡可以將這個方法，應用到更多的地方。
95 }
96 p->data[j%50]=ch;
97 //理解j%50即可。
98 ch=getchar();
99 }
100 Head[i].length=j+1;
101 //因為我們j是從0開始的。
102 }
103 }
104
105 void Delline()
106 //定義函數Delline()，用來刪除確定的字符串。
107 {
108 strnode *p,*q;
109 int i,LineNum;
110 while(1)
111 {
112 printf("input the number of line which do you want to delete(0-100),101-exit:\n");
113 scanf("%d",&LineNum);
114 //輸入具體要刪除的字符串所在的行數。
115 if(LineNum<0||LineNum>=MAX)
116 return;
117 i=LineNum;
118 p=Head[i].next;
119 //中間這四行代碼同input函數一樣
120 if(Head[i].length>0)
121 //判斷所要刪除的函數並非空
122 while(p!=NULL)
123 //判斷所要刪除字符串的下一個字符串非空時，采取的處理。
124 {
125 q=p->next;
126 free(p);
127 p=q;
128 //和之前鏈表，棧等的刪除相同。
129 }
130 Head[i].length=0;
131 Head[i].number=0;
132 //確定該字符串的頭文件中length、number均為0，等同於消除存在。
133 //正如之前Head[i].length>0這句代碼，有時可通過對length、number的判斷來顯示，該Head是否為空。
134 }
135 }
136
137 void List()
138 //自定義函數List()，用來展示所有的字符串。
139 {
140 strnode *p;
141 int i,j,m,n;
142 for(i=0;i<MAX;i++)
143 //老樣子，這個串，說白了數據深度就兩層。所以兩個循環就OK了。第二個循環在後面。要看成整體，中間只是多個判斷和順序。
144 //其中我是用printf一個字符一個字符地輸出的。所以一個字符串就是一層循環。
145 //但是，如果你要換成一個字符串一個字符串的輸出，類似putstr。自己改啊。
146 {
147 if(Head[i].length>0)
148 //這裡就驗證了之前提到的用length判斷是否為空。空時就不會輸出該字符串了。
149 {
150 printf("line%d: ",Head[i].number);
151 //輸出所要輸出字符串所在的行數。
152 n=Head[i].length;
153 m=1;
154 p=Head[i].next;
155 for(j=0;j<n;j++)
156 //第二個循環。用來將字符串中字符一個一個輸出。
157 if(j>=50*m)
158 //還記得我之前在輸入函數中提到的50長度的問題嗎？這裡就有了解決之道。
159 {
160 p=p->next;
161 m++;
162 }
163 else
164 printf("%c",p->data[j%50]);
165 //輸出一個個字符。
166 printf("\n");
167 }
168 }
169 printf("\n");
170 }
171
172 main()
173 //創建主函數mian(),作為程序的入口。控制程序的選擇界面、函數調用等。
174 {
175 int sel;
176 Init();
177 while(1)
178 {
179 sel=Menu();
180 switch(sel)
181 {
182 case 1:
183 input();
184 break;
185 case 2:
186 Delline();
187 break;
188 case 3:
189 List();
190 break;
191 case 4:
192 exit(0);
193 }
194 }
195 //主函數不做解釋了。這和之前的一模一樣啊。
196 }
反思：其中關於塊鏈結構的應用那兩段代碼，應當好好理解。是個很好用的思路。
實例099 廣義表的存儲 實例100 廣義表的存儲
ps:廣義表是一種非線性的列表。是線性表和樹的推廣。廣泛應用與人工智能領域。有興趣的小伙伴要多多注意了。
問題：我將兩個問題和在了一起。編程實現用動態鏈接結構存儲廣義表與廣義表的復制，要求輸出該廣義表的長度和深度，以及表頭和表尾。
邏輯： 在一個廣義表中，數據元素可以是一個單一元素，也可以是子表，相應地在對應的存儲結構中，存儲結構節點也有單元素節點和子表節點之分。單元素節點包含值域和指向其後繼結點的指針域。對於子表節點，應包含指向子表中第一個節點的表頭指針和指向其後繼結點的指針域。為了區分廣義表中單元素節點和子表元素，我們設置tag作為標志，當tag=0時表示本節點為單元素，當tag=1時表示本節點為子表。
當tag=1時，說明其為子表節點，則第二域是sublist域，存放的是指向其子表的指針，next域存放指向與該節點同層的直接後繼結點的指針，當該節點是所在層的最後一個節點時，此時next為空（和之前鏈表等，一樣）。
廣義表的復制可以采用遞歸實現。
其實，廣義表這個東西如果有圖，看一下圖，就立馬懂了。我過會兒找找，有的話，就貼上。（我才不會說，我還不知道怎麼添加圖片呢。）
代碼：
1 #include<stdio.h>
2 #include<stdlib.h>
3 typedef char ElemType;
4 //替換的實現
5 typedef struct lnode
6 //
7 {
8 int tag;
9 union
10 //由於，節點元素要麼是單一元素，要麼是子表元素。所以采用了union來統一管理，同時實現存儲空間的節約。
11 {
12 ElemType data;
13 //用來存放單一元素。
14 struct lnode *sublist;
15 //用來存放子表元素--子表頭結點指針地址。
16 }val;
17 //值域
18 struct lnode *next;
19 //指向後繼節點的指針域。
20 }GLNode;
21 //廣義表結構體名。
22
23 void creatGList(struct lnode **gl)
24 //創建函數creatGList()，用來實現廣義表的創建。
25 {
26 char ch;
27 ch=getchar();
28 if(ch=='#')
29 {
30 *gl=NULL;
31 }
32 else if(ch=='(')
33 //輸入的字符若是左括號，則建立子表。
34 {
35 *gl=malloc(sizeof(struct lnode));
36 //創建存儲空間。
37 (*gl)->tag=1;
38 //表明是子表
39 creatGList(&((*gl)->val.sublist));
40 //調用函數creatGList()，創建子表。
41 }
42 else
43 {
44 *gl=malloc(sizeof(struct lnode));
45 //創建存儲空間
46 (*gl)->tag=0;
47 //表明是字符。
48 (*gl)->val.data=ch;
49 //存儲輸入的字符。
50 }
51 ch=getchar();
52 if(*gl==NULL)
53 {
54 ;
55 }
56 else if(ch==',')
57 //輸入的是",",表示遞歸構造後繼表。
58 {
59 creatGList(&((*gl)->next));
60 }
61 else
62 (*gl)->next=NULL;
63 return;
64 }
65
66 void printGList(struct lnode *gl)
67 //創建函數printGList()，用於輸出廣義表。
68 {
69 if(gl->tag==1)
70 //如果類型是子表,則輸出括號
71 {
72 printf("(");
73 //先輸出左括號
74 if(gl->val.sublist==NULL)
75 {
76 printf("#");
77 }
78 else
79 {
80 printGList(gl->val.sublist);
81 //遞歸輸出子表
82 }
83 printf(")");
84 //輸出右括號
85 }
86 else
87 //否則，即輸出的是字符。
88 printf("%c",gl->val.data);
89 //直接輸出字符。
90 if(gl->next!=NULL)
91 {
92 printf(",");
93 printGList(gl->next);
94 //遞歸輸出後繼表。
95 }
96 return;
97 }
98
99 int GLLength(GLNode *gl)
100 //創建函數GLLength(),用來計算廣義表的長度。
101 {
102 int n=0;
103 gl=gl->val.sublist;
104 while(gl!=NULL)
105 {
106 n++;
107 //長度計數。
108 gl=gl->next;
109 //指向下一個節點。
110 }
111 return n;
112 }
113
114 int GLDepth(GLNode *gl)
115 //創建函數GLDepth()，用來計算廣義表的深度。
116 {
117 int max=0,dep;
118 if(gl->tag==0)
119 return 0;
120 gl=gl->val.sublist;
121 if(gl=NULL)
122 return 1;
123 while(gl!=NULL)
124 {
125 if(gl->tag==1)
126 //類型為子表
127 {
128 dep=GLDepth(gl);
129 //遞歸計算廣義表的深度。
130 if(dep>max)
131 max=dep;
132 //記錄下最大深度。
133 }
134 gl=gl->next;
135 //指向下一個節點。
136 }
137 return(max+1);
138 }
139
140 GLNode *GLCopy(GLNode *gl)
141 //創建函數GLCopy(),用來實現廣義表的復制。
142 {
143 GLNode *q;
144 if(gl==NULL)
145 return NULL;
146 q=(GLNode*)malloc(sizeof(GLNode));
147 //申請存儲空間
148 q->tag=gl->tag;
149 //復制元素類型。
150 if(gl->tag==1)
151 q->val.sublist=GLCopy(gl->val.sublist);
152 //遞歸復制子表
153 else
154 q->val.data=gl->val.sublist;
155 //遞歸復制數據元素
156 q->next=GLCopy(gl->next);
157 //復制next信息，指向下一個節點，遞歸復制。
158 return q;
159 }
160 GLNode *head(GLNode *gl)
161 //創建函數head()，用來實現計算廣義表的表頭。
162 {
163 GLNode *p=gl->val.sublist;
164 //初始化，賦值p.
165 GLNode *q,*t;
166 //初始化q,t。
167 if(gl==NULL)
168 {
169 printf("NULL\n");
170 return NULL;
171 }
172 if(gl->tag==0)
173 //如果廣義表為空。
174 {
175 printf("atom is not head! \n");
176 //輸出廣義表沒有表頭。
177 return NULL;
178 }
179 if(p->tag==0)
180 //如果元素的類型為字符
181 {
182 q=(GLNode*)malloc(sizeof(GLNode));
183 //為q申請存儲空間。
184 q->tag=0;
185 //記錄數據類型
186 q->val.data=p->val.data;
187 //復制數據。
188 q->next=NULL;
189 //單個元素的下一個節點為空。
190 }
191 else
192 {
193 t=(GLNode*)malloc(sizeof(GLNode));
194 //申請存儲空間。
195 t->tag=1;
196 //記錄元素的類型為子表
197 t->val.sublist=p->val.sublist;
198 //賦值子表
199 t->next=NULL;
200 //單個元素的下一個節點為空。
201 q=GLCopy(t);
202 //復制子表。
203 free(t);
204 //釋放t的存儲空間。
205 }
206 return q;
207 //返回q。
208 }
209
210 GLNode *tail(GLNode *gl)
211 //創建函數tail(),用來計算廣義表的表尾。
212 //概念同上，故不做注釋。參考上一個函數。
213 {
214 GLNode *p=gl->val.sublist;
215 GLNode *q,*t;
216 if(gl==NULL)
217 {
218 printf("NULL\n");
219 return NULL;
220 }
221 if(gl->tag==0)
222 {
223 printf("atom is not tail!\n");
224 return NULL;
225 }
226 p=p->next;
227 t=(GLNode*)malloc(sizeof(GLNode));
228 t->tag=1;
229 t->val.sublist=p;
230 t->next=NULL;
231 q=GLCopy(t);
232 free(t);
233 return q;
234 }
235
236 main()
237 //創建主函數main()，作為程序入口。用來執行輸入、調用函數等功能。
238 {
239 int len=0;
240 int dep=0;
241 struct lnode *g,*v;
242 struct lnode *h;
243 printf("Input Example: (a,b,(c,d,(e,f,g),h,i),j)");
244 printf("\n");
245 printf("PS:輸入的‘（）’是圓括號，並不是尖括號。");
246 //添加備注。
247 printf("\n");
248 creatGList(&h);
249 //創建廣義表。切記這裡是&h。
250 len=GLLength(h);
251 //計算廣義表長度。
252 dep=GLDepth(h);
253 //計算廣義表深度。
254 printf("\n");
255 printf("The length is:");
256 printf("%d",len);
257 printf("\n");
258 printf("The depth is:");
259 printf("%d",dep);
260 printf("\n");
261 v=head(h);
262 g=tail(h);
263 //賦值。
264 if(v!=NULL)
265 //計算，並輸出廣義表的表頭。
266 {
267 printf("The Head is:");
268 printGList(v);
269 printf("\n");
270 }
271 if(g!=NULL)
272 //計算，並輸出廣義表的表尾。
273 {
274 printf("The Tail is:");
275 printGList(g);
276 printf("\n");
277 }
278 if(h!=NULL)
279 //展示整個廣義表。
280 {
281 printf("Glist is:");
282 printGList(h);
283 printf("\n");
284 }
285 else
286 printf("Glist is NULL");
287 }
反思：其中有著不少的小點，需要記憶、理解。值得好好看看。
PS：1.關鍵字union:union 關鍵字的用法與struct 的用法非常類似。
union 維護足夠的空間來置放多個數據成員中的“一種”，而不是為每一個數據成員配置空間，在union 中所有的數據成員共用一個空間，同一時間只能儲存其中一個數據成員，所有的數據成員具有相同的起始地址。例子如下：
union StateMachine
{
char character;
int number;
char *str;
double exp;
};
一個union 只配置一個足夠大的空間以來容納最大長度的數據成員，以上例而言，最大長度是double 型態，所以StateMachine 的空間大小就是double 數據類型的大小。
在C++裡，union 的成員默認屬性頁為public。union 主要用來壓縮空間。如果一些數據不可能在同一時間同時被用到，則可以使用union。
以上關於union的說明采摘自：http://c.biancheng.net/cpp/html/450.html， 其中還有關於大小端模式、確認系統大小端方法的具體說明，感興趣的可以看一看。
到這裡，棧與隊列，串與廣義表就完成了。下一次就是這章的最後知識點--樹與圖。
