在這里插入圖片描述

根據此書所做隨筆筆記，（持續更新中）

手機版目錄效果差：可根據鏈接跳轉各章節知識點：
第一章緒論知識點
第二章線性表知識點

電腦版目錄，跳轉各章節知識點：（也可以用側邊目錄跳轉）

文章目錄

一、緒論
1.1、資料結構的研究內容
1.2、基本概念和術語
1.2.1、資料、資料結構、資料項和資料物件
1.2.2資料結構
a、邏輯結構
b、存盤結構（物理結構）
(1)、順序存盤結構
(2)、鏈式存盤結構

1.2.3、資料型別和抽象資料型別
a、資料型別
b、抽象資料型別

1.3、抽象資料型別的表示與實作
1.4、演算法和演算法分析
1.4.1、演算法的定義及特性
1.4.2、評價演算法優劣的基本標準
1.4.3、演算法的時間復雜度
1.4.4、演算法的空間復雜度

第一章總結
第一章課后習題

二、線性表
2.1、線性表的定義和特點
2.2、案例引入
2.3、線性表的型別定義
2.4、線性表的順序表示和實作
2.4.1、線性表的順序表示
2.4.2、順序表中基本操作的實作

2.5、線性表的鏈式表示和實作
2.5.1、單鏈表的定義和表示
2.5.2、單鏈表基本操作的實作
2.5.3、回圈鏈表
2.5.4、雙向鏈表

2.6、順序表和鏈表的比較
2.7、線性表的應用
2.8、案例分析與實作
第二章小結
第二章習題

三、堆疊和佇列

一、緒論

1.1、資料結構的研究內容

用計算機解決實際問題時，步驟：首先分析實際問題，從中抽象出一個適當的數學模型，然后設計一個解決此數學模型的演算法，最后編程，除錯，測驗，

1.2、基本概念和術語

1.2.1、資料、資料結構、資料項和資料物件

在這里插入圖片描述

根據網上大佬的理解可能會更直觀一些：

假設有兩張表，A表為人員表，B表為課程表，表的格式如下：

姓名	性別	身高	課程代號
小明	男	180	A
小紅	女	180	A
小綠	男	180	B

課程代號	課程名
A	語文
B	數學

這兩張表就是資料
而單獨的一張表就稱為資料物件，即人員表是一個資料物件，課程表也是一個資料物件
而每張表中的每一行就稱為資料元素
而姓名，性別，身高，課程代號，課程名就稱為資料項

1.2.2資料結構

資料結構包括邏輯結構和存盤結構兩個層次，

a、邏輯結構

邏輯結構分為四種型別：集合結構，線性結構，樹形結構，圖形結構，

集合結構：資料元素同屬一個集合，單個資料元素之間沒有任何關系，
在這里插入圖片描述

線性結構類似于線性關系，也就是說，線性結構中的資料元素之間是一對一的關系，

在這里插入圖片描述

樹形結構：樹形結構中的資料元素之間存在一對多的關系，（各元素及元素關系所組成圖形類似于樹狀圖），

在這里插入圖片描述

圖形結構：資料元素之間是多對多的關系，如下圖所示，

在這里插入圖片描述

b、存盤結構（物理結構）

物理結構又叫存盤結構，分為兩種，一種是順序存盤結構一種是鏈式存盤結構，

(1)、順序存盤結構

順序存盤結構是把資料元素放到地址連續的存盤單元里面，其資料間的邏輯關系和物理關系是一致的，之前學習的陣列就是一種順序存盤結構，（如圖所示）

在這里插入圖片描述

(2)、鏈式存盤結構

鏈式存盤結構：是把資料元素存放在任意的存盤單元里面，這組存盤單元可以是連續的也可以是不連續的，

根據指標找出相鄰元素的位置
在這里插入圖片描述

1.2.3、資料型別和抽象資料型別

a、資料型別

一般包括整型、實型、字符型等原子型別外，還有陣列、結構體和指標等結構型別，

b、抽象資料型別

