How to get Post_Order from In_Order and Pre_Order?

留下评论

// PP32.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace std;

int GetKey(const char & c)
{
    if (c >= ‘a’)
    {
        return (c – ‘a’ + 26);
    }
    else
    {
        return (c – ‘A’);
    }
}

void Post_Order(const char * pre_order, const char * in_order, char * post_order, int len)
{
    int indexes[52];
    int lens[52];
    int newIndexes[52];
 ::memset(indexes, 0, 52 * sizeof(int));
 ::memset(lens, 0, 52 * sizeof(int));
 ::memset(newIndexes, 0, 52 * sizeof(int));
    int i;
    for (i = 0; i < len; ++i)
    {
        indexes[GetKey(in_order[i])] = i;
    }

    lens[GetKey(pre_order[0])] = len;
    post_order[len – 1] = pre_order[0];
    newIndexes[GetKey(pre_order[0])] = len – 1;
 
 int rightLen;
 int leftLen;
 char leftRoot;
 char rightRoot;
 char rightSibling;
    for (i = 0; i < len; ++i)
    {
  if (lens[GetKey(pre_order[i])] == 1)
  {
   continue;
  }
  rightLen = 0;
  if (i != 0)
  {
   char parent;
   if (((GetKey(pre_order[i]) + 1) < len) && (post_order[newIndexes[GetKey(pre_order[i])] + 1] != 0))
   {
    // The current node is the right child root. And the right of it in the post_order is its parent or direct sibling.
    parent = post_order[newIndexes[GetKey(pre_order[i])] + 1];
    if (parent == rightSibling)
    {
     parent = pre_order[i – 1];
    }
   }
   else
   {
    // The current node is the left child root. And the left of it in the pre_order is its parent.
    parent = pre_order[i – 1];
   }

   int relative = indexes[GetKey(parent)] – indexes[GetKey(pre_order[i])];
   if (relative > 0)
   {
    rightLen = relative – 1;
    leftLen = lens[GetKey(pre_order[i])] – rightLen – 1;
   }
   else
   {
    leftLen = -relative – 1;
    rightLen = lens[GetKey(pre_order[i])] – leftLen – 1;
   }
  }
  else
  {
   rightLen = lens[GetKey(pre_order[i])] – indexes[GetKey(pre_order[i])] – 1;
   leftLen = lens[GetKey(pre_order[i])] – rightLen – 1;
  }
  if (leftLen > 0)
  {
         leftRoot = pre_order[i + 1];
         lens[GetKey(leftRoot)] = leftLen;
         post_order[newIndexes[GetKey(pre_order[i])] – rightLen – 1] = leftRoot;
   newIndexes[GetKey(leftRoot)] = newIndexes[GetKey(pre_order[i])] – rightLen – 1;
  }
  if (rightLen > 0)
  {
         rightRoot = pre_order[i + leftLen + 1];
         lens[GetKey(rightRoot)] = rightLen;
         post_order[newIndexes[GetKey(pre_order[i])] – 1] = rightRoot;
   newIndexes[GetKey(rightRoot)] = newIndexes[GetKey(pre_order[i])] – 1;
   rightSibling = rightRoot;
  }
  else
  {
   rightSibling = 0;
  }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
 
 char * res = new char[3];

 ::memset(res, 0, 3 * sizeof(char));
 ::Post_Order("ABC", "BAC", res, 3);
 cout << "Expected: " << "BCA" << endl;
 cout << "The actual post_order is :" << res << endl;

 ::memset(res, 0, 3 * sizeof(char));
 ::Post_Order("ABC", "CBA", res, 3);
 cout << "Expected: " << "CBA" << endl;
 cout << "The actual post_order is :" << res << endl;

 ::memset(res, 0, 3 * sizeof(char));
 ::Post_Order("ABC", "BCA", res, 3);
 cout << "Expected: " << "CBA" << endl;
 cout << "The actual post_order is :" << res << endl;
 
 ::memset(res, 0, 3 * sizeof(char));
 ::Post_Order("ABC", "ACB", res, 3);
 cout << "Expected: " << "CBA" << endl;
 cout << "The actual post_order is :" << res << endl;

 ::memset(res, 0, 3 * sizeof(char));
 ::Post_Order("ABC", "ABC", res, 3);
 cout << "Expected: " << "CBA" << endl;
 cout << "The actual post_order is :" << res << endl;
 
 delete[] res;

 char * res1 = new char[4];
 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "DCBA", res1, 4);
 cout << "Expected: " << "DCBA" << endl;
 cout << "The actual post_order is :" << res1 << endl;
 
 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "CDBA", res1, 4);
 cout << "Expected: " << "DCBA" << endl;
 cout << "The actual post_order is :" << res1 << endl;
 
 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "CBAD", res1, 4);
 cout << "Expected: " << "CBDA" << endl;
 cout << "The actual post_order is :" << res1 << endl;
 
 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "BCAD", res1, 4);
 cout << "Expected: " << "CBDA" << endl;
 cout << "The actual post_order is :" << res1 << endl;
 
 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "BADC", res1, 4);
 cout << "Expected: " << "BDCA" << endl;
 cout << "The actual post_order is :" << res1 << endl;

 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "BACD", res1, 4);
 cout << "Expected: " << "BDCA" << endl;
 cout << "The actual post_order is :" << res1 << endl;
 
 ::memset(res1, 0, 4 * sizeof(char));
 ::Post_Order("ABCD", "ABCD", res1, 4);
 cout << "Expected: " << "DCBA" << endl;
 cout << "The actual post_order is :" << res1 << endl;
 delete[] res1;
 
 char * res2 = new char[15];
 ::memset(res2, 0, 15 * sizeof(char));
 ::Post_Order("ABCDEFGHIKLNMJ", "DCFEBGAHNLKMIJ", res2, 14);
 cout << "Expected: " << "DFECGBNLMKJIHA" << endl;
 cout << "The actual post_order is :" << res2 << endl;
 delete[] res2;

 char * res3 = new char[7];
 ::memset(res3, 0, 7 * sizeof(char));
 ::Post_Order("ABCDEF", "CBAEDF", res3, 6);
 cout << "Expected: " << "CBEFDA" << endl;
 cout << "The actual post_order is: " << res3 << endl;
 delete[] res3;

 
 char * res4 = new char[4];
 ::memset(res3, 0, 4 * sizeof(char));
 ::Post_Order("xYz", "Yxz", res4, 3);
 cout << "Expected: " << "Yzx" << endl;
 cout << "The actual post_order is: " << res4 << endl;
 delete[] res4;

 
  return 0;
}

