1.線性表

線性表（英語：Linear List）是由n（n≥0）個元素（）a[0]，a[1]，a[2]…，a[n-1]組成的。

其中：

• 數據元素的個數n定義為表的長度 = “list”.length() （”list”.length() = 0（表裡沒有一個元素）時稱為空表）
• 將非空的線性表（n>=1）記作：（a[0]，a[1]，a[2]，…，a[n-1]）
• 數據元素a[i]（0≤i≤n-1）只是個抽象符號，其具體含義在不同情況下可以不同

一個數據元素可以由若干個數據項組成。數據元素稱為記錄，含有大量記錄的線性表又稱為文件。這種結構具有下列特點：存在一個唯一的沒有前驅的（頭）數據元素；存在一個唯一的沒有後繼的（尾）數據元素；此外，每一個數據元素均有一個直接前驅和一個直接後繼數據元素。

2.線性表的存儲結構

• 鏈表
  • 單鏈表
    • 動態單鏈表
    • 靜態單鏈表
  • 循環鏈表
    • 單循環鏈表
    • 雙循環鏈表
  • 靜態鏈表

3.順序表

利用數組的連續存儲空間順序存放線性表的各元素

3.1結構體定義

如果需要使用自定義的結構體來維護一個順序表，通常來講結構體的元素一般是一個固定大小的數組（可用長度足夠大），以及當前數組存放的元素個數，也即數組的長度

typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    int Last;//記錄順序表的最後一個元素的下標
} ;
struct LNode L;
List PtrL;

訪問結構體的成員

• 訪問下標為 i 的元素：L.Data[i] 或 PtrL->Data[i]
• 線性表的長度：L.Last+1 或 PtrL->Last+1
• 指針變量PtrL還可以這樣訪問兩個屬性(*PtrL).Data[i]和(*PtrL).Last，不過這種訪問方式並不常用

而一般來講，為了簡單，不會去維護這樣一個結構體，(因為一旦維護了這個結構體，就需要去封裝相應的函數，比如說常見的插入、刪除、查找等操作)，而是直接類似下面這樣

ElementType data[MaxSize];
int length;

定義一個足夠大的數組，然後定義一個對應關聯的變量來時刻維護數組的長度。

這兩種定義方式沒有什麼區別，一種是把常用操作封裝好，方便調用，另一種則是需要時刻自己維護對應的屬性。因為順序表的結構足夠簡單，所以不定義結構體也是可以的。

3.2順序表的常見操作

為了方便，這一節內容記錄的都是在定義的結構體基礎上，封裝的常見操作。

1.初始化

List MakeEmpty( ) {
    List PtrL;
    PtrL = (List )malloc( sizeof(struct LNode) );
    PtrL->Last = -1;
    return PtrL;
}

初始化的順序表，長度為0，所以Last為-1

2.查找

int Find( ElementType X, List PtrL ) {
    int i = 0;
    while( i <= PtrL->Last && PtrL->Data[i]!= X )
        i++;
    if (i > PtrL->Last) return -1; /* 如果沒找到，返回-1 */
    else return i; /* 找到后返回的是存儲位置 */
}

查找操作比較簡單，從順序表的第一個元素（下標為0開始）開始遍歷。

還有一種更加巧妙一點的實現方式，就是引入哨兵思想。

int Find( ElementType X, List PtrL ) {
    PtrL->Data[0] = x;//順序表第一個元素就是哨兵，賦值為x
    int i = PtrL->Last;//從最後一個元素開始遍歷
    while( PtrL->Data[i]!= X )
        i--;
    return i;
}

這樣做的好處很明顯，少了邊界的判斷，可以優化時間複雜度，編碼也更加簡單。

注意：這裏把下標為0的元素設置為哨兵，則要求順序表從下標為1開始存儲。而且，函數如果沒有找到，則一定返回i=0

3.插入

看圖示應該要注意，移動的方向是從后往前移，如果從前往後移，則Data[i]=Data[i+1]=…=Data[n]，因為後面的元素都被前面移過來的元素給覆蓋了。

void Insert( ElementType X, int i, List PtrL ) {
    int j;
    if ( PtrL->Last == MAXSIZE-1 ) { /* 表空間已滿，不能插入*/
        printf(＂表滿＂);
        return;
    }
    if ( i < 1 || i > PtrL->Last+2) { /*檢查插入位置的合法性*/
        printf(＂位置不合法＂);
        return;
    }
    for ( j = PtrL->Last; j >= i-1; j-- )
        PtrL->Data[j+1] = PtrL->Data[j]; /*將 ai～ an倒序向後移動*/
    PtrL->Data[i-1] = X; /*新元素插入*/
    PtrL->Last++; /*Last仍指向最後元素*/
    return;
}

為什麼這裏需要判斷順序表的空間是否已滿？

因為這個數組，是在初始化之後就固定了數組可容納的元素個數MaxSize，一旦超出，則程序下標就會越界。C++提供了動態數組vector，可以很方便的支持動態擴展數組長度，而且基本的插入刪除等操作都封裝好了，可以很方便的使用。

4.刪除

同樣的，需要注意元素移動的方向，如果從后往前移，則最後面的元素會一直覆蓋到Data[i]。