抽象資料型別（Abstract Data Type,ADT），類似C語言中的結構體以及C++、java語言中的類，

通俗的講，抽象資料型別，泛指除基本資料型別以外的資料型別，

1.3、抽象資料型別的表示與實作

抽象資料型別的概念與面向物件的思想是一致的，

1.4、演算法和演算法分析

演算法 + 資料結構 = 程式

1.4.1、演算法的定義及特性

演算法是為了解決某類問題而規定的一個有限長的操作序列，

一個演算法必須滿足以下五個重要特性： 有窮性、 確定性 、 可行性、輸入、輸出

1.4.2、評價演算法優劣的基本標準

正確性 、 可讀性 、 健壯性 、 高效性

1.4.3、演算法的時間復雜度

詳細可以看這個：一套圖搞懂“時間復雜度”

看下列代碼的時間復雜度：
在這里插入圖片描述

最好、最壞和平均時間復雜度

最好時間復雜度，指的是演算法計算量可能達到的最小值，
最壞時間復雜度，指的是演算法計算量可能達到的最大值，
平均時間復雜度，是指演算法在所有可能情況下，按照輸入實體以等概率出現時，演算法計算量的加權平均值，

1.4.4、演算法的空間復雜度

空間復雜度只需要分析輔助變數所占的額外空間，

空間復雜度：S(n) = O(f(n))

如果演算法執行所需要的臨時空間不隨著某個變數n的大小而變化，即此演算法空間復雜度為一個常量，可表示為 O(1)
舉例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代碼中的 i、j、m 所分配的空間都不隨著處理資料量變化，因此它的空間復雜度 S(n) = O(1)

我們再看一個代碼：

int[] m = new int[n]
for(i=1; i<=n; ++i){
   j = i;
   j++;
}

這段代碼中，第一行new了一個陣列出來，這個資料占用的大小為n，這段代碼的2-5行，雖然有回圈，但沒有再分配新的空間，因此，這段代碼的空間復雜度主要看第一行即可，即 S(n) = O(n)

第一章總結

在這里插入圖片描述

資料，資料物件和資料元素、資料項的關系如下

在這里插入圖片描述

資料結構是相互之間存在一種或者多種特定關系的資料元素的集合，同樣是結構，從不同角度來討論，會有不同的分類，如圖所示：

在這里插入圖片描述

演算法是為了解決某類問題而規定的一個有限長的操作序列，

演算法具有五個特性：有窮性、確定性、可行性、輸入和輸出，

一個演算法的優劣應該從以下四方面來評價：正確性、可讀性、健壯性和高效性，

演算法分析的重點方面是分析演算法的時間復雜度

第一章課后習題

1．簡述下列概念：資料、資料元素、資料項、資料物件、資料結構、邏輯結構、存盤結構、抽象資料型別，

資料：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程式處理的符號的總稱，

資料元素：是資料的基本單位，在計算機中通常作為一個整體進行考慮和處理，在有些情況下，資料元素也稱為元素、結點、記錄等，

資料項：是組成資料元素的、有獨立含義的、不可分割的最小單位，

資料物件：是性質相同的資料元素的集合，是資料的一個子集，

資料結構：是相互之間存在一種或多種特定關系的資料元素的集合，

邏輯結構：從邏輯關系上描述資料，它與資料的存盤無關，是獨立于計算機的，

存盤結構：資料物件在計算機中的存盤表示，也稱為物理結構，

抽象資料型別：由用戶定義的，表示應用問題的數學模型，以及定義在這個模型上的一組操作的總稱，具體包括三部分：資料物件、資料物件上關系的集合和對資料物件的基本操作的集合，

2．試舉一個資料結構的例子，敘述其邏輯結構和存盤結構兩方面的含義和相互關系，

例如有一張學生基本資訊表，包括學生的學號、姓名、性別、籍貫、專業等，每個學生基本資訊記錄
對應一個資料元素，學生記錄按順序號排列，形成了學生基本資訊記錄的線性序列，對于整個表來說，只有一個開始結點(它的前面無記錄)和一個終端結點(它的后面無記錄)，其他的結點則各有一個也只有一個直接前趨和直接后繼，學生記錄之間的這種關系就確定了學生表的邏輯結構，即線性結構，

