數據結構課上筆記5

介紹了鏈表和基本操作

用一組物理位置任意的存儲單元來存放線性表的數據元素。 這組存儲單元既可以是連續的,也可以是不連續的,甚至是零散分布在內存中的任意位置上的。因此,鏈表中元素的邏輯次序和 物理次序不一定相同。

?

定義:

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)循環之前,有兩句代碼:

node_t* n=head;

head=NULL;

這兩行代碼的中:第一句的作用是用一個臨時變量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.所以說隊頭和隊尾都需要修改

?

?

鏈表刷了幾百道吧,好題還有很多,以后接著更新

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/445602.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/445602.shtml
英文地址,請注明出處:http://en.pswp.cn/news/445602.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

并查集入門三連:HDU1213 POJ1611 POJ2236

HDU1213 http://acm.hdu.edu.cn/showproblem.php?pid1213 問題描述 今天是伊格納修斯的生日。他邀請了很多朋友。現在是晚餐時間。伊格納修斯想知道他至少需要多少桌子。你必須注意到并非所有的朋友都互相認識,而且所有的朋友都不想和陌生人呆在一起。 這個問題…

Java設計模式(2 / 23):觀察者模式

定義 觀察者(Observer)模式定義了對象之間的一對多依賴,這樣一來,當一個對象改變狀態時,它的所有依賴者都會收到通知并自動更新。 OO設計原則:為了交互對象之間的松耦合設計而努力。 案例:氣…

二叉樹概述

各種實現和應用以后放鏈接 一、二叉樹的基本概念 二叉樹:二叉樹是每個節點最多有兩個子樹的樹結構。 根節點:一棵樹最上面的節點稱為根節點。 父節點、子節點:如果一個節點下面連接多個節點,那么該節點稱為父節點,它…

Java設計模式(1 / 23):策略模式

定義 策略(Strategy)模式定義了算法族,分別封裝起來,讓它們之間可以互相替換 ,此模式讓算法的變化獨立于使用算法的客戶。 案例:模擬鴨子應用 一開始 新需求:模擬程序需要會飛的鴨子 在父類新…

Java設計模式(3 / 23):裝飾者模式

文章目錄定義案例1:三點幾啦首次嘗試再次嘗試設計原則:類應該對擴展開放,對修改關閉嘗用裝飾者模式裝飾者模式特征本例的類圖放碼過來飲料類HouseBlendDarkRoastEspressoDecaf調料裝飾類MilkMochaSoyWhip運行測試類案例2:編寫自己…

c語言知識體系

原文:https://blog.csdn.net/lf_2016/article/details/80126296#comments

《游戲編程入門 4th》筆記(1 / 14):Windows初步

文章目錄Windows編程概述獲取Windows理解Windows消息機制多任務多線程事件處理DirectX快速概覽Direct3D是什么Window程序基礎創建第一個Win32項目理解WinMainWinMain函數調用完整的WinMainGetMessage函數調用尋求幫助Windows編程概述 DirectX,流行的游戲編程庫。它…

17校招真題題集(1)1-5

注:本系列題目全是按照通過率降序來排列的,基本保證題目難度遞增。 1、 題目名稱:游戲任務標記 來源:騰訊 題目描述 游戲里面有很多各式各樣的任務,其中有一種任務玩家只能做一次,這類任務一共有1024個…

《游戲編程入門 4th》筆記(2 / 14):監聽Windows消息

文章目錄編寫一個Windows程序理解InitInstanceInitInstance函數調用InitInstance的結構理解MyRegisterClassMyRegisterClass函數調用MyRegisterClass的作用揭露WinProc的秘密WinProc函數調用WinProc的大秘密什么是游戲循環The Old WinMain對持續性的需要實時終止器WinMain和循環…

17校招真題題集(2)6-10

注:本系列題目全是按照通過率降序來排列的,基本保證題目難度遞增。 6、 題目名稱:Fibonacci數列 來源:網易 題目描述 Fibonacci數列是這樣定義的: F[0] 0 F[1] 1 for each i ≥ 2: F[i] F[i-1] F[i-2] 因此&am…

