TZ:我們恐懼的往往不是黑暗,而是光明
一 : 科普一分鐘
什么是數(shù)據(jù)結(jié)構(gòu)和算法,二者有和聯(lián)系呢.
其實(shí)一種是數(shù)據(jù)存儲的方式,一種是一種實(shí)現(xiàn)功能的手段.
我最近經(jīng)常做飯,打個比方,就好比做菜一樣,我們所用的食材就是數(shù)據(jù)結(jié)構(gòu),我們做同樣的菜,食材有新鮮的有不新鮮的,肉質(zhì)有老的有嫩的,同樣算法好比廚師的廚藝,有高手和菜鳥,兩者的配合會產(chǎn)生各種奇妙的結(jié)果,所以算法和數(shù)據(jù)結(jié)構(gòu) 是程序的重要組成部分.
二 : 數(shù)據(jù)結(jié)構(gòu)簡述和舉例
1. 概述:何為數(shù)據(jù)結(jié)構(gòu)?
數(shù)據(jù)結(jié)構(gòu)其實(shí)就是計(jì)算機(jī)存儲,組織數(shù)據(jù)的方式.
相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素的集合
2. 常見的數(shù)據(jù)結(jié)構(gòu)有哪些?
大家都學(xué)過數(shù)據(jù)結(jié)構(gòu)這門課程,接下來我們來復(fù)習(xí)一下,我們都學(xué)過哪些數(shù)據(jù)結(jié)構(gòu).
(1) 線性表
包括我們常用的數(shù)組,鏈表,棧,和隊(duì)列.
(2)樹
(3)圖
3.常見的邏輯結(jié)構(gòu)
什么是邏輯結(jié)構(gòu)?個人理解就是有點(diǎn)"紙上談兵"的意思,類似于草圖或者說是思路結(jié)構(gòu)
(1)集合結(jié)構(gòu) : 把雜亂的數(shù)據(jù)放進(jìn)一個大鍋里.
(2)線性結(jié)構(gòu) : 內(nèi)存是連續(xù)的,類似于"鐵索連環(huán)"
(3)樹形結(jié)構(gòu) : 這個結(jié)構(gòu)的特點(diǎn)就是....暫時理解像一顆樹就好了
(4)圖形結(jié)構(gòu) : 這個結(jié)構(gòu)特點(diǎn)內(nèi)存可以是連續(xù)的 也可以是不連續(xù)的
4.存儲結(jié)構(gòu)
說完了邏輯結(jié)構(gòu),我們說說存儲結(jié)構(gòu),
(1) 順序存儲結(jié)構(gòu)
(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)
- 隊(duì)列
假如此時我們做一個解密算法
把一個數(shù)據(jù)串 第一個數(shù)扔掉,第二個數(shù)放到尾部,第三個數(shù)扔掉,第四個數(shù)放到尾部.....等等, 刪掉的數(shù)按照移除順序就是我們要的結(jié)果 如何實(shí)現(xiàn)呢?
這其實(shí)就是隊(duì)列 ,隊(duì)列是先進(jìn)先出的,就好像我們排隊(duì)買票,先站排的人最先買到票,最先離開,好像兩頭開口的一個通道.
我們用head 來標(biāo)注 隊(duì)列頭 用tail 來標(biāo)注隊(duì)列尾部
注意 這里說的隊(duì)尾 是值 尾部后+ 1 的位置
#include <stdio.h>
int main()
{
int q[102] = {0,6,3,1,7,5,8,2,9,4},head,tail;
//初始化隊(duì)列
head = 1;
tail = 10;
while(head < tail){
//打印隊(duì)首
printf("%d",q[head]);
//出隊(duì)
head ++
//將新隊(duì)首數(shù)添加到隊(duì)尾
q[tail] = q[head];
tail++;
//再次隊(duì)首移除出隊(duì)
head++
}
return 0;
}
6.棧
簡單的說一下棧,我們吃的薯片或者彈夾,都類似棧,先進(jìn)后出.
現(xiàn)在我們做個簡單的小例子簡單分析一下
做一個判斷一個串 是否是回文
什么是回文, AABB ,ABBA ,ABCBA這種對稱的叫回文
我們用一個指向棧頂?shù)淖兞縯op
#include<stdio.h>
#include<string.h>
char a[101],s[101];
int i,len,mid,next,top;
gets(a)//讀入一個串
len = strlen(a);
mid = len/2 - 1;
top = 0;
//mid前面數(shù)一次入棧
for(i = 0; i <= mid ;i++){
s[++top] = a[i];
}
//判斷奇偶性
if(len%2 == 0)
next = mid + 1;
else
next = mid + 2;
//匹配
for(i = mext ; i<len-1;i++){
if(a[i] != s[stop])
breal;
top -- ;
}
if(top == 0){
printf("是回文");
}else{
printf("不是回文");
}
return 0;
- 鏈表
每一個鏈表的節(jié)點(diǎn)有兩個部分組成,左邊的部分存放的是具體的數(shù)值,右邊存放的是下一個節(jié)點(diǎn)的地址.我們可以用一個結(jié)構(gòu)體來描述它
struct node{
int data;
struct node *next;
}
現(xiàn)在實(shí)現(xiàn) 插入某個數(shù)到序列里,簡單來說就是拆鏈和補(bǔ)鏈的過程.
#include <sdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
int main(){
struct node *head,*p,*q,*t;
int i,n,a;
scanf("%d",&n);
head = NULL;//初始化
for(i = 1;i <= n;i++)
{
scanf("%d",&a);
//動態(tài)申請空間
p = (stuct node*)malloc(sizeof(stuct node));
p->data = a;//存放到當(dāng)前節(jié)點(diǎn)
p ->next = NULL;
if(head ==NULL){
head = p;//創(chuàng)建第一個節(jié)點(diǎn)
}else{
q->next= p;
}
q = p;
//輸入插入的數(shù)
scanf("%d",&a);
t = head;
while(t != NULL){
if(t->next ==NULL || t-> next->data > a){
p = (struct node*)malloc(sizeof( struct node));
//核心
p->data = a;
p->next= t->next;
t->next = p;
break;
}
t= t->next;
}
}
//輸出
t = head
while(t !=NULL){
printf("%d",t->data);
t= t->next;
}
return 0;
}
對于數(shù)據(jù)結(jié)構(gòu)和其存儲代碼只是簡單描述,日后慢慢講解.
三 : 算法簡述和常用基礎(chǔ)算法-排序
在工作中和學(xué)習(xí)中我們經(jīng)常聽到算法算法的,在上學(xué)的時候我們通常會學(xué)習(xí)算法這門單獨(dú)學(xué)科的課程,講的主要是,通過計(jì)算機(jī)語言編程解決一些和應(yīng)用題一樣的一些問題.
好,算法可以理解為是一種手段,或者一種解決方式,一系列的計(jì)算步驟,用來將輸入數(shù)據(jù)轉(zhuǎn)化為輸出結(jié)果
1.算法的意義
(1)用于解決特定的問題
(2)解決同一個問題的不同算法的效率常常相差很大,這種差距的影響往往比硬件和軟件方便的差距還要大.
2. 常用算法
(1)排序
(2)加密
3. 算法的優(yōu)劣
怎樣科學(xué)的評判一個算法的優(yōu)劣,算法那么重要,不同的算法會很大程度上影響運(yùn)行效率
時間復(fù)雜度 : 估算程序指令的執(zhí)行次數(shù)
空間復(fù)雜度 估算所需占用的存儲空間
這兩個的計(jì)算方式我們以后的博客仔細(xì)講解
4. 算法的優(yōu)化方向
(1)用盡量少的內(nèi)存空間
(2)用盡量少的執(zhí)行步驟
(3)空間換時間
(4)時間換空間
5. 排序算法
(1)桶排序
1965年有兩個大神, E.J Issac 和 R.C Singleton 提出來的基本思想.
下面簡單總結(jié)一下這種算法的思想
#include <stdio.h>
int main()
{
int a[10] , i,j,t;
for (i = 0 ; i <= 10 ; i++)
{
//初始化一下數(shù)組
a[i] = 0;
};
//循環(huán)輸入7個數(shù) 對應(yīng)的數(shù)字放到對應(yīng)的桶中
for (int i = 0 ; i <7; i++ )
{
scanf("%d",&t);
a[t]++;
};
//輸出打印
for(i = 0; i<= 10;i++){
for(j = 0;j <= a[i]; j++)
printf("%d",i);//每個桶中的數(shù)出現(xiàn)幾次就打印幾次
};
return 0;
}
總結(jié)分析 : 這是一個簡化版的桶排序實(shí)際上桶排序要復(fù)雜很多這里就是和大家分析一下思路,下面畫一個圖來捋順一下
每個桶的號碼就是存放自己的專屬數(shù)字,比如說1號桶專門存放的就是數(shù)字 1 5號桶專門存放 數(shù)組 5 初見幾次 就往對應(yīng)的桶里面 增加一次,也就是代碼中的 a[t]++;
可以看的出來這種算法需要的空間很大,也就是說,我們要準(zhǔn)備很多的 桶 這點(diǎn)并不可取
接下來看看其時間復(fù)雜度O(M+N) (計(jì)算方式以后博客會說明)
(2)冒泡排序
1956 年就有人曾經(jīng)研究過冒泡排序,之后很多人研究改進(jìn)過,但結(jié)果都令人失望,正如 高德納 所說 冒泡排序除了它迷人的名字和導(dǎo)致了某些有趣的理論問題這一事實(shí)之外,似乎沒什么值得推薦的
#include <stdio.h>
int main(){
int a[100],i,j,t,n;
//輸入n 個數(shù)存放到數(shù)組 a中
for(i = 0 ; i <= n ; i++){
scanf("%d",&a[i]);
};
//冒泡排序交換核心
for(i = 0 ; j <= n-1;i++){
for(j = 1 ; j < n - i;j++)
{
if( a[j] < a[j+1] ){
t = a[j]; a[j] = a[j+1]; a[j+1] = t;
}
}
}
//輸出結(jié)果
for(i = 0 ;i <= n;i++){
printf("%d".a[i]);
}
return 0;
}
總結(jié) : 冒泡排序就是兩兩交互比較大小,核心代碼中的外層循環(huán) 是 走的 趟 數(shù) 控制交換了幾趟,每一趟都能決定出一個最大的數(shù) 或者 最小的數(shù) ,為什么是 n-1 因?yàn)樽詈笠惶瞬挥门芤泊_定了,因?yàn)榫褪Ｏ履且粋€數(shù)了,同理內(nèi)層循環(huán) n - i 因?yàn)槊刻私粨Q 確定了一個數(shù) ,所以我們內(nèi)層循環(huán) 的時候 就要 排除那個已經(jīng) 確定的 數(shù).
接下來看看 冒泡排序 的時間復(fù)雜度 ->O(N2)
(3)快速排序
1960年 東尼霍爾 提出了快速排序 ,之后又有人做了優(yōu)化.
思路 : 簡單排序就是確定一個數(shù) 基數(shù) 讓基數(shù)左邊的數(shù)小于基數(shù)(這里說的是遞增),讓基數(shù)右邊的數(shù)大于基數(shù),
然后再去基數(shù)左邊做同樣操作 ,基數(shù)右邊做同樣操作
接下來上圖來分析一下
圖中 (1) 我們通常把首個數(shù)設(shè)置為基數(shù) 我們在序列左邊放了一個檢索 i 在 序列 右邊放了一個檢索 j 進(jìn)行檢索
當(dāng)i 發(fā)現(xiàn)了 比 '6' 大的數(shù)則停下,當(dāng) j 發(fā)現(xiàn)了 比 6 小的數(shù)則停下,然后 把發(fā)現(xiàn)的數(shù)交換位置 如圖(2)
交換完畢 i 和 j 繼續(xù)移動 如圖(3) 繼續(xù)交換 最后 i 和 j 相遇 檢索完畢
最后把 3 和 6 交換位置,以 6為基數(shù)的 檢索結(jié)束 ,接下來 6 左邊的數(shù) 和 6 右邊的數(shù)進(jìn)行 同理操作
#include <stdio.h>
int a[101],n;
//我們把排序封裝成方法 參數(shù) 分別是 左邊啟點(diǎn) 和 右邊啟點(diǎn)
void quicksort (int left,int right){
int i,j,t,temp;
if(left > right)
return;
};
temp = a[left];//確定基數(shù)
i = left;
j = right;
while(i != j){
//右邊先開始檢索
while( a[j] >= temp && i < j)
j--;
}
//從左往右檢索
while( a[i] <= temp && i < j ){
i++
}
//交換兩個數(shù)的位置
if( i < j) //沒有相遇
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//基數(shù)歸位
a[left] = a[i];
a[i] = temp;
quicksort(left,i-1);//處理基數(shù)左邊的
quicksort(i+1,right);//處理基數(shù)右邊的
return;
}
int main()
{
int i,j;
//讀取數(shù)據(jù)
scanf("%d",&n);
for(i = 1;i < n;i++)
scanf("%d",&a[1]);
}
//調(diào)用
quicksort(1,n);
//輸出
for(i = 1; i <= n ;i++){
printf("%d", a[i]);
}
return 0;
總結(jié) : 為什么 j 要先移動,而 i 要后移動呢
因我我們把基數(shù)設(shè)置在了左邊,我們假設(shè)一種特殊情況,就是數(shù)據(jù)序列已經(jīng)是從小到大拍好了的,假如我們從左邊開始檢索,因?yàn)榛鶖?shù)在左邊,循環(huán)條件可訂貨滿足,所以,i 肯定移動到下一個,所以就發(fā)生了錯誤,所以我們要右j邊先移動.
四 : 總結(jié)
簡單的聊過了數(shù)據(jù)結(jié)構(gòu)和算法,一個好的程序,我們不僅要考慮它的運(yùn)行速度,也要配上好的數(shù)據(jù)結(jié)構(gòu),也就是數(shù)據(jù)的存儲方式,數(shù)據(jù)結(jié)構(gòu)往往配合著算法的使用 更佳炫酷.
