2025-12-20 数据结构重点例题分析

稀疏矩阵的三元组表

三元组表需要把行,列,值分别列出来(意义在哪里?)

甚至还要再写辅助数组rowSize和rowStart,把很明显的东西再写一遍,却又不考算法,没招了.

链表反转

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

void ReverseList(LinkList L)
{
    LNode* p = L->next;
    LNode* q;

    L->next = NULL;   // 断开头结点与原链表

    while (p != NULL)
    {
        q = p->next;      // 保存后继
        p->next = L->next;
        L->next = p;      // 头插
        p = q;            // 处理下一个结点
    }
}

贴下代码就能看懂了,其实我觉得就是两端交换

KMP

参考1
参考2
都讲的挺好.

重点是明确next数组的作用,之所以存储模式的对应字串最长公共前后缀,是因为当匹配失败时,原字符串中在匹配失败位置前的成功匹配部分刚好可以作为重置后的模式字符串的前缀,它同时也是先前匹配时得到对应长度模式字串的后缀.搞懂了这个就能彻底理解kmp了.

例题: 设主串T=”abaabaabcabaabc”，模式串P=”abaabc”，采用KMP算法进行模式匹配，到匹配成功为止，在匹配过程中进行的单个字符间的比较次数是（）.

解题: int num=0,
先写出next数组[0,0,1,1,2,0],第一次匹配到abaab,num+=5,但由于失败的匹配也要算上,num+=1
指针移到后缀ab,接着比较找到abaabc,num+=4,故num=10

组合数求解

【例4】编写一个递归算法，找出从自
然数1,2,3,4,…,n中任取r个数的所有组
合。例如，n=5，r=3时的组合是543，
542，541，532，531，521，432，431
，421，321.

【解答】本问题就是求解组合数。
int Combin(int m, int n)
{ if(mn||n0) return 1;
else return Combin(m-1,n)+
Combin(m-1,n-1);}

一开始是用dfs写的,但没想到ppt里根本没考虑把组合写出来,不过这个递归也挺难想到的.

广义表

假设广义表是由带头节点的链
表存储，请画出广义表A(a, B((),
C(1)))的存储结构；假设head，tail分
别是求首元素操作和求尾表操作，求
如何获得元素1.

其中,一个结点的定义如下:

utype = 0/1/2/3 ;
value = ref /intgrinfo /charinfo / hlink ;tlink

0表示该节点为头节点,1表示为整数,2表示为char,3表示为子表节点,∧表示该节点为尾节点,指向该子表头节点

int GenList :: depth ( GenListNode *ls ) {
if ( ls→tlink == NULL ) return 1; //空表
GenListNode *temp = ls→tlink;
int m = 0;
while ( temp != NULL ) {
 //横扫广义表
if ( temp→utype == LST ) {
 //子表深度
int n = depth ( temp→value.hlink );
if ( m < n ) m = n;
}
 //不是子表不加深度
temp = temp→tlink;
}
return m+1;
}

二叉链的应用

假设二叉树采用二叉链存储，设计一个算法Level()求二叉树中值为 x 的节点的层数。

int Level(BiNode *T, int x, int level) {
    if (!T) return 0;
    if (T->data == x) return level;

    int l = Level(T->lchild, x, level + 1);
    if (l) return l;

    return Level(T->rchild, x, level + 1);
}