基本練習題 1. 請參照圖 3.4a 的 table 陣列, 如果先在 中國 之後加入 法國, 然後在 蘇 答 : (A) (B) 俄 之後加入 澳大利亞 : A. 請畫出最後的 table 陣列 B. 請以鏈結串列圖示法表示 table 陣列 data next table[0] 3 table[1] 美 國 6 table[2] 法國 1 table[3] 中國 2 table[4] 澳大利亞 0 table[5] -1 table[6] 英國 7 table[7] 蘇俄 4 table[8] -1 0 5 2 1 6 7 4 5 中 2 法 1 美 6 英 7 蘇 4 澳 0 首節點 2. 有一個線性雙向鏈結串列示意圖如下 : 答 : 0 5 3 2 6 Head 若欲將此雙向鏈結串列表示在下面的陣列中, 請完成其他部分 data left right table[0] 0 5 table[1] 81 99 38 56 table[2] 38 3 6
table[3] 99 5 2 table[4] table[5] 81 0 3 table[6] 56 2 0 table[7] table[8] 3. 設計程式處理稀疏矩陣 ( sparse matrix ) 問題時, 如考慮儲存空間的需求, 哪一種資料結構最為適合? 答 : 鏈結串列 4. 承上題, 請畫圖說明處理稀疏矩陣問題時, 每個非零項的結構如何? 並且以 C/C++ 語言設計這種結構 答 : 每個節點可以圖示為 : row down col data right 每個節點結構有 3 個資料欄位 data row col, 還有兩個鏈結欄位 right down 同一列的節點藉著 right 鏈結成為一個串列, 同一行節點也藉著 down 鏈結成為一個串列 節點的結構可以宣告為 : 1. typedef struct tagmlistnode 2. float data ; // 係數欄位 3. int row, col ; // 列號及行號 4. struct tagmlistnode *right, *down ; // 列指標及行指標 5. MListNode ; 5. 設計程式處理高次少項的多項式 ( polynomial ) 問題時, 如考慮儲存空間的 需求, 哪一種資料結構最為適合? 答 : 鏈結串列 6. 承上題, 請畫圖說明處理多項式問題時, 每個非零項的結構如何? 並且以 C/C++ 語言設計這種結構 答 : 每個節點必須包含兩個資料欄位 : 係數欄位和冪次欄位, 以及一個鏈結欄位 節點結構可以圖示為 :
係數 冪次 鏈結 節點結構可以宣告為 : 1. typedef struct tagplistnode 2. float coef ; // 係數 3. int expo ; // 冪次 4. struct tagplistnode *next ; // 鏈結指標 5 PListNode; 7. 動態配置節點的鏈結串列如下, 若執行 printf( %d,q->next->data) ( 或是 cout << q->next->data) 會印出什麼? Head q p 1 6 7 10 答 :7 8. 承上題, 若執行 for( i = 1; i < 9; i++ ) p = p->next ; printf( %d, p->data); // 或是 cout << p->data; 會印出什麼? 答 :1 進階練習題 1. 承基本練習題第 7 題, 若要插入由指標 n 所指到的新節點至指標 p 所指到的節點之後, 第一步須執行何敘述? 請畫圖說明此敘述 答 : n->next = p->next; Head q p 1 6 7 10 n 新節點
2. 承基本練習題第 7 題, 若要刪除由指標 p 所指到的節點, 第一步須執行何敘述? 請畫圖說明此敘述 答 : q->next = p->next; Head q p 1 6 7 10 3. 在動態配置節點的雙向環狀鏈結串列中, 若每個節點都有三個欄位 :left, data, right 若要插入由指標 n 所指到的新節點至指標 p 所指到的節點之右, 須執 行哪些敘述? 請畫圖說明 答 : 1. n->left = p; 2. n->right = p->right; 3. p->right->left = n; 4. p->right = n; p 4 3 1 2 n 4. 在動態配置節點的雙向環狀鏈結串列中, 若每個節點都有三個欄位 :left, data, right 假設要刪除由指標 p 所指到的節點, 須執行哪些敘述? 請畫圖說明 答 :1. p->left->right = p->right ; 2. p->right->left = p->left ; 1 p 2 5. 假設一個鏈結串列上的 n 個節點已經按照節點資料排序好, 請問要搜尋一個
節點的時間複雜度為何? 答 : O(n) 6. 假設一個鏈結串列上的 n 個節點並未按照節點資料排序好, 請問要搜尋一個 節點的時間複雜度為何? 答 : O(n) 程式題 1. 請完成 3.3.3 節的 GetFreeNode 副程式 ( 取得空節點 ) 答 : unsigned GetFreeNode(NODE table[]) unsigned i; for(i=1;i <= MAX_NODE ;i ++) if(table[i].next == -1) return i; return 0; 2. 寫一函式, 能在一個雙向環狀鏈結串列中, 將每個節點的 data( 資料 ) 欄位依序印出 ( 動態配置節點的鏈結串列 ) 答 : void PrintList(Dnode *head) Dnode *p=head; for(p=p->right; p!= head; p=p->right) printf("%d ",p->data); //cout << p->data; 3. 寫一函式, 能根據參數 value 的值, 在 head 串列中找到某一個節點 ( 搜尋 ) 假設此串列是雙向環狀鏈結串列 DListNode *search( DListNode *head, int value) /* 在 head 串列中, 找到欄位為 value 的節點, 找到這則傳回此節點的位址, 找不到傳回 NULL */
答 : typedef struct dlist_node struct dlist_node *left; int data; struct dlist_node *right; Dnode; Dnode *Search(Dnode *head, int value) Dnode *p=head; for(p=p->right; (p!= head) && (p->data!= value) ;p=p->right); if (p==head) return NULL; return p; 4. 根據 3.5 節串列的建立 增加和刪除 : A. 完成 3.5.6 節的 CreatList 函式 B. 寫一個完整程式, 能建立串列, 並且根據使用者由鍵盤輸入的指令, 而動態地執行插入和刪除 答 : #include <stdio.h> #include <stdlib.h> typedef struct listnode int data; /* 資料欄位 */ struct listnode *next; /* 鏈結欄位 */ Node; int InsertAfter(Node *p,int value) Node *newnode; newnode=(node*)malloc(sizeof(node)); if (newnode==null) return (0); newnode->data=value; newnode->next=p->next; p->next=newnode; return(1);
int DeleteNode(Node *head,node *node) Node *GetPreNode(),*prenode; if (head==node) return 0; prenode=getprenode(head,node); if (prenode==null) return 0; prenode->next=node->next; free(node); return(1); Node *GetPreNode(Node *head,node *node) Node *p,*q; p=head; q=head->next; while((q!=null) && (q!=node)) p=q; q=q->next; if(q!= NULL) return(p); else return(null); int InsertTail(Node *head,int value) Node *new_node,*p=head; if ((new_node=(node*)malloc(sizeof(node))) == NULL) return (0); new_node->data=value; new_node->next=null; while(p->next!= NULL) p=p->next; p->next=new_node; return (1);
void PrintList(Node *p) for(p=p->next;p!= NULL;p=p->next) printf("%d ",p->data); void FreeAllNode(Node *head) Node *p=head->next, *q; while( p!= NULL) q=p->next; free(p); p=q; void CreateList(Node *Head) FILE *fin; int NodeData; if((fin=fopen("list.in","r")) == NULL) printf("file can not be opened, program terminate."); exit(1); Head->next=NULL; fscanf(fin,"%d",&nodedata); while(!feof(fin)) InsertTail(Head,NodeData); fscanf(fin,"%d",&nodedata ); fclose(fin); void main(void) int choose,i,nodedata,num; Node Head,*p; CreateList( &Head); while(1) printf("\n 串列內容 ( Content of list )=>");
PrintList(&Head); printf("\n(1) 附加節點 (Append new node)\n(2) 插入節點 (Insert new node)\n(3) 刪除節點 (Delete node)\n(0) 結束 (exit)=>"); scanf("%d",&choose); switch(choose) case 0: FreeAllNode(&Head); /* 釋放所有節點 */ exit(0); /* 結束程式 */ case 1: printf(" 請輸入欲附加之資料 (Input new data )=>"); scanf("%d",&nodedata); InsertTail(&Head,NodeData); break; case 2: printf(" 請輸入欲插入之資料 (Input new data)=>"); scanf("%d",&nodedata); printf(" 請輸入欲插入之位置 (New Position)=>"); scanf("%d",&num); for(i=1,p=&head;i!=num && p!=null;p=p->next,i++); if(p == NULL) printf(" 插入失敗 ( Insert Failed )"); else if(insertafter(p,nodedata) == 0) printf(" 插入失敗 ( Insert Failed )"); break; case 3: printf(" 請輸入欲刪除之資料 ( data to be deleted )=>"); scanf("%d",&num); for(i=0,p=&head;p!=null&&p->data!=num;p=p->next,i++); if(p == NULL) printf(" 此資料不在串列中 ( the data is not in list )"); else if(deletenode(&head,p) == 0) printf(" 刪除失敗 ( Delete Failed)"); break; default: printf(" 選項錯誤 ( Wrong option )!!");
List.in 檔案 1 2 3 4 5 6 7 8 5. 寫一函式能將一單向鏈結串列轉向 首節點 50 20 29 31 31 29 20 50 首節點答 : #include <stdio.h> #include <stdlib.h> typedef struct listnode int data; /* 資料欄位 */ struct listnode *next; /* 鏈結欄位 */ Node; void InvertList(Node *P,Node *Q,Node *R) if (Q==NULL) // 終止條件 R->next = P; else InvertList(Q,Q->next,R); // 遞迴呼叫 Q->next = P; int InsertTail(Node *head,int value) Node *new_node,*p=head; if ((new_node=(node*)malloc(sizeof(node))) == NULL) return (0); new_node->data=value;
new_node->next=null; while(p->next!= NULL) p=p->next; p->next=new_node; return (1); void PrintList(Node *p) for(p=p->next;p!= NULL;p=p->next) printf("%d ",p->data); void FreeAllNode(Node *head) Node *p=head->next, *q; while( p!= NULL) q=p->next; free(p); p=q; void CreateList(Node *Head) FILE *fin; int NodeData; if((fin=fopen("list.in","r")) == NULL) printf("file can not be opened, program terminate."); exit(1); Head->next=NULL; fscanf(fin,"%d",&nodedata); while(!feof(fin)) InsertTail(Head,NodeData); fscanf(fin,"%d",&nodedata ); fclose(fin);
void main(void) Node Head; CreateList( &Head ); printf("\n 串列內容 ( Content of list )=>"); PrintList(&Head); InvertList(NULL, Head.next, &Head ); printf("\n 反轉的串列內容 ( Inverted Content of list )=>"); PrintList(&Head); printf("\n"); 6. 寫一完整程式, 輸入兩個多項式, 輸出多項式的和 例如 : A(x) = 5x 4 + 6.1x 2 + 2.9x +6 B(x) = 9x 5 + 3.2x 2 + 4x +5 輸出 : C(x) = 9x 5 + 5x 4 + 9.3x 2 + 6.9x + 11 答 : #include <stdio.h> #include <stdlib.h> typedef struct plistnode float coef; /* 係數 */ int expo; /* 冪次 */ struct plistnode *next; Pnode; FILE *fin1,*fin2; Pnode *AddTail(Pnode *tail,float co,int ex) Pnode *p; p=(pnode *)malloc(sizeof(pnode)); p->coef=co; p->expo=ex; p->next=null; tail->next=p; tail=p; return(tail);
Pnode *PolyAdd(Pnode *pa,pnode *pb) Pnode *c,*ctail; c=(pnode *)malloc(sizeof(pnode)); ctail=c; pa=pa->next; pb=pb->next; while(pa && pb) if(pa->expo > pb->expo) ctail=addtail(ctail,pa->coef,pa->expo); pa=pa->next; else if(pa->expo < pb->expo) ctail=addtail(ctail,pb->coef,pb->expo); pb=pb->next; else if((pa->coef + pb->coef)!= 0) ctail=addtail(ctail,pa->coef+pb->coef,pa->expo); pa=pa->next; pb=pb->next; while(pa) ctail=addtail(ctail,pa->coef,pa->expo); pa=pa->next; while(pb) ctail=addtail(ctail,pb->coef,pb->expo); pb=pb->next; return (c); void Read_data(FILE *f,pnode *Tail) int expo;
float coef; fscanf(f,"%f",&coef); /* 先讀讀看係數及乘冪, 若未達檔尾, 即 */ fscanf(f,"%d",&expo); /* 都讀入成功後才建立此節點, 否則會造 */ while(!feof(f)) /* 成最後一筆資料會建立兩次 */ Tail=AddTail(Tail,coef,expo); fscanf(f,"%f",&coef); fscanf(f,"%d",&expo); void PrintPoly(Pnode *p) for(p=p->next ;p->next!= NULL;p=p->next) if (p->coef > 0) printf("%2.1fx^%d + ",p->coef,p->expo); else if (p->coef < 0 ) printf("%2.1fx^%d - ",-(p->coef),p->expo); if (p->expo!=0 ) printf("%2.1fx^%d",p->coef,p->expo); else printf("%2.1f",p->coef); void FreeAllNode(Pnode *head) Pnode *next_node; while(head->next!= NULL) next_node=head->next; free(head); head=next_node; free(head); void main(void) Pnode *Pa,*Pb,*Pc; if((fin1=fopen("polya.in","r"))==null (fin2=fopen("polyb.in","r"))==null) printf(" 開檔失敗, 結束程式 ");
exit(1); Pa=(Pnode *)malloc(sizeof(pnode)); Pb=(Pnode *)malloc(sizeof(pnode)); Read_data(fin1,Pa); Read_data(fin2,Pb); Pc=PolyAdd(Pa,Pb); printf("\na(x)= "); PrintPoly(Pa); printf("\nb(x)= "); PrintPoly(Pb); printf("\nc(x)=a(x)+b(x)="); PrintPoly(Pc); printf("\n"); FreeAllNode(Pa); FreeAllNode(Pb); FreeAllNode(Pc); PolyA.in 檔案 5 4 6.1 2 2.9 1 6 0 PolyB.in 檔案 9 5 3.2 2 4 1 5 0 7. 稀疏矩陣的插入 (insert) 動作, 必須將新節點插入其所在的位置 例如要將 119 加入圖 3.24 的 M[1][2], 需要改變第 1 列的串列 (r1) 和第 2 行的串 列 (c2) A. 寫一函式初設稀疏矩陣 ( 首節點均接地 ) B. 寫一函式, 根據輸入的列號 (r) 行號 (c) 及資料 (x), 製造新節點, 並
將此新節點加入適當的位置 答 : #include <stdio.h> #include <stdlib.h> #define MAXROW 5 #define MAXCOL 6 typedef struct Mlistnode float data; /* 元素值 */ int row,col; /* 列號及行號 */ struct Mlistnode *right,*down;/* 列指標及行指標 */ Mnode; Mnode RowHead[MAXROW]; Mnode ColHead[MAXCOL]; void InsertRow(Mnode *p) Mnode *Follower = &RowHead[p->row]; Mnode *Prior=RowHead[p->row].right; int FlagExists; FlagExists=0; while (Prior!= &RowHead[p->row] ) if (Prior->col == p->col ) // already exists Prior->data = p->data; FlagExists=1; break; else if (Prior->col < p->col ) Follower = Prior; Prior = Prior->right; else break; if (FlagExists == 0) //Insert *p after p->right = Follower->right; Follower->right = p; void InsertCol(Mnode *p)
Mnode *Follower = &ColHead[p->col]; Mnode *Prior=ColHead[p->col].down; int FlagExists; FlagExists=0; while (Prior!= &ColHead[p->col] ) if (Prior->row == p->row ) // already exists Prior->data = p->data; FlagExists=1; break; else if (Prior->row < p->row ) Follower = Prior; Prior = Prior->down; else break; if (FlagExists == 0) //Insert *p after p->down = Follower->down; Follower->down = p; void IniRowColHead() int i; for (i=0;i<maxrow;i++) RowHead[i].row = i; RowHead[i].col = -1; RowHead[i].right=RowHead[i].down=&RowHead[i]; for (i=0;i<maxcol;i++) ColHead[i].col = i; ColHead[i].row = -1; ColHead[i].right=ColHead[i].down=&ColHead[i]; void InsertNode(int RowNo,int ColNo,float data) Mnode *p; p=(mnode *)malloc(sizeof(mnode));
p->data = data ; p->row = RowNo; p->col = ColNo; InsertRow(p); InsertCol(p); void PrintMatrix() Mnode *p; int i; for (i=0;i<maxrow;i++) p=rowhead[i].right; while ( p!= &RowHead[i]) printf("m[%d][%d]=%3.3f ",p->row,p->col,p->data); p=p->right; printf("\n"); void main(void) int choose; int RowNo,ColNo; float Data; IniRowColHead(); while (1) printf("\n(1) 插入節點 (Insert new node)\n(0) 結束 (exit)=>"); scanf("%d",&choose); switch(choose) case 0: exit(0); /* 結束程式 */ case 1: printf("please Input Row Column Data :"); scanf("%d %d %f",&rowno,&colno,&data); if ( (RowNo < MAXROW) && (ColNo < MAXCOL)) InsertNode(RowNo,ColNo,Data); PrintMatrix();