1. 請問「多個棧共存時,最好用鏈式存儲空間作為存儲結構」，這是為什麼啊
如果只有兩個棧，則可以將一個放在數組的低空間，一個放在高空間，兩者從兩頭向中間擴展，這樣沒有空間浪費
如果多於兩個棧時，還是採用順序存儲，則一個滿了另外棧空間雖然有空，但是必須要移動棧中元素才能使用別的浪費的空間，這樣演算法的效率就不高了，此時不如直接採用鏈接存儲好了
2. 棧與隊列
隊列 ：只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。
棧 ：是限定僅在表尾進行插入和刪除操作的線表。
兩棧共享 ：只針對兩個具有相同類型的棧的一個設計，一個棧增長，一個棧縮短，（相當於一個棧的棧底為數組的始端，下標為0處，另一個棧的棧底為末端，兩個棧如果增加元素，就是兩端點向中間延伸）否則會因棧滿而溢出。這樣讓兩個棧共享數據，可以最大化地利用數據空間。
棧的鏈式存儲結構： 對於鏈棧，基本不存在棧滿的情況，除非內存已經沒有可以使用的空間。此時計算機面臨死機崩潰問題。
鏈棧的空其實就是top=NULL
**順序棧與鏈棧的區別：
**
遞歸函數： 一個直接調用自己或通過一系列的調用語句間接的調用自己的函數。
迭代 使用循環結構，遞歸使用選擇結構
**棧的四則運算表達式求值
**
中綴表達式----->後綴表達式：
3. 兩棧共享空間
1.如果有兩個相同類型的棧，我們為它們各自開辟了數組空間，極有可能 一個棧已經滿了，再進棧就溢出了，而另一個棧還有很多存儲空間空間 。
2.所以我們可以使用 一個數組來存儲兩個棧 。
3.具體做法如下：數組有兩個端點，兩個棧有兩個棧底，讓 一個棧的棧底為數組的始端，即下標為0處 ， 另一個棧為數組的末端，即下標為數組長度n-1處
這樣，兩個棧如果增加元素，就是 兩端點向中間延伸
與上一遍順序棧的程序不同的是，此處採用下標記錄棧頂位置，而非指針，且並沒有指向棧頂的下一個存儲空間
如下圖所示：
測試：
4. 設有兩個堆棧S1，S2都採用順序棧方式，並且共享一個存儲區，採用棧頂相向、迎面增長的存貯方式，
1
s1空：S1的棧頂等於棧底
s2空：s2的棧頂等於棧底
2
s1滿：S1的棧頂等於S2的棧頂
s2滿：S2的棧頂等於S1的棧頂
#include
#define
TYPE_S1
1
#define
TYPE_S2
-1
#define
STACK_SIZE
20
void
StackPush(int
**stackTop,
int
elmnt,
int
type)
{
**stackTop
=
elmnt;
*stackTop
+=
type;
}
void
main()
{
int
stack[STACK_SIZE]
=
{0};
int
*S1Top
=
&stack[0],
*S2Top
=
&stack[STACK_SIZE
-
1];
int
i,
input
=0;
for
(i
=
0;
i
<
20;
i++)
{
printf("請輸入一個整數：");
scanf("%d",
&input);
if(input
%
2
==0)
{
StackPush(&S1Top,
input,
TYPE_S1);
}
else
{
StackPush(&S2Top,
input,
TYPE_S2);
}
if(S1Top
==
S2Top)
{
printf("堆棧已滿\n");
break;
}
}
return;
}
5. 單共享棧
棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性數據結構。應用廣，作用大。
一、1、 棧的定義：限定僅在表尾進行插入或刪除操作的線性表，因此，對棧來說，表尾端有其特殊含義，表尾—棧頂(top) ，表頭—棧底(bottom) ，不含元素的空表稱空棧。
例4：計算機系2001年考研題（程序設計基礎）
設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：
A）a，b，c，d B）c，d，a，b
C）b，c，d，a D）a，c，d，b
A、D可以（ B、C不行）。
答：
例5、習題集P22 3.4
status algo1(stack s)
{int i,n,a[255];
n=0;
While(!stackempty(s))
{n++;
pop (s,a[n]);}
For(i=1;i<=n;i++) push (s,a[i]);
}
5、補充公式：
若輸入的序列為1、2、3 ….n，則可能出現的輸出序列符合卡塔南數列：
驗證：
二、 棧的表示和實現：
順序存貯結構__順序棧；
鏈式存貯結構__鏈棧；
（一） 順序棧
利用一組地址連續的存貯單元依次自棧底到棧頂存放棧的數據元素.
棧底元素是最先進入的，實際上是線性表的第一個元素
數組（靜態數組）：空間固定
動態數組：動態申請空間（用指針表示）
表示容量；
表示數據元素個數；
// 順序棧的C表示
利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時附設指針top指示棧頂元素在順序棧中的位置；base表示棧底指針；
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{ SElemType *Base; // 棧底指針
SElemType *Top; // 棧頂指針
int StackSize;//當前已分配的存儲空間，以元素為 單位。
}SqStack
空棧
A
A進棧
top
base
top
base
s.top=0 或s.top=s.base 表示空棧；
s.base=NULL表示棧不存在；
當插入新的棧頂元素時，指針s.top++；
刪除棧頂元素時，指針s.top--；
當s.top-s.base>=stacksize時，棧滿，溢出
順序棧初始化
SqStack s;
s.Base = NULL;
s.Top = NULL;
s.StackSize = 0;
base
stacksize
top
&s
s.base = s.top =
( SElemType *)malloc( STACK_INIT_SIZE * sizeof( SElemType ));
順序棧的C圖示
base
top
空棧：
base = top;
A
base
top
*top = A;
top ++;
E
C
B
A
D
base
top
B
A
base
top
出棧：
if( top != base )
{
top --;
e = *top;
}
入棧：
if( 沒有空間 )
{
//realloc，調整top
}
順序棧基本演算法_InitStack
// 初始化順序棧, 構造一個空棧
Status InitStack( SqStack &S )
{
s.base = (SElemType *)malloc(
STACK_INIT_SIZE * sizeof( SElemType));
if( !s.base )
{
return OVERFLOW;
}
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return OK;
}// InitStack
順序棧基本演算法：GetTop
// 用e返回棧S的棧頂元素，若棧空，函數返回ERROR
Status GetTop( SqStack S, SElemType &e)
{
if( s.top != s.base ) // 棧空嗎？
{
e = *( s.top – 1 );
return OK;
}
else
{
return ERROR;
}
}// GetTop
順序棧基本演算法：Push
//把元素e入棧
Status Push(SqStack &S, SElemType e )
{
// 若棧，追加存貯空間
if( s.top == s.base + s.stacksize )
{
p = (SElemType *)realloc( s.base,
(s.stacksize + STACKINCREMENT)*sizeof(SElemType));
if( !p )
{
return OVERFLOW;
}
s.base = p;
順序棧基本演算法：Push
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*s.top = e;
s.top++;
return OK;
}// Push
順序棧基本演算法：Pop
// 出棧
Status Pop( SqStack &S, SElemType &e )
{
if( s.top == s.base ) // 空嗎？
{
return ERROR;
}
s.top --;
e = *s.top;
return OK;
}// Pop
順序棧基本演算法：其他
// 取順序棧長度
int StackLength( SqStack S )
{
return s.top – s.base;
}// StackLength
#define StackLength( S ) ((S).top – (S).base)
// 順序棧空嗎？
Status StackEmpty( SqStack S )
{
return s.top == s.base ? TRUE:FALSE;
}
#define StackEmpty( S ) (((S).top == (S).base )?TRUE:FALSE)
順序棧基本演算法：ClearStack
// 清空棧
Status ClearStack( SqStack S )
{
if( s.base )
{
s.top = s.base;
}
return OK;
}// ClearStack
順序棧基本演算法：DestroyStack
// 銷毀棧
Status DestroyStack( SqStack &S )
{
if( s.base )
{
free( s.base );
s.stacksize = 0;
s.base = s.top = NULL;
}
}// DestroyStack
3.1.3 鏈棧
棧的鏈式存儲結構稱為鏈棧，它的運算是受限的單鏈表，插入和刪除操作僅限制在表頭位置上進行。由於只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針。
鏈棧的類型說明如下：
棧的鏈接存儲結構
鏈棧的結點定義
typedef struct node
{ ElemType data;
struct node *next;
} LinkStack;
棧的鏈接表示 — 鏈式棧
鏈式棧無棧滿問題，空間可擴充
插入與刪除僅在棧頂處執行
鏈式棧的棧頂在鏈頭
適合於多棧操作
鏈棧的進棧演算法
LinkStack *PUSH (LinkStack *top, ElemType x)
{ LinkStack *p;
p＝malloc(sizeof(LinkStack));
p->data＝x; p->next＝top;top=p;
return top;
}
鏈棧的出棧演算法
linkstack *POP (linkstack *top, ElemType *datap)
{ linkstack *p;
if (top==NULL)
{printf(「under flow\n」); return NULL;}
else
{ *datap＝top->data;
p＝top;
top＝top->next;
free(p);
return top;
}
}
棧的共享存儲單元
有時，一個程序設計中，需要使用多個同一類型的棧,這時候，可能會產生一個棧空間過小，容量發生溢出，而另一個棧空間過大，造成大量存儲單元浪費的現象。 為了充分利用各個棧的存儲空間，這時可以採用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現存儲空間優勢互補。
棧的應用---基本應用
void read_write()
{ stack S;
int n,x;
cout<<」Please input num int n」;
cin>>n; //輸入元素個數
init_stack(S); //初始化棧
for (i=1; i<=n; i++)
{ cin>>x; //讀入一個數
push_stack(S,x); //入棧
}
while (stack_empty(S)!=TRUE)
{stack_top(S,x); //取出棧頂元素
cout<<x; //輸出
pop_stack(S); //退棧
}
}
讀入一個有限大小的整數n，並讀入n個整數，然後按輸入次序的相反次序輸出各元素的值。
3.2 棧的應用舉例
一、 數制轉換
二、 括弧匹配的檢驗
三、 行編輯程序問題
四、 表達式求值
五、 迷宮求解
六、 實現遞歸
一、數制轉換
十進制N和其它進制數的轉換是計算機實現計算的基本問題,其解決方法很多,其中一個簡單演算法基於下列原理:
N=(n div d)*d+n mod d
( 其中:div為整除運算,mod為求余運算)
例如 (1348)10=(2504)8，
其運算過程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
0
計算順序
輸出順序
演算法分析：
由十進制轉換為其他進制的數的規則，可知，求得的余數的順序為由低位到高位，而輸出則是由高位到低位。
因此，這正好利用棧的特點，先將求得的余數依次入棧，輸出時，再將棧中的數據出棧。
void conversion () {
InitStack(S); // 構造空棧
scanf ("%d",&N); //輸入一個十進制數
while (N) {
Push(S, N % 8); // "余數"入棧
N = N/8; // 非零"商"繼續運算
}
while (!StackEmpty(S)) {
Pop(S,&e);
//和"求余"所得相逆的順序輸出八進制的各位數
printf ( "%d", e );
}
} // conversion
二、 括弧匹配的檢驗
假設在表達式中
(〔〕（））或〔（〔 〕〔 〕）〕
等為正確的格式，
（〔]（ ） 或（（）））或 〔（ 〕）均為不正確的格式。
則 檢驗括弧是否匹配的方法可用「期待的急迫程度」這個概念來描述。
演算法的設計思想：
讀入表達式
1）凡出現左括弧，則進棧；
2）凡出現右括弧，首先檢查棧是否空
若棧空，則表明該「右括弧」多餘，
否則和棧頂元素比較，
若相匹配，則「左括弧出棧」 ，
否則表明不匹配。
3）表達式檢驗結束時，
若棧空，則表明表達式中匹配正確，
否則表明「左括弧」有餘。
Status matching(char exp[ ] ) {
while (i<=Length(exp)) {
switch exp[i] {
case '(『 || '[' :{Push(S,exp[i]); i++; break;}
case ')' : {
if( ！StackEmpty(S)&& GetTop(S)= '(' ）
{Pop(S,e); i++;}
else return ERROR;
break; }
case 『]' : {
if( ！StackEmpty(S)&& GetTop(S)= 『[' ）
{Pop(S,e); i++;}
else return ERROR;
break; } }
if (StackEmpty(S)) return OK;
}
三、行編輯程序問題
「每接受一個字元即存入存儲器」 ?
並不恰當！
設立一個輸入緩沖區，用以接受用戶輸入的一行字元，然後逐行存入用戶數據區,並假設「#」為退格符，「@」為退行符。
在用戶輸入一行的過程中，允許用戶輸入出差錯，並在發現有誤時可以及時更正。
合理的作法是：
假設從終端接受了這樣兩行字元：
whli##ilr#e（s#*s)
outcha@putchar(*s=#++);
則實際有效的是下列兩行：
while (*s)
putchar(*s++);
可設這個輸入緩沖區為一個棧結構，每當從終端接受了一個字元之後先作如下判斷：
1、既不是退格也不是退行符，則將該字元壓入棧頂；
2、如果是一個退格符，則從棧頂刪去一個字元；
3、如果是一個退行符，則將字元棧清為空棧 。
while (ch != EOF && ch != '\n') {
switch (ch) {
case 『#』 : Pop(S, c); break;//棧非空，退棧
case '@': ClearStack(S); break;// 重置S為空棧
default : Push(S, ch); break; //未考慮棧滿
}
ch = getchar( ); // 從終端接收下一個字元
}
ClearStack(S); // 重置S為空棧
if (ch != EOF) ch = getchar( );
}
DestroyStack(S); }
Void LineEdit( ) {
InitStack(S);
ch=getchar();
while (ch != EOF) { //EOF為全文結束符
將從棧底到棧頂的字元傳送至調用過程的數據區；
補充習題：
1、設計一個演算法，用棧的基本運算，判定一個字元串是否為對稱字元串，若是，則返回1，否則返回0。（abccba)
四、表達式求值
1、算術表達式的組成：
將表達式視為由操作數、運算符、界限符（稱為單詞）組成。
操作數：常數、變數或符號常量。
算符：運算符、界限符
表達式求值是程序設計語言編譯的一個最基本的問題。它的實現是棧應用的又一典型例子。 僅以算術表達式為例
2、算術表達式的形式：
中綴(infix)表達式——表達式的運算符在操作數的中間。 <操作數> <操作符> <操作數>
例：A*B 例：5+9*7
後綴(postfix)算術表達式(逆波蘭式)——將運算符置兩個操作數後面的算術表達式。 <操作數> <操作數> <操作符>
例：AB* 例：5 9 7*+
前綴(prefix)表達式(波蘭式)又稱波蘭式，與後綴表達式相反。把運算符放在兩個運算數的前面， <操作符> <操作數> <操作數>
例：*AB 例：+5*9 7
3、介紹中綴算術表達式的求值
例如：3*（7 – 2 ）
（1）算術四則運算的規則：
a. 從左算到右
b. 先乘除，後加減
c. 先括弧內，後括弧外
由此，此表達式的計算順序為：
3*（7 – 2 ）= 3 * 5 = 15
（2）根據上述三條運算規則，在運算的每一步中，對任意相繼出現的算符1和2 ，都要比較優先權關系。
一般任意兩個相繼出現的兩個算符p1和p2之間的優先關系至多有下面三種之一：
p1<p2 p2的優先權高於p1
p1=p2 二者優先權相等
p1>p2 p2的優先權低於p1
算符優先法所依據的算符間的優先關系
見教材P53表3.1
θ1<θ2，表明不能進行θ1 的運算，θ2 入棧，讀 下一字元。
θ1>θ2，表明可以進行θ1 的運算，θ1退棧，運算，運算結果入棧。
θ1=θ2，脫括弧，讀下一字元或表達式結束。
（3）演算法思想：
設定兩棧：操作符棧 OPTR ，操作數棧 OPND
棧初始化：設操作數棧 OPND 為空；操作符棧 OPTR 的棧底元素為表達式起始符 『#』；
依次讀入字元：是操作數則入OPND棧，是操作符則要判斷：
if 操作符 < 棧頂元素，則退棧、計算，結果壓入OPND棧；
操作符 = 棧頂元素且不為『#』，脫括弧（彈出左括弧）；
操作符 > 棧頂元素，壓入OPTR棧。
掃描基本符號
是否操作數？
Y
棧頂運算符低
於當前運算符？
操作數
入棧
N
Y
N
運算符
入棧
取出S棧頂運算符和
O棧頂的兩個操作數
運算，結果入棧O
定義運算符棧S
和操作數棧O
棧S為空？
Y
結束
Y
一般作為相同運算符，先出現的比後出現的優先順序高；
先出現的運算符優先順序低於「(」，高於「)」；
後出現的運算符優先順序高於「(」，低於「)」；優先權相等的僅有「(」和「)」、「#」。
#：作為表達式結束符，通常在表達式之前加一「#」使之成對，當出現「#」=「#」時，表明表達式求值結束，「#」的優先順序最低。
OPTR
OPND
INPUT
OPERATE
3*(7-2)#
Push(opnd,』3』)
#
*(7-2)#
3
#
Push(optr,』*』)
#,*
3
(7-2)#
Push(optr,』(』)
#,*,(
3
7-2)#
Push(opnd,』7』)
#,*,(
3,7
-2)#
Push(optr,』-』)
#,*,(,－
3,7
2)#
Push(opnd,』2』)
#,*,(,－
3,7,2
)#
Operate(7-2)
#,*,(
3,5
)#
Pop(optr)
#,*
3,5
#
Operate(3*5)
#
15
#
GetTop(opnd)
例：3*（7-2）
Status EvaluateExpression( OperandType &result) {
InitStack(OPND); InitStack(OPTR);
Push(OPTR ,』#』);c=getchar();
while((c!=『#』)&&(GetTop(OPTR)!=『#』))
{ if (!In(c,OP) { Push(OPND,c); c=getchar();}
else switch(compare(c,GetTop(OPTR)))
{case 『>』 : Push(OPTR , c); c=getchar();break;
case 『=』: Pop(OPTR);c=getchar();break;
case 『<』 : temat=Pop(OPTR); b=Pop();a=Pop();
result= Operate(a,temat,b);Push(OPND,result);
c=getchar();break;
} //switch }//while
result=GetTop(OPND);}//EvaluateExpression
此函數在哪裡？
4、計算後綴表達式
（1）為什麼要把中綴表示法變為後綴表示法？
計算機計算表達式是機械執行，只能從左至右掃描。計算中綴表達式比較困難。
後綴表達式的求值過程是自左至右運算符出現的次序和真正的計算次序是完全一樣的。
順序掃描表達式的每一項，根據它的類型做如下相應操作：
若該項是操作數，則將其壓棧；
若該項是操作符<op>，則連續從棧中退出兩個操作數Y和X，形成運算指令X<op>Y，並將計算結果重新壓棧。
當表達式的所有項都掃描並處理完後，棧頂存放的就是最後的計
算結果。
人們仍然使用中綴表達式 ，而讓機器把它們轉換成後綴表達式。
（2）後綴表達式求值實例：
A=B*C + D*(E-F)
ABC*DEF-*+=
ABC*—做 B*C=T1
AT1DEF- –—做E-F=T2
AT1DT2*—做D*T2=T3
AT1T3+—做T1+T3=T4
AT4=—做A=T4
後綴表達式「32422*+13*-^*5-」，棧中狀態變化情況：
typedef char elemtype ;
double calcul_exp(char *A) /*本函數返回由後綴表達式A表示的表達式運算結果*/
{ Seq_Starck s ;
ch=*A++ ; Init_SeqStack(s) ;
while ( ch != 』#』 )
{ if (ch!=運算符) Push_SeqStack (s , ch) ;
else { Pop_SeqStack (s , &a) ;
Pop_SeqStack (s , &b) ; /*取出兩個運算量*/
switch (ch).
{ case ch= =』+』： c=b+a ; break ;
case ch= =』-』： c=b-a ; break ;
case ch= =』*』： c=b*a ; break ;
case ch= =』/ 』： c=b/a ; break ;
case ch= =』%』： c=b%a ; break ; }
Push_SeqStack (s, c) ; }
ch=*A++ ;
}
Pop _SeqStack ( s , result ) ;
return result ;
}
（3）中綴表達式變後綴表達式
表達式中操作數次序不變,，運算符次序發生變化,運算符放在操作數的後面。同時去掉了圓括弧 。
例：3+（7*8-9）
運算符的優先數表
5
4
3
2
1
0
優先數
^
*，/
＋，－
＝
）
（
操作
存儲結構
W（I）存放表達式的第I個字元。
利用一個棧S（）。P為棧指針。
演算法設計
Step1：輸入是變數則輸出它；
Step2：是左括弧「（」，無條件地壓入堆棧；
Step3：輸入運算符優先數是2，3，4，5時，如果棧空，則進棧。如果棧不空，則將它與棧頂元進行比較。倘若優先數大於頂元，則進棧；小於頂元，則頂元退棧並輸出之。然後再繼續比較，直到大於頂元或棧空時它進棧；
Step4：若是右括弧「）」，同時棧頂元又為左括弧「（」，則退棧，並抹去「）」。否則按Step3處理；
Step5：輸入完而棧非空，則將棧內內容逐一退棧，並輸出之。
模擬演算法執行過程
A=B*C+D*(E-F)
ABC*DEF-*+=
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
棧s （）:
top=0
A
變數,輸出
輸出:
說明:
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
棧s （）:
A
算符,棧空,入棧
=
輸出:
說明:
top=0
top=0
top=1
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
=
棧s （）:
top=1
A
變數,輸出
輸出:
說明:
B
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
=
棧s （）:
AB
算符*,優先順序等於4,大於棧頂元素=優先順序,入棧
輸出:
說明:
*
top=1
top=1
top=2
)
F
-
6. 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點
順序棧--入棧操作受數組上界的約束有可能發生棧上溢，且需要地址連續的存儲單元。
鏈棧--無須地址連續，便於多個棧共享存儲單元，且不存在棧滿上溢情況。
順序隊列--需地址連續且有假上溢現象（需改為循環隊列才可解決假上溢）
鏈式隊列--特別適合於數據元素變動比較大的情況，且不存在隊列滿而產生的溢出問題。
7. 線性表，棧，隊列的優缺點，異同
三者都是邏輯結構，各有特性，但無所謂優缺點。線性表是一個含有n個元素的有序序列，形成線性結構。這種結構只有一個「第一個元素」和一個「最後一個元素」，除「第一個元素」之外每個元素都有一個前驅，除「最後一個元素」之外每個元素都有一個後繼。對線性表附加存取限制可以得到棧和隊列。棧只允許在棧頂進行存取，有「後進先出」的特性。隊列只允許在隊尾存，在隊首取，有先進先出的特性。三種結構有不同的應用。
8. 若棧採用順序存儲方式存儲,現兩棧共享空間
暈.這么簡單的問題也拿出來問
1 2 3 .m
| |
那麼當他們滿的時候,兩個指針相鄰
那就是
top[1]+1=top[2]
top[1]在top[2]左邊相鄰了
9. 給出用數組描述的棧的存儲結構，以及操作
數據結構復習重點歸納[適於清華嚴版教材]
一、數據結構的章節結構及重點構成
數據結構學科的章節劃分基本上為：概論，線性表，棧和隊列，串，多維數組和廣義表，樹和二叉樹，圖，查找，內排，外排，文件，動態存儲分配。
對於絕大多數的學校而言，「外排，文件，動態存儲分配」三章基本上是不考的，在大多數高校的計算機本科教學過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對於報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那麼這部分朋友就要留意這三章了。
按照以上我們給出的章節以及對後三章的介紹，數據結構的章節比重大致為：
概論：內容很少，概念簡單，分數大多隻有幾分，有的學校甚至不考。
線性表：基礎章節，必考內容之一。考題多數為基本概念題，名校考題中，鮮有大型演算法設計題。如果有，也是與其它章節內容相結合。
棧和隊列：基礎章節，容易出基本概念題，必考內容之一。而棧常與其它章節配合考查，也常與遞歸等概念相聯系進行考查。
串 ：基礎章節，概念較為簡單。專門針對於此章的大型演算法設計題很少，較常見的是根據KMP進行演算法分析。
多維數組及廣義表
：基礎章節，基於數組的演算法題也是常見的，分數比例波動較大，是出題的「可選單元」或「侯補單元」。一般如果要出題，多數不會作為大題出。數組常與「查找，排序」等章節結合來作為大題考查。
樹和二叉樹
：重點難點章節，各校必考章節。各校在此章出題的不同之處在於，是否在本章中出一到兩道大的演算法設計題。通過對多所學校的試卷分析，絕大多數學校在本章都曾有過出大型演算法設計題的歷史。
圖 ：重點難點章節，名校尤愛考。如果作為重點來考，則多出現於分析與設計題型當中，可與樹一章共同構成演算法設計大題的題型設計。
查找
：重點難點章節，概念較多，聯系較為緊密，容易混淆。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。演算法設計型題中可以數組結合來考查，也可以與樹一章結合來考查。
排序
：與查找一章類似，本章同屬於重點難點章節，且概念更多，聯系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序演算法的優劣比較此類的題。演算法設計大題中，如果作為出題，那麼常與數組結合來考查。
二、數據結構各章節重點勾劃：
第0章 概述
本章主要起到總領作用，為讀者進行數據結構的學習進行了一些先期鋪墊。大家主要注意以下幾點：數據結構的基本概念，時間和空間復雜度的概念及度量方法，演算法設計時的注意事項。本章考點不多，只要稍加註意理解即可。
第一章 線性表
作為線性結構的開篇章節，線性表一章在線性結構的學習乃至整個數據結構學科的學習中，其作用都是不可低估的。在這一章，第一次系統性地引入鏈式存儲的概念，鏈式存儲概念將是整個數據結構學科的重中之重，無論哪一章都涉及到了這個概念。
總體來說，線性表一章可供考查的重要考點有以下幾個方面：
1.線性表的相關基本概念，如：前驅、後繼、表長、空表、首元結點，頭結點，頭指針等概念。
2.線性表的結構特點，主要是指：除第一及最後一個元素外，每個結點都只有一個前趨和只有一個後繼。
3.線性表的順序存儲方式及其在具體語言環境下的兩種不同實現：表空間的靜態分配和動態分配。靜態鏈表與順序表的相似及不同之處。
4.線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算：單鏈表、循環鏈表，雙向鏈表，雙向循環鏈表。其中，單鏈表的歸並演算法、循環鏈表的歸並演算法、雙向鏈表及雙向循環鏈表的插入和刪除演算法等都是較為常見的考查方式。此外，近年來在不少學校中還多次出現要求用遞歸演算法實現單鏈表輸出（可能是順序也可能是倒序）的問題。
在鏈表的小題型中，經常考到一些諸如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。
5.線性表的順序存儲及鏈式存儲情況下，其不同的優缺點比較，即其各自適用的場合。單鏈表中設置頭指針、循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。
第二章 棧與隊列
棧與隊列，是很多學習DS的同學遇到第一隻攔路虎，很多人從這一章開始坐暈車，一直暈到現在。所以，理解棧與隊列，是走向DS高手的一條必由之路，。
學習此章前，你可以問一下自己是不是已經知道了以下幾點：
1.棧、隊列的定義及其相關數據結構的概念，包括：順序棧，鏈棧，共享棧，循環隊列，鏈隊等。棧與隊列存取數據（請注意包括：存和取兩部分）的特點。
2.遞歸演算法。棧與遞歸的關系，以及藉助棧將遞歸轉向於非遞歸的經典演算法：n!階乘問題，fib數列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節中進行考查。
3.棧的應用：數值表達式的求解，括弧的配對等的原理，只作原理性了解，具體要求考查此為題目的演算法設計題不多。
4.循環隊列中判隊空、隊滿條件，循環隊列中入隊與出隊演算法。
如果你已經對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，並不是可以不作題哦。
第三章 串
經歷了棧一章的痛苦煎熬後，終於迎來了串一章的柳暗花明。
串，在概念上是比較少的一個章節，也是最容易自學的章節之一，但正如每個過來人所了解的，KMP演算法是這一章的重要關隘，突破此關隘後，走過去又是一馬平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡壘有：
1.串的基本概念，串與線性表的關系（串是其元素均為字元型數據的特殊線性表），空串與空格串的區別，串相等的條件
2.串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的演算法是很多學校在基本操作上的考查重點。
3.順序串與鏈串及塊鏈串的區別和聯系，實現方式。
4.KMP演算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配演算法的不足，明確next數組需要改進之外。其中，理解演算法是核心，會求數組是得分點。不用我多說，這一節內容是本章的重中之重。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP演算法進行匹配的匹配過程。
第四章 數組與廣義表
學過程序語言的朋友，數組的概念我們已經不是第一次見到了，應該已經「一回生，二回熟」了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學里的程序語言所關注的不太一樣，下面會作介紹。
廣義表的概念，是數據結構里第一次出現的。它是線性表或表元素的有限序列，構成該結構的每個子表或元素也是線性結構的，所以，這一章也歸入線性結構中。
本章的考查重點有：
1.多維數組中某數組元素的position求解。一般是給出數組元素的首元素地址和每個元素佔用的地址空間並組給出多維數組的維數，然後要求你求出該數組中的某個元素所在的位置。
2.明確按行存儲和按列存儲的區別和聯系，並能夠按照這兩種不同的存儲方式求解1中類型的題。
3.將特殊矩陣中的元素按相應的換算方式存入數組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的演算法。
4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點，是理解整個廣義表一節演算法的基礎。近來，在一些學校中，出現了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作後的串值，要求求出原廣義表L。大家要留意。
5.與廣義表有關的遞歸演算法。由於廣義表的定義就是遞歸的，所以，與廣義表有關的演算法也常是遞歸形式的。比如：求表深度，復制廣義表等。這種題目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。
第五章 樹與二叉樹
從對線性結構的研究過度到對樹形結構的研究，是數據結構課程學習的一次躍變，此次躍變完成的好壞，將直接關繫到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業課總分。所以，樹這一章的重要性，已經不說自明了。
總體來說，樹一章的知識點包括：
二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種演算法（遞歸與非遞歸），在三種基本遍歷演算法的基礎上實現二叉樹的其它演算法，線索二叉樹的概念和線索化演算法以及線索化後的查找演算法，最優二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷演算法及其與二叉樹遍歷演算法的聯系，樹與森林和二叉樹的轉換。
下面我們來看考試中對以上知識的主要考查方法：
1.二叉樹的概念、性質和存儲結構
考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區別；考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質：第i層的最多結點數，深度為k的二叉樹的最多結點數，n0=n2+1的性質，n個結點的完全二叉樹的深度，順序存儲二叉樹時孩子結點與父結點之間的換算關系（左為：2*i，右為：2*i+1）。
二叉樹的順序存儲和二叉鏈表存儲的各自優缺點及適用場合，二叉樹的三叉鏈表表示方法。
2.二叉樹的三種遍歷演算法
這一知識點掌握的好壞，將直接關繫到樹一章的演算法能否理解，進而關繫到樹一章的演算法設計題能否順利完成。二叉樹的遍歷演算法有三種：先序，中序和後序。其劃分的依據是視其每個演算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸演算法，理解其執行的實際步驟，並且應該熟練掌握三種遍歷的非遞歸演算法。由於二叉樹一章的很多演算法，可以直接根據三種遞歸演算法改造而來（比如：求葉子個數），所以，掌握了三種遍歷的非遞歸演算法後，對付諸如：「利用非遞歸演算法求二叉樹葉子個數」這樣的題目就下筆如有神了。我會在另一篇系列文章（）里給出三種遍歷的遞歸和非遞歸演算法的背記版，到時請大家一定熟記。
3.可在三種遍歷演算法的基礎上改造完成的其它二叉樹演算法：
求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷演算法，那麼解決以上問題就是小菜一碟了。
4.線索二叉樹：
線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現了。對於線索二叉樹，應該掌握：線索化的實質，三種線索化的演算法，線索化後二叉樹的遍歷演算法，基本線索二叉樹的其它演算法問題（如：查找某一類線索二叉樹中指定結點的前驅或後繼結點就是一類常考題）。
5.最優二叉樹（哈夫曼樹）：
最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。最優二叉樹一節，直接考查演算法源碼的很少，一般是給你一組數據，要求你建立基於這組數據的最優二叉樹，並求出其最小權值之和，此類題目不難，屬送分題。
6.樹與森林：
二叉樹是一種特殊的樹，這種特殊不僅僅在於其分支最多為2以及其它特徵，一個最重要的特殊之處是在於：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之後的二叉樹與原二叉樹我們認為是不相同的兩棵二叉樹。但是，對於普通的雙分支樹而言，不具有這種性質。
樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷演算法：先根與後根（對於森林而言稱作：先序與後序遍歷）。在難度比較大的考試中，也有基於此二種演算法的基礎上再進行擴展要求你利用這兩種演算法設計其它演算法的，但一般院校很少有這種考法，最多隻是要求你根據先根或後根寫出他們的遍歷序列。此二者的先根與後根遍歷與二叉樹中的遍歷演算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而後根遍歷對應二叉樹的中序遍歷。這一點成為很多學校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然後回答這個問題。二叉樹、樹與森林之所以能有以上的對應關系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。
樹一章，處處是重點，道道是考題，大家務必個個過關。
第六章 圖
如果說，從線性結構向樹形結構研究的轉變，是數據結構學科對數據組織形式研究的一次升華，那麼從樹形結構的研究轉到圖形結構的研究，則進一步讓我們看到了數據結構對於解決實際問題的重大推動作用。
圖這一章的特點是：概念繁多，與離散數學中圖的概念聯系緊密，演算法復雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。
下面我們看一下圖這一章的主要考點以及這些考點的考查方式：
1.考查有關圖的基本概念問題：
這些概念是進行圖一章學習的基礎，這一章的概念包括：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，迴路，（強）連通圖，（強）連通分量等概念。與這些概念相聯系的相關計算題也應該掌握。
2.考查圖的幾種存儲形式：
圖的存儲形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用演算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。
3.考查圖的兩種遍歷演算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷演算法，這兩個演算法對圖一章的重要性等同於「先序、中序、後序遍歷」對於二叉樹一章的重要性。在考查時，圖一章的演算法設計題常常是基於這兩種基本的遍歷演算法而設計的，比如：「求最長的最短路徑問題」和「判斷兩頂點間是否存在長為K的簡單路徑問題」，就分別用到了廣度遍歷和深度遍歷演算法。
4.生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM演算法和KRUSKAL演算法。
考查時，一般不要求寫出演算法源碼，而是要求根據這兩種最小生成樹的演算法思想寫出其構造過程及最終生成的最小生成樹。
5.拓撲排序問題：
拓撲排序有兩種方法，一是無前趨的頂點優先演算法，二是無後繼的頂點優先演算法。換句話說，一種是「從前向後」的排序，一種是「從後向前」排。當然，後一種排序出來的結果是「逆拓撲有序」的。
6.關鍵路徑問題：
這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑，二是最早時間是什麼意思、如何求，三是最晚時間是什麼意思、如何求。簡單地說，最早時間是通過「從前向後」的方法求的，而最晚時間是通過「從後向前」的方法求解的，並且，要想求最晚時間必須是在所有的最早時間都已經求出來之後才能進行。這個問題拿來直接考演算法源碼的不多，一般是要求按照書上的演算法描述求解的過程和步驟。
在實際設計關鍵路徑的演算法時，還應該注意以下這一點：採用鄰接表的存儲結構，求最早時間和最晚時間要採用不同的處理方法，即：在演算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。
7.最短路徑問題：
與關鍵路徑問題並稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是演算法的理解。最短路徑問題分為兩種：一是求從某一點出發到其餘各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅遊景點及旅遊路線的選擇問題。解決第一個問題用DIJSKTRA演算法，解決第二個問題用FLOYD演算法。注意區分。
第七章 查找
在不少數據結構的教材中，是把查找與排序放入高級數據結構中的。應該說，查找和排序兩章是前面我們所學的知識的綜合運用，用到了樹、也用到了鏈表等知識，對這些數據結構某一方面的運用就構成了查找和排序。
現實生活中，search幾乎無處不在，特別是現在的網路時代，萬事離不開search，小到文檔內文字的搜索，大到INTERNET上的搜索，search占據了我們上網的大部分時間。
在復習這一章的知識時，你需要先弄清楚以下幾個概念：
關鍵字、主關鍵字、次關鍵字的含義；靜態查找與動態查找的含義及區別；平均查找長度ASL的概念及在各種查找演算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。
在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹表上的查找；3rd，在哈希表上的查找。下面詳細介紹其考查知識點及考查方式：
1.線性表上的查找：
主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。考生需要注意這三種表下的ASL值以及三種演算法的實現。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。
2.樹表上的查找：
這是本章的重點和難點。由於這一節介紹的內容是使用樹表進行的查找，所以很容易與樹一間的某些概念相混淆。本節內容與樹一章的內容有聯系，但也有很多不同，應注意規納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密，二叉樹一章學好了，這里也就不難了。
二叉排序樹，簡言之，就是「左小右大」，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大於1。對於二叉排序樹，「判斷某棵二叉樹是否二叉排序樹」這一演算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整演算法，所以應該掌握平衡二叉樹的四種調整演算法，調整的一個參照是：調整前後的中序遍歷結果相同。
B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找演算法外，應該特別注意一下B樹的插入和刪除演算法。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。B樹是報考名校的同學應該關注的焦點之一。
鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。
3.基本哈希表的查找演算法：
哈希一詞，是外來詞，譯自「hash」一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。基於哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。
第八章 內部排序
內排是DS課程中最後一個重要的章節，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型演算法題。但是，歸結到一點，就是考查你對書本上的各種排序演算法及其思想以及其優缺點和性能指標（時間復雜度）能否了如指掌。
這一章，我們對重點的規納將跟以上各章不同。我們將從以下幾個側面來對排序一章進行不同的規納，以期能更全面的理解排序一章的總體結構及各種演算法。
從排序演算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸並、計數等五種排序方法。
其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序演算法的最根本的不同點，說到底就是根據什麼規則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數的總范圍「由小到大」的增量來實現排序效率提高的目的。
交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序。快速排序的思想，一語以敝之：用中間數將待排數據組一分為二。快速排序，在處理的「問題規模」這個概念上，與希爾有點相反，快速排序，是先處理一個較大規模，然後逐漸把處理的規模降低，最終達到排序的目的。
選擇排序，相對於前面幾種排序演算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據什麼規則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數；樹選擇，是通過「錦標賽」類似的思想，讓兩數相比，不斷淘汰較大（小）者，最終選出最小（大）數；而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。樹選擇排序，也曾經在一些學校中的大型演算法題中出現，請大家注意。
歸並排序，故名思義，是通過「歸並」這種操作完成排序的目的，既然是歸並就必須是兩者以上的數據集合才可能實現歸並。所以，在歸並排序中，關注最多的就是2路歸並。演算法思想比較簡單，有一點，要銘記在心：歸並排序是穩定排序。
基數排序，是一種很特別的排序方法，也正是由於它的特殊，所以，基數排序就比較適合於一些特別的場合，比如撲克牌排序問題等。基數排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數排序）。基數排序的核心思想也是利用「基數空間」這個概念將問題規模規范、變小，並且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。
本章各種排序演算法的思想以及偽代碼實現，及其時間復雜度都是必須掌握的，學習時要多注意規納、總結、對比。此外，對於教材中的10.7節，要求必須熟記，在理解的基礎上記憶，這一節幾乎成為很多學校每年的必考點。
至此，數據結構所有章節的章節重點問題，我們已經規納完畢，使用清華嚴版教材的同學，在復習的同時，可以參照本貼給出的重點進行復習。但是，由於作者本人水平有限，可能有很多考點沒有規納出來，也可能有些考點規納有誤，在此，作者本人誠懇希望諸位朋友直面提出，我會不斷完善和發布新的關於數據結構復習的總結以及筆記
嚴蔚敏數據結構為主的筆記二
第二章：線性表(包括習題與答案及要點)
--------------------------------------------------------------------------------
本章的重點是掌握順序表和單鏈表上實現的各種基本演算法及相關的時間性能分析，難點是使用本章所學的基本知識設計有效演算法解決與線性表相關的應用問題。
要求達到<識記>層次的內容有:線性表的邏輯結構特徵；線性表上定義的基本運算，並利用基本運算構造出較復雜的運算。
要求達到<綜合應用>層次的內容有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應用問題。
鏈表如何表示線性表中元素之間的邏輯關系；單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。循環鏈表上尾指針取代頭指針的作用，以及單循環鏈表上的演算法與單鏈表上相應演算法的異同點。雙鏈表的定義和相關演算法。利用鏈表設計演算法解決簡單應用問題。
要求達到<領會>層次的內容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優的時空性能。
--------------------------------------------------------------------------------
線性表的邏輯結構特徵是很容易理解的，如其名，它的邏輯結構特徵就好象是一條線，上面打了一個個結，很形象的，如果這條線上面有結，那麼它就是非空表，只能有一個開始結點，有且只能有一個終端結點，其它的結前後所相鄰的也只能是一個結點(直接前趨和直接後繼)。
關於線性表上定義的基本運算，主要有構造空表、求表長、取結點、查找、插入、刪除等。
--------------------------------------------------------------------------------
線性表的邏輯結構和存儲結構之間的關系。在計算機中，如何把線性表的結點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。
在順序表中實現的基本運算主要討論了插入和刪除兩種運算。相關的演算法我們通過練習掌握。對於順序表的插入和刪除運算，其平均時間復雜度均為O(n)。
--------------------------------------------------------------------------------
線性表的鏈式存儲結構。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結點，這組存儲單元可以分布在內存中任何位置上。因此，鏈表中結點的邏輯次序和物理次序不一定相同。所以為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其後繼結點的地址信息(即
10. 棧的共享存儲單元是什麼
有時，一個程序設計中，需要使用多個同一類型的棧，這時候，可能會產生一個棧空間過小，發生溢出，而另一個棧空間過大，造成大量存儲單元浪費的現象。為了充分利用各個棧的存儲空間，這時可以採用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現存儲空間優勢互補。
1.雙棧為兩個棧共同開辟一個存儲空間，讓一個棧的棧底為該空間的始端，另一棧的棧底為該空間的末端，當元素進棧時，都從兩端向中間「增長」，這樣能夠使剩餘的空間為任意一個棧所使用，即當一個棧的深度不足整個空間的一半時，另一個棧的深度可超過其一半，從而提高了存儲空間的利用率。可以使用一個數組同時存兩個棧，讓一個棧的棧底為數組的始端，另一個棧的棧底為數組的末端，每個棧從各自的端點向中間延伸，雙棧示意如圖1所示。其中，MAXSTACKSIZE為整個數組空間的長度，棧1的底端固定在下標為0的一端，棧2的底端固定在下標為MAXSTACKSIZE－1的一端。top1和top2分別為棧1和棧2的棧頂指針，並約定棧頂指針指向當前元素，即棧1空的條件是top1＝－1，棧1滿的條件是top1＝＝top2－1，棧2空的條件是top2＝MAXSTACKSIZE，棧2滿的條件是top2＝＝top1＋1。
圖1兩相棧共享存儲單元示意