這些學生記錄在計算機中的存盤表示就是存盤結構，如果用連續的存盤單元(如用陣串列示)來存放這些記錄，則稱為順序存盤結構；如果存盤單元不連續，而是隨機存放各個記錄，然后用指標進行鏈接，則稱為鏈式存盤結構，

即相同的邏輯結構，可以對應不同的存盤結構，

3．簡述邏輯結構的四種基本關系并畫出它們的關系圖，

（1）集合結構

資料元素之間除了“屬于同一集合”的關系外，別無其他關系，例如，確定一名學生是否為班級成員，只需將班級看做一個集合結構，

（2）線性結構

資料元素之間存在一對一的關系，例如，將學生資訊資料按照其入學報到的時間先后順序進行排列，將組成一個線性結構，

（3）樹結構

資料元素之間存在一對多的關系，例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構成樹形結構，

（4）圖結構或網狀結構

資料元素之間存在多對多的關系，例如，多位同學之間的朋友關系，任何兩位同學都可以是朋友，從而構成圖形結構或網狀結構，

其中樹結構和圖結構都屬于非線性結構，

4．存盤結構由哪兩種基本的存盤方法實作？

（1）順序存盤結構

順序存盤結構是借助元素在存盤器中的相對位置來表示資料元素之間的邏輯關系，通常借助程式設計語言的陣列型別來描述，

（2）鏈式存盤結構

順序存盤結構要求所有的元素依次存放在一片連續的存盤空間中，而鏈式存盤結構，無需占用一整塊存盤空間，但為了表示結點之間的關系，需要給每個結點附加指標欄位，用于存放后繼元素的存盤地址，所以鏈式存盤結構通常借助于程式設計語言的指標型別來描述，

5．選擇題

（1）在資料結構中，從邏輯上可以把資料結構分成（），

A．動態結構和靜態結構 B．緊湊結構和非緊湊結構

C．線性結構和非線性結構 D．內部結構和外部結構

答案：C

（2）與資料元素本身的形式、內容、相對位置、個數無關的是資料的（），

A．存盤結構 B．存盤實作

C．邏輯結構 D．運算實作

答案：C

（3）通常要求同一邏輯結構中的所有資料元素具有相同的特性，這意味著（），

A．資料具有同一特點

B．不僅資料元素所包含的資料項的個數要相同，而且對應資料項的型別要一致

C．每個資料元素都一樣

D．資料元素所包含的資料項的個數要相等

答案：B

（4）以下說法正確的是（），

A．資料元素是資料的最小單位

B．資料項是資料的基本單位

C．資料結構是帶有結構的各資料項的集合

D．一些表面上很不相同的資料可以有相同的邏輯結構

答案：D

解釋：資料元素是資料的基本單位，資料項是資料的最小單位，資料結構是帶有結構的各資料元素的集合，

（5）演算法的時間復雜度取決于（），

A．問題的規模 B．待處理資料的初態

C．計算機的配置 D．A和B

答案：D

解釋：演算法的時間復雜度不僅與問題的規模有關，還與問題的其他因素有關，如某些排序的演算法，其執行時間與待排序記錄的初始狀態有關，為此，有時會對演算法有最好、最壞以及平均時間復雜度的評價，

（6）以下資料結構中，（）是非線性資料結構

A．樹 B．字串 C．佇列 D．堆疊

答案：A

6．試分析下面各程式段的時間復雜度，

（1）

x=90; y=100; 

while(y>0){
    
if(x>100){
 	x=x-10;
     y--;
}

else x++;
}

答案：O(1)

解釋：程式的執行次數為常數階，

（2）

for (i=0; i<n; i++){
	for (j=0; j<m; j++){
		a[i][j]=0;
	}
}

答案：O(m*n)

解釋：陳述句a[i] [j]=0; 的執行次數為m*n，

3）

