第10章 基本數據結構

本章重點

· 棧

· 隊列

· 鍊表

在前面的章節中講解了C語言的基礎知識、數組、指針、流程控制等，在C語言中還有一些基本的數據結構，如棧、隊列和鍊表，這些數據結構有着自己的特性，合理利用這些數據結構可以在程序中起到事半功倍的效果，本章将針對這些基本的數據結構進行詳細地講解。

棧

在現實生活中經常會完成一些"後進先出"的動作，例如一群人排隊等一個電梯，當電梯門打開後，排在隊首的人先進入電梯，排在隊末的人最後進入電梯，當電梯停止時，後進入電梯的人就會先下去，先進入電梯的人後下去。在C語言中有一種數據結構也滿足這種"後進先出"的原則，該數據結構就是棧，棧中可以加入元素也可以彈出元素，這些元素在存取的過程中會滿足"後進先出"的原則。接下來将針對棧進行詳細地講解。

10.1.1 定義棧

在C語言中可以用數組來模拟棧。數組的開頭（下标為0的元素）被稱為棧底，再利用另外一個指針指向數組的末尾，被稱為棧頂：

#include <stdio.h>

#define STACK_SIZE1000

int head, tail;//棧底和棧頂

int stack[STACK_SIZE];//int類型的數組用來實現棧

int main()

{

head = 0;

tail = 0;

return 0;

}

下面來逐行分析這個程序：

第2行定義了宏STACK_SIZE，并将它的值定為1000。這是本節中棧的默認大小；

第3行定義了兩個全局變量head和tail，分别指向棧底和棧頂；

第4行定義了一個全局的int類型數組stack，它的長度為STACK_SIZE。接下來将用這個數組來模拟棧上的操作。

第7到8行在進入main函數之後，将head和tail都初始化為指向數組的第0個元素。

在棧這一節中，約定tail指向棧中即将加入的新元素的位置，即棧中已有元素的下标為0，1，2到tail-1。按照這樣的約定，當head和tail的值都指向第0個元素時，這個棧就是空的。

10.1.2 向棧中加入新元素

push函數實現了向棧中加入新元素的操作，它的定義如下：

void push(int element)

{

stack[tail] = element;

tail ;

}

其中，參數element是要加入棧中的新元素。根據此前的約定，tail指向的是新元素加入的位置，因此stack[tail]用來保存要加入的值element。

新元素加入完畢後，棧的長度增加一，tail的值也需要更新。tail 負責把tail的值移向下一個元素，也就是接下來新元素要加入的位置。

10.1.3 彈出棧中元素

pop函數實現了彈出棧頂元素的操作，它的定義如下：

int pop()

{

tail--;

return stack[tail];

}

pop函數不接受任何參數，它返回一個int類型的數，這個數正是當前棧頂的元素。為了實現pop函數的功能，首先将tail自減，此時tail被挪到了棧中的最後一個元素，随後将這個元素返回。注意pop函數調用之後棧的長度也減一，因此tail自減之後恰好指向的就是pop之後新元素加入棧時的位置。

10.1.4 查看棧頂元素

有的時候程序隻是想查看棧頂的元素，并根據查看的結果來決定是否需要将這個元素彈出棧。peek函數實現了這個功能，它的定義如下：

int peek()

{

return stack[tail - 1];

}

由于tail指向了棧頂的後一個元素，因此棧頂元素的下标是tail-1，peek函數返回這個下标對應的元素。請注意比較peek函數和pop函數的區别：兩個函數的返回元素其實是一樣的，但是pop函數在返回棧頂元素的同時還修改了tail的值，而peek函數僅僅返回棧頂元素，棧底的位置并沒有被修改。

10.1.5 清空棧

由于一個棧為空的條件是tail=head=0，因此清空棧的操作非常簡單：

void cleanStack()

{

tail = head;

}

注意到在棧中head的值自始至終為0，cleanStack函數實際上将tail的值設為了0。另一個值得留意的地方是清空一個棧并沒有必要将棧中的所有元素統統pop一遍，或者将這些元素都設為0，隻要将tail移到棧底就足夠了。

10.1.6 打印棧中元素

為了更加方便直觀地觀察棧的行為，這裡提供一個用于打印棧中所有元素的函數

void printStack()

{

for (int i = head; i < tail; i )

{

printf("%d ", stack[i]);

}

printf("\n");

}

如前所述棧中的元素下标從head開始，到tail-1結束，printStack利用一個for循環将這些元素都打印出來，以方便觀察棧的當前狀态。

到此為止，一個最基本的棧就完成了。為了更加直觀地展示棧後進先出的特點，如例程10-1所示：

例程 10‑1 實現一個棧

1 #include <stdio.h>

2 #define STACK_SIZE1000

3 int head, tail;//棧底和棧頂

4 int stack[STACK_SIZE];//int類型的數組用來實現棧

5 void push(int element)

6 {

7 stack[tail] = element;

8 tail ;

9 }

10 int pop()

11 {

12 tail--;

13 returnstack[tail];

14 }

15 void cleanStack()

16 {

17 tail = head;

18 }

19 int peek()

20 {

21 return stack[tail - 1];

22 }

23 void printStack()

24 {

25 for (int i = head; i < tail; i )

26 {

27 printf("%d ", stack[i]);

28 }

29 printf("\n");

30 }

31 int main()

32 {

33 head = 0;

34 tail = 0;

35 printStack();

36 push(3);

37 push(5);

38 push(12);

39 printStack();

40 printf("pop %d\n", pop());

41 printStack();

42 printf("peek %d\n", peek());

43 printStack();

44 return 0;

45 }

程序的運行結果如圖10-1所示：

圖 10‑1 實現一個簡單的棧

例程10-1中包含了前面實現的所有函數，接下來逐行分析main函數中的程序，看看這個程序對棧都做了什麼：

