鏈表-線性表的鏈式表示

頭插法

#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;
}