欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

线性表的C语言实现

程序员文章站 2022-06-22 12:01:50
函数声明头文件:function.h #define true 1 #define false 0 /* 定义链表的数据类型为int型 */ typedef int datatype;...

函数声明头文件: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);
    }

}