第33到34行：初始化棧，将head和tail都設為0，即指向棧底；

第35行：打印當前棧中的元素。由于此時是一個空棧，打印的結果應該也為空；

第36行：向棧中插入一個元素3；

第37行：向棧中插入一個元素5；

第38行：向棧中插入一個元素12。此時棧中的元素應該是3、5和12。

第39行：打印當前棧中的元素；

第40行：從棧中彈出一個元素，由于此時棧頂為12，因此打印出的結果應該也是12，同時棧中的元素變為3和5；

第41行：打印當前棧中元素；

第42行：利用peek查看當前棧頂元素，此時棧頂元素為5。由于peek并不會彈出棧頂元素，因此棧中的元素依然為3和5；

第43行：打印棧中元素。

以上的程序實現了一個基本的棧，從圖10-1的程序運行結果中可以看出棧後進先出的特點。在後面還将會介紹如何利用棧的這一特點解決實際問題。

隊列

隊列與棧的"後進先出"原則正好相反，它是滿足"先進先出"的原則，也就是先進入隊列的元素會先出隊列。這就好像現實生活中排隊買火車票一樣，先排隊的人自然能先買到票，也先離開隊列。接下來将針對隊列進行詳細地講解。

10.1.7 定義隊列

和棧類似，隊列也可以用C中的數組來實現，如例程10-2所示：

例程 10‑2 定義隊列

46 #include <stdio.h>

47 #define QUEUE_SIZE1000

48 int head, tail;//隊首和隊尾

49 int queue[QUEUE_SIZE];//int類型的數組用來實現隊列

50 int main()

51 {

52 head = 0;

53 tail = 0;

54 return 0;

55 }

程序的運行結果如圖10-2所示：

圖 10‑2 定義一個隊列

隊列的初始化過程和棧幾乎完全一樣。例程10-2中定義了一個int類型的隊列queue，隊列的長度為QUEUE_SIZE。在main函數中将隊首和隊尾的位置都初始化為0。和棧一樣，我們約定tail指向的是隊尾之後的一個位置，而head指向的是隊首元素的位置。

10.1.8 進入隊列

enQueue函數實現了向隊列中加入一個元素的作用，它的定義如下所示：

void enQueue(int element)

{

queue[tail] = element;

tail ;

}

這裡可以将enQueue和棧中的push函數進行比較：由于都是從尾部加入元素，enQueue的實現和棧中的push函數完全一樣。

10.1.9 離開隊列

deQueue函數實現了從隊列中删除一個元素的作用。和棧中的pop函數不同的是，離開隊列發生在隊首而不是隊尾，因此deQueue函數和pop函數完全不同，以下是它的實現：

int deQueue()

{

head ;

return queue[head - 1];

}

在deQueue函數中首先将head的位置向後挪一位，這是deQueue之後head應該在的位置。随後，隊首的元素現在的下标變成了head-1，deQueue函數返回這個下标的對應元素值，實現從隊首彈出元素的功能。

10.1.10 清空隊列

cleanQueue函數實現了清空一個隊列的功能。和棧一樣，清空一個隊列也隻需要把head和tail重新設為0即可。cleanQueue的實現和前面的cleanStack完全一樣。

void cleanQueue()

{

tail = head = 0;

}

10.1.11 打印隊列中元素

printQueue函數實現了打印隊列中元素的功能，由于隊列中元素的下标從head開始，到tail-1結束，和棧完全一樣，因此printQueue的實現也和棧完全一樣：

void printQueue()

{

for (int i = head; i < tail; i )

printf("%d ", queue[i]);

printf("\n");

}

至此一個簡單的隊列就完成了，和棧一樣，下面的實例直觀地展示了隊列先進先出的特點，如例程10-3所示：

例程 10‑3 實現一個隊列

56 #include <stdio.h>

57 #define QUEUE_SIZE1000

58 int head, tail;//隊首和隊尾

59 int queue[QUEUE_SIZE];//int類型的數組用來實現隊列

60 void enQueue(int element)

61 {

62 queue[tail] = element;

63 tail ;

64 }

65 int deQueue()

66 {

67 head ;

68 return queue[head - 1];

69 }

70 void cleanQueue()

71 {

72 tail = head = 0;

73 }

74 void printQueue()

75 {

76 for (int i = head; i < tail; i )

77 printf("%d ", queue[i]);

78 printf("\n");

79 }

80 int main()

81 {

82 head = 0;

83 tail = 0;

84 printQueue();

85 enQueue(3);

86 enQueue(5);

87 enQueue(12);

88 printQueue();

89 printf("deQueue %d\n", deQueue());

90 printQueue();

91 printf("deQueue %d\n", deQueue());

92 printQueue();

93 return 0;

94 }

程序的運行結果如圖10-3所示：

圖 10‑3 實現一個簡單的隊列

例程10-3中包含了本節中所有的函數。逐行分析main函數中的程序，看看程序對隊列都做了什麼：

第27到28行：将head和tail都初始化為0，指向隊首；

第29行：打印當前隊列中的元素。由于隊列剛剛被初始化，打印的結果應該是一個空隊列；

第30行：向隊列中插入元素3；

第31行：向隊列中插入元素5；

第32行：向隊列中插入元素12；

第33行：打印隊列中元素。此時隊列中的元素按順序依次是3、5和12；

第34行：利用deQueue函數取出隊首的元素3并打印，此時隊列中的元素按順序依次是5和12；

第35行：打印隊列中元素，此時的打印結果應該是5和12；

第36行：再次利用deQueue取出隊首的5，此時隊列中隻有12；

第37行：打印隊列中元素，此時隻有12。

關于隊列要牢牢把握隊列先進先出的特點，本章之後會介紹如何充分利用隊列的這一特點解決實際問題。