Advertisements

Visual Studio .NET 启动时”the application cannot start.”的解决办法

留下评论

一般IDE不能启动有以下两种原因:
1.不能加载msxml3.dll
2.不能加载mso.dll

*不能加载msxml3.dll

该种问题我相信最多,应该是无法创建Msxml2.DOMDocument对象造成的,
可以用下面的代码进行检验你的系统:
Set x = CreateObject("Msxml2.DOMDocument")

并且装msxml 4是无法解决的,因为msxml 4是side by side安装的,重新安装Component Update或IE6也无法解决。

对此,解决步骤是:

准备:
msxml3.exe 如果已经有system32\msxml3.dll则不需要了
xmlinst.exe 可以到ms下载

运行以下命令
1.xmlinst -u
2.regsvr32 msxml.dll
3.regsvr32 msxml2.dll
4.regsvr32 msxml3.dll
5.xmlinst
6.regsvr32 msxml4.dll  如果有msxml4.dll的话

*不能加载mso.dll

.确定没有运行Microsoft Office XP beta release
.运行一遍Office XP的修复安装
.确定下列注册项是否正确
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\VisualStudio\7.0\Path]
"MSO"="C:\Program Files\Common Files\Microsoft Shared\Office10\MSO.DLL"

转载:http://support.microsoft.com/kb/306905

(续)Return the first non-repeatable character in a literal string.

留下评论

void Exchange(int a[], int i, int j)
{
 char temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}
void GetFirstOne(char a[], int len)
{
 int perf = 0;
 int * b = new int[len];
 int i;
 for (i = 0; i < len; ++i)
 {
  b[i] = i;
 }

 int *c = new int[len];
 int cLen = 0;

 int start = 0;
 int end = len – 1;

 bool isFound;
 int pos = 0;
 while (pos < len)
 {
  isFound = false;
  for (i = 0; i < cLen; ++i)
  {++perf;
   if (a[b[c[i]]] == a[pos])
   {
    isFound = true;
    break;
   }
   else if (a[b[c[i]]] < a[pos])
   {
    if (i > 0)
    {
     start = c[i – 1] + 1;
    }
    else
    {
     start = 0;
    }
    end = c[i] – 1;
    break;
   }
  }
  if (!isFound)
  {
   if (cLen != 0 && i == cLen)
   {
    start = ((c[i – 1] + 1) > (pos + 1)) ? (c[i – 1] + 1) : (pos + 1);
    end = len – 1;
   }
   int pivot;
   while (start <= end)
   {++perf;
    // DESC
    while (start <= end && a[b[start]] >= a[pos])
    {++perf;
     if (a[b[start]] == a[pos])
     {
      if (b[start] != pos)
      {
       isFound = true;
      }
      break;
     }
     ++start;
    }
    while (end >= start && a[b[end]] <= a[pos])
    {++perf;
     if (a[b[end]] == a[pos])
     {
      if (b[end] != pos)
      {
       isFound = true;
      }
      else
      {
       pivot = end;
      }
     }
     –end;
    }
    if (start <= end)
    {
     Exchange(b, start, end);
    }
   }
   Exchange(b, pivot, end + 1);

   if (!isFound)
   { 
    cout << endl << "perf = " << perf << endl;
    cout << "The wanted char is: " << a[pos] << endl;
    cout << "+++++++++++++++++++++++++++++++" << endl;
    return;
   }   

   int temp = 0;
   while (temp < cLen && c[temp] < (end + 1))
   {
    ++temp;
   }
   if (temp == cLen)
   {
    c[temp] = end + 1;
    ++cLen;
   }
   else
   {
    for (i = cLen; i> temp; –i)
    {
     c[i] = c[i – 1];
    }
    c[temp] = end + 1;
    ++cLen;
   }
  }    
  ++pos;
 }
 delete[] b;
 delete[] c;
}

