链表

链表是最基本的数据结构，链表是线性表的链式存储结构。每个结点不仅包含所存元素的信息，还包含元素之间的逻辑关系。 链表不支持随机访问，结点的存储空间利用率较顺序表稍低一些。在链表中插入删除元素无需移动元素，插入删除操作速度快，查询较顺序表速度慢

分类

单链表（循环单链表）

typedef struct LNode { int Element; struct Lnode *next; }LinkList;

双链表（循环双链表）

typedef struct DLNode { int Element; struct DLnode *prior; struct DLnode *next; }DLinkList;

常用操作

头插法

LinkList Creat_list(Linklist head) { head = (Linklist)malloc(sizeof(LNode)); // 创建头节点 head->next = NULL; Lnode *node = NULL; // 定义新结点 node = head->next; // 将最后一个结点的指针域永远保持为NULL printf("Input the node number: "); int count = 0 ; scanf("%d", &count); for (int i = 0; i < count; i++) { node = (Linklist)malloc(sizeof(LNode)); node->data = i; // 为新结点的数据域赋值 node->next = head->next; // 将头结点的下一个结点的地址，赋给新创建结点的next head->next = node; // 头结点下一个结点指针指向新插入结点 } return head; }

尾插法

LinkList Creat_list(Linklist head) { head = (Linklist)malloc(sizeof(LNode)); // 为头指针开辟内存空间 head->next = NULL; Linklist *end = NULL; // 新增定义尾结点 Linklist *node = NULL; // 定义结点 end = head; // 未创建其余结点之前，只有一个头结点 printf("Input node number: "); int count = 0 ; scanf("%d", &count); for (int i = 0; i < count; i++) { node = (Linklist)malloc(sizeof(LNode)); // 为新结点开辟新内存 node->data = i; end->next = node; //新增结点插入在尾指针所指结点之后 end = node; } end->next = NULL; }

删除指定元素

void deleteNode(LinkList *head,int pos) { LNode* posNode=head->next; LNode* posNodeFront=head; if(posNode==NULL) printf("链表为空！"); else{ while(posNode->data!=posData && posNode!=NULL){ posNodeFront=posNode; posNode=posNodeFront->next; } if(posNode==NULL){ printf("无法找到指定位置"); return; } posNodeFront->next=posNode->next; free(posNode); } }

二叉树

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点

二叉树性质

1、二叉树中，第 i 层最多有 2i-1 个结点。 2、如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。 3、二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1 深度为m的二叉树最多有2m-1个结点，最少有m个结点；

二叉树结构体

typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

二叉树的遍历方式（递归建立）

void PreOrderTraverse(BiTree T)//二叉树的先序遍历 { if(T==NULL) return ; printf("%c ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } void InOrderTraverse(BiTree T)//二叉树的中序遍历 { if(T==NULL) return ; InOrderTraverse(T->lchild); printf("%c ",T->data); InOrderTraverse(T->rchild); } void PostOrderTraverse(BiTree T)//后序遍历 { if(T==NULL) return; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); } void BinaryTreeLevelOrder(BiTNode* root) //层次遍历 { Queue q; //树为空，直接返回 if (root == NULL) { return; } QueueInit(&q); //先将根节点入队 QueuePush(&q, root); while (QueueEmpty(&q)) { //出队保存队头并访问 BTNode* front = QueueFront(&q); printf("%c", front->_data); QueuePop(&q); //将出队结点的左子树根入队 if (front->_left) QueuePush(&q, front->_left); //将出队结点的右子树根入队 if (front->_right) QueuePush(&q, front->_right); } }