s=0;
for i=0; i<n; i++){
	for(j=0; j<n; j++){
         s+=B[i][j];
        sum=s;
	}
}

答案：O(n²)

解釋：陳述句 s+=B[i] [j]; 的執行次數為n²，

（4）

i=1;
while(i<=n){
 i=i*3;
}

答案：O(log₃n)

解釋：陳述句i=i*3;的執行次數為log₃n (有關對數公式：如果a^x = N,記做 x = log_aN)

設 i = i*3 執行了 x 次，則 3^x = n ；故 x = log₃n

（5）

x=0;
for(i=1; i<n; i++){
  for (j=1; j<=n-i; j++){
x++;
  }
}

答案：O(n²)

解釋：陳述句x++;的執行次數為 n-1+n-2+……＋1= n(n-1)/2，

i = 1 時，回圈執行 n-1 次

i = 2 時，回圈執行 n-2 次，

i = 3 時，回圈執行 n-3 次，

…

i = n-1 時，回圈執行 1 次

則相加： (n-1)+(n-2)+(n-3)+…+3+2+1 = n(n-1)/2

一共有 n-1 個式子，前后相加等于 n ，則總和為 n(n-1)/2

（6）

x=n; //n>1
y=0;

while(x≥(y+1)* (y+1)){
  y++;
}

答案：O( n \sqrt{n} n ?)

解釋： x≥(y+1)*(y+1) = n≥(y+1)²

開根號： n ≥ ( y + 1 ) \sqrt{n}≥(y+1) n ?≥(y+1)

n ? 1 ≥ y \sqrt{n}-1≥y n ??1≥y

則 y ≤ n ? 1 y≤\sqrt{n}-1 y≤n ??1

x=n; //n>1

y=0;

? while( y ≤ n ? 1 y≤\sqrt{n}-1 y≤n ??1){

? y++;
? }

y++;執行了 n \sqrt{n} n ? 次，則時間復雜度為：O( n \sqrt{n} n ?)

二、線性表

偽碼書上講的也很詳細，筆記中就不再打了，可以看后面的案例分析與實作中的完整代碼，

2.1、線性表的定義和特點

由n (n≥0)個資料特性相同的元素構成的有限序列稱為線性表，(n=0)的時候被稱為空表，

2.2、案例引入

略

2.3、線性表的型別定義

在這里插入圖片描述

2.4、線性表的順序表示和實作

2.4.1、線性表的順序表示

順序存盤表示：用一組地址連續的存盤單元依次存盤線性表的資料元素的方式

順序存盤特點：邏輯上相鄰的資料元素，其物理次序也是相鄰的

假設線性表的每個元素需占用n個存盤單元，并以所在的第一個單元的存盤地址作為資料元素的存盤起始位置

則LOC(ai+1)=LOC(ai)+n，LOC(ai)=LOC(a1)+(i-1)*n.

線性表的順序存盤結構是一種隨機存取的存盤結構，

//－－－－－ 順序表的存盤結構－－－－－
#define MAXSIZE 100 	   //順序表可能達到的最大長度
typedef struct 
    {
    ElemType *elem; 		 //存盤空間的基地址
    int length; 			 //當前長度
    }SqList;				//順序表的結構型別為SqList

2.4.2、順序表中基本操作的實作

一、順序表初始化
①、為順序表L動態分配一個預定義大小的陣列空間，使elem指向這段空間的基地址，
②、將表的當前長度設為0，

Status InitList(SqList &L) 
｛//構造一個空的順序表 L
    L.elem= new ElemType[MAXSIZE]; 	//為順序表分配一個大小為MAXSIZE的陣列空間
    if (!L. elem) exit(OVERFLOW); 	//存盤分配失敗退出
    L.length=O; 				  //空表長度為0
    return OK; 
}

二、順序表取值

①、判斷指定的位置序號 i 值是否合理 (1≤i≤L.length), 若不合理，則回傳ERROR，

②、若 i 值合理，則將第 i 個資料元素 L.elem[i-1] 賦給引數 e, 通過 e回傳第 i 個資料元素的傳值，