結構體

前面的章節中已經介紹了int，char，float等基本數據類型，有的時候這些基本數據類型不能滿足程序員的需求，比如想要表示數學中的複數，就需要實部和虛部兩個double類型；想要表示空間中的一個點就需要x，y和z三個坐标；想要表示學校的一個學生，就至少需要一個表示姓名的字符串和一個int類型的學号。C語言允許定義自己的數據類型，這種自定義的新數據類型就是結構體。

10.1.12 定義結構體

結構體的定義需要遵循下面的語法格式：

struct 結構體名

{

成員1的類型 變量名;

成員2的類型 變量名;

…

成員n的類型 變量名;

};

下面是幾個結構體定義的例子：

一、學生

struct Student

{

char name[50];

int studentID;

};

Student結構體中定義了兩個成員：一個是char類型的數組name，用來保存學生的姓名（字符串形式）；第二個是int類型的學号studentID。

二、點

struct Point

{

double x;

double y;

double z;

};

Point就是程序中新定義的數據類型，它包含了三個double類型的數，分别表示x，y和z坐标的值。定義了Point之後，就可以像int，float等基本數據類型一樣去聲明Point類型的變量。

三、棧

struct Stack

{

int head;

int tail;

int size;

int *stack;

};

本章第一節中的棧也可以定義成結構體的形式。在Stack結構體中包含四個成員變量：棧底head，棧頂tail，棧的大小size，以及一個int*類型的指針stack，用來實現棧。

四、隊列

本章第二節的隊列也可以定義成結構體的形式，其定義和棧完全一樣：

struct Queue

{

int head;

int tail;

int size;

int *queue;

};

這是因為在前面的例子中，棧和隊列都是基于數組并且利用兩個下标來實現的。隊列結構體中也包含四個成員變量：隊首head，隊尾tail，隊列的大小size，以及一個int*類型的指針queue用來實現隊列。

10.1.13 定義結構變量

定義了結構體之後就可以向定義基本數據類型int，double等的變量一樣去定義一個結構體類型的變量。結構體變量的定義語法如下所示：

struct 結構體名 結構變量名;

類似的，也可以定義結構體數組：

struct 結構體名 結構體數組名[數組長度];

以上一節中的Stack為例：

struct Stack s;

這裡定義了一個Stack類型的變量，它的名字是s，s裡面包含了一個整數head，一個整數tail，一個整數size和一個整型指針stack。

定義結構變量之後的下一個問題就是如何初始化結構變量。結構體變量的初始化實際上是結構體中各個成員變量的初始化過程。它的語法是：

struct 結構體名 結構變量名={成員變量1初值, 成員變量2初值,…,成員變量n初值};

給定結構體中所有變量的初值，結構體會用這些初值對所有成員變量分别進行初始化。以下是一些實例：

一、初始化Student

struct Student student = {"Zhang San", 20140100};

這裡定義了一個Student類型的變量，變量名為student，student中包含一個char數組name用來存儲學生的名字，name被初始化為Zhang San。student中還包含了一個int類型的學号，在這裡被初始化為20140100。

二、初始化Point

struct Point p[2] = {{1.0, 2.0, -1.0}, {0.0, 0.0, 0.0}};

變量p是結構體類型Point的數組，數組的長度為2，p中包含了兩個元素p[0]和p[1]。p[0]中包含三個double類型的浮點數x，y和z，它們分别被初始化為了1.0，2.0和-1.0；p[1]中同樣包含三個浮點數x，y和z，它們被初始化為了0.0，0.0和0.0。

三、初始化Stack

struct Stack s = {0, 0, 1000, NULL};

Stack類型的變量s中包含4個成員，其中int類型的head和tail被分别初始化為了0和0，int類型的長度size被初始化為了1000，int類型的指針stack被初始化為NULL。

四、初始化Queue

struct Queue q = {0, 0, 1000, NULL};

Queue類型的變量q中包含4個成員，其中int類型的head和tail被分别初始化為了0和0，int類型的長度size被初始化為了1000，int類型的指針queue被初始化為NULL。

10.1.14 結構體與指針

既然基本數據類型可以有對應的指針，結構體類型作為一種新的數據類型，也應該可以有自己的指針。事實确實如此。結構體指針的定義和使用方式和一般的指針并無太大差别，比如：

定義一個Student類型的指針：

struct Student *p = NULL;

這個指針被初始化為NULL。

指向現有的結構體變量：

struct Student s = {"Zhang San", 20140100};

struct Student *p = &s;

這裡首先定義了一個結構體變量s，并用字符串Zhang San和學号20140100去初始化它。随後定義了一個Student類型的指針p，并利用取地址&将s的地址賦值給p，p成為了指向Student類型的變量s的指針。

動态聲明結構體數組：

//num是一個int類型的變量，表示數組長度

struct Student *p = (struct Student *)malloc(sizeof(struct Student) * num);

這裡num是一個int類型的變量，假定num的值隻有在運行時才能确定，Student類型的指針p分配了長度為num的一個結構體數組，數組中的每個元素都是一個Student類型的結構體變量，整個要分配的内存大小就是Student的大小乘以數量num。

10.1.15 訪問成員變量

結構體中的數據都是保存在成員變量中的，因此要想真正使用結構體光賦值還是遠遠不夠的，還需要知道如何去訪問結構體中的每一個成員變量。訪問成員變量的方法可以分為兩類：

通過結構變量訪問：

如果已經在程序中定義好了一個結構變量，那麼通過"結構變量名.成員變量名"就可以訪問相應的成員變量。如例程10-4所示：

例程 10‑4 通過結構變量訪問成員

95 #include <stdio.h>

96 #include <stdlib.h>

97 struct Student

