不好意思，這兩天要幫家裡做一些活兒。而且內容量與操作量也確實大幅提升了。所以寫得很慢。
不過，從今天開始。我寫的東西，許多都是之前沒怎麼學的了。所以速度會慢下來，同時寫得也會詳細許多。
第三章是數據結構，數據結構可以說是理論學習的重點。同時許多學校（包括我所就讀的大學）都開設了數據結構課程。但是講的東西大多太過理論性，主要講解概念與思想。
另外，數據結構可是計算機考研中專業課的重點科目哦。
這章數據結構包括結構體、鏈表、棧與隊列、串與廣義表、二叉樹、圖與圖的應用。
每一個都是重點，所以我會細細地過一遍。
3.1結構體
也許你的C語言老師不會講解鏈表、二叉樹等，但他一定會講解結構體的使用，並且讓你們作出代碼實現。
結構體是什麼？其實結構體就是一個制式容器。裡面包括了規定的各個變量。
比如說，我設定了
1 struct student
2 {
3 char name;
4 int age;
5 float score;
6 };
那麼在這個結構體所在的程序裡，student就是一個包含三個不同數據類型的變量。當然，你也可以認為student是一個新的數據類型，一個自己設立的數據類型。不過這個數據類型是一個特定的數組，因為其中有著許多不同的數據類型（數組只能是相同數據類型）。
創建結構體是要用到struct。其他用法將在接下來的例子中提到。
實例076
問題：從鍵盤中輸入姓名和電話號碼，以#結束，編程實現輸入姓名，查詢電話號碼的功能。
邏輯：首先一個主函數作為程序入口，實現程序運行框架。然後一個存儲函數readin實現數據的存儲，再一個查詢函數seach實現數據的查找。
主函數無非定義，初始化變量。調用存儲函數來存儲我們輸入的函數。再調用查詢函數來輸出所要的結果。
存儲函數定義，初始化變量。建立循環，判讀輸入是否為#，同時將數據存儲。
查詢函數定義，初始化變量。建立循環，判斷所要查找的數據與當前數據是否符合，判斷數據是否已經全部遍歷。
程序代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #define MAX 101
4 struct aa
5 {
6 char name[15];
7 char tel[15];
8 };
9 int readin(struct aa *a)
10
11 //注意這裡結構體aa的變量名為*a，是一個指針，因為這個結構體在三個函數中均被調用。所以只有使用指針才較為便利地可以實現函數間大量數據的調用。
12
13 //其實，在使用指針為變量時，就已經建立了一個以a為名的aa型結構體數組了。
14
15 {
16 int i=0,n=0;
17 while(1)
18
19 //本人最為喜歡的循環體設置方法，包括for(;1;)的設立，循環體中再建立相關判斷條件。
20 {
21 scanf("%s",a[i].name);
22 if(!strcmp(a[i].name,"#"))
23
24 //利用這樣的判斷語句判斷輸入是否為#，（其實可以在判斷語句中實現賦值與判斷的共同實現，雖然好看，但是確保自己邏輯正確。）
25
26 //strcmp()比較兩個字符串是否相等，相等返還0，相等返還0，相等返還0.
27 break;
28 scanf("%s",a[i].tel);
29 i++;
30 n++;
31 }
32 return n;
33
34 //返回輸入結構體的數量。（一組數據就是一個結構體）
35 }
36 void search(struct aa *b,char *x,int n)
37
38 //x是一個指針，主函數中name是數組名，即一個指針。
39 {
40 int i;
41 i=0;
42 while(1)
43 {
44 if(!strcmp(b[i].name,x))
45 {
46 printf("name:%s tel:%s\n",b[i].name,b[i].tel);
47 break;
48 }
49 else
50 i++;
51 n--;
52
53 //其實這個n是用來計算是否所有結構體遍歷。但是我認為用i就行了。雖然i是在判斷語句裡面，但這個語句在沒找到目標是是一直執行的，如同在外面和n相同待遇
54
55 //當判斷語句找到目標時，那就更不需要他了。因為程序結束了。
56
57 if(n==0)
58 {
59 printf("No found!");
60 break;
61 }
62 }
63 }
64 main()
65 {
66 struct aa s[MAX];
67 int num;
68 char name[15];
69 num=readin(s);
70
71 //這個語句有兩個用處，1.將readin函數返回給num；2.readin函數將數據存儲於數組s。
72 printf("input the name:");
73 scanf("%s",name);
74 search(s,name,num);
75 }
反思：結構體在日後的使用中，就好像int、char這些數據類型一般，很常用。同時，這個程序中，我們學到程序中函數的簡單架構。另外，我們完全可以將這個函數擴展化。比如小到平時存儲東西，查找東西。大到各個程序中的存儲，查找功能等。
3.2鏈表
一般來說，數據結構這門課講解的第一個數據結構一般就是鏈表。很多教材第一頁就是鏈表。
曾經有公司高層談論編程時，說：”學生大多缺乏實際編程經驗，我在招聘時經常讓應聘者做一個簡單的鏈表。結果很多人都不會。“
鏈表可以說是數據結構應用的入門，如果連這個都不會，最好別去考慮與編程有關的職業。
曾經看過一本書，它的開頭講述了一個故事。說有一個剛入行的程序員第一次處理網站數據，做了一個1500長度的數組和循環用來存儲臨時數據。然後不久那個網站就掛了。後來作者去就將他做得數組改成了一個1500的循環鏈表就完事兒了。
鏈表是動態分配存儲空間來存儲數據，避免了空間的浪費。（當年用數組存儲數據有多少人和我一樣糾結空間大小的舉個手）同時，鏈表的存儲空間可以不連續、不連續、不連續。這樣產生了許多便利，並且有效利用了存儲空間。
我會講解每一個例子。（我才不會說，之前看的時候，我就記得單向鏈表了。。。）
實例078 創建單向鏈表
問題：創建一個單向鏈表，實現數據的輸入、輸出。
邏輯：鏈表是由一個個節點組成的。每一個節點分為兩部分：數據域與指針域。數據域用來存儲數據，指針域用來存儲下一個節點位置（雙向鏈表就還有一個指向前一個節點的鏈表）。一般第0個節點是整個鏈表的頭結點，稱為”頭指針“，一般不存放數據，只存放指向第1個節點的指針。鏈表的最後一個節點的指針設為空（NULL），作為鏈表的結束標志。
程序代碼：
1 #include<stdio.h>
2 #include<malloc.h>
3 //malloc是用來劃分存儲空間的函數。
4 struct LNode
5 {
6 int data;
7 struct LNode *next;
8 //指向下一個的結構體。從而形成鏈表。
9 };
10 struct LNode *create(int n)
11 {
12 int i;
13 struct LNode *head,*p1,*p2;
14 //head表示頭節點。p1，實現存儲空間的獲取，數據域賦值等。p2，作為與p1的中間指針，構成鏈表的替換連接。
15 int a;
16 head=NULL;
17 //頭節點為空。
18 printf("Input the integers:\n");
19 for(i=n;i>0;--i)
20 {
21 p1=(struct LNode*)malloc(sizeof(struct LNode));
22 //malloc(sizeof(struct LNode)表示劃分LNode大小的存儲空間。
23 //(struct LNode*)表示數據類型的轉換，將劃分來的存儲空間首地址轉化為LNode的變量名（指針類型）。
24 scanf("%d",&a);
25 p1->data=a;
26 //向p1的結構體中存儲數據。
27 if(head==NULL)
28 {
29 head=p1;
30 p2=p1;
31 //對頭節點的處理。
32 }
33 else
34 {
35 p2->next=p1;
36 //表明p2的下一個節點是p1。其中p2是上個循環中的p1。也就是說，p2只是一個中間變量temp。
37 p2=p1;
38 //印證了上個注釋中，p2的由來。
39 //具體的過程在變量名的說明中就已經體現了。
40 }
41 }
42 p2->next=NULL;
43 //最後一個節點的指針域為空，作為結束的標志。
44 return head;
45 //返回代表頭結點的結構體的變量名（指針）。
46 }
47 void main()
48 {
49 int n;
50 struct LNode *q;
51 printf("Input the count of the nodes you want to creat:");
52 scanf("%d",&n);
53 q=create(n);
54 //輸入，返回。
55 printf("The result is:\n");
56 while(q)
57 //q只有到了最後一個節點的next時，為NULL，才會跳出循環。一個很有用的小技巧。
58 {
59 printf("%d ",q->data);
60 q=q->next;
61 //實現q的轉換，從而輸出所有數據。
62 }
63 getch();
64 }
如果對其中提到的malloc函數，以及相關的calloc函數，free函數感興趣的話，可以浏覽http://blog.csdn.net/shuaishuai80/article/details/6140979。
反思：學習該例有這麼幾個要點： 1.指針不要混淆，不要將結構體名的指針和結構體內next的指針混淆，雖然有時這兩者表達的是同一個東西；
2.一定要完全理解p1=(struct LNode*)malloc(sizeof(struct LNode));這句代碼；（解釋在樣例中）
3.正確理解p2->next=p1;與p2=p1;這兩句代碼的實現。（無法理解可帶入數據進行兩到三次循環，即可理解）。
實例079 創建雙向鏈表
問題：創建一個雙向鏈表 ，並將這個鏈表中數據輸出到窗體上，輸入要查找的學生姓名，將查找的姓名從鏈表中刪除，並現實刪除後的鏈表。
邏輯：其實就邏輯而言是很簡單的。與之前的單向鏈表相同，不過比後繼結點的設置多了一個前驅節點的設置。另外查找，與一般的結構體數組查找，並沒有什麼區別。至於刪除嘛，就需要改動刪除節點的前驅節點和後繼結點的設置。具體操作，可以看代碼。
程序代碼：
1 #include<stdio.h>
2 typedef struct node
3 {
4 char name[20];
5 struct *prior,*next;
6 //設立節點的前驅節點和後繼結點。
7 }stud;
8 stud *creat(int n)
9 {
10 stud *p,*h,*s;
11 int i;
12 h=(stud*)malloc(sizeof(stud));
13 //申請存儲空間
14 h->name[0]='\0';
15 //設置name為空
16 h->prior=NULL;
17 h->next=NULL;
18 p=h;
19 for(i=0;i<n;i++)
20 {
21 s=(stud*)malloc(sizeof(stud));
22 p->next=s;
23 printf("Input the %d student'sname:",i+1);
24 scanf("%s",s->name);
25 s->prior=p;
26 s->next=NULL;
27 p=s;
28 //方法和單向鏈表沒什麼區別，區別只在於多了一個前驅節點的設置。
29 //從一些方面來說，多了前驅節點更容易理解了。
30 }
31 p->next=NULL;
32 //設置最後節點的後繼結點為空，作為結束標志。
33 return(h);
34 }
35 stud *search(stud *h,char *x)
36 {
37 stud *p;
38 char *y;
39 p=h->next;
40 while(p)
41 {
42 y=p->name;
43 if(strcmp(y,x)==0)
44 //判斷是否為尋找的目標。
45 return(p);
46 //返回目標地址。
47 else
48 p=p->next;
49 //繼續下一個節點的檢測。
50 }
51 printf("cannot find data!\n");
52 //沒有任何符合條件的返回。
53 }
54 void del(stud *p)
55 {
56 p->next->prior=p->prior;
57 //令p的下一個節點的前驅節點與現在p的前驅節點一致（這樣在前驅節點中p就不存在了。並且鏈表沒有斷開。）
58 p->prior->next=p->next;
59 //令p的前一個節點的後繼結點與現在p的後繼結點一致（這樣在後街節點中p就不存在了。並且鏈表沒有斷開。）
60 //切記：p->next是指p的後一個節點。p->prior同理。
61 //無法理解的話，請在草稿紙上畫出鏈表圖，就清晰無比了。
62 //這裡兩句代碼在有些運行環境中會報錯，可以自行更改語句或環境。
63 free(p);
64 //釋放p的存儲空間（鏈表上p已經不存在了。當然不能讓它占著空間了）
65 }
66 main()
67 {
68 int number;
69 char sname[20];
70 stud *head,*sp;
71 puts("Please input the size of the list:");
72 scanf("%d",&number);
73 head=creat(number);
74 sp=head->next;
75 printf("\nNow the double list is:\n");
76 while(sp)
77 {
78 printf("%s",&*(sp->name));
79 sp=sp->next;
80 }
81 //之前的都與單向鏈表相同。
82 printf("\nPlease input the name which you want to find:\n");
83 scanf("%s",sname);
84 sp=search(head,sname);
85 //通過search函數，尋找到所要尋找的sname的地址sp。
86 printf("the name you want to find is:\n",*&sp->name);
87 del(sp);
88 //將sp帶入到del()函數中，刪除。
89 sp=head->next;
90 //這句話只是為了下面的while循環做二次利用的。完全可以刪除這句話，為下面的循環單獨設置一個變量。
91 printf("\nNow the double list is:\n");
92 while(sp)
93 {
94 printf("%s",&*(sp->name));
95 sp=sp->next;
96 }
97 printf("\n");
98 puts("\nPress any key to quit...");
99 getch();
100 //與單向鏈表相同的輸出原理。
101 }
反思：雙向鏈表與單向鏈表並沒有什麼不同。要記得的是，雙向鏈表可是比單向鏈表多了一個prior的指針，無論是添加，刪除，移動，修改，都要記住。
實例080 循環鏈表
還記得開頭，我說的那個網站關於鏈表的故事嗎。這下說的就是循環鏈表。
其實到了這個時候也就沒有什麼說的了。循環鏈表就是將最後節點的後繼結點設置為頭結點。
循環鏈表與普通鏈表的操作基本一致，只是在算法中循環遍歷鏈表節點時判斷條件不再是p->next是否為空，而是是否等於鏈表的頭結點
程序代碼：（這裡就不演示。篇幅不應該留給不需要的東西。）
實例081 雙鏈表逆置
問題：創建一個雙向鏈表，將雙向鏈表的節點逆置，即將尾節點放到第一個節點的位置，倒數第二個節點放到第二個節點的位置，依此類推。
邏輯：雙向鏈表的創建、輸入、輸出，都和之前一樣。為了模塊化的操作，就單獨創建一個reverse函數，用來執行逆置操作。逆置操作就是指針的變換。
部分代碼：
1 stud *reverse(stud *head)
2 {
3 stud *p,*r,*h;
4 h=head->next;
5
6 //設置h。
7 if(h&&h->next)
8 {
9 p=h;
10 r=p->next;
11 p->next=NULL;
12 while(r)
13 {
14 p=r;
15 r=r->next;
16 p->next=h;
17 h->prior=p;
18 h=p;
19
20 //中間變量p，變量r從鏈表的頭部向後遍歷，變量h從鏈表的尾部向前遍歷。變量p作為中間變量來轉移指針地址，完成鏈表逆置。
21 }
22 head->next=h;
23 h->prior=head;
24
25 //事後，完成鏈表的補全。即鏈表的開頭和結尾。
26 return head;
27 }
28 }
反思：想要完成這些，自己一定不能混淆指針，指針的指針，指針的指向。這三個概念。
後面還有很多相關的知識，比如逆序輸出，約瑟夫環，鏈表的元素插入，節點插入，節點刪除，合並鏈表以及頭插入法建立鏈表等。但是，我認為，如果之前的鏈表都懂了。那麼後面的知識無非就是鏈表的基礎知識版應用。如果有需要，可以找我。
總結：其實鏈表在學習後，就會發現，之前指針學得好是多麼重要啊。尤其是指針的指針這一點。如果，指針學得好，那麼鏈表要學的就是鏈表的概念，鏈表的一些專用函數，以及常用的算法。那麼之後的一些應用就是水到渠成的事兒。（完全就是之前程序的鏈表版應用啦。）
由於時間關系，這次就先寫這麼多了。（其實這次寫的比之前多了很多，尤其線下還做了那麼多的程序調試。）
謝謝大家的鑒賞和評價。也希望能夠結識一些相關興趣的小伙伴。
另外，也許不久，我還會寫一些別的東西。
（剛剛博客園官方通知了我，我才知道有代碼插入這個東西。挺贊的。對於我這個有代碼行潔癖的，每次copy後敲Tab，也是蠻難過的。謝謝了。）
