介紹了鏈表和基本操作
用一組物理位置任意的存儲單元來存放線性表的數據元素。 這組存儲單元既可以是連續的,也可以是不連續的,甚至是零散分布在內存中的任意位置上的。因此,鏈表中元素的邏輯次序和 物理次序不一定相同。
?
定義:
typedef struct Lnode{ //聲明結點的類型和指向結點的指針類型 ElemType data; //數據元素的類型 struct Lnode *next; //指示結點地址的指針
}Lnode, *LinkList;
struct Student
{ char num[8]; //數據域char name[8]; //數據域int score; //數據域struct Student *next; // next 既是 struct Student // 類型中的一個成員,又指 // 向 struct Student 類型的數據。
}Stu_1, Stu_2, Stu_3, *LL;
頭結點:在單鏈表的第一個結點之前人為地附設的一個結點。
帶頭結點操作會方便很多。
帶和不帶的我都寫過了
下面列出我見過的一些好題
1、
線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類型。
-
正確
-
錯誤
?
錯,線性表是邏輯結構概念,可以順序存儲或鏈式儲,與元素數據類型無關。鏈表就是線性表的一種 ?前后矛盾
?
2、
若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素,則采用( ???)存儲方式最節省運算時間。
-
單鏈表
-
僅有頭指針的單循環鏈表
-
雙鏈表
-
僅有尾指針的單循環鏈表
對于A,B,C要想在尾端插入結點,需要遍歷整個鏈表。
對于D,要插入結點,只要改變一下指針即可,要刪除頭結點,只要刪除指針.next的元素即可。
?
3、注意:線性表是具有n個數據元素的有限序列,而不是數據項
?
4、
以下關于單向鏈表說法正確的是
-
如果兩個單向鏈表相交,那他們的尾結點一定相同
-
快慢指針是判斷一個單向鏈表有沒有環的一種方法
-
有環的單向鏈表跟無環的單向鏈表不可能相交
-
如果兩個單向鏈表相交,那這兩個鏈表都一定不存在環
自己多畫畫想想就明白了,關于快慢指針我以后會寫總結。
?
5、
鏈接線性表是順序存取的線性表?。?(?)
-
正確
-
錯誤
鏈接線性表可以理解為鏈表
線性表分為順序表和鏈表
順序表是順序存儲結構、隨機存取結構
鏈表是隨機存儲結構、順序存取結構
?
6、
typedef struct node_s{int item;struct node_s* next;
}node_t;
node_t* reverse_list(node_t* head)
{node_t* n=head;head=NULL;while(n){_________ }return head;}
空白處填入以下哪項能實現該函數的功能?
-
node_t* m=head; head=n; head->next=m; n=n->next;
-
node_t* m=n; n=n->next; m->next=head; head=m;
-
node_t* m=n->next; n->next=head; n=m; head=n;
-
head=n->next; head->next=n; n=n->next;
?
代碼的功能是要實現鏈表的反轉。為了方便闡述,每個結點用①②③④⑤⑥等來標示。
在執行while(n)循環之前,有兩句代碼:
|
這兩行代碼的中:第一句的作用是用一個臨時變量n來保存結點①,第二句是把head修改為NULL。
然后就開始遍歷了,我們看到while循環里的那四句代碼:
node_t* m=n;
n=n->next;
m->next=head;
head=m;
先看前兩句,用m來保存n,然后讓n指向n的下一個結點,之所以復制 n 給 m ,是因為 n 的作用其實是? 控制while循環次數? 的作用,每循環一次它就要被修改為指向下一個結點。
再看后兩句,變量head在這里像是一個臨時變量,后兩句讓 m 指向了 head,然后 head 等于 m。
?
7、
若某表最常用的操作是在最后一個結點之后插入一個節點或刪除最后一二個結點,則采用()省運算時間。
-
單鏈表
-
雙鏈表
-
單循環鏈表
-
帶頭結點的雙循環鏈表
D
帶頭結點的雙向循環鏈表,頭結點的前驅即可找到最后一個結點,可以快速插入,再向前可以找到最后一二個結點快速刪除
單鏈表找到鏈表尾部需要掃描整個鏈表
雙鏈表找到鏈表尾部也需要掃描整個鏈表
單循環鏈表只有單向指針,找到鏈表尾部也需要掃描整個鏈表
?
8、
單鏈表的存儲密度( ?)
-
大于1
-
等于1
-
小于1
-
不能確定
全麥白
存儲密度 = 數據項所占空間 / 結點所占空間
?
9、完成在雙循環鏈表結點p之后插入s的操作是
-
s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;
?
10、用不帶頭結點的單鏈表存儲隊列,其隊頭指針指向隊頭結點,隊尾指針指向隊尾結點,則在進行出隊操作時()
-
僅修改隊頭指針
-
僅修改隊尾指針
-
隊頭、隊尾指針都可能要修改
-
隊頭、隊尾指針都要修改
?
當只有一個元素,出隊列時,要將隊頭和隊尾,指向-1.所以說隊頭和隊尾都需要修改
?
?
鏈表刷了幾百道吧,好題還有很多,以后接著更新