棧

初始化

#define MaxSize 50//棧中元素的最大個(gè)數(shù)
typedef char ElemType;//數(shù)據(jù)結(jié)構(gòu)
typedef struct{int top;//棧頂指針ElemType data[MaxSize];//存放棧中的元素
}SqStack;//初始化棧，給top賦值為-1
void InitStack(SqStack *stack){stack->top = -1;
}

---

判斷是否為空

//判斷棧是否為空,空返回true，反之即返回false
bool StackEmpty(SqStack stack){if(stack.top==-1) return true;return false;
}

---

進(jìn)棧

//進(jìn)棧
bool Push(SqStack *stack,ElemType e){//判斷是否滿棧if(stack->top==MaxSize-1) return false;//指針先加1，再入棧stack->data[++stack->top]=e;return true;
}

---

出棧

//出棧
ElemType Pop(SqStack *stack){//判斷是否為空棧if(stack->top==-1) return false;//先取值，再自減return stack->data[stack->top--];
}

---

讀取棧頂元素

//讀取棧頂元素
ElemType GetTop(SqStack stack){//判斷是否為空棧if(stack.top==-1) return false;return stack.data[stack.top];
}

---

隊(duì)列

初始化

#define MaxSize 5
typedef char ElemType;typedef struct 
{ElemType data[MaxSize];int rear,front;
}SqQueue;//初始化
void InitQueue(SqQueue *queue){queue->front = queue->rear=0;
}

---

判斷空

//判斷是否為空，即判斷首尾指針是否相等
bool QueueEmpty(SqQueue queue){if(queue.front==queue.rear) return true;return false;
}

---

入隊(duì)

//入隊(duì)
bool EnQueue(SqQueue *queue,ElemType e){//判斷是否是滿隊(duì)，即尾指針的下一個(gè)指向首指針if((queue->rear+1)%MaxSize==queue->front) return false;queue->data[queue->rear]=e;//賦值//尾指針+1取模queue->rear = (queue->rear+1)%MaxSize;return true;
}

---

出隊(duì)

//出隊(duì)
ElemType DeQueue(SqQueue *queue){//判斷是否為空if(queue->front==queue->rear) return false;//先取值，首指針再+1取模ElemType e = queue->data[queue->front];queue->front++;return e;
}

---

數(shù)組

提到數(shù)組，大家首先會(huì)想到的是：很多編程語(yǔ)言中都提供有數(shù)組這種數(shù)據(jù)類型，比如 C/C++、Java、Go、C# 等。但本節(jié)我要講解的不是作為數(shù)據(jù)類型的數(shù)組，而是數(shù)據(jù)結(jié)構(gòu)中提供的一種叫數(shù)組的存儲(chǔ)結(jié)構(gòu)。

和線性存儲(chǔ)結(jié)構(gòu)相比，數(shù)組最大的不同是：它存儲(chǔ)的數(shù)據(jù)可以包含多種“一對(duì)一”的邏輯關(guān)系。舉個(gè)簡(jiǎn)單的例子：

上圖中，{a1, a2, a3, a4}、{b1, b2, b3, b4}、{c1, c2, c3, c4}、{d1, d2, d3, d4} 中各自包含的元素具有“一對(duì)一”的邏輯關(guān)系，同時(shí) a、b、c、d 這 4 個(gè)序列也具有“一對(duì)一”的邏輯關(guān)系。

這樣存儲(chǔ)不止一種“一對(duì)一”邏輯關(guān)系的數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)就推薦使用數(shù)組存儲(chǔ)結(jié)構(gòu)。

---

對(duì)于數(shù)組存儲(chǔ)結(jié)構(gòu)，我們可以這樣理解它：數(shù)組是對(duì)線性表的擴(kuò)展，是一種“特殊”的線性存儲(chǔ)結(jié)構(gòu)，用來(lái)存儲(chǔ)具有多種“一對(duì)一”邏輯關(guān)系的數(shù)據(jù)。

實(shí)際場(chǎng)景中，存儲(chǔ)具有 N 種“一對(duì)一”邏輯關(guān)系的數(shù)據(jù)，通常會(huì)建立 N 維數(shù)組：

• 一維數(shù)組和其它線性存儲(chǔ)結(jié)構(gòu)很類似，用來(lái)存儲(chǔ)只有一種“一對(duì)一”邏輯關(guān)系的數(shù)據(jù)：

• 二維數(shù)組用來(lái)存儲(chǔ)包含兩種“一對(duì)一”邏輯關(guān)系的數(shù)據(jù)。二維數(shù)組可以看作是存儲(chǔ)一維數(shù)組的一維數(shù)組
  
