第二章學習小結

第二章學習小結

? 對比于上學期所學的知識，能切實感覺到這個學期的課程更加深入和抽象，在學習上難度也有所增加，雖然上個學期就聽老師推薦過博客園，但是真正開始寫博客還是第一次，最直觀的感受就是在完成博客的過程中，能夠幫助我們梳理了一下知識點，算是復習了一遍

一、內容小結

　　1、線性表的定義：由n個數據特性相同的數據元素構成的有限序列，n=0時為空表

　　　　分為順序表和鏈表

　　2、優缺點

　　　　順序存儲：優點：隨機存取；缺點：插入、刪除擴容不方便

　　　　鏈式存儲：優點：方便插入、刪除、擴容；缺點按下標查詢效率低

　　3、數組在棧區為用戶開辟存儲位置，如果定義為全局變量，則在堆區（全局變量：在所有函數之外）

　　4、typedef把一個自己起的名字的類型用已經有的類型代替使用

　　　　用法：typedef 已有類型名 新名

　　5、bool類型

　　　　while（x）=>true

　　　　while （!x）=>false

　　6、申請大空間

　　　　int *a = new int[...]

?　　7、head指向的節點的成員

　　　　head->next=*head.next

　　　　LinkList L;與LNode *p含義是一樣的

　　8、數據結構分為邏輯結構和存儲結構

　　　　邏輯結構：抽象概念，獨立于計算機之外,包括線性結構和為線性結構

　　　　　　線性結構：線性表

　　　　　　非線性結構：樹結構、圖結構和集合結構

　　　　存儲結構：包括順序存儲結構和鏈式存儲結構

　　9、時間復雜度：執行算法所需的計算工作量

　　　　T（n)=O（f（n））

　　　　O（1）循環次數與n無關

　　　　O（n）一次循環

　　　　O（n^2）嵌套循環

　　10、空間復雜度：

　　　　（1）寄存本身所用的命令、常數、變量和輸入數據

　　　　（2）數據進行操作的輔助存儲空間

　　　　（3）算法在實現時所需要的輔助空間

二、作業的完成過程積累

　　1、求集合交集

#include <iostream>
#include <algorithm>	//包含sort函數
using namespace std;
int main()
{int m, n, i = 0, count = 0, k = 0, x = 0, y = 0;cin >> m >> n;int *a = new int[100000];	//創建三個數組，c用來裝交集int *b = new int[100000];int *c = new int[200000];for(i = 0; i < m; i++){	//循環輸入兩個集合的數cin >> a[i];}for(k = 0; k < n; k++){cin >> b[k];}sort(a ,a+m);	//對兩個數組排序，默認順序sort(b ,b+n);	while(x < m && y < n){	//逐個對比兩個數組的大小，小的往后一位if(a[x]==b[y]){	//相同 c[count]=a[x];count++;x++;y++;}else if(a[x] > b[y]){	//b數組后移一位 y++;	}else x++;}cout << count << endl;	//輸出相同的個數和元素 for(i = 0;i < count; i++){	cout<<c[i];if(i != count-1){	//最后一位不輸出空格 cout << " ";}}
}

　　

　　ps：這是代碼，一開始我沒有另外設x和y，直接用i和k，但是答案一直錯誤，后來發現，因為i在前面的的循環中已經被改變了，所以導致答案錯誤

　　2、sort函數的使用方法（開始地址，結束地址，compare），但是sort函數本身默認升序

三、學習問題

　　目前的學習中發現自己對于很多基礎知識的掌握還不夠牢固，且在思考問題上總是不能想到一個巧妙地解決方法

四、接下來的目標

　　多看一些題目，去思考怎么解題，多參考博客上優秀的代碼，思考過后自己再打一遍，熟悉書上的只是概念

?