Ch5-4-1e.c

#include< stdio.h>
#include< stdlib.h>
/* 堆疊節點的宣告 */
struct Node
{
int data; /* 儲存堆疊資料 */
struct Node *next; /* 指向下一節點 */
};

typedef struct Node SNode; /* 堆疊節點的新型態 */
typedef SNode *LStack; /* 串列堆疊的新型態 */
LStack top = NULL; /* 堆疊頂端的指標 */

/* 函數: isStackEmpty() 檢查堆疊是否是空的 */
int isStackEmpty()
{
if ( top == NULL )
return 1;
else
return 0;
}

/* 函數: push() 將資料存入堆疊 */
void push(int d)
{
LStack new_node; /* 新節點指標 */
/* 配置節點記憶體 */
new_node = (LStack)malloc(sizeof(SNode));
new_node->data = d; /* 建立節點內容 */
new_node->next = top; /* 新節點指向原開始 */
top = new_node; /* 新節點成為堆疊開始 */
}

/* 函數: pop() 從堆疊取出資料 */
int pop()
{
LStack ptr; /* 指向堆疊頂端 */
int temp;
if ( !isStackEmpty() )
{ /* 堆疊是否是空的 */
ptr = top; /* 指向堆疊頂端 */
top = top->next; /* 堆疊指標指向下節點 */
temp = ptr->data; /* 取出資料 */
free(ptr); /* 釋回節點記憶體 */
return temp; /* 堆疊取出 */
}
else
return -1;
}

/* 主程式: 使用回溯方法在陣列走迷宮 */
int main()
{
/* 迷宮陣列, 數字 0 可走, 1 不可走 */
int maze[7][10] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 1, 0, 0, 0, 0, 1,
1, 0, 1, 1, 0, 0, 1, 1, 0, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
1, 0, 1, 0, 1, 0, 0, 0, 1, 1,
1, 0, 1, 0, 0, 0, 1, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int i, j;
int x = 5; /* 迷宮入口座標 */
int y = 8;
maze[5][8] = 7; /* 標示迷宮入口位置 */

printf("\n　迷宮路徑圖(請從右下角(７)走到左上角)\n");
printf("\n數字 0：尚未走過的路徑\t數字 1：牆壁\n");
printf("數字 7：迷宮起始點\n");
for ( i = 0; i <= 6; i++)
{ /* 顯示迷宮圖形 */
for ( j = 0; j <= 9; j++)
printf("%d ", maze[i][j]); /* 顯示座標值 */
printf("\n");
}
printf("\n 想好了嗎？\n");
system("PAUSE");
while ( x != 1 || y != 1 )
{ /* 主迴圈 */
maze[x][y] = 2; /* 標示為已走過的路 */
if ( maze[x-1][y] <= 0 )
{ /* 往上方走 */
x = x - 1; /* 座標x減1 */
push(x); /* 存入路徑 */
push(y);
}
else
if ( maze[x+1][y] <= 0 )
{ /* 往下方走 */
x = x + 1; /* 座標x加1 */
push(x); /* 存入路徑 */
push(y);
}
else
if ( maze[x][y-1] <= 0 )
{ /* 往左方走 */
y = y - 1; /* 座標y減1 */
push(x); /* 存入路徑 */
push(y);
}
else
if ( maze[x][y+1] <= 0 )
{ /* 往右方走 */
y = y + 1; /* 座標y加1 */
push(x); /* 存入路徑 */
push(y);
}
else
{ /* 沒有路可走:迴溯 */
maze[x][y] = 3; /* 表示是迴溯的路 */
y = pop(); /* 退回一步 */
x = pop();
}
}
maze[x][y] = 9; /* 標示最後位置 */
printf("\n　迷宮完成圖(從右下角走出左上角(９))\n");
for ( i = 0; i <= 6; i++)
{ /* 顯示迷宮圖形 */
for ( j = 0; j <= 9; j++)
printf("%d ", maze[i][j]); /* 顯示座標值 */
printf("\n");
}
printf("\n數字 0：尚未走過的路徑\t數字 1：牆壁\n");
printf("數字 2：走過的路徑\t數字 3：回溯路徑\n");
printf("\n　哇!終於走出來囉\n");
system("PAUSE");
return 0;
}

ch4-6e.c

