# 資料結構Week04補充

## 班級 學號 姓名

1. 建立一個三個節點的雙向鏈結串列，呈現程式碼以及執行的截圖。

typedef struct node {
	int data;
	struct node *prev;
	struct node *next;
} DNODE;

DNODE *d1,*d2,*d3;
d1=malloc(sizeof(DNODE));
d1->data = 10;
d2=malloc(sizeof(DNODE));
d2->data = 20;
d3=malloc(sizeof(DNODE));
d3->data = 30;
d1->prev = NULL;
d1->next = d2;
d2->prev = d1;
d2->next = d3;
d3->prev = d2;
d3->next = NULL;

2. 多項式$f(x)=5x^4-4x+1$為例，寫出下列表示方式。

- 一維陣列(索引值即為次數)

int a[5]; // 5:最高次項+1
a[4]=5;
a[1]=-4;
a[0]=1;

- 二維陣列(係數與次數)

int a[3][2]; // 3:共有3個非零項 
a[0][0]=5; a[0][1]=4;
a[1][0]=-4; a[1][1]=1;
a[2][0]=1; a[2][1]=1    

- 結構陣列

typedef struct node {
    int coef;
    int exp;
} POLY;

POLY a[3]; // 3:共有3個非零項
a[0].coef=5; a[0].exp=4;
a[1].coef=-4; a[1].exp=1;
a[2].coef=1; a[2].exp=0;

- 鏈結串列

typedef struct node {
    int coef;
    int exp;
    struct node *next;
} POLY;

POLY *a[3]; // 3:共有3個非零項
a[0]=malloc(sizeof(POLY));
a[0]->coef=5;
a[0]->exp=4;
a[1]=malloc(sizeof(POLY));
a[1]->coef=-4;
a[1]->exp=1;
a[2]=malloc(sizeof(POLY));
a[2]->coef=1;
a[2]->exp=0;
a[0]->next=a[1];
a[1]->next=a[2];
a[2]->next=NULL;

3. 寫出下列稀疏矩陣的表示方式。

$$\left(
\begin{array}{c}
1 & 0 & 0 & 9 \\
0 & 0 & 9 & 0 \\
0 & 0 & 0 & 4 \\
0 & -7 & 0 & 0
\end{array}
\right)$$

- 使用二維陣列

# define M 4
# define N 4

int a[M][N]={{1,0,0,9},{0,0,9,0},{0,0,0,4},{0,-7,0,0}};

- 使用一維結構陣列

typedef struct node {
    int row;
    int col;
    int value;
} POLY;

POLY a[5]; // 5:共有5個非零項
a[0].row=0; a[0].col=0; a[0].value=1;
a[1].row=0; a[1].col=3; a[0].value=9;
a[2].row=1; a[2].col=2; a[0].value=9;
a[3].row=2; a[3].col=3; a[0].value=4;
a[4].row=3; a[1].col=1; a[0].value=-7;

- 使用鏈結串列

typedef struct node {
    int row;
    int column;
    int value;
    struct node *next;
} SparseMatrix;

SparseMatrix *a[5]; // 5:共有5個非零項
a[0]=malloc(sizeof(SparseMatrix));
a[0]->row=0;
a[0]->column=0;
a[0]->value=1;
a[1]=malloc(sizeof(SparseMatrix));
a[1]->row=0;
a[1]->column=3;
a[1]->value=9;
a[2]=malloc(sizeof(SparseMatrix));
a[2]->row=1;
a[2]->column=2;
a[2]->value=9;
a[3]=malloc(sizeof(SparseMatrix));
a[3]->row=2;
a[3]->column=3;
a[3]->value=4;
a[4]=malloc(sizeof(SparseMatrix));
a[4]->row=3;
a[4]->column=1;
a[4]->value=-7;
a[0]->next=a[1]; a[1]->next=a[2]; a[2]->next=a[3]; a[3]->next=a[4];

- 使用多個鏈結串列

struct row_list {
    int row_index;
    struct row_list *link_down;
    struct value_list *link_right;
};
struct value_list {
    int colum_index;
    int value;
    struct value_list *next;
}
struct row_list *h = NULL, *p;

**留給考試用**