二、實驗預習

1、線性表：線性表中數據元素之間的關系是一對一的關系,即除了第一個和最后一個數據元素之外,其它數據元素都是首尾相接的。

2、順序表：順序表是線性表的一種 順序表示的線性表稱為順序表。

3、鏈表：鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列鏈表中每一個元素即結點組成，結點可以在運行時動態生成。

三、實驗內容和要求

1、閱讀下面程序，在橫線處填寫函數的基本功能。并運行程序，寫出結果。

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1

#define INIT_SIZE 5     /*初始分配的順序表長度*/
#define INCREM 5        /*溢出時，順序表長度的增量*/
typedef  int ElemType;  /*定義表元素的類型*/
typedef struct Sqlist{
    ElemType *slist;      /*存儲空間的基地址*/
    int length;           /*順序表的當前長度*/
    int listsize;         /*當前分配的存儲空間*/
}Sqlist;

int InitList_sq(Sqlist *L); /*________初始化順序表，為其分配存儲空間_________________*/
int CreateList_sq(Sqlist *L,int n); /*____________創建一個順序表_____________*/
int ListInsert_sq(Sqlist *L,int i,ElemType e);/*____________將新元素e插入到順序表第i個位置_____________*/
int PrintList_sq(Sqlist *L);  /*輸出順序表的元素*/
int ListDelete_sq(Sqlist *L,int i); /*刪除第i個元素*/
int ListLocate(Sqlist *L,ElemType e); /*查找值為e的元素*/

int InitList_sq(Sqlist *L){
    L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
    if(!L->slist) return ERROR;      
    L->length=0;                     
    L->listsize=INIT_SIZE;           
    return OK;                   
}/*InitList*/

int CreateList_sq(Sqlist *L,int n){
    ElemType e;
    int i;
    for(i=0;i<n;i++){
        printf("input data %d",i+1);
        scanf("%d",&e);
        if(!ListInsert_sq(L,i+1,e))
            return ERROR;
    }
    return OK;
}/*CreateList*/

/*輸出順序表中的元素*/
int PrintList_sq(Sqlist *L){
    int i;
    for(i=1;i<=L->length;i++)
        printf("%5d",L->slist[i-1]);
    return OK;
}/*PrintList*/

int ListInsert_sq(Sqlist *L,int i,ElemType e){
    int k;
if(i<1||i>L->length+1) 
return ERROR;    
if(L->length>=L->listsize){  
L->slist=(ElemType*)realloc(L->slist,
(INIT_SIZE+INCREM)*sizeof(ElemType));
        if(!L->slist) 
return ERROR; 
L->listsize+=INCREM;                
}
    for(k=L->length-1;k>=i-1;k--){         
        L->slist[k+1]= L->slist[k];
    }
    L->slist[i-1]=e;                     
    L->length++;                         
    return OK;
}/*ListInsert*/

/*在順序表中刪除第i個元素*/
int ListDelete_sq(Sqlist *L,int i){


}
/*在順序表中查找指定值元素，返回其序號*/
int ListLocate(Sqlist *L,ElemType e){    


}

int main(){
    Sqlist sl;
    int n,m,k;
    printf("please input n:");  /*輸入順序表的元素個數*/
    scanf("%d",&n);
    if(n>0){
        printf("\n1-Create Sqlist:\n");
        InitList_sq(&sl);
        CreateList_sq(&sl,n);
        printf("\n2-Print Sqlist:\n");
        PrintList_sq(&sl);
        printf("\nplease input insert location and data:(location,data)\n");
        scanf("%d,%d",&m,&k);
        ListInsert_sq(&sl,m,k);
        printf("\n3-Print Sqlist:\n");
        PrintList_sq(&sl);
        printf("\n");
        }
    else
        printf("ERROR");
    return 0;
}

運行結果:

算法分析：
首先選擇順序表的動態存儲方式進行順序表結構的定義，然后在程序的開頭進行順序表各種操作函數的聲明以及預定義命令，接著編寫各種操作函數的函數體，而在主函數中要首先調用Initlise_sq()函數初始化，然后調用InitList_sq()創建順序表，調用PrintList_sq()函數輸出該順序表中元素的值；然后調用ListInsert_sq()函數，進行插入操作，并輸出插入新元素的狀態。

2、為第1題補充刪除和查找功能函數，并在主函數中補充代碼驗證算法的正確性。

刪除算法代碼：

int ListDelete_sq(Sqlist *L,int i){
if(L->length==0) return 0;
if(i<1||i>L->length) return 0;
for(int j=i;j<L->length;j++)
L->slist[j-1]=L->slist[j];
L->length--;
return 1;
}

運行結果:

算法分析：
在主函數里面調用刪除功能函數并傳參數進去時，程序將自動跳到函數體里面，利用所傳參數一步步執行，在該函數里面，當把順序表和序號i傳值進去時，程序可以先判斷所傳值是否滿足條件，若滿足，則開始從順序表第一個元素開始依次遍歷，直到找到第i個位置的元素，并將其刪除，后面的元素依次前移，填補。而表的長度則減一，刪除成功。若不滿足，則返回0，表示刪除失敗。
查找刪除代碼：

int ListLocate(Sqlist *L,Elemtype e){
for(int i=1;i<=L->length;i++)
{if(L->slist[i-1]==e)
return i;
return0;
}
}

運行結果：