• n 維數(shù)組用來(lái)存儲(chǔ)包含 n 種“一對(duì)一”邏輯關(guān)系的數(shù)據(jù)，可以看作是存儲(chǔ) n-1 維數(shù)組的一維數(shù)組；

---

數(shù)組存儲(chǔ)結(jié)構(gòu)還具有一些其它的特性，包括：

• 無(wú)論數(shù)組的維度是多少，數(shù)組中的數(shù)據(jù)類型都必須一致；
• 數(shù)組一旦建立，它的維度將不再改變；
• 數(shù)組存儲(chǔ)結(jié)構(gòu)不會(huì)對(duì)內(nèi)部的元素做插入和刪除操作，常見的操作有 4 種，分別是初始化數(shù)組、銷毀數(shù)組、取數(shù)組中的元素和修改數(shù)組中的元素。

---

數(shù)組的順序表示和實(shí)現(xiàn)

數(shù)組可以是多維的，而順序表只能是一維的線性空間。要想將 N 維的數(shù)組存儲(chǔ)到順序表中，可以采用以下兩種方案：

• 以列序?yàn)橹?#xff08;先列后行）：按照行號(hào)從小到大的順序，依次存儲(chǔ)每一列的元素；
• 以行序?yàn)橹?#xff08;先行后序）：按照列號(hào)從小到大的順序，依次存儲(chǔ)每一行的元素。

多維數(shù)組中，最常用的是二維數(shù)組，接下里就以二維數(shù)組為例，講解數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。

所示的二維數(shù)組按照“列序?yàn)橹鳌钡姆桨复鎯?chǔ)時(shí)，數(shù)組中的元素在順序表中的存儲(chǔ)狀態(tài)如下圖所示：

同樣的道理，按照“行序?yàn)橹鳌钡姆桨复鎯?chǔ)數(shù)組時(shí)，各個(gè)元素在順序表中的存儲(chǔ)狀態(tài)如圖

---

順序表中查找和修改數(shù)組元素

注意，只有在順序表內(nèi)查找到數(shù)組中的目標(biāo)元素之后，才能對(duì)該元素執(zhí)行讀取和修改操作。

在 N 維數(shù)組中查找目標(biāo)元素，需知道以下信息：

• 數(shù)組的存儲(chǔ)方式；
• 數(shù)組在內(nèi)存中存放的起始地址；
• 目標(biāo)元素在數(shù)組中的坐標(biāo)。比如說(shuō)，二維數(shù)組中是通過(guò)行標(biāo)和列標(biāo)來(lái)確定元素位置的；
• 數(shù)組中元素的類型，即數(shù)組中單個(gè)數(shù)據(jù)元素所占內(nèi)存的大小，通常用字母 L 表示；

根據(jù)存儲(chǔ)方式的不同，查找目標(biāo)元素的方式也不同。仍以二維數(shù)組為例，如果數(shù)組采用“行序?yàn)橹鳌钡拇鎯?chǔ)方式，則在二維數(shù)組 anm 中查找 aij 位置的公式為：

LOC(i, j) = LOC(0, 0) + (i * m + j) * L;

其中，LOC(i, j) 為 aij 在內(nèi)存中的地址，LOC(0, 0) 為二維數(shù)組在內(nèi)存中存放的起始位置（也就是 a00 的位置）。

而如果采用以列存儲(chǔ)的方式，在 anm 中查找 aij 的方式為：

LOC(i, j) = LOC(0, 0) + (j * n + i) * L;

根據(jù)以上兩個(gè)公式，就可以在順序表中找到目標(biāo)元素，自然也就可以進(jìn)行讀取和修改操作了。

---

代碼實(shí)現(xiàn)