void Delete( int i, List PtrL ) {
    int j;
    if( i < 1 || i > PtrL->Last+1 ) { /*檢查空表及刪除位置的合法性*/
        printf (“不存在第%d個元素”, i );
        return ;
    }
    for ( j = i; j <= PtrL->Last; j++ )
        PtrL->Data[j-1] = PtrL->Data[j]; /*將 ai+1～ an順序向前移動*/
    PtrL->Last--; /*Last仍指向最後元素*/
    return;
}

5.排序

因為排序算法比較多，本文不展開講解，可以參考以下博文，內容包括了常見的十大排序算法的算法分析，時間複雜度和空間複雜度分析以及c實現和動圖圖解。

4.鏈表

不要求邏輯上相鄰的兩個元素物理上也相鄰；通過“鏈”建立起數據元素之間的邏輯關係。插入、刪除不需要移動數據元素，只需要修改“鏈”。

4.1單鏈表

typedef struct LNode *List;
struct LNode {
    ElementType Data;
    List Next;
};
struct Lnode L;
List PtrL;

1.求表長

int Length ( List PtrL ) {
    List p = PtrL; /* p指向表的第一個結點*/
    int j = 0;
    while ( p ) {
        p = p->Next;
        j++; /* 當前p指向的是第 j 個結點*/
    }
    return j;
}

時間複雜度O(n)

2.查找

按序查找

List FindKth( int K, List PtrL ) {
    List p = PtrL;
    int i = 1;
    while (p !=NULL && i < K ) {
        p = p->Next;
        i++;
    }
    if ( i == K ) return p;
    /* 找到第K個，返回指針 */
    else return NULL;
    /* 否則返回空 */
}

時間複雜度O(n)

按值查找

List Find( ElementType X, List PtrL ) {
    List p = PtrL;
    while ( p!=NULL && p->Data != X )
        p = p->Next;
    return p;
}

時間複雜度O(n)

3.插入

（1）先構造一個新結點，用s指向；
（2）再找到鏈表的第 i-1個結點，用p指向；
（3）然後修改指針，插入結點 ( p之後插入新結點是 s)

List Insert( ElementType X, int i, List PtrL ) {
    List p, s;
    if ( i == 1 ) { /* 新結點插入在表頭 */
        s = (List)malloc(sizeof(struct LNode)); /*申請、填裝結點*/
        s->Data = X;
        s->Next = PtrL;
        return s; /*返回新表頭指針*/
    }
    p = FindKth( i-1, PtrL ); /* 查找第i-1個結點 */
    if ( p == NULL ) { /* 第i-1個不存在，不能插入 */
        printf("參數i錯");
        return NULL;
    } else {
        s = (List)malloc(sizeof(struct LNode)); /*申請、填裝結點*/
        s->Data = X;
        s->Next = p->Next; /*新結點插入在第i-1個結點的後面*/
        p->Next = s;
        return PtrL;
    }
}

4.刪除

（1）先找到鏈表的第 i-1個結點，用p指向；
（2）再用指針s指向要被刪除的結點（p的下一個結點）;
（3）然後修改指針，刪除s所指結點;
（4）最後釋放s所指結點的空間。

List Delete( int i, List PtrL ) {
    List p, s;
    if ( i == 1 ) { /* 若要刪除的是表的第一個結點 */
        s = PtrL; /*s指向第1個結點*/
        if (PtrL!=NULL) PtrL = PtrL->Next; /*從鏈表中刪除*/
        else return NULL;
        free(s); /*釋放被刪除結點 */
        return PtrL;
    }
    p = FindKth( i-1, PtrL ); /*查找第i-1個結點*/
    if ( p == NULL ) {
        printf("第%d個結點不存在", i-1);
        return NULL;
    } else if ( p->Next == NULL ) {
        printf("第%d個結點不存在", i);
        return NULL;
    } else {
        s = p->Next; /*s指向第i個結點*/
        p->Next = s->Next; /*從鏈表中刪除*/
        free(s); /*釋放被刪除結點 */
        return PtrL;
    }
}

4.2雙鏈表

雙向鏈表，又稱為雙鏈表，是的一種，它的每個數據結點中都有兩個，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。

typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

4.3循環鏈表

4.3.1單循環鏈表

存儲結構和單鏈表相同。

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

// 設立尾指針的單循環鏈表的12個基本操作
void InitList(LinkList *L) { // 操作結果：構造一個空的線性表L
    *L = (LinkList)malloc(sizeof(struct LNode)); // 產生頭結點，並使L指向此頭結點
    if (!*L) // 存儲分配失敗
        exit(OVERFLOW);
    (*L)->next = *L; // 指針域指向頭結點
}

void DestroyList(LinkList *L) { // 操作結果：銷毀線性表L
    LinkList q, p = (*L)->next; // p指向頭結點
    while (p != *L) { // 沒到表尾
        q = p->next;
        free(p);
        p = q;
    }
    free(*L);
    *L = NULL;
}

