資料結構考研重難點彙總

定義一個結構的一般形式為：

struct 結構名
{
//成員表列
};

例如

struct stu
{
    int num;
    char name[20];
    char sex;
    float score;
};

向上取整：比自己大的最小整數；

向下取整：比自己小的最大整數；

一、

1、基本資料類型

int char long float double

2、結構型(系統提供給程式員制作新的資料類型的一種機制，即可以用已經有的不同的基本資料類型或使用者定義的結構型，組合成使用者需要的負責資料類型)

typedef struct{
	int a;
	char b;
	float c;
}TypeA;//定義了一個新的資料類型，TypeA型

TypeA a[3] int a[3]

取資料時:用“.”引用：a[0].a 對比 a[0]

2、指針型

int *a //定義了一個指向整型變量的指針類比 int a

（假設a中存放了b的位址，a指向b）*a代表取b的内容

則x=*a == x=b a=&b

3、結點構造

連結清單結點定義

typedef struct Node{
	int data;
	struct Node *next;
}node;

二叉樹結點定義

typedef struct BTNode
{
	int data;
	struct BTNode *rhild;
	struct BTNode *lchild;
}BTNode; *btnode (BTNode類型指針的别名 BTNode *p=btnode p)

制作新結點：BTNode BT;

BTNode *BT;
BT=(BTNode*)malloc(sizeof(BTNode));//申請結點

動态申請數組空間：

int *p
p=(int *)malloc(n*sizeof(int));(P指向數組中第一個元素的位址)

4、函數

++x //先加再用

串定義：char str[]=”abcdef”; 以’\0’作為結束标志，數組長度=7，串長度=6。

串存儲結構：順序存儲和鍊式存儲

定長順序存儲結構體定義：

typedef struct{

char str[maxSize+1];//maxSize表示串的最大長度，數組長度定義為maxSize+1，多了一個‘\0’為結束标志

int length;

}Str;

變長存儲配置設定表示

typedef struct{

char *ch; //指向動态配置設定存儲區首位址的字元指針

int length;

}Str;

串操作：

1)StrAssign(&s,chars):将一個字元串常量賦給串s,即生成一個其值等于chars的串s。

(2) StrCopy(&s,t):串複制:将串t賦給串s。

(3) StrEqual(s,t):判串相等:若兩個串s與t相等則傳回真；否則傳回假。

(4) StrLength(s):求串長:傳回串s中字元個數。

(5)Concat(s,t):串連接配接:傳回由兩個串s和t連接配接在一起形成的新串。

(6)SubStr(s,i,j):求子串:傳回串s中從第i(1≤i≤StrLength(s))個字元開始的、由連續j個字元組成的子串。

(7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤StrLength(s)+1)個字元中,即将s2的第一個字元作為s1的第i個字元,并傳回産生的新串。

(8)DelStr(s,i,j):從串s中删去從第i(1≤i≤StrLength(s))個字元開始的長度為j的子串,并傳回産生的新串。

(9)RepStr(s,i,j,t):替換:在串s中,将第i(1≤i≤StrLength(s))個字元開始的j個字元構成的子串用串t替換,并傳回産生的新串。

(10) DispStr(s):串輸出:輸出串s的所有元素值。

1、指派操作:

2、求串長度操作

3、串比較操作

4、串連接配接

5、求子串

6、串清空

數組和廣義表

數組：存儲：行優先、列優先

一維數組A[0…n-1]存儲結構關系式：LOC(ai)=LOC(a0)+(i)L（0=<i<n）(L為每個數組元素所占存儲單元)

二維數組A[a,b]行下标、列下标範圍分别為[l1,h1][l2,h2]，存儲關系式為：

LOC(Aij)=LOC(Al1,l2)+[(i-l1)(h2-l2+1)+(j-l2)]*L//行優先存儲

假設l1和l2的值均為0，則上式變為:LOC(Aij)=LOC(A0,0)+[i*(h2+1)+j]L

LOC(Aij)=LOC(Al1,l2)+[(j-l2)(h1-l1+1)+(i-l1)]*L//列優先存儲

