数据结构算法合集

发表于 分类于 Waline： 本文字数： 10k 阅读时长 ≈ 9 分钟

数据结构算法合集

第一部分：链表

  • 从一给定的顺序表L中删除下标i-j（i<=j,包括i,j）的所有元素，假定i,j合法。
1
2
3
4
5
6
7
8
9
//顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中，以数组的形式保存的线性表
void delete(SqList &L,int i,j){
    int k, delta;
    delta = j - i + 1;
    for(k = j + 1; k < L.length; ++k){
        L.data[k - delta]=L.data[k];
    }
    L.length -= delta;//最后要更新顺序表的表长
}
  • 有一顺序表L，其元素为整型数据，设计一个算法，将L中所有小于表头元素的数据放在前半部分，大于表头元素的数据放在后半部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void move(SqList &L){
    int temp;
    int  i = 0, j = L.length - 1;
    temp = L.data[0];
    while(i < j){
        while(i < j&& L.data[j] > temp) --j;
        if(i < j){
            L.data[i] = L.data[j];
            ++i;
        }
        while(i < j&& L.data[i] < temp) ++i;
        if(i < j){
            L.data[j] = L.data[i];
            --j; 
        }
    }
    L.data[i] = temp;
}
  • 递增非空单链表，设计一个算法删除值域重复的结点。
1
2
3
4
5
6
7
8
9
10
11
12
viod dels(LNode *L){
    LNode *p = L->next, *q;
    while(p->next != NULL){
        if(p->data == p->next->data){
            q = p->next;
            p->next = q->next;
            free(q);
        }
        else
            p = p->next;
    }
}
  • 带头结点的单链表L，在不建立新结点，只能通过已有结点的条件下将其逆置。
