C语言学习强化

前言

数据的逻辑结构包括：

常见数据结构：

线性结构：数组、链表、队列、栈

树形结构：树、堆

图形结构：图 

一、链表

链表是物理位置不连续，逻辑位置连续

链表的特点：

1.链表没有固定的长度，可以自由增加节点

2.链表可以快速插入和删除数据

链表和数组的优劣

1.数组查找方便，尾部插入数据效率高，但在开头和中间插入数据效率低，需要移位

2.链表查找麻烦，无论在什么位置插入或删除数据效率都高

1.链表的创建与死亡

（1）定义链表中节点的结构

//在实现链式表之前，先确定表中某一个节点类型
typedef struct MyNode
{int data;struct MyNode *pNext;
}NODE;

data为数据域，pNext为指针域，指向下一个节点 

（2）定义链表结构

//单向链表的类型定义
typedef struct LinkList
{NODE* pHead;		//链表的头节点NODE* pEnd;			//链表的尾节点int length;			//链表的长度
}LL;

pHead指向链表的头节点，pEnd指向链表的尾节点，length来记录链表的长度

（3）创建单链表

//创建单链表
LL* List_Init()
{LL* pTemp = (LL*)malloc(sizeof(LL));if (NULL == pTemp){return NULL;}else{pTemp->pHead = NULL;pTemp->pEnd = NULL;pTemp->length = 0;return pTemp;}
}

链表初始化，malloc动态分配内存，将头节点、尾节点、长度初始化后，返回链表的首地址。

（4）创建链表中的一个节点

//创建链表的一个节点
NODE* NODE_Init(int data)
{NODE* pTemp = (NODE*)malloc(sizeof(NODE));if (NULL == pTemp){return NULL;}else{pTemp->pNext = NULL;pTemp->data = data;return pTemp;}
}

创建链表中的一个节点，把数据放入节点中，但指向下一个节点的指针仍为空指针，也暂时还没有指针指向该节点，也就是说该节点目前还没有与链表建立联系

（5）链表的死亡

//链表的死亡
void List_Dele(LL **pList)
{if (NULL == *pList){printf("链表不存在\n");return;}NODE* pTemp = NULL;			//借用临时变量循环遍历链表中的每个节点再进行删除while ((*pList)->pHead)		//当头节点为空指针时，链表节点遍历完成{pTemp = (*pList)->pHead;		//暂存头节点的地址(*pList)->pHead = (*pList)->pHead->pNext;			//头节点移至下一节点free(pTemp);			//释放节点所占内存}free(*pList);			//释放链表所占内存*pList = NULL;          //将指向链表的指针赋值为空指针
}

利用二级指针可以改变一级指针的内容

int main()
{LL* pList = List_Init();if (NULL == pList){printf("创建失败\n");}List_Dele(&pList);return 0;
}

这里main函数给List_Dele传参时是取了链表指针的地址，于是在函数中，就能修改链表指针的内容

2.链表的插入

（1）链表尾部添加元素

//在链表尾部添加元素
void List_append(LL* pList, int val)
{if (NULL == pList){printf("链表不存在，添加失败\n");return;}NODE* pTemp = NODE_Init(val);if (NULL == pTemp){printf("节点创建失败\n");}if (NULL == pList->pHead)        //检查是否为空链表{pList->pHead = pList->pEnd = pTemp;        //空链表则头尾指针同时指向该新增元素}else{pList->pEnd->pNext = pTemp;            //非空链表情况pList->pEnd = pTemp;}pList->length++;                        //链表长度加1
}

详细分析见注释内容 

（2）链表中插入元素

//链表中插入元素
void List_insert(LL* pList, int idx, int val)
{if (NULL == pList){printf("链表不存在，添加失败\n");return;}NODE* pTemp = NODE_Init(val);if (NULL == pTemp){printf("节点创建失败，添加失败\n");}if (idx >= pList->length)            //如果索引超出长度范围，元素添加至尾部		{pList->pEnd->pNext = pTemp;pList->pEnd = pTemp;}else if (idx <= 0)                    //如果索引小于等于0，元素添加至开头{pTemp->pNext = pList->pHead;pList->pHead = pTemp;}else                                    //索引不在首尾处{NODE* pInsertNode = pList->pHead;        //从头节点开始迭代for (int i = 0; i < idx - 1; i++)         //指针迭代一次次往后指{pInsertNode = pInsertNode->pNext;    //一直迭代到指向要插入索引的前面}pTemp->pNext = pInsertNode->pNext;        //先让插入元素指向索引位置元素pInsertNode->pNext = pTemp;                //再让索引位置前的元素指向插入元素}pList->length++;
}

