关于皇后问题的核心数据用到的结构体要采用动态内存分配和链表结构 - 编程论坛

#2

卢露露2012-04-09 10:59

#include<stdio.h>
#include<malloc.h>
#include<math.h>

#define N 4

typedef int Datatype;
typedef struct Node
{
    Datatype data;
    struct Node*next;
}LNode,*LinkList;
#define flag -1
void Create_LinkList1(LinkList L)
{
    LNode*s;
    Datatype x;
    scanf("%d",&x);
    while(x!=flag)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
}

/* 所有可能的数目 */
int result;
/* 保存结果的一个解,q[i] 是第i行皇后的位置 */
int q[N];


void queen();
int search(int i);
void init(int index);
void printresult();

/* 查找第i行皇后的位置，查找到返回1，否则返回0，

将被保存在q[i]中*/
int search(int i)
{
  int m,n;
  int conflict;
  /* 搜索后以前的位置为: q[i]+1 */
  for (m = q[i] + 1 ; m < N; m++)
    {
      conflict = 0;
      /* compare with prevois i-1 lines */
      for (n = 0; n < i ; n++)
        {
          /* 找到冲突 */
          if (m == q[n] || abs(m - q[n]) == abs(i - n))
            {
              conflict = 1;
              break;
            }
        }
      /* 在第i行找到一个皇后 */
      if (conflict == 0)
        {
      q[i]=m;
          return 1;
        }
    }
  return 0;
}

void queen()
{
  int i;
  int number;
  result = 0;
  number = 0;
  for (i = 0; i < N; i++)
    {
      if (i == 0)
        {
          init(1);
          /* 在第0行重置皇后的位置 */
          q[0] = number - 1;
          /* have find all the result */
          if (number == N )
            {
              break;
            }
          number++;
        }
          /*第i行没找到位置,所以必须追溯 */
      if (search(i) == 0)
        {
          init(i);
          i = i - 2;
          continue;
        }
          /* 找到一个解决方案，输出结果并追踪 */
      if (i == N-1)
        {
          printresult();
          init(i);
          i = i -2;
        }
    }
  printf("The result is:%d\n", result);
}

/* 回溯后, 索引到q的元素要重置 */
void init(int index)
{
  int i;
  for (i = index; i < N; i++)
    {
      q[i] = -1;
    }
}

/* 输出一个结果 */
void printresult()
{
  int i,j;
  for (i = 0; i < N; i++)
    {
      for (j = 0; j < N; j++)
        {
          if (q[i] == j)
            {
              printf("1 ");
            }
          else
            {
              printf("0 ");
            }
        }
      printf("\n");
    }
  result++;
  printf("************************\n");

}

int main(int argc, char * argv[])
{
  queen();
  return 1;
  LinkList L;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    Create_LinkList1(L);
}

这是我的程序，链表创建了，但是核心数据用的还是数组，不知咋用啊？各位高手看看啦~~~

#3

寒风中的细雨2012-04-09 11:57

程序代码：

#include <stdio.h>
#include <math.h>

#define MAX_QUEEN_SIZE    (8)//

int array[MAX_QUEEN_SIZE]={0};//确定了行号
int counter=0;//计数器

//冲突返回0  否则返回非0

int is_conflict(int val_row, int val_col)
{
    int i;
    if (0 == val_row)
    {
        return -1;
    }
    //同列
    for (i=0; i<val_row; ++i)
    {
        if (array[i] == val_col)
        {
            return 0;
        }
    }
    //同斜线
    for (i=0; i<val_row; ++i)
    {
        if (abs(array[i]-val_col)==abs(i-val_row))
        {
            return 0;
        }
    }
    return -1;
}

//确定列号
void queen(int val_row)
{
    int i;

    if (MAX_QUEEN_SIZE == val_row)
    {
        ++counter;
        return;
    }

    for (i=0; i<MAX_QUEEN_SIZE; ++i)
    {
        if (0 != is_conflict(val_row, i))
        {//不冲突
            array[val_row] = i;//记录列
            queen(val_row+1);
        }
    }
}

int main(void)
{
    queen(0);

    printf ("%d\n", counter);

    return 0;
}

#4

寒风中的细雨2012-04-09 12:01

回复 2楼卢露露

题的要求是什么？那点指明是需要动态实现？

#5

卢露露2012-04-09 15:34

回复 4楼寒风中的细雨

程序应具有以下基本功能：
（1）输入棋盘规模N；
（2）采用回逆法计算皇后位置；
（3）以棋盘的形式显示皇后位置。

设计要求设计要求设计要求设计要求：
1．核心数据结构用到的结构体要采用动态内存分配和链表结构。
2．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用
接口要注释清楚。对程序其它部分也进行必要的注释。

#6

卢露露2012-04-10 21:45