98 {

99 char name[50];

100 int studentID;

101 };

102 int main()

103 {

104 struct Student s[2] = {{"Zhang San", 20140000}, {"Li Si", 20140001}};

105 for (int i = 0; i < 2; i )

106 {

107 printf("%s %d\n", s[i].name, s[i].studentID);

108 }

109 return 0;

110 }

程序的運行結果如圖10-4所示：

圖 10‑4 通過結構變量訪問成員

在例程10-4中，main函數裡定義了一個結構體數組s，它的長度為2，兩個數組成員s[0]和s[1]被分别初始化。此時通過s[0].name可以訪問到s[0]中的char數組name，通過s[0].studentID可以訪問到s[0]中的int類型成員變量studentID。程序中利用一個for循環将兩個數組成員的姓名和學号分别輸出。

通過結構體指針訪問：

如果程序中有一個指向某個結構體變量的指針，那麼可以利用"指針名->成員變量名"的方法來訪問成員變量，如例程10-5所示：

例程 10‑5 通過結構變量訪問成員

111 #include <stdio.h>

112 #include <stdlib.h>

113 struct Student

114 {

115 char name[50];

116 int studentID;

117 };

118 int main()

119 {

120 struct Student s = {"Zhang San", 20140000};

121 struct Student *p = &s;

122 printf("%s %d\n", s.name, s.studentID);

123 printf("%s %d\n", p->name, p->studentID);

124 return 0;

125 }

程序的運行結果如圖10-5所示：

圖 10‑5 通過指針訪問成員變量

在例程10-5中，main函數裡首先聲明了一個Student類型的結構變量s，并将s初始化為Zhang San，學号為20140000。接下來main函數裡聲明了Student類型的指針p，并将p指向s的地址。随後的兩條printf語句比較了兩種訪問方式：通過s.name訪問學生名，以及通過p->name訪問學生名。由于p指向了s，因此這兩種訪問方法訪問的都是s中的char數組name，類似的情況也出現在s中的int變量studentID上。

鍊表

前面講解的棧和隊列都可以用數組實現，在數組中訪問元素非常迅速，但是在數組的任意位置插入和删除元素時所有元素整體後移或前移一位，非常麻煩。為此C語言中還提供了一種數據結構——鍊表，鍊表中的每一個元素都使用引用的方式來記住它的前一個元素和後一個元素，從而可以将所有的元素彼此連接起來。因此當插入一個新元素時，隻需要修改元素之間的這種引用關系即可，非常方便，但是訪問元素相對來說較慢。接下來将針對鍊表進行詳細地講解。

10.1.16 定義鍊表

鍊表的定義分為兩部分，首先定義一個鍊表的表頭：

struct Head

{

int length;

struct Node* first;

};

這是一個Head類型的結構體，它包含了兩個成員，一個是int類型的變量length，用來表示整個鍊表的長度；第二個成員是一個指針，指向Node類型的變量。Node的定義如下所示：

struct Node

{

int val;

struct Node *next;

};

Node是這個鍊表中真正的元素，類似于數組當中的元素。Node中包含兩個成員：首先是int類型的變量val，用來保存數據；其次是一個指針next，它指向一個新的Node變量。

整個鍊表就是由一系列指針和結構體構成的蛇形結構：從Head開始指向鍊表的第一個Node，第一個Node指向第二個Node，第二個Node指向第三個Node，以此類推。直到某一個Node的next指針為NULL了，鍊表終止。

在下面的例程中，main函數裡首先定義了一個Head類型的指針h，并申請了一塊内存。目前h鍊表為空，在初始化的時候将鍊表的長度初始化為0，first指針初始化為NULL，如例程10-6所示：

例程 10‑6 定義鍊表

126 #include <stdio.h>

127 #include <stdlib.h>

128 struct Head

129 {

130 int length;

131 struct Node* first;

132 };

133 struct Node

134 {

135 int val;

136 struct Node *next;

137 };

138 int main()

139 {

140 struct Head *h = (struct Head*)malloc(sizeof(struct Head));

141 h->length = 0;

142 h->first = NULL;

143 free(h);

144 return 0;

145 }

程序的運行結果如圖10-6所示：

圖 10‑6 定義一個鍊表

逐行解釋main函數中的程序：

第15行：利用malloc函數申請一塊大小為Head的内存，初始化一個鍊表指針；

第16行：将Head中的鍊表長度設為0；

第17行：将Head中的first指針設為NULL；

第18行：回收内存，釋放申請的Head内存。

10.1.17 訪問元素

和數組元素類似，這裡約定鍊表中Node的下标也是從0開始的，即緊随在Head之後的Node下标為0。整個鍊表中的元素下表範圍是0到length-1。訪問元素的函數getNode定義如下：

struct Node* getNode(struct Head* head, int id)

{

if (id < 0 || id >= head->length)

return NULL;

struct Node* p = head->first;

int i = 0;

while (i < id)

{

p = p->next;

i ;

}

return p;

}

getNode函數的輸入是一個Head指針head，以及将要訪問的元素下标id。getNode函數返回一個Node類型的指針，指向鍊表中下标為id的Node。

如果id不在0到length-1的範圍之内，getNode返回NULL。否則，函數會初始化一個指針p指向鍊表中下标為0的Node，并初始化當前Node的下标i為0。随後函數利用while循環來尋找下标為id的Node。在當前循環中，如果i還沒有到id，那麼就将指針p更新到p的下一個Node，并将i的值加1，直到i指向id為止。

10.1.18 插入元素

在鍊表中插入元素采用如下的規則：如果插入位置的下标id在0到length-1的範圍之内，那麼就插入到元素id之前，即插入後新元素的下标應當為id。如果下标id=length，那麼就将元素插入到鍊表末尾。其他任何情況下對鍊表都不作改動：