Status GetElem(SqList L,int i,ElemType &e) 
{
    if {i<1 || i>L.length) return ERROR;   //判斷l. 值是否合理，若不合理， 回傳 ERROR
    e=L.elem[i-1]; 						//elem[i-1] 單元存盤第 i 個資料元素
    return OK;
}

順序表取值演算法的時間復雜度為：O(1)

三、順序表的按值查找

①、從第一個元素起，依次和 e相比較，若找到與 e相等的元素 L.elem[i], 則查找成功，回傳該元素的序號 i+l (陣列下標從 0 開始)

②、若查遍整個順序表都沒有找到，則查找失敗，回傳0

int LocateELem(SqList L,ElemType e)
{//在順序表1中查找值為e的資料元素， 回傳其序號
for(i=O;i< L.length;i++){ 
	if(L.elem[i)==e){ 
              return i+l; 	       //查找成功， 回傳序號 i+l
		}
			return O; 			 //查找失敗， 回傳 0
	}
}

順序表按值查找演算法的平均時間復雜度為 O(n)

四、順序表插入元素

在第 i 個位置插入一個元素時，需從最后一個元素即第 n 個元素開始，依次向后移動一個位置，直至第 i 個元素，

在這里插入圖片描述
①、判斷插入位置l是否合法(i 值的合法范圍是 1≤i≤n+ I), 若不合法則回傳 ERROR，

②、判斷順序表的存盤空間是否已滿，若滿則回傳 ERROR，