1
2
3
4
5
6
7
8
9
10
void reverseList(LNode *L){
    LNode *p = L->next, *q;
    L->next = NULL;
    while(p != NULL){
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}
  • 设计一个算法，删除带头结点的单链表L中最小值结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
void delminNode(LNode *L){
    LNode *pre = L, *p = L->next, *minpre = pre, *minp = p;
    while(p != NULL){
        if(p->data < minp->data){
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    free(minp);
}
  • 设计一个算法，将一个头结点为A的单链表（其数据域为整型），分解成两个单链表A和B，使保持相对顺序的情况下，A中只有奇数结点，B中只有偶数结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void spList(LNode *A, LNode *&B){
    LNode *p, *q, *r;
    B = (LNode*)malloc(sizeof(LNode));
    B->next = NULL;
    r = B;
    p = A;
    while(p->next != NULL){
        if(p->next->data%2 == 0){
            q = p->next;
            p->next = q->next;
            q->next = NULL;
            r->next = q;
            r = q;
        }else
            p = p->next;
    }
}
  • 有N个个位正整数存放在int型数组A[0,1,…,N-1]中，N为已定义的常量且N<=9，数组A[]的长度为N，另给一个int型变量i，要求只要上述变量（A[0]~A[N-1]与i这N+1个整型变量）写一个算法，找出这N个整数中的最小值，并且要求不能破坏数组A[]中的数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 难点： int i 这一个变量来实现通航数组下标 i 和 min 两个变量所实现的功能
// 实现方法： 可以让 i 的十位上的数字作为循环变量，将 i 的个位上的数字用来存储 min 
// i % 10 即取 i 个位上的数字，i / 10 即取 i 十位上的数字
void findMin(int A[], int &i){
    i = A[0];
    while(i/10 <= N-1){
        if(i%10 > A[i/10]){
            i = i - i%10;
            i = i + A[i/10];
        }
        i = i + 10;
    }
    i = i % 10;
}
  • 写一个函数，逆序打印单链表中的数据，假设指针L指向了单链表的开始结点。
1
2
3
4
5
6
7
//递归思想：在表不空的情况下，递归地逆序打印表中第一个数据之后的数据，然后打印第一个数据。
void reprint(LNode *L){
    if(L != NULL){
        reprint(L->next);
        printf("%s", L->data);
    }
}
  • 试编写一个函数，以不多于3n/2的平均比较次数，在一个有n个整型的顺序表A中找出最大最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
void FindMaxMin(int A[], int n, int &max, int &min){
    max = min = A[1];
    for(int i = 2; i <= n; ++i){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
}
//最坏情况：当表中 n 个整数按从大到小非递增排列时，数据比较次数为 2(n-1) 次
//最好情况：当表中 n 个整数按从小到大非递减排列时，数据比较次数为 n-1 次
//A 中数据的有序性可以认为是等可能的，故，最好最坏情况概率相同
//综上所述，数据平均比较次数为 (2*(n-1)+(n-1))/2 = 3n/2 - 3/2 < 3n/2
  • 设A=（a1,a2,…,an）和B=（b1,b2,..,bn）均为顺序表，A’和B’分别是除去最大公共前缀后的子表。若A=（b,e,i,j,i,n,g）,B=（b,e,i,f,a,n,g），则A’=（j,i,n,g），B’=（f,a,n,g），若A’=B’=∅，则A=B，若A’=∅且B≠∅，或两者均不为空且A’的第一个元素值小于B’的第一个元素值，则A<B，否则A>B.试写出一个函数，根据上述方法比较A,B大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//只需先进行一趟循环，过滤掉最大公共前缀，再判断剩余部分，A = B 返回0， A < B 返回-1，否则返回1
int compare(float A[], int An, float B[], int Bn){
    int i = 0;
    /* 过滤公共前缀*/
    while(i < An && i < Bn){
        if(fabs(A[i] - B[i]) < min)
            ++i;
        else
            break;
    }
    /* A',B'均为空*/
    if (i >= An && i >= Bn)
        return 0;
    /* A' ≠ ∅且B' ≠ ∅，或A'第一个元素值小于B'*/
    else if ((i >= An && i < Bn)||A[i] < B[i])
        return -1;
    else
        return 1;
}

  • 键盘输入n个英文字母，输入格式为n,C1,C2,…,Cn，其中n表示字母个数，请编程以这些输入数据建立一个单链表，并要求将字母不重复的存入链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//每输入一个数据，扫描其在链表中是否出现，如果出现，就什么都不做，否则构造结点，插入表中
void createLinkNoSameElem(LNode *&head){
    /* 初始化链表*/
    head = (LNode*)malloc(sizeof(LNode));
    head->next = NULL;
    LNode *p;
    int n;
    char ch;
    scanf("%d", &n);//输入字母个数
    for(int i = 0; i < n; ++i){
        scanf("%c", &ch);
        p = head->next;
        while(p!=NULL){
        /* 若出现过该数据，则退出循环，且此时 p != NULL*/
            if(p->data == ch)
                break;
            p = p->next;
        }
        /* 若未出现过该数据，则 p 此时遍历到了表尾结点，进行插入操作，让 p 重新指向新结点*/
        if(p == NULL){
            p = (LNode*)malloc(sizeof(LNode));
            p->data = ch;
            /* 头插法，插入结点*/
            p->next = head->next;
            head->next = p;
        }
    }
}
  • 将一长度为n的数组的前段k(k<n)个元素逆序后移动到数组后端，要求数组中的数据不丢失。
1
2
3
4
5
6
7
8
9
10
11
//思路：可直接将第一个元素与最后一个元素交换，第二个与倒数第二个元素交换，以此类推，依次执行 k 次，利用顺序表逆置算法将前 k 个按逆序的方式移动到了数组后端
/* a[]:逆置数组，left~right:逆置范围，k:逆置次数*/
void reverse(int a[], int left, int right, int k){
    int temp;
    for(int i = left, j = right; i < j && i < left + k ; ++i, --j){
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
//当 k 大于逆序数组元素个数的一半时，只需要逆序到 i < j 时即可，因为此时整个数组已经完全逆置
  • 将一长度为n的数组的前段k(k<n)个元素保持原序移动到数组后端，要求数组中的数据不丢失。
1
2
3
4
5
//思路：代码间尽量提高已有代码的复用性，12为本题前一问，则本题思路为，通过将前 k 个元素先进行一次逆序，再将 k 个元素进行一个整体逆序，则前 k 个元素经过两次逆序保持了原来的顺序，而一次交换到了数组最后端。
void moveToEND(int a[], int n, int k){
    reverse(a, 0, k-1, k);
    reverse(a, 0, n-1, k);
}
  • 将n(n>1)个数组存放在一维数组R中，设计一个算法，将R中的序列循环左移p(0<p<n)个位置，即将R中的数据由{X0,X1,…,Xn-1}变换为{Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1}。
1
2
3
4
5
6
//思路：需实现 R 中序列循环左移 p 个位置，只需将 R 中前 p 个元素逆置，再将剩余元素逆置，最后进行一次整体逆置即可
void moveP(int a[], int n, int p){
    reverse(a, 0, p-1, p);
    reverse(a, p, n-1, n-p);
    reverse(a, 0, n-i, n);
}
  • 一由Head指针指出的非空双链表中，结点结构为{lLink,data,rLink},请设计一个算法，将结点数据data值最大的那个结点（最大的结点唯一），移动到链表最前边，要求不得申请新结点空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//思路：①找出最大值结点；②“删除”结点；③插入最大值结点
//{llink,data,rlink}是伪代码表示法，仅只改了名字，llink对应于prior指针，rlink对应于next指针
void maxFirst(DLNode *head){
    DLNode *p = head->rlink, *q = p;
    int max = p->data;
    /* 查找*/
    while(p != NULL){
        if(max < p_.data){
            max = p->data;
            q = p;
        }
        p = p->rlink;
    }
    /* 删除*/
    DLNode *l = q->llink, *r = q->rlink;
    l->rlink = r;
    if(r != NULL){
        r->llink = l;
    /* 插入*/
    q->llink = head;
    q->rlink = head->rlink;
    head->rlink = q;
    q->rlink->llink = q;
}

第二部分：二叉树

  • 表达式 (a-(b+c))*(d/e) 存储在如图所示的一颗以二叉链表为存储结构的二叉树中，（二叉树结点的data域为字符型），编写程序求出该表达式的值（操作数均为一位整数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
             *
           /  \
          -    /
        /  \  /  \
        a  +  d  e
          / \
          b c 
*/
//分析：递归求值时，首先要知道，左子树的值，右子树的值，再根据根节点的运算符才可以进行下一步运算，故应采用后序遍历来解决此题
int comp(BTNode *p){
    int A, B;
    if(p != NULL){
        if(p->lchild != NULL&& p->rchild != NULL){
        /* 此二叉树为正则二叉树，若度为2，则子树为子表达式*/
            A = comp(p->lchild);
            B = comp(p->rchild);
            return op(A, B, p->data);//度为2的结点上，子树根节点为运算操作符
        }else
            return p->data - '0';//度为0的结点上，子树为操作数
    }
    else
        return 0;
}
  • 写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
//分析：已知一颗左子树的深度，和右子树的深度，如何算出整棵树的深度呢？（递归思想）
//左子树的深度为LD，右子树的深度为RD，则整棵树的深度就是max{LD,RD}+1
//需要得到左右子树的信息后再进行操作，故为后序遍历
int getDepth(BTNode *p) {
    int LD, RD;
    if (p != NULL)
        return 0;
    else {
        LD = getDepth(p->lchild);
        RD = getDepth(p->rchild);
        return (LD > RD ? LD : RD) + 1;
    }
}
  • 在一棵以二叉链表为存储结构的二叉树中，查找data域值等于key的结点，存在则用 q 指向该结点（找到任何一个即可），否则赋值为NULL，假设data域为int型。
1
2
3
4
5
6
7
8
9
10
11
12
//剪枝操作：当在左子树中找到满足的结点后，无需继续查找右子树
void search (BTNode *p, BTNode *&q, int key) {
    if (p != NULL) {
        if (p->data == key)
            q = p;
        else {
            search(p->lchild, q, key);
            if (q == NULL)
                search(p->rchild, q, key);
        }
    }
}
  • 假设二叉树采用二叉链表存储结构存储，设计一个算法，求出二叉树的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//下面定义的这个结构体为顺序非循环队列的队列元素，可以存储结点指针以及结点所在的层次号
typedef struct {
    BTNode  *p;     //结点指针
    int     lno;    //结点所在层次号
} St;
int maxNode(BTNode *p) {
    St que[maxSize];
    int front, rear;
    int Lno, i, j, n, max;
    front = rear = 0;
    BTNode *q;
    if (b != NULL) {
        ++rear;
        que[rear].p = b;
        que[rear].lno = 1;          //树根层次号设为1
        while (front != rear) {
            ++front;
            q = que[front].p;
            Lno = que[front].lno;   //Lno用来存储当前结点层号
            if (q->lchild != NULL) {
                ++rear;
                que[rear].p = q->lchild;
                //根据当前结点的层号推知其孩子结点的层号
                que[rear].lno = Lno + 1;
            }
            if (q->rchild != NULL) {
                 ++rear;
                que[rear].p = q->rchild;
                //根据当前结点的层号推知其孩子结点的层号
                que[rear].lno = Lno + 1;
            }
        }
        //注意：此时退出循环，Lno保存了结点的最大层数
        max = 0;
        for (i = 0; i <= Lno; ++i) {
            n = 0;
            for (j = 1; j <= rear; ++j) {
                if (que[j].lno == i)
                    ++n;
                if(max < n)
                    max = n;
            }
        }
        return max;
    } else
        return 0;
}
  • 假设二叉树采用二叉链表存储结构，设计一个算法，利用结点的右孩子指针 rchild，将一颗二叉树的叶子节点按照从左往右的顺序串成一个单链表，（在题目中定义两个指针 head 与 tail，head 初值为 NULL, head 指向第一个结点，tail 指向最后一个结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void link (BTNode *p, BTNode *&head, BTNode *&tail) {
    if (p != NULL) {
        if (p->lchild == NULL && p->rchild == NULL) {
            if (head == tail) {
                head = p;
                tail = p;
            } else {
                tail->rchild = p;
                tail = p;
            }
        }
        link(p->lchild, head, tail);
        link(p->rchild, head, tail);
    }
}
  • 在二叉树的二叉链式存储结构中，增加一个指向双亲结点的 parent 指针，设计一个算法，给这个指针赋值，并输出所有结点到根节点的路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//修改数据结构
typedef struct BTNode {
    char data;
    struct BTNode *parent;
    struct BTNode *lchild;
    struct BTNode *rchild;
} BTNode;

//给各个结点的 parent 指针赋值
void triBtree (BTNode *p, BTNode *q) {
    if (p != NULL) {
        p->parent = q;  //q初值为NULL
        q = p;          //让q一直为p的双亲
        triBtree(p->lchild, q);
        triBtree(p->rchild, q);
    }
}

//打印路径
//单个路径
void printPath(BTNode *p) {
    while (p != NULL) {
        printf("%c", p->data);
        p = p->parent;
    }
}
//所有结点路径
void printAllPath(BTNode *p) {
    if (p != NULL) {
        printPath(p);
        printAllPath(p->lchild);
        printAllPath(p->rchild);
    }
}
  • 假设满二叉树ｂ的先序遍历序列已经存在于数组中（名称自定义，长度为ｎ），设计一个算法将其转换为后序遍历序列。
1
2
3
4
5
6
7
void change (char pre[], int L1, int R1, char post[], int L2, int R2) {
    if (L1 <= R2) {
        post[R2] = pre[L1];
        change(pre, L1+1, (L1+R1+1)/2, post, L2, (L2+R2-1)/2);
        change(pre, (L1+R1+1)/2, R1, post, (L2+R2-1)/2, R2);
    }
}
  • 假设二叉树采用二叉链式存储结构，设计一个算法，求二叉树中，值为 x 的结点的层号。
1
2
3
4
5
6
7
8
9
10
11
int L;
void findElemNo(BTNode *p, char x) {
    if (p != NULL) {
        if (p->data == x)
            printf("%d", L);
        ++L;    //打印完后，p指针要进入下一层结点，故L要自增1
        findElemNo(p->lchild, x);
        findElemNo(p->rchild, x);
        --L;    //p指针将要由下一层返回到上一层，故L要自减1
    }
}
  • 设中序线索二叉树的类型为TBTNode* InThTree:<1>设计算法，在一棵中序线索二叉树中寻找结点t的子树上中序下的最后一个结点；<2>设计算法，在一棵中序线索二叉树中寻找结点t中序下的前驱；<3>设计算法，在一棵中序线索二叉树中寻找结点t前序下的后继。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//1>
TBTNode* inLast (TBTNode *t)
{
    TBTNode *p = t;
    while(p && !p->rtag)//p非空且p不为线索（rtag == 0）时
        p = p->rchild;
    return p;
}
//2>
TBTNode* inPrior (TBTNode *t)
{
    TBTNode *p = t->lchild;
    while(p && !p->ltag)
        p = inLast(p);
    return p;
}
//3>
TBTNode* treNext(TBTNode *t)
{
    TBTNode *p;
    if(!t->ltag)
        p = t->lchild;
    else if(!t->rtag)
        p = t->rchild;
    else//左右都为线索，则到了叶子结点
    {
        p = t;
        while(p && !p->rtag)
        /* 沿着线索一直找到第一个有右子树的祖先结点
         * 其第一个右孩子即为前序下的后继结点      */
            p = p->rchild;
        if(p)
            p = p->rchild;
    }
    return p;
}
  • 假设二叉树采用二叉链式存储结构，设计一个算法，输出根节点到每个叶子结点的路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 先全局定义一个用来存储路径的栈，由于采用先入栈根结点，故栈顶top值初值为0 */
char pathStack[maxSize];
int top = 0;
void allPath(BTNode *p)
{
    if(p != NULL)
    {
        pathStack[top] = p->data;
        ++top;  //p自上往下走时，结点入栈
        if(p->lchild == NULL && p->rchild == NULL)
        {       //p指向叶子结点时，打印路径
            for(int i = 0; i < top; ++i)
                printf("%c", pathStack[i]);
        }
        allPath(p->lchild);
        allPath(p->rchild);
        --top;  //p自下往上走时，结点出栈
    }
}