資料結構

1. 資料結構概念
- 1.1 資料結構相關概念
- - 1.1.1 為什麼要學習資料結構？
  - 1.1.2 資料結構中的基本概念
- 1.2 算法
- - 1.2.1 算法的概念
  - 1.2.2 算法和資料結構差別
  - 1.2.3 算法特性
  - 1.2.4算法效率的度量
  - - 1.2.4.1 事後統計法
    - 1.2.4.2 事前分析估算
    - 1.2.4.3 大O表示法
2. 線性表
- 2.1 線性表基本概念
- - 2.1.1 基本概念
  - 2.1.2 性質
  - 2.1.3 線性表的操作
- 2.2 線性表的順序存儲
- - 2.2.1 線性表順序存儲基本概念
  - 2.2.2 線性表順序存儲的設計與實作
3. 受限線性表
4. 樹和二叉樹
5. 排序
6. C++模闆類與資料結構基礎

1. 資料結構概念

1.1 資料結構相關概念

1.1.1 為什麼要學習資料結構？

為什麼要學習資料結構？在回答這個問題之前，我們應該弄清楚什麼是資料結構，資料結構能夠用來幹什麼？直白的，它能夠幫我們解決什麼問題？

資料結構是思想層面的，與具體的語言無關，可以用其他的語言去實作這些思想都沒有問題

舉個例子：

比如我們C語言中沒有數組這個資料結構，那麼如何實作10個數排序，是不是要定義10個變量，然後讓10個變量互相比較，重複勞動，但是使用數組之後，是不是問題變得簡單了，隻需要通過數組下表就可以，提高了程式設計的編寫效率

再比如說，我們有了數組，為什麼還要學習連結清單這種資料結構？數組是連續記憶體空間，一旦定義了不能改變，适應性差，但是連結清單有多少資料，就建立多少個結點，而且比如說資料，删除中間位置一個元素，會引起後面資料的移動，但是連結清單不會，在有些場合下，使用連結清單是不是會增加程式的效率

可以得出資料結構的概念：資料結構就是幫我們解決如何組織和存儲資料的方式

資料結構主要研究非數值計算問題的程式中的操作對象以及他們之間的關系，不是研究複雜的算法

資料結構是計算機存儲、組織資料的方式

1.1.2 資料結構中的基本概念

資料：程式的操作對象

資料是一個抽象的概念，将其進行分類後得到的程式設計語言中的類型。如：int, float, char等等

資料元素：組成資料的基本機關

資料項：一個資料元素由若幹個資料項組成

資料對象：性質相同的資料元素的集合（比如：數組、連結清單）

//聲明一個結構體類型
struct _MyTeacher	//一種資料類型
{
	char name[32];
	char tile[32];
	int age;
	char addr[128];
};

int main()
{
	struct _MyTeacher t1;	//資料元素
	struct _MyTeacher tArray[30];	//資料對象
	memset (&t1, 0, sizeof(t1));
	strcpy(t1.name, "name")l	//資料項
	strcpy(t1.addr, "addr")l	//資料項
	strcpy(t1.tile, "tile")l	//資料項
	ti.age = 1;
}

1.2 算法

1.2.1 算法的概念

算法是特定問題求解步驟的描述，在計算機中表現為指令的有限序列，算法是獨立存在的一種解決問題的方法和思想

對于算法而言，語言不重要，重要的是思想

1.2.2 算法和資料結構差別

資料結構隻是靜态的描述了資料元素之間的關系，高效的程式需要在資料結構的基礎上設計和選擇算法

·算法是為了解決實際問題而設計的

·資料結構是算法需要處理的問題載體

·資料結構與算法相輔相成

1.2.3 算法特性

輸入：算法具有0個或多個輸入

輸出：算法至少有1個或多個輸出

有窮性：算法在有限的步驟之後會自動結束而不會無限循環，并且每一個步驟可以在接受的實際内完成

确定性：算法中的每一步都有确定的含義，不會出現二義性

可行性：算法的每一步都是可行的，也就說每一部都能夠執行有限的次數完成

問題：針對某一具體的問題，解決此類問題的算法是唯一的嘛？

