西安响应式网站建设,国外怎么做网站,中煤第一建设公司网站,wordpress登录小工具基础知识
数据是所有能被输入计算机中#xff0c;且能被计算机处理的符号的集合数据元素是数据的基本单位数据项是独立含义的数据最小单元数据对象是独立含义最小单位数据对象是指性质相同的数据元素的集合数据结构是带结构的数据元素的集合主要讨论数据之间的相邻关系或者邻…基础知识
数据是所有能被输入计算机中且能被计算机处理的符号的集合数据元素是数据的基本单位数据项是独立含义的数据最小单元数据对象是独立含义最小单位数据对象是指性质相同的数据元素的集合数据结构是带结构的数据元素的集合主要讨论数据之间的相邻关系或者邻接关系顺序存储结构是采用一组连续的存储单元存放所有的数据元素链式存储结构中每个逻辑单元用一个内存单节点存储每个节点是单独分配的所有的节点地址不一定是连续的抽象数据类型逻辑结构抽象运算算法的5个特性 有穷性确定性可行性0个或多个输入一个或者多个输出 O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2^n)O(n!)线性表的三个特性有穷性一致性序列性链表的插入结点 s-nextp-next;p-nexts; 链表的删除结点 -p-nextp-next-next;链表的初始化创建头结点 L-nextNULL;栈空的条件s-top-1;栈满的条件s-topmaxSize-1;进栈e操作top;将e放在top处退栈操作从top处取出元素e;top–;栈的初始化条件s-top-1;和出栈运算相比取栈顶元素没有移动栈顶指针栈空条件栈1空top1-1;栈2空top2MaxSize栈满条件top1top2-1元素x进栈操作进栈1操作top1;data[top1]x;进栈2操作top2–;data[top2]x;出栈x操作出栈1操作xdata[top1];top1一出栈2操作xdata[top2];top2;链栈:栈空的条件s-nextNULL;没有栈满的条件元素e进栈的操作新建一个结点存放元素e将结点p插入头结点之后。出栈的操作取出首结点的data值并将其删除队空的条件q-frontq-rear队满的条件q-rearmaxsize-1元素e进栈:rear,data[rear]e;出队front;edata[front];链队队空的条件q-rearNULL,队满不考虑元素e进栈的操作新建一个结点存放元素e将结点p插入作为尾结点出队的操作取出队首结点的data值并将其删除
线性表
顺序表
顺序表类型定义
typedef struct
{ ElemType data[Maxsize];int length;
}SqList; //顺序表类型其中data成员存放元素length.成员存放线性表的实际长度。 说明注意逻辑位序和物理位序相差1。
建立顺序表
void
CreateList(SqList L,ElemType a[],int n)
{ int i0,k0;L(SqList *)malloc(sizeof(SaList));while (in) //i扫描a中元素{ L-data[k]a[i];k;1; //k记录插入到L中的元素个数}L-lengthk
}初始化线性表
void InitList(SqList *L)
{ L(SqList *)malloc(sizeof(SqList));//分配存放线性表的顺序表空间L-length0;
}销毁线性表
void DestroyList(SqList *L)
{free(L);
} 判断是否是空表
bool ListEmpty(SqList *L)
{return(L-length0);
}
求线性表的长度
int ListLength(SqList *L)
{return(L-length);
}
输出线性表
void DispList(SqList *L)
{ int i;if (ListEmpty(L)) return;for (i0;iL-length;i)printf(%cL-data[i]);printf(\n);
}
求某个数据元素值
bool GetElem(SqList *Lint iElemType e)
{ if (i1 || iL-length) return false;eL-data[i-1];return true;
}
按元素值查找
int LocateElem(SqList *LElemType e)
{ int i0;while (iL-length L-data[i]!e) i;if (iL-length) return 0;else return i1;
}
插入数据元素
bool ListInsert(SqList *Lint iElemType e)
{ int j;if (i1 || iL-length1)return false; //参数错误时返回falsei--; //将顺序表逻辑序号转化为物理序号for (jL-length;ji;j--) //将data[i..n]元素后移一个位置L-data[j]L-data[j-1];L-data[i]e; //插入元素eL-length; //顺序表长度增1return true; //成功插入返回true
}
删除数据元素
bool ListDelete(SqList *Lint iElemType e)
{ int j;if (i1 || iL-length) //参数错误时返回falsereturn false;i--; //将顺序表逻辑序号转化为物理序号eL-data[i];for (ji;jL-length-1;j) //将data[i..n-1]元素前移L-data[j]L-data[j1];L-length--; //顺序表长度减1return true; //成功删除返回true
}
删除线性表所有值为X的数据元素
void delnode1(SqList *L ElemType x)
{ int k0 i; //k记录值不等于x的元素个数for (i0;iL-length;i)if (L-data[i]!x) //若当前元素不为x将其插入A中{ L-data[k]L-data[i];k; //不等于x的元素增1}L-lengthk; //顺序表L的长度等于k
}
小前大后
以第一个元素为分界线基准将所有小于等于它的元素移到该元素的前面将所有大于它的元素移到该元素的后面。
void move1(SqList *L)
{ int i0 jL-length-1;ElemType baseL-data[0]; //以data[0]为基准while (ij){ while (ij L-data[j]base)j--; //从后向前扫描找一个≤base的元素while (ij L-data[i]base)i; //从前向后扫描找一个base的元素if (ij)swap(L-data[i],L-data[j]);}swap(L-data[0],L-data[i]);
}
将L所有奇数移动到偶数的前面
void move1(SqList *L)
{ int i0,jL-length-1;while (ij){ while (ij L-data[j]%20)j--; //从右向左,找一个奇数元素while (ij L-data[i]%21)i; //从左向右,找一个偶数元素if (ij) //若ijL-data[i]和L-data[j]交换swap(L-data[i],L-data[j]); }
}
链表
单链表
单链表中结点类型定义:
typedef struct LNode //定义单链表结点类型
{ ElemType data;struct LNode *next; //指向后继结点
} LinkNode;
头插法建表
void CreateListF(LinkNode *LElemType a[]int n)
{ LinkNode *s;int i;L(LinkNode *)malloc(sizeof(LinkNode));L-nextNULL; //创建头结点其next域置为NULLfor (i0;in;i) //循环建立数据结点{ s(LinkNode *)malloc(sizeof(LinkNode));s-dataa[i]; //创建数据结点ss-nextL-next; //将s插在原开始结点之前头结点之后L-nexts;}
}
尾插法建表
void CreateListR(LinkNode *LElemType a[]int n)
{ LinkNode *s*r;int i;L(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点rL; //r始终指向尾结点开始时指向头结点 for (i0;in;i) //循环建立数据结点{ s(LinkNode *)malloc(sizeof(LinkNode));s-dataa[i]; //创建数据结点sr-nexts; //将s插入r之后rs;}r-nextNULL; //尾结点next域置为NULL
}
初始化线性表
void InitList(LinkNode *L){L(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-nextNULL;}
销毁线性表
void DestroyList(LinkNode *L)
{ LinkNode *preL *pL-next; //pre指向p的前驱结点while (p!NULL) //扫描单链表L{ free(pre); //释放pre结点prep; //pre、p同步后移一个结点ppre-next;}free(pre); //循环结束时p为NULLpre指向尾结点释放它
}判断线性表是否是空表
bool ListEmpty(LinkNode *L)
{return(L-nextNULL);
}
求线性表的长度
int ListLength(LinkNode *L)
{int n0;LinkNode *pL; //p指向头结点n置为0即头结点的序号为0while (p-next!NULL){ n;pp-next;}return(n); //循环结束p指向尾结点其序号n为结点个数
}
输出线性表
void DispList(LinkNode *L)
{LinkNode *pL-next; //p指向开始结点while (p!NULL) //p不为NULL输出p结点的data域{ printf(%d p-data);pp-next; //p移向下一个结点}printf(\n);
}求线性表L中位置i的数据元素
bool GetElem(LinkNode *Lint iElemType e)
{ int j0;LinkNode *pL; //p指向头结点j置为0即头结点的序号为0while (ji p!NULL){ j;pp-next;}if (pNULL) //不存在第i个数据结点返回falsereturn false;else //存在第i个数据结点返回true{ ep-data;return true;}
}
按元素值查找
int LocateElem(LinkNode *LElemType e)
{int i1;LinkNode *pL-next; //p指向开始结点i置为1 while (p!NULL p-data!e) { pp-next; //查找data值为e的结点其序号为ii;}if (pNULL) //不存在元素值为e的结点返回0return 0;else //存在元素值为e的结点返回其逻辑序号ireturn i;
}
插入数据元素
bool ListInsert(LinkNode *Lint iElemType e)
{ int j0;LinkNode *pL*s; //p指向头结点j置为0while (ji-1 p!NULL){ j;pp-next;}if (pNULL) //未找到第i-1个结点返回falsereturn false;else //找到第i-1个结点p插入并返回true{s(LinkNode *)malloc(sizeof(LinkNode));s-datae; //创建新结点s其data域置为es-nextp-next; //将s插入到p之后p-nexts;return true;}
}
删除数据元素
bool ListDelete(LinkNode *Lint iElemType e)
{ int j0;LinkNode *pL*q; //p指向头结点j置为0while (ji-1 p!NULL) //查找第i-1个结点{ j;pp-next;}if (pNULL) //未找到第i-1个结点返回falsereturn false;else //找到第i-1个结点p{ qp-next; //q指向第i个结点if (qNULL) //若不存在第i个结点返回falsereturn false;eq-data;p-nextq-next; //从单链表中删除q结点free(q); //释放q结点return true; //返回true表示成功删除第i个结点}
}
带头结点的单链表逆置
void Reverse(LinkNode *L)
{ LinkNode *pL-next*q;L-nextNULL;while (p!NULL){ qp-next; //临时保存p的后继结点p-nextL-next; //将p结点采用头插法连接L-nextp;pq;}
}
将L其拆分成两个带头结点的单链表L1和L2
void split(LinkNode *LLinkNode *L1LinkNode *L2)
{ LinkNode *pL-next*q*r1; //p指向第1个数据结点L1L; //L1利用原来L的头结点r1L1; //r1始终指向L1的尾结点L2(LinkNode *)malloc(sizeof(LinkNode)); //创建L2的头结点L2-nextNULL; //置L2的指针域为NULL while (p!NULL){ r1-nextp; //采用尾插法将p(data值为ai)插入L1中r1p;pp-next; //p移向下一个结点(data值为bi)qp-next; //用q保存p的后继结点p-nextL2-next; //采用头插法将p插入L2中L2-nextp;pq; //p重新指向ai1的结点}r1-nextNULL; //尾结点next置空
}
删除一个单链表L中元素值最大的结点唯一
void delmaxnode(LinkNode *L)
{ LinkNode *pL-next*preL*maxpp*maxprepre;while (p!NULL){ if (maxp-datap-data) //若找到一个更大的结点{ maxpp; //更改maxpmaxprepre; //更改maxpre}prep; //p、pre同步后移一个结点pp-next;}maxpre-nextmaxp-next; //删除maxp结点free(maxp); //释放maxp结点
}
使L其元素递增有序排列
void sort(LinkNode *L)
{ LinkNode *p*pre*q;pL-next-next; //p指向L的第2个数据结点L-next-nextNULL; //构造只含一个数据结点的有序表while (p!NULL){ qp-next; //q保存p结点后继结点的指针preL; //从有序表开头pre指向插入p的前驱结点while (pre-next!NULL pre-next-datap-data)prepre-next; //在有序表中找插入p的前驱结点prep-nextpre-next;pre-nextp;pq; //扫描原单链表余下的结点}
}
双链表
类型定义
typedef struct DNode //双链表结点类型
{ ElemType data;struct DNode *prior; //指向前驱结点struct DNode *next; //指向后继结点
} DLinkNode;
头插法建表
void CreateListF(DLinkNode *LElemType a[]int n)
{ DLinkNode *s; int i;L(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-priorL-nextNULL; //前后指针域置为NULLfor (i0;in;i) //循环建立数据结点{ s(DLinkNode *)malloc(sizeof(DLinkNode));s-dataa[i]; //创建数据结点ss-nextL-next; //将s插入到头结点之后if (L-next!NULL) //若L存在数据结点修改前驱指针L-next-priors;L-nexts;s-priorL;}
}
尾插法建表
void CreateListR(DLinkNode *LElemType a[]int n)
{ DLinkNode *s*r;int i;L(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点rL; //r始终指向尾结点开始时指向头结点for (i0;in;i) //循环建立数据结点{ s(DLinkNode *)malloc(sizeof(DLinkNode));s-dataa[i]; //创建数据结点sr-nexts;s-prirr; //将s插入r之后rs; //r指向尾结点}r-nextNULL; //尾结点next域置为NULL
}
插入
bool ListInsert(DLinkNode *Lint iElemType e)
{ int j0;DLinkNode *pL*s; //p指向头结点j设置为0while (ji-1 p!NULL) //查找第i-1个结点{ j;pp-next;} if (pNULL) //未找到第i-1个结点返回falsereturn false;else //找到第i-1个结点p在其后插入新结点s{s(DLinkNode *)malloc(sizeof(DLinkNode));s-datae; //创建新结点ss-nextp-next; //在p之后插入s结点if (p-next!NULL) //若存在后继结点修改其前驱指针p-next-priors;s-priorp;p-nexts;return true;}
}
删除
bool ListDelete(DLinkNode *Lint iElemType e)
{ int j0; DLinkNode *pL*q; //p指向头结点j设置为0while (ji-1 p!NULL) //查找第i-1个结点{ j;pp-next;}if (pNULL) //未找到第i-1个结点return false;else //找到第i-1个结点p{ qp-next; //q指向第i个结点if (qNULL) //当不存在第i个结点时返回falsereturn false;eq-data;p-nextq-next; //从双单链表中删除q结点if (q-next!NULL) //若q结点存在后继结点q-next-priorp; //修改q结点后继结点的前驱指针free(q); //释放q结点return true;}
}
链表元素逆置
void reverse(DLinkNode *L) //双链表结点逆置
{ DLinkNode *pL-next*q; //p指向开始结点L-nextNULL; //构造只有头结点的双链表Lwhile (p!NULL) //扫描L的数据结点{ qp-next; //用q保存其后继结点p-nextL-next; //采用头插法将p结点插入if (L-next!NULL) //修改其前驱指针L-next-priorp;L-nextp;p-priorL;pq; //让p重新指向其后继结点}
}
使L其元素递增有序排列。
void sort(DLinkNode *L) //双链表结点递增排序
{ DLinkNode *p,*pre,*q;pL-next-next; //p指向L的第2个数据结点L-next-nextNULL; //构造只含一个数据结点的有序表while (p!NULL){ qp-next; //q保存p结点后继结点preL; //从L开头比较,pre指向插入结点p的前驱结点while (pre-next!NULL pre-next-datap-data)prepre-next; //在有序表中找插入结点的前驱结点prep-nextpre-next; //在pre结点之后插入结点pif (pre-next!NULL)pre-next-priorp;pre-nextp;p-priorpre;pq; //扫描原双链表余下的结点}
}
循环链表
统计L其data域值为X的个数
int count(LinkNode *L,ElemType x)
{ int cnt0;LinkNode *pL-next; //p指向首结点,cnt置为0while (p!L) //扫描循环单链表L{ if (p-datax)cnt; //找到值为x的结点后cnt增1pp-next; //p指向下一个结点}return cnt; //返回值为x的结点个数
}
循环双链表
删除第一个data域值为x的结点
bool delelem(DLinkNode *L,ElemType x)
{ DLinkNode *pL-next; //p指向首结点while (p!L p-data!x) //查找第一个data值为x的结点ppp-next;if (p!L) //找到了第一个值为x的结点p{ p-next-priorp-prior; //删除p结点p-prior-nextp-next;free(p);return true; //返回真}else //没有找到为x的结点返回假return false;
}
判断带头结点的L是否对称相等
bool Symm(DLinkNode *L)
{ bool sametrue;DLinkNode *pL-next; //p指向首结点DLinkNode *qL-prior; //q指向尾结点while (same){if (p-data!q-data)samefalse;else { if (pq || pq-prior) break;qq-prior; //q前移pp-next; //p后移}}return same;
}
有序表
插入
void ListInsert(SqList *LElemType e)
{ int i0j;while (iL-length L-data[i]e)i; //查找值为e的元素for (jListLength(L);ji;j--) //将data[i..n]后移一个位置L-data[j]L-data[j-1]; L-data[i]e;L-length; //有序顺序表长度增1
}
void ListInsert(LinkNode *LElemType e)
{ LinkNode *preL*p;while (pre-next!NULL pre-next-datae)prepre-next; //查找插入结点的前驱结点prep(LinkNode *)malloc(sizeof(LinkNode));p-datae; //创建存放e的数据结点pp-nextpre-next; //在pre结点之后插入p结点pre-nextp;
}
代码实现
顺序表代码实现
#include stdio.h
#include stdlib.h
#include malloc.h //内存分配空间
#define MaxSize 50 //定义整型常量
#include stdbool.h
typedef int ElemType;//自定义数据类型假设ElemType为int类型
typedef struct
{ElemType data[MaxSize]; //存放线性表中的元素 int length;//存放线性表的长度
} SqList;//顺序表类型 //创建线性表
//方法:将给定的含有个n元素的数组的每个元素依次放入到顺序表中
//并将给n赋值给顺序表的长度成员 L-length
void CreateList(SqList *L,ElemType a[],int n)//由a中的n个元素建立顺序表
{ //引用参数将执行结果回传给实参传递顺序表指针 int i0;L(SqList *)malloc(sizeof(SqList));//求出SqList的内存长度 for(i0;in;i) //并转换为SqList类型的指针赋值给L L-data[i]a[i];L-lengthn; } //时间复杂度是O(n)//初始化线性表
void InitList(SqList *L)//引用型指针
{L(SqList *)malloc(sizeof(SqList)); L-length0; //置空线性表的长度
}//销毁线性表
void DestroyList(SqList *L)
{free(L);//释放L所指的顺序表空间 } //判断是否为空表
bool ListEmpty(SqList *L)
{return(L-length0);//空表返回true否者返回false } //求数据表的长度int ListLength(SqList *L){return(L-length);//直接返回数据域length } //输出线性表
void DispList(SqList *L)
{int i;if(ListEmpty(L))//先判断是否为空true继续 return;for(i0;iL-length;i)printf( %d,L-data[i]);printf(\n); } //按序号求线性表中的元素bool GetElem(SqList *L,int i,ElemType e){if(i1||iL-length)return false; //判断是否在表中 eL-data[i-1];//i是逻辑顺序,i-1是物理顺序求出下标并取元素的值 return true;}//按元素查找 //如果遍历完整个列表都没有找到元素a函数返回0。//如果找到了元素a函数返回它在列表中的位置从1开始计数。int LocateElem(SqList *L,ElemType a){int i0;while(iL-lengthL-data[i])i;if(iL-length)return 0;elsereturn i1;} //插入数据bool ListInsert(SqList *L,int i,ElemType e) {int j;if(i1||iL-length1||L-lengthMaxSize)return false;//表示线性表元素在表外 i--;//将逻辑序号转换为物理序号下标for(jL-length;ji;j--)L-data[j]L-data[j-1];//将data[i]及后面的元素后移一个位置L-data[i]e;L-length;return true; }//删除元素数据
bool ListDelete(SqList *L,int i,ElemType e)
{int j;if(i1||iL-length)return false;//不在表中 i--;//将逻辑序号转换为物理序号下标eL-data[i];//将位置i的元素赋值给e。 for(ji;jL-length-1;j)//下标 L-data[j]L-data[j1];//将data[i]之后的元素前移一个元素 L-length--;//顺序表的长度减一 return true;
}int main()//测试函数
{SqList *sq;//分配空间保存的指针值 ElemType x[20]{1,2,3,4,5,6,6};CreateList(sq,x,7);printf(原始线性表);DispList(sq);ElemType d2;ListInsert(sq,2,d);printf(插入后的线性表);//在元素2之后上插入2 DispList(sq);ElemType f;ListDelete(sq,4,f);printf(删除的元素是);// 删除第4个元素 DispList(sq);printf(输出线性表的长度); ListLength(sq);int length ListLength(sq);printf(%d\n,length);ElemType w2;int b;bLocateElem(sq,w);printf(存在这个元素吗存在的话在第几位%d\n,b);ElemType e;
// bool a true;
// bool b false; printf(线性表中存第3个元素吗); printf(%d\n,GetElem(sq,3,e)); return 0;
}
单链表代码实现
#include stdio.h
#include malloc.h
typedef int ElemType;//数据域可以为其他类型typedef struct LNode//定义单链表节点类型
{ElemType data;//数据域struct LNode *next;//指针域指向后继节点
}LinkNode;
//头插法建立单链表
void CreateListF(LinkNode *L,ElemType a[],int n)
{LinkNode *s;L(LinkNode *)malloc(sizeof(LinkNode));L-nextNULL;for(int i0;in;i){s(LinkNode *)malloc(sizeof(LinkNode));s-dataa[i];s-nextL-next;L-nexts;}
}
//尾插法建立单链表
void CreateLsitR(LinkNode *L,ElemType a[],int n)
{LinkNode *s,*r;L(LinkNode *)malloc(sizeof(LinkNode));rL;for(int i0;in;i){s(LinkNode *)malloc(sizeof(LinkNode));s-dataa[i];r-nexts;rs;} r-nextNULL;}
//初始化单链表
void InitList(LinkNode *L)
{L(LinkNode *)malloc(sizeof(LinkNode));L-nextNULL;
} //输出单链表
void DisList(LinkNode *L)
{LinkNode *pL-next;while(p!NULL){printf( %d,p-data);pp-next;}printf(\n);}
bool ListEmpty(LinkNode *L)
{return(L-nextNULL);
}
//线性表的长度
int ListLength(LinkNode *L)
{int n0;LinkNode *pL;while(p-next!NULL){n;pp-next;}return(n);} //按序号求表中的元素bool GetElem(LinkNode *L,int i,ElemType e){int j0;LinkNode *pL;if(i0)return false;while(jip!NULL){j;pp-next;}if(pNULL)return false;else{ep-data;return true;}} //按元素值查找int LocateElem(LinkNode *L,ElemType e){int i 1;LinkNode *pL-next;while(p!NULLp-data!e){pp-next;i;}if(pNULL)return(0);elsereturn(i);}
//插入数据元素
bool ListInsert(LinkNode *L,int i,ElemType e)
{int j0;LinkNode *pL,*s;if(i0) return false;while(ji-1p!NULL){j;pp-next;}if(pNULL)return false;else{s(LinkNode *)malloc(sizeof(LinkNode));s-datae;s-nextp-next;p-nexts;return true;}} //删除数据元素
bool ListDelete(LinkNode *L,int i,ElemType e)
{int j0;LinkNode *pL,*q;if(i0)return false;while(ji-1p!NULL){j;pp-next;}if(pNULL)return false;else{qp-next;if(qNULL)return false;eq-data;p-nextq-next;free(q);return true;}}
//测试函数
int main()
{LinkNode *L;ElemType x[20]{1,2,3,4,5,6,7};printf(头插法建立单链表\n);CreateListF(L,x,7);//InitList(L);DisList(L);printf(尾插法建立单链表\n);CreateLsitR(L,x,7);DisList(L);int a;aListLength(L);printf(输出单链表的长度%d\n,a);int b;bListEmpty(L);printf(这个单链表是否为空%d\n,b);ElemType c;printf(找到第3个数据结点%d\n,GetElem(L,3,c));ElemType d5;printf(第一个值域为5的结点的逻辑序号为%d\n,LocateElem(L,d));ElemType e2;ListInsert(L,2,e);printf(插入后的链表\n);DisList(L);ElemType f2;ListDelete(L,2,f);printf(删除后的链表\n);DisList(L);}
栈代码实现
判断表达式中的括号是否正确配对
#include stdio.h
#include malloc.h
#include stdlib.h
#define MaxSize 50
typedef char ElemType;
typedef struct
{ElemType data[MaxSize];int top;
}SqStack;
void InitStack(SqStack *s)
{s(SqStack *)malloc(sizeof(SqStack));s-top-1;
}
DestroyStack(SqStack *s)
{free(s);
}
bool StackEmpty(SqStack *s)
{return (s-top-1);
}
bool GetTop (SqStack *s,ElemType e)
{if(s-top-1)return false;es-data[s-top];return true;
}
bool Push(SqStack *s,ElemType e)
{if(s-topMaxSize-1)return false;s-top;s-data[s-top]e;return true;
}
bool Pop(SqStack *s,ElemType e)
{if(s-top-1)return false;es-data[s-top];s-top--;return true;
}
bool Match(char exp[],int n)
{ SqStack *ls;InitStack(ls);int i0;ElemType e;bool flagtrue;while (in flag){ if (exp[i]( || exp[i][ || exp[i]{)Push(ls,exp[i]); //遇到(、[或{,则将其进栈if (exp[i])) //遇到),若栈顶是(,则继续处理,否则以不配对返回{ if (GetTop(ls,e)){ if (e() Pop(ls,e);else flagfalse;}else flagfalse;}if (exp[i]]) //遇到],若栈顶是[,则继续处理,否则以不配对返回{ if (GetTop(ls,e)){ if (e[) Pop(ls,e);else flagfalse;}else flagfalse;}if (exp[i]}) //遇到},若栈顶是{,则继续处理,否则以不配对返回{ if (GetTop(ls,e)){ if (e{) Pop(ls,e);else flagfalse;}else flagfalse;}i;}if (!StackEmpty(ls)) flagfalse; //若栈不空,则不配对DestroyStack(ls);return flag;
}
int main()
{ char exp[] {a,a,(b,b),c,c}; int n sizeof(exp) / sizeof(char); //计算字符串数组的长度也就是字符串中的字符数。 bool result Match(exp, n); printf(Result: %s\n, result ? true : false); return 0;
}
队列的代码实现
数字进队小写字母出队其他字符输入结束
#include stdio.h
#include malloc.h
#include stdlib.h
#define MaxSize 10
typedef int ElemType;
typedef struct
{ElemType data[MaxSize];int front,rear;
}SqQueue;
void InitQueue(SqQueue *q)
{q(SqQueue *)malloc(sizeof(SqQueue));q-frontq-rear-1;
}
void DestroyQueue (SqQueue *q)
{free(q);
}
bool enQueue (SqQueue *q,ElemType e)
{if(q-rearMaxSize-1)return false;q-rear;q-data[q-rear]e;return true;
}
bool deQueue(SqQueue *q,ElemType e)
{if(q-frontq-rear)return false;q-front;eq-data[q-front];return true;
}
bool QueueEmpty(Squeue *q)
{return (q-frontq-rear);
}void fun()
{ ElemType a,e;SqQueue *qu; //定义队列指针InitQueue(qu);while (true){ printf(输入 a:);scanf(%s,a);if (a0 a9) //为数字字符{ if (!enQueue(qu,a))printf( 队列满,不能进队\n);}else if (aa az) //为小写字母{ if (!deQueue(qu,e))printf( 队列空,不能出队\n);elseprintf( 出队元素:%c\n,e);}else break; //为其他字符}DestroyQueue(qu);
}
int main()
{fun();
}
串的代码实现
//递归求串s 的逆串
#include stdio.h
#define MaxSize 50
typedef struct
{char data[MaxSize];int length;
}SqString;
int StrLength(SqString s){return(s.length);
}
SqString InsStr(SqString s1,int i,SqString s2)
{int j;SqString str;str.length0; if(i0||is1.length1) return str;for(j0; ji-1; j)str.data[j]s1.data[j];for(j0; js2.length; j)str.data[ij-1]s2.data[j];for(ji-1; js1.length; j)str.data[s2.lengthj]s1.data[j];str.lengths1.lengths2.length;return str;
}
void StrCopy(SqString s, SqString t){for(int i0; it.length; i) {s.data[i]t.data[i]; }s.lengtht.length;
}
SqString Concat(SqString s,SqString t)
{SqString str;int i;str.lengths.lengtht.length;for(i0; is.length; i)str.data[i]s.data[i];for(i0; it.length; i)str.data[s.lengthi]t.data[i];return str;
}
SqString SubStr(SqString s,int i,int j)
{int k;SqString str;str.length0;if(i0||is.length||j0||ij-1s.length)return str;for(ki-1; kij-1; k)str.data[k-i1]s.data[k];str.lengthj;return str;
}
SqString invert(SqString s)
{ SqString s1,s2;if (StrLength(s)0){ s1invert(SubStr(s,2,StrLength(s)-1));s2Concat(s1,SubStr(s,1,1));}elseStrCopy(s2,s);return s2;
}
int main()
{ SqString s {Hello,world, 11}; SqString Invert invert(s); for(int i 0; i Invert.length; i) { printf(%c, Invert.data[i]); } return 0;
}
递归的代码实现
//判断几位数
#include stdio.h
int fun(int n)
{ if (n10)return 1;elsereturn fun(n/10)1;
}
int main()
{int n;printf(输入正整数n:\n); scanf(%d,n);printf(n是%d位数,fun(n));}二叉树代码实现
#include stdio.h
#include stdlib.h
#define MaxSize 50
typedef char ElemType;
typedef struct node
{ElemType data;struct node *lchild;struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *b,char *str) //由str串创建二叉链
{BTNode *St[MaxSize],*pNULL;int top-1,k,j0;char ch;bNULL; //建立的二叉树初始时为空chstr[j];while (ch!\0) //str未扫描完时循环{switch(ch){case (:top;St[top]p;k1;break; //为左节点case ):top--;break;case ,:k2;break; //为右节点default:p(BTNode *)malloc(sizeof(BTNode));p-datach;p-lchildp-rchildNULL;if (bNULL) //p指向二叉树的根节点bp;else //已建立二叉树根节点{switch(k){case 1:St[top]-lchildp;break;case 2:St[top]-rchildp;break;}}}j;chstr[j];}
}void DispBTNode(BTNode *b)
{if(b!NULL){printf(%c,b-data);if(b-lchild!NULL||b-rchild!NULL){printf(();DispBTNode(b-lchild);if(b-rchild!NULL) printf(,);DispBTNode(b-rchild);printf());}}
}
int BTHeight (BTNode *b)
{int lchildh,rchildh;if(bNULL)return(0);else{lchildhBTHeight(b-lchild);rchildhBTHeight(b-rchild);return(lchildhrchildh)?(lchildh1):(rchildh1);}} BTNode * FindNode(BTNode *b,ElemType x) {BTNode *p;if(bNULL)return NULL;else if (b-datax)return b;else {pFindNode(b-lchild,x);if(p!NULL)return p;elsereturn FindNode(b-rchild,x);}}BTNode *LchildNode(BTNode *p){return p-lchild;}BTNode *RchildNode(BTNode *p){return p-rchild;}void PreOrder(BTNode *b){if(b!NULL){printf(%c,b-data);PreOrder(b-lchild);PreOrder(b-rchild);}}void InOrder(BTNode *b){if(b!NULL){PreOrder(b-lchild);printf(%c,b-data);PreOrder(b-rchild);}}void PostOrder(BTNode *b){if(b!NULL){PostOrder(b-lchild);PostOrder(b-rchild);printf(%c,b-data);}}int Nodes(BTNode *b){if(bNULL) return 0;else return Nodes(b-lchild)Nodes(b-rchild)1;}void Displeaf(BTNode *b){if(b!NULL){if(b-lchildNULLb-rchildNULL)printf(%c,b-data);Displeaf(b-lchild);Displeaf(b-rchild);}}int Level(BTNode *b,ElemType x,int h){int l;if(bNULL) return (0);else if(b-datax)return (h);else{// 修改这里在左右子树中查找时都增加层级l Level(b-lchild, x, h 1);if (l ! 0)return (l);elsereturn (Level(b-rchild, x, h 1));}}
void Lnodenum (BTNode *b,int h,int k,int n)
{if(bNULL)return;else{if(hk) n;else if(hk){Lnodenum(b-lchild,h1,k,n); Lnodenum(b-rchild,h1,k,n);}}
}
bool Like(BTNode *b1,BTNode *b2)
//b1和b2两二叉树相似时返回true否则返回false
{bool like1,like2;if(b1NULLb2NULL)return true;else if(b1NULL||b2NULL)return false;else {like1Like(b1-lchild,b2-lchild);like2Like(b1-lchild,b2-lchild);return (like1like2);}
}
bool ancestor (BTNode *b,ElemType x)
{if(bNULL)return false;//节点b的左右孩子节点的data域为x else if (b-lchild!NULLb-lchild-datax||b-rchild!NULLb-rchild-datax){printf(%c,b-data);return true;}//若左右孩子为true else if(ancestor(b-lchild,x)||ancestor(b-rchild,x)){printf(%c,b-data);return true;}else return false;
}int main()
{BTNode *b,*p,*lp,*rp,*b1,*b2;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));CreateBTNode(b1,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));CreateBTNode(b2,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));printf(\n);printf( 输出二叉树:);DispBTNode(b);printf(\n);printf( 输出二叉树的高度:%d,BTHeight(b));printf(\n);printf( 查找H节点:);pFindNode(b,H);if (p!NULL){lpLchildNode(p);if (lp!NULL)printf(左孩子为%c ,lp-data);elseprintf(无左孩子 );rpRchildNode(p);if (rp!NULL)printf(右孩子为%c,rp-data);elseprintf(无右孩子 );}elseprintf( 未找到);printf(\n);printf( 先序遍历);PreOrder(b);printf(\n);printf( 中序遍历);InOrder(b);printf(\n);printf( 后序遍历);PostOrder(b);printf(\n);printf( 二叉树的总结点数%d,Nodes(b));printf(\n);printf( 二叉树所有的叶子结点);Displeaf(b);printf(\n);ElemType X;int h; printf( 输入要查找的结点值); scanf(%c,X); hLevel(b,X,1);if(h0)printf( b不存在%c结点\n,X);else printf( 在b中%c结点的层次为%d\n,X,h);printf(\n); int k ;//第几层printf( 求节点数的层数为); scanf(%d,k);int n 0;//有几个结点 Lnodenum(b, 1, k, n);printf( 第%d的结点个数是%d, k, n);printf(\n);printf( 判断b1和b2是否相似\n);bool result;resultLike(b1,b2);if (result)printf( The two binary trees are similar.\n);elseprintf( The two binary trees are not similar.\n);char ZN;printf( 求N的祖先结点为:);//scanf(%c,Z);ancestor(b,Z); return 0;
}