Return the first non-repeatable character in a literal string.

留下评论

#include <iostream>

using namespace std;

typedef struct ABC
{
    int index;
    int count;
} ABC;

void GetTheFirst(char a[], int len)
{
    if (len == 0)
    {
        return;
    }

    ABC *b = new ABC[len];
    int bLen = 1;
    b[0].index = 0;
    b[0].count = 1;

    int perf = 0;
    for (int i = 1; i < len; ++i)
    {
        int start = 0;
        int end = bLen – 1;
        int pos = 0;
        bool isFound = false;
        while (start <= end)
        {
            ++perf;
            pos = ((start + end) / 2);
            if (a[b[pos].index] == a[i])
            {
                isFound = true;
                b[pos].index = i;
                ++(b[pos].count);
                break;
            }
            else if (a[b[pos].index] > a[i])
            {
                start = pos + 1;
            }
            else
            {
                end = pos – 1;
            }
        }
        if (!isFound)
        {
            ++bLen;
            int temp = bLen – 1;
            while (temp >= start)
            {
                b[temp + 1] = b[temp];
                –temp;
            }
            b[start].index = i;
            b[start].count = 1;
        }
    }

    cout << endl;

    int index = len – 1;
    for (int i = 0; i < bLen; ++i)
    {
        cout << b[i].index << " " << a[b[i].index] << " " << b[i].count << endl;
        if (b[i].count == 1 && index > b[i].index)
        {
            index = b[i].index;
        }
    }

    delete[] b;
    cout << "+++++++++++++++++++++++++++++++" << endl;
    cout << "len = " << len << endl;
    cout << "perf = " << perf + bLen << endl;
    cout << "index = " << index << endl;
    cout << endl;
}

void GetTheFirst1(char a[], int len)
{
    int perf = 0;
    bool *b = new bool[len];
    for (int i = 0; i < len; ++i)
    {
        b[i] = true;
    }
    for (int i = 0; i < len; ++i)
    {
        if (b[i])
        {
            int j;
            bool isFound = false;
            for (j = i + 1; j < len; ++j)
            {
                ++perf;
                if (a[i] == a[j])
                {
                    b[j] = false;
                    isFound = true;
                }
            }
            if (!isFound)
            {
                cout << "perf = " << perf << endl;
                cout << "index = " << i << endl;
                cout << endl;
                break;
            }
        }
    }
    delete[] b;
}

void GetTheFirst2(char a[], int len)
{
    int perf;
    for (int i = 0; i < len; ++i)
    {
        int j;
        for (j = 0; j < len; ++j)
        {
            ++perf;
            if (i != j && a[i] == a[j])
            {
                break;
            }
        }
        if (j == len)
        {
            cout << "perf = " << perf << endl;
            cout << "index = " << i << endl;
            cout << "+++++++++++++++++++++++++++++++" << endl << endl;
            break;
        }
    }
}

int main()
{
    char a[] = "ab1cdedaacb1ddddep";
    GetTheFirst(a, sizeof(a) – 1);
    GetTheFirst1(a, sizeof(a) – 1);
    GetTheFirst2(a, sizeof(a) – 1);

    char b[] = "qab1cdedaacb1ddddep";
    GetTheFirst(b, sizeof(b) – 1);
    GetTheFirst1(b, sizeof(b) – 1);
    GetTheFirst2(b, sizeof(b) – 1);

    char c[] = "ab1cdedaacb1ddddepefqacf";
    GetTheFirst(c, sizeof(c) – 1);
    GetTheFirst1(c, sizeof(c) – 1);
    GetTheFirst2(c, sizeof(c) – 1);

    char d[] = "jli,.kjiunkgajfi1294423n423nnsjwidjsjab1cdedaacb1ddddepefqacfasdffesdcdesdssejli,.kjiunkgajfi1294423n423nnsjwidjsj";
    GetTheFirst(d, sizeof(d) – 1);
    GetTheFirst1(d, sizeof(d) – 1);
    GetTheFirst2(d, sizeof(d) – 1);

    char e[] = "0123456789abcdefghijhlmnopqrstuvwxyz";
    GetTheFirst(e, sizeof(e) – 1);
    GetTheFirst1(e, sizeof(e) – 1);
    GetTheFirst2(e, sizeof(e) – 1);

    char f[] = "zyxwvutsrqponmlhjihgfedcba9876543210";
    GetTheFirst(f, sizeof(f) – 1);
    GetTheFirst1(f, sizeof(f) – 1);
    GetTheFirst2(f, sizeof(f) – 1);
    return 0;
}