#include<stdarg.h>
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3
#define UNDERFLOW 4
typedef int Status; //Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
typedef int Boolean; //Boolean是布爾類型,其值是TRUE或FALSE
typedef int ElemType;#define MAX_ARRAY_DIM 8 //假設(shè)數(shù)組維數(shù)的最大值為8
typedef struct
{ElemType* base; //數(shù)組元素基址，由InitArray分配int dim; //數(shù)組維數(shù)int* bounds; //數(shù)組維界基址，由InitArray分配int* constants; // 數(shù)組映象函數(shù)常量基址，由InitArray分配
} Array;Status InitArray(Array* A, int dim, ...)
{//若維數(shù)dim和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OKint elemtotal = 1, i; // elemtotal是元素總值va_list ap;if (dim<1 || dim>MAX_ARRAY_DIM)return ERROR;(*A).dim = dim;(*A).bounds = (int*)malloc(dim * sizeof(int));if (!(*A).bounds)exit(OVERFLOW);va_start(ap, dim);for (i = 0; i < dim; ++i){(*A).bounds[i] = va_arg(ap, int);if ((*A).bounds[i] < 0)return UNDERFLOW;elemtotal *= (*A).bounds[i];}va_end(ap);(*A).base = (ElemType*)malloc(elemtotal * sizeof(ElemType));if (!(*A).base)exit(OVERFLOW);(*A).constants = (int*)malloc(dim * sizeof(int));if (!(*A).constants)exit(OVERFLOW);(*A).constants[dim - 1] = 1;for (i = dim - 2; i >= 0; --i)(*A).constants[i] = (*A).bounds[i + 1] * (*A).constants[i + 1];return OK;
}Status DestroyArray(Array* A)
{//銷毀數(shù)組Aif ((*A).base){free((*A).base);(*A).base = NULL;}elsereturn ERROR;if ((*A).bounds){free((*A).bounds);(*A).bounds = NULL;}elsereturn ERROR;if ((*A).constants){free((*A).constants);(*A).constants = NULL;}elsereturn ERROR;return OK;
}Status Locate(Array A, va_list ap, int* off) // Value()、Assign()調(diào)用此函數(shù) */
{//若ap指示的各下標(biāo)值合法，則求出該元素在A中的相對(duì)地址offint i, ind;*off = 0;for (i = 0; i < A.dim; i++){ind = va_arg(ap, int);if (ind < 0 || ind >= A.bounds[i])return OVERFLOW;*off += A.constants[i] * ind;}return OK;
}Status Value(ElemType* e, Array A, ...) //在VC++中，...之前的形參不能是引用類型
{//依次為各維的下標(biāo)值，若各下標(biāo)合法，則e被賦值為A的相應(yīng)的元素值va_list ap;Status result;int off;va_start(ap, A);if ((result = Locate(A, ap, &off)) == OVERFLOW) //調(diào)用Locate()return result;*e = *(A.base + off);return OK;
}Status Assign(Array* A, ElemType e, ...)
{//依次為各維的下標(biāo)值，若各下標(biāo)合法，則將e的值賦給A的指定的元素va_list ap;Status result;int off;va_start(ap, e);if ((result = Locate(*A, ap, &off)) == OVERFLOW) //調(diào)用Locate()return result;*((*A).base + off) = e;return OK;
}int main()
{Array A;int i, j, k, * p, dim = 3, bound1 = 3, bound2 = 4, bound3 = 2; //a[3][4][2]數(shù)組ElemType e, * p1;InitArray(&A, dim, bound1, bound2, bound3); //構(gòu)造3＊4＊2的3維數(shù)組Ap = A.bounds;printf("A.bounds=");for (i = 0; i < dim; i++) //順序輸出A.boundsprintf("%d ", *(p + i));p = A.constants;printf("\nA.constants=");for (i = 0; i < dim; i++) //順序輸出A.constantsprintf("%d ", *(p + i));printf("\n%d頁(yè)%d行%d列矩陣元素如下:\n", bound1, bound2, bound3);for (i = 0; i < bound1; i++){for (j = 0; j < bound2; j++){for (k = 0; k < bound3; k++){Assign(&A, i * 100 + j * 10 + k, i, j, k); // 將i*100+j*10+k賦值給A[i][j][k]Value(&e, A, i, j, k); //將A[i][j][k]的值賦給eprintf("A[%d][%d][%d]=%2d ", i, j, k, e); //輸出A[i][j][k]}printf("\n");}printf("\n");}p1 = A.base;printf("A.base=\n");for (i = 0; i < bound1 * bound2 * bound3; i++) //順序輸出A.base{printf("%4d", *(p1 + i));if (i % (bound2 * bound3) == bound2 * bound3 - 1)printf("\n");}DestroyArray(&A);return 0;
}

矩陣的壓縮存儲(chǔ)

特殊矩陣

這里所說(shuō)的特殊矩陣，主要分為以下兩類：

• 含有大量相同數(shù)據(jù)元素的矩陣，比如對(duì)稱矩陣；
• 含有大量 0 元素的矩陣，比如稀疏矩陣、上（下）三角矩陣；

針對(duì)以上兩類矩陣，數(shù)據(jù)結(jié)構(gòu)的壓縮存儲(chǔ)思想是：矩陣中的相同數(shù)據(jù)元素（包括元素 0）只存儲(chǔ)一個(gè)

數(shù)據(jù)元素沿主對(duì)角線對(duì)應(yīng)相等，這類矩陣稱為對(duì)稱矩陣，矩陣中有兩條對(duì)角線，對(duì)角線稱為主對(duì)角線，另一條從左下角到右上角的對(duì)角線為副對(duì)角線。對(duì)稱矩陣指的是各數(shù)據(jù)元素沿主對(duì)角線對(duì)稱的矩陣。

