※ 優點 -> 使用容易
※ 缺點 -> (1)刪除與插入造成資料移動頻繁
(2)浪費不必要之記憶體
(3)陣列長度為常數，可能不夠用
#include<stdio.h>
struct student
{
int math;
int eng;
int comp;
};
typedef struct student student;
int main(){
student s[5];
int sum[3] = {0};
int i;
int n = 0;
int op,qid;
while(1){
puts("(1) 新增一位同學資料");
puts("(2) 查詢某位同學成績 (輸入座號)");
puts("(3) 修改某位同學成績 (輸入座號)");
puts("(4) 列出所有資料");
puts("(5) 計算各科平均");
puts("(6) 計算某位同學成績平均 (輸入座號)");
puts("(0) 離開");
scanf("%d", &op);
switch(op)
{
case 1:
scanf("%d", &s[n].math);
scanf("%d", &s[n].eng);
scanf("%d", &s[n].comp);
n++;
break;
case 2:
scanf("%d", &qid);
if(qid>0 && qid<=n)
{
printf("%d\n", s[qid-1].math);
printf("%d\n", s[qid-1].eng);
printf("%d\n", s[qid-1].comp);
}
else
{
printf("無此座號\n");
}
break;
case 3:
scanf("%d", &qid);
if(qid>0 && qid<=n)
{
scanf("%d\n", &s[qid-1].math);
scanf("%d\n", &s[qid-1].eng);
scanf("%d\n", &s[qid-1].comp);
}
else
{
printf("無此座號\n");
}
break;
case 4:
for(i=0; i<n; i++){
printf("%d\n", s[i].math);
printf("%d\n", s[i].eng);
printf("%d\n", s[i].comp);
}
break;
case 5:
//算各科總分
for(i=0;i<n;i++){
sum[0] += s[i].math;
sum[1] += s[i].eng;
sum[2] += s[i].comp;
}
for(i=0;i<3;i++){
printf("%.2f\n", (double)sum[i]/n);
}
break;
case 6:
scanf("%d", &qid);
if(qid>0 && qid<=n)
{
printf("%.2f\n", (double)(s[qid-1].math + s[qid-1].eng + s[qid-1].comp)/3);
}
else
{
printf("無此座號\n");
}
break;
case 0:
return 0;
break;
}
}
return 0;
}
鏈結串列
節點:鏈結串列中最基本的單位
節點 = 資料 + 結構指標
◎ 定義鏈結串列節點結構
鏈結串列透過儲存元素在記憶體之位址為指標(Pointer)或鏈結(Link)取得下一個節點。
定義節點結構:
head : 指向串列前端之指標
◎ 連續鏈結串列
node *head, *ptr;
head = (node *)malloc(sizeof(node));
ptr = head;
int value;
scanf("%d", &value);
ptr->data = value;
ptr->next = (node
*)malloc(sizeof(node));
ptr = ptr->next;
★ 新增節點
在新增節點時，最好是使用動態配置一節點之記憶體。
node *getnode () /* 此函數產生一個新節點 */
{
node *p;
p = (node *) malloc(sizeof(node));
/* malloc 會動態地配置大小為sizeof 的記憶體*/
/* sizeof 會傳回一個型態為node之值*/
if ( p == NULL)
{
printf ("記憶體不足");
exit(1);
}
return(p);
}
★ 釋放節點
當然在使用完畢記得歸還一個節點之記憶體。
void freenode (node *p) /* 此函數將節點還給記憶體 */
{
free(p);
}
★ 插入節點
由鏈結串列加入一個節點，一個節點插入有三種情況:
◆ 節點加於第一個節點之前
head = (node *)malloc(sizeof(node));
head -> next = ptr;
ptr = head;
◆ 節點加於最後一個節點之後
ptr->next = (node *)malloc(sizeof(node));
ptr = ptr->next;
◆ 加於節點中間任何一個位置
node *new_node; //(1)
new_node = getnode(); //(2)
new_node->next = ptr->next; //(3)
/* 新節點指向下一節點*/
ptr->next = new_node; //(4)
/* 節點ptr指向新節點*/
node *insert_node (node *head, node *ptr, node data)
{
node *new_node; /* 新節點指標變數 */
new_node = getnode(); /* 建立新節點,取得一個可用節點 */
*new_node = data; /* 建立節點內容 */
new_node->next = NULL; /* 設定指標初值 */
if ( ptr == NULL ) /* 指標ptr是否是NULL */
{
/* 第一種情況: 插入第一個節點 */
new_node->next = head; /* 新節點成為串列開始 */
head = new_node;
}
else
{
if ( ptr->next == NULL ) /* 是否是串列結束 */
/* 第二種情況: 插入最後一個節點 */
ptr->next = new_node; /* 最後指向新節點 */
else
{
/* 第三種情況: 插入成為中間節點 */
new_node->next = ptr->next; /* (3) 新節點指向下一節點 (3)*/
ptr->next = new_node; /* 節點ptr指向新節點 (4)*/
}
}
return (head);
}
★ 尋找節點
走訪串列，將找到節點位置回傳。
node *find_node(node *head, int num)
{
node *ptr;
ptr = head; /* 指向串列起始 */
while ( ptr != NULL ) /* 走訪串列 */
{
if ( ptr->data == num ) /* 找尋data */
return (ptr);
ptr = ptr->next; /* 指向下一節點 */
}
return (ptr);
}
★ 刪除節點
由鏈結串列中刪除一個節點，一個節點刪除有三重情況:
◆ 刪除第一個節點
head = head->next;
freenode(ptr);
return(head); /* reset 起始節點指標 */
◆ 刪除最後一個節點
previous = head;
while ( previous->next != ptr ) /* 找節點ptr的前節點 */
previous = previous->next;
previous->next = NULL; /* 最後一個節點 */
freenode(ptr); /* 此函數將節點歸還給記憶體 */
◆ 刪除中間任何一個節點
previous = head;
while ( previous->next != ptr ) /* 找節點ptr的前節點 */
previous = previous->next;
/* 第三種情況: 刪除中間節點 */
previous->next = ptr->next; //(1)
freenode(ptr); //(2) /* 此函數將節點歸還給記憶體 */
/*
* 使用鏈結串列製作一個 會員資料表功能
* ‧輸入’i’ 新增節點在串列最後,可輸入姓名, 電話, Email
* ‧輸入’d’接著輸入姓名，可將節點中之姓名相同者刪除(假設輸入之姓名不會重覆)
* ‧輸入’f’接著輸入一個姓名，可將節點中之姓名相同者印出資料
* ‧輸入’l’ 印出串列所有節點內容並顯示目前人數
* ‧輸入’q’ 離開程式
*
* 提示: 使用strcmp來實作 (string.h )
* strcmp(data[0], data[0])
* 第一個字串大於第二個字串回傳正值，反之回傳負值。相等則為0
* ※bonus:可設計插入位置於最前/中間/最後
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct _node{
int data;
char name[80];
int phone;
char email[80];
struct _node *next;
};
typedef struct _node node;
node *getnode(){
node *p;
p = (node *) malloc(sizeof(node));
if(p == NULL){
printf ("記憶體不足");
exit(1);
}
return(p);
}
void freenode (node *p){
free(p);
}
node *insert_node (node *head, node *ptr, node data){
node *new_node;
new_node = getnode();
*new_node = data; /* 建立節點內容 */
new_node->next = NULL; /* 設定指標初值 */
if (ptr == NULL) {
new_node->next = head; /* 新節點成為串列開始 */
head = new_node;
}
else{
if (ptr->next == NULL)
ptr->next = new_node; /*插入最後一個節點 */
else{
new_node->next = ptr->next; /*插入成為中間節點 */
ptr->next = new_node;
}
}
return (head);
}
node *find_node(node *head, char name[]){
node *ptr;
ptr = head;
while (ptr != NULL){
if (strcmp(ptr->name ,name)== 0)
return (ptr);
ptr = ptr->next;
}
return (ptr);
}
node *delete_node(node *head, node *ptr){
node *previous;
if (ptr == head)
head = head->next; /*刪除第一個節點 */
else{
previous = head;
while (previous->next != ptr)
previous = previous->next;
if (ptr->next == NULL)
previous->next = NULL; /*刪除最後一個節點 */
else
previous->next = ptr->next; /*刪除中間節點 */
}
freenode(ptr);
return(head);
}
int length (node *head){
int num=0;
node *q = head;
while (q != NULL) {
num ++;
q = q->next;
}
return(num);
}
int main()
{
node *head, *ptr, input;
head = NULL;
int value;
char name[80];
char key;
while(1){
puts("i insert at last");
puts("d delete");
puts("f find");
puts("q exit");
puts("g length");
puts("l list all data");
scanf(" %c", &key);
switch(key)
{
case 'i':
scanf("%s", input.name);
scanf("%s", input.email);
scanf("%d", &input.phone);
if(head==NULL)
head = insert_node (head, NULL, input);
else{
ptr = head;
while(ptr->next!=NULL)
ptr = ptr->next;
head = insert_node (head, ptr, input);
}
break;
case 'd':
scanf("%s", name);
ptr = find_node(head, name);
if(ptr==NULL)
printf("Can not delete\n");
else{
head = delete_node(head, ptr);
printf("Delete ok\n");
}
break;
case 'f':
scanf("%s", name);
ptr = find_node(head, name);
if(ptr==NULL)
printf("Not found\n");
else{
printf("found\n");
printf("%s\n", ptr->name);
printf("%s\n", ptr->email);
printf("%010d\n\n", ptr->phone);
}
break;
case 'g':
printf("%d\n", length(head) );
break;
case 'l':
ptr = head;
while(ptr!=NULL){
printf("%s\n", ptr->name);
printf("%s\n", ptr->email);
printf("%010d\n\n", ptr->phone);
ptr = ptr->next;
}
break;
case 'q':
return 0;
break;
}
system("pause");
system("cls");
}
return 0;
}