算法分析：
當在主函數里面調用查找功能函數并傳參數進去時，程序將自動跳到函數體里面，利用所傳參數一步步執行，在該函數里面，當把順序表和要查找的值e傳值進去時，程序開始從順序表第一個元素開始依次遍歷，直到找到值為e的元素，并返回其位置序號，查找成功。若遍歷了順序表所有元素依然沒有符合條件的e的值，則返回0,表示查找失敗。

3、閱讀下面程序，在橫線處填寫函數的基本功能。并運行程序，寫出結果。

#include<malloc.h>
#define ERROR 0
#define OK 1
typedef  int ElemType; /*定義表元素的類型*/
typedef struct LNode{  /*線性表的單鏈表存儲*/
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

LinkList CreateList(int n); /*_____________建立帶表頭節點的單鏈表____________*/
void PrintList(LinkList L); /*輸出帶頭結點單鏈表的所有元素*/
int GetElem(LinkList L,int i,ElemType *e); /*__________在單鏈表中查找第i個節點的值_______________*/

LinkList CreateList(int n){
    LNode *p,*q,*head;
    int i;
    head=(LinkList)malloc(sizeof(LNode));       
    head->next=NULL;
    p=head;
    for(i=0;i<n;i++){
       q=(LinkList)malloc(sizeof(LNode));       
       printf("input data %i:",i+1);
       scanf("%d",&q->data);            /*輸入元素值*/
       q->next=NULL;                    /*結點指針域置空*/
       p->next=q;                       /*新結點連在表末尾*/
       p=q;
    }
    return head;
}/*CreateList*/

void PrintList(LinkList L){
    LNode *p;
    p=L->next;  /*p指向單鏈表的第1個元素*/
    while(p!=NULL){
        printf("%5d",p->data);
        p=p->next;
    }
}/*PrintList*/

int GetElem(LinkList L,int i,ElemType *e){
    LNode *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;
}/*GetElem*/

int main(){
    int n,i;ElemType e;
    LinkList L=NULL;            /*定義指向單鏈表的指針*/
    printf("please input n:");  /*輸入單鏈表的元素個數*/
    scanf("%d",&n);
    if(n>0){
        printf("\n1-Create LinkList:\n");
        L=CreateList(n);        
        printf("\n2-Print LinkList:\n");
        PrintList(L);           
        printf("\n3-GetElem from LinkList:\n");
        printf("input i=");
        scanf("%d",&i);
        if(GetElem(L,i,&e))     
            printf("No%i is %d",i,e);
        else
            printf("not exists");
    }else
        printf("ERROR");
    return 0;
}

運行結果：

算法分析：
首先進行單鏈表結構的定義，然后在程序開頭進行順序表各種操作函數的聲明以及預定義命令，接著編寫各種操作函數的函數體，而在主函數中要首先調用LinkList CreateList(int n)創建帶頭結點的單鏈表，輸入結點數，然后依次輸入各個結點的值。接著調用打印單鏈表功能函數輸出單鏈表中的值。再調用查找功能函數，輸入查找元素的位置，輸出對應元素的值。然后調用插入功能函數，輸入要插入的位置和元素，打印輸出插入后的新鏈表。同理調用刪除功能函數，輸入要刪除的元素值，最后打印輸出刪除后的單鏈表。

4、為第3題補充插入功能函數和刪除功能函數。并在主函數中補充代碼驗證算法的正確性。

插入算法代碼：

int InsertList(LinkList L,int i,ElemType e){
	int j=1; 
    LNode*p,*q; 
    p=L->next; 
    while(p&&j<i-1){
    	p=p->next;j++; 
	} 
    if(!p) return ERROR;
    q=(LNode*)malloc(sizeof(LNode)); 
    q->data=e;q->next=p->next;p->next=q; 
return OK; 
}

運行結果：

算法分析：
在主函數里面調用查找功能函數，程序自動跳到函數體里面，利用參數一步步執行，在該函數里面，當把單鏈表要插入的位置序號和元素內容傳值進去時，程序開始從單鏈表第一個元素開始依次遍歷，直到找到插入置的前一個節點，用指針p指向它。然后創建一個以e為值的新節點指針q，修改節點q的next域指向節點p的下一個節點，點p的next域修改為指向新節點s。返回ok，表示插入成功。最后輸出插入后的新鏈表。
刪除算法代碼：

int DeleteList(LinkList L ,ElemType e){
	LNode*p,*q;
    p=L->next; 
    while(p&&p->data!=e) {
    	q=p;p=p->next;
    }
    if(!p) return ERROR; 
    else {
        q->next=p->next;
        free(p); 
    return OK;
    } 
}

運行結果：

算法分析：
在主函數里面調用刪除功能函數并傳參數進去時，程序將自動跳到函數體里面，利用所傳參數一步步執行，在該函數里面，當把單鏈表要刪除的元素內容傳值進去時，程序開始從單鏈表的第一個元素開始依次遍歷，直到找到刪除位置的前一個節點，用指針p指向它。指針q指向要刪除的節點。然后修改指針p的next域為指向待刪除節點*q的后繼節點。返回ok,表示刪除成功。最后打印輸出刪除后的新鏈表。

四、實驗小結

通過本次實驗，我掌握了線性表中元素的前驅、后續的概念，以及實際操作體驗了順序表與鏈表的建立、插入元素、刪除表中某元素的算法?？傮w上還算容易理解，但是c的短板還是暴露出來了，代碼都太老了需要修改才能用。雖然因為基礎太差基本是靠自學，但是仍然體驗到了數據結構的樂趣，期待此科目后續的學習生活。