线性表的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); } }
上一篇: WinCE获取SD卡序列号
下一篇: c语言文件操作函数