链表-线性表的链式表示
头插法
#include <stdio.h>
#include <stdlib.h>typedef int ElemType;
typedef struct LNode {// 存储数据ElemType data;// 后继节点地址LNode *next;
} LNode, *LinkList;/** 头插法创建链表*/
void list_head_insert(LinkList &L) {// 创建头节点// L指向头节点L = (LinkList) malloc(sizeof(LNode));L->next = NULL;// 创建新节点指针LinkList new_node;ElemType data;// 读取数据scanf("%d", &data);while (999 != data) {// 创建新节点// 指针指向新节点new_node = (LinkList) malloc(sizeof(LNode));// 存入数据值new_node->data = data;// 新节点的next指向链表的第一个元素(不包含头节点)new_node->next = L->next;// 新节点作为第一个节点L->next = new_node;// 再次读取数据scanf("%d", &data);}
}/** 打印链表*/
void print_list(LinkList L) {// L指向第一个节点L = L->next;while (NULL != L) {printf("%3d", L->data);// 指向下一个节点L = L->next;}
}int main() {// 一、创建链表头指针LinkList L;// 二、头插法创建链表list_head_insert(L);// 三、打印链表print_list(L);return 0;
}
尾插法
#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct LNode {// 存储数据ElemType data;// 后继节点地址LNode *next;
} LNode, *LinkList;/** 尾插法创建链表*/
void list_tail_insert(LinkList &L) {// 创建头节点// L指向头节点L = (LinkList) malloc(sizeof(LNode));L->next = NULL;// 创建新节点指针变量s 尾节点指针变量rLinkList new_node, r;r = L;ElemType data;scanf("%d", &data);while (999 != data) {// 创建新节点new_node = (LinkList) malloc(sizeof(LNode));// 存入数据值new_node->data = data;// 尾节点的next指向新节点r->next = new_node;// 新节点变成尾节点r = new_node;// 输入数据scanf("%d", &data);}// 尾节点的next指向NULLr->next = NULL;
}/** 打印链表*/
void print_list(LinkList L) {// L指向第一个节点L = L->next;while (NULL != L) {printf("%3d", L->data);// 指向下一个节点L = L->next;}printf("\n");
}/** 通过位置查找元素*/
LinkList search_elem_by_location(LinkList L, int pos) {// 判断位置是否合法if (0 > pos) {return NULL;}int i = 0;while (L && i < pos) {L = L->next;i++;}return L;
}/** 通过值查找元素*/
LinkList search_elem_by_value(LinkList L, ElemType data) {while (L) {if (data == L->data) {return L;}// 未匹配时 L指向下一个节点L = L->next;}return L;
}/** 链表插入元素* 此处不改变头指针L因此不需要写引用* @param*/
bool list_insert_elememt(LinkList L, int pos, ElemType data) {// 获取第pos-1个元素LinkList p = search_elem_by_location(L, pos - 1);// 判断位置是否合法if (NULL == p) {return false;}// 创建新节点LinkList q = (LinkList) malloc(sizeof(LNode));q->data = data;q->next = p->next;p->next = q;return true;
}/** 按位置删除元素* 此处不改变头指针L因此不需要写引用*/
bool list_delete(LinkList L, int pos) {// 查询第pos-1个位置LinkList p = search_elem_by_location(L, pos - 1);if (NULL == p) {return false;}// 被删除的元素LinkList q;q = p->next;// 如果要删除的位置 超过了链表长度if (NULL == q) {return false;}// 断链p->next = q ->next;// 释放节点空间free(q);return true;
}int main() {// 一、创建链表头指针LinkList L;// 二、尾插法创建链表list_tail_insert(L);// 三、打印链表print_list(L);// 四、查询操作LinkList search_elem = search_elem_by_location(L, 2);// 按位置查找元素if (search_elem) {printf("search elem by location success\n");printf("element data = %d\n", search_elem->data);} else {printf("search elem by location faild\n");}// 按值查询元素search_elem = search_elem_by_value(L, 99);if (search_elem) {printf("search elem by value success\n");printf("element data = %d\n", search_elem->data);} else {printf("search elem by value faild\n");}// 五、插入操作// 新节点插入在第i个位置bool ret = list_insert_elememt(L, 2, 19);if (ret) {printf("insert success\n");} else {printf("insert fail\n");}print_list(L);// 六、删除操作ret = list_delete(L, 9);if (ret) {printf("delete success\n");} else {printf("delete failed\n");}print_list(L);return 0;
}