详细分析见注释内容 

（3）链表中删除元素

//删除单个元素
void List_deleNode(LL* pList, int idx)
{if (NULL == pList || 0 == pList->length){printf("链表不存在，添加失败\n");return;}if (idx < 0 || idx >= pList->length){printf("删除位置不存在\n");return;}NODE* pTemp = NULL;if (idx == 0)            //删除位置为开头{pTemp = pList->pHead;pList->pHead = pList->pHead->pNext;}else                    //删除位置为中间或尾部{NODE* pCurNode = pList->pHead;for (int i = 0; i < idx - 1; i++){pCurNode = pCurNode->pNext;        //迭代至指向删除元素的上一个}pTemp = pCurNode->pNext;pCurNode->pNext = pTemp->pNext;if (pCurNode->pNext == NULL){pList->pEnd = pCurNode;}}free(pTemp);pList->length--;
}

二、栈和队列

操作受限的线性表

栈的特点：先进后出

队列的特点：先进先出

1.栈

操作：出栈、入栈、得到栈顶元素、判断栈满或栈空

通过顺序表来实现

#include <stdio.h>
#include <stdlib.h>
#define STACK_LEN 10typedef struct MyStack
{int dataArr[STACK_LEN];int top;
}STACK;//创建
STACK* Stack_Init()
{STACK* pStack = (STACK*)malloc(sizeof(STACK));if (NULL == pStack){printf("栈创建失败\n");return NULL;}pStack->top = 0;return pStack;
}//判断栈是否满
int FullStack(STACK* pStack)
{if (pStack->top >= STACK_LEN){return 1;}return 0;
}//判断栈是否空
int EmptyStack(STACK* pStack)
{if (pStack->top == 0){return 1;}return 0;
}
//入栈
void Stack_push(STACK* pStack, int val)
{if (NULL == pStack){printf("栈不存在，入栈失败\n");return;}if (FullStack(pStack) == 1){printf("栈已满，不能入栈\n");return;}pStack->dataArr[pStack->top++] = val;
}//出栈
void Stack_pop(STACK* pStack)
{if (NULL == pStack){printf("栈不存在，入栈失败\n");return;}if (EmptyStack(pStack) == 1){printf("栈为空，不能入栈\n");return;}pStack->top--;
}//获取栈顶元素
int Stack_top(STACK* pStack)
{//栈为空，或栈不存在都会报错return pStack->dataArr[pStack->top - 1];
}//删除栈
void Stack_clear(STACK** pStack)
{if (NULL != *pStack){free(*pStack);*pStack = NULL;}
}int main()
{STACK* pStack = NULL;pStack = Stack_Init();Stack_clear(&pStack);return 0;
}

2.队列

操作：出栈、入栈、得到队头、得到队尾

通过链式表来实现

#include <stdio.h>
#include <stdlib.h>typedef struct MyNode
{int data;struct MyNode* pNext;
}NODE;typedef struct MyQueue
{NODE* pHead;		NODE* pEnd;			
}QUEUE;QUEUE* Queue_Init()
{QUEUE* pTemp = (QUEUE*)malloc(sizeof(QUEUE));if (NULL == pTemp){printf("队列创建失败\n");return NULL;}else{pTemp->pHead = NULL;pTemp->pEnd = NULL;return pTemp;}
}NODE* NODE_Init(int data)
{NODE* pTemp = (NODE*)malloc(sizeof(NODE));if (NULL == pTemp){printf("节点创建失败\n");return NULL;}else{pTemp->pNext = NULL;pTemp->data = data;return pTemp;}
}//入队
void Queue_push(QUEUE* pQue, int val)
{if (NULL == pQue){printf("链表不存在，添加失败\n");return;}NODE* pTemp = NODE_Init(val);if (NULL == pQue->pHead){pQue->pHead = pQue->pEnd = pTemp;}else{pQue->pEnd->pNext = pTemp;pQue->pEnd = pTemp;}
}//出队
void Queue_pop(QUEUE* pQue)
{if (NULL == pQue || NULL == pQue->pHead){printf("队列不存在\n");return;}NODE* pTemp = NULL;pTemp = pQue->pHead;pQue->pHead = pQue->pHead->pNext;if (NULL == pQue->pHead)pQue->pEnd = NULL;
}int Queue_front(QUEUE* pQue)
{return pQue->pHead->data;
}int Queue_back(QUEUE* pQue)
{return pQue->pEnd->data;
}void Queue_clear(QUEUE** pQue)
{if (NULL != *pQue){free(*pQue);*pQue = NULL;}
}

总体跟链表类似