線性表的C語言實現

函數聲明頭文件:function.h

#define true 1
#define false 0

/* 定義鏈表的數據類型為int型 */
typedef int datatype;
/*線性表的單鏈表存儲結構*/
typedef struct l_node
{
    /*聲明數據域*/
    datatype data;
    /*聲明指針域*/
    struct l_node *next;
}l_node, *link_list;

/* 判斷第i個元素是否存在
 * 若存在,把該元素的值賦給*e,並返回true
 * 若不存在,返回false
 * 參數HEAD為單鏈表的頭指針
*/
int get_elem(link_list HEAD, int i, datatype *e);


/* 在帶頭結點的單鏈線性表HEAD中,在第i個位置之前插入元素e
 * 參數HEAD是單鏈表的頭指針
*/
int list_insert_posision(link_list HEAD, int i,datatype e);


/* 在帶頭結點的單鏈線性表HEAD中,刪除第i個元素,並由e返回其值
 * 參數HEAD是單鏈表的頭指針頭指針
*/
int list_delete_position(link_list HEAD, int i, datatype *e);


/* 創建新的鏈表,並插入輸入的n個元素(插入元素的位置為1)
 * 參數HEAD為鏈表的頭指針
 * 參數n為插入元素的個數
*/
void create_list(link_list HEAD, int n);


/* 將兩個鏈表並為一個有序鏈表
 * 參數HEAD_A為鏈表A的頭指針(元素按非遞減排列)
 * 參數HEAD_B為鏈表B的頭指針(元素按非遞減排列)
 * 參數HEAD_C為合成鏈的頭指針
*/
void merge_list(link_list HEAD_A, link_list HEAD_B, link_list HEAD_C);

/* 若鏈表為空,返回true,否則返回false
 * 參數HEAD為鏈表的頭指針
*/

int list_empty(link_list HEAD);

/* 獲取鏈表的長度 */
int list_length(link_list HEAD);


/*在表中查找第k個元素,若找到,返回該元素的指針
 * 否則返回空指針NULL
 * 參數HEAD為單鏈表的頭指針
*/
link_list list_locate(link_list HEAD, int k);


/* 遍歷單鏈表 */
void list_print(link_list HEAD);


/* 在表中查找第一個值為k的結點
 * 若找到返回位置索引(從1開始)
 * 否則,返回0
*/

int list_locate_pos(link_list HEAD, datatype k);


/* 銷毀鏈表 */
void list_destory(link_list HEAD);

函數實現文件:implementation.c

#include
#include
#include"function.h"

int get_elem(link_list HEAD, int i, datatype *e)
{
    /* 初始化第一個結點 */
    link_list p = NULL;
    p = HEAD -> next;
    /* 計數器 */
    int j = 1;
    /* 指針向後查找,直到p指向第i個元素或者p為空 */
    while(p && j < i )
    {
        p = p -> next;
        j += 1;
    }
    /* 若L為空 或 j > i,說明不存在*/ 
    if (!p || j > i)
    {
        return false;
    }
    /* 否則說明找到第i個元素 */
    *e = p -> data; 
    return true;
}



int list_insert_posision(link_list HEAD,int i, datatype e)
{
    /* 單鏈表的第一個結點 */
    link_list p = NULL;
    p = HEAD;
    /* 初始化計數器 */
    int j = 0;
    /* 指針向後查找,直到指針指向第(i-1)個元素或者p為空 */
    while( p && (j < i - 1) )
    {
        p = p -> next;
        j += 1;
    }
    /* 若i小於1或者i大於鏈表的changdu */
    if ( !p || (j > i - 1) )
    {
        return false;
    }
    /* 插入元素 */
    /* 生成新結點 */
    link_list new_node = (link_list) malloc(sizeof(l_node));
    new_node -> data = e;
    /* 改變指針域 */
    new_node -> next = p -> next;
    p -> next = new_node;
    return true;
}


int list_delete_position(link_list HEAD, int i, datatype *e)
{
    /* 初始化第一個結點p */
    link_list p = NULL;
    p = HEAD;
    /* 計數器 */
    int j = 0;
    /* 指針向後查找,直到指針指向第(i-1)個元素或者p為空 */
    while( p -> next && j < i - 1)
    {
        p = p -> next;
        j += 1;
    }
    /* 若i小於1或者i大於鏈表的長度 */
    if ( !(p -> next) || j > i - 1 )
    {
        return false;
    }
    /* 返回其值 */
    *e = p -> next -> data;
    /* 刪除結點 */
    link_list q = p -> next;
    p -> next = q -> next;
    free(q);
    return true;
}

void create_list(link_list HEAD, int n)
{
    int i = 0;
    /* 初始化頭指針 */
    HEAD -> next = NULL;
    for (i = 0; i < n; i++)
    {
        /* 新建結點 */
        link_list p = (link_list) malloc(sizeof(l_node));
        /* 輸入結點值 */
        scanf("%d",&(p -> data));
        /* 改變指針域 */
        p -> next = HEAD -> next;
        HEAD -> next = p;
    }

}


void merge_list(link_list HEAD_A, link_list HEAD_B, link_list HEAD_C)
{
    /* 用L_A的頭結點作為合成鏈表L_C的頭結點 */
    HEAD_C = HEAD_A;
    link_list pa, pb, pc;
    pa = HEAD_A -> next;
    pb = HEAD_B -> next;
    /* pc為合成鏈的尾指針 */
    pc = HEAD_C;
    while(pa && pb)
    {
        if(pa -> data <= pb -> data)
        {
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;
        }
        else
        {
            pc -> next = pb;
            pc = pb;
            pb = pb -> next;
        }
    }
    /* 插入剩余段 */
    pc -> next = pa?pa:pb;
    /* 釋放鏈表B的根節點 */
    free(HEAD_B);
}    


int list_empty(link_list HEAD)
{
    if (HEAD -> next == NULL)
        return true;
    else
        return false;
}


int list_length(link_list HEAD)
{
    /* 計數器 */
    int count = 0;
    link_list p = HEAD -> next;
    while(p)
    {
        count += 1;
        p = p -> next;
    }
    return count;
}



link_list list_locate(link_list HEAD, int k)
{
    /* 單鏈表的第一個結點 */
    link_list p = HEAD -> next;
    /* 計數器 */
    int i = 1;
    while(p && i < k)
    {
        p = p -> next;
        i += 1;
    }
    /* 存在第k個元素,且指針p指向該元素 */
    if (p && i == k)
    {
        return p;
    } return NULL;
}


void list_print(link_list HEAD)
{
    printf("打印單鏈表\n");
    link_list p = HEAD -> next;
    while(p)
    {
        printf("%d\n", p -> data);
        p = p -> next;
    }
}


int list_locate_pos(link_list HEAD, datatype k)
{
    /* 指針p指向鏈表的第一個結點 */
    link_list p = HEAD -> next;
    /* 計數器 */
    int i = 1;
    while(p)
    {
        if(p -> data == k)
            return i;
        p = p -> next;
        i += 1;
    }
    return 0;
}

void list_destory(link_list HEAD)
{
    while(HEAD)
    {
        link_list p = HEAD;
        HEAD = HEAD -> next;
        free(p);
    }

}