數(shù)據(jù)結(jié)構(gòu)——基礎(chǔ)7
鏈表
練習(xí)題：已知一個(gè)帶有表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L， 結(jié)點(diǎn)結(jié)構(gòu)為prev?data?next， 其中prev和
next分別是指向其直接前驅(qū)和直接后繼結(jié)點(diǎn)的指針。 現(xiàn)要刪除指針p所指的結(jié)點(diǎn)， 正
確的語句序列是（ ）
A p->next->prev = p->prev; p->prev->next = p->prev; free(p);
B p->next->prev = p->next; p->prev->next = p->next; free(p);
C p->next->prev = p->next; p->prev->next = p->prev; free(p);
D p->next->prev = p->prev; p->prev->next = p->next; free(p);
答：D
答：原始鏈表——c->a->e->b->d
????插入后——c->a->f->e->b->d
????選D
已知頭指針h指向一個(gè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表， 結(jié)點(diǎn)結(jié)構(gòu)為 data next， 其
中next是指向直接后繼結(jié)點(diǎn)的指針， p是尾指針， q是臨時(shí)指針。 現(xiàn)要刪除該鏈
表的第一個(gè)元素， 正確的語句序列是（ ）
A h->next = h->next->next; q = h->next; free(q);
B q = h->next; h->next = h->next->next; free(q);
C q = h->next; h->next = q->next; if(p != q) p=h; free(q);
D q = h->next; h->next = q->next; if(p == q) p=h; free(q);
答：D
設(shè)線性表L=(a1,a2,a3,…,an-2,an-1,an)采用帶頭結(jié)點(diǎn)的單鏈表保存， 鏈表中的結(jié)點(diǎn)定義如下：
typedef struct node{
????int data;
????struct node *next;
}NODE;
請?jiān)O(shè)計(jì)一個(gè)空間復(fù)雜度為O(1)且時(shí)間上盡可能高效的算法， 重新排列L中的各結(jié)點(diǎn)， 得到線性表L'=(a1,an,a2,an-1,a3,an-2,…)。 要求：
1） 給出算法的基本設(shè)計(jì)思想。
2） 根據(jù)設(shè)計(jì)思想， 采用C或C++語言描述算法， 關(guān)鍵之處給出注釋。
3） 說明你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。
答：1)
找到中間結(jié)點(diǎn)——>后半段逆置——>向前插入
2）
NODE *change(NODE *L){
????NODE *p,*q,*r,*s;//q插入結(jié)點(diǎn)，s指向被插入點(diǎn)，r臨時(shí)指向未插入結(jié)點(diǎn)頭部
????//步驟一：中間結(jié)點(diǎn)
????p = q =L;
????while(q->next == NULL){//p指向下一個(gè)，q下一個(gè)指向不為空指向下下一個(gè)
????????p = p->next;
????????q = q->next;
????????if(q->next == NULL) q = q->next;?
????}
????//步驟二：后半段逆置
????q = p->next;
????p->next = NULL:
????while(q){
????????r = q->next;
????????q->next = p->next;
????????p->next = q;
????????q = r;
????}
????//步驟三：向前插入
????s = L->next;
????q = p->next;
????p->next = NULL;//當(dāng)前是中間結(jié)點(diǎn)，算法結(jié)束之后是尾結(jié)點(diǎn)
????while(q){
????????r = q->next;
????????q->next = s->next;
????????s->next = q;
????????s = q->next;
????????q = r;
????}
????return L;
}
3）時(shí)間復(fù)雜度O（n）
?！薅ㄖ荒茉谝欢诉M(jìn)行插入和刪除的線性表
插入：進(jìn)棧，壓棧，入棧，push
刪除：出棧，彈棧，退棧，pop
棧的特點(diǎn)：棧的元素先進(jìn)后出
例題：
解：
A先出d則abcd依次入棧，順序?yàn)閐、c出棧，e入棧、出棧，b出棧，f入棧、出棧，a出棧；
B先出a則a入棧、出棧，bcd依次入棧，d、c、b出棧，故選B
C先出c則abc依次入棧，順序?yàn)閏、b出棧，d入棧、出棧，a出棧，e入棧、出棧，f入棧、出棧；
D先出b則ab依次入棧，順序?yàn)閎出棧，c入棧、出棧，a出棧，d入棧，e入棧、出棧，f入棧、出棧，d出棧。
解：abcd先入棧，d、b、c、a之間和末尾位置，e可以入棧、出棧，故選B
解：棧S1、S2如下所示：
第一次調(diào)用函數(shù)F()，
1）S1的2、3出棧，則a=2、b=3? ? ? ? ? 2）S2的+出棧? ? ? ? 3）3+2=5?? ? ? 4）5入棧S1中
如下所示：
第二次調(diào)用函數(shù)F()，
1）S1的5、8出棧，則a=5、b=8? ? ??????2）S2的-出棧??? ? ? 3）8-5=3? ? ? ?4）3入棧S1中
第三次調(diào)用函數(shù)F()，
1）S1的3、5出棧，則a=3、b=5? ? ??????2）S2的*出棧??? ? ? 3）5+3=15? ? 4）15入棧S1中
故選B
解：過，選D
隊(duì)列
環(huán)形隊(duì)列
雙端隊(duì)列
例題：
解：rear指向隊(duì)尾元素，不是隊(duì)尾元素的下一個(gè)位置，故選B
解：
第一軌道：列車次序8、9??
第二軌道：列車次序4、5、6、7?
第三軌道：列車次序2、3??
第四軌道：列車次序1
故選C
