部分问题例程

2015-09-09

基础数据结构中部分问题例程

摘要

例程

最大子序列和问题

给定一个整数数列A1,A2,,…,An，求∑ A(k) ( k from i to j ，0 <= i <= j <= n )的最大值。规定，当所有整数均为负数，则结果为0。

以下共四种代码，时间复杂度由高到低。
O( N^3 )代码，枚举所有的子序列

int MaxSubsequenceSum( const int A[], int N){
    int tempSum, MaxSum = 0, i, j, k;
    for ( i = 0 ; i < N ; i++ )
        for ( j = 0 ; j < N ; j++ ){
            tempSum = 0;
            for ( k = i ; k < j ; k++ )
                tempSum += A[k];
            if ( tempSum > MaxSum )
                MaxSum = tempSum;
        }
    return MaxSum;
}

O( N^2 )代码，由∑(i->j) = ∑(i->j-1) + Aj 可简化上述代码一层循环

int MaxSubsequenceSum( const int A[], int N){
    int tempSum, MaxSum = 0, i, j;
    for ( i = 0 ; i < N ; i++ ){
        tempSum = 0;
        for ( j = i ; j < N ; j++ ){
            tempSum += A[j];
            if ( tempSum > MaxSum )
                MaxSum = tempSum;
        }
    }
    return MaxSum;
}

O( NlogN )代码，分治。MaxSubsequence只可能出现在1.整个序列的最左端，2.整个序列的最右端，3.中间的某一段。对于一段序列，将其一分为二后，只需要比较两个序列各自的MaxSubsequenceSum，之后再和某个中间的最大子序列比较，中间最大子序列的判定：包含左半部分最后一个数的最大和子序列和包含右半部分第一个数的最大和子序列相连接。

static MAX3( int a, int b, int c ){
    a = a > b ? a : b ;
    return a > c ? a : c ;
}
static int Partition( const int A[], int l, int r){
    if ( l == r ) // Only one number
        if ( A[l] > 0 )
            return A[l];
        else 
            return 0;
    int MaxL, MaxR;
    int MaxLBorder = 0 , MaxRBorder = 0 , tempLBorder = 0 , tempRBorder = 0;
    int mid = ( l + r ) >> 1, i;
    MaxL = Partition( A, l, mid );
    MaxR = Partition( A, mid + 1, r );
    for ( i = mid ; i >= l ; i-- ){
        tempLBorder += A[i];
        if ( tempLBorder > MaxLBorder )
            MaxLBorder = tempLBorder;
    }
    for ( i = mid + 1 ; i <= r ; i++ ){
        tempRBorder += A[i];
        if ( tempRBorder > MaxRBorder )
            MaxRBorder = tempRBorder;
    }
    return MAX3( MaxL , MaxR , MaxLBorder + MaxRBorder );
}
int MaxSubsequence( const int A[], int N ){
    return Partition( A , 0 , N - 1 );
}

O( N ) 代码，正确性容易理解。以上三份代码均为离线算法，此代码满足联机特性（不需要记忆数据，顺序读入的同时处理数据）。

int MaxSubsequenceSum( const int A[], int N ){
    int tempSum = 0, MaxSum = 0, i;
    for ( i = 0 ; i < N ; i++ ){
        tempSum += A[i];
        if ( tempSum > MaxSum )
            MaxSum = tempSum;
        else if ( tempSum < 0 )
            tempSum = 0;
    }
    return MaxSum;
}

单向链表的类型声明及其ADT操作

类型声明（模拟整型数组）

typedef struct Node{
    int value;
    struct Node* next;
}Node;

#ifndef _List_
Node * MakeEmpty( Node * L );
Node * Find( int toFind, Node * L );
Node * FindPrevious( int present, Node * L );
Node * head; // need to malloc
int IsEmpty( Node * L );
int IsLast( Node * present, Node * L );
void Insert( int x, Node * L, Node * insertP );
void Delete( int x, Node * L );
void DeleteList( Node * L );

#endif    /* _List_ */

ADT操作实现

