数据结构作业

期末复习

算法：输入输出，确定性，有穷性，有效性

线性表： N个元素的有限序列；具有逻辑上的顺序性，即：排列有其先后次序；表中元素的数据类型相同。

顺序表： 将线性表中的元素相继存放在一个连续的存储空间中。元素的逻辑顺序与物理顺序一致。

线性链表： 对线性表的链接存储表示；分为：单链表、循环链表、双向链表；

单链表：节点可以连续、可以不连续存储；节点的逻辑顺序与其物理顺序可以不一致

引用型参数 & 的使用，函数体内对其的操作是对实际变量的操作

栈和队列都是限制了存储位置的线性表，逻辑结构是线性结构

栈与数据的存储结构无关。

广义表：允许线性表的元素有其自身的结构

---

结点的度：结点所拥有的子树的棵树

叶节点：度为0的节点

满二叉树，肯定是完全二叉树

完全二叉树特点：最下层的叶子结点集中在左部。

二叉排序树：节点左子树所有关键字小于节点关键字。

先序+后序：一般无法确定唯一一颗二叉树

平衡二叉树： 任一结点左右子树的高度之差的绝对值不超过1

二叉链表示一颗 N 个结点的二叉树有 N+1 个空指针域

---

内排序：排序期间数据记录全部存放在内存中。

排序算法的稳定性：两个相等的值排序后相对次序不变。

希尔排序，又称缩小增量排序，是一种不稳定的排序。

堆排序及优先队列⭐

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
#pragma warning(disable:4996)

typedef struct {
    int key;
}node;
typedef struct {
    node data[maxsize];
    int n;
}datalist;

void siftdown(datalist&h, int l, int r) {
    int i = l;
    int j = 2 * i + 1;
    node w = h.data[i];
    while (j <= r) {
        if (j < r && h.data[j].key < h.data[j + 1].key)
            j++;
        if (w.key >= h.data[j].key)
            break;
        else {
            h.data[i] = h.data[j];
            i = j;
            j = 2 * j + 1;
        }
    }
    h.data[i] = w;
}
void siftup(datalist&h, int l, int r) {
    int i = l;
    int j = 2 * i + 1;
    node w = h.data[i];
    while (j <= r) {
        if (j < r && h.data[j].key > h.data[j + 1].key)
            j++;
        if (w.key <= h.data[j].key)
            break;
        else {
            h.data[i] = h.data[j];
            i = j;
            j = 2 * j + 1;
        }
    }
    h.data[i] = w;
}

void heapsort(datalist &h) {
    int i;

    //将表转换成堆
    for (i = (h.n - 2) / 2; i >= 0; i--)
        siftdown(h, i, h.n - 1);

    for (i = h.n - 1; i >= 1; i--) {
        node tmp = h.data[0];
        h.data[0] = h.data[i];
        h.data[i] = tmp;
        siftdown(h, 0, i - 1);
    }
}

void main() {
    datalist l,h;
    printf("input the length of datalist:\n");
    scanf("%d", &l.n);

    printf("input the numbers:\n");
    for (int i = 0; i < l.n; i++)
        scanf("%d", &l.data[i].key);

    h.n = 5;
    for (int i = 0; i < 5; i++)
        h.data[i].key = l.data[i].key;
    heapsort(h);
    //先构建一个n为5的最小堆
    for (int i = 4; i < l.n; i++) {
        int x = l.data[i].key;
        if (x > h.data[0].key)
            h.data[0].key = x;
            siftup(h, 0, 4);
    }
    printf("\n the top 5 :\n");
    for (int i = 0; i < 5; i++)
        printf(" %d ", h.data[i].key);
    system("pause");
}

哈希表的实现及链地址法处理冲突

理解：
哈希可以理解为一种映射关系，这样会查找得快一些
但哈希可能带来key冲突的问题，于是有了冲突处理

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)

typedef struct node {
    int val;
    struct node* next;
}ha,*hap;

void insert(ha arr[],int k, int num) {
    hap p = &arr[k];
    while (p->next)
        p = p->next;
    p->val = num;
    hap tmp = new ha;
    tmp->val = -1;
    tmp->next = NULL;
    p->next = tmp;
}

int search(ha arr[],int k, int x) {
    hap p = &arr[k];
    while (p) {
        if (p->val == x)
            break;
        p = p->next;
    }
    if (p == NULL)
        return 0;
    else
        return 1;

}

