數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版本)
第1章 緒論
1.常用的數(shù)據(jù)結(jié)構(gòu)類型:集合撬碟、線性图甜、樹形、圖狀囚灼。
2.數(shù)據(jù)結(jié)構(gòu):
- 邏輯結(jié)構(gòu):數(shù)據(jù)元素之間的關(guān)系
- 存儲(chǔ)結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示骆膝。存儲(chǔ)結(jié)構(gòu)分為:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
3.算法是對(duì)特定問(wèn)題求解步驟的一種描述灶体,算法具有如下特性:有窮性阅签、確定性、可行性蝎抽、輸入政钟、輸出。
4.算法的度量:
- 時(shí)間復(fù)雜度
- 空間復(fù)雜度
第二章 線性表
1.線性表的定義:
- 存在唯一一個(gè)“第一個(gè)”元素
- 存在唯一一個(gè)“最后一個(gè)”元素
- 除第一個(gè)元素外樟结,每一個(gè)元素都有且只有一個(gè)前驅(qū)
- 除最后一個(gè)元素外养交,每個(gè)元素都有且只有一個(gè)后繼
2.線性表合并的方法:
- 將表A中的元素逐個(gè)和B中的比較,不同就加入到B中瓢宦。時(shí)間復(fù)雜度為O(len(A)*len(B))
- AB是有序排列的前提下碎连,使用兩個(gè)指針?lè)謩e指向A和B,將兩者較小的元素插入到C中刁笙,然后移動(dòng)較小的指針破花,直到全部插入到C。時(shí)間復(fù)雜度為O(len(A)+len(B))
3.線性表的順序?qū)崿F(xiàn):滿足LOC(A(i+l))=LOC(A(i))+l疲吸,LOC表示元素地址座每。特點(diǎn):下標(biāo)讀取快O(1),插入刪除O(n)摘悴。
#include <stdlib.h>
#ifndef SEQUENCE_LINER_LIST_H
#define SEQUENCE_LINER_LIST_H
/*
線性表的順序?qū)崿F(xiàn)
*/
#define LIST_INIT_SIZE 100 //初始分配量
#define LIST_INCREMENT 10 //增量
#define LIST_TYPE int //存儲(chǔ)類型
typedef struct strSequenceLinerList
{
LIST_TYPE *elem; //存儲(chǔ)空間基址
unsigned int length; //當(dāng)前長(zhǎng)度
unsigned int listSize; //當(dāng)前存儲(chǔ)容量
}SequnceLinerList;
static enum Status
{
OK,
FAILED,
OVERFLOW
};
/* 線性表初始化 */
Status initSequenceLinerList(SequnceLinerList& list)
{
list.elem = (LIST_TYPE *)malloc(sizeof(LIST_TYPE)*LIST_INIT_SIZE);
if (!list.elem)
{
return OVERFLOW;
}
list.length = 0;
list.listSize = LIST_INIT_SIZE;
return OK;
}
/* 擴(kuò)展 */
Status resizeSequenceLinerList(SequnceLinerList& list)
{
printf("Resize...\n");
list.elem = (LIST_TYPE*)realloc(list.elem, sizeof(LIST_TYPE)*(list.listSize + LIST_INCREMENT));
if (!list.elem)
{
return OVERFLOW;
}
list.listSize += LIST_INCREMENT;
return OK;
}
/* 打印 */
void printSequnceLinerList(SequnceLinerList& list)
{
printf("Begin print list...\n");
printf("length=%d,listSize=%d.\n",list.length,list.listSize);
unsigned int i = 0;
for (; i < list.length-1;++i)
{
printf("%d,",list.elem[i]);
}
printf("%d\n", list.elem[i]);
printf("End print list.\n");
}
/* 線性表插入:position表示插入的位置峭梳,從1開始。第一個(gè)元素是list.elem[0] */
Status insertSequenceLinerList(SequnceLinerList& list, unsigned int position, LIST_TYPE value)
{
if (position<1 || position>list.length+1)
{
return FAILED;
}
if (list.length >= list.listSize)
{
Status res = resizeSequenceLinerList(list);
if (OK != res)
{
return FAILED;
}
}
LIST_TYPE* p = &list.elem[position -1];
LIST_TYPE* q = &list.elem[list.length];
for (; p != q; --q)
{
*(p + 1) = *p;
}
list.length++;
*p = value;
return OK;
}
/* 刪除元素 */
Status deleteSequenceLinerList(SequnceLinerList& list, unsigned int position)
{
if (position<1 || position>list.length)
{
return FAILED;
}
LIST_TYPE* p = &list.elem[position - 1];
LIST_TYPE* q = &list.elem[list.length - 1];
for (; p != q; ++p)
{
*p = *(p+1);
}
--list.length;
return OK;
}
/* 查找:第一個(gè)值的下標(biāo) */
unsigned int findSequenceLinerList(SequnceLinerList& list, int value)
{
for (unsigned int i = 0; i < list.length;++i)
{
if (value == list.elem[i])
{
return i;
}
}
return -1;
}
/* 排序(冒泡) */
void sortSequeceLinerList(SequnceLinerList& list)
{
unsigned int i = 0;
unsigned int j = 0;
for (; i < list.length-1;++i)
{
for (j = i + 1; j < list.length; ++j)
{
if (list.elem[i]>list.elem[j])
{
LIST_TYPE tmp = list.elem[i];
list.elem[i] = list.elem[j];
list.elem[j] = tmp;
}
}
}
}
/* 銷毀 */
void destroySequenceLincerList(SequnceLinerList& list)
{
delete list.elem;
list.elem = NULL;
}
#endif
4.線性表的鏈?zhǔn)綄?shí)現(xiàn):通過(guò)p=p.next查找具體位置的鏈表蹂喻。特點(diǎn):插入葱椭、刪除快O(n)。
#include <stdio.h>
#include <stdio.h>
#ifndef LINK_LINER_LIST_H
#define LINK_lINER_LIST_H
#define LINK_LIST_TYPE int
/*
線性表的鏈表實(shí)現(xiàn)
*/
typedef struct strLinkLinerList
{
LINK_LIST_TYPE data;
struct strLinkLinerList* pNext;
}LinkLinerList;
LinkLinerList* head = NULL;
/* 鏈表初始化 */
Status initLinkLinerList()
{
if (NULL == head)
{
head = (LinkLinerList*)malloc(sizeof(LinkLinerList));
if (!head)
{
return OVERFLOW;
}
head->pNext = NULL;
return OK;
}
else
{
return FAILED;
}
}
/* 添加元素 */
Status insertLinkLinerList(LINK_LIST_TYPE value)
{
if (NULL == head)
{
return FAILED;
}
LinkLinerList* p = head;
while (p->pNext)
{
p = p->pNext;
}
LinkLinerList* tmp = (LinkLinerList*)malloc(sizeof(LinkLinerList));
if (!tmp)
{
return OVERFLOW;
}
tmp->data = value;
tmp->pNext = NULL;
p->pNext = tmp;
return OK;
}
/*打印*/
void printLinkLinerList()
{
printf("Begin print...\n");
if (NULL == head || NULL == head->pNext)
{
printf("List is null.");
}
LinkLinerList* p = head->pNext;
while (p->pNext)
{
printf("%d,",p->data);
p = p->pNext;
}
printf("%d\n", p->data);
printf("End print.\n");
}
/* 排序 */
Status sortLinkLinerList()
{
if (NULL == head || NULL == head->pNext)
{
return FAILED;
}
LinkLinerList* p = head->pNext;
LinkLinerList* q = p->pNext;
while (p)
{
q = p->pNext;
while (q)
{
if (p->data > q->data)
{
LINK_LIST_TYPE tmp = p->data;
p->data = q->data;
q->data = tmp;
}
q = q->pNext;
}
p = p->pNext;
}
return OK;
}
/* 長(zhǎng)度 */
unsigned int lengthLinkLinerList()
{
if (head == NULL || head->pNext == NULL)
{
return 0;
}
LinkLinerList* p = head->pNext;
unsigned int length = 0;
while (p)
{
p = p->pNext;
length++;
}
return length;
}
/* 刪除 */
Status deleteLinkLinerList(unsigned int position)
{
if (position > lengthLinkLinerList() || position < 1)
{
return FAILED;
}
else
{
LinkLinerList* p = head;
LinkLinerList* q = p->pNext;
if (NULL == p || NULL == q)
{
return FAILED;
}
while (--position)
{
p = p->pNext;
q = p->pNext;
}
p->pNext = q->pNext;
free(q);
return OK;
}
}
/* 銷毀 */
void destroyLinkLinerList()
{
if (NULL == head)
{
return;
}
else
{
LinkLinerList* p = head->pNext;
LinkLinerList* q = p;
while (p)
{
p = p->pNext;
free(q);
q = p;
}
}
}
#endif
上面實(shí)現(xiàn)的是線性表的鏈?zhǔn)浇Y(jié)構(gòu)口四。此外孵运,線性表通過(guò)鏈表還可以實(shí)現(xiàn):
- 循環(huán)列表:表最后的一個(gè)節(jié)點(diǎn)的指針指向表頭
- 雙列表:指針可以指向下一個(gè)元素或者上一個(gè)元素
5.線性表的用途:
- 一元多項(xiàng)式的表示和相加
第3章 棧和隊(duì)列
1.棧和隊(duì)列是特殊的線性表。
2.棧是先進(jìn)后出的線性表蔓彩,其表示:typedef struct{Type *base;Type *top; int stacksize;}SqStack
治笨;其中base始終指向棧底,top隨元素的添加一直指向棧頂赤嚼】趵担可以有順序?qū)崿F(xiàn)和鏈表實(shí)現(xiàn)。
3.棧的應(yīng)用舉例:
- 數(shù)制轉(zhuǎn)換
- 括號(hào)匹配
- 行編輯器幫助處理錯(cuò)誤輸入
- 迷宮求解
- 表達(dá)式求解
- 實(shí)現(xiàn)遞歸
3.隊(duì)列是先進(jìn)先出的線性表更卒〉确酰可以由鏈表實(shí)現(xiàn)和順序?qū)崿F(xiàn)。
第四章 串
1.串是由零到多個(gè)字符組成的字符序列蹂空。
2.串的模式匹配算法(查找子串):
- 找到主串中第一個(gè)等于子串首字符的位置俯萌,開始逐步遍歷子串和主串:時(shí)間復(fù)雜度O(n*(m-n+1)),其中m,n是主串上枕、子串長(zhǎng)度
- kmp算法:關(guān)鍵是部分匹配值的計(jì)算("部分匹配"的實(shí)質(zhì)是绳瘟,有時(shí)候,字符串頭部和尾部會(huì)有重復(fù)姿骏。比如糖声,"ABCDAB"之中有兩個(gè)"AB",那么它的"部分匹配值"就是2("AB"的長(zhǎng)度)分瘦。搜索詞移動(dòng)的時(shí)候蘸泻,第一個(gè)"AB"向后移動(dòng)4位(字符串長(zhǎng)度-部分匹配值),就可以來(lái)到第二個(gè)"AB"的位置)嘲玫。時(shí)間復(fù)雜度O(n+m)悦施。KMP算法僅當(dāng)子串與主串之間存在很多"部分匹配"的情況下才快的多。詳見(jiàn)
http://kb.cnblogs.com/page/176818/
去团。
第五章 數(shù)組和廣義表
1.廣義表(Lists抡诞,又稱列表)是一種非線性的數(shù)據(jù)結(jié)構(gòu)穷蛹,是線性表的一種推廣。即廣義表中放松對(duì)表元素的原子限制昼汗,容許它們具有其自身結(jié)構(gòu)肴熏。
第六章 樹和二叉樹
1.樹的相關(guān)概念:
- 度:節(jié)點(diǎn)的子樹數(shù)目稱之為節(jié)點(diǎn)的度。度為0的節(jié)點(diǎn)稱之為葉子顷窒。
- 深度:樹中結(jié)點(diǎn)的最大層次蛙吏。
2.二叉樹子節(jié)點(diǎn)至多有兩個(gè),且有左右之分鞋吉。二叉樹有五種基本形態(tài):空鸦做、根、右子樹為空谓着、左右子樹非空泼诱、左子樹為空。二叉樹的性質(zhì):
- 第i層有2^(i-1)個(gè)節(jié)點(diǎn)
- 深度為k的二叉樹至多2^k-1個(gè)節(jié)點(diǎn)
- 終端節(jié)點(diǎn)數(shù)為n赊锚,度為2的節(jié)點(diǎn)數(shù)為m坷檩,則n=m+1
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是(log2N)+1
3.二叉樹分類:
- 滿二叉樹:深度為k且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹
- 完全二叉樹:深度為k,有n個(gè)結(jié)點(diǎn)的二叉樹改抡,每個(gè)結(jié)點(diǎn)的編號(hào)與深度為k的滿二叉樹編號(hào)一一對(duì)應(yīng)
4.二叉樹的存儲(chǔ)結(jié)構(gòu):
- 順序結(jié)構(gòu):按照完全二叉樹的編號(hào)將其存放在一位數(shù)組中標(biāo)有i-1的分量中矢炼。
- 鏈表結(jié)構(gòu):
typedef struct BitNode{ElemType data; struct BitNode *lchild,*rchild}BitNode;
5.二叉樹的遍歷:
- 先序(根)遍歷
- 中序(根)遍歷
- 后序(根)遍歷
先根和后根反映的是雙親與孩子節(jié)點(diǎn)的關(guān)系,中根反映的是兄弟節(jié)點(diǎn)之間的左右次序阿纤。對(duì)于表達(dá)式而言句灌,這三種遍歷分別前綴表達(dá)式(波蘭表達(dá)式)、中綴表達(dá)式和后綴表達(dá)式(逆波蘭表達(dá)式)欠拾。
6.二叉樹的確定:
- 已知先根和中根遍歷可以建立唯一二叉樹
- 已知后根和中根遍歷可以建立唯一二叉樹
- 已知先根和后根遍歷不可以建立唯一二叉樹
7.二叉樹的遍歷可以使用遞歸實(shí)現(xiàn)闯两,其非遞歸中根遍歷的算法是(使用棧操作):
[圖片上傳失敗...(image-5f478f-1524397579659)]
8.二叉樹從根開始分層從左至右遍歷算法是(使用隊(duì)列操作):
9.線索二叉樹:指向前驅(qū)或者后繼的節(jié)點(diǎn)的鏈成為線索帮孔。線索二叉樹使用的節(jié)點(diǎn)結(jié)構(gòu)為:data、left、right言缤、ltag璧坟、rtag本冲。其中l(wèi)tag(rtag)=0表示子樹囊蓝,=1表示前驅(qū)(后繼)節(jié)點(diǎn)。
10.赫夫曼樹又稱最優(yōu)樹刹枉,是一類帶權(quán)路徑長(zhǎng)度(子葉到根的路徑個(gè)數(shù))最短的樹叽唱。赫夫曼樹的構(gòu)造算法:赫夫曼算法:
- (1)以權(quán)值分別為W1,W2...Wn的n各結(jié)點(diǎn),構(gòu)成n棵二叉樹T1,T2,...Tn并組成森林F={T1,T2,...Tn},其中每棵二叉樹 Ti僅有一個(gè)權(quán)值為 Wi的根結(jié)點(diǎn)微宝;
- (2)在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹棺亭,并且置新二叉樹根結(jié)點(diǎn)權(quán)值為左右子樹上根結(jié)點(diǎn)的權(quán)值之和(根結(jié)點(diǎn)的權(quán)值=左右孩子權(quán)值之和,葉結(jié)點(diǎn)的權(quán)值= Wi)
- (3)從F中刪除這兩棵二叉樹蟋软,同時(shí)將新二叉樹加入到F中;
- (4)重復(fù)(2)镶摘、(3)直到F中只含一棵二叉樹為止嗽桩,這棵二叉樹就是Huffman樹。
11.赫夫曼樹的應(yīng)用:
- 不同分?jǐn)?shù)段評(píng)定優(yōu)良中差凄敢,可以按照分?jǐn)?shù)出現(xiàn)比例為權(quán)值構(gòu)造赫夫曼數(shù)碌冶,優(yōu)化程序判斷次序
- 赫夫曼編碼
第七章 圖
1.圖的遍歷算法:
- 深度優(yōu)先算法
- 廣度優(yōu)先算法
第八章 動(dòng)態(tài)管理內(nèi)存
略
第九章 查找
1.查找算法(詳見(jiàn)https://www.cnblogs.com/yw09041432/p/5908444.html
)。平均查找長(zhǎng)度(Average Search Length贡未,ASL):需和指定key進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值,稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度蒙袍。對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表俊卤,查找成功的平均查找長(zhǎng)度為:ASL = Pi*Ci的和。Pi:查找表中第i個(gè)數(shù)據(jù)元素的概率害幅。Ci:找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過(guò)的次數(shù)消恍。
- (1)順序表查找:順序查找:
- 要求:存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)或者鏈表存儲(chǔ)
- 思想:順序依次查找
- ASL:(1/n)*(1+2+...+n)=(n+1)/2
- 時(shí)間復(fù)雜度:O(n)
- (2)二分查找、折半查找:
- 要求:有序順序存儲(chǔ)列表
- 思想:先將查找值與中間值比較以现,查找不成功折半查找區(qū)間
- ASL:log2(n+1)
- 時(shí)間復(fù)雜度:O(log2n)
- (3)插值查找:
- 要求:有序順序存儲(chǔ)列表
- 思想:基于二分查找算法狠怨,將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇(由mid=low+1/2(high-low)改為mid=low+(key-a[low])/(a[high]-a[low])(high-low),)邑遏,可以提高查找效率佣赖。
- 時(shí)間復(fù)雜度:O(log2n)
- (4)斐波那契額查找:
- 要求:有序順序存儲(chǔ)列表
- 思想:依然是對(duì)查找點(diǎn)的優(yōu)化,采用Fibonacci數(shù)組记盒,找到對(duì)于當(dāng)前長(zhǎng)度的有序表的黃金分割點(diǎn)憎蛤,作為每次的中間值。
- 時(shí)間復(fù)雜度:O(log2n)纪吮。平均性能俩檬,菲波那切查找優(yōu)于折半查找,最壞情況低于折半查找碾盟。
- (5)二叉查找樹:
- 要求:需要首先二叉查找樹(左子樹<根<右子樹)
- 思想:先對(duì)待查找的數(shù)據(jù)進(jìn)行生成樹棚辽,確保樹的左分支的值小于右分支的值,然后在就行和每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)比較大小冰肴,查找最適合的范圍
- 時(shí)間復(fù)雜度:O(log2n)屈藐,最壞O(n),原因是沒(méi)有保持平衡熙尉,形成單支樹
- (6)平衡二叉樹AVL:
- 要求:二叉查找樹的基礎(chǔ)上估盘,需要進(jìn)行樹的平衡
- 時(shí)間復(fù)雜度:一直是O(log2n)
- 此外,在此基礎(chǔ)上還有2-3樹骡尽,2-3-4樹遣妥,B+樹,紅黑樹等攀细。
2.上述算法中:
- 順序表查找:(1)
- 優(yōu)點(diǎn):簡(jiǎn)單
- 缺點(diǎn):效率低O(n)
- 有序表查找:(2)/(3)/(4)
- 優(yōu)點(diǎn):時(shí)間復(fù)雜度低O(log2n)
- 缺點(diǎn):有序表的插入和刪除性能是比較差的
第十章 第十一章 排序
1.排序算法的穩(wěn)定性:經(jīng)過(guò)排序箫踩,這些記錄的相對(duì)次序保持不變爱态,即在原序列中,ri=rj境钟,且ri在rj之前锦担,而在排序后的序列中,ri仍在rj之前慨削,則稱這種排序算法是穩(wěn)定的洞渔;否則稱為不穩(wěn)定的。例如冒泡排序是穩(wěn)定的缚态,但是如果交換條件改為a[j].key>=a[j+1].key磁椒,就是不穩(wěn)定的。
2.排序算法可以分為內(nèi)部排序和外部排序玫芦,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序浆熔,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部的排序記錄桥帆,在排序過(guò)程中需要訪問(wèn)外存医增。
3.常見(jiàn)的8種內(nèi)部排序算法有(詳見(jiàn)https://www.cnblogs.com/RainyBear/p/5258483.html
):
- 插入排序:將第一個(gè)元素看成是有序的序列,之后的元素看成是未排序的序列老虫,然后遍歷未排序的序列叶骨,將其插入到有序序列中
- 希爾排序:先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,待整個(gè)序列中的記錄“基本有序”時(shí)祈匙,再對(duì)全體記錄進(jìn)行依次直接插入排序
- 選擇排序:首先在未排序序列中找到最械巳(大)元素,存放到排序序列的起始位置菊卷。再?gòu)氖S辔磁判蛟刂欣^續(xù)尋找最械蘅摇(大)元素,然后放到已排序序列的末尾洁闰。
- 冒泡排序:比較相鄰元素歉甚,如果前面的大就交換
- 歸并排序
- 快速排序
- 堆排序
- 基數(shù)排序
第十二章 文件
略