③、將第n個至第 i 個位置的元素依次向后移動一個位置，空出第 i 個位置 ( i =n+l 時無需移動），

④、將要插入的新元素e放入第i個位置，

⑤、表長加1

Status Listinsert(SqList &L,int i ,ElemType e)
{
{//在順序表 L 中第 l. 個位置之前插入新的元素 e, i值的合法范圍是 1..;i..;L.length+l 
if((i<l) || (i>L.length+l)) return ERROR; 	   //i值不合法
if(L.length==MAXSIZE) return ERROR; 		  //當前存盤空間已滿
    for (j=L.length-1; j>=i-1; j--){
        L.elem[j+l]=L.elem[j];					 //插入位置及之后的元素后移
    }
L.elem[i-l]=e;								//將新元素e放入第l個位置
++L.length; 							    //表長加1
return OK;
}

順序表插入演算法的平均時間復雜度為O(n)

五、順序表洗掉元素

洗掉第 i 個元素時需將第 i+ 1 個至第 n 個元素依次向前移動一個位置 (i = n 時無需移動）

在這里插入圖片描述

①、判斷洗掉位置 i是否合法（合法值為 1 ≤ i ≤n), 若不合法則回傳 ERROR，

②、將第 i個至第n個的元素依次向前移動一個位置 (i = n時無需移動）

③、表長減 1

Status ListDelete(SqList &L,int i){ 
{//在順序表L中洗掉第J.個元素，J.值的合法范圍是 1.;;i.;;L. length 
if((i<l) 11 (i>L.length)) return ERROR; 	 //i值不合法
    for (j=i; j <=L. length-1; j ++){ 
    L.elem[j-1)=1.elem[j);					//被洗掉元素之后的元素前移
    }
--L.length; 							   //表長減 1
return OK;
}

順序表洗掉演算法的平均時間復雜度為 O(n)

2.5、線性表的鏈式表示和實作

鏈式存盤結構的特點：用一組任意的存盤單元存盤線性表的資料元素（這組存盤單元可以是連續的，也可以是不連續的），存放資料元素的結點至少包括兩個域（指標域、資料域），也可以包含若干個指標域和資料域，

2.5.1、單鏈表的定義和表示

在這里插入圖片描述

關于帶頭結點的單鏈表及不帶頭節點的單鏈表

帶頭結點：

在這里插入圖片描述

不帶頭結點：

在這里插入圖片描述

帶頭結點的單鏈表為空時：L->next==NULL；
不帶頭結點的單鏈表為空時：L=NULL;

//－－－－－ 單鏈表的存盤結構－－－－－
typedef struct LNode 
ElemType data;			//結點的資料域
struct LNode *next; 	//結點的指標域	
}LNode,*LinkList;		//LinkList 為指向結構體 LNode 的指標型別

2.5.2、單鏈表基本操作的實作

一、單鏈表的初始化

①、生成新結點作為頭結點，用頭指標L 指向頭結點，

②、頭結點的指標域置空，

Status InitList(LinkList &L) 
｛//構造一個空的單鏈表L
L=new LNode; 		//生成新結點作為頭結點，用頭指標L指向頭結點
L->next=NULL; 		//頭結點的指標域置空
return OK;
}

二、單鏈表的取值

①、用指標p指向首元結點，用 j 做計數器初值賦為1

②、從首元結點開始依次順著鏈域 next 向下訪問，只要指向當前結點的指標 p 不為空(NULL), 并且沒有到達序號為 i 的結點，則回圈執行以下操作：

p指向下一個結點；
計數器 j 相應加 1

③、退出回圈時，如果指標p為空，或者計數器 j 大于 i, 說明指定的序號 i 值不合法（i 大于表長n或 i 小于等于0), 取值失敗回傳ERROR; 否則取值成功，此時 j=i 時，p所指的結點就是要找的第 i 個結點，用引數 e 保存當前結點的資料域，回傳OK，

Status GetElem(LinkList L,int i,ElemType &e) 
{//在帶頭結點的單鏈表L中根據序號l.獲取元素的值，用e回傳L中第l.個資料元素的值
p=L->next;j=1; 			//初始化，p指向首元結點，計數器］初值賦為1
while(p&&j<i){ 			//順鏈域向后掃描，直到p為慷訓p指向第l.個元素
p=p->next;   			//p指向下一個結點
++j; 					//計數器j相應加1
}
    
if(!p || j>i)  return ERROR; 	// i值不合法 i>n或i≤0
e=p->data; 						//取第i個結點的資料域
return OK;
}

單鏈表取值演算法的平均時間復雜度為 O(n)

三、單鏈表的按值查找

①、用指標p指向首元結點

②、從首元結點開始依次順著鏈域next向下查找，只要指向當前結點的指標p不為空，并且p所指結點的資料域不等于給定值e, 則回圈執行以下操作： p指向下一個結點，

③、回傳p，若查找成功，p此時即為結點的地址值，若查找失敗，p的值即為NULL

LNode *LocateELem(LinkList L, Elemtype e) 
｛								//在帶頭結點的單鏈表L中查找值為e的元素
p=L->next; 						  //初始化，p指向首元結點
while(p && p->data!=e){ 			//順鏈域向后掃描，直到p為慷訓p所指結點的資料域等于e	
	p=p->next; 						//p指向下一個結點
}
return p; 							//查找成功回傳值為e的結點地址p, 查找失敗p為NULL
}

單鏈表的按值查找演算法的平均時間復雜度為 O(n)

四、單鏈表的插入

在這里插入圖片描述

①、查找結點 a_i-1 并由指標p指向該結點

②、生成一個新結點*s

③、將新結點*s 的資料域置為 e

④、將新結點*s 的指標域指向結點a_i

⑤、將結點 * p 的指標域指向新結點*s

Status Listinsert(LinkList &L,int i,ElemType e) 
{//在帶頭結點的單鏈表L中第i個位置插入值為e的新結點
p=L;j=O; 
while (p && (j<i-1)){
    p=p->next;++j;				  //查找第i-1個結點，p指向該結點
  } 			 
if (!p || j>i-1) return ERROR; 	   //i>n+1 或者 i≤1
    
s=new LNode; 					 //生成新結點 *s

s->data= e; 					 //將結點*s的資料域置為e

s->next=p->next;				 //將結點 *s的指標域指向結點 ai
    
p->next=s;						//將結點*p的指標域指向結點*s
    
return OK;
}

單鏈表插入演算法的時間復雜度為：O(n)

五、單鏈表的洗掉

