数据结构期末总结

四、数组、串和广义表

数组

行优先存放:
LOC ( j, k ) = a + ( j x m + k ) x l
列优先存放:
LOC ( j, k ) = a + ( k x n + j ) x l
三维数组:
LOC ( i1, i2, i3) = a +( i1 x m2 x m3 + i2 x m3 + i3) x l

特殊矩阵

下三角矩阵:
LOC(i, j) : (i+1)*i/2+j
上三角矩阵:
LOC(i, j) : (j+1)*j/2+i

三对角矩阵:
LOC(i, j) : 2*i+j
已知某元素ai存放于k位置,则i = (k+1)/3, j = k-2*i

稀疏矩阵:
三元组:行下标、列下标、元素值

字符串

模式匹配:
B-F

int i=pos; int j=1;
while (i<=S[0] && j<=T[0]) {
    if (S[i]==T[j]) {++i; ++j;}
    else {i=i-j+2; j=1;}
}
if (j>T[0]) return i-T[0];
else return 0;

KMP

int j = 0, k = -1, lengthP = curLength;
next[0] = -1;
while (j < lengthP) //计算next[j]
    if ( k == -1 || ch[j] == ch[k]) {
    j++; k++;
    next[j] = k;
}
else k = next[k];

广义表

第一个表元素为表头(可能是原子或列表),除表头元素外的其他元素组成的表为表尾(一定是列表)。
深度Depth(LS) =

  • 1 (LS为空表时)
  • 0 (LS为原子时)
  • 1 + max{Depth(α)} (其他)

五、树

二叉树

性质:

  • 若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1个结点。( i≥1)
  • 深度为 k 的二叉树最少有 k 个结点,最多有 2k-1个结点
  • 对任何一棵二叉树,如果其叶结点有n0 个, 度为 2 的非叶结点有 n2 个, 则有n0=n2+1
  • 具有 n (n≥0) 个结点的完全二叉树的深度为 log2(n+1)向上取整

六、排序

直接插入排序

void InsertSort (dataList<T>& L, int left,                                 int right) {
Element<T> temp; int i, j;
for (i = left+1; i <= right; i++)
    if (L[i] < L[i-1]) {
        temp = L[i]; j = i-1;
        do {
            L[j+1] = L[j]; j--;
        } while (j >= left && temp < L[j]);
        L[j+1] = temp;
    }
};

折半插入排序

void BinaryInsertSort (dataList<T>& L, const int left, const int right) {
    Element<T> temp;
    int i, low, high, middle, k;
    for (i = left+1; i <= right; i++) {
        temp = L[i]; low = left; high = i-1;
        while (low <= high) { //折半搜索插入位置
            middle = (low+high)/2; //取中点
            if (temp < L[middle]) //插入值小于中点值
            high = middle-1; //向左缩小区间
            else low = middle+1; //否则, 向右缩小区间
        }
        for (k = i-1; k >= low; k--) L[k+1] = L[k];
        L[low] = temp; //插入
    }
};

希尔排序

void Shellsort (dataList<T>& L, const int left, const int right) {
    int i, j, gap = right-left+1; //增量的初始值
    Element<T> temp;
    do {
    gap = gap/3+1; //求下一增量值
    for (i = left+gap; i <= right; i++)
        if (L[i] < L[i-gap]) { //逆序
            temp = L[i]; j = i-gap;
            do {
                L[j+gap] = L[j]; j = j-gap;
            } while (j >= left && temp < L[j]);
            L[j+gap] = temp; //将vector[i]回送
        }
    } while (gap > 1);
};

选择排序

void SelectSort (dataList<T>& L, const int left, const int right) {
    for (int i = left; i < right; i++) {
        int k = i; //在L[i]到L[n-1]找最小排序码元素
        for (int j = i+1; j <= right; j++)
            if (L[j] < L[k]) k = j;
        if (k != i) Swap (L[i], L[k]); //交换
    }
};

归并排序