void ClearList(LinkList *L) /* 改變L */ { // 初始條件：線性表L已存在。操作結果：將L重置為空表
    LinkList p, q;
    *L = (*L)->next; // L指向頭結點
    p = (*L)->next; // p指向第一個結點
    while (p != *L) { // 沒到表尾
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = *L; // 頭結點指針域指向自身
}

Status ListEmpty(LinkList L) { // 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE
    if (L->next == L) // 空
        return TRUE;
    else
        return FALSE;
}

int ListLength(LinkList L) { // 初始條件：L已存在。操作結果：返回L中數據元素個數
    int i = 0;
    LinkList p = L->next; // p指向頭結點
    while (p != L) { // 沒到表尾
        i++;
        p = p->next;
    }
    return i;
}

Status GetElem(LinkList L, int i, ElemType *e) { // 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR
    int j = 1; // 初始化，j為計數器
    LinkList p = L->next->next; // p指向第一個結點
    if (i <= 0 || i > ListLength(L)) // 第i個元素不存在
        return ERROR;
    while (j < i) { // 順指針向後查找，直到p指向第i個元素
        p = p->next;
        j++;
    }
    *e = p->data; // 取第i個元素
    return OK;
}

int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 初始條件：線性表L已存在，compare()是數據元素判定函數
    // 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。
    //           若這樣的數據元素不存在，則返回值為0
    int i = 0;
    LinkList p = L->next->next; // p指向第一個結點
    while (p != L->next) {
        i++;
        if (compare(p->data, e)) // 滿足關係
            return i;
        p = p->next;
    }
    return 0;
}

Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e) { // 初始條件：線性表L已存在
    // 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，
    //           否則操作失敗，pre_e無定義
    LinkList q, p = L->next->next; // p指向第一個結點
    q = p->next;
    while (q != L->next) { // p沒到表尾
        if (q->data == cur_e) {
            *pre_e = p->data;
            return TRUE;
        }
        p = q;
        q = q->next;
    }
    return FALSE; // 操作失敗
}

Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { // 初始條件：線性表L已存在
    // 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
    //           否則操作失敗，next_e無定義
    LinkList p = L->next->next; // p指向第一個結點
    while (p != L) { // p沒到表尾
        if (p->data == cur_e) {
            *next_e = p->next->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE; // 操作失敗
}

Status ListInsert(LinkList *L, int i, ElemType e) /* 改變L */ { // 在L的第i個位置之前插入元素e
    LinkList p = (*L)->next, s; // p指向頭結點
    int j = 0;
    if (i <= 0 || i > ListLength(*L) + 1) // 無法在第i個元素之前插入
        return ERROR;
    while (j < i - 1) { // 尋找第i-1個結點
        p = p->next;
        j++;
    }
    s = (LinkList)malloc(sizeof(struct LNode)); // 生成新結點
    s->data = e; // 插入L中
    s->next = p->next;
    p->next = s;
    if (p == *L) // 改變尾結點
        *L = s;
    return OK;
}

Status ListDelete(LinkList *L, int i, ElemType *e) /* 改變L */ { // 刪除L的第i個元素，並由e返回其值
    LinkList p = (*L)->next, q; // p指向頭結點
    int j = 0;
    if (i <= 0 || i > ListLength(*L)) // 第i個元素不存在
        return ERROR;
    while (j < i - 1) { // 尋找第i-1個結點
        p = p->next;
        j++;
    }
    q = p->next; // q指向待刪除結點
    p->next = q->next;
    *e = q->data;
    if (*L == q) // 刪除的是表尾元素
        *L = p;
    free(q); // 釋放待刪除結點
    return OK;
}

void ListTraverse(LinkList L, void(*vi)(ElemType)) { // 初始條件：L已存在。操作結果：依次對L的每個數據元素調用函數vi()
    LinkList p = L->next->next; // p指向首元結點
    while (p != L->next) { // p不指向頭結點
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}

4.3.2雙循環鏈表

// 線性表的雙向鏈表存儲結構
typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

// 帶頭結點的雙向循環鏈表的基本操作(14個)
void InitList(DuLinkList *L) {
    // 產生空的雙向循環鏈表L
    *L = (DuLinkList)malloc(sizeof(DuLNode));
    if (*L)
        (*L)->next = (*L)->prior = *L;
    else
        exit(OVERFLOW);
}

void DestroyList(DuLinkList *L) {
    // 操作結果：銷毀雙向循環鏈表L
    DuLinkList q, p = (*L)->next; // p指向第一個結點
    while (p != *L) { // p沒到表頭
        q = p->next;
        free(p);
        p = q;
    }
    free(*L);
    *L = NULL;
}

void ClearList(DuLinkList L) { // 不改變L
    // 初始條件：L已存在。操作結果：將L重置為空表
    DuLinkList q, p = L->next; // p指向第一個結點
    while (p != L) { // p沒到表頭
        q = p->next;
        free(p);
        p = q;
    }
    L->next = L->prior = L; // 頭結點的兩個指針域均指向自身
}

Status ListEmpty(DuLinkList L) {
    // 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE
    if (L->next == L && L->prior == L)
        return TRUE;
    else
        return FALSE;
}

int ListLength(DuLinkList L) {
    // 初始條件：L已存在。操作結果：返回L中數據元素個數
    int i = 0;
    DuLinkList p = L->next; // p指向第一個結點
    while (p != L) { // p沒到表頭
        i++;
        p = p->next;
    }
    return i;
}

Status GetElem(DuLinkList L, int i, ElemType *e) {
    // 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR
    int j = 1; // j為計數器
    DuLinkList p = L->next; // p指向第一個結點
    while (p != L && j < i) { // 順指針向後查找，直到p指向第i個元素或p指向頭結點
        p = p->next;
        j++;
    }
    if (p == L || j > i) // 第i個元素不存在
        return ERROR;
    *e = p->data; // 取第i個元素
    return OK;
}

int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
    // 初始條件：L已存在，compare()是數據元素判定函數
    // 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。
    // 若這樣的數據元素不存在，則返回值為0
    int i = 0;
    DuLinkList p = L->next; // p指向第1個元素
    while (p != L) {
        i++;
        if (compare(p->data, e)) // 找到這樣的數據元素
            return i;
        p = p->next;
    }
    return 0;
}

Status PriorElem(DuLinkList L, ElemType cur_e, ElemType *pre_e) {
    // 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，
    // 否則操作失敗，pre_e無定義
    DuLinkList p = L->next->next; // p指向第2個元素
    while (p != L) { // p沒到表頭
        if (p->data == cur_e) {
            *pre_e = p->prior->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE;
}

Status NextElem(DuLinkList L, ElemType cur_e, ElemType *next_e) {
    // 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
    // 否則操作失敗，next_e無定義
    DuLinkList p = L->next->next; // p指向第2個元素
    while (p != L) { // p沒到表頭
        if (p->prior->data == cur_e) {
            *next_e = p->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE;
}

DuLinkList GetElemP(DuLinkList L, int i) { // 另加
    // 在雙向鏈表L中返回第i個元素的地址。i為0，返回頭結點的地址。若第i個元素不存在，
    // 返回NULL
    int j;
    DuLinkList p = L; // p指向頭結點
    if (i < 0 || i > ListLength(L)) // i值不合法
        return NULL;
    for (j = 1; j <= i; j++)
        p = p->next;
    return p;
}

Status ListInsert(DuLinkList L, int i, ElemType e) {
    // 在帶頭結點的雙鏈循環線性表L中第i個位置之前插入元素e，i的合法值為1≤i≤表長+1
    // 改進算法2.18，否則無法在第表長+1個結點之前插入元素
    DuLinkList p, s;
    if (i < 1 || i > ListLength(L) + 1) // i值不合法
        return ERROR;
    p = GetElemP(L, i - 1); // 在L中確定第i個元素前驅的位置指針p
    if (!p) // p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅)
        return ERROR;
    s = (DuLinkList)malloc(sizeof(DuLNode));
    if (!s)
        return OVERFLOW;
    s->data = e;
    s->prior = p; // 在第i-1個元素之後插入
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    return OK;
}

Status ListDelete(DuLinkList L, int i, ElemType *e) {
    // 刪除帶頭結點的雙鏈循環線性表L的第i個元素，i的合法值為1≤i≤表長
    DuLinkList p;
    if (i < 1) // i值不合法
        return ERROR;
    p = GetElemP(L, i); // 在L中確定第i個元素的位置指針p
    if (!p) // p = NULL,即第i個元素不存在
        return ERROR;
    *e = p->data;
    p->prior->next = p->next; // 此處並沒有考慮鏈表頭，鏈表尾
    p->next->prior = p->prior;
    free(p);
    return OK;
}

void ListTraverse(DuLinkList L, void(*visit)(ElemType)) {
    // 由雙鏈循環線性表L的頭結點出發，正序對每個數據元素調用函數visit()
    DuLinkList p = L->next; // p指向頭結點
    while (p != L) {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
}

void ListTraverseBack(DuLinkList L, void(*visit)(ElemType)) {
    // 由雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函數visit()
    DuLinkList p = L->prior; // p指向尾結點
    while (p != L) {
        visit(p->data);
        p = p->prior;
    }
    printf("\n");
}

4.4靜態鏈表

前面講解的都是動態鏈表，即需要指針來建立結點之間的連接關係。而對有些問題來說結點的地址是比較小的整數（例如5位數的地址），這樣就沒有必要去建立動態鏈表，而應使用方便得多的靜態鏈表。
靜態鏈表的實現原理是hash，即通過建立一個結構體數組，並令數組的下標直接表示結點的地址，來達到直接訪問數組中的元素就能訪問結點的效果。另外，由於結點的訪問非常方便，因此靜態鏈表是不需要頭結點的。靜態鏈表結點定義的方法如下：

struct Node{
    typename data;//數據域
    int next;//指針域
}node[size];

參考資料：

• 《算法筆記》
• 《數據結構和算法》-極客時間專欄

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

　　在業務系統需求規劃過程中，通常對於諸如組織機構、用戶和角色等這種基礎功能，通常是將這部分功能規劃到通用子域中，這也說明了，對於這部分功能來講，是系統的基石，整個業務體系是建立於這部分基石之上的，當然，還有諸如多語言、設置管理、認證和授權等。對於這部分功能，ABP中存在這些概念，並且通過Module Zero模塊完成了這些概念。

一、角色訪問控制之RBAC

　　RBAC：Role Based Access Control，基於角色的訪問控制，這在目前大多數軟件中來講已經算得上是普遍應用了，最常見的結構如下，結構簡單，設計思路清晰。

　　但是也存在其它升級版的設計，諸如用戶權限表、角色組、用戶組的概念等，具體分類有RBAC0、RBAC1、RBAC2等，後者功能越來越強大，也越來越複雜。

• RBAC0：是RBAC的核心思想。
• RBAC1：是把RBAC的角色分層模型。
• RBAC2：增加了RBAC的約束模型。
• RBAC3：整合RBAC2 + RBAC1。

二、ABP中的RBAC

　　在Abp中，已經集成了這些概念，並在ModuleZero模塊中實現了這些概念，基於IdentityServer4的ModuleZero模塊完成了封裝。對於我們大多數以業務為中心的開發人員來講，不應該又去造一個輪子，而是應該開好這輛車。首先看下Abp中的RBAC模型

　　在這其中權限表中記錄了用戶與權限，角色與權限兩部分。對於權限通常指的是功能權限和數據權限兩部分，一般來講，大多指的是功能權限，這種通過角色與權限進行管理即可，如還有用戶部分的功能區分，則可以再使用上用戶與權限，而對於數據權限，可以利用用戶與權限部分，個人用的比較少，但是，可以想象到這麼一個場景，針對於一家門店內的多個店長，角色相同即相應的權限相同，但各自關心的數據來源不同，關心東部、南部等數據，而不關心西部、北部數據，因此可以在數據層面進行劃分，比如設置數據來源，東南西北，對於數據來源進行權限關聯，這樣一來用戶本身如果擁有東部數據權限，則只能看到東部數據。

1、權限聲明及應用

　　在Abp中，需要首先在Core層/Authorization/PermissionNames.cs中聲明權限，Abp權限部分設計原則是：先聲明再使用。

/// <summary>
/// 權限命名
/// </summary>
public static class PermissionNames
{
    #region 頂級權限
    public const string Pages = "Pages";
    #endregion

    #region 基礎支撐平台
    public const string Pages_Frame = "Pages.Frame";

    #region 租戶管理
    public const string Pages_Frame_Tenants = "Pages.Frame.Tenants";
    #endregion

    #region 組織機構
    public const string Pages_Frame_OrganizationUnits = "Pages.Frame.OrganizationUnits";
    public const string Pages_Frame_OrganizationUnits_Create = "Pages.Frame.OrganizationUnits.Create";
    public const string Pages_Frame_OrganizationUnits_Update = "Pages.Frame.OrganizationUnits.Update";
    public const string Pages_Frame_OrganizationUnits_Delete = "Pages.Frame.OrganizationUnits.Delete";
    #endregion

    #region 用戶管理
    public const string Pages_Frame_Users = "Pages.Frame.Users";
    public const string Pages_Frame_Users_Create = "Pages.Frame.Users.Create";
    public const string Pages_Frame_Users_Update = "Pages.Frame.Users.Update";
    public const string Pages_Frame_Users_Delete = "Pages.Frame.Users.Delete";
    public const string Pages_Frame_Users_ResetPassword = "Pages.Frame.Users.ResetPassword";
    #endregion

    #region 角色管理
    public const string Pages_Frame_Roles = "Pages.Roles";
    public const string Pages_Frame_Roles_Create = "Pages.Frame.Roles.Create";
    public const string Pages_Frame_Roles_Update = "Pages.Frame.Roles.Update";
    public const string Pages_Frame_Roles_Delete = "Pages.Frame.Roles.Delete";
    #endregion

}

　　然後在Core層/Authorization/XXXAuthorizationProvider.cs中設置具體權限，在此處設置權限時，可以根據權限設計時候的職責劃分，比如如果僅僅是多租戶需要這部分，那便設置權限範圍為多租戶即可。

public class SurroundAuthorizationProvider : AuthorizationProvider
{
    public override void SetPermissions(IPermissionDefinitionContext context)
    {
        #region 頂級權限
        var pages = context.CreatePermission(PermissionNames.Pages, L("Pages"));
        #endregion

        #region 基礎支撐平台
        var frame = pages.CreateChildPermission(PermissionNames.Pages_Frame, L("Frame"));

        #region 租戶管理
        frame.CreateChildPermission(PermissionNames.Pages_Frame_Tenants, L("Tenants"), multiTenancySides: MultiTenancySides.Host);
        #endregion

        #region 組織機構
        var organizationUnits = frame.CreateChildPermission(PermissionNames.Pages_Frame_OrganizationUnits, L("OrganizationUnits"));
        organizationUnits.CreateChildPermission(PermissionNames.Pages_Frame_OrganizationUnits_Create, L("CreateOrganizationUnit"));
        organizationUnits.CreateChildPermission(PermissionNames.Pages_Frame_OrganizationUnits_Update, L("EditOrganizationUnit"));
        organizationUnits.CreateChildPermission(PermissionNames.Pages_Frame_OrganizationUnits_Delete, L("DeleteOrganizationUnit"));
        #endregion

        #region 用戶管理
        var users = frame.CreateChildPermission(PermissionNames.Pages_Frame_Users, L("Users"));
        users.CreateChildPermission(PermissionNames.Pages_Frame_Users_Create, L("CreateUser"));
        users.CreateChildPermission(PermissionNames.Pages_Frame_Users_Update, L("UpdateUser"));
        users.CreateChildPermission(PermissionNames.Pages_Frame_Users_Delete, L("DeleteUser"));
        users.CreateChildPermission(PermissionNames.Pages_Frame_Users_ResetPassword, L("ResetPassword"));
        #endregion

        #region 角色管理
        var roles = frame.CreateChildPermission(PermissionNames.Pages_Frame_Roles, L("Roles"));
        roles.CreateChildPermission(PermissionNames.Pages_Frame_Roles_Create, L("CreateRole"));
        roles.CreateChildPermission(PermissionNames.Pages_Frame_Roles_Update, L("UpdateRole"));
        roles.CreateChildPermission(PermissionNames.Pages_Frame_Roles_Delete, L("DeleteRole"));
        #endregion
    }
}

　　在設置完畢后，需要將該類集成到Core層/XXXCoreModule當前模塊中，才能使得該部分權限設置生效。

//配置權限管理
Configuration.Authorization.Providers.Add<SurroundAuthorizationProvider>();

 　　作為業務的入口，菜單是較為直觀的體現方式，現在可以，為菜單分配權限了，擁有權限的人才能看的到菜單，同時後台方法中也要有權限判定，菜單僅作為前端入口上的控制，權限判定作為後端的控制。在MVC層的Startup/XXXNavigationProvider.cs中完成菜單的配置工作，可以配置多級菜單，每個菜單可以配置相應的權限，在生成菜單判定時，如果父級菜單權限不足，則直接會跳過子級菜單的判定。

new MenuItemDefinition(//基礎支撐
    PageNames.FrameManage,
    L(PageNames.FrameManage),
    icon: "",
    requiredPermissionName: PermissionNames.Pages_Frame
).AddItem(
    new MenuItemDefinition(//組織機構
        PageNames.OrganizationUnits,
        L(PageNames.OrganizationUnits),
        url: "/OrganizationUnits",
        icon: "",
        requiredPermissionName: PermissionNames.Pages_Frame_OrganizationUnits
    )
).AddItem(
    new MenuItemDefinition(//用戶管理
        PageNames.Users,
        L(PageNames.Users),
        url: "/Users",
        icon: "",
        requiredPermissionName: PermissionNames.Pages_Frame_Users
    )
).AddItem(
    new MenuItemDefinition(//角色管理
        PageNames.Roles,
        L(PageNames.Roles),
        url: "/Roles",
        icon: "",
        requiredPermissionName: PermissionNames.Pages_Frame_Roles
    )
).AddItem(
    new MenuItemDefinition(//系統設置
        PageNames.HostSettings,
        L(PageNames.HostSettings),
        url: "/HostSettings",
        icon: "",
        requiredPermissionName: PermissionNames.Pages_Frame_HostSettings
    )
)

　　在前端頁面上，對於按鈕級別的控制也通過權限判定，Abp提供了判定方法，利用Razor語法進行按鈕控制

@if (await PermissionChecker.IsGrantedAsync(PermissionNames.Pages_Core_DataDictionary_Create))
{
    <button class="layui-btn layuiadmin-btn-dataDictionary" data-type="addDataDictionary">添加類型</button>
}

　　在後端方法上，通常我喜歡直接在應用服務中的方法上做權限判定(當然也可以前移到MVC層，但是這樣一來，針對於WebApi形式的Host層，又得多加一次判定了)，利用AbpAuthorize特性，判定該方法需要哪幾個權限才能訪問，而在mvc的控制器上做訪問認證。

[AbpAuthorize(PermissionNames.Pages_Core_DataDictionary_Create)]
private async Task CreateDataDictionaryAsync(CreateOrUpdateDataDictionaryInput input)
{

}

2、角色與權限

 　　在Abp中，角色信息存儲在abprole表中，角色與權限間的關聯存儲在abppermission這張表中，一個角色有多個權限，如果某個角色的權限被去掉了，這張表中的相關記錄將由abp負責刪除，我們只需要完成掌控哪些權限是這個角色有的就行。Abp中已經完成了角色的所有操作，但是前端部分採用的是bootstrap弄的，將其改造一波，成為layui風格。

　　在創建角色中，主要是將選中的權限掛鈎到具體的某個角色上，該部分代碼沿用abp中自帶的角色權限處理方法。

private async Task CreateRole(CreateOrUpdateRoleInput input)
{
    var role = ObjectMapper.Map<Role>(input.Role);
    role.SetNormalizedName();

    CheckErrors(await _roleManager.CreateAsync(role));

    var grantedPermissions = PermissionManager
        .GetAllPermissions()
        .Where(p => input.PermissionNames.Contains(p.Name))
        .ToList();

    await _roleManager.SetGrantedPermissionsAsync(role, grantedPermissions);
}

　　指定角色Id，租戶Id及之前聲明的權限名稱，在abppermission中可查看到具體角色權限。

3、用戶與角色

 　　一個用戶可以承擔多個角色，履行不同角色的義務，作為一個業務系統最基本的單元，abp中提供了這些概念並在Module Zero模塊中已經完成了對用戶的一系列操作，用戶信息存儲在AbpUsers表中,用戶直接關聯的角色保存在AbpUserRoles表中，abp中MVC版本採用的是bootstrap風格，因此，用layui風格完成一次替換，並且，改動一些頁面布局。

　　Abp版本中，由於是土耳其大佬所開發的習慣，針對於姓和名做了拆分，因此對於我們的使用要做一次處理，我這先簡單處理了一下，並且在業務系統中，郵箱時有時無，因此也需要進行考慮。

[AbpAuthorize(PermissionNames.Pages_Frame_Users_Create)]
private async Task CreateUser(CreateOrUpdateUserInput input)
{
    var user = ObjectMapper.Map<User>(input.User);
    user.TenantId = AbpSession.TenantId;
    user.IsEmailConfirmed = true;
    user.Name = "Name";
    user.Surname = "Surname";
    //user.EmailAddress = string.Empty;

    await UserManager.InitializeOptionsAsync(AbpSession.TenantId);
    foreach (var validator in _passwordValidators)
    {
        CheckErrors(await validator.ValidateAsync(UserManager, user, AppConsts.DefaultPassword));
    }

    user.Password = _passwordHasher.HashPassword(user, AppConsts.DefaultPassword);

    await _userManager.InitializeOptionsAsync(AbpSession.TenantId);

    CheckErrors(await _userManager.CreateAsync(user, AppConsts.DefaultPassword));

    if (input.AssignedRoleNames != null)
    {
        CheckErrors(await _userManager.SetRoles(user, input.AssignedRoleNames));
    }

    if (input.OrganizationUnitIds != null)
    {
        await _userManager.SetOrganizationUnitsAsync(user, input.OrganizationUnitIds);
    }

    CurrentUnitOfWork.SaveChanges();
}

　　此處對用戶個人單獨的權限沒有去做處理，依照Abp的文檔有那麼一句話，大多數應用程序中，基於角色的已經足夠使用了，如果想聲明特定權限給用戶，那麼針對於用戶本身的角色權限則被覆蓋。 　　　

　至此，修改整合用戶、角色和權限加入到系統中初步完成了，至於一些更為豐富的功能，待逐步加入中，車子再好，司機也得睡覺。

　倉庫地址：

2019-11-17,望技術有成后能回來看見自己的腳步

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計

※不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置，台北網頁設計，各種案例分享

text-decoration屬性介紹

• text-decoration屬性是用來設置文本修飾線呢，text-decoration屬性一共有4個值。

text-decoration屬性值說明表

HTML標籤自帶修飾線

• 在開始實踐text-decoration屬性之前，筆者先給大家普及下HTML中的標籤自帶修飾線如：u標籤、s標籤，若有不全大家可以在下面評論中告訴筆者,畢竟筆者也是前端的一個小白,希望和大家相互交流，互幫互助，共同進步。

u標籤

• 下面讓我們進入u標籤的實踐，u標籤自帶的是文本下劃線。

• 代碼塊

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>設置文本修飾線</title>
  
</head>
<body>
    <u>成功不是擊敗別人，而是改變自己</u>
</body>
</html>

• 結果圖

• 注意：u標籤也可以配合HTML中的其他標籤使用，舉例：將u標籤嵌套到h1標籤中使用。

• 代碼塊

<h1><u>成功不是擊敗別人，而是改變自己</u></h1>

s標籤

• 下面讓我們進入s標籤的實踐，s標籤自帶的是文本刪除線。

• 代碼塊

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>設置文本修飾線</title>
  
</head>
<body>
    <s>成功不是擊敗別人，而是改變自己</s>
</body>
</html>

• 結果圖

• 注意：s標籤也可以嵌套，和u標籤一致，筆者就不過多的介紹了。

none去除修飾線

• 讓我們進入text-decoration屬性的none值實踐，實踐內容如：筆者將HTML頁面中的s標籤自帶的刪除線給去除掉。

• 代碼塊

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>設置文本修飾線</title>
    <style>
        s{
            text-decoration: none;
        }
    </style>
</head>
<body>
    <s>成功不是擊敗別人，而是改變自己</s>
</body>
</html>

• 結果圖

• 注意：u標籤、s標籤、包括text-decoration屬性值的所有的修飾線都可以去掉哦。

underline設置下劃線

• 讓我們進入text-decoration屬性的underline值實踐，實踐內容如：筆者將HTML頁面中的h2標籤中的文本設置一個下劃線。

• 代碼塊

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>設置文本修飾線</title>
    <style>
        h2{
            text-decoration: underline;
        }
    </style>
</head>
<body>
    <h2>成功不是擊敗別人，而是改變自己</h2>
</body>
</html>

• 結果圖

overline設置上劃線

• 讓我們進入text-decoration屬性的overline值實踐，實踐內容如：筆者將HTML頁面中的h2標籤中的文本設置一個上劃線。

• 代碼塊

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>設置文本修飾線</title>
    <style>
        h2{
            text-decoration: overline;
        }
    </style>
</head>
<body>
    <h2>成功不是擊敗別人，而是改變自己</h2>
</body>
</html>

• 結果圖

line-through設置刪除線

• 讓我們進入text-decoration屬性的line-through值實踐，實踐內容如：筆者將HTML頁面中的h2標籤中的文本設置一個刪除線。

• 代碼塊

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>設置文本修飾線</title>
    <style>
        h2{
            text-decoration: line-through;
        }
    </style>
</head>
<body>
    <h2>成功不是擊敗別人，而是改變自己</h2>
</body>
</html>

• 結果圖

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※南投搬家前需注意的眉眉角角，別等搬了再說!

一、故事的起因

JDK1.8最重要的就是引入了紅黑樹的設計（當衝突的鏈表長度超過8個的時候），為什麼要這樣設計呢？好處就是避免在最極端的情況下衝突鏈表變得很長很長，在查詢的時候，效率會非常慢。

• 紅黑樹查詢：其訪問性能近似於折半查找，時間複雜度O(logn)；
• 鏈表查詢：這種情況下，需要遍歷全部元素才行，時間複雜度O(n)；

本文主要是講解紅黑樹的實現，只有充分理解了紅黑樹，對於後面的分析才會更加順利。

簡單的說，紅黑樹是一種近似平衡的二叉查找樹，其主要的優點就是“平衡“，即左右子樹高度幾乎一致，以此來防止樹退化為鏈表，通過這種方式來保障查找的時間複雜度為log(n)。

關於紅黑樹的內容，網上給出的內容非常多，主要有以下幾個特性：

• 1、每個節點要麼是紅色，要麼是黑色，但根節點永遠是黑色的；
• 2、每個紅色節點的兩個子節點一定都是黑色；
• 3、紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）；
• 4、從任一節點到其子樹中每個恭弘=叶 恭弘子節點的路徑都包含相同數量的黑色節點；
• 5、所有的恭弘=叶 恭弘節點都是是黑色的（注意這裏說恭弘=叶 恭弘子節點其實是上圖中的 NIL 節點）；

在樹的結構發生改變時（插入或者刪除操作），往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的條件。

二、調整方式

上面已經說到當樹的結構發生改變時，紅黑樹的條件可能被破壞，需要通過調整使得查找樹重新滿足紅黑樹的條件。

調整可以分為兩類：一類是顏色調整，即改變某個節點的顏色，這種比較簡單，直接將節點顏色進行轉換即可；另一類是結構調整，改變檢索樹的結構關係。結構調整主要包含兩個基本操作：左旋（Rotate Left），右旋（RotateRight）。

2.1、左旋

左旋的過程是將p的右子樹繞p逆時針旋轉，使得p的右子樹成為p的父親，同時修改相關節點的引用，使左子樹的深度加1，右子樹的深度減1，通過這種做法來調整樹的穩定性。過程如下：

以jdk1.8為例，打開HashMap的源碼部分，紅黑樹內部類TreeNode屬性分析：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        //指向父節點的指針
        TreeNode<K,V> parent;
        //指向左孩子的指針
        TreeNode<K,V> left;
        //指向右孩子的指針
        TreeNode<K,V> right;
        //前驅指針，跟next屬性相反的指向
        TreeNode<K,V> prev;
        //是否為紅色節點
        boolean red;
        ......
}

左旋方法rotateLeft如下：

/*
 * 左旋邏輯
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            //root:表示根節點
            //p:表示要調整的節點
            //r:表示p的右節點
            //pp:表示p的parent節點
            //rl:表示p的右孩子的左孩子節點
            TreeNode<K,V> r, pp, rl;
            //r判斷，如果r為空則旋轉沒有意義
            if (p != null && (r = p.right) != null) {
                //多個等號的連接操作從右往左看，設置rl的父親為p
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                //判斷p的父親，為空，為根節點，根節點的話就設置為黑色
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                //判斷p節點是左兒子還是右兒子
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
}

2.2、右旋

了解了左旋轉之後，相應的就會有右旋，邏輯基本也是一樣，只是方向變了。右旋的過程是將p的左子樹繞p順時針旋轉，使得p的左子樹成為p的父親，同時修改相關節點的引用，使右子樹的深度加1，左子樹的深度減1，通過這種做法來調整樹的穩定性。實現過程如下：

同樣的，右旋方法rotateRight如下：

/*
 * 右旋邏輯
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            //root:表示根節點
            //p:表示要調整的節點
            //l:表示p的左節點
            //pp:表示p的parent節點
            //lr:表示p的左孩子的右孩子節點
            TreeNode<K,V> l, pp, lr;
            //l判斷，如果l為空則旋轉沒有意義
            if (p != null && (l = p.left) != null) {
                //多個等號的連接操作從右往左看，設置lr的父親為p
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                //判斷p的父親，為空，為根節點，根節點的話就設置為黑色
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                //判斷p節點是右兒子還是左兒子
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
}

三、操作示例介紹

3.1、插入調整過程圖解

3.2、刪除調整過程圖解

3.3、查詢過程圖解

四、總結

至此，紅黑樹的實現就基本完成了，關於紅黑樹的結構，有很多種情況，情況也比較複雜，但是整體調整流程，基本都是先調整結構然後調整顏色，直到最後滿足紅黑樹特性要求為止。整篇文章，如果有理解不當之處，歡迎指正！

五、參考

1、
2、

作者：炸雞可樂
出處：

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!