對(duì)稱矩陣的實(shí)現(xiàn)過(guò)程是，若存儲(chǔ)下三角中的元素，只需將各元素所在的行標(biāo) i 和列標(biāo) j 代入下面的公式：

存儲(chǔ)上三角的元素要將各元素的行標(biāo) i 和列標(biāo) j 代入另一個(gè)公式：

最終求得的 k 值即為該元素存儲(chǔ)到數(shù)組中的位置（矩陣中元素的行標(biāo)和列標(biāo)都從 1 開始）。

例如，在數(shù)組 skr[6] 中存儲(chǔ)圖 1 中的對(duì)稱矩陣，則矩陣的壓縮存儲(chǔ)狀態(tài)如圖所示（存儲(chǔ)上三角和下三角的結(jié)果相同）：

注意，以上兩個(gè)公式既是用來(lái)存儲(chǔ)矩陣中元素的，也用來(lái)從數(shù)組中提取矩陣相應(yīng)位置的元素。例如，如果想從圖中的數(shù)組提取矩陣中位于 (3,1) 處的元素，由于該元素位于下三角，需用下三角公式獲取元素在數(shù)組中的位置，即：

---

稀疏矩陣

如果矩陣中分布有大量的元素 0，即非 0 元素非常少，這類矩陣稱為稀疏矩陣。

壓縮存儲(chǔ)稀疏矩陣的方法是：只存儲(chǔ)矩陣中的非 0 元素，與前面的存儲(chǔ)方法不同，稀疏矩陣非 0 元素的存儲(chǔ)需同時(shí)存儲(chǔ)該元素所在矩陣中的行標(biāo)和列標(biāo)。

例如，存儲(chǔ)上圖中的稀疏矩陣，需存儲(chǔ)以下信息：

• (1,1,1)：數(shù)據(jù)元素為 1，在矩陣中的位置為 (1,1)；
• (3,3,1)：數(shù)據(jù)元素為 3，在矩陣中的位置為 (3,1)；
• (5,2,3)：數(shù)據(jù)元素為 5，在矩陣中的位置為 (2,3)；
• 除此之外，還要存儲(chǔ)矩陣的行數(shù) 3 和列數(shù) 3；

---

**若對(duì)其進(jìn)行壓縮存儲(chǔ)，矩陣中各非 0 元素的存儲(chǔ)狀態(tài)如圖 **

三元組的結(jié)構(gòu)體

//三元組結(jié)構(gòu)體
typedef struct {int i,j;//行標(biāo)i，列標(biāo)jint data;//元素值
}triple;

由于稀疏矩陣中非 0 元素有多個(gè)，因此需要建立 triple 數(shù)組存儲(chǔ)各個(gè)元素的三元組。除此之外，考慮到還要存儲(chǔ)矩陣的總行數(shù)和總列數(shù)，因此可以采用以下結(jié)構(gòu)表示整個(gè)稀疏矩陣：

#define number 20
//矩陣的結(jié)構(gòu)表示
typedef struct {triple data[number];//存儲(chǔ)該矩陣中所有非0元素的三元組int mu, nu, tu;//mu和nu分別記錄矩陣的行數(shù)和列數(shù)，tu記錄矩陣中所有的非0元素的個(gè)數(shù)
}TSMatrix;

#include<stdio.h>
#define NUM 3
//存儲(chǔ)三元組的結(jié)構(gòu)體
typedef struct {int i, j;int data;
}triple;
//存儲(chǔ)稀疏矩陣的結(jié)構(gòu)體
typedef struct {triple data[NUM];int mu, nu, tu;
}TSMatrix;
//輸出存儲(chǔ)的稀疏矩陣
void display(TSMatrix M);
int main() {TSMatrix M;M.mu = 3;M.nu = 3;M.tu = 3;M.data[0].i = 1;M.data[0].j = 1;M.data[0].data = 1;M.data[1].i = 2;M.data[1].j = 3;M.data[1].data = 5;M.data[2].i = 3;M.data[2].j = 1;M.data[2].data = 3;display(M);return 0;
}
void display(TSMatrix M) {int i, j, k;for (i = 1; i <= M.mu; i++) {for (j = 1; j <= M.nu; j++) {int value = 0;for (k = 0; k < M.tu; k++) {if (i == M.data[k].i && j == M.data[k].j) {printf("%d ", M.data[k].data);value = 1;break;}}if (value == 0)printf("0 ");}printf("\n");}
}

---