QT5的數據庫

#include <QtSql> QT sql QSqlDatabase類實現了數據庫連接的操作 QSqlQuery類執行SQL語句 QSqlRecord類封裝數據庫所有記錄 QSqlDatabase類 [cpp] view plaincopy print?QSqlDatabase db QSqlDatabase::addDatabase("QOCI"); db.setHostName("localh…

數據結構課上筆記6

本節課介紹了單鏈表的操作實現細節&#xff0c;介紹了靜態鏈表。 鏈表帶頭的作用&#xff1a;對鏈表進行操作時&#xff0c;可以對空表、非空表的情況以及 對首元結點進行統一處理&#xff0c;編程更方便。 下面給出帶頭的單鏈表實現思路&#xff1a; 按下標查找&#xff1a; …

《Unity2018入門與實戰》筆記(9 / 9):個人總結

個人總結 腳本語言學習的竅門 盡可能多讀、多寫、多說腳本語言&#xff01; Link 游戲制作步驟 設計游戲時一般會遵循5個步驟&#xff1a; 羅列出畫面上所有的對象。確定游戲對象運行需要哪些控制器腳本。確定自動生成游戲對象需要哪些生成器腳本。準備好用于更新UI的調度…

17校招真題題集(3)11-15

注&#xff1a;本系列題目全是按照通過率降序來排列的&#xff0c;基本保證題目難度遞增。 11、 題目名稱&#xff1a;買蘋果 來源&#xff1a;網易 題目描述 小易去附近的商店買蘋果&#xff0c;奸詐的商販使用了捆綁交易&#xff0c;只提供6個每袋和8個每袋的包裝(包裝不…

Qt學習:QDomDocument

QDomDocument類代表了一個XML文件 QDomDocument類代表整個的XML文件。概念上講&#xff1a;它是文檔樹的根節點&#xff0c;并提供了文檔數據的基本訪問方法。由于元素、文本節點、注釋、指令執行等等不可能脫離一個文檔的上下文&#xff0c;所以文檔類也包含了需要用來創建這些…

《事實:用數據思考,避免情緒化決策》筆記

文章目錄一分為二負面思維直線思維恐懼本能規模錯覺以偏概全命中注定單一視角歸咎他人情急生亂一分為二 要做到實事求是&#xff0c; 就要做到當你聽到一分為二的說法時&#xff0c; 你就能迅速認識到這種說法描述的是一種兩極分化的圖畫&#xff0c; 而兩極之間存在一道巨大的…

順序存儲線性表實現

在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素,稱作線性表的順序存儲結構。 順序存儲結構的主要優點是節省存儲空間&#xff0c;因為分配給數據的存儲單元全用存放結點的數據&#xff08;不考慮c/c語言中數組需指定大小的情況&#xff09;&#xff0c;結點之…

QT5生成.exe文件時,出現缺少QT5core.dll文件解決方法

在 http://qt-project.org/downloads 下載Qt SDK安裝需要Qt版本。在QtCreator下&#xff0c;程序可以正常運行&#xff0c;但是當關閉QtCreator后&#xff0c;在DeBug目錄下再運行相應的*.exe程序時&#xff0c;會提示缺少Qt5Core.dll錯誤。解決方法&#xff1a;添加電腦環境變…

《基于Java實現的遺傳算法》筆記(7 / 7):個人總結

文章目錄為何采用遺傳算法哪些問題適合用遺傳算法解決遺傳算法基本術語一般遺傳算法的過程基本遺傳算法的偽代碼為何采用遺傳算法 遺傳算法是機器學習的子集。在實踐中&#xff0c;遺傳算法通常不是用來解決單一的、特定問題的最好算法。對任何一個問題&#xff0c;幾乎總有更…

單鏈表不帶頭標準c語言實現

鏈表是一種物理存儲單元上非連續、非順序的存儲結構&#xff0c;數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點&#xff08;鏈表中每一個元素稱為結點&#xff09;組成&#xff0c;結點可以在運行時動態生成。每個結點包括兩個部分&#xff1a;一個是…