#include< stdio.h>
#include< stdlib.h>
struct Node { /* Node節點結構 */
float coef; int exp; /* 結構變數宣告 */
struct Node *next; /* 指向下一個節點 */
};
typedef struct Node PNode; /* 多項式串列節點的新型態 */
typedef PNode *PList; /* 多項式串列的新型態 */
//#include "createPoly.c"
/* 程式範例: createPoly.c */
/* 函數: 建立多項式的串列 */
PList createPoly(int len, float *array) {
int i;
PList first, ptr, newnode; /* 建立開頭節點 */
first = (PList) malloc(sizeof(PNode));
first->coef = 0.0; /* 建立開頭節點的內容 */
first->exp = -1;
ptr = first; /* 前一個節點指標 */
for ( i = len-1; i >= 0; i-- ) {
if ( array[i] != 0.0 ) { /* 配置節點記憶體 */
newnode = (PList) malloc(sizeof(PNode));
newnode->coef = array[i]; /* 建立節點的內容 */
newnode->exp = i;
ptr->next = newnode; /* 連結新節點 */
ptr = newnode; /* 成為前一個節點 */
}
}
ptr->next = first; /* 連結第1個節點, 建立環狀串列 */
return first;
}
/* 函數: 顯示多項式 */
void printPoly(PList first) {
PList ptr = first->next; /* 串列真正的開頭 */
float c;
int e;
while ( ptr != first ) { /* 顯示主迴圈 */
c = ptr->coef;
e = ptr->exp;
printf("%3.1fX^%d", c, e);
ptr = ptr->next; /* 下一個節點 */
if ( ptr != first ) printf("+");
}
printf("\n");
}
/* 主程式 */
int main() {
PList a = NULL; /* 多項式串列1的開頭指標 */
PList b = NULL; /* 多項式串列2的開頭指標 */
/* 建立多項式物件所需的陣列 */
float list1[5] = { 3, 4, 0, 5, 1};
float list2[5] = { 5, 2, 5, 0, 0};
a = createPoly(5, list1); /* 建立多項式串列1 */
b = createPoly(5, list2); /* 建立多項式串列2 */
printf("f(x)=");
printPoly(a); /* 顯示多項式1 */
printf("g(x)=");
printPoly(b); /* 顯示多項式2 */
system("PAUSE");
return 0;
}

ch4-3-2e.c

#include< stdio.h>
#include< stdlib.h>
/* 程式範例: Ch4-3.h */
struct Node { /* Node節點結構 */
int data; /* 結構變數宣告 */
struct Node *next; /* 指向下一個節點 */
};

typedef struct Node LNode; /* 串列節點的新型態 */
typedef LNode *List; /* 串列的新型態 */
List first = NULL; /* 串列的開頭指標 */
/* 函數: 建立串列 */
void createList(int len, int *array) {
int i;
List newnode;
for ( i = 0; i < len; i++ ) { /* 配置節點記憶體 */ newnode = (List) malloc(sizeof(LNode)); newnode->data = array[i]; /* 建立節點內容 */
newnode->next = first;
first = newnode;
}
}
/* 函數: 檢查串列是否是空的 */
int isListEmpty() {
if ( first == NULL ) return 1;
else return 0;
}
/* 函數: 顯示串列資料 */
void printList() {
List current = first; /* 目前的串列指標 */
while ( current != NULL ) { /* 顯示主迴圈 */
printf("[%d]", current->data);
current = current->next; /* 下一個節點 */
}
printf("\n");
}
/* 函數: 搜尋節點資料 */
List searchNode(int d) {
List current = first; /* 目前的串列指標 */
while ( current != NULL ) { /* 搜尋主迴圈 */
if ( current->data == d ) /* 是否找到資料 */
return current; /* 找到 */
current = current->next; /* 下一個節點 */
}
return NULL; /* 沒有找到 */
}
/* 程式範例: deleteNode.c */
/* 函數: 刪除節點 */
int deleteNode(List ptr) {
List current = first; /* 指向前一節點 */
int value = ptr->data; /* 取得刪除的節點值 */
if ( isListEmpty() ) /* 檢查串列是否是空的 */
return -1;
if (ptr==first || ptr==NULL) {/* 串列開始或NULL */
first = first->next; /* 刪除第1個節點 */
} else {
while (current->next!=ptr) /* 找節點ptr的前節點 */
current = current->next;
current->next = ptr->next; /* 刪除中間節點 */
}
free(ptr); /* 釋放節點記憶體 */
return value; /* 傳回刪除的節點值 */
}
/* 主程式 */
int main() {
int temp; /* 宣告變數 */
int data[6]={ 1, 2, 3, 4, 5, 6 };/* 建立串列的陣列 */
List ptr;
createList(6, data); /* 建立串列 */
printf("原來的串列: ");
printList(); /* 顯示串列 */
/* 4-3-2: 節點刪除 */
temp = 0;
while ( temp != -1 ) {
printf("請輸入刪除的郵寄編號(-1結束) ==> ");
scanf("%d", &temp); /* 讀取郵寄編號 */
if ( temp != -1 ) { /* 搜尋節點資料 */
ptr = searchNode(temp); /* 找尋節點 */
if ( ptr != NULL ) {
temp = deleteNode(ptr); /* 刪除節點 */
printf("刪除節點: %d\n", temp);
printf("刪除後串列: ");
printList(); /* 顯示刪除後串列 */
}
}
}
system("PAUSE");
return 0;
}