void addNode(struct Head* head, int val, int id)

{

if (id < 0 || id > head->length)

return;

if (id == 0)

{

struct Node* p = head->first;

head->first = (struct Node*)malloc(sizeof(struct Node));

head->first->val = val;

head->first->next = p;

}

else

{

struct Node* p = getNode(head, id - 1);

struct Node* q = p->next;

p->next = (struct Node*)malloc(sizeof(struct Node));

p->next->val = val;

p->next->next = q;

}

head->length ;

}

addNode函數接受一個Head指針，将要插入的值val，以及要插入的位置id。如果id超出了範圍，就直接返回不做任何改動；否則，根據id的值分别進行處理：如果id為0，意味着新的Node要插入在Head和第一個Node之間，程序在if中進行處理；否則直接使用getNode獲得id-1處的Node，利用該Node的next指針将val插入到它身後。

10.1.19 删除元素

删除元素和插入元素類似，要求删除元素的id必須在0到length-1的範圍之内，否則不做處理：

void deleteNode(struct Head* head, int id)

{

if (id < 0 || id >= head->length)

return;

if (id == 0)

{

struct Node* p = head->first;

head->first = p->next;

free(p);

}

else

{

struct Node* p = getNode(head, id - 1);

struct Node* q = p->next;

p->next = q->next;

free(q);

}

head->length--;

}

deleteNode和addNode的流程類似，都是首先檢驗id是否在有效範圍之内，如果在的話，再根據id的值是否為0分情況讨論，選擇是直接從head開始删除還是從id-1的位置開始删除。

10.1.20 釋放鍊表

釋放鍊表的函數destroyLinkedList定義如下。它負責釋放鍊表中所有Node所占用的内存。

void destroyLinkedList(struct Head *head)

{

struct Node* p = head->first;

while (p)

{

head->first = p->next;

free(p);

p = head->first;

}

head->length = 0;

}

destroyLinkedList的執行過程實際上是在不斷地删除鍊表的第一個Node，直到所有Node都被删除為止。

10.1.21 打印鍊表

打印鍊表的函數定義如下：

void printLinkedList(struct Head *head)

{

struct Node* p = head->first;

for (int i = 0; i < head->length; i )

{

printf("%d ", p->val);

p = p->next;

}

printf("\n");

}

printLinkedList函數的輸入參數包括一個head指針，由于我們知道鍊表中所有Node的數量，因此可以利用一重for循環遍曆所有Node，分别輸出Node中存儲的val值即可。

至此一個簡單的鍊表就算是完成了。下面的程序可以用來上面這些鍊表函數的實現是否正确，如例程10-7所示：

例程 10‑7 實現鍊表

146 #include <stdio.h>

147 #include <stdlib.h>

148 struct Head

149 {

150 int length;

151 struct Node* first;

152 };

153 struct Node

154 {

155 int val;

156 struct Node *next;

157 };

158 struct Node* getNode(struct Head* head, int id)

159 {

160 if (id < 0 || id >= head->length)

161 return NULL;

162 struct Node* p = head->first;

163 int i = 0;

164 while (i < id)

165 {

166 p = p->next;

167 i ;

168 }

169 return p;

170 }

171 void addNode(struct Head* head, int val, int id)

172 {

173 if (id < 0 || id > head->length)

174 return;

175 if (id == 0)

176 {

177 struct Node* p = head->first;

178 head->first = (struct Node*)malloc(sizeof(struct Node));

179 head->first->val = val;

180 head->first->next = p;

181 }

182 else

183 {

184 struct Node* p = getNode(head, id - 1);

185 struct Node* q = p->next;

186 p->next = (struct Node*)malloc(sizeof(struct Node));

187 p->next->val = val;

188 p->next->next = q;

189 }

190 head->length ;

191 }

192 void deleteNode(struct Head* head, int id)

193 {

194 if (id < 0 || id >= head->length)

195 return;

196 if (id == 0)

197 {

198 struct Node* p = head->first;

199 head->first = p->next;

200 free(p);

201 }

202 else

203 {

204 struct Node* p = getNode(head, id - 1);

205 struct Node* q = p->next;

206 p->next = q->next;

207 free(q);

208 }

209 head->length--;

210 }

211 void printLinkedList(struct Head *head)

212 {

213 struct Node* p = head->first;

214 for (int i = 0; i < head->length; i )

215 {

216 printf("%d ", p->val);

217 p = p->next;

218 }

219 printf("\n");

220 }

221 void destroyLinkedList(struct Head *head)

222 {

223 struct Node* p = head->first;

224 while (p)

225 {

226 head->first = p->next;

227 free(p);

228 p = head->first;

229 }

230 head->length = 0;

231 }

232 int main()

233 {

234 struct Head *h = (struct Head*)malloc(sizeof(struct Head));

235 h->length = 0;

236 h->first = NULL;

237 addNode(h, 1, 0);

238 //1

239 printLinkedList(h);

240 addNode(h, 2, 1);

241 //1 2

242 printLinkedList(h);

243 addNode(h, 4, 1);

244 //1 4 2

245 printLinkedList(h);

246 addNode(h, 5, 2);

247 //1 4 5 2

248 printLinkedList(h);

249 deleteNode(h, 2);

250 //1 4 2

251 printLinkedList(h);

252 deleteNode(h, 1);

253 //1 2

254 printLinkedList(h);

255 destroyLinkedList(h);

256 //

257 printLinkedList(h);

258 free(h);

259 return 0;

260 }

程序的運行結果如圖10-7所示：

圖 10‑7 實現鍊表

根據本節中各個函數的定義，main函數中每一個printLinkedList之前都用注釋給出了鍊表中預期的值。

union共同體

本章最後要介紹union，也叫做共同體。union是一種特殊的數據類型，它允許多個成員使用同一塊内存。靈活地使用union可以減少程序所使用的内存。