在這里插入圖片描述

①、查找結點a_i-1 并由指標p指向該結點

②、臨時保存待洗掉結點a_i的地址在q中，以備釋放，

③、將結點*p的指標域指向a_i的直接后繼結點

④、釋放結點a_i的空間

Status ListDelete(LinkList &L,int i){
//在帶頭結點的單鏈表L中，洗掉第l個元素
    p=L;j=O;
    while ((p->next) && (j<i-1)){				//查找第i-1個結點，p指向該結點
			p=p->next; 
        	++j;
    }
    if (! (p->next) || (j>i-1)) return ERROR; 	 //當i＞n或i＜1時，洗掉位置不合理
    q=p->next;								  //臨時保存被刪結點的地址以備釋放
    p->next=q->next;						  //改變洗掉結點前驅結點的指標域
    delete q;								 //釋放洗掉結點的空間
    return OK;
}

單鏈表洗掉演算法的時間復雜度為： O(n)

六、創建單鏈表

前插法：始終讓新結點在第一的位置，不常用，因為輸入順序和輸出順序是相反的，

在這里插入圖片描述

后插法：尾指標r始終指向單鏈表的表尾，常用（輸入順序和輸出順序相同）

在這里插入圖片描述

①、創建一個只有頭結點的空鏈表，

②、尾指標r初始化，指向頭結點，

③、根據創建鏈表包括的元素個數n, 回圈n次執行以下操作

生成一個新結點*p;
輸入元素值賦給新結點*p 的資料域；
將新結點p 插入到尾結點r之后；
尾指標r指向新的尾結點*p

2.5.3、回圈鏈表

在這里插入圖片描述

2.5.4、雙向鏈表

在這里插入圖片描述

雙向鏈表的插入：
在這里插入圖片描述

雙向鏈表的洗掉：

2.6、順序表和鏈表的比較

在這里插入圖片描述

2.7、線性表的應用

略

2.8、案例分析與實作

線性表的順序實作案例：順序表案例
線性表的鏈式實作案例：單鏈表案例

第二章小結

在這里插入圖片描述

第二章習題

（1）順序表中第一個元素的存盤地址是100，每個元素的長度為2，則第5個元素的地址是（），

A．110 B．108 C．100 D．120

答案：B

解釋：順序表中的資料連續存盤，所以第5個元素的地址為：100+2*4=108

（2）在n個結點的順序表中，演算法的時間復雜度是O(1)的操作是（），

A．訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）

B．在第i個結點后插入一個新結點（1≤i≤n）

C．洗掉第i個結點（1≤i≤n）

D．將n個結點從小到大排序

答案：A

解釋：在順序表中插入一個結點的時間復雜度都是O(n²)，排序的時間復雜度為O(n²)或O(nlog₂n)，

順序表是一種隨機存取結構，訪問第 i 個結點和求第 i 個結點的直接前驅都可以直接通過陣列的下標直接定位，時間復雜度是O(1)

（3）向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數為（），

A．8 B．63.5 C．63 D．7

答案：B

解釋：順序表中插入元素，平均要移動的元素個數為：n/2

（4）鏈接存盤的存盤結構所占存盤空間（），

A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指標

B．只有一部分，存放結點值

C．只有一部分，存盤表示結點間關系的指標

D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數

答案：A

（5）線性表若采用鏈式存盤結構時，要求記憶體中可用存盤單元的地址（），

A．必須是連續的 B．部分地址必須是連續的

C．一定是不連續的 D．連續或不連續都可以

答案：D

（6）線性表Ｌ在（）情況下適用于使用鏈式結構實作，

A．需經常修改Ｌ中的結點值Ｂ．需不斷對Ｌ進行洗掉插入

C．Ｌ中含有大量的結點Ｄ．Ｌ中結點結構復雜

答案：B

解釋：鏈表最大的優點在于插入和洗掉時不需要移動資料，直接修改指標即可

（7）單鏈表的存盤密度（），

A．大于1 B．等于1 C．小于1 D．不能確定

答案：C

