7-1~7-2

#include
#include
typedef int DataType;
struct Node {
	DataType	  coef;
	 DataType     exp;
	struct Node*  next;
};
typedef struct Node  *PNode;
typedef struct Node  *LinkList;
LinkList SetNullList_Link()
{
	LinkList head = (LinkList)malloc(sizeof(struct Node));
	if (head != NULL) head->next = NULL;
	else printf("alloc failure");
	return head;
}

void CreateList(struct Node* head)
{
    DataType coef,exp;
	PNode p = NULL;
	PNode q = head;
	scanf("%d,%d", &coef,&exp);
	while (coef!=0)
	{
		p = (struct Node*)malloc(sizeof(struct Node));
		p->coef = coef;
		p->exp = exp;
		p->next=NULL;
		q->next=p;
		q=p;
		scanf("%d,%d", &coef,&exp);
	}
}
void MoveMaxToTail (LinkList head)
{
    PNode pre,q;
    int tcoef,texp;
    for(pre=head->next;pre->next!=NULL;pre=pre->next)
       for(q=pre->next;q!=NULL;q=q->next)
    {
        if(q->exp<pre->exp)
           {
               tcoef=pre->coef;
               texp=pre->exp;
               pre->coef=q->coef;
               pre->exp=q->exp;
               q->coef=tcoef;
               q->exp=texp;
           }
    }
}
LinkList PolynomialAddition(LinkList head1,LinkList head2)
{
    PNode preA=head1->next,qA=preA->next;
    free(head1);
    PNode preB=head2->next,qB=preB->next;
    free(head2);
    PNode head = (LinkList)malloc(sizeof(struct Node));
    head->next=NULL;
    PNode pre=head;
    while(preA!=NULL&&preB!=NULL)//当链表链表有一个遍历到表尾时结束
    {
        if(preA->exp<preB->exp)//当满足条件时，将preA节点插入新链表
        {
            preA->next=pre->next;
            pre->next=preA;
            preA=qA;
             if(preB==NULL)
                    continue;
            qA=qA->next;
            pre=pre->next;

        }
        else
             if(preB->exp<preA->exp)//当满足条件时，将preB插入新链表
            {
                preB->next=pre->next;
                pre->next=preB;
                preB=qB;
                 pre=pre->next;
                if(preB==NULL)
                    continue;
                qB=qB->next;


            }
            else
              if(preA->coef+preB->coef==0)//当满足条件，书房preA和preB
              {
                 free(preA);
                 preA=qA;
                 if(preA!=NULL)
                 qA=qA->next;
                 free(preB);
                 preB=qB;
                 if(preB!=NULL)
                 qB=qB->next;
              }
              else//当preA->coef+preB->coef≠0时
              {
                preA->coef=preB->coef+preA->coef;
                preA->next=pre->next;
                pre->next=preA;
                preA=qA;
                if(preA!=NULL)
                qA=qA->next;
                pre=pre->next;
                free(preB);
                preB=qB;
                if(preB!=NULL)
                qB=qB->next;

              }
    }//当循环结束时，两条链表遍历不一定就此结束，以为链表长度不一定相同，所以要进行以下操作
    //将链表中未遍历的部分直接接入新链表
    if(preA!=NULL)
        pre->next=preA;
    else
        pre->next=preB;
    return head;
}
void print(LinkList head)
{
    LinkList p;
    p=head->next;
    while(p!=NULL)
    {
        printf("%d,%d ",p->coef,p->exp);
        p=p->next;
    }
}
int main()
{
    LinkList head1;
    LinkList head2;
    LinkList head;
    head1=SetNullList_Link();
    head2=SetNullList_Link();
    CreateList(head1);
    CreateList(head2);
    MoveMaxToTail (head1);
    MoveMaxToTail (head2);
    head=PolynomialAddition(head1,head2);
    print(head);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

这是一个陷入迷官的老鼠如何找到出口的问题,要求输出老鼠探索出的从入口到出口的路径。老鼠希望尽快地找到出口走出迷官。如果它到达一个死胡同,将原路返回到上一个位置,尝试新的路径。在每个位置上老鼠可以向 4 个方向运动,即上、下、左、右。无论离出口多远，它总是按照这样的顺序尝试,当到达一个死胡同之后,老鼠将进行“回溯”。这种探索路径的回溯过程是最后走的位置要最先返回,因此可以使用栈来保存走过的路径序列。
迷宫可以用一个二维数组 maze[m+2][n+2]表示,数组中的元素或者为0,或者为1.0表示通路,1表示墙,迷宫的四周可以设想为全 1,即为墙。设置入口为 maze[1][1]、出口为 maze[6][6]。为了避免检查是否到达了边界,在迷官四周添加一条取值为 1的边来表示障碍,如图 3-4 所示。
解决迷宫问题有两种策略(一种是深度优先策略,另外一种是广度优先策略。两种策略分别对应栈和队列做辅助数据结构。在本节采用深度优先策略,在 3.11 节采用广度优先策略解决迷宫问题。
在迷宫问题中要找到路径并输出需要解决 3 个问题。
为了让计拿
(1) 从某一个坐标点(x,y)出发如何搜索其相邻位置(g,h)?
为了简化判断,假设迷官四周都是墙,即在四周都赋值为 1 的一条边这样对于任意的位置,与它相邻的位置有 8 个,如图 3-5 所示

为了让计算机对 8个位置按照一定的顺序搜索,不妨假设 8个方向的顺序是从正东按照顺时针，将这 8个方向的位置的坐标放到一个结构数组 direction[8][2]中,数组内容为:
direction[8][2]=((0,1),[1,1},(1,0),(1,-1),(0,-1),(-1,-1),[ -1,0)
数组中给出了相邻位置(g,h)相对于当前位置(x,y)的增量,即:
g=x+direction[i][j]
h= y+ direction[i][j]
假设从当前位置(3,5)向南出发,则:
g=x+ direction[2][0] = 3 + 1 = 4
h= y+ direction[2][1] = 5 + 0 = 5
(2) 如何记录探索过的路径?由于采用了回溯方法,因此设计栈来存放探索过的路径,当不能向前继续探索时从栈中弹出元素。
为了重复使用前面定义好的栈结构,在这里使用两个栈 linkStackX和linkStackY 分别存放行坐标和列坐标。
(3) 如何防止重复探索某位置?
通过设置标志位来识别,初始时各个位置的标志位 mark[][j]-0当探索到某位置后设置 mark[][]=1。
有了上述基本定义,迷宫算法的思路如下:
(1)创建两个空栈 StackX 和 StackY。
(2)将人口 entryX 和 entryY 分别压人栈 StackX和 StackY中
(3) while(栈不空)
1, 取栈顶元素，出栈，当前位置为栈顶元素
2, while(mov< 8),即还存在探索的方向。
a，按照顺时针依次探索各个位置(posX，posY)
b。如果(posX，posY)是出口,输出路径，返回1。
c。如果(posX，posY)是没有走过的通路:
·设置标志位mark[posX][pos=1.
.当前位置进栈。
.将(posX，posY)设置为当前位置
.设置 mov=0。
d，否则(如果(X，Y)是没有走过的通路),mov++

#include
#include
struct MAZE_STRU
{
    int size;
    int **data;
};
typedef struct MAZE_STRU Maze;
typedef int DataTye;
struct Node
{
    DataTye data;
    struct Node *next;
};
typedef struct Node *PNode;
typedef struct Node*top,*LinkStack;
LinkStack SetNullStack_Link()
{
    LinkStack top=(LinkStack)malloc(sizeof(struct Node));
    if(top!=NULL)
    {
        top->next=NULL;
    }
    else
    {
        printf("alloc failuer");
    }
    return top;
}
 void Push_Link(LinkStack top,DataTye x)
 {
     PNode p=(PNode)malloc(sizeof(struct Node));
         if(p==NULL)
         {
             printf("alloc failuer");
         }
     else
     {
         p->data=x;
         p->next=top->next;
         top->next=p;
     }
 }
int IsNullStack_Link(LinkStack top)
{
    if(top->next==NULL)
    {
        return 1;
    }
    else
        return 0;
}

void Pop_Link(LinkStack top)
{
    PNode p;
    if(top->next==NULL)
    {
        printf("it is empty stack!");
    }
    else{
        p=top->next;
        top->next=p->next;
        free(p);
    }
}

DataTye Top_Link(LinkStack top)
{
    if(IsNullStack_Link(top)==1)
    {
        printf("if is empty stack");
    }
    else{
        return top->next->data;
    }
}

Maze*InitMaze(int size)
{
    int i;
    Maze*maze=(Maze*)malloc(sizeof(Maze));
    maze->size=size;
    maze->data=(int**)malloc(sizeof(int*)*maze->size);
    for(i=0;i<maze->size;i++)
    {
        maze->data[i]=(int*)malloc(sizeof(int)*maze->size);
    }
    return maze;
}
void ReadMaze(Maze *maze)
{
    int i,j;
    for(i=0;i<maze->size;i++)
    {
        for(j=0;j<maze->size;j++)
        {
            scanf("%d",&maze->data[i][j]);
        }
    }
}
void WriteMaze(Maze*maze)
{
    int i,j;
    printf("迷宫结构如下：\n");
    for(i=0;i<maze->size;i++)
    {
        for(j=0;j<maze->size;j++)
        {
            printf("%5d",maze->data[i][j]);
        }
        printf("\n");
    }
}
int MazeDFD(int entryX,int entryY,int exitX,int exitY,Maze *maze)
{
    int derection[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,1},{-1,-1},{-1,0},{-1,1}};
    LinkStack LinkStackX=NULL;
    LinkStack LinkStackY=NULL;
    int posX,posY;
    int preposX,preposY;
    int **mark;
    int i,j;
    int mov;
    mark=(int**)malloc(sizeof(int*)*maze->size);
    for(i=0;i<maze->size;i++)
    {
        mark[i]=(int*)malloc(sizeof(int)*maze->size);
    }
    for(i=0;i<maze->size;i++)
    {
        for(j=0;j<maze->size;j++)
        {
            mark[i][j]=0;
        }
    }
LinkStackX=SetNullStack_Link();
LinkStackY=SetNullStack_Link();
mark[entryX][entryY]=1;
Push_Link(LinkStackX,entryX);
Push_Link(LinkStackY,entryY);
while(!IsNullStack_Link(LinkStackX))
{
    preposX=Top_Link(LinkStackX);
    preposY=Top_Link(LinkStackY);
    Pop_Link(LinkStackX);
    Pop_Link(LinkStackY);
    mov=0;
    while(mov<8)
    {
        posX=preposX+derection[mov][0];
        posY=preposY+derection[mov][1];
        if(posX==exitX&&posY==exitY)
        {
            Push_Link(LinkStackX,preposX);
            Push_Link(LinkStackY,preposY);
            printf("%d %d;",exitX,exitY);
        while(!IsNullStack_Link(LinkStackX))
        {
            posX=Top_Link(LinkStackX);
            posY=Top_Link(LinkStackY);
            printf("%d %d;",posX,posY);
            Pop_Link(LinkStackX);
            Pop_Link(LinkStackY);
        }
        return 1;
        }
    if(maze->data[posX][posY]!=1&&mark[posX][posY]!=1)
    {
        mark[posX][posY]=1;
        Push_Link(LinkStackX,preposX);
        Push_Link(LinkStackY,preposY);
        preposX=posX;
        preposY=posY;
        mov=0;
    }
    else
        mov++;
    }
}
return 0;
}
 int main()
 {
     Maze* maze;
     int mazeSize;
     int entryX,entryY,exitX,exitY;
     int find=0;
     scanf("%d",&mazeSize);
     maze=InitMaze(mazeSize);
     ReadMaze(maze);
     scanf("%d%d%d%d",&entryX,&entryY,&exitX,&exitY);
     find=MazeDFD(entryX,entryY,exitX,exitY,maze);
     if(find==0)
     {
         printf("找不到路径！");
     }
     return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199