數據結構與演算法分析視頻

㈠ 數據結構與演算法分析 C++

你說的是中序線索二叉樹的插入和刪除

#include<stdio.h>
#include"malloc.h"
#include"windows.h"
#definemaxsize20//規定樹中結點的最大數目
typedefstructnode{//定義數據結構
intltag,rtag;//表示child域指示該結點是否孩子
chardata;//記錄結點的數據
structnode*lchild,*rchild;//記錄左右孩子的指針
}Bithptr;

Bithptr*Q[maxsize];//建隊，保存已輸入的結點的地址
Bithptr*CreatTree(){//建樹函數，返回根指針
charch;
intfront,rear;
Bithptr*T,*s;
T=NULL;
front=1;rear=0;//置空二叉樹
printf("建立一棵二叉樹，請輸入結點信息：
");
printf("請輸入新的結點信息，@為空結點，#為結束標志：");
ch=getchar()();//輸入第一個字元
while(ch!='#')//判斷是否為結束字元
{
s=NULL;
if(ch!='@')//判斷是否為虛結點
{
s=(Bithptr*)malloc(sizeof(Bithptr));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
}
rear++;
Q[rear]=s;//將結點地址加入隊列中
if(rear==1)T=s;//輸入為第一個結點為根結點
else
{
if(s!=NULL&&Q[front]!=NULL)//孩子和雙親結點均不是虛結點
if(rear%2==0)
Q[front]->lchild=s;
elseQ[front]->rchild=s;
if(rear%2==1)front++;
}getchar()();
printf("請輸入新的結點信息，@為空結點，#為結束標志：");
ch=getchar()();
}
returnT;
}
voidInorder(Bithptr*T)//中序遍歷
{
if(T)
{
if(T->ltag!=1)Inorder(T->lchild);
printf("→%c",T->data);
if(T->rtag!=1)Inorder(T->rchild);
}
}

Bithptr*pre=NULL;
voidPreThread(Bithptr*root)//中序線索化演算法，函數實現
{
Bithptr*p;
p=root;
if(p){
PreThread(p->lchild);//線索化左子樹
if(pre&&pre->rtag==1)pre->rchild=p;//前驅結點後繼線索化
if(p->lchild==NULL)
{
p->ltag=1;
p->lchild=pre;
}
if(p->rchild==NULL)//後繼結點前驅線索化
p->rtag=1;
pre=p;
PreThread(p->rchild);
}
}
voidPrintIndex(Bithptr*t)//輸出線索
{
Bithptr*f;
f=t;
if(f)
{
if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)printf("【%c】",f->data);//如果是第一個結點
if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data);//如果此結點有前驅就輸出前驅和此結點
if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data);//如果此結點有前驅也有後繼，就輸出後繼
elseif(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果沒有前驅，就輸出此結點和後繼
printf("
");
if(f->ltag!=1)PrintIndex(f->lchild);
if(f->rtag!=1)PrintIndex(f->rchild);
}
}
Bithptr*SearchChild(Bithptr*point,charfindnode)//查找孩子結點函數
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if(point->data==findnode)returnpoint;
else
if(point->ltag!=1){point1=SearchChild(point->lchild,findnode);if(point1!=NULL)returnpoint1;}
if(point->rtag!=1){point2=SearchChild(point->rchild,findnode);if(point2!=NULL)returnpoint2;}
returnNULL;
}
else
returnNULL;
}
Bithptr*SearchPre(Bithptr*point,Bithptr*child)//查找父親結點函數
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))returnpoint;//找到則返回
else
if(point->ltag!=1)
{
point1=SearchPre(point->lchild,child);
if(point1!=NULL)
returnpoint1;
}
if(point->rtag!=1)
{
point2=SearchPre(point->rchild,child);
if(point2!=NULL)
returnpoint2;
}
returnNULL;
}
else
returnNULL;
}
voidInsert(Bithptr*root)
{
charch;
charc;
Bithptr*p1,*child,*p2;
printf("請輸入要插入的結點的信息:");
scanf("%c",&c);
scanf("%c",&c);
p1=(Bithptr*)malloc(sizeof(Bithptr));//插入的結點信息
p1->data=c;
p1->lchild=NULL;
p1->rchild=NULL;
p1->rtag=0;
p1->ltag=0;
printf("輸入查找的結點信息:");
scanf("%c",&ch);
scanf("%c",&ch);
child=SearchChild(root,ch);//查孩子結點的地址
if(child==NULL){
printf("沒有找到結點
");
system("pause");
return;
}
elseprintf("發現結點%c
",child->data);
if(child->ltag==0)//當孩子結點有左孩子的時候
{
p2=child;
child=child->lchild;
while(child->rchild&&child->rtag==0)//找到左子樹下，最右結點
child=child->rchild;
printf("發現結點%c
",child->data);
p1->rchild=child->rchild;//後繼化
p1->rtag=1;
child->rtag=0;
child->rchild=p1;//連接
p1->lchild=child;//前驅化
p1->ltag=1;
}
else//當孩子結點沒有左孩子的時候
{
p1->lchild=child->lchild;//前驅化
child->ltag=0;
p1->ltag=1;
child->lchild=p1;
p1->rchild=child;
p1->rtag=1;
}
printf("	插入結點操作已經完成，並同時完成了線索化的恢復
");
}

㈡ 數據結構與演算法分析 —— C 語言描述：開放定址法

分離鏈接散列演算法的缺點是需要指針，由於給新單元分配地址需要時間，因此這就導致演算法的速度多少有些緩慢，同時演算法實際上還要求實現另一種數據結構。除使用鏈表解決沖突外，開放定址散列法（open addressing hashing）是另外一種用鏈表解決沖突的方法。在開放定址散列演算法系統中，如果有沖突發生，那麼就要嘗試選擇另外的單元，直到找出空的單元為止。更一般地，單元 相繼試選，其中 ，且 。函數 F 是沖突解決方法，因為所有的數據都要置入表內，所以開放定址散列法所需要的表要比分離鏈接散列用的表大。一般說來，對開放定址散列演算法來說，裝填因子應該低於 。開放定址散列法有三種常用的沖突解決辦法：

在線性探測法中，函數 F 是 的線性函數，典型的情形是 。這相當於逐個探測每個單元（必要時可以繞回）以查找出一個空空單元。即插入一個第一個沖突關鍵字，它將被放入下一個空閑地址，即地址 0，該地址是開放的。之後插入的沖突關鍵字，會對表進行試選，只要表足夠大，總能夠找到一個自由單元，但是如此花費的時間是相當多的。更糟的是，即使表相對較空，這樣占據的單元也會開始形成一些區塊，其結果稱為一次聚集（primary clustering），於是，散列到區塊中的任何關鍵字都需要多次試選單元才能解決沖突，然後該關鍵字被添加到相應的區塊中。

可以證明，使用線性探測的預期探測次數對於插入和不成功的查找來說大約為 ，而對於成功的查找來說則是 。略加思考不難得出，成功查找應該比不成功查找平均花費較少的時間。

如果聚算不算是問題，那麼對應的公式就不難得到。我們假設有一個很大的表，並設每次探測都與前面的探測無關。對於隨機沖突解決辦法而言，這些假設是成立的，並且當 不是非常接近 1 時也是合理的。首先，我們導出在一次不成功查找中探測的期望次數，而這正是直到我們找到一個空單元的探測次數。由於空單元所佔的份額為 ，因此我們預計要探測的單元數是 。一次成功查找的探測次數等於該特定元素插入時所需要的探測次數。當一個元素被插入時，可以看成是一次不成功查找的結果。因此，我們可以使用一次不成功查找的開銷來計算一次成功查找的平均開銷。

需要指出， 在 0 到當前值之間的變化，因此早期的插入操作開銷較少，從而降低平均開銷。我可以通過使用積分計算插入時間平均值的方法來估計平均值，如此得到

這些公式顯然優於線性探測相應的公式，聚集不僅是理論上的問題，而且實際上也發生在具體的實現中。線性探測的預計探測次數與 呈正比，即 越小，插入操作平均次數越少。

平方探測是消除線性探測中一次聚集問題的沖突解決辦法。平方探測就是沖突函數為二次函數的探測方法。流行的選擇是 。

對於線性探測，讓元素幾乎填滿散列表並不是個好主意，因為此時表的性能會降低。對於平方探測情況甚至更糟：一旦表被填滿超過一半，當表的大小不是素數時甚至在表被填滿超過一半之前，就不能保證一次找到一個空單元了。這是因為最多有一半的表可以用作解決沖突的備選位置。

定理：如果使用平方探測，且表的大小是素數，那麼當表至少有一半是空的時候，總能夠插入一個新的元素。

哪怕表有比一半多一個的位置被填滿，那麼插入都有可能失敗（雖然這是非常難以見到的，但是把它記住很重要。）。另外，表的大小是素數也非常重要，如果表的大小不是素數，則備選單元的個數可能會銳減。

在開放定址散列表中，標準的刪除操作不能施行，因為相應的單元可能已經引起過沖突，元素繞過它存在了別處。例如，如果我們刪除一個沖突的中間元素，那麼實際上所有其他的 Find 常式都將不能正確運行。因此，開放定址散列表需要懶惰刪除，雖然在這種情況下並不存在真正意義上的懶惰。

開放定址散列表的類型聲明如下，這里，我們不用鏈表數組，而是使用散列表項單元的數組，與在分離鏈接散列中一樣，這些單元也是動態分配地址的。

初始化開放定址散列表的常式如下，由分配空間（第1～10行）及其後將每個單元的 Info 域設置為 Empty 組成。

使用平方探測散列法的 Find 常式如下。如果分裂鏈接散列法一樣， 將返回 Key 在散列表中的位置。如果 Key 不出現，那麼 Find 將返回最後的單元。該單元就是當需要時，Key 將被插入的地方。此外，因為被標記了 Empty，所以表達 Find 失敗很容易。為了方便起見，我們假設散列表的大小至少為表中元素個數的兩倍，因此平方探測方法總能夠實現。否則，我們就要在第 4 行前測試 。在下面的常式中，標記為刪除的那些元素被認為還在表內，這可能引起一些問題，因為該表可能提前過滿。

第 4～6 行為進行平方探測的快速方法。由平方解決函數的定義可知， ，因此，下一個要探測的單元可以用乘以 2（實際上就是進行一位二進制移位）並減 1 來確定。如果新的定位越過數組，那麼可以通過減去 TableSize 把它拉回到數組范圍內。這比通常的方法要快，因為它避免了看似需要的乘法和除法。注意一條重要的警告：第 3 行的測試順序很重要，切勿改變它。

下面的常式是插入。正如分離鏈接散列方法那樣，若 Key 已經存在，則我們就什麼也不做。其他工作只是簡單的修改。否則，我們就把要插入的元素放在 Find 常式指出的地方。

雖然平方探測排除了一次聚集，但是散列到同一位置上的那些元素將探測相同的備選單元。這叫做二次聚集（secondary clustering）。二次聚集是理論上的一個小缺憾，模擬結果指出，對每次查找，它一般要引起另外的少於一半的探測。

雙散列（double hashing）能夠解決平方探測中的二次聚集問題，不過也需要花費另外的一些乘法和除法形銷。對於雙散列，一種流行的選擇是 。這個公式是說，我們將第二個散列函數應用到 X 並在距離 , 等處探測。 選擇的不好將會是災難性的。

在雙散列時，保證表的帶下為素數是非常重要的。假設我們在插入一個關鍵字的時候，發現它已經引發沖突，就會選擇備選位置，如果表的大小不是素數，那麼備選單元就很有可能提前用完。然後，如果雙散列正確實現，則模擬表明，預期的探測次數幾乎和隨機沖突解決方法的情形相同。這使得雙散列理論上很有吸引力，不過，平方探測不需要使用第二個散列函數，從而在實踐中可能更簡單並且更快。

㈢ 數據結構與演算法分析

本文出自：

www點54manong點com

請尊重原創，轉載請註明出處，謝謝！

什麼是數據結構，為什麼要學習數據結構？數據結構是否是一門純數學課程？它在專業課程體系中起什麼樣的作用？我們要怎麼才能學好數據結構？… 相信同學們在剛開始《數據結構》這門課的學習時，心裡有著類似前面幾個問題的這樣那樣的疑問。希望下面的內容能幫助大家消除疑惑，下定決心堅持學好這門課：

1 學習數據數據結構的意義

數據結構是計算機科學與技術專業、計算機信息管理與應用專業，電子商務等專業的基礎課，是十分重要的核心課程。所有的計算機系統軟體和應用軟體都要用到各種類型的數據結構。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設計語言是難以應付當前眾多復雜的課題。要想有效地使用計算機、充分發揮計算機的性能，還必須學習和掌握好數據結構的有關知識。打好「數據結構」這門課程的扎實基礎，對於學習計算機專業的其他課程，如操作系統、資料庫管理系統、軟體工程、編譯原理、人工智慧、圖視學等都是十分有益的。

2 為什麼要學習數據結構

在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。當我們使用計算機來解決一個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題抽象出一個適當的數學模型，然後設計或選擇一個解此數學模型的演算法，最後編出程序進行調試、測試，直至得到最終的解答。例如，求解梁架結構中應力的數學模型的線性方程組，可以使用迭代演算法來求解。

由於當時所涉及的運算對象是簡單的整型、實型或布爾類型數據，所以程序設計者的主要精力是集中於程序設計的技巧上，而無須重視數據結構。隨著計算機應用領域的擴大和軟、硬體的發展，非數值計算問題越來越顯得重要。據統計，當今處理非數值計算性問題佔用了85%以上的機器時間。這類問題涉及到的數據結構更為復雜，數據元素之間的相互關系一般無法用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的數據結構，才能有效地解決問題。下面所列舉的就是屬於這一類的具體問題。

例1：圖書館信息檢索系統。當我們根據書名查找某本書有關情況的時候；或者根據作者或某個出版社查找有關書籍的時候，或根據書刊號查找作者和出版社等有關情況的時候，只要我們建立了相關的數據結構，按照某種演算法編寫了相關程序，就可以實現計算機自動檢索。由此，可以在圖書館信息檢索系統中建立一張按書刊號順序排列的圖書信息表和分別按作者、書名、出版社順序排列的索引表，如圖1.1所示。由這四張表構成的文件便是圖書信息檢索的數學模型，計算機的主要操作便是按照某個特定要求（如給定書名）對圖書館藏書信息文件進行查詢。

諸如此類的還有學生信息查詢系統、商場商品管理系統、倉庫物資管理系統等。在這類文檔管理的數學模型中，計算機處理的對象之間通常存在著的是一種簡單的線性關系，這類數學模型可稱為線性的數據結構。

例2：八皇後問題。在八皇後問題中，處理過程不是根據某種確定的計演算法則，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態。從最初的布局狀態開始，一步步地進行試探，每試探一步形成一個新的狀態，整個試探過程形成了一棵隱含的狀態樹。如圖1.2所示（為了描述方便，將八皇後問題簡化為四皇後問題）。回溯法求解過程實質上就是一個遍歷狀態樹的過程。在這個問題中所出現的樹也是一種數據結構，它可以應用在許多非數值計算的問題中。

例3：教學計劃編排問題。一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些必須按規定的先後次序進行，有些則沒有次序要求。即有些課程之間有先修和後續的關系，有些課程可以任意安排次序。這種各個課程之間的次序關系可用一個稱作圖的數據結構來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先於課程j進行。由以上三個例子可見，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如線性表、樹、圖之類的數據結構。因此，可以說數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。

學習數據結構的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來並對它們進行處理。與此同時，通過演算法訓練來提高學生的思維能力，通過程序設計的技能訓練來促進學生的綜合應用能力和專業素質的提高。

3數據結構課程的內容

數據結構與數學、計算機硬體和軟體有十分密切的關系，它是介於數學、計算機硬體和計算機軟體之間的一門計算機專業的核心課程，是高級程序設計語言、操作系統、編譯原理、資料庫、人工智慧、圖視學等課程的基礎。同時，數據結構技術也廣泛應用於信息科學、系統工程、應用數學以及各種工程技術領域。

數據結構課程重在討論軟體開發過程中的方案設計階段、同時設計編碼和分析階段的若干基本問題。此外，為了構造出好的數據結構及其實現，還需考慮數據結構及其實現的評價與選擇。因此，數據結構的內容包括三個層次的五個「要素」，如圖1.3所示。

數據結構的核心技術是分解與抽象。通過分解可以劃分出數據的三個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現細節，就得到運算的定義。上述兩個方面的結合使我們將問題變換為數據結構。這是一個從具體（即具體問題）到抽象（即數據結構）的過程。然後，通過增加對實現細節的考慮進一步得到存儲結構和實現運算，從而完成設計任務。這是一個從抽象（即數據結構）到具體（即具體實現）的過程。熟練地掌握這兩個過程是數據結構課程在專業技能培養方面的基本目標。

結束語：數據結構作為一門獨立的課程在國外是從1968年才開始的，但在此之前其有關內容已散見於編譯原理及操作系統之中。20世紀60年代中期，美國的一些大學開始設立有關課程，但當時的課程名稱並不叫數據結構。1968年美國唐.歐.克努特教授開創了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本演算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。從20世紀60年代末到70年代初，出現了大型程序，軟體也相對獨立，結構程序設計成為程序設計方法學的主要內容，人們越來越重視數據結構。從70年代中期到80年代，各種版本的數據結構著作相繼出現。目前，數據結構的發展並未終結，一方面，面向各專門領域中特殊問題的數據結構得到研究和發展，如多維圖形數據結構等；另一方面，從抽象數據類型和面向對象的觀點來討論數據結構已成為一種新的趨勢，越來越被人們所重視。

㈣ 那位大佬有數據結構和演算法java版的視頻如果好的話可以購買，

我有馬士兵視頻的網路雲版，裡麵包含前期的基礎演算法和數據結構，但是沒有面面俱到的那種專業數據結構和演算法

當然還包括許多其他老師的數據結構和演算法的視頻，不知道你要的是什麼樣的

㈤ 大家有沒有數據結構與演算法的視頻或好書呀

個人感覺比較好的 清華嚴尉敏的《數據結構》 中國鐵道出版社的 《數據結構C語言版》 weiss的《數據結構與演算法分析》 《演算法導論》 《演算法概論》 Sedgewick《演算法I－V》 Knuth《計算機程序設計藝術》 《編程珠璣》 好書很多，pdf和視頻之類的可以去 www.verycd.com 下，有很多好資源 ：）