int IsEmpty( Node * L ){
    return L->next == NULL;
}            /* return true if L is empty */

int IsLast( Node * present, Node * L ){
    return P->next == NULL;
}

Node * Find( int toFind, Node * L ){
    Node * P = L->next;
    while ( P != NULL && P->value != toFind ) /* 1 */
        P = P->next;
    return P;
    /* 1.   if P == NULL, then the check after && won't run */
}

Node * FindPrevious( int present, Node * L ){
    Node * P = L;
    while ( P->next != NULL && P->next->value != toFind ) /* 1 */
        P = P->next;
    return P;
}

void Insert( int x, Node * L, Node * insertP ){
    Node * temp = ( Node * )malloc( sizeof ( Node ) );
    if ( temp == NULL )
        FatalError("flood");
    temp->value = x;
    temp->next = insertP->next;
    insertP->next = temp;
}

void Delete( int x, Node * L ){
    Node * P = FindPrevious( x, L );
    Node * temp;
    if ( !IsLast( P, L ) ){
        temp = P->next;
        P->next = temp->next;
        free( temp );
    }
}

void DeleteList( Node * L ){
    Node * P = L->next, temp;
    L->next = NULL;
    while ( P != NULL ){
        temp = P->next;
        free( P );
        P = temp;
    }
}

链表实现基数排序

基数排序（卡式排序）
有N个整数，范围从0~M-1，对其进行排序。

小学生排序法（计数排序）是桶数为M的简单的基数排序，时间复杂度O(N+M)。
基数排序按照位优先的方式进行桶式排序，假设有10个桶0~9，输入样例为243 2434 24 1328 41 72 385 3902 903 3，随便敲的数。先按照最低位排序，得表如下
0 1 2 3 4 5 6 7 8 9
41 72
3902 243
903
3 2434
24 385 1328

之后按照次最低位（十位）排序，得表如下
0 1 2 3 4 5 6 7 8 9
3
903
3902 24
1328 2434 41
243 72 385

按照百位排序，得表如下
0 1 2 3 4 5 6 7 8 9
72
41
24
3 243 1328
385 2434 3902
903

按照千位排序，得表如下
0 1 2 3 4 5 6 7 8 9
903
385
243
72
41
24
3 1328 2434 3902

每次排序过程中都只有N个数据节点之间的交换，整个算法时间复杂度为O(H*P)，其中P为桶数，H为数据以P进制表示可以达到的最高位数。上例中H为4（最高位千位），P为10。
降序排列代码如下

/*
 * @author Forec
 * Test radix sorting
 */
#include <stdio.h>
#include <stdlib.h>
const int MaxLen = 200;
typedef struct node
{
	int value;
	struct node * next;
}node;
node head[10];
int main(){
	int input[MaxLen];
	int n, i, j, max = 0;
	for ( i = 0 ; i <= 9 ; i++)
		head[i].next= NULL;
	scanf("%d",&n);
	for ( i = 0 ; i < n ; i ++){
		scanf("%d",input+i);
		node * temp = (node*)malloc(sizeof(node));
		if ( temp == NULL){
			printf("NULL error");
			exit(0);
		}
		temp->next= head[input[i]%10].next;
		temp->value = input[i];
		head[input[i]%10].next = temp;
		if ( input[i] > max)
			max = input[i];
	}
	int base = 1, h = 0;
	while ( max / base != 0 ){
		base *= 10;
		h++;
	}
	int baseh = 100,basel = 10;
	for ( i = 2 ; i <= h ; i++){
		for ( j = 0 ;  j <=9 ; j++){
			node * pre = head+j;
			node * temp= head[j].next;
			while (temp!=NULL){
				int pos = (temp->value%baseh)/basel;
				if ( pos != j ){
					pre->next = temp->next;
					temp->next = head[pos].next;
					head[pos].next = temp;
					temp = pre->next;
				}
				else {
					pre = temp;
					temp = temp->next;
				}
			}
		}
		baseh*=10;
		basel*=10;		
	}
	for ( j = 9 ; j >= 0 ; j --){
		node *temp = head[j].next;
		while ( temp != NULL){
			printf("%d ",temp->value);
			temp = temp->next;
		}
	}
}