三維數組：LOC(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1

其中ci,di是各維的下界和上界，Vi=di-ci+1是各維元素個數，L是一個元素所占的存儲單元數。

矩陣：

矩陣的壓縮存儲：指為多個值相同的元素值配置設定一個存儲空間，對零元素不配置設定存儲空間。其目的是為了節省空間。

特殊矩陣：（對稱矩陣、三角陣、對角矩陣）

對稱矩陣;A[1…n][1…n] 存放在一維數組B[n(n+1)/2]

故元素aij在數組B中的下标k=1+2+…+（i-1）+j-1=i(i-1)/2+j-1(數組下标從0開始)

k=i(i-1)/2+j-1（當i>=j 下三角區和主對角線區）

j(j-1)/2+i-1 (當i<j 上三角區元素)

稀疏矩陣：順序存儲：三元組表示法

typedef struct{

int val;

int i,j;

}Trimat;

Trimat trimat[maxterms+1];//maxterms是已經定義的常量，定義了一個含有maxterms元素的稀疏矩陣

取值：trimat[k].val;表示取第k個元素的值

簡便寫法定義三元組

int trimat[maxterms+1][3];

trimat[k][0]表示矩陣中的元素按行優先順序的第k個非零元素的值

float trimat[maxterms+1][3];

取非零元素位置：(int)trimat[k][1];強制轉換實作取位置

鍊式存儲：鄰接表表示法和十字連結清單表示法

鄰接表表示法：将原矩陣的每一行的非零元素串連成一個連結清單，連結清單結點中有兩個分量：一個表示該結點對應的元素值和列号

十字連結清單的兩種結點定義：

普通結點定義：

typedef struct OLNode{
	int row,col;
	struct OLNode*right,*down;
	float val;
}OLNode;

typedef struct{
	OLNode *rhead,*chead;
	int m,n,k;//矩陣行數、列數以及非零結點總數
}CrossList;

廣義表

長度：

深度：括号的最大層數

表頭，表尾

存儲：頭尾連結清單存儲結構、擴充線性表存儲結構

樹和二叉樹

樹：

樹的存儲結構：1、雙親表示法2、孩子表示法3、孩子兄弟表示法

樹的先序周遊、後序周遊

森林的先序周遊、後序周遊

二叉樹的先序周遊、中序周遊

n個結點的樹中有n-1條邊，n個結點的二叉樹中有n+1個空指針

樹的性質：

1、樹中的結點數等于所有結點數的度數+1

2、度為m的樹中第i層上至多有mi-1個結點

3、高度為h的m叉樹至多有（mh-1）/(m-1)個結點

4、具有n個結點的m叉樹的最小高度為logm(n(m-1)+1)

總結點數=n0+n1+n2+…+nm

總分支數=1n1+2n2+…+m*nm

總結點數=總分支數+1

二叉樹：

由二叉樹的（後序、中序）（層次、中序）可以唯一确定一棵二叉樹（先序、後序無法确定）

對于有N個結點的二叉樹，其高度 (log2—N)

二叉樹高度最高的情況是每一個層隻有一個結點，此時高度為N

最小的情況是完全二叉樹，高度是[log2N]+1，以2為底的對數取整後+1

是以高度是[log2N]+1 到 N

鍊式存儲結構：

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;(在含有n個結點的二叉連結清單中含有n+1個空鍊域)

先序周遊：

遞歸遞歸算法周遊

void PreOrder(Bitree T){
	if(T!=NULL){
		visit(T);//通路根結點
		PreOrder(T->lchild);//遞歸周遊左子樹
		PreOrder(T->rchild);//遞歸周遊右子樹
	}
}

中序周遊：

void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

中序周遊非遞歸算法：

void InOrder2(BiTree T){
InitStack(S);BiTree p=T;
	while(p||！IsEmpty(p)){
		if(p){
			Push(S,p);
			p=p->lchild;
		}
		else {
			Pop(S,p);visit(p);
			p=p->rchild;
		}
	}
}

後序周遊

void PostOrder(BiTree T){
	if（T！=NULL）{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

三種算法時間複雜度均為O(n)

最壞情況下空間複雜度為0（n）

層次周遊：

void LevelOrder(BiTree T){//借助隊列
InitQueue(Q);//初始化
BiTree p;
EnQueue(Q,T);//入隊
while(!IsEmpty(Q)){
	DeQueue(Q,p);
	visit(p);
	if(p->lchild!=NULL)
		EnQueue(Q,p->lchild);
	if(p->rchild!=NULL)
		EnQueue(Q,p->rchild);
}
}

圖

度：與頂點v相關的邊數稱為頂點v的度

有向圖：有n個頂點，則最多有n(n-1)條邊------有向完全圖

無向圖：有n個頂點，最多有n(n-1)/2條邊-----無向完全圖

無向圖中的極大連通子圖稱為連通分量（極大連通子圖：是無向圖的連通分量，極大要求即要求該連通子圖其所有的邊，極小連通子圖：是既要保持圖連通，又要使得邊數最少的子圖）

有向圖中的任何一對頂點都是強連通的，則稱此圖為強連通圖，有向圖中的極大強連通子圖稱為有向圖的強連通分量

存儲方式：鄰接矩陣和鄰接表

鄰接矩陣：圖的順序存儲結構

具有n個頂點的圖，頂點序号是0，1，，n-1；n階方陣A

A[i][j]=1表示頂點i與頂點j鄰接

A[i][j]=0表示頂點i與頂點j不鄰接

無向圖：1的個數為圖中總邊數的2倍，矩陣中第i列或第i列的元素之和=頂點i的度

有向圖：1的個數為圖的邊數，矩陣中第i行的元素之和=頂點i的出度，第j列元素之和=頂點j的入度

有向有權圖：有邊存在，則把無權圖的1改為權值，若無邊存在，則把0改為∞。

#define MaxVertexNum 100;  //頂點數目最大值
typedef char VertexType;//頂點的資料類型
typedef int EdgeType;//帶權圖中邊上權值的資料類型
typedef struct{
	VertexType Vex[MaxVertexNum];//頂點表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];//鄰接矩陣，邊表
	int vexnum,arcnum;//圖的目前頂點數和弧數
}MGraph;

例如：

void f(MGraph G){
	int a=G.n;
	int b=G.e;
}

排序：

插入：直接插入排序、折半插入排序、希爾排序

交換：冒泡排序、快速排序

選擇：簡單選擇排序、堆排序

歸并類排序、基數排序

經過一趟排序，能夠保證一個關鍵字到達最終位置，這樣的排序是交換類排序（冒泡、快速）和選擇（簡單選擇、堆）

查找：

順序查找：

折半查找：

分塊查找：

二叉排序樹

二叉平衡樹

散清單:根據給定關鍵字依照函數h查找關鍵字key在表中的位址，把key存在這個位址上

散列函數的構造方法：直接定位址法（不會發生沖突）、除留餘數法

解決沖突的方法：開放定址法：線性探測法

拉鍊法

資料結構考研重難點彙總

繼續閱讀

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

shell排序基本思想及其複雜度分析

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器