10.1.22 定義共同體

定義和使用共同體的方法和結構體十分類似，也需要首先定義共同體内部的成員類型。首先來看union的定義語法：

union 名稱

{

變量類型1 變量名1;

變量類型2 變量名2;

變量類型3 變量名3;

...

};

union的定義方法和結構體很類似，但是需要注意的是，union中所有的變量名實際上共用同一塊内存。下面對例程的分析将會揭示這一點，如例程10-8所示：

例程 10‑8 使用union

261 #include <stdio.h>

262 union Data

263 {

264 int i;

265 int j;

266 };

267 int main()

268 {

269 union Data d;//定義了一個union

270 d.i = 15;

271 printf("%d\n", d.i);

272 printf("%d\n", d.j);

273 d.j = 23;

274 printf("%d\n", d.i);

275 printf("%d\n", d.j);

276 printf("%p\n", &d.i);

277 printf("%p\n", &d.j);

278 return 0;

279 }

程序的運行結果如圖10-8所示：

圖 10‑8 使用union

在剛剛的例程中，main函數裡首先定義了一個union Data變量，名稱為d，在union Data中包含兩個int類型的變量i和j，main函數裡首先對i進行賦值，并利用printf打印出i和j的值。由于i和j數據類型完全一樣，占用同一塊4個字節的内存，因此對i賦值也就相當于對j進行了賦值，可以預料到兩者打印的結果應該是一樣的。

随後程序對j進行賦值。同樣地，由于i和j隻占用相同的一段内存，因此對j賦值為23就會将這塊4個字節内存上原有的值15覆蓋，這是通過i和j訪問到這塊内存的值都是23，因此接下來兩次printf的值應該也是一緻的。

最後，利用printf打印出了i和j的内存地址。根據union的定義，打印的結果應該完全相同。

在上面的例程中，union裡面包含的是兩個相同類型的數據，union中也可以包含不同類型的成員變量，如例程10-9所示：

例程 10‑9 union中包含不同類型的成員

280 #include <stdio.h>

281 union Data

282 {

283 int i;

284 unsigned int u;

285 };

286 int main()

287 {

288 union Data d;//定義一個union變量

289 d.u = 0xffffffff;

290 printf("size(d) = %d\n", size(d));

291 printf("%u\n", d.u);

292 printf("%d\n", d.i);

293 return 0;

294 }

程序的運行結果如圖10-9所示：

圖 10‑9 union中包含不同類型的成員

上面的程序中定義了一個union類型Data，但是Data中包含了兩個不同類型的成員變量：unsigned int類型的u和int類型的i。在main函數中首先将u賦值為0xffffffff，這是unsigned int能夠表示的最大數，它在内存中的形式是：

1111 1111 1111 1111 1111 1111 1111 1111

當程序通過d.i的形式來訪問這段内存時，i的值也是0xffffffff，但是由于i的類型是int，根據前面的知識，這個值對應的有符号整數應該是-1，所以可以預計main函數中第二次printf的結果應該是-1。

一般地，在union中不同類型的成員共享同一塊内存，它們底層的二進制表示都是一樣的，但是不同的成員會根據自己的類型将這一塊内存中的值解讀為不同的内容。

10.1.23 使用不同長度的成員

上面的兩個例程中union包含的成員大小都是一樣的（盡管在第二個例子中數據類型不一樣），因此對于union成員共用的内存大小沒有什麼疑義。如果union中包含了不同大小的成員，那麼union所占用的内存大小取決于最長的成員所使用的内存，并且所有成員的首字節對齊。如例程10-10所示：

例程 10‑10 union包含不等長成員

295 #include <stdio.h>

296 #include <string.h>

297 union Data

298 {

299 char ch;

300 char str[4];

301 };

302 int main()

303 {

304 union Data d;//定義union變量

305 strcpy(d.str, "ABC");

306 printf("%s\n", d.str);

307 printf("%c\n", d.ch);

308 return 0;

309 }

程序的運行結果如圖10-10所示：

圖 10‑10 union包含不等長成員

在例程10-10中，union内包含了兩個不等長的數據成員：成員ch的類型是char，占用1個字節；成員str是一個字符串，長度為4個char，占用4個字節。此時union的大小是字符串的大小4個字節，并且ch和str的首字節對齊，即ch和str的第一個字符占用同樣位置的内存。

在main函數裡首先将str的值賦為一個長度為3的字符串ABC。根據上面的分析，此時字符ch的值應該和str[0]的值一緻，因此第二個printf的預期輸出應該是字符A。

可以看到printf的輸出支持上面的分析。這個例子從側面揭示了union中包含不同長度的數據成員時它們在内存中的位置關系。

數據結構應用實例

本節将通過兩個例子介紹如何使用棧和隊列解決實際問題。逆波蘭表達式求值的例子利用到了棧後進先出的特點，而為像素點染色的例子利用了隊列先進先出的特點。在解決實際問題時，要根據問題本身的要求和特性選擇合适的數據結構，以達到事半功倍的效果。

10.1.24 逆波蘭表達式求值

數學書上通常将代數運算表達式表示成"操作數 操作符 操作數"的形式，比如3 4表示加法運算，它的兩個操作數分别是3和4；5 * 2表示乘法運算，它的兩個操作數分别是5和2。逆波蘭表達式是将操作數按順序依次放在操作符之前的表達式，如3 4在逆波蘭表達式中就是3 4 ，而5 * 2在逆波蘭表達式中是5 2 *。一個稍微複雜一些的例子是四則運算的混合：

3 4 * 5 – 2

在逆波蘭表達式中，4 * 5首先被表示成4 5 *：

3 4 5 * - 2