比如說：求從1到100的和？

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//算法1
long sum1(int n)
{
	long ret = 0;
	int* array = (int*)malloc(n * sizeof(int));
	int i = 0;
	for (int i = 0; i < n; i++)
	{
		array[i] = i + 1;
	}
	for (int i = 0; i < n; i++)
	{
		ret += array[i];
	}
	free(array);
	return ret;
}
//算法2
long sum2(int n)
{
	long ret = 0;
	int i = 0;
	for (int i = 0; i < n + 1; i++)
	{
		ret += i;
	}
	return ret;
}
//算法3
long sum3(int n)
{
	long ret = 0;
	if (n > 0)
	{
		ret = (1 + n) * n / 2;
	}
	return ret;
}
int main()
{
	printf("%d\n", sum1(100));
	printf("%d\n", sum2(100));
	printf("%d\n", sum3(100));
	system("pause");
	return EXIT_SUCCESS;
}

同樣一個問題，有三種不同的算法，這三種算法都可以解決同樣的問題，那麼我們如何選擇？需要有個方法來衡量算法的效率？

1.2.4算法效率的度量

1.2.4.1 事後統計法

主要通過設計好的測試程式和資料，利用計算機的計時器對不同算法的編制的程式的運作時間進行比較，進而确定算法效率的高低

統計方法：

比較不同算法對同一組輸入資料的運作處理時間

缺陷：

為了獲得不同算法的運作時間必須編寫相應程式；

運作時間嚴重依賴硬體以及運作時的環境因素；

算法的測試資料的選取相當困難

總結：

事後統計法雖然直覺，但是實施困難且缺陷多

1.2.4.2 事前分析估算

在計算機程式編制前，依據統計方法對算法進行估算

統計方法：

依據統計的方法對算法效率進行估算

影響算法效率的主要因素：

算法采用的政策和方法；

問題的輸入規模；

編譯器所産生的代碼；

計算機執行速度

算法推導的理論基礎：

算法最終編譯成具體的計算機指令

每一個指令，在具體的計算機上運作速度固定

通過具體的步驟，就可以推導出算法的複雜度

怎麼判斷一個算法的效率？

判斷一個算法的效率時，往往隻需要關注操作數量的最高次項，其它次項和常數項可以忽略
在沒有特殊說明時，我們所分析的算法的時間複雜度都是指最壞時間複雜度
隻有常數項記作1
操作數量的估算可以作為時間複雜度的估算

1.2.4.3 大O表示法

總結：

隻需要最高次項
常數項記為1
操作數量的估算可以作為時間複雜度的估算

2. 線性表

2.1 線性表基本概念

2.1.1 基本概念

線性表是零個或多個資料元素的有限序列

特性：

資料元素之間是有順序的
資料元素個數是有限的
資料元素的類型必須相同

數學定義：線性表是具有相同類型的n（≥0）個資料元素的優先序列（a0, a1, a2, …, an）ai是表項，n是表長度

2.1.2 性質

a0為線性表的第一個元素，隻有一個後繼
an為線性表的最後一個元素，隻有一個前驅
除a0和an外的其他元素ai，既有前驅，又有後繼
線性表能夠逐項通路和順序存取

2.1.3 線性表的操作

· 建立線性表

· 銷毀線性表

· 清空線性表

· 将元素插入線性表

· 将元素從線性表中删除

· 擷取線性表中某個位置的元素

· 擷取線性表的長度

線性表的抽象資料類型定義：

ADT線性表(List)
Data
	線性表的資料對象集合為{a1, a2, … , an}，每個元素的類型均為DataType。其中，除第一個元素a1外，每個元素有且隻有一個直接前驅元素，除最後一個元素an外，每個元素有且隻有一個直接後繼元素。資料元素之間的關系是一一對應的。
Operation（操作）
//初始化，建立一個空的線性表L
InitList(*L);
//若線性表為空，傳回true，否則傳回false
ListEmpty(L);
//将線性表清空
ClearList(*L);
//将線性表L中的第i個位置的元素傳回給e
GetElem(L, i, e);
//線上性表L中第i個位置插入新元素e
ListInsert(*L, i, e);
//删除線性表L中的第i個位置元素，并用e傳回其值
ListDelete(*L, i, *e);
//傳回線性表L的元素個數
ListLength(L);
//銷毀線性表
DestroyList(*L);

2.2 線性表的順序存儲

2.2.1 線性表順序存儲基本概念

線性表的順序存儲結構，指的是用一段位址連續的存儲單元一次存儲線性表的資料元素

線性表（a1，a2，……，an）的順序存儲示意圖如下：

資料結構（筆記）1. 資料結構概念2. 線性表3. 受限線性表4. 樹和二叉樹5. 排序6. C++模闆類與資料結構基礎