/*
说明:程序实现二维数组中插入列、插入行、交换两个指定位置的元素，并输出指定
位置元素的变化轨迹
作者: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 = getRowAndColN