C：二維數組常用操作

C：二維數組常用操作

/*
說明:程序實現二維數組中插入列、插入行、交換兩個指定位置的元素，並輸出指定
位置元素的變化軌跡
作者:socrates
日期:2014-08-17
*/

#include "stdafx.h"
#include  
#include 

/*二維數組最大行數和列數*/
#define MAX_ROW_NUM (9)
#define MAX_COL_NUM (9)

/*二維數組中各元素位置信息*/
typedef struct _PathNode
{
    int x;  /*行*/
    int y;  /*列*/
}Node;

/*各元素內容(表示位置軌跡的鏈表)*/
typedef struct _PathNodeList
{
    Node node;
    _PathNodeList *pNext;
}PathNodeList;

/*表示二維數組有效的行列數*/
typedef struct _CurRowColNum
{
    int iArrayRow;
    int iArrayCol;
}CurRowColNum;

/*二維數組行列數*/
static CurRowColNum g_stRowColNum = {0};

/*二維數組定義*/
PathNodeList* g_pGrid[MAX_ROW_NUM][MAX_COL_NUM];

/*錯誤碼*/
enum _RetCode
{
    ERR = -1, /*失敗*/
    OK = 0    /*成功*/
}RETCODE;

/*設置當前數組行列數*/
void SetRowAndColNum(int iRow, int iCol)
{
    g_stRowColNum.iArrayRow = iRow;
    g_stRowColNum.iArrayCol = iCol;
}

/*獲取數組行列數*/
CurRowColNum getRowAndColNum()
{
    return g_stRowColNum;
}

/*創建軌跡鏈表，不帶頭結點*/
int CreatePathNodelist(PathNodeList *&pList, Node *pPathNode)
{
    if (NULL == pPathNode)
    {
        return ERR;
    }
    
    pList = (PathNodeList *)malloc(sizeof(PathNodeList));
    if (NULL == pList)
    {
        return ERR;
    }
    pList->node.x = pPathNode->x;
    pList->node.y = pPathNode->y;
    pList->pNext = NULL;
    
    return OK;
}

/*銷毀軌跡鏈表*/
int DestoryPathNodelist(PathNodeList *pList)
{
    if (NULL == pList)
    {
        return ERR;
    }
    
    PathNodeList *p = pList;
    while (NULL != p->pNext)
    {
        p = p->pNext;
        free(pList);
        pList = p;
    }    
    free(pList);
    pList = NULL;

    return OK;
}

/*向軌跡鏈表中插入當前結點所在位置*/
int InsertPathNodeList(PathNodeList *pPathNodeList, Node *pPathNode)
{
    if ((NULL == pPathNodeList)
        || (NULL == pPathNode))
    {
        return ERR;
    }
    
    PathNodeList *pNewPathNode = (PathNodeList *)malloc(sizeof(PathNodeList));
    if (NULL == pPathNode)
    {
        return ERR;
    }
    
    pNewPathNode->node.x = pPathNode->x;
    pNewPathNode->node.y = pPathNode->y;
    pNewPathNode->pNext = NULL;
    
    PathNodeList *p = pPathNodeList;
    while (NULL != p->pNext)
    {
        p = p->pNext;
    }
    
    p->pNext = pNewPathNode;
    
    return OK;
}

/*初始化二維數組*/
int InitGrid(int iXNum, int iYNum)
{  
    if ((iXNum < 0) || (iXNum > MAX_ROW_NUM))
    {
        return ERR;
    }

    if ((iYNum < 0) || (iYNum > MAX_COL_NUM))
    {
        return ERR;
    }

    /*存儲數組行列個數*/
    SetRowAndColNum(iXNum, iYNum);

    /*數組中的每個元素均建立一個以應的鏈表存放其運行軌跡，
    沒有初始化元素默認為NULL*/
    for (int i = 0; i < iXNum; i++)
    {
        for (int j = 0; j < iYNum; j++)
        {
            Node node = {0};
            node.x = i;
            node.y = j;
            
            if (OK != CreatePathNodelist(g_pGrid[i][j], &node))
            {
                return ERR;
            }
        }
    }
    
    return OK;
}

/*銷毀二維數組*/
int DestoryGrid()
{
    CurRowColNum stcurRowColNum = getRowAndColNum();
    for (int i = 0; i < stcurRowColNum.iArrayRow; i++)
    {
        for (int j = 0; j < stcurRowColNum.iArrayCol; j++)
        {
            if (OK != DestoryPathNodelist(g_pGrid[i][j]))
            {
                continue;
            }
        }
    }

    return OK;
}

/*獲取元素當前所在位置*/
Node *GetCurPostion(PathNodeList *pPathList)
{
    if (NULL == pPathList)
    {
        return NULL;
    }

    PathNodeList *p = pPathList;

    /*鏈表的最後一個結點表示當前位置*/
    while(NULL != p->pNext)
    {
        p = p->pNext;
    }

    return &(p->node);
}

/*交換兩個結點的位置*/
int SwapNode(Node aNode, Node bNode)
{   

    Node *paNode = GetCurPostion(g_pGrid[aNode.x][aNode.y]);
    Node *pbNode = GetCurPostion(g_pGrid[bNode.x][bNode.y]);

    /*將b結點的當前位置插入到a結點鏈表中*/    
    if (OK != InsertPathNodeList(g_pGrid[aNode.x][aNode.y], pbNode))
    {
        return ERR;
    }
    
    /*將a結點的當前位置插入到b結點鏈表中*/  
    if (OK != InsertPathNodeList(g_pGrid[bNode.x][bNode.y], paNode))
    {
        return ERR;
    }

    /*交換a、b兩個結點*/
    PathNodeList *pTmp = NULL;
    pTmp = g_pGrid[aNode.x][aNode.y];
    g_pGrid[aNode.x][aNode.y] = g_pGrid[bNode.x][bNode.y];
    g_pGrid[bNode.x][bNode.y] = pTmp;

    return OK;
}