解釋：存盤密度是指一個結點資料本身所占的存盤空間和整個結點所占的存盤空間之比，假設單鏈表一個結點本身所占的空間為D，指標域所占的空間為N，則存盤密度為：D/(D+N)，一定小于1，

（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是（），

A．n B．2n-1 C．2n D．n-1

答案：A

解釋：當第一個有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次，

（9）在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（）個元素，

A．n-i B．n-i+1 C．n-i-1 D．I

答案：B

(10) 線性表L=(a1，a2,……an)，下列說法正確的是（），

A．每個元素都有一個直接前驅和一個直接后繼

B．線性表中至少有一個元素

C．表中諸元素的排列必須是由小到大或由大到小

D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼，

答案：D

第一個資料元素無直接前驅，最后一個資料元素無直接后繼

線性表定義中定義n = 0 時稱為線性表中的空表

元素可以隨機排列

(11) 創建一個包括n個結點的有序單鏈表的時間復雜度是（），

A．O(1) B．O(n) C．O(n²) D．O(nlog₂n)

答案：C

解釋：單鏈表創建的時間復雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結點時需要和已有的結點進行比較，確定合適的插入位置，所以時間復雜度是O(n²)，

(12) 以下說法錯誤的是（），

A．求表長、定位這兩種運算在采用順序存盤結構時實作的效率不比采用鏈式存盤結構時實作的效率低

B．順序存盤的線性表可以隨機存取

C．由于順序存盤要求連續的存盤區域，所以在存盤管理上不夠靈活

D．線性表的鏈式存盤結構優于順序存盤結構

答案：D

解釋：鏈式存盤結構和順序存盤結構各有優缺點，有不同的適用場合，

(13) 在單鏈表中，要將s所指結點插入到p所指結點之后，其陳述句應為（），

A．s->next=p+1; p->next=s;

B．(* p).next=s; (* s).next=(* p).next;

C．s->next=p->next; p->next=s->next;

D．s->next=p->next; p->next=s;

答案：D

(14) 在雙向鏈表存盤結構中，洗掉p所指的結點時須修改指標（），

A．p->next->prior=p->prior; p->prior->next=p->next;

B．p->next=p->next->next; p->next->prior=p;

C．p->prior->next=p; p->prior=p->prior->prior;

D．p->prior=p->next->next; p->next=p->prior->prior;

答案：A

(15) 在雙向回圈鏈表中，在p指標所指的結點后插入q所指向的新結點，其修改指標的操作是（），

A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

答案：C

三、堆疊和佇列

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/206548.html

標籤：其他

上一篇：在Android studio活動中寫入Button，為什么提示找不到位置

下一篇：計算機組成原理

資料結構C語言嚴蔚敏版(第二版)超詳細筆記附帶課后習題

文章目錄

一、緒論

1.1、資料結構的研究內容

1.2、基本概念和術語

1.2.1、資料、資料結構、資料項和資料物件

1.2.2資料結構

a、邏輯結構

b、存盤結構（物理結構）

(1)、順序存盤結構

(2)、鏈式存盤結構

1.2.3、資料型別和抽象資料型別

a、資料型別

b、抽象資料型別

1.3、抽象資料型別的表示與實作

1.4、演算法和演算法分析

1.4.1、演算法的定義及特性

1.4.2、評價演算法優劣的基本標準

1.4.3、演算法的時間復雜度

1.4.4、演算法的空間復雜度

第一章總結

第一章課后習題

二、線性表

2.1、線性表的定義和特點

2.2、案例引入

2.3、線性表的型別定義

2.4、線性表的順序表示和實作

2.4.1、線性表的順序表示

2.4.2、順序表中基本操作的實作

2.5、線性表的鏈式表示和實作

2.5.1、單鏈表的定義和表示

2.5.2、單鏈表基本操作的實作

2.5.3、回圈鏈表

2.5.4、雙向鏈表

2.6、順序表和鏈表的比較

2.7、線性表的應用

2.8、案例分析與實作

第二章小結

第二章習題

三、堆疊和佇列