加法運算3 4 5 *的兩個操作數現在分别是3和4 5 *，它的逆波蘭表達式為3 4 5 * ：

3 4 5 * - 2

最後減法的操作數分别是3 4 5 * 和2，因此該四則運算最終的逆波蘭表達式為：

3 4 5 * 2 –

給定上述逆波蘭表達式，可以在隻遍曆輸入數據一次的情況下，利用棧求得逆波蘭表達式的值，在上面的例子中，這個值等于21。解決逆波蘭表達式的思路是：從左到右遍曆逆波蘭表達式中的所有字符，如果遇到一個操作數，就将操作數壓入一個操作數棧；如果遇到一個操作符，就将操作數棧最上端的兩個操作數彈出，利用操作符進行計算，并将計算結果壓棧。這時，計算結果就成為了未來操作符的操作數。當整個逆波蘭表達式被處理完之後，棧中隻剩下唯一的一個元素，這個元素就是最後一個操作符對應的結果，也就是整個逆波蘭表達式的值，如例程10-11所示：

例程 10‑11 逆波蘭表達式求值

310 #include <stdio.h>

311 #define STACK_SIZE1000

312 int head, tail;

313 int stack[STACK_SIZE];

314 void push(int element)

315 {

316 stack[tail] = element;

317 tail ;

318 }

319 int pop()

320 {

321 tail--;

322 returnstack[tail];

323 }

324 void cleanStack()

325 {

326 tail = head;

327 }

328 int peek()

329 {

330 return stack[tail - 1];

331 }

332 void printStack()

333 {

334 for (int i = head; i < tail; i )

335 printf("%d ", stack[i]);

336 printf("\n");

337 }

338 int main()

339 {

340 head = 0;//棧底

341 tail = 0;//棧頂

342 char RPN[20] = "345* 2-";//逆波蘭表達式

343 int i = 0;//字符串下标

344 int op1, op2;//操作數

345 while (RPN[i] != 0)

346 {

347 if (RPN[i] >= '0' && RPN[i] <= '9')

348 {

349 push(RPN[i] - '0');

350 }

351 else

352 {

353 op2 = pop();

354 op1 = pop();

355 switch (RPN[i])

356 {

357 case ' ':

358 push(op1 op2);

359 break;

360 case '-':

361 push(op1 - op2);

362 break;

363 case '*':

364 push(op1 * op2);

365 break;

366 case '/':

367 push(op1 / op2);

368 break;

369 default:

370 printf("輸入錯誤！\n");

371 }

372 }

373 i ;

374 }

375 printf("%d\n", pop());

376 return 0;

377 }

程序的運行結果如圖10-11 所示：

圖 10‑11 逆波蘭表達式求值

例程10-11中的程序相對比較複雜，這裡來逐行解釋main函數中的代碼（main函數之前的代碼和此前棧一節中的代碼一緻）：

第31到32行：定義了棧底和棧頂指針；

第33行：定義了要求值的逆波蘭表達式；

第34行：定義了用來訪問逆波蘭表達式每個字符的下标。接下來的while循環将會遍曆表達式中的每個字符；

第35行：定義了兩個操作數；

第36行：進入while循環。在while循環中會依次訪問字符串表達式的每一個字符，并根據字符是操作符還是操作數進行不同的處理；

第38到41行：如果字符是一個操作數，就将這個操作數壓入棧中；

第42行：進入else，這時字符本身是一個操作符。

第44到45行：對于操作符，将棧中的最上面兩個元素彈出，作為操作符使用的兩個操作數；

第46行：進入switch。針對不同的操作符進行不同的處理；

第48到50行：如果操作符是加法，将兩個操作數相加，并将結果壓入棧中；

第51到53行：如果操作符是減法，将兩個操作數相加，并将結果壓入棧中；

第54到56行：如果操作符是乘法，将兩個操作數相加，并将結果壓入棧中；

第57到59行：如果操作符是除法，将兩個操作數相加，并将結果壓入棧中；

第60到61行：如果操作符不滿足上述情況，則提示輸入錯誤；

第64行：将下标加1，訪問下一個字符；

第66行：此時已經跳出了while函數之外，即處理完了所有的操作符和操作數。如果一切正确，現在棧中應該隻有一個元素，并且這個元素是處理最後一個操作符時得到的結果——整個逆波蘭表達式的值。将這個值輸出；

10.1.25 為像素點染色

在使用畫圖程序時經常會選擇某種顔色，然後在一個封閉圖形内部點一下鼠标，就可将圖形内染上同一種顔色。在已知封閉圖形邊界和鼠标位置的情況下，如何将所有處于圖形内部的像素點染上同一種顔色？更加具體的描述是：給定一個隻包含0和1的二維數組，用1表示封閉圖形的邊界，0表示底色。給定一個大于1的整數（表示某一種特定顔色），以及一個二維坐标（保證在圖形内部），将二維數組中處在這個封閉圖形中的元素都賦值為這種顔色。

首先，給定的像素當然應該被染色。将這個像素染色完畢之後，下一步應該是查看這個像素的四個鄰居，如果它們是0，那意味着這些鄰居還在圖形内部，也應該被染色；如果它們有1，那麼意味着像素已經接近了圖形邊界，有些鄰居不需要染色了。對于4個鄰居中為0的像素，這個過程應該不斷進行下去，即它們也應該檢查它們的鄰居，如果有為0的，就将它染色，并繼續檢查它的鄰居，直到将邊界内的所有像素染色完成。

上述過程可以用隊列來實現：在隊列中保存探查到的尚未染色且在内部的點，隻要隊列非空，就開始處理隊首的像素，将它染色，并檢查它的鄰居。如果它的鄰居當中有像素點尚未染色，且還沒有加入到隊列中，就将這個像素加入到隊列中來。下面是例程的實現，如例程10-12所示：