/*向數組中沒有使用的行插入元素*/
int insertToEmptyRow(int iRow)
{
    CurRowColNum stcurRowColNum = getRowAndColNum();
    
    for (int j = 0; j < stcurRowColNum.iArrayCol; j++)
    {
        Node node = {0};
        node.x = iRow;
        node.y = j;
             
        if (OK != CreatePathNodelist(g_pGrid[iRow][j], &node))
        {
            return ERR;
        }
    }  
    
    return OK;
}

/*向二維數組插入一行*/
int insertRowtoGrid(int iInsertRow)
{
    if (MAX_ROW_NUM <= iInsertRow)
    {
        return ERR;
    }

    CurRowColNum stcurRowColNum = getRowAndColNum();

    /*插入數組中的無效行，直接插入，而向已有行中間插入，需要從前
    向後兩兩交換行元素的位置*/
    if (iInsertRow >= stcurRowColNum.iArrayRow)
    {
        if (OK != insertToEmptyRow(iInsertRow))
        {
            return ERR;
        }
    }
    else
    {
        /*先將新行插入第一個無效行中*/
        if (OK != insertToEmptyRow(stcurRowColNum.iArrayRow))
        {
            return ERR;
        }  

        /*從剛插入的新行開始，按行兩兩交換，直到把插入的行
        置換到參數指定的位置*/
        for (int i = stcurRowColNum.iArrayRow; i > iInsertRow; i--)
        {
            for (int j = 0; j < stcurRowColNum.iArrayCol; j++)
            {
                Node curNode;
                Node nextNode;

                curNode.x = i - 1;
                curNode.y = j;

                nextNode.x = i;
                nextNode.y = j;
                
                if (OK != SwapNode(curNode, nextNode))
                {
                    return ERR;
                }                
            }
        }
            
    }

    /*數組有效行數加1*/
    SetRowAndColNum(stcurRowColNum.iArrayRow + 1, stcurRowColNum.iArrayCol);
    
    return OK;
}

/*獲取二維數組中指定結點的運動軌跡*/
int GetNodePath(Node pathNode, PathNodeList **pPathList)
{    
    CurRowColNum stcurRowColNum = getRowAndColNum();
    if ((pathNode.x < 0) 
        || (pathNode.x >= stcurRowColNum.iArrayRow))
    {
        *pPathList = NULL;
        return ERR;
    }

    if ((pathNode.y < 0) 
        || (pathNode.y >= stcurRowColNum.iArrayCol))
    {
        *pPathList = NULL;
        return ERR;
    }

    *pPathList = g_pGrid[pathNode.x][pathNode.y];
    return OK;

}

/*向數組中沒有使用的列插入元素*/
int insertToEmptyCol(int iCol)
{
    CurRowColNum stcurRowColNum = getRowAndColNum();
    
    for (int i = 0; i < stcurRowColNum.iArrayRow; i++)
    {
        Node node = {0};
        node.x = i;
        node.y = iCol;
             
        if (OK != CreatePathNodelist(g_pGrid[i][iCol], &node))
        {
            return ERR;
        }
    } 
    
    return OK;
}

/*向二維數組插入一列*/
int insertColtoGrid(int iInsertCol)
{
    if (MAX_COL_NUM <= iInsertCol)
    {
        return ERR;
    }

    CurRowColNum stcurRowColNum = getRowAndColNum();

    /*插入數組中的無效列，直接插入，而向已有列中間插入，需要從前
    向後兩兩交換列元素的位置*/
    if (iInsertCol >= stcurRowColNum.iArrayCol)
    {
        if (OK != insertToEmptyCol(iInsertCol))
        {
            return ERR;
        }
    }
    else
    {
        /*先將新行插入第一個無效列中*/
        if (OK != insertToEmptyCol(stcurRowColNum.iArrayCol))
        {
            return ERR;
        }  

        /*從剛插入的新列開始，按列兩兩交換，直到把插入的列
        置換到參數指定的位置*/
        for (int j = stcurRowColNum.iArrayCol; j > iInsertCol; j--)
        {
            for (int i = 0; i < stcurRowColNum.iArrayRow; i++)
            {
                Node curNode;
                Node nextNode;

                curNode.x = i;
                curNode.y = j - 1;

                nextNode.x = i;
                nextNode.y = j;
                
                if (OK != SwapNode(curNode, nextNode))
                {
                    return ERR;
                }                
            }
        }
            
    }

    /*數組有效列數加1*/
    SetRowAndColNum(stcurRowColNum.iArrayRow, stcurRowColNum.iArrayCol + 1);
    
    return OK;
}


/*測試代碼*/
int main(int argc, char* argv[])
{
    assert(OK == InitGrid(5, 5));
    
    PathNodeList *pList = NULL;
    Node node;
    node.x = 3;
    node.y = 4;

    Node node1;
    node1.x = 1;
    node1.y = 1;

    Node node2;
    node2.x = 4;
    node2.y = 4;

    assert(OK == SwapNode(node, node1));
    assert(OK == insertRowtoGrid(1));
    assert(OK == insertColtoGrid(3));
    
    assert(OK == GetNodePath(node2, &pList));

    PathNodeList *p = pList;
    while (NULL != p)
    {
        printf("(%d\t%d)\n", p->node.x, p->node.y);
        p = p->pNext;
    }

    assert(OK == DestoryGrid());
    return 0;
}