void merge (dataList<T>& L1, dataList<T>& L2, const int left, const int mid, const int right) {
    int k, i, j;
    i = left; j = mid+1; k = left;
    while (i <= mid && j <= right) //两两比较
        if (L1[i] <= L1[j])
            L2[k++] = L1[i++];
        else
            L2[k++] = L1[j++];
    while (i <= mid) L2[k++] = L1[i++];
    while (j <= right) L2[k++] = L1[j++];

void MergePass (dataList<T>& L1, datalist<T>& L2, const int len) {
    int i = 0, j, n = L1.Length();
    while (i+2*len <= n-1) {
        merge (L1, L2, i, i+len-1);
        i += 2*len;
    }
    if(i+len <= n-1)
        merger(L1, L2, i, i+len-1, n-1);
    else for(j=i; j<=n-1; ++j) L2[j] = L1[j];
}

堆排序

void siftDown (dataList<T>& L, const int start, const int m){
    int i = start; int j = 2*i+1; //j是i的左子女
    Element<T> temp = L[i]; //暂存子树根结点
    while (j <= m) { //逐层比较
        if (j < m && L[j] < L[j+1]) j++;
        if (temp >= L[j]) break; //temp排序码大不调整
        else { //否则子女中的大者上移
            L[i] = L[j];
            i = j; j = 2*j+1; //i下降到子女位置
        }
    }
    L[i] = temp; //temp放到合适位置
};

void HeapSort (dataList<T>& L) {
    int i, n = L.length();
    for (i = (n-2)/2; i >= 0; i--) //将表转换为堆
        siftDown (L, i, n-1);
    for (i = n-1; i >= 0; i--) { //对表排序
        L.Swap(0, i); siftDown (L, 0, i-1);
    }
};

快速排序

void QuickSort (dataList<T>& L, const int left, const int right) {
    if (left < right) { //元素序列长度大于1时
        int pivotpos = L.Partition (left, right); //划分
        QuickSort (L, left, pivotpos-1);
        QuickSort (L, pivotpos+1, right);
    }
};

int dataList<T>::Partition (const int low, const int high) {
    int pivotpos = low;
    Element<T> pivot = Vector[low]; //基准元素
    for (int i = low+1; i <= high; i++)
        if (Vector[i] < pivot) {
            pivotpos++;
            if (pivotpos != i)
            Swap(Vector[pivotpos],Vector[i]);
        } //小于基准的交换到左侧去
    Vector[low] = Vector[pivotpos];
    Vector[pivotpos] = pivot;
    return pivotpos; //返回基准元素位置
};

基数排序

void Sort (staticlinkList<T>& L, int d) {
    int rear[radix], front[radix]; //队尾与队头指针
    int i, j, k, last, current, n = L.Length();
    for (i = 0; i < n; i++) L[i].link = i+1;
    L[n].link = 0; //初始化, 循环链表
    current = 1; //取表元素计数
    for (i = d; i >= 1; i--) { //按排序码key[i]分配
        for (j = 0; j < radix; j++) front[j] = 0; 
        while (current != 0) { //分配
            k = getDigit (L[current], i); //取第i个排序码
            if (front[k] == 0) front[k] = current;
            //第k个队列空, 该元素为队头
            else L[rear[k]].link = current; //不空, 尾链接
            rear[k] = current; //该元素成为新的队尾
            current = L[current].link; //下一个元素
        }
        j = 0; //依次从各队列收集并拉链
        while (front[j] == 0) j++; //跳过空队列
        L[0].link = current = front[j]; //新链表的链
        last = rear[j]; //非空队列链尾
        for (k = j+1; k < radix; k++) //连接其余队列
            if (front[k] != 0) { //队列非空
                 L[last].link = front[k];
                 //前一非空队列队尾链接到第k队列队头
                 last = rear[k]; //记第k队列队尾
         }
         L[last].link = 0; //新链表表尾
    } //下一趟分配与收集
};

Sort.jpg

添加新评论