一.链表
1.线性存储结构：
在一个结构体中 再放一个本类型（结构体类型）的指针
这个指针不指向自己 指向的是要找的下一个结构体的地址 以此类推 没有数量限制
2.声明及链表遍历：
1 #include2 3 typedef struct AA 4 { 5 int bh; 6 char* name; 7 char* tel; 8 struct AA* pNext; 9 }Node;10 11 int main()12 {13 14 Node a = { 1,"aa","111",NULL};15 Node b = { 2,"bb","222",NULL};16 Node c = { 3,"cc","333",NULL};17 18 Node* p = &a;19 20 a.pNext = &b;21 b.pNext = &c;22 23 while(p != NULL)24 {25 printf("%d %s %s\n",p->bh,p->name,p->tel);26 p = p -> pNext; 27 }28 29 return 0;30 }
注：
①代码中的p存的是这个结构体的地址 而不是这个结构体的指针
②在移动p的时候 不能用p++ 链表的存储不一定是连续的 连续的空间才可以用p++
3.链表添加：
思路：
①给节点申请空间 并赋值
②判断链表是否存在
分两种情况：一是不存在 那么这个新来的结点即是头 也是尾
二是存在 那么就让尾的下一个指向新来的这个结点（先连） 然后让尾指向新来的结点（后移）
1 #include2 #include 3 4 typedef struct NODE 5 { 6 int bh; 7 char* name; 8 char* tel; 9 struct NODE* pNext;10 }Node;11 12 void AddNode(int bh,char* name,char* tel,Node** ppHead,Node** ppEnd);13 14 int main()15 {16 Node* pHead = NULL;17 Node* pEnd = NULL;18 19 AddNode(1,"aaa","111",&pHead,&pEnd);20 AddNode(2,"bbb","222",&pHead,&pEnd);21 AddNode(3,"ccc","333",&pHead,&pEnd);22 AddNode(4,"ddd","444",&pHead,&pEnd);23 24 return 0;25 }26 27 void AddNode(int bh,char* name,char* tel,Node** ppHead,Node** ppEnd)28 {29 Node* pNode = (Node*)malloc(sizeof(Node));30 pNode -> bh = bh;31 pNode -> name = name;32 pNode -> tel = tel;33 pNode -> pNext = NULL;34 35 if((*ppHead) == NULL)36 {37 *ppHead = pNode;38 *ppEnd = pNode;39 }40 else41 {42 (*ppEnd) -> pNext = pNode;43 *ppEnd = pNode;44 }45 46 return ;47 }
注：
①整个链表是以第一个节点的地址存在的
②之所以链表有两个指针 一个头指针 一个尾指针 有了尾指针是为了省去遍历的过程 方便知道最后一个节点的位置
③在传参的时候 要注意 如果你想改变外面传进来的指针的值 那就得用二级指针
4.链表插入：
思路：
①头插：要插入的结点的下一个指向头 头指向新来的结点（要插入的结点）
②中间插入：循环遍历判断bh
如果等于 插入的结点的下一个指向标记的下一个 标记的下一个指向插入的结点
③尾插：尾的下一个等于新插入的结点 让新插入的结点作尾
1 #include2 #include 3 4 typedef struct NODE 5 { 6 int bh; 7 char* name; 8 char* tel; 9 struct NODE* pNext; 10 }Node; 11 12 int GetBh(); 13 Node* GetNode(); 14 void AddNode(Node** ppHead,Node** ppEnd,Node* pNode); 15 void InsertNode(Node** ppHead,Node** ppEnd,Node* pNode,int bh); 16 17 int main() 18 { 19 Node* pHead = NULL; 20 Node* pEnd = NULL; 21 22 AddNode(&pHead,&pEnd,GetNode()); 23 AddNode(&pHead,&pEnd,GetNode()); 24 AddNode(&pHead,&pEnd,GetNode()); 25 AddNode(&pHead,&pEnd,GetNode()); 26 27 InsertNode(&pHead,&pEnd,GetNode(),1); 28 InsertNode(&pHead,&pEnd,GetNode(),3); 29 InsertNode(&pHead,&pEnd,GetNode(),10); 30 31 return 0; 32 } 33 34 int GetBh() 35 { 36 static int i = 1; 37 return i++; 38 } 39 40 Node* GetNode() 41 { 42 Node* pNode = (Node*)malloc(sizeof(Node)); 43 pNode -> bh = GetBh(); 44 pNode -> name = "aaa"; 45 pNode -> tel = "111"; 46 pNode -> pNext = NULL; 47 48 return pNode; 49 } 50 51 void AddNode(Node** ppHead,Node** ppEnd,Node* pNode) 52 { 53 if(ppHead == NULL || ppEnd == NULL || pNode == NULL) 54 { 55 return ; 56 } 57 58 if((*ppHead) == NULL) 59 { 60 *ppHead = pNode; 61 *ppEnd = pNode; 62 } 63 else 64 { 65 (*ppEnd) -> pNext = pNode; 66 *ppEnd = pNode; 67 } 68 69 return ; 70 } 71 72 void InsertNode(Node** ppHead,Node** ppEnd,Node* pNode,int bh) 73 { 74 Node* pMark = *ppHead; 75 76 if((*ppHead) -> bh == bh) 77 { 78 pNode -> pNext = *ppHead; 79 *ppHead = pNode; 80 81 return ; 82 } 83 84 while(pMark -> pNext != NULL) 85 { 86 if(pMark -> pNext -> bh == bh) 87 { 88 pNode -> pNext = pMark -> pNext; 89 pMark -> pNext = pNode; 90 91 return ; 92 } 93 pMark = pMark -> pNext; 94 } 95 96 (*ppEnd) -> pNext = pNode; 97 *ppEnd = pNode; 98 99 return ;100 }
注：对链表进行操作的时候 一定要先连后面的 再连前面的
5.链表删除：
思路：
①删除的是否是头节点：pDel = 头节点 然后让头指向头的下一个 释放 free 赋空 return
②中间删除：
首先遍历链表 要删除的是标记的下一个 标记的下一个指向要删除的下一个（标记的下一个的下一个）
特殊情况：删除的是尾结点 所以这里要多一个if判断 判断删除的是否是尾结点
1 #include2 #include 3 4 typedef struct NODE 5 { 6 int bh; 7 char* name; 8 char* tel; 9 struct NODE* pNext; 10 }Node; 11 12 int GetBh(); 13 Node* GetNode(); 14 void AddNode(Node** ppHead,Node** ppEnd,Node* pNode); 15 void DeleteNode(Node** ppHead,Node** ppEnd,int bh); 16 17 int main() 18 { 19 Node* pHead = NULL; 20 Node* pEnd = NULL; 21 22 AddNode(&pHead,&pEnd,GetNode()); 23 AddNode(&pHead,&pEnd,GetNode()); 24 AddNode(&pHead,&pEnd,GetNode()); 25 AddNode(&pHead,&pEnd,GetNode()); 26 27 DeleteNode(&pHead,&pEnd,1); 28 DeleteNode(&pHead,&pEnd,2); 29 DeleteNode(&pHead,&pEnd,4); 30 31 return 0; 32 } 33 34 int GetBh() 35 { 36 static int i = 1; 37 return i++; 38 } 39 40 Node* GetNode() 41 { 42 Node* pNode = (Node*)malloc(sizeof(Node)); 43 pNode -> bh = GetBh(); 44 pNode -> name = "aaa"; 45 pNode -> tel = "111"; 46 pNode -> pNext = NULL; 47 48 return pNode; 49 } 50 51 void AddNode(Node** ppHead,Node** ppEnd,Node* pNode) 52 { 53 if(ppHead == NULL || ppEnd == NULL || pNode == NULL) 54 { 55 return ; 56 } 57 58 if((*ppHead) == NULL) 59 { 60 *ppHead = pNode; 61 *ppEnd = pNode; 62 } 63 else 64 { 65 (*ppEnd) -> pNext = pNode; 66 *ppEnd = pNode; 67 } 68 69 return ; 70 } 71 72 void DeleteNode(Node** ppHead,Node** ppEnd,int bh) 73 { 74 Node* pDel = NULL; 75 Node* pMark = *ppHead; 76 77 if((*ppHead) -> bh == bh) 78 { 79 pDel = *ppHead; 80 *ppHead = (*ppHead) -> pNext; 81 free(pDel); 82 pDel = NULL; 83 84 return ; 85 } 86 87 while(pMark -> pNext != NULL) 88 { 89 if(pMark -> pNext -> bh == bh) 90 { 91 pDel = pMark -> pNext; 92 pMark -> pNext = pMark -> pNext -> pNext; 93 free(pDel); 94 pDel = NULL; 95 96 if(pMark -> pNext == NULL) 97 { 98 *ppEnd = pMark; 99 100 return ;101 }102 }103 pMark = pMark -> pNext;104 }105 106 return ;107 }
注：一定要先连后删
6.链表简单练习：
①如何判断两个链表是否重合：看尾结点的地址
②如何找到第一个重合的点：
例如A链表 7个结点 B链表 5个结点
那么A比B长两个 让A先往下走两个 然后A和B一起走 重合的时候就找到了
③一个单向链表 想找到倒数第k个结点 且只遍历一次
定义两个指针 让指针1先移动k次 然后让指针1和指针2开始同时移动
当指针1移动到尾巴的时候 指针2指的地方就是倒数第k个结点
二.双向链表
1.说明：
相比单向链表 就是结构体中 多了一个pLast的指针 指向上一个 双向链表较单向的会更好操作
2.声明及增加：
思路：
①申请结点：对结点进行赋值 num和两个指针（NULL）
②如果头为空 即链表不存在 新来的结点既是头也是尾
其他情况 让新来的结点的上一个指向尾
1 #include2 #include 3 4 typedef struct NODE 5 { 6 int num; 7 struct NODE* pLast; 8 struct NODE* pNext; 9 }Node;10 11 void AddNode();12 13 int main()14 {15 Node* pHead = NULL;16 Node* pEnd = NULL;17 18 AddNode(&pHead,&pEnd,1);19 AddNode(&pHead,&pEnd,2);20 AddNode(&pHead,&pEnd,3);21 22 return 0;23 }24 25 void AddNode(Node** ppHead,Node** ppEnd,int num)26 {27 Node* pMark = *ppHead;28 Node* pNode = (Node*)malloc(sizeof(Node));29 pNode -> num = num;30 pNode -> pLast = NULL;31 pNode -> pNext = NULL;32 33 if((*ppHead) == NULL)34 {35 *ppHead = pNode;36 *ppEnd = pNode;37 38 return ;39 }40 else41 {42 (*ppEnd) -> pNext = pNode;43 pNode -> pLast = *ppEnd;44 *ppEnd = pNode;45 46 return ;47 }48 }
三.栈
1.特点：先进后出 FILO（first in last out）
2.声明一个栈顶：
这里我们只能对栈顶元素进行操作 一个就够 这是不同与链表的地方
1 Stack* pTop = NULL;
3.判断栈是否为空：
思路：
①如果pTop为空 返回TRUE
②如果pTop不为空 返回FASLE
注：在C中是没有bool类型的 但是我们可以自己定义一个 详情看下面的代码
4.压栈：（进栈 相当于链表的头插）
思路：
①申请结点 赋值
②让新来结点的下一个等于栈顶 让栈顶等于新来的结点
这里是不用做if判断栈是否为空的 如果进栈的顺序是1 2 3 那么栈中的顺序就是3 2 1
5.出栈：不是把这个结点删除 而是把这个头的指针返给我 方便我进行下一步的操作
写法一：（返回的是一个结点）
思路：
①定义一个Stack*类型的pMark指向栈顶
②判断栈是否为空 为空就return
③让栈顶指向栈顶的下一个 返回pMark
注：
判断栈是否为空的时候 条件是IsEmpty(*ppTop) == TRUE
写法二：（返回的是里面的值）
思路：
①定义一个int类型的变量num来接我们要返回的值
②定义一个Stack*类型的pDel来接栈顶元素
③先赋值 后删除
④return num这个数
把上面的三个功能放在下面一个代码中：
1 #include2 #include 3 4 typedef struct STACK 5 { 6 int num; 7 struct STACK* pNext; 8 }Stack; 9 10 typedef int BOOL;11 #define TRUE 112 #define FALSE 013 14 BOOL IsEmpty(Stack* pTop);15 void Push(Stack** pTop,int num);16 Stack* Pop(Stack** pTop);17 int PopInt(Stack** pTop);18 19 int main()20 {21 Stack* pTop = NULL;22 23 Push(&pTop,1);24 Push(&pTop,2);25 Push(&pTop,3);26 27 Pop(&pTop);28 printf("%d\n",PopInt(&pTop));29 30 return 0;31 }32 33 BOOL IsEmpty(Stack* pTop)34 {35 if(pTop == NULL)36 {37 return TRUE;38 }39 else40 {41 return FALSE;42 }43 }44 45 void Push(Stack** pTop,int num)46 {47 Stack* pStack = (Stack*)malloc(sizeof(Stack));48 pStack -> num = num;49 pStack -> pNext = NULL;50 51 pStack -> pNext = *pTop;52 *pTop = pStack;53 54 return ;55 }56 57 Stack* Pop(Stack** pTop)58 {59 Stack* pMark = *pTop;60 if(IsEmpty(*pTop) == TRUE)61 {62 return NULL;63 }64 else65 {66 *pTop = (*pTop) -> pNext;67 return pMark;68 }69 }70 71 int PopInt(Stack** pTop)72 {73 int num;74 Stack* pDel = *pTop;75 76 if(IsEmpty(*pTop) == TRUE)77 {78 return -1;79 }80 else81 {82 num = (*pTop) -> num;83 *pTop = (*pTop) -> pNext;84 free(pDel);85 pDel = NULL;86 87 return num;88 }89 }
四.队列
1.特点：先进先出 FIFO（first in first out）
2.入队（即尾部添加）
3.出队（即头部删除 返回值是一个结点）
1 #include2 #include 3 4 typedef struct QUEUE 5 { 6 int num; 7 struct QUEUE* pNext; 8 }Queue; 9 10 void Push(Queue** ppHead,Queue** ppEnd,int num);11 Queue* Pop(Queue** ppHead,Queue** ppEnd);12 13 int main()14 {15 Queue* pHead = NULL;16 Queue* pEnd = NULL;17 18 Push(&pHead,&pEnd,1);19 Push(&pHead,&pEnd,2);20 Push(&pHead,&pEnd,3);21 22 printf("%d\n",(Pop(&pHead,&pEnd)) -> num);23 printf("%d\n",(Pop(&pHead,&pEnd)) -> num);24 printf("%d\n",(Pop(&pHead,&pEnd)) -> num); 25 26 return 0;27 }28 29 void Push(Queue** ppHead,Queue** ppEnd,int num)30 {31 Queue* pQueue = (Queue*)malloc(sizeof(Queue));32 pQueue -> num = num;33 pQueue -> pNext = NULL;34 35 if(*ppHead == NULL)36 {37 *ppHead = pQueue;38 *ppEnd = pQueue;39 }40 else41 {42 (*ppEnd) -> pNext = pQueue;43 *ppEnd = pQueue;44 }45 46 return ;47 }48 49 Queue* Pop(Queue** ppHead,Queue** ppEnd)50 {51 Queue* pDel = *ppHead;52 53 if((*ppHead) == NULL)54 {55 return NULL;56 }57 else58 {59 *ppHead = (*ppHead) -> pNext;60 if((*ppHead) == NULL)61 {62 *ppEnd = NULL;63 }64 return pDel;65 }66 }