ch4-3-3e.c

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

/* 程式範例: Ch4-3.h */
struct Node { /* Node節點結構 */
int data; /* 結構變數宣告 */
struct Node *next; /* 指向下一個節點 */
};
typedef struct Node LNode; /* 串列節點的新型態 */
typedef LNode *List; /* 串列的新型態 */
List first = NULL; /* 串列的開頭指標 */
/* 函數: 建立串列 */
void createList(int len, int *array) {
int i;
List newnode;
for ( i = 0; i < len; i++ ) { /* 配置節點記憶體 */ newnode = (List) malloc(sizeof(LNode)); newnode->data = array[i]; /* 建立節點內容 */
newnode->next = first;
first = newnode;
}
}
/* 函數: 檢查串列是否是空的 */
int isListEmpty() {
if ( first == NULL ) return 1;
else return 0;
}
/* 函數: 顯示串列資料 */
void printList() {
List current = first; /* 目前的串列指標 */
while ( current != NULL ) { /* 顯示主迴圈 */
printf("[%d]", current->data);
current = current->next; /* 下一個節點 */
}
printf("\n");
}
/* 函數: 搜尋節點資料 */
List searchNode(int d) {
List current = first; /* 目前的串列指標 */
while ( current != NULL ) { /* 搜尋主迴圈 */
if ( current->data == d ) /* 是否找到資料 */
return current; /* 找到 */
current = current->next; /* 下一個節點 */
}
return NULL; /* 沒有找到 */
}

/* 程式範例: insertNode.c */
/* 函數: 插入節點 */
void insertNode(List ptr, int d) {
List newnode;
/* 配置節點記憶體 */
newnode = (List) malloc(sizeof(LNode));
newnode->data = d; /* 指定節點值 */
if ( ptr == NULL ) {
/* 情況1: 插入第一個節點 */
newnode->next = first; /* 新節點成為串列開始 */
first = newnode;
}else {
newnode->next=ptr->next;/* 新節點指向下一節點 */
ptr->next = newnode; /* 節點ptr指向新節點 */
}
}
/* 主程式 */ int main() {
int temp; /* 宣告變數 */
int data[6]={ 1, 2, 3, 4, 5, 6 };/* 建立串列的陣列 */
List ptr;
createList(6, data); /* 建立串列 */
printf("原來的串列: ");
printList(); /* 顯示串列 */
/* 4-3-3: 節點插入 */
temp = 0;
insertNode(NULL, 50); /* 插入第一個節點 */
printf("插入後串列: ");
printList(); /* 顯示插入後串列 */
while ( temp != -1 ) {
printf("請輸入插入其後的郵寄編號(-1結束) ==> ");
scanf("%d", &temp); /* 讀取郵寄編號 */
if ( temp != -1 ) {
ptr = searchNode(temp); /* 找尋節點 */
if ( ptr != NULL )
printf("請輸入新的郵寄編號(0~100) ==> ");
scanf("%d", &temp); /* 讀取新的郵寄編號 */
insertNode(ptr, temp);
printf("插入後串列: ");
printList(); /* 顯示插入後串列 */
}
}
system("PAUSE");
return 0;
}

ch4-5-3e.c

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

