AUSTOj4

                               LinkList可以定義指向List的指針

1.當函數參數為LinkList L時，意味著只改變或操作List的內容，而不需要改變L這個指針

如

Status GetElem(LinkList L,int i,ElemType)

2.當參數為LinkList &L時，意味著需要改變或操作L這個指針本身

如

Status InitList(LinkList &L)
{
    L=(LinkList)malloc(sizeof(struct LNode));
    ......
}

這裡想初始化單鏈表，需要給L分配記憶體空間，即需要改變L

3.當參數為LinkList *L時，意味著需要改變或操作L這個指針指向的LinkList類型的指針

(此處的L可以理解為指向前兩點中的L的指針)

此時給頭結點分配儲存空間時要這樣寫

(*L)=(LinkList)malloc(sizeof(struct LNode));

L前面要加*,表示L所指向的那個指針

#include <stdio.h>

#include <stdlib.h>
#include <string.h>
typedef int ElemType;   
typedef int Status;     
#define ERROR 0
#define OK 1
typedef struct LNode{     //定義一個鏈表
    ElemType data;    　   //鏈表的數據
    struct LNode *next;     //定義數據的後續空間
}LNode, *linkList;      
 
Status GetElem_L(linkList &L, int i, ElemType &e) {   //獲取位置i處的元素，並用e接住這個值
   linkList p;
   int j=1;
   p=L->next;
   while(p&&j<i){
    p=p->next;++j;
   }
   if(!p||j<i)
   return ERROR;
   e=p->data;
   return OK;
} 
 
Status ListInsert_L(linkList &L, int i, ElemType e) {   //在位置i處插入一個元素，並用e接住
  LNode *p,*s;
  int j=0;
  p=L;
  while(p&&j<i-1)  //可以理解為：while(p!=null && p != 0 && p!=false &&j<i-1) 即p的範圍是合理的
  {
   p=p->next; //p指向他的下一個
   ++j;
  }
  if(!p||j>i-1)
  return ERROR;
  s=(linkList)malloc(sizeof(LNode));//malloc函數用於在記憶體開闢了一段地址，而這段地址的首地址存在返回的那個指針變數里
  s->data=e;
  s->next=p->next;
  p->next=s;
  return OK;
} 
 
Status ListDelete_L(linkList &L, int i, ElemType &e) {  //刪除i處的元素，並用e接住
    LNode *p,*q;
    p=L;
int j=0;
   while(p->next&&j<i-1)
   {
    p=p->next;
    ++j;
   }
   if(!(p->next)||j>i-1)
   return ERROR;
   q=p->next;
   p->next=q->next;
   e=q->data;
   free(q);
   return OK;
}
 
void CreateList_L(linkList &L, int n) {  //創造一個新的鏈表
   int i;
   linkList p;
   L=(linkList)malloc(sizeof(LNode));
   L->next=NULL;
   for(i=n;i>0;--i)
   {
    p=(linkList)malloc(sizeof(LNode));
    scanf("%d",&(p->data));
   p->next=L->next ;
   L->next =p; 
   }
} 
 
int ShowList_L(linkList L){ 
    // 顯示鏈表中的元素，返回值為鏈表元素的數目
    ///===============補充代碼======================== 
    linkList p;
    p=L->next;   //定義頭指針
    int i=0;
    while(p!=NULL){ //確認非空
     printf("%d ",p->data);
     p=p->next;
     i++;
}
return i;
}

int main(){
 
    int n;                  // 初始時元素的數目
    int m;                  // 指令的數目
    char strInst[30];       // 存儲指令:instruction
    int a;                  // 存儲位置數據
    linkList L;             // 鏈表
    int e;                  // 定義節點，用來存儲獲取的節點或者刪除的節點
    scanf("%d", &n);        // 讀入元素的數目
    CreateList_L(L, n);     // 創建鏈表
    scanf("%d", &m);        // 讀取指令的數目
    while(m--){             // 做 m 次迴圈
        scanf("%s", strInst);                   // 讀取指令
        if(strcmp(strInst, "get") == 0){        // 如果是需要獲取某個元素
            scanf("%d", &a);                    // 讀取元素的位置
            if(GetElem_L(L, a, e) == OK){       // 如果獲取元素成功
                printf("%d\n", e);              // 輸出元素的值
            }else{                              // 如果獲取元素失敗
                puts("get fail");               // 輸出獲取元素的出錯信息
            }
        }else if(strcmp(strInst, "insert") == 0){// 如果是插入某個元素
            scanf("%d%d", &a, &e);              // 獲取待插入的位置以及待插入的值
            if(ListInsert_L(L, a, e) == OK){    // 如果插入元素成功
                puts("insert OK");              // 輸出插入成功的信息
            }else{
                puts("insert fail");            // 否則輸出插入失敗的信息
            }
        }else if(strcmp(strInst, "delete") == 0){// 如果是刪除某個元素
            scanf("%d",&a);                     // 獲得待刪除元素的位置
            if(ListDelete_L(L, a, e) == OK){    // 如果刪除成功
                puts("delete OK");              // 輸出刪除成功的信息
            }else{
                puts("delete fail");            // 否則輸出刪除失敗的信息
            }
        }else if(strcmp(strInst, "show") == 0){ // 如果是顯示鏈表
            if(ShowList_L(L) == 0){             // 如果鏈表為空
                puts("Link list is empty");     //顯示量表為空的信息
            }
        }
    }
 
    return 0;
}