void main() {
    int n,m,x;
    printf("input the length of hashtable:\n");
    scanf("%d", &n);
    hap arr = new ha[n];  //define the pointer of hash-linklist

    for (int i = 0; i < n; i++) {  //init
        arr[i].val = -1;
        arr[i].next = NULL;
    }

    printf("input the length of numbers:\n");
    scanf("%d", &m);
    printf("\ninput the num:");
    while (m--) {
        int num;
        scanf("%d", &num);
        insert(arr, num%n, num); //将num%n作为key
    }

    printf("input the num should find:\n");
    scanf("%d", &x);
    int ans = search(arr, x%n, x); //将num%n作为key
    if (ans)
        printf("success,");
    else
        printf("fail");

    system("pause");
}

插入排序

typedef struct {
    int key;
}node;
typedef struct {
    node data[maxsize];
    int n;
}datalist;

void quicksort(datalist&l, int left, int right) {
    if (left < right) {
        int mid = partition(l, left, right);
        quicksort(l, left, mid - 1);
        quicksort(l, mid + 1, right);
    }
}

int partition(datalist&l, int left, int right){
    node cur = l.data[left];
    while (left < right) {
        while (left < right &&l.data[right].key >= cur.key)
            right--;
        l.data[left] = l.data[right];
        while (left < right &&l.data[left].key <= cur.key)
            left++;
        l.data[right] = l.data[left];
    }
    l.data[left] = cur;
    return left;
}

快速排序

void insertsort(datalist&l) {
    node w;
    int i, j;
    for (i = 1; i < l.n; i++) {
        if (l.data[i].key < l.data[i - 1].key) {
            w = l.data[i];
            l.data[i] = l.data[i - 1];
            for (j = i - 1; i > 0; j--)
                if (w.key < l.data[j - 1].key)
                    l.data[j] = l.data[j - 1];
                else break;
            l.data[j] = w;
        }
    }
}

稀疏矩阵的转置

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)

typedef struct {
    int row, col, val;
}trituple;

typedef struct {
    trituple *terms;
    int cols, rows, cnt;
}sparsematrix;

//int rowsize[a.cols] 报错：表达式必须含有常量值
void transpose_fast(const sparsematrix&a, sparsematrix&b) {
    int *rowsize = new int[a.cols];
    int *rowstart = new int[a.cols];
    b.rows = a.cols;
    b.cols = a.rows;
    b.cnt = a.cnt;
    b.terms = new trituple[a.cnt];    //忘了初始化，报错：写入位置 0xCCCCCCD8 时发生访问冲突。

    if (b.cnt > 0) {
        for (int i = 0; i < a.cols; i++) {
            rowsize[i] = 0;
        }
        for (int i = 0; i < a.cnt; i++) {
            rowsize[a.terms[i].col]++;
        }
        rowstart[0] = 0;
        for (int i = 1; i < a.cols; i++)
            rowstart[i] = rowstart[i - 1] + rowsize[i - 1];

        //for (int i = 0; i < a.cols; i++) {
        //    printf("%d %d\n", rowsize[i], rowstart[i]);
        //}
        for (int i = 0; i < a.cnt; i++) {
            int j = rowstart[a.terms[i].col];
            b.terms[j].row = a.terms[i].col;
            b.terms[j].col = a.terms[i].row;
            b.terms[j].val = a.terms[i].val;
            rowstart[a.terms[i].col]++;
        }
    }
    delete[] rowsize;
    delete[] rowstart;
}

void main() {
    sparsematrix a,b;
    printf("input the rows,cols and count:\n");
    scanf("%d %d %d", &a.rows, &a.cols, &a.cnt);
    a.terms = new trituple[a.cnt];
    printf("\ninput the row,col and val for every items (index begin from 0) :\n");
    for (int i = 0; i < a.cnt; i++) {
        scanf("%d", &a.terms[i].row);
        scanf("%d", &a.terms[i].col);
        scanf("%d", &a.terms[i].val);
    }
    transpose_fast(a, b);
    printf("the ans:\n");
    for (int i = 0; i < b.cnt; i++) {
        printf("%d %d %d\n", b.terms[i].row, b.terms[i].col, b.terms[i].val);
    }
    system("pause");
}