逆波兰表达式

实现步骤
1. 给出中缀表达式，如 3*(1/4+2)

定义两个栈（符号入栈in和操作出栈out）
从左至右读取中缀表达式，读入数字直接压入出栈（out），读入第一个运算符直接压入入栈（in），读入’(‘直接压入入栈（in）。
按上述规则读取若干次后，此时栈in中为{,(,/},栈out中为{3,1,4}，读入操作符’+’，与栈顶操作符’/‘比较，因’+’优先级低于’/‘，将in出栈至out，直到in的栈顶为比’+’优先级低的预算操作符或’(‘，再将’+’压入in。此时in中为{,(,+}，out中为{3,1,4,/}。即： 高于栈顶运算符级别的算符直接进栈，低于或等于栈顶级别的要将in按次压入out，直到in的栈顶操作符优先级低于当前操作符。
最后读取”)”时要找到入栈in中最近的”(“，将括号内符号按后进先出的顺序全部压入出栈out，此时两栈的数据为：in[]，out[3,1,4,/,+,*]。
系统读取中缀表达式结束后将入栈in中的所有符号出栈并依次压入出栈out中。

栈ADT的链表实现

类型声明（以整型数据为例）

typedef struct Node{
    int value;
    struct Node *next;
}Node;

#ifndef _Stack_
int IsEmpty( Node * S );
void MakeEmpty( Node * S );
void Push( int x, Node * S );
void Pop( Node * S );
int Top( Node * S );
Node * CreateStack( void );
#endif   /* _stack_ */

实现代码

int IsEmpty( Node * S ){
    return S->next == NULL;
}

int Top( Node * S ){
    if ( !IsEmpty( S ) )
        return S->next->value;
    Error("Empty Stack");
    return 0;
}

void Pop( Node * S ){
    if ( IsEmpty( S ) )
        Error("Empty Stack");
    else {
        Node * temp = S->next;
        S->next = temp->next;
        free( temp );
    }
}

void MakeEmpty( Node * S ){
    if ( S == NULL )
        Error("NULL Exception");
    else 
        while( !IsEmpty( S ) )
            Pop( S );
}

Node * CreateStack(){
    Node * S = ( Node * )malloc( sizeof ( Node ) );
    if ( S == NULL )
        FatalError("flood");
    S->next = NULL;
    MakeEmpty( S );
    return S;
}

void Push( int x, Node * S ){
    Node * temp = ( Node * ) malloc ( sizeof( Node ) );
    if ( temp == NULL )
        FatalError("flood");
    else {
        temp->value = x;
        temp->next = S->next;
        S->next = temp;
    }
}

栈ADT的数组实现

类型声明（以整型数据为例）

typedef struct Stack{
    int top;
    int cap;
    int *array;
}Stack;

#ifndef _Stack_
int IsEmpty( Stack * S );
int IsFull( Stack * S );
Stack * CreateStack( int MaxLen );
void Push( int x, Stack * S );
void Pop( Stack * S );
void MakeEmpty( Stack * S );
int Top( Stack * S );
#endif    /* _Stack_ */

实现代码

void MakeEmpty( Stack * S ){
    S->top = 0;
} 

Stack * CreateStack( int MaxLen ){
    Stack * S = ( Stack * ) malloc ( sizeof ( Stack ) );
    if ( S == NULL )
        FatalError("flood");
    S->array = ( int * ) malloc ( sizeof( int ) * MaxLen );
    if ( S->array == NULL){
        FatalError("flood");
    S->cap = MaxLen;
    MakeEmpty( S );
    return S;
}

int IsEmpty( Stack * S ){
    return S->top == 0;
}

int IsFull( Stack * S ){
    return S->top > S->cap;
}

void Push( int x, Stack * S ){
    if ( IsFull( S ) )
        Error("Full Stack");
    else
        S->array[ S->top++ ] = x;
}
int Top( Stack * S ){
    if ( !IsEmpty( S ) )
        return S->array[ S->top - 1 ];
    Error("Empty Stack");
    return 0;
}

void Pop( Stack * S ){
    if ( IsEmpty( S ) )
        Error("Empty Stack");
    else 
        S->top--;
}

约瑟夫环问题（队列链表模拟实现）

n个整数（1~n）围成一圈，从1开始，每隔m个数则出列。输出最后一个数。如n=3，m=2，则3最先出列(1,2,3)，之后1出列(1,2,1)，最后一个数为2。

代码如下

/*
 * @author Forec
 * Test Joseph
 */
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
	int num;
	struct node * next;
}node;
int main(int argc, char const *argv[])
{
	int n, m, i;
	scanf("%d %d",&n,&m);
	node * front = ( node * )malloc( sizeof( node ) );
	node * rear = front;
	front->num = 1;
	node * temp;
	for ( i = 2 ; i <= n ; i++ ){
		temp = ( node * )malloc( sizeof( node ) );
		temp->num = i;
		temp->next = NULL;
		rear->next = temp;
		rear = temp;
	}
	rear->next = front;
	temp = front;
	while ( --n ){
		for ( i = 0 ; i < m ; i++ ){
			temp = temp->next;
			rear = rear->next;
		}
		rear->next = temp->next;
		free(temp);
		temp = rear->next;
	}
	printf("%d\n", temp->num );
	return 0;
}

队列ADT的代码实现

类型声明（数组模拟，循环队列）

typedef struct Queue{
    int cap;
    int front;
    int fear;
    int size;
    int *array;
}Queue;

#ifndef _Queue_
int IsEmpty( Queue * Q );
int IsFull( Queue * Q );
int Front( Queue * Q );
void Dequeue( Queue * Q );
void Enqueue( int x, Queue * Q );
void MakeEmpty( Queue * Q );
Queue * CreateQueue( int MaxLen );
#endif

代码实现

int IsEmpty( Queue * Q ){
    return Q->size == 0 ;
}

int IsFull( Queue * Q ){
    return Q->size == Q->cap;
}

void MakeEmpty( Queue * Q ){
    Q->size = 0;
    Q->front = 1;
    Q->rear = 0;
}

void Enqueue( int x, Queue * Q ){
    if ( IsFull( Q ) )
        Error("Full Queue");
    else{
        Q->size++;
        Q->rear = ( Q->rear + 1 ) % Q->cap;
    }
}

void Dequeue( Queue * Q ){
    if ( IsEmpty( Q ) )
        Error("Empty Queue");
    else{
        Q->size--;
        Q->front = ( Q->front + 1 ) % Q->cap;
    }
}

Queue * CreateQueue( int MaxLen ){
    Queue * temp = ( Queue * ) malloc ( sizeof ( Queue ) );
    if ( temp == NULL )
        FatalError("flood");
    temp->cap = MaxLen;
    temp->array = ( int * ) malloc ( sizeof( int ) * MaxLen );
    if ( temp->array == NULL )
        FatalError("flood");
    MakeEmpty( temp );
    return temp;
}

int Front( Queue * Q ){
    return Q->array[ Q->front ];
}

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2015/09/09/Data-Structure-example1/) 、作者信息（Forec）和本声明。

0	1	2	3	4	5	6	7	8	9
	41	72 3902	243 903 3	2434 24	385			1328

0	1	2	3	4	5	6	7	8	9
3 903 3902		24 1328	2434	41 243			72	385

0	1	2	3	4	5	6	7	8	9
72 41 24 3		243	1328 385	2434					3902 903

0	1	2	3	4	5	6	7	8	9
903 385 243 72 41 24 3	1328	2434	3902

Code

摘要

例程

最大子序列和问题

单向链表的类型声明及其ADT操作

链表实现基数排序

逆波兰表达式

栈ADT的链表实现

栈ADT的数组实现

约瑟夫环问题（队列链表模拟实现）

队列ADT的代码实现