struct Node { /* Node節點結構 */
int data; /* 結構變數宣告 */
struct Node *next; /* 指向下一個節點 */
struct Node *previous; /* 指向前一個節點 */
};
typedef struct Node DNode; /* 雙向串列節點的新型態 */
typedef DNode *DList; /* 雙向串列的新型態 */
DList first = NULL; /* 雙向串列的開頭指標 */
DList now = NULL; /* 雙向串列目前節點指標 */
/* 程式範例: createDList.c - 函數: 建立雙向串列 */
void createDList(int len, int *array) {
int i;
DList newnode, before; /* 配置第1個節點 */
first = (DList) malloc(sizeof(DNode));
first->data = array[0]; /* 建立節點內容 */
first->previous = NULL; /* 前節點指標為NULL */
before = first; /* 指向第一個節點 */
now = first; /* 重設目前節點指標 */
for ( i = 1; i < len; i++ ) { /* 配置節點記憶體 */ newnode = (DList) malloc(sizeof(DNode)); newnode->data = array[i]; /* 建立節點內容 */
newnode->next = NULL; /* 下節點指標為NULL */
newnode->previous=before; /* 將新節點指向前節點 */
before->next=newnode; /* 將前節點指向新節點 */
before = newnode; /* 新節點成為前節點 */
}
}
/* 函數: 顯示雙向串列的節點資料 */
void printDList() {
DList current = first; /* 目前的節點指標 */
while ( current != NULL ) { /* 顯示主迴圈 */
if ( current == now )
printf("#%d#", current->data);
else
printf("[%d]", current->data);
current = current->next; /* 下一個節點 */
}
printf("\n");
}
/* 函數: 移動節點指標到下一個節點 */
void nextNode() {
if ( now->next != NULL )
now = now->next; /* 下一個節點 */
}
/* 函數: 移動節點指標到上一個節點 */
void previousNode() {
if ( now->previous != NULL )
now = now->previous; /* 前一個節點 */
}
/* 函數: 重設節點指標 */
void resetNode() { now = first; }
/* 函數: 取得節點指標 */
DList readNode() { return now; }
/* 程式範例: insertDNode.c - 函數: 插入節點 */
void insertDNode(DList ptr, int d) {
/* 配置節點記憶體 */
DList newnode = (DList) malloc(sizeof(DNode));
newnode->data = d; /* 建立節點內容 */
if ( first == NULL ) /* 如果串列是空的 */
first = newnode; /* 傳回新節點指標 */
if ( ptr == NULL ) {
/* 情況1: 插在第一個節點之前, 成為串列開始 */
newnode->previous = NULL; /* 前指標為NULL */
newnode->next = first; /* 新節點指向串列開始 */
first->previous = newnode;/* 原節點指向新節點 */
first = newnode; /* 新節點成為串列開始 */
}
else {
if ( ptr->next == NULL ) {/* 是否是最後一個節點 */
/* 情況2: 插在串列的最後 */
ptr->next = newnode; /* 最後節點指向新節點 */
newnode->previous=ptr; /* 新節點指回最後節點 */
newnode->next = NULL; /* 後回指標為NULL */
}
else {
/* 情況3: 插入節點至串列的中間節點 */
ptr->next->previous = newnode; /* 指回新節點 */
newnode->next = ptr->next; /* 指向下一節點 */
newnode->previous=ptr; /* 新節點指回插入節點 */
ptr->next = newnode; /* 插入節點指向新節點 */
}
}
}
/* 程式範例: deleteDNode.c - 函數: 刪除節點 */
void deleteDNode(DList ptr) {
if ( ptr->previous == NULL ) { /* 是否有前一個節點 */
/* 情況1: 刪除第一個節點 */
first = first->next; /* 指向下一個節點 */
first->previous = NULL; /* 設定指向前節點指標 */
}
else {
if ( ptr->next == NULL ) { /* 是否有下一個節點 */
/* 情況2: 刪除最後一個節點 */
ptr->previous->next = NULL; /* 前節點指向NULL */
}
else {
/* 情況3: 刪除中間的節點 - 前節點指向下一節點 */
ptr->previous->next = ptr->next;
/* 下一節點指向前節點 */
ptr->next->previous = ptr->previous;
}
}
free(ptr); /* 釋回刪除節點記憶體 */
}
/* 主程式 */
int main() {
char temp; /* 宣告變數 */
int data[6]={ 1, 2, 3, 4, 5, 6 }; /* 建立串列的陣列 */
createDList(6, data); /* 建立雙向串列 */
while ( temp != 'E' && temp != 'e' ) {
printf("原來的串列: ");
printDList(); /* 顯示雙向串列 */
printf("[F]往下移動 [B]往前移動 [A]新增節點 [D]刪除節點");
printf("[R]重設 [V]節點值 [E]離開 ==> ");
scanf("%s", &temp); /* 讀入選項 */
switch ( temp ) {
case 'F':
case 'f':
nextNode(); /* 往下移動 */
break;
case 'B':
case 'b':
previousNode(); /* 往前移動 */
break;
case 'A':
case 'a': printf("請輸入新號碼(7~100) ==> ");
scanf("%d", &temp); /* 讀取新編號 */
insertDNode(readNode(), temp);
resetNode(); /* 重設目前指標 */
break;
case 'D':
case 'd':
deleteDNode(readNode());
resetNode(); /* 重設目前指標 */
break;
case 'R':
case 'r':
resetNode();
break;
case 'V':
case 'v':
printf("節點值: %d\n", readNode()->data);
break;
}
}
system("PAUSE");
return 0;
}

花心

蘇格蘭狗