回复 4楼寒风中的细雨

帮帮啦~~~·老大

#7

寒风中的细雨2012-04-10 23:45

还以为你早就好了

本来挺简单的东西为什么要搞复杂勒这点很不理解

[ 本帖最后由寒风中的细雨于 2012-4-10 23:47 编辑 ]

#8

卢露露2012-04-11 16:33

回复 7楼寒风中的细雨

该死的课程设计非要用链表

#9

寒风中的细雨2012-04-11 20:35

程序代码：

/***

* @文件名：xxxx.c

* @作  者：寒风中的细雨

* @时  间：2012/4/11/20:32

* @概  要：№‰¾√→

*/

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <math.h>

unsigned int counter=0;//计数器

typedef unsigned int elem_type;
typedef struct _node
{
    elem_type str_col;//列
    elem_type str_row;//行
    struct _node *next;
}node, *ptr_node;

//建立对象
ptr_node create_list(ptr_node h_list, elem_type v_code)
{
    assert(NULL == h_list);
    h_list = (ptr_node) malloc (sizeof(node));
    assert(NULL != h_list);//带头结点，用于存放棋盘大小
    h_list->str_col = h_list->str_row = v_code;
    h_list->next = NULL;

    return h_list;
}

//添加
int add_list(ptr_node h_list, elem_type v_row, elem_type v_col)
{
    ptr_node p_tail = h_list;

    while ((NULL!=p_tail->next) && (p_tail=p_tail->next));
    p_tail->next = (ptr_node) malloc (sizeof (node));
    assert(NULL != p_tail->next);
    p_tail = p_tail->next;
    p_tail->str_col = v_col;
    p_tail->str_row = v_row;
    p_tail->next = NULL;

    return 0;//成功
}

//输出
void print_list(ptr_node h_list)
{
    unsigned int i, j;
    ptr_node p_tmp = h_list->next;

    for (i=0; i<h_list->str_row; ++i)
    {
        for (j=0; j<h_list->str_col; ++j)
        {
            if (p_tmp->str_col == j)
            {
                printf ("№");
            }
            else
            {
                printf ("→");
            }
        }
        printf ("\n");
        p_tmp = p_tmp->next;
    }
    printf ("\n");
}

//删除某结点
int delete_list(ptr_node h_list, int index)
{
    ptr_node p_tail = h_list->next;
    ptr_node p_ftail = h_list;

    while (--index && (NULL!=p_tail->next) && (p_ftail=p_tail))
    {
        p_tail = p_tail->next;
    }

    if (0 != index)
    {
        //error
        printf ("error!\n");
        return -1;
    }
    p_ftail->next = p_tail->next;
    free(p_tail);

    return 0;
}

//释放资源
ptr_node destroy_list(ptr_node h_list)
{
    ptr_node p_tail = h_list;

    while (p_tail)
    {
        ptr_node p_tmp = p_tail->next;
        free(p_tail);
        p_tail = p_tmp;
    }
    h_list = NULL;

    return h_list;
}

//
int is_conflict(ptr_node h_list, const int val_row, const int val_col)
{
    ptr_node p_tmp = h_list->next;

    if (0 == val_row)
    {
        return -1;
    }
    //同列
    for (p_tmp = h_list->next; p_tmp; p_tmp = p_tmp->next)
    {
        if (val_col == p_tmp->str_col)
        {
            return 0;
        }
    }
    //同斜线
    for (p_tmp = h_list->next; p_tmp; p_tmp = p_tmp->next)
    {
        if (abs(val_col-p_tmp->str_col) == abs(val_row-p_tmp->str_row))
        {
            return 0;
        }
    }

    return -1;
}

//
void queen(ptr_node h_list, const unsigned int val_row)
{
    unsigned int i;

    if (val_row == h_list->str_row)
    {
        ++counter;
        print_list(h_list);
        return;
    }

    for (i=0; i<h_list->str_col; ++i)
    {
        if (0 != is_conflict(h_list, val_row, i))
        {
            add_list(h_list, val_row, i);
            queen(h_list, val_row+1);
            delete_list(h_list, val_row+1);
        }
    }
}

//
int main(int argc, char *argv[])
{
    int i;
    ptr_node list=NULL;

    printf (">\\");
    scanf_s ("%d", &i);
    assert(0 < i);

    list = create_list(list, i);

    queen(list, 0);

    printf ("%d\n", counter);

    list = destroy_list(list);
    assert(NULL == list);

    return 0;
}

#10

卢露露2012-04-12 09:24

回复 9楼寒风中的细雨

真厉害，好佩服哦

#11

寒风中的细雨2012-04-12 09:38

回复 10楼卢露露

参考着看看~~

毕竟是劳动成果

[ 本帖最后由寒风中的细雨于 2012-4-12 09:40 编辑 ]