DUAN的专栏

题目：将十进制数 src 转换为 k 进制数。原理：N = ( N div k ) x k + N mod k，其中div为整除，mod为取余。void num_sys_convert( int src, int k ){ link_stack ls; init_stack_link( &ls ); while( src != 0 ) { push_link( &ls,

C语言版#include #define SWAP( a, b ) { t = a; a = b; b = t; }#define LESS( a, b ) a < bvoid disp_array( int a[], int n );void bubble_sort( int a[], int n ){ int i, j, t; int flag = 1; /

#include #include typedef struct bitree_node{ char data; struct bitree_node * lchild, * rchild;}bitree_node, *binary_tree;int locate_data( char arr[], int left, int right, char key ){

C语言版 #include #define SWAP( a, i, j ) { t = a[i]; a[i] = a[j]; a[j] = t; }void disp_array( int a[], int n ){ int i; for( i = 0; i < n; ++i ) printf( "%d ", a[i] );

1、Huffman树结构定义#ifndef _huffman_tree_h#define _huffman_tree_htypedef struct huffman_tree_node{ float weight; int lchild, rchild, parent;}huffman_tree_node, * huffman_tree;typedef st

1、顺序栈的声明#ifndef _seq_stack_h#define _seq_stack_h#include "binary_tree.h"#define STACK_INIT_SIZE 5#define STACK_INCR_SIZE 2typedef bitree_node * stack_elem_type;//typedef int stack_

编写程序实现从终端接收用户输入的数据，并存入用户数据区。输入#表示上一字符无效，输入@表示当前输入行整行无效。/* * line editor by using stack. * * fduan, Dec. 31, 2011. */void line_editor(){ using std::stack; stack ss; std::string li

最小堆本质上是一棵局部有序的完全二叉树，适于需要查找序列中前k小的元素的场合，如构造Huffman树。核心算法为 向上调整（fix up）和向下调整（fix down）算法。void fix_up_min_heap( int arr[], int n, int len, int i ){ int j = ( i - 1 ) / 2; // parent index int tmp =

C语言版 #include void disp_array( int a[], int n ){ int i; for( i = 0; i < n; ++i ) printf( "%d ", a[i] ); printf( "\n" );}int partition( int a[], int low, int high ){ in

C语言版#include #define SWAP( a, i, j ) { t = a[i]; a[i] = a[j]; a[j] = t; }#define LESS( a, b ) ( a < b ) void disp_array( int a[], int n ){ int i; for( i = 0; i < n; ++i ) printf( "%d ",

题目：假设表达式中允许出现圆括号和方括号，其嵌套顺序随意，设计算法检验给定表达式中的括号是否匹配。/* * Brackets matching algorithm by utilizing stack. * * fduan, Dec. 31, 2011. */bool is_pair( char c1, char c2 ){ return ( c1 == '(' && c2

1、链式栈ADT的定义#ifndef _link_stack_h#define _link_stack_htypedef int elem_type;struct stack_node;typedef struct stack_node stack_node;typedef stack_node * snode_ptr;typedef stack_node * link_sta

1、多项式结构定义polynomial.h#ifndef _polynomial_h#define _polynomial_hstruct poly_term{ int expn; int coef;};typedef struct poly_term poly_term;typedef poly_term * poly_term_ptr;struct poly_n

数据结构题典005：单链表的复制（ANSI C）void clone_node( node_ptr src, node_ptr * dst ){ if( src != NULL ) { *dst = ( node_ptr )malloc( sizeof( node ) ); (*dst)->data = src->data; } else *dst = NULL;}

1、有序顺序表的归并排序，假设a[0] void merge_list( int a[], int m, int b[], int n, int ** c ){ int i = 0, j = 0; int *pa = a, *pb = b, *pc = NULL, *qa = a + m - 1, *qb = b + n - 1; if( *c != NULL )

假设有顺序表 L.elem[] = { a_1, a_2, ..., a_m, | b_1, b_2, ..., b_n }，设计算法将L的两部分元素互换，使得 L.elem[] = { b_1, b_2, ..., b_n, |a_1, a_2, ..., a_m }思路一：循环移位，数组整体循环右移n个元素void circ_right_shift( int c[], int len,

1、顺序表a) 通过数组下标访问元素/* * 通过数组下标访问 */void reverse_sqlist( int c[], int n ){ int i = 0, j = n - 1; int t; for( ; i < j; ++i, --j ) { t = c[i]; c[i] = c[j]; c[j] = t; }}b) 通过指针访问元素/

1、顺序表，假设元素已按升序排序/* * remove redundant elements from ordered sequence */int remove_redundant_elem( int c[], int n ){ int i = 0, j = 1; while( j < n ) { if( c[i] != c[j] ) c[++i]

分析：此题关键在于找到最大元素所在的前驱结点。status_code remove_max_elem_llist( link_list * lst, elem_type * e ){ status_code res = Success; node_ptr h = *lst, p = h, pre_max = p; int max_v = -1000; while( p->next

这是一道面试题，要求用最简洁的代码写出判别单链表中是否存在环。我是这样做的，可将单链表视作一种简化的图，在依照链表指针域遍历链表时，保留每个结点的入度，若在到达尾结点之前出现入度为2的结点，说明链表中存在环，同时终止遍历。/* * 判别单链表中是否存在环 */#include using std::map;typedef int elem_type;struct Node

1、首先定义公共头文件common.h，其中包含了枚举类型status_code的定义，目的是将其作为循环链表结构操作的返回类型。#ifndef _common_h#define _common_henum status_code { Success, Fail, MemoryOut, NotPresent, RangeError };typedef enum status_co

1、double_link_list.h#ifndef _double_link_list_h#define _double_link_list_h#include "common.h"typedef int elem_type;struct node;typedef struct node node;typedef node * node_ptr;typedef no

注：代码注释及说明待补充……   结构声明typedef int elem_type;struct LNode{ elem_type elem; LNode * next;};typedef LNode * circ_list; 基本操作status_code init_list( circ_list & lst ){ lst = (circ_list)mal

带头结点的单链表void insert_sort_llist( link_list * lst ){ node_ptr h = *lst, p = h->next, r = NULL, q = NULL; h->next = NULL; while( p != NULL ) { q = p->next; r = h; while( r->next != NULL && r

题意：设有顺序表La和Lb，二者中元素均为非递减有序，空间足够大。设计算法将Lb中的元素合并到La中，使新的La元素仍非递减有序。分析：此题与将两个有序顺序表合并到第三个顺序表中的思路类似，只是为了减少移动次数，比较的次序从两线性表的尾部开始，这样每个元素最多只移动一次。/* * merging of two ordered sequences * * fduan, Dec. 27,

设所考虑单链表含头结点，写出逆序输出表中元素的递归算法。void inv_trav_recur( link_list p ){ if( p != NULL ) { inv_trav_recur( p->next ); printf( "%d ", p->data ); }}void inverse_traverse_llist( link_list lst ){ i

1、顺序栈ADT定义#ifndef _seq_stack_h#define _seq_stack_h#define STACK_INIT_SIZE 100#define STACK_INCR_SIZE 10typedef struct seq_stack{ int * base; int * top; int size;}seq_stack;void init_sta

题目：设有三个带头结点的元素按非递减有序排列的单链表A, B, C，对A进行如下操作，使A中仅含有三个表中的交，且没有值相同的结点，并释放无用结点。限定时间复杂度为O( m + n + p )，其中m, n, p分别为三个表的长度。/* * Intersection of three ordered linked lists. * * fduan, Dec. 29, 2011.

题目：从无序的输入数据中建立一个递增有序的顺序表。int order_insert_array( int x[], int e, int n, int m ){ int len = m, pos, i; if( m == 0 ) x[len++] = e; else { i = 0; while( i < m && x[i] < e ) ++i; pos = (

题目：设有两个整数序列 A = a_1, a_2, ..., a_m和 B = b_1, b_2, ..., b_n已存入两个单链表，设计算法判断序列B是否为序列A的子序列。int is_subseq_llist( link_list lst_a, link_list lst_b ){ node_ptr pa = lst_a->next, pb = lst_b->next; while(

问题：已知两个按元素递增排列的链表，求二者交集，要求将结果放入第一个链表中。/* * Intersection of two ordered linked lists. * * fduan, Dec. 28, 2011. */void intersect_v2( link_list * lst_a, link_list lst_b ){ node_ptr pa = *lst_a

题目：与009类似，但这次是求并集。分析：与有序顺序表归并思路类似，只是注意要处理两个顺序表当前指针指向的元素相同的情形（此时只为并集中增加一项）。/* * Union set of two linked lists which have non-descending order. * * fduan, Dec. 28, 2011. */void calc_union( lin

题目：按递增次序输出单链表所有元素，并释放结点的存储空间。要求不使用数组做辅助空间。#include void min_elem( link_list * lst, node_ptr * min_prev, node_ptr * min_ptr ){ node_ptr p = (*lst)->next, prev = NULL; elem_type min_v = INT_MAX;

题目：设有两个元素递增的单链表（带头结点），编写算法将二者合并为按元素递减排列的链表L，要求利用原表的结点空间存放L。/* * fduan, Dec. 28, 2011. */void calc_union_v2( link_list * lst_a, link_list * lst_b ){ node_ptr pa = *lst_a, pb = *lst_b, p = NULL;

题目：设有两个非递减有序的单链表，编写算法求二者的交集（以链表形式存放），要求交集中元素保持递增有序。分析：此题关键是要跳过相邻的重复元素。/* * Intersection of two non-descending linked lists. * * fduan, Dec. 28, 2011. */void intersection( link_list lst_a, l

Using static linked list is an alternative solution when the programming language you are using does not supportpointer operations. This short article gives some key operations of the static linked