例程 10‑12 為像素點染色

378 #include <stdio.h>

379 #define QUEUE_SIZE100

380 #define SIZE 8

381 struct Pos

382 {

383 int i;

384 int j;

385 };

386 int head, tail;

387 struct Pos queue[QUEUE_SIZE];

388 void enQueue(struct Pos element)

389 {

390 queue[tail] = element;

391 tail ;

392 }

393 struct Pos deQueue()

394 {

395 head ;

396 return queue[head - 1];

397 }

398 int main()

399 {

400 head = 0;//隊首

401 tail = 0;//隊尾

402 int image[SIZE][SIZE] = {{0, 0, 0, 0, 0, 0, 0, 0},

403 {0, 0, 1, 1, 0, 0, 0, 0},

404 {0, 1, 0, 0, 1, 0, 0, 0},

405 {0, 1, 0, 0, 1, 1, 1, 0},

406 {0, 1, 0, 0, 0, 0, 1, 0},

407 {0, 1, 0, 0, 0, 0, 1, 0},

408 {0, 0, 1, 1, 1, 1, 1, 0},

409 {0, 0, 0, 0, 0, 0, 0, 0}};//要染色的圖片

410 for (int i = 0; i < SIZE; i )

411 {

412 for (int j = 0; j < SIZE; j )

413 {

414 if (image[i][j] != 0)

415 printf("%d ", image[i][j]);

416 else

417 printf(" ");

418 }

419 printf("\n");

420 }

421 printf("\n");

422 struct Pos start = {2, 2};

423 enQueue(start);

424 int color = 2;

425 int inQueue = 3;

426 while (head != tail)

427 {

428 struct Pos p = deQueue();

429 image[p.i][p.j] = color;

430 struct Pos neighbor;

431 if (p.i > 0)

432 {

433 neighbor.i = p.i - 1;

434 neighbor.j = p.j;

435 if (image[neighbor.i][neighbor.j] == 0)

436 {

437 enQueue(neighbor);

438 image[neighbor.i][neighbor.j] = inQueue;

439 }

440 }

441 if (p.i < SIZE - 1)

442 {

443 neighbor.i = p.i 1;

444 neighbor.j = p.j;

445 if (image[neighbor.i][neighbor.j] == 0)

446 {

447 enQueue(neighbor);

448 image[neighbor.i][neighbor.j] = inQueue;

449 }

450 }

451 if (p.j > 0)

452 {

453 neighbor.i = p.i;

454 neighbor.j = p.j - 1;

455 if (image[neighbor.i][neighbor.j] == 0)

456 {

457 enQueue(neighbor);

458 image[neighbor.i][neighbor.j] = inQueue;

459 }

460 }

461 if (p.j < SIZE - 1)

462 {

463 neighbor.i = p.i;

464 neighbor.j = p.j 1;

465 if (image[neighbor.i][neighbor.j] == 0)

466 {

467 enQueue(neighbor);

468 image[neighbor.i][neighbor.j] = inQueue;

469 }

470 }

471 }

472 for (int i = 0; i < SIZE; i )

473 {

474 for (int j = 0; j < SIZE; j )

475 {

476 if (image[i][j] != 0)

477 printf("%d ", image[i][j]);

478 else

479 printf(" ");

480 }

481 printf("\n");

482 }

483 return 0;

484 }

程序的運行結果如圖10-12所示：

圖 10‑12 為像素點染色

逐行講解main函數中的程序：

第23到24行：定義了隊首和隊尾，并将它們初始化為0，即一個空隊列；

第25到32行：定義了一張要染色的圖片。這個圖片以二維數組的形式來表示，每一個元素的值是0或者1，表示像素點的顔色；

第33到44行：利用for循環将圖片打印在控制台上；

第45行：利用Pos結構體定義了一個起點像素。接下來要将和這個像素向連通的區域（相同顔色的像素）染上新的顔色；

第46行：将起點像素加入到隊列中去。目前隊列中隻有一個元素；

第47行：定義了要染上的新顔色2；

第48行：定義了一個标簽，用來表示像素點是否已經在隊列中。這是因為一個像素點A可能是好幾個像素點B、C和D的鄰居，如果像素B、C和D都已經在隊列中了，那麼就會多次訪問A，如果不加區别，A就會被重複加入到隊列中。因此程序中需要一個标簽來表明A像素是否處于已經加入隊列的狀态；

第49行：進入while循環，開始從隊首處理隊列中的像素點；

第51行：将隊首的元素p取出，這是本次while循環将要處理的像素點；

第52行：取出元素後要做的第一件事：将這個像素染色；

第53行：定義了一個新的Pos結構體neighbor，用來表示要處理的像素的鄰居。接下來的程序朝四個方向分别檢查四個鄰居的狀态；

第54到63行：如果p的行号大于0，那麼p存在一個上方的鄰居。檢查這個鄰居的顔色是否和p一樣（p的顔色是0），如果一緻，那麼這個元素也需要被染色。将這個元素加入到隊列中，并将圖中這個元素的顔色标記為已經在隊列中；

第64到73行：處理p下方的鄰居；

第74到83行：處理p左側的鄰居；

第84到93行：處理p右側的鄰居；

第95到105行：利用printf打印染色之後的圖片；

第106行：返回。

在例程中，像素點一共有4種可能的狀态：0表示底色，1表示邊界， color表示要上的顔色，inQueue表示像素點已經在隊列中，等待被處理（處理完之後像素點的值從inQueue變成color）。inQueue可以避免同一個像素點被反複加入到隊列中。

本章小結

本章主要講解了C語言中的基本數據結構，其中包括棧、隊列、鍊表，還講解結構體以及共同體等，通過本章的學習可以掌握C語言中的基本數據結構，以及在實際開發中的應用。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!