西安交通大学
数据结构实验报告
孙广大 计算机试验班 61 2140506021
2017-6-8
课内实验设计
一、 使用链式存储结构实现队列
问题描述
使用链式存储结构实现队列及其基本操作.
解题思路
使用不带头节点的链表作为队列的内部实现,所以首先实现一个标准的队列结构以备用.该链
表使用变异的静态链表结构,使用两个动态分配的数组分别用于存储数据和维护后继节点.该
链表非空时有一个"当前位置",可以通过获得或修改其"当前位置"的值,还可以将当前位置向
前或向后移动,还可以重新设置为链表的头元素.代码文件当中 lnklst.h/.c 分别为该链表
的接口和实现,
在此基础上,quelst.h/.c 分別给出了一个队列的定义和实现.通过调用链表的 append 方法
可以将新的元素添加到队列的尾部,而通过 getval 和 delete 方法则可以将队列的首元素
出队("当前位置"在队列的使用中始终固定在首元素位置).此外,队列和链表还实现了一些工
具函数用于获取当前长度,或者以一种友好的方式将数据结构打印出来.
测试代码 quelst_test.c 实现了一个交互式的动态构建队列.可以读取键盘的输入对队列进行
对应的操作.
代码详单
lnklst.h
/*
* lnklst.h
* A linked list.
* Created by oziroe on May 30, 2017.
*/
#ifndef LNKLST_H
#define LNKLST_H
typedef struct {
int * memo; // used: data, unused: next use position, -1 for no
more
int * next; // next data position, -1 for end
int len; // data length
int max; // length of `memo` and `next`
int cur; // current position (or cursor)
int new; // next free position, -1 for no more
int pre; // previous position of `cur`, -1 when `len` < 2
int fst; // first position
int end; // last position
} lnklst_t;
#ifndef LNKLST_INIT_SIZE
#define LNKLST_INIT_SIZE 64
#endif
// New linked list with size of `LNKLST_INIT_SIZE`.
lnklst_t * lnklst_alloca (void);
// Insert data at current position. Current data move to next.
// Only can be called on non-empty list.
int lnklst_insert (lnklst_t *list, int data);
// Append new data to the end.
int lnklst_append (lnklst_t *list, int data);
// Delete data at current position.
// Set current position to next if exists, or first.
int lnklst_delete (lnklst_t *list);
// Set current position to somewhere.
int lnklst_setpos (lnklst_t *list, int pos);
// Move current position forward.
int lnklst_nxtpos (lnklst_t *list);
// Print list in a proper way to console.
void lnklst_printf (lnklst_t *list);
// Get the length of list.
int lnklst_length (lnklst_t *list);
// Get current position data of list.
int lnklst_getval (lnklst_t *list, int *out_data);
// Delete a list that no more used.
void lnklst_destro (lnklst_t *list);
#endif
lnklst.c
#include <stdio.h>
#include <stdlib.h>
#include "lnklst.h"
lnklst_t *lnklst_alloca(void) {
lnklst_t *list = malloc(sizeof(lnklst_t));
if (!list)
return NULL;
list->memo = malloc(sizeof(int) * LNKLST_INIT_SIZE);
list->next = malloc(sizeof(int) * LNKLST_INIT_SIZE);
if (!list->memo || !list->next)
return NULL;
for (int i = 0; i < LNKLST_INIT_SIZE - 1; i++)
list->memo[i] = i + 1;
list->memo[LNKLST_INIT_SIZE - 1] = -1;
list->len = 0;
list->max = LNKLST_INIT_SIZE;
list->cur = -1;
list->new = 0;
list->pre = -1;
list->fst = -1;
list->end = -1;
return list;
}
static int _extend_list(lnklst_t *list, int new_size) {
int *new_memo = realloc(list->memo, sizeof(int) * new_size);
int *new_next = realloc(list->next, sizeof(int) * new_size);
if (!new_memo || !new_next)
return 1;
else {
list->memo = new_memo;
list->next = new_next;
}
for (int i = list->max; i < new_size - 1; i++)
list->memo[i] = i + 1;
list->memo[new_size - 1] = -1;
list->new = list->max;
list->max = new_size;
return 0;
}
int lnklst_insert(lnklst_t *list, int data) {
if (list->cur < 0)
return 1;
// Double size of `memo` and `next` when no more space.
if (list->new < 0) {
if (_extend_list(list, list->max * 2))
return 2;
}
int pos = list->new;
list->new = list->memo[pos];
list->memo[pos] = data;
list->next[pos] = list->cur;
if (list->cur == list->fst)
list->fst = pos;
list->cur = pos;
list->len++;
if (list->pre >= 0)
list->next[list->pre] = pos;
return 0;
}
void lnklst_destro(lnklst_t *list) {
free(list->memo);
free(list->next);
free(list);
}
int lnklst_append(lnklst_t *list, int data) {
if (list->new < 0) {
if (_extend_list(list, list->max * 2))
return 1;
}
int pos = list->new;
list->new = list->memo[pos];
list->memo[pos] = data;
list->next[pos] = -1;
list->len++;
if (list->len == 1) {
list->fst = list->end = pos;
list->pre = -1;
list->cur = pos;
}
else if (list->len == 2) {
//list->pre = list->fst;
list->end = pos;
list->next[list->fst] = pos;
}
else {
list->next[list->end] = pos;
list->end = pos;
}
return 0;
}
void lnklst_printf(lnklst_t *list) {
printf("[>");
const char *prefix = "";
for (int pos = list->fst; pos >= 0; pos = list->next[pos]) {
printf("%s%d", prefix, list->memo[pos]);
if (pos == list->cur)
printf("^");
prefix = ", ";
}
printf("]\n");
}
int lnklst_delete(lnklst_t *list) {
if (list->cur < 0)
return 1;
list->memo[list->cur] = list->new;
list->new = list->cur;
list->len--;
if (list->len == 0) {
list->cur = list->pre = list->fst = list->end = -1;
return 0;
}
else if (list->cur == list->end) {
list->next[list->pre] = -1;
list->cur = list->fst;
list->end = list->pre;
list->pre = -1;
return 0;
} else {
if (list->cur == list->fst)
list->fst = list->next[list->cur];
list->cur = list->next[list->cur];
list->next[list->pre] = list->cur;
return 0;
}
}
int lnklst_nxtpos(lnklst_t *list) {
if (list->next[list->cur] < 0)
return 1;
else {
list->pre = list->cur;
list->cur = list->next[list->cur];
return 0;
}
}
int lnklst_setpos(lnklst_t *list, int pos) {
if (pos < 0 || pos >= list->len)
return 1;
list->cur = list->fst;
list->pre = -1;
for (int i = 0; i < pos; i++) {
list->pre = list->cur;
list->cur = list->next[list->cur];
}
return 0;
}
int lnklst_length(lnklst_t *list) {
return list->len;
}
int lnklst_getval(lnklst_t *list, int *out) {
if (list->cur < 0)
return 1;
else {
*out = list->memo[list->cur];
return 0;
}
}
quelst.h
/*
* quelst.h
* A queue model list.
* Created by oziroe on May 31, 2017.
*/
#ifndef QUELST_H
#define QUELST_H
#include "lnklst.h"
typedef struct {
lnklst_t * list;
} quelst_t;
quelst_t * quelst_alloca(void);
int quelst_append(quelst_t *queue, int data);
int quelst_poplft(quelst_t *queue, int *out_data);
void quelst_printf(quelst_t *queue);
int quelst_length(quelst_t *queue);
void quelst_destro(quelst_t *queue);
#endif
quelst.c
#include <stdio.h>
#include <stdlib.h>
#include "quelst.h"
quelst_t *quelst_alloca(void) {
quelst_t *queue = malloc(sizeof(quelst_t));
if (!queue)
return NULL;
queue->list = lnklst_alloca();
if (!queue->list)
return NULL;
return queue;
}
void quelst_destro(quelst_t *queue) {
lnklst_destro(queue->list);
free(queue);
}
int quelst_length(quelst_t *queue) {
return lnklst_length(queue->list);
}
void quelst_printf(quelst_t *queue) {
printf("q");
lnklst_printf(queue->list);
}
int quelst_append(quelst_t *queue, int data) {
return lnklst_append(queue->list, data);
}
int quelst_poplft(quelst_t *queue, int *out) {
if (lnklst_getval(queue->list, out))
return 1;
if (lnklst_delete(queue->list))
return 2;
return 0;
}
quelst_test.c
#include <stdio.h>
#include "quelst.h"
int main(void) {
printf("Queue Test Program.\n");
printf("Usage: a d -> append `d` to queue\n");
printf(" p -> pop first data\n");
printf(" q -> quit\n");
quelst_t *queue = quelst_alloca();
for (;;) {
printf("Current queue: ");
quelst_printf(queue);
printf("\n>> ");
char command;
scanf("%c", &command);
switch (command) {
case 'a': {
int data;
scanf("%d", &data);
int status = quelst_append(queue, data);
printf("Status: %d\n", status);
break;
}
case 'p': {
int data = -1;
int status = quelst_poplft(queue, &data);
printf("Data: %d\nStatus: %d\n", data, status);
break;
}
case 'q': {
quelst_destro(queue);
return 0;
}
default:
break;
}
while (getchar() != '\n')
;
}
}
运行结果
二、 使用邻接表实现图数据结构
问题描述
使用邻接表作为内部结构实现一个图,以及相关的基本操作.
解题思路
复用上一道题中实现的队列作为邻接表的内部实现,这样有助于程序的可维护性.通过调用下
层队列的接口即可实现添加顶点和边以及遍历与一个顶点相邻的边的接口.
该图为一个有向图,通过一个辅助结构 genedg_t 作为边的内部结构.该结构储存了边的终点
和权值,可以基本满足对图的使用.如果有对于边的特殊要求,只需要更改这个结构就可以实
现,从而达到最大的可拓展性和灵活性.
该图还提供了两个高级遍历接口:深度优先顺序和广度优先顺序遍历整个图.这两个接口接收
一个图,一个回调函数,遍历的起点和一个额外的 void *类型的负载变量作为参数.回调函数
会在遍历到每一个顶点时被调用,它接受四个参数,分别是当前顶点,到达当前顶点所走的边,
一个 prev 数组以及负载变量.prev 数组当中储存了访问各顶点的顺序,如果一个顶点已经被
遍历到,则储存到达它的顶点,否则储存-1.传给遍历接口的负载变量会原封不动地传给回调
函数.回调函数返回一个整形数,若该数不为 0,则遍历提前结束.这两个遍历接口可以满足大多
数的对图遍历的需求.在文件 adjlst.h/.c 中分别为该图实现的接口和实现.
在测试代码 adjlst_test.c 中,实现了一个与上一道题中类似的交互式测试环境.由于图的
输入比较复杂,因此将输入存放在 adjlist_test.txt 中以供备用.该文件中的指令先构建一
个与教材中"深度遍历和广度遍历"一节的示例图一样的结构(由于教材中是无向图所以每一
条边需要两条指令),然后执行深度优先和广度优先遍历,最后结束程序.
代码详单
adjlst.h
/*
* adjlst.h
* Impl a graph with adjacency list.
* Created by oziroe on May 30, 2017.
*/
#ifndef ADJLST_H
#define ADJLST_H
#define LNKLST_INIT_SIZE 4
#include "lnklst.h"
typedef struct {
int dst; // edge's destination
int wei; // edge's weight
} genedg_t;
typedef struct {
lnklst_t ** vtex; // edges' index start from a vertex
genedg_t * edge; // edges in the graph
int vlen; // number of vertex
int vmax; // length of `vtex`
int elen; // number of edges
int emax; // length of `edge`
} adjlst_t;
#ifndef ADJLST_INIT_ECOUNT
#define ADJLST_INIT_ECOUNT 64
#endif
// Create a new empty graph.
adjlst_t * adjlst_alloca(int vertex_length);
// Add a new vertex to graph. Output index of new vertex.
int adjlst_addvtx(adjlst_t *graph, int *out_vertex);
// Add a new edge to graph. (single-pass)
int adjlst_addedg(adjlst_t *graph, int source, genedg_t edge);
// Start to get all edges start from a vertex.
int adjlst_staitr(adjlst_t *graph, int vertex);
// Get current edge and move to next edge that start from a vertex.
// Return -1 if no more edge.
int adjlst_nxtedg(adjlst_t *graph, int vertex, genedg_t *out_edge);
// Print a graph in a proper way.
void adjlst_printf(adjlst_t *graph);
// Delete a graph.
void adjlst_destro(adjlst_t *graph);
typedef int adjlst_method_t(int current_vertex, genedg_t *current_edge,
int prev[], void *payload);
void adjlst_dfsexe(adjlst_t *graph, adjlst_method_t *callback,
int start_vertex, void *payload);
void adjlst_bfsexe(adjlst_t *graph, adjlst_method_t *callback,
int start_vertex, void *payload);
#endif
adjlst.c
#include <stdio.h>
#include <stdlib.h>
#include "adjlst.h"
#include "quelst.h"
adjlst_t *adjlst_alloca(int vlen) {
adjlst_t *graph = malloc(sizeof(adjlst_t));
if (!graph)
return NULL;
graph->vtex = malloc(sizeof(lnklst_t *) * vlen);
graph->edge = malloc(sizeof(genedg_t) * ADJLST_INIT_ECOUNT);
if (!graph->vtex || !graph->edge)
return NULL;
graph->vlen = graph->elen = 0;
graph->vmax = vlen;
graph->emax = ADJLST_INIT_ECOUNT;
return graph;
}
int adjlst_addvtx(adjlst_t *graph, int *vert) {
if (graph->vlen == graph->vmax)
return 1;
graph->vtex[graph->vlen] = lnklst_alloca();
if (!graph->vtex[graph->vlen])
return 1;
else {
*vert = graph->vlen;
graph->vlen++;
return 0;
}
}
int adjlst_addedg(adjlst_t *graph, int source, genedg_t edge) {
if (source >= graph->vlen || edge.dst >= graph->vlen)
return 1;
if (graph->elen == graph->emax) {
genedg_t *new_edge = realloc(graph->edge,
sizeof(genedg_t) * graph->emax * 2);
if (!new_edge)
return 2;
graph->edge = new_edge;
graph->emax *= 2;
}
graph->edge[graph->elen] = edge;
lnklst_t *vert = graph->vtex[source];
lnklst_append(vert, graph->elen);
graph->elen++;
return 0;
}
int adjlst_staitr(adjlst_t *graph, int vert) {
if (vert < 0 || vert >= graph->vlen)
return 1;
if (lnklst_setpos(graph->vtex[vert], 0))
return 2;
else
return 0;
}
static int next_index(adjlst_t *graph, int vert, int *index) {
if (vert < 0 || vert >= graph->vlen)
return 1;
if (lnklst_getval(graph->vtex[vert], index))
return 2;
if (lnklst_nxtpos(graph->vtex[vert]))
return -1;
else
return 0;
}
int adjlst_nxtedg(adjlst_t *graph, int vert, genedg_t *out) {
int index;
int status = next_index(graph, vert, &index);
if (status <= 0)
*out = graph->edge[index];
return status;
}
void adjlst_printf(adjlst_t *graph) {
printf("Vertex\tEdges\n");
for (int i = 0; i < graph->vlen; i++) {
printf("%d\t", i);
lnklst_printf(graph->vtex[i]);
}
printf("Edge\tDest\tWeight\n");
for (int i = 0; i < graph->elen; i++)
printf("%d\t%d\t%d\n", i, graph->edge[i].dst, graph->edge[i].wei);
}
void adjlst_destro(adjlst_t *graph) {
for (int i = 0; i < graph->vlen; i++)
lnklst_destro(graph->vtex[i]);
free(graph->vtex);
free(graph->edge);
free(graph);
}
static void dfs(adjlst_t *graph, adjlst_method_t *cb, int cur, int
through_edge,
int prev[], void *payload) {
int status = cb(cur,
through_edge < 0 ? NULL : &graph->edge[through_edge],
prev, payload);
if (status)
return;
if (adjlst_staitr(graph, cur))
return;
for (;;) {
int edge_index;
int no_more = next_index(graph, cur, &edge_index);
int dest = graph->edge[edge_index].dst;
if (prev[dest] < 0) {
prev[dest] = cur;
dfs(graph, cb, dest, edge_index, prev, payload);
}
if (no_more)
break;
}
}
void adjlst_dfsexe(adjlst_t *graph, adjlst_method_t *callback, int start,
void *payload) {
int *prev = malloc(sizeof(int) * graph->vlen);
for (int i = 0; i < graph->vlen; i++)
prev[i] = -1;
prev[start] = start;
dfs(graph, callback, start, -1, prev, payload);
free(prev);
}
void adjlst_bfsexe(adjlst_t *graph, adjlst_method_t *callback, int start,
void *payload) {
int *prev = malloc(sizeof(int) * graph->vlen);
for (int i = 0; i < graph->vlen; i++)
prev[i] = -1;
prev[start] = start;
if (callback(start, NULL, prev, payload)) {
free(prev);
return;
}
quelst_t *queue = quelst_alloca();
if (adjlst_staitr(graph, start)) {
free(prev);
return;
}
int no_more;
do {
int edge_index;
no_more = next_index(graph, start, &edge_index);
int dest = graph->edge[edge_index].dst;
if (prev[dest] < 0) {
quelst_append(queue, edge_index);
prev[dest] = start;
}
} while (!no_more);
while (quelst_length(queue) > 0) {
int edge_index;
quelst_poplft(queue, &edge_index);
int vert = graph->edge[edge_index].dst;
int status = callback(vert, &graph->edge[edge_index], prev,
payload);
if (status)
break;
if (adjlst_staitr(graph, vert))
continue;
int no_more;
do {
int edge_index;
no_more = next_index(graph, vert, &edge_index);
int dest = graph->edge[edge_index].dst;
if (prev[dest] < 0) {
quelst_append(queue, edge_index);
prev[dest] = vert;
}
} while (!no_more);
}
quelst_destro(queue);
free(prev);
}
adjlst_test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "adjlst.h"
#define NAME_LENGTH 31
#define NAME_LENGTH_STRING "31"
int print_graph(int cur, genedg_t *edge, int prev[], void *payload) {
char **names = (char **)payload;
if (edge)
printf("%s => %s.\n",
names[prev[cur]], names[cur]);
else
printf("Start: %s.\n", names[cur]);
return 0;
}
int input_vertex(int max, char *names[]) {
char name_buffer[NAME_LENGTH + 1];
scanf("%"NAME_LENGTH_STRING"s", name_buffer);
for (int i = 0; i < max; i++) {
if (!strcmp(name_buffer, names[i])) {
return i;
}
}
return -1;
}
int main(int argc, char *argv[]) {
printf("Graph Test Program\n");
printf("Usage: v name -> Add a new vertex called `name`.\n");
printf(" e s d w -> Add a new edge from `s` to `d` "
"and weight is `w`.\n");
printf(" d s -> DFS example start from `s`.\n");
printf(" b s -> BFS example start from `s`.\n");
printf(" q -> Quit.\n");
int vcount = 32;
if (argc > 1)
vcount = atoi(argv[1]);
adjlst_t *graph = adjlst_alloca(vcount);
char **names = malloc(sizeof(char *) * vcount);
for (int i = 0; i < vcount; i++) {
names[i] = malloc(sizeof(char) * (NAME_LENGTH + 1));
names[i][0] = '\0';
}
for (;;) {
printf("\nName Table:\n");
printf("Index\tName\n");
for (int i = 0; i < vcount; i++) {
if (names[i][0] != '\0') {
printf("%d\t%s\n", i, names[i]);
}
}
adjlst_printf(graph);
printf("\n>> ");
char command;
scanf("%c", &command);
switch (command) {
case 'v': {
char name_buffer[NAME_LENGTH + 1];
name_buffer[NAME_LENGTH] = '\0';
scanf("%"NAME_LENGTH_STRING"s", name_buffer);
int index = -1;
int status = adjlst_addvtx(graph, &index);
printf("Status: %d", status);
if (!status)
strcpy(names[index], name_buffer);
break;
}
case 'q': {
adjlst_destro(graph);
for (int i = 0; i < vcount; i++)
free(names[i]);
free(names);
return 0;
}
case 'e': {
int source_index = input_vertex(vcount, names);
if (source_index < 0) {
printf("No such source vertex.\n");
break;
}
int dest_index = input_vertex(vcount, names);
if (dest_index < 0) {
printf("No such destination vertex.\n");
break;
}
int weight;
scanf("%d", &weight);
genedg_t edge;
edge.dst = dest_index;
edge.wei = weight;
int status = adjlst_addedg(graph, source_index, edge);
printf("Status: %d\n", status);
break;
}
case 'd': {
int start = input_vertex(vcount, names);
if (start < 0) {
printf("No such start vertex.\n");
break;
}
adjlst_dfsexe(graph, print_graph, start, (void *)names);
break;
}
case 'b': {
int start = input_vertex(vcount, names);
if (start < 0) {
printf("No such start vertex.\n");
break;
}
adjlst_bfsexe(graph, print_graph, start, (void *)names);
break;
}
default:
break;
}
while (getchar() != '\n')
;
}
}
adjlst_test.txt
v v1
v v2
v v3
v v4
v v5
v v6
v v7
v v8
v v9
e v1 v2 12
e v2 v1 21
e v1 v3 13
e v3 v1 31
e v1 v4 14
e v4 v1 41
e v2 v3 23
e v3 v2 32
e v3 v6 36
e v6 v3 63
e v4 v6 46
e v6 v4 64
e v2 v5 25
e v5 v2 52
e v5 v7 57
e v7 v5 75
e v7 v9 79
e v9 v7 97
e v8 v9 89
e v9 v8 98
e v6 v8 68
e v8 v6 86
d v1
b v1
q
运行结果
adjlst_test.output.txt
Graph Test Program
Usage: v name -> Add a new vertex called `name`.
e s d w -> Add a new edge from `s` to `d` and weight is `w`.
d s -> DFS example start from `s`.
b s -> BFS example start from `s`.
q -> Quit.
Name Table:
Index Name
Vertex Edges
Edge Dest Weight
>> Status: 0
Name Table:
Index Name
0 v1
Vertex Edges
0 [>]
Edge Dest Weight
这里省略了其他构造图部分的输出
>> Start: v1.
v1 => v2.
v2 => v3.
v3 => v6.
v6 => v4.
v6 => v8.
v8 => v9.
v9 => v7.
v7 => v5.
Name Table:
Index Name
0 v1
1 v2
2 v3
3 v4
4 v5
5 v6
6 v7
7 v8
8 v9
Vertex Edges
0 [>0, 2, 4^]
1 [>1, 6, 12^]
2 [>3, 7, 8^]
3 [>5, 10^]
4 [>13, 14^]
5 [>9, 11, 20^]
6 [>15, 16^]
7 [>18, 21^]
8 [>17, 19^]
Edge Dest Weight
0 1 12
1 0 21
2 2 13
3 0 31
4 3 14
5 0 41
6 2 23
7 1 32
8 5 36
9 2 63
10 5 46
11 3 64
12 4 25
13 1 52
14 6 57
15 4 75
16 8 79
17 6 97
18 8 89
19 7 98
20 7 68
21 5 86
>> Start: v1.
v1 => v2.
v1 => v3.
v1 => v4.
v2 => v5.
v3 => v6.
v5 => v7.
v6 => v8.
v7 => v9.
Name Table:
Index Name
0 v1
1 v2
2 v3
3 v4
4 v5
5 v6
6 v7
7 v8
8 v9
Vertex Edges
0 [>0, 2, 4^]
1 [>1, 6, 12^]
2 [>3, 7, 8^]
3 [>5, 10^]
4 [>13, 14^]
5 [>9, 11, 20^]
6 [>15, 16^]
7 [>18, 21^]
8 [>17, 19^]
Edge Dest Weight
0 1 12
1 0 21
2 2 13
3 0 31
4 3 14
5 0 41
6 2 23
7 1 32
8 5 36
9 2 63
10 5 46
11 3 64
12 4 25
13 1 52
14 6 57
15 4 75
16 8 79
17 6 97
18 8 89
19 7 98
20 7 68
21 5 86
>>
课外专题实验
三、 背包问题求解
问题描述
有一个给定体积的背包和一堆物品,试找出所有将背包刚好装满的方案.
解题思路
该题可以使用递归与栈配合的方式求解.
由于本题所需的栈较为简单,所以使用一个全局数组 g_stack[]和一个用来储存栈顶位置的
全局变量 g_top 来表示.凡是在 g_stack 当中的元素被认为是装进了背包.
设当前状态如下:给定剩下的物品
items[]
和剩余空间
left_space
,则问题可以分为以下几种情
况:
1.
items
为空,则直接返回.
2. 头一件物品的体积比
left_space
大,则舍弃该物品,换下一件继续试.
3. 头一件物品的体积与
left_space
相等,则先将物品放进背包,输出当前的装配方案,再
将物品拿出背包,换下一件继续尝试.
4. 否则,先把物品放入背包,然后用新的
items
和新的
left_space
递归的调用;再将物品拿
出背包,再调用一次.
其中,输出当前的装配方案时,将栈内元素依次输出即可.
代码详单
/*
* backpack.c
* Solve backpack problem.
* Created by oziroe on May 31, 2017.
*/
#include <stdio.h>
int g_stack[1024];
int g_top = 0;
void fill(int items[], int count, int cur, int left_space) {
if (cur == count)
return;
if (items[cur] > left_space)
return fill(items, count, cur + 1, left_space);
g_stack[g_top++] = items[cur];
if (items[cur] == left_space) {
printf("(");
const char *prefix = "";
for (int i = 0; i < g_top; i++) {
printf("%s%d", prefix, g_stack[i]);
prefix = ", ";
}
printf(")\n");
g_top--;
}
else {
fill(items, count, cur + 1, left_space - items[cur]);
g_top--;
fill(items, count, cur + 1, left_space);
}
}
int main(void) {
int T, count, items[1024];
printf("Input T: ");
scanf("%d", &T);
printf("Input count: ");
scanf("%d", &count);
printf("Input %d items: ", count);
for (int i = 0; i < count; i++)
scanf("%d", &items[i]);
fill(items, count, 0, T);
return 0;
}
运行结果
四、 农夫过河问题
问题描述
一个农夫带着一只羊,一匹狼和一颗白菜一起过河,床上只能乘农夫与其他三样中的一个.农
夫不在的时候狼会吃掉羊,羊会吃掉白菜.求全部可行的过河方案.
解题思路
该题目可以通过构建以过河状态为顶点,以过河方式为边的图,通过搜索初始状态到最终状态
的路径来求解.由于要得到全部答案,因此可以采用任意方式遍历该图,这里使用了深度优先
搜索简化代码.
每一个状态由一个 4 位二进制数表示,最高位代表农夫是否过河:1 为已过河(北岸),0 为未过
河(南岸).其余 3 位分别代表狼,羊和白菜是否过河,意义同上.函数 print_status 接受一个状
态变量作为参数,检查其中的每一位,在屏幕上输出.
该图由于难以在程序运行之前确定各边,因此采用"走一步看一步"的策略.即每遍历到一个顶
点时,进行一下流程:
检查该顶点是否已是终点.若是则输出整个状态序列.
获取全部由当前状态可以到达的状态,并依次检查终点是否已经路过.若没有,则换终点递
归进行当前流程.
其中获取当前状态可以到达的状态的过程如下:首先将农夫位取反,代表农夫孤身一人过河,
作为第一个可以到达的状态;然后将原来与农夫位相同的位依次取反,作为余下的状态.
这里注意的一点是存储路径的数组若使用 prev,则获得的路径是反序的,不方便输出.因此这
里使用的是 next,在每次递归遍历下一个顶点前将当前顶点存入对应位置.
代码详单
/*
* farmer.c
* Solve farmer cross river problem.
* Created by oziroe on May 30, 2017.
*/
#include <stdio.h>
// General Data Model:
// status = 0b 0 1 0 1
// f w s c 0 => Not cross 1 => crossed
void print_status(int s) {
for (int i = 0b1000; i; i >>= 1)
printf("%s\t", s & i ? "北岸" : "南岸");
printf("\n");
}
int possible_index(int i) {
if (!!(i & 8) != !!(i & 4) && !!(i & 4) == !!(i & 2))
return 0;
if (!!(i & 8) != !!(i & 2) && !!(i & 2) == !!(i & 1))
return 0;
return 1;
}
void to_next_status(int cur, int next[16]) {
if (cur == 0b1111) {
printf("解决方案（之一）：\n");
printf("农夫\t 狼\t 羊\t 白菜\n");
for (int s = 0; s != cur; s = next[s])
print_status(s);
print_status(cur);
printf("\n");
return;
}
// Farmer crosses the river.
int newcur = cur ^ 0b1000;
if (possible_index(newcur)) {
if (next[newcur] < 0) {
next[cur] = newcur;
to_next_status(newcur, next);
}
}
for (int i = 0b0001; i <= 0b0100; i <<= 1) {
// Cross each item that was on the same side of farmer.
if (!!(newcur & i) != !!(newcur & 0b1000)) {
newcur ^= i;
if (possible_index(newcur) && next[newcur] < 0) {
next[cur] = newcur;
to_next_status(newcur, next);
}
newcur ^= i; // Cross back.
}
}
next[cur] = -1;
}
int main(void) {
int next[16];
for (int i = 0; i < 16; i++)
next[i] = -1;
to_next_status(0, next);
return 0;
}
运行结果
五、 约瑟夫环问题
问题描述
有 n 个人围成一圈,每个人掌握着一个数作为自己的密码.以一个初始的 m,从第一个人开始
报数,报到 m 的人出队,将自己的密码作为密文的下一个数字,同时作为新的 m 继续报数.给定
每个人的密码以及初始的 m,模拟求密文.
解题思路
可以用一个循环链表模拟该密文的生成过程.使用一个数组作为数据结构,用一个循环变量作
为当前位置的指示,并当该变量超出[0,n)的范围时将其置为 0(或 n-1),从而达到循环访问每一
个元素的效果.删除元素时将其位置上的数据改为-1 作为墓碑标志,在接下来的遍历当中将
其跳过.
模拟报数过程中注意的一点:实际上,只需要数 m-1 个人即可得到报出数 m 的人,但是在其出
列以后要从其后的下一个人开始重新报数,因此为简化代码,将初始位置设置为第一个人的前
一个人(即最后一个人),然后每次都数 m 个人即可得到正确结果.
代码详单
/*
* josephus.c
* Solve Josephus problem by simulating.
* Created by oziroe on May 31, 2017.
*/
#include <stdio.h>
int main(void) {
int n, m, person[1024];
printf("Input n: ");
scanf("%d", &n);
printf("Input %d person's secret: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &person[i]);
printf("Input initial m: ");
scanf("%d", &m);
int pos = n - 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pos++;
if (pos >= n)
pos = 0;
if (person[pos] < 0)
j--;
}
printf("%d ", person[pos]);
m = person[pos];
person[pos] = -1;
}
printf("\n");
return 0;
}
运行结果
六、 霍夫曼压缩/解压缩的实现
问题描述
写一个程序,可以对任意的文件进行压缩和解压缩,并采用霍夫曼编码的方式.
求解思路
该程序主要分为三部分:构建霍夫曼树,压缩和解压缩.
在整个程序中使用四个平行数组作为树的表示,分别存储每一个节点的父节点,左/右子节点
和数据本身.其实表示子节点的数组有大约一半的浪费,不过在此问题当中可以忽略不计.
该程序以字节为单位进行霍夫曼编码.因此会构建一颗共 256 个叶子节点的霍夫曼树.压缩只
需要用到存储父节点和存储左子节点的两个数组,通过从代表该数组字节的叶子结点走到根
节点来得到逆序的霍夫曼编码,因此需要维护一个本地栈(与 backpack 中的结构相同)来方便
调整顺序.在写压缩后的数据时,按照每一个字节内由低至高的顺序依次填满每一个比特位.
最后一个字节可以不填满,函数返回一共使用了的比特位数.
解压缩时只需要用到存储左/右子节点的数组,通过不断从根节点开始,按照压缩后的数据向
下方行走,直到走到一个叶子结点即解码成功一个字节,然后回到根节点继续.之前返回的比
特位数用于标记结束位置.
在压缩后的文件中储存以下信息:magic code,压缩格式版本,压缩前的字节数,压缩后的比特
数,左/右子节点数组(解压缩只需要这两个数组),以及压缩后的数据.
要注意的是在压缩时为了效率,没有预先对压缩数组进行清零处理,而是在写入时先将其置为
零再与压缩的编码进行按位或来实现的.
代码详单
/*
* huffman.c
* An impl of Huffman compression.
* Created by oziroe on May 31, 2017.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int VERSION = 1;
void count_bytes(unsigned char bytes[], int length, float count[]) {
for (int i = 0; i <= 0xff; i++)
count[i] = 0;
for (int i = 0; i < length; i++)
count[(int)bytes[i]] += 1;
for (int i = 0; i <= 0xff; i++)
count[i] /= length;
}
void make_tree(float count[], int parent[], int left[], int right[]) {
int used[0x1ff];
for (int i = 0; i < 0x1ff; i++)
used[i] = 0;
float weight[0x1ff];
for (int i = 0; i <= 0xff; i++)
weight[i] = count[i];
for (int pos = 0x100; pos < 0x1ff; pos++) {
int min1 = -1, min2 = -1;
for (int i = 0; i < pos; i++) {
if (used[i])
continue;
if (min1 < 0 || weight[i] < weight[min1]) {
min2 = min1;
min1 = i;
}
else if (min2 < 0 || weight[i] < weight[min2])
min2 = i;
}
weight[pos] = weight[min1] + weight[min2];
parent[min1] = parent[min2] = pos;
left[pos] = min1;
right[pos] = min2;
used[min1] = used[min2] = 1;
}
}
int decompress(unsigned char buffer[], int max, unsigned char coded[],
int length, int left[], int right[]) {
int i = 0;
int pos = 0x1fe;
for (int j = 0; i < max && j < length; j++) {
int bit = coded[j / 8] & (1 << j % 8);
if (bit)
pos = left[pos];
else
pos = right[pos];
if (pos <= 0xff) {
buffer[i++] = pos;
pos = 0x1fe;
}
}
return i;
}
int compress(unsigned char buffer[], int max, unsigned char raw[], int
length,
int parent[], int left[]) {
int i = 0;
for (int j = 0; j < length && i < max * 8; j++) {
int stack[0xff], top = 0;
int pos = raw[j];
while (pos != 0x1fe) {
if (pos == left[parent[pos]])
stack[top++] = 1;
else
stack[top++] = 0;
pos = parent[pos];
}
while (top > 0 && i < max * 8) {
buffer[i / 8] = (buffer[i / 8] & ~(1 << i % 8)) |
(stack[--top] << i % 8);
i++;
}
}
return i;
}
int main(int argc, char *argv[]) {
if (argc != 4 || strlen(argv[1]) != 1)
return 1;
switch (argv[1][0]) {
case 'c': {
FILE *raw_file = fopen(argv[2], "rb");
fseek(raw_file, 0, SEEK_END);
long raw_size = ftell(raw_file);
rewind(raw_file);
unsigned char *raw = malloc(raw_size);
fread(raw, raw_size, 1, raw_file);
fclose(raw_file);
float count[0x100];
int parent[0x1ff], left[0x1ff], right[0x1ff];
count_bytes(raw, raw_size, count);
make_tree(count, parent, left, right);
unsigned char *zipped = malloc(raw_size);
int bit = compress(zipped, raw_size, raw, raw_size, parent,
left);
if (bit == raw_size * 8) {
printf("This file is not suitable for zipping.\n");
goto finalize;
}
FILE *zip_file = fopen(argv[3], "wb");
fwrite("\xf0\xf1" "LiMeng", sizeof(char), 8, zip_file);
fwrite(&VERSION, sizeof(int), 1, zip_file);
fwrite(left, sizeof(int), 0x1ff, zip_file);
fwrite(right, sizeof(int), 0x1ff, zip_file);
fwrite(&bit, sizeof(int), 1, zip_file);
fwrite(&raw_size, sizeof(long), 1, zip_file);
fwrite(zipped, bit / 8 + 1, 1, zip_file);
fclose(zip_file);
finalize:
free(raw);
free(zipped);
break;
}
case 'd': {
int left[0x1ff], right[0x1ff], bit, ver;
long byte;
char magic[8];
FILE *zip_file = fopen(argv[2], "rb");
fread(magic, sizeof(char), 8, zip_file);
fread(&ver, sizeof(int), 1, zip_file);
if (memcmp(magic, "\xf0\xf1" "LiMeng", 8) || ver != VERSION)
{
printf("This is not a valid zip file.\n");
return 3;
}
fread(left, sizeof(int), 0x1ff, zip_file);
fread(right, sizeof(int), 0x1ff, zip_file);
fread(&bit, sizeof(int), 1, zip_file);
unsigned char *zipped = malloc(bit / 8 + 1);
fread(&byte, sizeof(long), 1, zip_file);
unsigned char *raw = malloc(byte);
fread(zipped, bit / 8 + 1, 1, zip_file);
fclose(zip_file);
decompress(raw, byte, zipped, bit, left, right);
FILE *raw_file = fopen(argv[3], "wb");
fwrite(raw, byte, 1, raw_file);
fclose(raw_file);
free(raw);
free(zipped);
break;
}
default:
return 2;
}
return 0;
}
运行结果
其中可以看到,压缩后的文件为 6.4K,其中约 4K 为霍夫曼树(4bytes * 511 * 2),因此实际上将数
据压缩至原来的 28%.该数据随着被压缩文件的变化而剧烈变化,对于可执行程序这种大占比
为零字节的文件有很好的压缩效果.
