在[緒論](http://blog.csdn.net/u013595419/article/details/50461536)中,我們介紹了數據結構三要素, [第1章](http://blog.csdn.net/u013595419/article/details/50461712)中,講解了邏輯結構分類中線性結構的第一個部分——一般線性表,這章開始講解邏輯結構線性結構的第二個部分——受限的線性表。這里先鞏固下邏輯結構的分類,如下圖所示:

受限線性表最簡單直白的理解便是插入,刪除,查找等操作時,不能隨心所欲的進行,必須遵循一定的限制(規則)。
## 一.棧
### 1.1定義
棧(stack)是一種只允許在一端進行插入或刪除操作的線性表。
一般規定,棧只能在棧頂進行插入,刪除操作。因此訪問元素的順序是先進后出。
如下圖所示:

這里介紹幾個重要的概念:
> - 棧頂(top):棧的操作中,僅允許插入和刪除的那一端。
> - 棧底(bottom):固定的,不允許進行插入和刪除操作的那一端。
> - 空棧:不含有任何元素的空線性表。
### 1.2基本操作
~~~
InitStack(&S) //初始化一個空棧S
StackEmpty(S) //判斷一個棧是否為空
Push(&S,x) //入棧,若棧未滿,則將x加入使之稱為新棧頂
Pop(&S,x) //出棧,若棧非空,則彈出棧頂元素,并用x返回
GetTop(S,&x) //讀取棧頂元素,若棧S非空,則用x返回棧頂元素
ClearStack(S) //銷毀棧,并釋放棧S占用的存儲空間
~~~
## 二.隊列
### 2.1定義
隊列(Queue)簡稱隊,只允許在線性表的一端進行插入,另一端進行刪除。
一般規定,只能在隊尾進行插入操作,隊頭進行刪除操作。因此訪問時的順序是先進先出。
如下圖所示:

介紹幾個重要的概念:
> - 隊頭:允許刪除的一端,又稱為隊首。
> - 隊尾:允許插入的一端。
> - 空隊列:不含任何元素的空表。
### 2.2基本操作
~~~
InitQueue(&Q) //初始化隊列,構造一個空隊列
QueueEmpty(&Q) //判斷隊列是否為空
EnQueue(&Q,x) //入隊,若隊列Q未滿,將x加入,使之稱為新的隊尾
DeQueue(&Q,&x) //出隊,若隊列Q非空,刪除隊頭元素,并用x返回
GetHead(Q,&x) //讀取隊頭元素,若隊列非空,則將隊頭元素賦值給x
~~~
## 三.串
### 3.1定義
字符串(string)簡稱串,是由零個或多個字符組成的有窮序列。
介紹幾個重要概念:
> - 串長:串中所含字符的個數
> - 子串:一個串中任意個連續字符組成的子序列(含空串,但不含串本身)
> - 主串:包含子串的串
> - 空串:含零個字符的串,通常用 Φ 表示。
### 3.2基本操作
~~~
StrAssign(&T,chars) //由字符串常量chars生成字符串T的操作。
StrCopy(&T,S) //由串S復制生成串T的操作。
StrCompare(S,T) //若S=T返回0,S>T返回正數,S<T返回負數。
StrLength(S) //返回串S的長度。
Concat(&T,S1,S2) //將串S1和S2連接起來生成串T的操作。
SubString(&Sub,S,pos,len)//以串S中pos位置開始的len個字符生成子串Sub的操作。
Index(S,T,pos) //返回子串T在S中pos個字符以后出現的位置。
Replace(&S,T,V) //將串S中所有不重疊子串T替換為串V的操作。
StrInsert(&S,pos,T) //在串S中第pos個字符前插入串T的操作。
StrDelete(&S,pos,len) //刪除串S中第pos個字符開始的len個字符的操作
~~~
- 前言
- 緒論
- 第1章線性表
- 第1章第1節 線性表的順序表示
- 第1章第1節練習題1 刪除最小值
- 第1章第1節練習題2 逆置順序表
- 第1章第1節練習題3 刪除指定元素
- 第1章第1節練習題4 有序表刪除指定區間值
- 第1章第1節練習題5 無序表刪除指定區間值
- 第1章第1節練習題6 刪除重復值
- 第1章第1節練習題7 順序表的歸并
- 第1章第1節練習題8 順序表循環移位
- 第1章第1節練習題9 查找指定值
- 第1章第1節練習題10 查找中位數
- 第1章第2節 線性表的鏈式表示(1)
- 第1章第2節 線性表的鏈式表示(2)
- 第1章第2節 線性表的鏈式表示(3)
- 第1章第2節練習題1 遞歸刪除指定結點
- 第1章第2節練習題2 非遞歸刪除指定結點
- 第1章第2節練習題3 刪除最小值結點
- 第1章第2節練習題4 刪除指定區間結點
- 第1章第2節練習題5 刪除重復結點
- 第1章第2節練習題6 反向輸出
- 第1章第2節練習題7 遞減輸出
- 第1章第2節練習題8 奇偶拆分單鏈表
- 第1章第2節練習題9 查找公共結點
- 第1章第2節練習題10 查找指定倒數結點
- 第1章第2節練習題11 就地逆置單鏈表
- 第1章第2節練習題12 單鏈表之插入排序
- 第1章第2節練習題13 單鏈表之選擇排序
- 第1章第2節練習題14 判斷子序列
- 第1章第2節練習題15 拆分并逆序單鏈表
- 第1章第2節練習題16 歸并并逆序單鏈表
- 第1章第2節練習題17 使用相同值結形成新單鏈表
- 第1章第2節練習題18 求兩個單鏈表的交集
- 第1章第2節練習題19 判斷循環雙鏈表對稱
- 第1章第2節練習題20 連接兩個循環單鏈表
- 第1章第2節練習題21 輸出并刪除最小值結點
- 第1章第2節練習題22 按結點訪問頻度排序
- 第1章第3節 線性表的比較
- 第2章受限的線性表
- 第2章第1節 棧
- 第2章第1節練習題1 判斷棧的操作次序是否合法
- 第2章第1節練習題2 判斷是否中心對稱
- 第2章第2節 隊列
- 第2章第1節練習題3 共享棧的基本操作
- 第2章第2節練習題1 逆置隊列
- 第2章第2節練習題2 使用棧模擬隊列操作
- 第2章第2節練習題3 使用隊列模擬渡口管理
- 第2章第3節 串
- 第2章第3節練習題1 串的模式匹配(Basic)
- 第2章第3節練習題2 串的模式匹配(KMP)