LinkList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int ElemType;//假定线性表的元素类型为整型
//定义节点
typedef struct node {
int data;
struct node *pNext;
}LinkListNode;
///创建带有头节点的链表Init
///函数的返回值是头节点，没有参数
LinkListNode* InitLinkList(void);
///求长度：求顺序表中的元素的个数
///函数的返回值是顺序表的长度，参数pHead：是单链表的头节点
int GetSizeLinkList(LinkListNode* pHead);
///取元素：取给定位置的元素值
///返回值：第i个元素的地址，pHead：头指针，i 待查节点的序号
LinkListNode* GetLinkListNode(LinkListNode* pHead, int pos);
///查元素：查找给定元素值的位置
///返回值：节点的地址，找不到就返回NULL
///pHead:单链表的头指针，objData：是需要匹配的元素值
LinkListNode* LocateLinkList(LinkListNode* pHead, int objData);
///插入元素：在指定的位置插入给定的值
///尾插法建立单链表（将逻辑上的顺序表放入单链表的物理结构当中）
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
LinkListNode* Create_Rear_LkList(ElemType arr[], int length);
///头插法建立单链表
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
LinkListNode* Create_Front1_LkList(ElemType arr[], int length);
///头插法2
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
LinkListNode* Create_Front2_LkList(ElemType arr[], int length);
///头插法建立
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
LinkListNode* Create_Front3_LkList(ElemType arr[], int length);
///插入元素：在指定的位置插入给定的值
//ptr:带插入的元素位置，将在ptr的后继结点中插入，x：插入的值
void Insert_After_LkList(LinkListNode* ptr, ElemType x);
///指定位置之前插入
///pHead:链表的头指针，ptr：带插入的元素位置，x：插入的值
void Insert_Before_LkList(LinkListNode* pHead, LinkListNode* ptr, ElemType x);
///删除节点：Ptr是需要删除的节点，将删除ptr的后续节点
///返回值是带删除的节点位置
LinkListNode* Delete_After_LkList(LinkListNode* ptr);
///删除第i个节点
///返回值是带删除的节点位置,pHead:头节点，i是第i个元素
LinkListNode* Delete_i_LkList(LinkListNode* pHead, int i);
///遍历
void ShowLkList(LinkListNode* pHead);
SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;//假定线性表的元素类型为整型
#define LIST_SIZE 1024 //假定我们的线性表长度是1024
#define TRUE 1
#define FALSE 0
typedef struct {
ElemType data[LIST_SIZE];
int last;//指向最后一个节点的位置
}SequenList;
//last的存在的目的：为了在函数调用的时候传递数据方便，因为我们与分配
//的空间中，并不是立即存满的
///数组顺序表的实现初始化
///获得一个长度为0的数组
SequenList* InitSeq();
///求长度：求线性表中的元素的个数
///获得当前数组顺序表的元素个数，pList:顺序表的起始地址
int GetSizeSeq(SequenList* pList);
///取元素：取给定位置的元素值
///返回值是元素值
///pList:目标的顺序表, pos：获取元素的下标 ,e：将元素值放入
int GetElemSqList(SequenList* pList, int pos, ElemType *e);
/// 查元素：查找给定元素值的位置
///相同值只去第一个
///返回值：-1表示没有找到，否则返回带查找元素的角标
///pList：传入的数组顺序表，Key比对的值
int LocateElemSqList(SequenList* pList, ElemType key);
/// 插入元素：在指定的位置插入给定的值
/// 插入的位置为k：k: 0 -- n-1
//pList:目标顺序表，x待插入的元素，k插入的位置
int InsertElemSqList(SequenList* pList, ElemType x, int k);
///删除：删除指定位置的值或者是删除给定的值。
//pList:目标顺序数组，k表示需要删除的位置
int DelElemSqList(SequenList *pList, int k);
///遍历元素：从头到尾扫描线性表。
///pList:目标顺序数组
void showSeqList(SequenList* pList);
Linux内核中的双向链表.h
//#ifndef _LIST_HEAD_H
//#define _LIST_HEAD_H
//
双向链表节点
//struct list_head {
// struct list_head *next, *prev;
//};
//
初始化节点：设置name节点的前继节点和后继节点都是指向name本身。
//#define LIST_HEAD_INIT(name) { &(name), &(name) }
//
定义表头(节点)：新建双向链表表头name，并设置name的前继节点和后继节点都是指向name本身。
//#define LIST_HEAD(name) \
// struct list_head name = LIST_HEAD_INIT(name)
//
初始化节点：将list节点的前继节点和后继节点都是指向list本身。
//static inline void INIT_LIST_HEAD(struct list_head *list)
//{
// list->next = list;
// list->prev = list;
//}
//
添加节点：将new插入到prev和next之间。
//static inline void __list_add(struct list_head *new,
// struct list_head *prev,
// struct list_head *next)
//{
// next->prev = new;
// new->next = next;
// new->prev = prev;
// prev->next = new;
//}
//
添加new节点：将new添加到head之后，是new称为head的后继节点。
//static inline void list_add(struct list_head *new, struct list_head *head)
//{
// __list_add(new, head, head->next);
//}
//
添加new节点：将new添加到head之前，即将new添加到双链表的末尾。
//static inline void list_add_tail(struct list_head *new, struct list_head *head)
//{
// __list_add(new, head->prev, head);
//}
//
从双链表中删除entry节点。
//static inline void __list_del(struct list_head * prev, struct list_head * next)
//{
// next->prev = prev;
// prev->next = next;
//}
//
从双链表中删除entry节点。
//static inline void list_del(struct list_head *entry)
//{
// __list_del(entry->prev, entry->next);
//}
//
从双链表中删除entry节点。
//static inline void __list_del_entry(struct list_head *entry)
//{
// __list_del(entry->prev, entry->next);
//}
//
从双链表中删除entry节点，并将entry节点的前继节点和后继节点都指向entry本身。
//static inline void list_del_init(struct list_head *entry)
//{
// __list_del_entry(entry);
// INIT_LIST_HEAD(entry);
//}
//
用new节点取代old节点
//static inline void list_replace(struct list_head *old,
// struct list_head *new)
//{
// new->next = old->next;
// new->next->prev = new;
// new->prev = old->prev;
// new->prev->next = new;
//}
//
双链表是否为空
//static inline int list_empty(const struct list_head *head)
//{
// return head->next == head;
//}
//
获取"MEMBER成员"在"结构体TYPE"中的位置偏移
//#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
//
根据"结构体(type)变量"中的"域成员变量(member)的指针(ptr)"来获取指向整个结构体变量的指针
//#define container_of(ptr, type, member) ({ \
// const typeof( ((type *)0)->member ) *__mptr = (ptr); \
// //(type *)( (char *)__mptr - offsetof(type,member) );})
//
遍历双向链表
//#define list_for_each(pos, head) \
// for (pos = (head)->next; pos != (head); pos = pos->next)
//
//#define list_for_each_safe(pos, n, head) \
// for (pos = (head)->next, n = pos->next; pos != (head); \
// pos = n, n = pos->next)
//
//#define list_entry(ptr, type, member) \
// container_of(ptr, type, member)
//
//#endif
数组形式的顺序表
#include "SeqList.h"
/*
1） 初始化：给线性表中的相关参数赋值
2） 求长度：求线性表中的元素的个数
3） 取元素：取给定位置的元素值
4） 查元素：查找给定元素值的位置
5） 插入元素：在指定的位置插入给定的值
6） 删除：删除指定位置的值或者是删除给定的值。
7） 遍历元素：从头到尾扫描线性表。
*/
SequenList* lPtr;
//实现初始化
SequenList* InitSeq() {
SequenList *pList=NULL;
pList = (SequenList *)malloc(sizeof(SequenList));
if (pList != NULL)
pList->last = 0;//初始化成功，且长度为0
return pList;
}
//SequenList seqenList;
//SequenList *seqenList;
//前者分配空间了，而后者没有空间
//求长度：求线性表中的元素的个数
int GetSizeSeq(SequenList* pList) {
return pList->last;
}
//取元素：取给定位置的元素值
/// pList:目标的顺序表, pos：获取元素的下标 ,e：将元素值放入
int GetElemSqList(SequenList* pList, int pos, ElemType *e) {
if (pos<0 || pos>pList->last) {
return FALSE;
}
if (pList->last <= 0)
return FALSE;
//说明此时pos在0 -- n之间
*e = pList->data[pos];
return TRUE;
}
// 查元素：查找给定元素值的位置
//相同值只去第一个
//返回值：-1表示没有找到，否则返回带查找元素的角标
//pList：传入的数组顺序表，Key比对的值
int LocateElemSqList(SequenList* pList, ElemType key) {
int i;
for (i = 0;i < pList->last;i++) {
if (pList->data[i] == key)
return i;
}
return -1;
}
// 插入元素：在指定的位置插入给定的值
// 插入的位置为k：k: 0 -- n-1
// 顺序表：不满
//pList:目标顺序表，x待插入的元素，k插入的位置
int InsertElemSqList(SequenList* pList, ElemType x, int k) {
int j;
//顺序表尚未填满
if (pList->last >= LIST_SIZE - 1)
return FALSE;
//表明K是有效位置
if (k<0 || k>(pList->last + 1))
return FALSE;
for (j = pList->last;j >= k;j--) {
pList->data[j + 1] = pList->data[j];
}
pList->data[k] = x;
pList->last = pList->last + 1;
return TRUE;
}
//删除：删除指定位置的值或者是删除给定的值。
//pList:目标顺序数组，k表示需要删除的位置
int DelElemSqList(SequenList *pList, int k) {
if ((k >= 0 && k <= pList->last) && (pList->last != 0)) {
for (int j = k;j <= pList->last;j++) {
pList->data[j] = pList->data[j + 1];
}
pList->last--;
return TRUE;
}
return FALSE;
}
//遍历元素：从头到尾扫描线性表。
void showSeqList(SequenList* pList) {
for (int i = 0;i < pList->last;i++) {
printf(" %d", pList->data[i]);
}
}
int main1(void) {
lPtr = InitSeq();//这样是否可以=>可以的，且使用NULL来判断是否初始化完毕
if (lPtr) {
//todo:继续使用这个顺序表
for (int i = 0;i < 10;i++) {
InsertElemSqList(lPtr, i, i);
}
printf("初始化后顺序表的元素个数：%d", GetSizeSeq(lPtr));
printf("************\n");
showSeqList(lPtr);
InsertElemSqList(lPtr, 2000, 0);
printf("初始化后顺序表的元素个数：%d", GetSizeSeq(lPtr));
printf("************\n");
showSeqList(lPtr);
DelElemSqList(lPtr, 1);
printf("初始化后顺序表的元素个数：%d", GetSizeSeq(lPtr));
printf("************\n");
showSeqList(lPtr);
int pos = LocateElemSqList(lPtr, 16);
if (pos >= 0) {
printf("当前元素位于%d", pos);
}
else {
printf("没有找到这个元素");
}
printf("************\n");
showSeqList(lPtr);
}
else {
//todo:提示没有可以使用的空间
}
getchar();
getchar();
return 0;
}
链表形式的顺序表
#include "LinkList.h"
/*
1） 初始化：给线性表中的相关参数赋值
2） 求长度：求线性表中的元素的个数
3） 取元素：取给定位置的元素值
4） 查元素：查找给定元素值的位置
5） 插入元素：在指定的位置插入给定的值
6） 删除：删除指定位置的值或者是删除给定的值。
7） 遍历元素：从头到尾扫描线性表。
*/
///创建带有头节点的链表Init
LinkListNode* InitLinkList(void) {
LinkListNode* pHead = NULL;
pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
if (pHead) {
pHead->pNext = NULL;
}
return pHead;
}
//求长度：求线性表中的元素的个数
int GetSizeLinkList(LinkListNode* pHead) {
int n = 0;
while (pHead->pNext) {
n++;
pHead = pHead->pNext;
}
return n;
}
//取元素：取给定位置的元素值
//输入链表的头指针，要查找的编号，输出第i个元素的地址
///pHead：头指针，i 待查节点的序号
LinkListNode* GetLinkListNode(LinkListNode* pHead, int pos) {
int j;
LinkListNode* p;
p = pHead;
j = 0;
if(pos == 0)
return NULL;
while (j < pos && p->pNext != NULL) {
p = p->pNext;
j++;
}
if (pos == j)
return p;
else
return NULL;
}
//查元素：查找给定元素值的位置
///找到就返回节点的地址，找不到就返回NULL
LinkListNode* LocateLinkList(LinkListNode* pHead, int objData) {
LinkListNode* p;
p = pHead->pNext;//跳过头节点
while (p != NULL && p->data != objData) {
p = p->pNext;
}
return p;
}
//插入元素：在指定的位置插入给定的值
//因为链表这种结构的内存是由程序员管理的，因此它的建立有一定的运算
//方法
///尾插法建立单链表（将逻辑上的顺序表放入单链表的物理结构当中）
//arr:传入的顺序表，length：顺序表的长度
LinkListNode* Create_Rear_LkList(ElemType arr[], int length) {
LinkListNode* pHead, *p, *q;
int i;//循环变量，用来遍历全部的顺序表
pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
q = pHead; //q是获得了当前链表的头节点
//q保存了pHead,同时通过q不断前移使得链表串联起来
for (i = 0;i < length;i++) {
//获得一个单链表的节点，将这个节点加入到有
//pHead指向的这个链表当中
p = (LinkListNode*)malloc(sizeof(LinkListNode));
//p获得一个可以加入链表的节点单元
p->data = arr[i];//将顺序表的内容存入单链表的节点
q->pNext = p;//
q = p;
}
p->pNext = NULL;
return pHead;
}
///头插法建立单链表
LinkListNode* Create_Front1_LkList(ElemType arr[], int length) {
LinkListNode* pHead, *p, *q;
int i;
pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
pHead->pNext = NULL;
q = pHead->pNext;
//头插的时候，必须逆序遍历顺序表
for (i = length - 1;i >= 0;i--) {
p = (LinkListNode*)malloc(sizeof(LinkListNode));
p->data = arr[i];
p->pNext = q;//是的新加入的节点传入了上一个节点
pHead->pNext = p;//头节点指向了当前的新加入节点
q = pHead->pNext;//让q指向当前的节点
}
return pHead;
}
///头插法2
LinkListNode* Create_Front2_LkList(ElemType arr[], int length) {
LinkListNode* pHead, *p, *q;
//p是新加入节点，q是当前节点
int i;
q = NULL;
for (i = length - 1;i >= 0;i--) {
p = (LinkListNode*)malloc(sizeof(LinkListNode));
p->data = arr[i];
p->pNext = q;
q = p;
}
pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
pHead->pNext = q;
return pHead;
}
///头插法建立
LinkListNode* Create_Front3_LkList(ElemType arr[], int length) {
LinkListNode* pHead, *p;
int i;
pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
pHead->pNext = NULL;
for (i = length - 1;i >= 0;i--) {
p = (LinkListNode*)malloc(sizeof(LinkListNode));
p->data = arr[i];
p->pNext = pHead->pNext;
pHead->pNext = p;
}
//之所以我们的方法三可以节省方法一中的一个变量q
//原因是：pHead不发生变化，而pHead中的pNext始终作为当前节点的指针
return pHead;
}
/*
顺序表：12，33，44，76，89，90（逻辑上的顺序表）=>单链表
本例中，我们用数组表示这种顺序表
*/
//插入元素：在指定的位置插入给定的值
//在指定位置之后插入
void Insert_After_LkList(LinkListNode* ptr, ElemType x) {
LinkListNode* s;
s = (LinkListNode*)malloc(sizeof(LinkListNode));
s->data = x;
s->pNext = ptr->pNext;
ptr->pNext = s;
}
//指定位置之前插入
void Insert_Before_LkList(LinkListNode* pHead, LinkListNode* ptr, ElemType x) {
LinkListNode* s, *qPtr;
s = (LinkListNode*)malloc(sizeof(LinkListNode));
s->data = x;
qPtr = pHead;//qPtr是用来代替pHead的移动的,ptr是目标节点
while (qPtr->pNext != ptr)
qPtr = qPtr->pNext;
s->pNext = ptr;
qPtr->pNext = s;
//因为链表是单向的，虽然我知道当前节点是ptr
//但是在语法层面上，我如果想知道ptr的前继节点只能从head遍历而来
//查到了当前节点的前继，才能使用后插的方法完成节点的加入
}
//删除：删除指定位置的值或者是删除给定的值。
//情形一：删除指定节点的后继结点
//情形二：删除第i个节点，假定头节点i=0
//删除返回目标节点的地址，并不涉及到动态空间的回收
//在动态回收空间的要求中，应该遵循的原理是谁污染谁治理
//在顺序表中的删除就是逻辑上的删除，就是说我们的这个节点不再
//存在于当前的顺序表中了
///删除节点：Ptr是需要删除的节点，将删除ptr的后续节点
LinkListNode* Delete_After_LkList(LinkListNode* ptr) {
LinkListNode* fptr;
//假定我们的顺序表A-》B-》C,我们要删除的是A的后续节点B，A-》C
fptr = ptr->pNext;// ptr是A，所以ptr的next是B，所以fptr是B
ptr->pNext = fptr->pNext;//ptr是A，fptr是B，所以fptr的next是C，所以ptr-next就变成C
return fptr;
}
///删除第i个节点
LinkListNode* Delete_i_LkList(LinkListNode* pHead, int i) {
LinkListNode*ptr, *qPtr = NULL;
ptr = GetLinkListNode(pHead, i - 1);//找到i的前继节点
if (ptr != NULL && ptr->pNext != NULL)
qPtr = Delete_After_LkList(ptr);
return qPtr;
}
//遍历
void ShowLkList(LinkListNode* pHead) {
LinkListNode* p = pHead->pNext;
while (p != NULL) {
printf(" %d", p->data);
p = p->pNext;
}
}
int main3(void) {
ElemType MySeq[] = { 1,2,3,4,5 };
LinkListNode* pHead = Create_Rear_LkList(MySeq, 5);
printf("\n********显示当前单链表中的全部元素******\n");
ShowLkList(pHead);
LinkListNode* pPos = GetLinkListNode(pHead, 2);
Insert_After_LkList(pPos, 999);
printf("\n********显示当前单链表中的全部元素******\n");
ShowLkList(pHead);
Insert_Before_LkList(pHead, pPos, 666);
printf("\n********显示当前单链表中的全部元素******\n");
ShowLkList(pHead);
//Delete_After_LkList(pPos);
Delete_i_LkList(pHead, 2);
printf("\n********显示当前单链表中的全部元素******\n");
ShowLkList(pHead);
printf("\nList Size:%d", GetSizeLinkList(pHead));
getchar();
return 0;
}
顺序表转置
设有一个顺序表，其数据为a,b,c,d,e,f,g,要求将其就地转置成g,f,e,d,c,b,a
要求逆转表仍然占据原空间
//#include "SeqList.h"
//SequenList* pGlobalSeq;
//
//void RevseSeqList(SequenList* pList) {
// int temp;
// int count, i;
// if (pList->last == 0 || pList->last == 1)
// return;
// count = pList->last / 2;
// for (i = 0;i < count;i++) {
// temp = pList->data[i];
// pList->data[i] = pList->data[pList->last - 1 - i];
// pList->data[pList->last - 1 - i] = temp;
// }
//}
//int main(void) {
// pGlobalSeq=InitSeq();
// for (int i = 0;i < 10;i++) {
// InsertElemSqList(pGlobalSeq, i * 2, i);
// }
// printf("\n**********当前的顺序表元素********\n");
// showSeqList(pGlobalSeq);
// RevseSeqList(pGlobalSeq);
// printf("\n**********当前的顺序表元素********\n");
// showSeqList(pGlobalSeq);
// free(pGlobalSeq);
// getchar();
// return 0;
//}
//Ctrl+a Ctrl+k Ctrl+C
#include "LinkList.h"
LinkListNode* ReverseLkList(LinkListNode* pHead) {
LinkListNode* Pointer, *Next;//Pointer是将来依次获得的当前节点
//Next:将来获得的当前节点的原先的下一个节点
LinkListNode* Back; //原先节点的上一个节点
//step 1: 将原先的next节点的next域变为pointer
//step 2：将原先的pointer的next域变成back
Back = pHead; //原先就是从头节点开始，因此，我们首先将back作为头节点
Pointer = Back->pNext;//通过头节点获得了第一个元素=>pointer指向第一个元素
Next = Pointer->pNext;//此时pointer是第一个元素，因此它的pNext是第二个元素
Pointer->pNext = Back;//pointer->pNext域变成了Back，又因为Back是头节点，所以
//此时原先的第一个元素的后继已经变成了原先的头节点
Back = Pointer;//pointer是第一个元素，因此，此时Back变成了第一个元素
Pointer = Next;//因为在46行，Next已经是第二个元素了，
//因此，此时pointer指向了第二个元素
//在46行，Next变成了原先的第二个元素，有因为在46行-51行，没有在对Next的pNext域
//进行操作,因此，原先链表中的后继信息没有破坏
//47行，pointer作为当前元素指向了原先的前继节点的时候，此时，当前元素把原先的前继元素
//变成了后续节点
//48行，再将Back设为当前元素，49行将Pointer设为下一个元素
while (Pointer->pNext != NULL) {
Next = Pointer->pNext;
Pointer->pNext = Back;
Back = Pointer;
Pointer = Next;
}
Pointer->pNext = Back;
//此时Pointer已经是原先链表中的最后一个元素了，
//因此，必须要把Pointer和原先的前继节点联系起来，而原先的前继节点一定在Back
//此时反转完毕，我们需要重新设置头节点
//原先的pHead没有变，因此原先的pHead->pNext指向的原先的第一个元素
//但是现在我们要让这个元素的pNext域置为空
pHead->pNext->pNext = NULL;
//由于pHead没有变，所以我们依然让它作为反转后链表的头节点
//所以将当前的首元素放置它的pnext域中
pHead->pNext = Pointer;
return pHead;
}
int mainAAA(void) {
LinkListNode* pHead = NULL;
int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
pHead = Create_Rear_LkList(arr, 10);
printf("\n************当前的元素有\n");
ShowLkList(pHead);
pHead = ReverseLkList(pHead);
printf("\n************当前的元素有\n");
ShowLkList(pHead);
getchar();
return 0;
}
双向链表
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data;
struct DNode* prior, *next;
}DLinkListNode;
DLinkListNode* Delete_DL(DLinkListNode* ptr) {
ptr->prior->next = ptr->next;
ptr->next->prior = ptr->prior;//在逻辑上，我们再也无法找到这个ptr
return ptr;
}
void Insert_Before_DL(DLinkListNode* p, int x) {
DLinkListNode* s;
s = (DLinkListNode*)malloc(sizeof(DLinkListNode));
s->data = x;
//将s的关系加入到链表
s->prior = p->prior;
if (p->prior != NULL)
p->prior->next = s;
s->next = p;
p->prior = s;
}
int main(void) {
DLinkListNode x;
DLinkListNode *head;
DLinkListNode *ptr;
ptr = &x;
ptr->data = 3;
ptr->prior = NULL;
ptr->next = NULL;
Insert_Before_DL(ptr, 1);
Insert_Before_DL(ptr, 2);
DLinkListNode* p,*q;
p = &x;
while (p != NULL) {
printf("%d\n", p->data);
if (p->prior == NULL)
q = p;//q记录了第一个节点
p = p->prior;
}
while (q != NULL) {
printf("%d\n", q->data);
q = q->next;
}
getchar();
return 0;
}
循环链表的建立
#include <stdio.h>
#include <stdlib.h>
///循环链表的建立
///输入：顺序表集合，顺序表长度
///输出:循环链表的尾地址
//定义节点
typedef struct node {
int data;
struct node *pNext;
}LinkCircleListNode;
LinkCircleListNode* Create_Circle_LkList(int arr[], int length) {
LinkCircleListNode *head, *p, *q;
int i;
head = (LinkCircleListNode*)malloc(sizeof(LinkCircleListNode));
q = head;
for (i = 0;i < length;i++) {
//p指向了临时申请的空间
p = (LinkCircleListNode*)malloc(sizeof(LinkCircleListNode));
p->data = arr[i];
q->pNext = p;//q在串联p的节点
q = p;//q移动到当前的节点
}
p->pNext = head;
return p;
}
//遍历输出
void ShowCircleLkList(LinkCircleListNode* pRear) {
LinkCircleListNode* p = pRear->pNext;//循环链表建立的尾指针的next域指向的是头节点
//因为遍历的时候，我们希望获得的真正元素，所以我们首先让p移动
p = p->pNext;//此时p指向第一个真正的元素
//while (p->pNext != pRrear->pNext) {//当且仅当p == pRear的时候，循环结束,那么最后一个reare节点是没有输出的
while (p != pRear->pNext) {
printf("%d\n", p->data);
p = p->pNext;
}
}
//两个循环链表合并
//输入为链表a的尾指针，链表b的尾指针
LinkCircleListNode * Connect_Circle_LkList(LinkCircleListNode* ra, LinkCircleListNode *rb) {
LinkCircleListNode* p;
//记录a的头节点
p = ra->pNext;
//将b的第一个元素节点链入a的尾部
ra->pNext = rb->pNext->pNext;
free(rb->pNext);//回收空间，意味着b链表的头节点空间不可达，但是rb->pNext依然是有值的
rb->pNext = p;
//假定rb0x20空间，在ox20空间下有一个next的分量，这个分量是可以存储地址值
//free(rb)才是是的rb->pnext不可用
//free(rb->pnext),rb->pnext中的（data和pnext）分量不可用
//rb->pNext始终指向的是原b链表的头节点
//所以52行执行完毕以后，将b链表的尾指针指向了a链表的头节点
return rb;
}
int mainCCCC(void) {
int arr[] = { 11,22,33,44,55 };
LinkCircleListNode* pRrear = Create_Circle_LkList(arr, 5);
//
//测试合并
int a[] = { 1,3,5 };
int b[] = { 2,4,6 };
LinkCircleListNode *ra, *rb;
ra = Create_Circle_LkList(a, 3);
rb = Create_Circle_LkList(b, 3);
LinkCircleListNode * pRear =Connect_Circle_LkList(ra, rb);
ShowCircleLkList(pRear);
getchar();
return 0;
}
约瑟夫环
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* pNext;
}LinkJoeNode;
//考虑建立约瑟夫环的循环链表
//不带头节点：需要模拟约瑟夫环的工作过程
LinkJoeNode* CreateLkList(int arr[], int length) {
LinkJoeNode *head, *p, *q;
int i;
head = (LinkJoeNode*)malloc(sizeof(LinkJoeNode));
head->data = arr[0];
q = head;
for (i = 1;i < length;i++) {
p = (LinkJoeNode*)malloc(sizeof(LinkJoeNode));
p->data = arr[i];
q->pNext = p;
q = p;
}
p->pNext = head;
return p;
}
//是不是要写show方法：打印输出大法，log
int mainDDDD(void) {
//从位置1开始，初始30个人，剩余15个人
int s = 1;
int m = 9;//每逢9就出圈
int k = 15;//表明出圈者要有15个人
int arr[30];
//构造初始的序列
for (int i = 0;i < 30;i++) {
arr[i] = i + 1;//因为我们为每一个变量的序号设为i+1
}
LinkJoeNode *p, *q;
LinkJoeNode *rear = CreateLkList(arr, 30);
p = rear;//p是遍历指针，只要游戏运行，那么这个p就要移动
while (k > 0) {
//step1:只要人数没有达到15个人，那么就要找出第m-1个，因为它的后继是即将要出圈
for (int j = 0;j < m - 1;j++) {
p = p->pNext;
}
//此时，p停在了m-1处
q = p->pNext;//q指向了第m个元素
printf("第%d个元素出圈\n", q->data);
//让m-1和m+1相连,此时q指向的第m个元素依然存在在内存空间当中，只是逻辑上
//不再存在和m元素相关联的联系
p->pNext = q->pNext;//p->pNext->pNext;
//为了防止内存泄漏
free(q);
k--;
}
getchar();
return 0;
}
一元多次多项式的加减
#include "stdio.h"
#include "stdlib.h"
//设计数据项的数据结构
typedef struct Polynode {
int coef;//系数
int exp;//指数
Polynode* pNext;
}LinkPolyNode;
//面临算法抽象：补充说明：所有的存储结构按照幂指数升序
//我们需要新增节点，因为有可能在原链表不存在
///新多项式元素的地址
///coef:系数，exp：幂指数，pc：新节点要插入的位置
///返回值：新分配的节点地址
LinkPolyNode* attach(int coef, int exp, LinkPolyNode* pc) {
LinkPolyNode* p;
p = (LinkPolyNode*)malloc(sizeof(LinkPolyNode));
p->coef = coef;
p->exp=exp;
pc->pNext = p;
return p;
}
///将PolyA和PolyB进行相加，将结果放入PolyC中
///函数的输入是PolyA和PolyB的首地址
///函数返回的是PolyC的首地址
LinkPolyNode* MergePoly(LinkPolyNode* headA, LinkPolyNode* headB) {
LinkPolyNode* headC;//需要返回的多项式C的地址
LinkPolyNode *pa, *pb, *pc, *p;
int x;
pa = headA->pNext;
pb = headB->pNext;
headC = (LinkPolyNode*)malloc(sizeof(LinkPolyNode));
pc = headC;//此时将pc做C多项式的头节点
while (pa && pb) {
if (pa->exp == pb->exp) {
x = pa->coef + pb->coef;
if (x != 0)
pc = attach(x, pa->exp, pc);
pa = pa->pNext;
pb = pb->pNext;
continue;
}
if (pa->exp < pb->exp) {
p = pa;pa = pa->pNext;
}
else {
p = pb;pb = pb->pNext;
}
pc = attach(p->coef, p->exp, pc);
}
p = pa;
if (pa == NULL) p = pb;
while (p) {
pc = attach(p->coef, p->exp, pc);
p = p->pNext;
}
pc->pNext = NULL;
return headC;
}
//假定多项式的最低项是常数项,假定所有的元素都是关于X的多项式
//PolyA: 1+2x+3x^2
//PolyB: 3x+x^4
///设计显示的辅助函数
void ShowList(LinkPolyNode* pHead) {
LinkPolyNode* p;
p = pHead->pNext;
while (p != NULL) {
//美化设计显示的内容:设计常数项的显示
if (p->exp == 0) {
printf("%d", p->coef);
p = p->pNext;
continue;
}
//设计一次项的显示
if (p->exp == 1) {
//printf("x")
if (p->coef > 0) {
printf("+%dx",p->coef);
}
else {
printf("%dx", p->coef);
}
p = p->pNext;
continue;
}
//设计高此项的显示
if (p->coef > 0) {
printf("+%dx^%d", p->coef, p->exp);
}
else {
printf("%dx^%d", p->coef, p->exp);
}
p = p->pNext;
}
}
/*程序是调出来的，不是一蹴而就的，只有掌握了原理才能完成*/
int mainBBB(void) {
//PolyA: 1+2x+3x^2
//PolyB: 3x+x^4
LinkPolyNode HeadA,A1,A2,A3;
LinkPolyNode HeadB, B1, B2;
HeadA.pNext = &A1;
A1.pNext = &A2;
A2.pNext = &A3;
A3.pNext = NULL;
HeadB.pNext = &B1;
B1.pNext = &B2;
B2.pNext = NULL;
//建立多项式:PolyA: 1+2x+3x^2
A1.coef = 1;
A1.exp = 0;
A2.coef = 2;
A2.exp = 1;
A3.coef = 3;
A3.exp = 2;
//PolyB: 3x+x^4
B1.coef = 3;
B1.exp = 1;
B2.coef = 1;
B2.exp = 4;
printf("\n*********PolyA********\n");
ShowList(&HeadA);
printf("\n*********PolyB********\n");
ShowList(&HeadB);
LinkPolyNode* pPloyC;
pPloyC = MergePoly(&HeadA, &HeadB);
printf("\n*********PolyC********\n");
ShowList(pPloyC);
getchar();
return 0;
}
学生成绩管理系统
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct student {
int num;
float score;
}node;
//单班人数上限是50
#define LIST_SIZE 50
#define TRUE 1
#define FALSE 0
//定义顺序表的结构
typedef struct {
node data[LIST_SIZE];
int last;//表明最后一个节点的位置
}SeqList;
//获取班级人数
int GetSize(SeqList* pList) {
return pList->last;
}
//遍历输出全体学生信息
void ShowSeqList(SeqList* pList) {
for (int i = 0;i < pList->last;i++) {
printf("学生的学号是%d,成绩是%f\n", pList->data[i].num, pList->data[i].score);
}
}
//初始化
SeqList* InitSeq() {
SeqList* pList = NULL;
pList = (SeqList*)malloc(sizeof(SeqList));
if (pList != NULL)
pList->last = 0;//初始化成功，且长度为0
return pList;
//因为在服务器分配中，连续分配大量空间，往往不容易成功
//所以我们经常在内部就进行判断
}
//插入元素
int InesrtStuSeq(SeqList* pList, node *pNode, int k) {
int j;
/*if (pList->last >= LIST_SIZE - 1)
return FALSE;*/
//移到函数之外，有业务人员维护插入
//如果这个函数被反复调用的开销很大，那么我们会放弃内部校验
//但是，如果这是一个对安全要求很高程序，内部校验依然需要
//如果去掉了内部校验，在实际的公司开发中，会有Team leader做codereview
//在本例中，我们假定k传入就是有效位置。
//永远不要相信调用者传入的数据，但是，在具体开发中，还是具体情况具体分析
for (j = pList->last;j >= k;j--) {
pList->data[j + 1].num = pList->data[j].num;
pList->data[j + 1].score = pList->data[j].score;
}
pList->data[k].num = pNode->num;
pList->data[k].score = pNode->score;
pList->last++;
return TRUE;
}
int DelSeqList(SeqList* pList, int k) {
/*if (k <= 0 || k > pList->last)
return FALSE;*/
if (pList->last == 0)
return FALSE;
for (int j = k;j <= pList->last;j++) {
pList->data[j].num = pList->data[j + 1].num;
pList->data[j].score = pList->data[j + 1].score;
}
pList->last--;
return TRUE;
}
//实现按学号查找的
void DisplayStu(SeqList* pList, int stuNo) {
for (int i = 0;i < pList->last;i++) {
if (pList->data[i].num == stuNo) {
printf("该学生的成绩是%f\n", pList->data[i].score);
return;
}
}
printf("该学生不存在\n");
}
int main222(void) {
SeqList* stuList = InitSeq();
node stu[2];
stu[0].num = 1;
stu[0].score = 99;
stu[1].num = 2;
stu[1].score = 100;
if (stuList) {
for (int i = 0;i < 2;i++) {
InesrtStuSeq(stuList, &stu[i], i);
}
}
ShowSeqList(stuList);
//DelSeqList(stuList, 1);
//ShowSeqList(stuList);
printf("\n************\n");
DisplayStu(stuList, 1);
getchar();
return 0;
}
************************************************************************************************************************************************
SeqStack.h
#pragma once
//假定处理的是一位数，没有括号
#define stackSize 100
#define TRUE 1
#define FALSE 0
typedef int BOOL;
typedef int ElemType;//元素类型
typedef struct {
ElemType stack[stackSize];
int top;//栈顶指针
}SeqStack;
///栈的初始化
BOOL init(SeqStack* pStack);
///栈的判空
BOOL isEmpty(SeqStack* pStack);
///压栈
///返回值为1表示成功，-1表示错误，
///pStack表示顺序栈，x表示压入元素
BOOL pushStack(SeqStack* pStack, ElemType x);
///出栈
ElemType popStack(SeqStack* pStack);
///获取栈顶元素
///如果栈为空，返回取值不成功，否则直接取出栈顶元素供用户使用
BOOL GetSeqStack(SeqStack* s, ElemType* data);
//判断是否是运算符,如果是运算符，返回true，否则返回false
BOOL Is_Operator(char oper);
//判断优先级：×/ 为2，+，-为1，
int Priority(char oper);
//计算数值:不考虑浮点数，也不考虑除数为0
int two_res(int oper, int opand1, int opand2);
SeqStack
#include <stdio.h>
#define stackSize 100
#define TRUE 1
#define FALSE 0
typedef int BOOL;
typedef int ElemType;//元素类型
typedef struct {
ElemType stack[stackSize];
int top;//栈顶指针
}SeqStack;
///栈的初始化
BOOL init(SeqStack* pStack) {
pStack->top = 0;
return 1;
}
///栈的判空
BOOL isEmpty(SeqStack* pStack) {
return (pStack->top == 0);
}
///压栈
///返回值为1表示成功，-1表示错误，
///pStack表示顺序栈，x表示压入元素
BOOL pushStack(SeqStack* pStack, ElemType x) {
if (pStack->top == stackSize)
{
printf("空间溢出\n");
return FALSE;
}
pStack->top = pStack->top + 1;
pStack->stack[pStack->top] = x;
return TRUE;
}
///出栈
ElemType popStack(SeqStack* pStack) {
ElemType tmp;
if (pStack->top == 0) {
printf("当前是空栈\n");
return -1;
}
tmp = pStack->stack[pStack->top];
pStack->top = pStack->top - 1;//逻辑上的出栈
return tmp;
}
void myConv(SeqStack* pStack, int n) {
int e;//每一个元素
while (n) {
pushStack(pStack, n % 8);
n = n / 8;
}
while (!isEmpty(pStack)) {
e = popStack(pStack);
printf("%d", e);
}
}
///获取栈顶元素
///如果栈为空，返回取值不成功，否则直接取出栈顶元素供用户使用
BOOL GetSeqStack(SeqStack* s, ElemType* data) {
if (s->top == 0)
return FALSE;
*data = s->stack[s->top];
return TRUE;
}
int main1(void) {
SeqStack s;
init(&s);
printf("十进制数1348，转为的8进制是：\n");
myConv(&s, 1348);
getchar();
return 0;
}
/*
首先我们必须知道，一旦设立了栈，那么就请按照栈的特点进行操作
“先进后出”
我们都知道，只要知道下标就可以获取数组的元素
stack[0],stack[1],stack[2].....
我们没有能力再直接操作上面的元素
我们只能取栈顶，因为只有这一个函数；其他，要么出栈，要么进栈
这就是数据结构思考问题方式：我们设立一个逻辑结构，就用这个结构控制
程序逻辑
*/
LinkStack
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node {
datatype data;
struct node * pNext;
}LinkStack;
//入栈
LinkStack* PushLkStack(LinkStack* top, datatype x) {
LinkStack* p;
p = (LinkStack*)malloc(sizeof(LinkStack));
p->data = x;
p->pNext = top; //类似于首先将p链入链表
top = p;//top上移到当前栈顶，指向刚刚加入的p节点，此时top永远指向栈顶的第一个元素
return top;
}
//出栈
LinkStack* PopLkStack(LinkStack* top, datatype* pData) {
LinkStack* p;
//一旦我们出栈，那么我们认为这个元素就不应当维护链表指向的关系了
if (top != NULL) {
*pData = top->data;
p = top;//此时我们将当前的栈顶元素的位置，保存下来了，接下栈顶元素即将脱离
top = p->pNext;
free(p);
}
return top;
}
int main2(void) {
LinkStack* pTop=NULL;
pTop = PushLkStack(pTop, 1);
pTop = PushLkStack(pTop, 1);
getchar();
return 0;
}
SeqQueue
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 100
typedef int datatype;
#define TRUE 1
#define FALSE 0
typedef int BOOL;
typedef struct queue {
datatype data[QUEUE_SIZE];
int front, rear;
}SeqQueue;
void Init_SqQueue(SeqQueue* sq) {
sq->front = QUEUE_SIZE - 1;
sq->rear = QUEUE_SIZE - 1;
}
BOOL IsEmpty_SqQueue(SeqQueue *sq) {
if (sq->rear == sq->front)
return TRUE;
return FALSE;
}
//返回的应当是数组的角标
int Get_SqQueue(SeqQueue* sq) {
if (!IsEmpty_SqQueue(sq)) {
return (sq->front + 1) % QUEUE_SIZE;
}
return -1;
}
BOOL EnSqQueue(SeqQueue* sq, datatype x) {
if (sq->front == (sq->rear + 1) % QUEUE_SIZE)
return FALSE;
sq->rear = (sq->rear + 1) % QUEUE_SIZE;//队尾指针后移
sq->data[sq->rear] = x;//元素入队
return TRUE;
}
///出队如果队空，返回的是元素的角标记为-1；否则，返回数组角标
int DeSqQueue(SeqQueue* sq) {
if (!IsEmpty_SqQueue(sq)) {
sq->front = (sq->front + 1) % QUEUE_SIZE;
return sq->front;
}
return -1;
}
int mainAA(void) {
return 0;
}
LkQueue
#include <stdio.h>
#include <stdlib.h>
typedef int BOOL;
#define TRUE 1
#define FALSE 0
typedef int datatype;
typedef struct node {
datatype data;
struct node * next;
}LinkListNode;
typedef struct {
LinkListNode* front, *rear;
}LinkQueue;
void Init_LkQueue(LinkQueue* lq) {
lq->front = (LinkListNode*)malloc(sizeof(LinkListNode));
lq->front->next = NULL;
lq->rear = lq->front;
}
BOOL IsEmpty_LkQueue(LinkQueue* lq) {
if (lq->front == lq->rear)
return TRUE;
else
return FALSE;
}
BOOL Get_LkQueue(LinkQueue* lq, datatype *x) {
if (IsEmpty_LkQueue(lq))
return FALSE;
x = &(lq->front->next->data);//因为front始终指向头节点，而队列是先进先出，front的next一定是队头元素
return TRUE;
}
void Insert_LkQueue(LinkQueue* lq, datatype x) {
lq->rear->next = (LinkListNode*)malloc(sizeof(LinkListNode));
//新节点入队尾部
lq->rear = lq->rear->next;
lq->rear->data = x;
lq->rear->next = NULL;
}
LinkListNode* Del_LkQueue(LinkQueue* lq) {
LinkListNode* s;
if (!IsEmpty_LkQueue(lq)) {
s = lq->front->next;
if (s->next == NULL)//队中只有一个节点
lq->rear = lq->front;//队列置空
else
lq->front->next = s->next;//因为lq是我们自己设计记录位置的指针，所以要让指向下一个队头元素
return s;
}
return NULL;
}
void Destroy_LkQueue(LinkQueue* lq) {
//即使销毁队列，也要保持住结构
LinkListNode* s;
while (!IsEmpty_LkQueue(lq)) {
s = Del_LkQueue(lq);
free(s);
}
free(lq->front);//释放头节点
lq->front = NULL;
lq->front = NULL;
}
int main222(void) {
LinkQueue node;
LinkQueue *lpPtr = &node;
LinkListNode* sPtr;
datatype value;
Init_LkQueue(lpPtr);
//0，1，1，0入队
Insert_LkQueue(lpPtr, 0);
Insert_LkQueue(lpPtr, 1);
Insert_LkQueue(lpPtr, 1);
Insert_LkQueue(lpPtr, 0);
int N = 42;
for (int i = 0;i < 42;i++) {
//队头元素出队
sPtr = Del_LkQueue(lpPtr);
if(sPtr!=NULL){
//队头的两个元素，n-1 n 生成新的系数
value = sPtr->data + lpPtr->front->next->data;
if (sPtr->data != 0) {
printf("%d ", sPtr->data);
}
Insert_LkQueue(lpPtr, value);
}
if (lpPtr->front->next->data == 0) {
//队头元素作为分隔符
Insert_LkQueue(lpPtr, 0);
printf("\n");
}
}
getchar();
return 0;
}
八皇后问题
#include <stdio.h>
#define TRUE 1
#define FALSE 0
int a[9], b[17], c[17],s[9];//用来处理第i行上第j个元素的冲突问题
void eightQueen() {
int i, j;
//因为这样对角线有15条，且i+j从2开始
//初始化好全部的冲突，现在都可以放皇后
for (i = 2;i <= 16;i++) {
if (i >= 2 && i <= 9) {
a[i - 1] = TRUE;
}
b[i] = TRUE;
c[i] = TRUE;
}
i = 1;
j = 1;
//开始使用回溯法进行处理
while (i<=8) {
while (j <= 8) {
//在第i行寻找潜在的第j列
if (a[j] && b[i + j] && c[i - j + 9])
break;
j++;
}
if (j <= 8) {
//找到安全位置
a[j] = FALSE;
b[i + j] = FALSE;
c[i- j + 9] = FALSE;
s[i] = j;
i++;//前进到下一行
j = 1;
}
else {
//当前的第i行已经不能再放入元素了，那么回溯到上一行再寻找
i--;
j = s[i];
a[j] = TRUE;
b[i + j] = TRUE;
c[i - j + 9] = TRUE;
j++;//前进到下一列
}
}
}
int main333333() {
eightQueen();
for (int i = 1;i < 9;i++) {
printf("%d,%d\n", i, s[i]);
}
getchar();
return 0;
}
八皇后递归解法
#include <stdio.h>
//使用回溯，每一行放一个，直到不冲突
int c[20], n = 8, cnt = 0;
//找到一个解就是输出，c[]里面存的是可以放的皇后的列
void print() {
for (int i = 0;i < n;++i) {
for (int j = 0;j < n;++j) {
if (j == c[i])
printf("1 "); //1表示皇后占位
else
printf("0 "); //0表示空的位置
}
printf("\n");
}
printf("\n");
}
//用r表示搜索到了第r行
void search(int r) {
if (r == n) {
//说明已经放置成功
print();
++cnt;
return;
}
//什么时候才能进入下一级递归呢？
//只有满足了当前皇后和前面所有的皇后都不互相攻击的时候，才能进入下一级递归
for (int i = 0;i < n;++i) {
c[r] = i;
int ok = 1;
for (int j = 0;j < r;++j) {
if (c[r] == c[j] || r - j == c[r] - c[j] || r - j == c[j] - c[r]) {
ok = 0;
break;
}
}
if (ok)
search(r + 1);
}
}
int mainQQQ(void) {
search(0);
printf("八皇后一共有%d种解法", cnt);
getchar();
return 0;
}
八皇后问题的全解
#include <stdio.h>
#define TRUE 1
#define FALSE 0
int a[9], b[17], c[17], s[9];//用来处理第i行上第j个元素的冲突问题
void print() {
printf("\n");
for (int i = 1;i < 9;i++) {
printf("%d,%d\n", i, s[i]);
}
}
void move(int i,int j) {
a[j] = TRUE;
b[i + j] = TRUE;
c[i - j + 9] = TRUE;
}
void eightQueenEx() {
int i, j;
//因为这样对角线有15条，且i+j从2开始
//初始化好全部的冲突，现在都可以放皇后
for (i = 2;i <= 16;i++) {
if (i >= 2 && i <= 9) {
a[i - 1] = TRUE;
}
b[i] = TRUE;
c[i] = TRUE;
}
i = 1;
j = 1;
//开始使用回溯法进行处理
while (i <= 8) {
while (j <= 8) {
//在第i行寻找潜在的第j列
if (a[j] && b[i + j] && c[i - j + 9])
break;
j++;
}
if (j <= 8) {
//找到安全位置
a[j] = FALSE;
b[i + j] = FALSE;
c[i - j + 9] = FALSE;
s[i] = j;
if (i == 8) {
//找到一个解
print();
//移除i，j位置上的皇后
move(i, j);
//回溯退栈
i = i - 1;
j = s[i];
move(i, j);
j++;//从上一个的第j+1列再寻找
}
else{
i++;//前进到下一行
j = 1;
}
}
else {
//当前的第i行已经不能再放入元素了，那么回溯到上一行再寻找
i--;
if (i >= 1) {
//如果栈不空，那么移除皇后
j = s[i];
move(i, j);
j++;//前进到下一列
}
}
}
}
int main4444() {
eightQueenEx();
getchar();
return 0;
}
/*
求的一个解，我们就打印，但是，不停止，
我们让我们的皇后移除，返回到上一行的下一个j列，看看能不能找到
如果上一行的j列全部遍历结束，那么再回溯到上上一行，直到到第一行为止
*/
递归的原理
#include <stdio.h>
int fun(int n) {
if (n > 1)
return n*fun(n - 1);
if (n == 1)
return 1;
}
int funG(int n) {
int temp = 1;
for (int i = 1;i <= n;i++) {
temp *= i;
}
return temp;
}
int main55555(void) {
printf("5*4*3*2=%d", funG(5));
getchar();
return 0;
}
函数栈帧调试剖析
#include <stdio.h>
//1+2+3+4+5....
//递归是我们程序设计入门一个槛
//我们可以使用重复的力量，来解决这个问题
int sum = 0;
int FunGaosi(int value) {
if (value == 1)
return 1;
sum = value + FunGaosi(value - 1);
return sum;
}
/*int go() {
}
int gogo() {
go();
}
int fun() {
gogo();
}*/
int main3(void) {
printf("%d", FunGaosi(4));
getchar();
return 0;
}
//call stack最基本的作用：
/*
就是告诉程序员，你现在停留的指令在什么位置，当你的函数返回时
你将在哪一个函数的指令继续推进你的程序。
只有我们清楚的知道你的程序代码是如何推进，你才知道你的程序怎么运行的。
bug，是程序没有按照我们预定的逻辑进行推进，那么我们就必须知道
在哪里运行的路径不正确。
*/
后缀表达式_逆波兰表达式运算
#include <stdio.h>
#include "SeqStack.h"
int main222(void) {
char expression[] = "1562/-3*+#";
int position = 0;
int operand1 = 0;
int operand2 = 0;
int evaluate = 0;//没有所谓的操作符
SeqStack sStack;
init(&sStack);
while (expression[position]!='#')
{
if (Is_Operator(expression[position])) {
operand1 = popStack(&sStack);
operand2 = popStack(&sStack);
pushStack(&sStack, two_res(expression[position], operand1, operand2));
}
else {
pushStack(&sStack, expression[position] - 48);
}
position++;
}
evaluate = popStack(&sStack);
printf("%d ", evaluate);
getchar();
return 0;
}
迷宫的递归解法
#include <stdio.h>
typedef int BOOL;
#define TRUE 1
#define FALSE 0
#define ROWS 7
#define COLUMNS 10
int MyMaze[][11] =
{ { 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,0,1,1,1,0,0,1 },
{ 1,0,0,0,0,0,1,0,0,1,1 },
{ 1,0,1,1,1,0,0,0,1,1,1 },
{ 1,0,0,0,1,0,1,1,0,1,1 },
{ 1,1,0,0,1,0,1,0,0,0,1 },
{ 1,1,1,0,0,0,0,0,1,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 } };
//判断是否是障碍
BOOL Valid(int row, int col) {
BOOL flag = FALSE;
if (row >= 1 && row < ROWS && col >= 1 && col < COLUMNS && MyMaze[row][col] == 0)
flag = TRUE;
return flag;
}
//只要我们相信我们设计的递归函数，严格按照我们设计的指令序列
//依次，运行，那么这个函数本身就是蕴含答案的
//函数的栈帧重复运行将我们设计的如for，while循环的过程隐藏
//所以，直觉上会觉得递归抽象。
BOOL exitMaze(int row, int col) {
BOOL done = FALSE;
if (Valid(row, col)) {
//走过的标记，我们给2
MyMaze[row][col] = 2;
//抵达出口
if (row == (ROWS - 1) && col == (COLUMNS - 1)) {
done = TRUE;
}
else {
//未达到终点，我们就按照E-》S—》W—》N
done = exitMaze(row, col + 1);
if (!done)
done = exitMaze(row + 1, col);
if (!done)
done = exitMaze(row, col - 1);
if (!done)
done = exitMaze(row - 1,col);
}
// 设一个可以找到的表示，我们将数字9表示可以通过的路径
if (done)
MyMaze[row][col] = 9;
}
return done;
}
int main(void) {
BOOL done = exitMaze(1, 1);
if (done) {
for (int i = 0;i < ROWS;i++) {
for (int j = 0;j < COLUMNS;j++) {
printf("%d", MyMaze[i][j]);
}
printf("\n");
}
}
else {
printf("没有找到路径");
}
getchar();
return 0;
}
迷宫问题的非递归解法
#include <stdio.h>
#include <stdlib.h>
typedef int BOOL;
#define TRUE 1
#define FALSE 0
typedef struct {
int x; //表示节点的横坐标
int y;//表示节点的纵坐标
int d;//表示节点的方向
}DataType;
typedef struct linknode {
DataType data;
struct linknode* pNext;
}LinkStack;
LinkStack* InitLkStack(void) {
LinkStack* p = NULL;
p = (LinkStack*)malloc(sizeof(LinkStack));
if (p != NULL)
p->pNext = NULL;
return p;
}//建立一个带头节点的链表作为链栈
BOOL IsEmptyLkMazeStack(LinkStack* top) {
return (top->pNext == NULL);
}
LinkStack* PushLkStack(LinkStack* top, DataType elem) {
LinkStack* p;
p = (LinkStack*)malloc(sizeof(LinkStack));
p->data.x = elem.x;
p->data.y = elem.y;
p->data.d = elem.d;
p->pNext = top; //p节点尾插入lkStack
top = p;//top栈顶指针上移
return top;
}
//出栈
LinkStack* PopLkStack(LinkStack* top, DataType *pData) {
LinkStack* p;
if (top != NULL) {
*pData = top->data;
p = top;
top = p->pNext;
free(p);
}
return top;
}
int main1add(void) {
//迷宫
int maze[][11] = {
{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,0,1,1,1,0,0,1 },
{1,0,0,0,0,0,1,0,0,1,1 },
{1,0,1,1,1,0,0,0,1,1,1 },
{1,0,0,0,1,0,1,1,0,1,1 },
{1,1,0,0,1,0,1,0,0,0,1 },
{1,1,1,0,0,0,0,0,1,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 },
};
//路径移动辅助数组
int direction[4][2] = {
{0,1},
{1,0},
{0,-1},
{-1,0}
};
LinkStack* pTop = NULL;
pTop = InitLkStack();//用来保存路径
DataType element;
element.x = 1;
element.y = 1;
element.d = -1;//保证下一个节点推进是起点方向是0
pTop = PushLkStack(pTop, element);//迷宫入口入栈
int i, j, k;//当前的横坐标，纵坐标以及方向
int g, h;//潜在的下一个方向
while (!IsEmptyLkMazeStack(pTop)) {
//获得当前节点的坐标
i = pTop->data.x;
j = pTop->data.y;
k = pTop->data.d+1;
while (k <= 3) {
g = i + direction[k][0];
h = j + direction[k][1];
if (g == 6 && h == 9 && maze[g][h] == 0) {
printf("找到了\n");
printf("节点位置是:%d,%d\n", i, j);
while (!IsEmptyLkMazeStack(pTop)) {
pTop = PopLkStack(pTop, &element);
printf("节点位置是:%d,%d\n", pTop->data.x, pTop->data.y);
}
getchar();
return;
}
//判断是否可以前进到下一个节点
if (maze[g][h] == 0) {
maze[g][h] = 2;//不要走回头路
//要将节点路径保留，那么就要入栈
element.x = g;
element.y = h;
element.d = -1;
pTop = PushLkStack(pTop, element);
break;
}
k = k + 1;
}
//回溯：k大于3说明，所有的当前节点的4个方向都找过，没有通路，所以要退栈，当上一个节点上
if (k > 3) {
pTop = PopLkStack(pTop, &element);//此时element接住上一个在栈中的节点
}
}
printf("没有找到通路\n");
return 0;
}
使用队列设计实现杨辉三角形
//思想：看看我们需要设计的业务中，有那些可以用我们已经学过的数据结构
//进行刻画，将这些业务问题，变成数据结构的组织问题
#include <stdio.h>
int mainA(void) {
int n = 50;
int queue[42] = { 0,1,1,0 };//0是换行
int front = 1,rear = 4;//首先将杨辉三角的第一行输入
for (int i = 0;i < n;i++) {
queue[rear] = queue[front - 1] + queue[front];
//将队头的两个元素和插入rear位置
printf("%d ", queue[rear]);
rear++;//准备好新元素的位置
if (queue[front] == 0) {
//添加新的分割
queue[rear] = 0;
rear++;
printf("\n");
}
front++;
}
getchar();
return 0;
}
//front是即将要处理的数据，rear是添加的数据。
中缀表达式求值
#include <stdio.h>
#include <stdio.h>
#include "SeqStack.h"
///栈的初始化
BOOL init(SeqStack* pStack) {
pStack->top = 0;
return 1;
}
///栈的判空
BOOL isEmpty(SeqStack* pStack) {
return (pStack->top == 0);
}
///压栈
///返回值为1表示成功，-1表示错误，
///pStack表示顺序栈，x表示压入元素
BOOL pushStack(SeqStack* pStack, ElemType x) {
if (pStack->top == stackSize)
{
printf("空间溢出\n");
return FALSE;
}
pStack->top = pStack->top + 1;
pStack->stack[pStack->top] = x;
return TRUE;
}
///出栈
ElemType popStack(SeqStack* pStack) {
ElemType tmp;
if (pStack->top == 0) {
printf("当前是空栈\n");
return -1;
}
tmp = pStack->stack[pStack->top];
pStack->top = pStack->top - 1;//逻辑上的出栈
return tmp;
}
///获取栈顶元素
///如果栈为空，返回取值不成功，否则直接取出栈顶元素供用户使用
BOOL GetSeqStack(SeqStack* s, ElemType* data) {
if (s->top == 0)
return FALSE;
*data = s->stack[s->top];
return TRUE;
}
//判断是否是运算符,如果是运算符，返回true，否则返回false
BOOL Is_Operator(char oper) {
switch (oper)
{
case '+':
case'-':
case '*':
case '/':
return TRUE;
default:
return FALSE;
}
}
//判断优先级：×/ 为2，+，-为1，
int Priority(char oper) {
switch (oper)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
//计算数值:不考虑浮点数，也不考虑除数为0
int two_res(int oper, int opand1, int opand2) {
switch (oper)
{
case '+': return (opand2 + opand1);
case '-':return (opand2 - opand1);
case '*':return (opand2 * opand1);
case '/':return (opand2 / opand1);
default:
return 0;
}
}
int main1111(void) {
char expression[] = "8*9-4/2";
int position = 0;//扫描的字符串
int op = 0;//运算符
int operand1 = 0;
int operand2 = 0;
int evaluate = 0;//运算结果
SeqStack sOperator;//操作符栈
init(&sOperator);
SeqStack sOperand;
init(&sOperand);// 操作数栈
//第一步扫描字符串
while (expression[position] != '\0' && expression[position] != '\n') {
if (Is_Operator(expression[position])) {
if (!isEmpty(&sOperator)) {
while (Priority(expression[position])<=
Priority(sOperator.stack[sOperator.top])
&&!isEmpty(&sOperator)) {
operand1 = popStack(&sOperand);
operand2 = popStack(&sOperand);
op = popStack(&sOperator);
pushStack(&sOperand, two_res(op, operand1, operand2));
}
}
pushStack(&sOperator, expression[position]);
}
else {
pushStack(&sOperand, expression[position] - 48);//将Ascii码转成数值
}
position++;
}
//清空操作符栈
while (!isEmpty(&sOperator)) {
op = popStack(&sOperator);
operand1 = popStack(&sOperand);
operand2 = popStack(&sOperand);
pushStack(&sOperand, two_res(op,operand1, operand2));
}
printf("%d", popStack(&sOperand));
getchar();
return 0;
}
中缀转后缀
#include <stdio.h>
#include "SeqStack.h"
//对扩展开放，对修改封闭
//修改一下运算符
int Is_OperatorEx(char op) {
switch (op)
{
case '(':
case ')':
case '+':
case '-':
case '*':
case '/':
return 1;
default:
return 0;
}
}
int PriorityEx(char op) {
switch (op)
{
case '(':return 1;
case '+':
case '-':return 2;
case '*':
case '/':
return 3;
default:
return 0;
}
}
int main21(void) {
char inorder[50] = "1+2-3#"; //"1+((2+3)*4)-5#";//声明中缀（中序）表达式的字符串
char postorder[50];
int op = 0;//运算符
int in_position;//中序表达式的角标
int po_position;//后续表达式的角标
int i;
in_position = 0;
po_position = 0;
for (i = 0;i < 50;i++)
postorder[i] = 0;
SeqStack sOper;
init(&sOper);
while (inorder[in_position]!='#')
{
//todo利用栈进行优先级，去括号的过程
if (Is_OperatorEx(inorder[in_position])) {
if (isEmpty(&sOper) || inorder[in_position] == '(') {
pushStack(&sOper, inorder[in_position]);
}
else {
if (inorder[in_position] == ')') {
//匹配左括号
while (sOper.stack[sOper.top] != '(') {
op = popStack(&sOper);
postorder[po_position++] = op;
}
if (sOper.stack[sOper.top] == '(')
{
popStack(&sOper);
}
}//ctrl+]
else
{
while (PriorityEx(inorder[in_position]) <= PriorityEx(sOper.stack[sOper.top]) && !isEmpty(&sOper)) {
op = popStack(&sOper);
postorder[po_position++] = op;
}
pushStack(&sOper, inorder[in_position]);
}
}
}
else {
postorder[po_position++] = inorder[in_position];
}
in_position++;
}
while (!isEmpty(&sOper)) {
op = popStack(&sOper);
postorder[po_position++] = op;
}
for (int i = 0;i < 50;i++) {
if (postorder[i] == 0)
break;
printf("%c", postorder[i]);
}
getchar();
return 0;
}
************************************************************************************************************************************************
顺序存储的二叉树
#include <stdio.h>
//用顺序数组的形式，存储建立一个二叉搜索树
/*
1，我们根据完全二叉树的编号，我们做数组角标1存储输入的第一个元素
2,得到根元素之后，我们开始建立这样的二叉树
若元素的值大于根节点，则将元素往根节点的右子节点移动，若此节点为空
那么，存入，否则，直到找到这个空位置
若元素的值小于根节点，按么则将元素往根节点的左子节点移动，直到找到
空位存储之
注意，如何寻找节点的左右子节点呢？
用左节点为父节点×2，右子节点为父节点×2+1，
根据这个关系，找到角标，存储之。
*/
void create_btree(int b_tree[], int nodelist[], int len) {
int i;
int level;//树的层级，我们用这个level去推进计算将要插入的数字的角标，
//直白的说，就是确定它的树中位置
b_tree[1] = nodelist[1];
for (i = 2;i < len;i++) {
level = 1;//每一个新元素在二叉搜索树的位置都是通过根节点进行搜索
while (b_tree[level] != 0) {//0表示当前的子树位置是空的
if (nodelist[i] < b_tree[level]) {
level = level * 2;
}
else {
level = level * 2 + 1;
}
}
//出了循环，说明新元素在二叉搜索树中的位置就定下了
b_tree[level] = nodelist[i];
}
}
//若一棵树的左子树所有的值都比根节点的值小，右子树的值都比根大
//这样的二叉树，我们成为二叉查找树（Binary search tree)
int main1(void){
int b_tree[16] = { 0 };
int nodelist[16] = { 0, 6,3,8,
5,2,9,4,7,
10,0,0,0,
0,0,0};//根据角标的定义，我们的数组形式不用0开始做编号
create_btree(b_tree, nodelist, 16);
for (int i = 1;i < 16;i++) {
printf("%d,[%d] \n", i, b_tree[i]);
}
getchar();
return 0;
}
二叉链表的存储方式
#include <stdio.h>
#include <stdlib.h>
typedef int datatype ;
typedef struct node {
datatype data;
struct node *left, *right;
}BitTree;
//辅助队列Q，这是用来存关系的
BitTree* Q[16];//这是一个指针数组，它将缓存节点的地址，因为这个地址将以
//left域，或者right域进入二叉链表，它本身不维护i，2i，2i+1的关系
//他的关系通过front，rear来维护
//按照直观的建立，我们首先想到的是层次法
//我们根据层次，来逐一将二叉树建立
//输入的数组是按照完全二叉树的编号规则设立，即
//数组角标反映了节点位置关系（存联系）
//逐个扫描数组，直到所有的节点都存取完毕之后，就结束
//约定，0表示数组当前元素为空，最后一个节点标志是-999
BitTree* CreateBinTree(int arr[]) {
int i = 1;
//只要我们没有扫描完元素，那么这个二叉链表就没有完成
//只要扫描，我们就malloc一个节点，然后把这个节点存入left域或者right域
int front = 1, rear = 0;
BitTree* root = NULL;
BitTree* s;//暂存节点
while (arr[i]!=-999) {
s = NULL;
if (arr[i] != 0) {//意味着这个不是空节点，那么我们就要分配空间
s = (BitTree*)malloc(sizeof(BitTree));
s->data = arr[i];//存数值
s->left = NULL;
s->right = NULL;
}
//要让我们新节点入队，进入缓存，等待分配双亲的left域和right域
Q[++rear] = s;
if (rear == 1)
{
root = s;
}
else {
if (s != NULL && Q[front]) {
if (rear % 2 == 0) {
Q[front]->left = s;
}
else {
Q[front]->right = s;
}
}
if (rear % 2 == 1)
front++;
}
i++;
}
return root;
}
//树遍历问题：非线性结构的输出问题：前序，中序，后序
void inorder(BitTree *t) {
if (t) {
inorder(t->left);
printf("%d ", t->data);
inorder(t->right);
}
}
void preorder(BitTree* t) {
if (t) {
//根左右
printf("%d ", t->data);
preorder(t->left);
preorder(t->right);
}
}
void postorder(BitTree* t) {
if (t) {
//左右根
postorder(t->left);
postorder(t->right);
printf("%d ", t->data);
}
}
int main(void) {
int arr[17] = {0,6,3,8,
2,5,7,9,
0,0,4,0,
0,0,0,10,
-999
};
BitTree *root = CreateBinTree(arr);
inorder(root);
getchar();
return 0;
}
二叉树非递归遍历的经典解法 BinTreeNonRecvImp
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node {
datatype data;
struct node *left, *right;
}BitTree;
//*************************Begin*************
//添加辅助栈的结构：主要是用来保存树的节点
//简言之，这个就是用来存树节点的栈
typedef BitTree BitTreeNode;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
//-——————————修订V0.01——changed by dingst
//BitTreeNode data;那么一定是侵入式的，为什么=》逐个深拷贝每一个分量
//只要是BitTreeNode* Addr;在32位中，这个值永远是4字节
//保存的都是传入的源节点的地址值的一个副本（c/C++语言，都是指拷贝形式）
typedef struct linknode {
BitTreeNode* _NodeAddrCopy;
struct linknode* pNext;
}LinkStack;
LinkStack* InitLkStack(void) {
LinkStack* p = NULL;
p = (LinkStack*)malloc(sizeof(LinkStack));
if (p != NULL)
p->pNext = NULL;
return p;
}//建立一个带头节点的链表作为链栈
BOOL IsEmptyLkMazeStack(LinkStack* top) {
return (top->pNext == NULL);
}
LinkStack* PushLkStack(LinkStack* top, BitTreeNode* elem) {
LinkStack* p = NULL;
//深拷贝的bug修订，如果传入的是空指针，那么不能访问,修订人丁宋涛
//elem就是将当前树节点的地址值考一份：比如0x00d500578，我们现在
//栈就是把这个0x00d500578拷贝一份下来，放到我们_NodeAddrCopy
//及时栈节点出栈，此时也是我么你的_NodeAddrCopy这个变量被释放
//与原先的树节点没有关系，不会影响
//elem是这个函数的形参，它将调用者的实参拷贝一份放入到elem中
//所以elem就是这个0x00d500578
//我们用p->_NodeAddrCopy = elem;的操作
//就把0x00d500578保存下来了，此时他就是原节点地址的一个副本
if (elem != NULL)
{
p = (LinkStack*)malloc(sizeof(LinkStack));
//todo:我们用新建节点，对传入的二叉树节点做一个深拷贝
//changed by dingst，我们要做非侵入式的设计
/*p->data.data = elem->data;
p->data.left = elem->left;
p->data.right = elem->right;*/
p->_NodeAddrCopy = elem;
p->pNext = top; //p节点尾插入lkStack
top = p;//top栈顶指针上移
}
//我们思考，既然我们允许空指针进入到我们的栈结构，那么我们如何修订
//我们的出栈？
//top为空以为着？
//意味着是否和栈空条件冲突了？
//如果我们让我们的NULL进入栈空间，那么出栈也会造成空指针
//这意味着当前的节点不动
return top;
}
//出栈:pData是传入的一个“临时”空间用来接收出栈的节点信息。
LinkStack* PopLkStack(LinkStack* top, BitTreeNode *pData) {
LinkStack* p;
if (top != NULL) {
//*pData = top->data;
//----changed by dingst
/*pData->data = top->data.data;
pData->left = top->data.left;
pData->right = top->data.right;*/
pData = top->_NodeAddrCopy;
//pData实际上深拷贝了一份节点信息，所以释放栈中节点，不会影响
//节点数据
p = top;
top = p->pNext;
free(p);
}
return top;
}
//*************************End***************
//辅助队列Q，这是用来存关系的
BitTree* Q[16];//这是一个指针数组，它将缓存节点的地址，因为这个地址将以
//left域，或者right域进入二叉链表，它本身不维护i，2i，2i+1的关系
//他的关系通过front，rear来维护
//按照直观的建立，我们首先想到的是层次法
//我们根据层次，来逐一将二叉树建立
//输入的数组是按照完全二叉树的编号规则设立，即
//数组角标反映了节点位置关系（存联系）
//逐个扫描数组，直到所有的节点都存取完毕之后，就结束
//约定，0表示数组当前元素为空，最后一个节点标志是-999
BitTree* CreateBinTree(int arr[]) {
int i = 1;
//只要我们没有扫描完元素，那么这个二叉链表就没有完成
//只要扫描，我们就malloc一个节点，然后把这个节点存入left域或者right域
int front = 1, rear = 0;
BitTree* root = NULL;
BitTree* s;//暂存节点
while (arr[i] != -999) {
s = NULL;
if (arr[i] != 0) {//意味着这个不是空节点，那么我们就要分配空间
s = (BitTree*)malloc(sizeof(BitTree));
s->data = arr[i];//存数值
s->left = NULL;
s->right = NULL;
}
//要让我们新节点入队，进入缓存，等待分配双亲的left域和right域
Q[++rear] = s;
if (rear == 1)
{
root = s;
}
else {
if (s != NULL && Q[front]) {
if (rear % 2 == 0) {
Q[front]->left = s;
}
else {
Q[front]->right = s;
}
}
if (rear % 2 == 1)
front++;
}
i++;
}
return root;
}
//树遍历问题：非线性结构的输出问题：前序，中序，后序
void preorder(BitTree* t) {
if (t) {
//根左右
printf("%d ", t->data);
preorder(t->left);
preorder(t->right);
}
}
void NonRecrvPreOrder(BitTree* root) {
LinkStack* pTop = NULL;
//BitTreeNode TempNode;//用来接栈中对应的二叉树节点的
//-----change by dingst
BitTreeNode* pNode; //我要让pNode推进树遍历，而且pNode就是
//真实地址的副本
pTop = InitLkStack();
//pTop = PushLkStack(pTop, root);
//---change by dingst
pNode = root;
pTop = PushLkStack(pTop, pNode);
while (!IsEmptyLkMazeStack(pTop)) {
pNode = pTop->_NodeAddrCopy;//178行的这个赋值操作，就将真实的节点地址赋给了pNode这个函数的局部变量
pTop = PopLkStack(pTop, pNode);
if (pNode != NULL) {
printf("%d ",pNode->data);
//对右子树压栈
pTop = PushLkStack(pTop, pNode->right);
pTop = PushLkStack(pTop, pNode->left);
}
}
}
void inorder(BitTree *t) {
if (t) {
inorder(t->left);
printf("%d ", t->data);
inorder(t->right);
}
}
/*
中序就是左根右，这就意味着，当我们从根节点出发，应当首先走向左孩子
,而根的左孩子，是根的左子树的根节点，因此
又必须，继续访问其左孩子，直到左孩子为空
当这个节点访问之后，按照相同的规则，访问其右子树
我们借助的栈，就应该按照左根右来压栈
对于任意节点p
1 如果其左孩子不为空，则将p入栈，然后将p的左孩子置为当前的p，然后
再对p进行相同的处理
2 若左孩子为空，则取栈顶元素进行出栈操作，访问当前栈顶节点，然后
将当前的p置为栈顶节点的右孩子
3 直到p为NULL为止
*/
void NonRecvInorder(BitTree *root) {
LinkStack* pTop = NULL;
BitTreeNode TempNode;//用来接收栈中的对应的二叉树的节点
pTop = InitLkStack();
BitTree *p = root;
while (p != NULL || !IsEmptyLkMazeStack(pTop)) {
while (p != NULL) {
pTop = PushLkStack(pTop, p);
p = p->left;
}
if (!IsEmptyLkMazeStack(pTop)) {
//因为此时我们在输出的节点信息，就一定要从栈中
//取出元素
//这个是取出的元素的_NodeAddrCopy分量就是树中节点的地址
//因此对这个节点使用->就可以获得真实的数据
printf("%d ", pTop->_NodeAddrCopy->data);
p = pTop->_NodeAddrCopy; //因为我们设计的p就是要走完root全部节点，因此
//p必须获得的是树节点的真实地址
pTop = PopLkStack(pTop, &TempNode);//当我们把左子树的左叶子节点走完以后，
//此时栈顶一定是这个左孩子的根，所以根据左根右，这个根要出栈
//----change by dingst
//p = &TempNode; 因为tmpenode是bitnode的对象，
//所以tmpenode的地址值可以赋值给p这个指针变量，但是这个tempnode的这个地址值
//是肯定不等于真实树节点的地址值的
p = p->right;//走向根的右孩子
}
}
}
void postorder(BitTree* t) {
if (t) {
//左右根
postorder(t->left);
postorder(t->right);
printf("%d ", t->data);
}
}
/*
后序：左右根
根节点只有在左孩子和右孩子都访问以后才能访问
因此，对于任何一个节点，都将其入栈，如果p不存在左孩子和右孩子，直接访问
或者p存在左孩子或者右孩子，但是他的左孩子和右孩子都已经被访问过了
同样的，这个节点也可以直接访问.
如果，上述条件都不满足,就要将这个p的右孩子，左孩子依次入栈
这样就能保证，每次取栈顶元素的时候，左孩子都在右孩子之前被访问，
左右孩子访问之后，根才被访问
*/
void NonRecvPostorder(BitTree* root) {
BitTree* cur;//当前节点==>cur 保存的就是树节点的地址
BitTree* pre = NULL;//前一次访问的节点
LinkStack* pTop = NULL;
BitTreeNode TempNode;//注意我们就是用tempnode来接里面的内容，他是不能参与地址比较的，他的地址一定和我们栈中的地址不一样
pTop = InitLkStack();
pTop = PushLkStack(pTop, root);
while (!IsEmptyLkMazeStack(pTop)) {
cur = pTop->_NodeAddrCopy;//拿到栈中深拷贝获得的节点
//在访问中，由于我们是深拷贝树的节点，因此，pre和cur的地址不一样，我们只能比较器元素内容
//小技巧：利用短路，确保程序的可靠性
if ((cur->left == NULL && cur->right == NULL) ||
(pre != NULL && (pre == cur->left|| pre == cur->right))
) {
printf("%d ", cur->data);
pTop = PopLkStack(pTop, &TempNode);
pre = cur;
}
else {
if (cur->right != NULL)
pTop = PushLkStack(pTop, cur->right);
if (cur->left != NULL)
pTop = PushLkStack(pTop, cur->left);
}
}
}
//求叶子节点:树的遍历是一种非线性遍历，在业务编程中，从实现角度上
//用递归遍历三个方法之一，判断节点属性，就可以完成暴力搜索树
int LeafCount = 0;
void LeafCount_DLR(BitTree* t) {
if (t) {
if(t->left == NULL && t->right == NULL){
printf("%d ", t->data);
LeafCount++;
}
LeafCount_DLR(t->left);
LeafCount_DLR(t->right);
}
}
//因为我们现在能够不重复，不遗漏获取每一个节点，只有前中后序3种方法，所以，我们首先先写出
//先序递归获取树的深度
int hight = 0;//它可以在多个函数之间共享
//前序是根左右，我们把每一个树从root出发的树，可以看出左右两个子树
//无论我们如何遍历，我们前进到每一个节点都是潜在的根节点。
//我们可以认为每到一个新节点，就是到了一个新树,
//如果说，我们对新节点的发现，我们就认为到了一个新层，那么我们累加
//记录就可以了
//我用level作为当前树的高度
//当我用root，0传入的时候，就意味着已经有第一层的计数起始器
//我们用打擂台的思路，用h比对，就可以完成记录
/*
找一组数中的最大值
for（）{
if(max < a[i])
max =a[i]
}
*/
int TreeDepth_DLR(BitTree *pNode, int level) {
if (pNode) {
level++;
if (level > hight)
hight = level;//这一就意味伴随着level的不断深入，我们的hight始终获得的是树中最深的层次
printf("%d ", pNode->data);
//从327开始到333行，我们认为这个函数的终止条件完成了
//根据我们前面的观点，递归函数本身就是答案
//因此hight就应该接递归函数的返回值
hight = TreeDepth_DLR(pNode->left, level);
hight = TreeDepth_DLR(pNode->right, level);//因为所有节点的遍历都是跟左右，所以和当前树节点传入的同时，它当前做在的层数我们要传入
}
return hight;
}
//根据前序、中序重建二叉树
BitTree* reConstructBinTree(int pre[], int startPre, int endPre,
int in[], int startIn, int endIn) {
//如果起始的下标大于结束的下标，那么就退出
if (startPre > endPre || startIn > endIn) {
return NULL;
}
//前序找到根节点
BitTree* pNode = (BitTree*)malloc(sizeof(BitTree));
pNode->left = NULL;
pNode->right = NULL;
pNode->data = pre[startPre];//前根当中的首元素一定是当前子树的根节点
for (int i = startIn;i <= endIn;i++) {
if (in[i] == pre[startPre]) {
//i-startIn就是左子树节点的个数
//i -1就是中序遍历左子树的终点
pNode->left = reConstructBinTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
//前序右子树的遍历起始值：startPre+i-startIn+1
//中序遍历右子树的起始值：i+1,endIn(i理解成你第几次切刀)
pNode->right = reConstructBinTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
}
}
return pNode;
}
//求根到所有叶子节点的路径
BitTree* Paths[10] = { 0 };
void OutPutPath(){
int i = 0;
while (Paths[i] != NULL) {
printf("%d ", Paths[i]->data);
i++;
}
printf("\n");
}
//求路径的函数
void LeavesPath(BitTree* tree, int level) {
if (tree == NULL)
return;
Paths[level] = tree;//这句话就意味着，只要走到这里，这个子树的根就被记录下来
//求路径，意味着找到叶子节点，就输出
if ((tree->left == NULL) && (tree->right == NULL)) {
//当我确定到已经从树根节点root走到了一个叶子节点，那么它以前所有的根节点都存在paths里面
Paths[level + 1] = NULL;//通过level传递了路线信息
OutPutPath();
return;
}
LeavesPath(tree->left, level + 1);
LeavesPath(tree->right, level + 1);
}
//判断两个二叉树是否相等
//提问如果两个二叉树的前序遍历相等，能否说明，这两个树相等？
//答案是否定的，只有这两个树的 A前序=B前序，A中序=B中序才可以。
BOOL isEqualTree(BitTree* t1, BitTree* t2) {
if (t1 == NULL && t2 == NULL)
return TRUE;
if (!t1 || !t2)//t1，t2一个空一个不空，肯定不相同
return FALSE;
if (t1->data == t2->data)
return isEqualTree(t1->left, t2->left) && isEqualTree(t1->right, t2->right);
else
return FALSE;
}
//使用二叉链表建立二叉搜索树:注意，我们目前这个树不支持相同元素
BitTree* insertIntoBinSearchTree(BitTree* root, int node) {
BitTree* newNode;
BitTree* currentNode;
BitTree* parentNode;
newNode = (BitTree*)malloc(sizeof(BitTree));
newNode->data = node;
newNode->left = NULL;
newNode->right = NULL;
if (root == NULL)
return newNode;
else {
currentNode = root;//然后我们对当前节点进行定位
//注意，传入root是根节点，我们要根据根节点，按照左小右大的逻辑找到节点位置
//首先通过while找到新节点的位置
while (currentNode != NULL) {
parentNode = currentNode;
if (currentNode->data > node) {
currentNode = currentNode->left;
}
else {
currentNode = currentNode->right;
}
}
//其次，我们将父节点和子节点做连接
if (parentNode->data > node) {
parentNode->left = newNode;
}
else {
parentNode->right = newNode;
}
}
return root;
}
BitTree* create_LkBinTree(int data[], int length) {
BitTree* root=NULL;
int i;
for (i = 0;i < length;i++) {
root = insertIntoBinSearchTree(root, data[i]);
}
return root;
}
//二叉树镜像:交换两个子树
void SwapTree(BitTree* tree) {
BitTree* pTemp;
pTemp = tree->left;
tree->left = tree->right;
tree->right = pTemp;
}
void ExchangeSubTree(BitTree* tree) {
if (tree == NULL)
return;
else {
SwapTree(tree);
ExchangeSubTree(tree->left);
ExchangeSubTree(tree->right);
}
}
int main(void) {
int arr[17] = { 0,6,3,8,
2,5,7,9,
0,0,4,0,
0,0,0,10,
-999
};
BitTree *root = CreateBinTree(arr);
/*printf("递归形式的先跟遍历\n");
preorder(root);
printf("\n非递归形式的先跟遍历\n");
NonRecrvPreOrder(root);*/
//NonRecvInorder(root);
/*printf("递归形式的后根遍历\n");
postorder(root);
printf("\n非递归形式的后根遍历\n");
NonRecvPostorder(root);*/
//******************BEGIN:树的节点与深度****************
/*LeafCount_DLR(root);
printf("\n当前书总共有%d个叶子节点", LeafCount);*/
//printf("\n当前树有%d层", TreeDepth_DLR(root, 0));
给定一个二叉树，我要分别得到它的左子树的深度和右子树的深度
我们用复用的思想，很容易就得到了内容
注意，虽然复用的思想是好的，当时要注意全局变量的副作用
要对全局变量清零
//hight = 0;
//printf("\n当前树的左子树有%d层\n", TreeDepth_DLR(root->left, 0));
//hight = 0;
//printf("\n当前树的右子树有%d层\n", TreeDepth_DLR(root->right, 0));
当我们在使用递归遍历中，利用全局变量进行传递的时候
函数的复用应当注意全局变量的置0
//******************END 树的节点与深度****************
//************Beign 二叉树重建
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
/*int pre[] = { 1,2,4,7,3,5,6,8 };
int in[] = { 4,7,2,1,5,3,8,6 };
BitTree* rootNew;
rootNew = reConstructBinTree(pre, 0, 7, in, 0, 7);
preorder(rootNew);
printf("\n");
inorder(rootNew);*/
//*************End 二叉树重建
//***********Begin 获取根节点到叶子节点
//LeavesPath(root, 0);//0表示层级的传递，只要根据level延伸就能找到每一棵子树的根节点
//************END获取根节点到叶子节点
//***************Begin 判断两颗二叉树是否一致
//如果，输入的数字序列前后不一致，那么使用二叉搜索树建立的也不是同一棵树
/*int arrary[] = { 1,2,3 };
BitTree* tree1 = create_LkBinTree(arrary, 3);
int brr[] = { 1,2,3 };
BitTree* tree2 = create_LkBinTree(brr, 3);
printf("\n");
inorder(tree1);
printf("\n");
inorder(tree2);
printf("\n%d", isEqualTree(tree1, tree2));
*/
//***************End 判断两颗二叉树是否一致
//*************Begin 二叉树镜像：交换一个二叉树的左右子树
int arrary[] = { 5,4,7,2,3,6,8 };
BitTree* tree1 = create_LkBinTree(arrary, 7);
printf("\n");
inorder(tree1);
ExchangeSubTree(tree1);
printf("\n");
inorder(tree1);
//*************End 二叉树镜像：交换一个二叉树的左右子树
getchar();
return 0;
}
二叉树的非递归遍历算法 BitTreeApp
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node {
datatype data;
struct node *left, *right;
}BitTree;
//*************************Begin*************
//添加辅助栈的结构：主要是用来保存树的节点
//简言之，这个就是用来存树节点的栈
typedef BitTree BitTreeNode;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
typedef struct linknode {
BitTreeNode data;
struct linknode* pNext;
}LinkStack;
LinkStack* InitLkStack(void) {
LinkStack* p = NULL;
p = (LinkStack*)malloc(sizeof(LinkStack));
if (p != NULL)
p->pNext = NULL;
return p;
}//建立一个带头节点的链表作为链栈
BOOL IsEmptyLkMazeStack(LinkStack* top) {
return (top->pNext == NULL);
}
LinkStack* PushLkStack(LinkStack* top, BitTreeNode* elem) {
LinkStack* p=NULL;
//深拷贝的bug修订，如果传入的是空指针，那么不能访问,修订人丁宋涛
if (elem != NULL)
{
p = (LinkStack*)malloc(sizeof(LinkStack));
//todo:我们用新建节点，对传入的二叉树节点做一个深拷贝
p->data.data = elem->data;
p->data.left = elem->left;
p->data.right = elem->right;
p->pNext = top; //p节点尾插入lkStack
top = p;//top栈顶指针上移
}
//我们思考，既然我们允许空指针进入到我们的栈结构，那么我们如何修订
//我们的出栈？
//top为空以为着？
//意味着是否和栈空条件冲突了？
//如果我们让我们的NULL进入栈空间，那么出栈也会造成空指针
//这意味着当前的节点不动
return top;
}
//出栈:pData是传入的一个“临时”空间用来接收出栈的节点信息。
LinkStack* PopLkStack(LinkStack* top, BitTreeNode *pData) {
LinkStack* p;
if (top != NULL) {
//*pData = top->data;
pData->data = top->data.data;
pData->left = top->data.left;
pData->right = top->data.right;
//pData实际上深拷贝了一份节点信息，所以释放栈中节点，不会影响
//节点数据
p = top;
top = p->pNext;
free(p);
}
return top;
}
//*************************End***************
//辅助队列Q，这是用来存关系的
BitTree* Q[16];//这是一个指针数组，它将缓存节点的地址，因为这个地址将以
//left域，或者right域进入二叉链表，它本身不维护i，2i，2i+1的关系
//他的关系通过front，rear来维护
//按照直观的建立，我们首先想到的是层次法
//我们根据层次，来逐一将二叉树建立
//输入的数组是按照完全二叉树的编号规则设立，即
//数组角标反映了节点位置关系（存联系）
//逐个扫描数组，直到所有的节点都存取完毕之后，就结束
//约定，0表示数组当前元素为空，最后一个节点标志是-999
BitTree* CreateBinTree(int arr[]) {
int i = 1;
//只要我们没有扫描完元素，那么这个二叉链表就没有完成
//只要扫描，我们就malloc一个节点，然后把这个节点存入left域或者right域
int front = 1, rear = 0;
BitTree* root = NULL;
BitTree* s;//暂存节点
while (arr[i] != -999) {
s = NULL;
if (arr[i] != 0) {//意味着这个不是空节点，那么我们就要分配空间
s = (BitTree*)malloc(sizeof(BitTree));
s->data = arr[i];//存数值
s->left = NULL;
s->right = NULL;
}
//要让我们新节点入队，进入缓存，等待分配双亲的left域和right域
Q[++rear] = s;
if (rear == 1)
{
root = s;
}
else {
if (s != NULL && Q[front]) {
if (rear % 2 == 0) {
Q[front]->left = s;
}
else {
Q[front]->right = s;
}
}
if (rear % 2 == 1)
front++;
}
i++;
}
return root;
}
//树遍历问题：非线性结构的输出问题：前序，中序，后序
void preorder(BitTree* t) {
if (t) {
//根左右
printf("%d ", t->data);
preorder(t->left);
preorder(t->right);
}
}
void NonRecrvPreOrder(BitTree* root) {
LinkStack* pTop = NULL;
BitTreeNode TempNode;//用来接栈中对应的二叉树节点的
pTop = InitLkStack();
pTop = PushLkStack(pTop, root);
while (!IsEmptyLkMazeStack(pTop)) {
pTop = PopLkStack(pTop, &TempNode);
if (&TempNode != NULL) {
printf("%d ", TempNode.data);
//对右子树压栈
pTop = PushLkStack(pTop, TempNode.right);
pTop = PushLkStack(pTop, TempNode.left);
}
}
}
void inorder(BitTree *t) {
if (t) {
inorder(t->left);
printf("%d ", t->data);
inorder(t->right);
}
}
/*
中序就是左根右，这就意味着，当我们从根节点出发，应当首先走向左孩子
,而根的左孩子，是根的左子树的根节点，因此
又必须，继续访问其左孩子，直到左孩子为空
当这个节点访问之后，按照相同的规则，访问其右子树
我们借助的栈，就应该按照左根右来压栈
对于任意节点p
1 如果其左孩子不为空，则将p入栈，然后将p的左孩子置为当前的p，然后
再对p进行相同的处理
2 若左孩子为空，则取栈顶元素进行出栈操作，访问当前栈顶节点，然后
将当前的p置为栈顶节点的右孩子
3 直到p为NULL为止
*/
void NonRecvInorder(BitTree *root) {
LinkStack* pTop = NULL;
BitTreeNode TempNode;//用来接收栈中的对应的二叉树的节点
pTop = InitLkStack();
BitTree *p = root;
while (p != NULL || !IsEmptyLkMazeStack(pTop)) {
while (p != NULL) {
pTop = PushLkStack(pTop, p);
p = p->left;
}
if (!IsEmptyLkMazeStack(pTop)) {
printf("%d ", pTop->data.data);
pTop = PopLkStack(pTop, &TempNode);//当我们把左子树的左叶子节点走完以后，
//此时栈顶一定是这个左孩子的根，所以根据左根右，这个根要出栈
p = &TempNode;
p = p->right;//走向根的右孩子
}
}
}
void postorder(BitTree* t) {
if (t) {
//左右根
postorder(t->left);
postorder(t->right);
printf("%d ", t->data);
}
}
/*
后序：左右根
根节点只有在左孩子和右孩子都访问以后才能访问
因此，对于任何一个节点，都将其入栈，如果p不存在左孩子和右孩子，直接访问
或者p存在左孩子或者右孩子，但是他的左孩子和右孩子都已经被访问过了
同样的，这个节点也可以直接访问.
如果，上述条件都不满足,就要将这个p的右孩子，左孩子依次入栈
这样就能保证，每次取栈顶元素的时候，左孩子都在右孩子之前被访问，
左右孩子访问之后，根才被访问
*/
void NonRecvPostorder(BitTree* root) {
BitTree* cur;//当前节点
BitTree* pre = NULL;//前一次访问的节点
LinkStack* pTop = NULL;
BitTreeNode TempNode;
pTop = InitLkStack();
pTop = PushLkStack(pTop, root);
while (!IsEmptyLkMazeStack(pTop)) {
cur = &pTop->data;//拿到栈中深拷贝获得的节点
//在访问中，由于我们是深拷贝树的节点，因此，pre和cur的地址不一样，我们只能比较器元素内容
//小技巧：利用短路，确保程序的可靠性
if ((cur->left == NULL && cur->right == NULL) ||
(pre != NULL && ((cur->left && pre->data == cur->left->data) || (cur->right && pre->data == cur->right->data)))
) {
printf("%d ", cur->data);
pTop = PopLkStack(pTop, &TempNode);
pre = &TempNode;
}
else {
if (cur->right != NULL)
pTop = PushLkStack(pTop, cur->right);
if (cur->left != NULL)
pTop = PushLkStack(pTop, cur->left);
}
}
}
int main(void) {
int arr[17] = { 0,6,3,8,
2,5,7,9,
0,0,4,0,
0,0,0,10,
-999
};
BitTree *root = CreateBinTree(arr);
/*printf("递归形式的先跟遍历\n");
preorder(root);
printf("\n非递归形式的先跟遍历\n");
NonRecrvPreOrder(root);*/
//NonRecvInorder(root);
printf("递归形式的后根遍历\n");
postorder(root);
printf("\n非递归形式的后根遍历\n");
NonRecvPostorder(root);
getchar();
return 0;
}
HuffmanTree
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct BTreeNode {
ElemType data;
struct BTreeNode* left, *right;
}BTreeNode;
//根据传入的数组a，其中n个元素作为其权值，构建一颗哈夫曼树，返回根节点
BTreeNode* CreateHuffman(ElemType a[], int n) {
int i, j;
BTreeNode ** b, *q;
b = (BTreeNode **)malloc(n * sizeof(BTreeNode));
for (i = 0;i < n;i++) {
b[i] = (BTreeNode*)malloc(sizeof(BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
//以上通过构建连续存储空间，拿到了需要存储的n个huffman节点，然后根据
//逐个将节点加入的过程，完成哈夫曼树
for (i = 1;i < n;i++) {
//k1:森林中具有最小权值的树根节点的下标，k2为次小下标
int k1 = -1, k2;
//让k1指向第一棵树，k2指向第二棵
for (j = 0;j < n;j++) {
if (b[j] != NULL && k1 == -1) {
k1 = j;
continue;
}
if (b[j] != NULL) {
k2 = j;
break;
}
}
//从当前森林中求出最小权值树、次小的
for (j = k2;j < n;j++) {
if (b[j] != NULL) {
if (b[j]->data < b[k1]->data) {
k2 = k1;
k1 = j;
}
else {
if (b[j]->data < b[k2]->data)
k2 = j;
}
}
}
//由k1，k2拼树，q指向树根节点
q =(BTreeNode*) malloc(sizeof(BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//将新树节点放回原来b申请的数组k1的位置
b[k2] = NULL;
}
free(b);
return q;//返回整个Huffman树的根节点
}
//求Huffman 树的路径
ElemType WeightPathLength(BTreeNode* FBT,int len){
if (FBT == NULL)
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL) {
//到叶子节点
return FBT->data * len;
}
else {
//非叶子节点，递归,返回左右子树带权路径长度的和，len要递增
return WeightPathLength(FBT->left, len + 1) + WeightPathLength(FBT->right, len + 1);
}
}
}
//求Huffman编码
void HuffmanCoding(BTreeNode* FBT, int len) {
static int a[10];//定义一个静态数组，保存每一个叶子节点的编码
if (FBT != NULL) {
if (FBT->left == NULL && FBT->right == NULL) {
//进入到了叶子节点
int i;
printf("节点权值为%d的编码是:", FBT->data);
for (i = 0;i < len;i++) {
printf("%d", a[i]);
}
printf("\n");
}
else {
//访问到的是非叶子节点，那么就要按照分支中，左0，右1的方式递归调用，存入a数组中
a[len] = 0;
HuffmanCoding(FBT->left, len + 1);
a[len] = 1;
HuffmanCoding(FBT->right, len + 1);
}
}
}
int main() {
int n = 6, i;
BTreeNode* fbt;
int arr[] = { 3,9,5,12,6,15 };
fbt = CreateHuffman(arr, n);
printf("带权路径长度%d\n", WeightPathLength(fbt, 0));
HuffmanCoding(fbt, 0);
getchar();
return 0;
}
