这里写目录标题
一：三元组二：顺序表三：单链表四：约瑟夫环(链表)五：顺序栈链栈：进制转换：（链栈实现）链队列：循环队列kmp算法bf算法树邻接表邻接矩阵遍历查找排序一：三元组
#include<stdio.h>#include<stdlib.h>#define Time 1000 typedef int Status; typedef Status *Triplet;//初始化 输入 void InitTriplet(Triplet *T, Status v1, Status v2, Status v3);//销毁三元组void DestroyTriplet(Triplet *T);//返回第i个位置的的元素 void Get(Triplet T, Status i);//改变第i个位置的元素的值 void Put(Triplet *T, Status i, Status e);//判断是否升序排列 void isAscending(Triplet T);//返回最大值 void Max(Triplet T);//列表函数 void Show();//逻辑函数列表 void Logic(Triplet *T, char key);//判断是否有数据输入 void isTrue(Triplet T);//主函数 int main(){char key;Triplet T = NULL;while(1){Show();scanf("%c", &key);Logic(&T, key);} } void isTrue(Triplet T){if(T==NULL){printf("\n抱歉 未分配内存\n");exit(0);}}void Show(){system("cls"); printf("\n0.请输入三个数 ！"); printf("\n1.获取第i个位置的元素值");printf("\n2.判断三元组是否为升序排列");printf("\n3.返回三元组中最大值");printf("\n4.改变第i个位置的元素值");printf("\n5.操作结束\n");printf("\n请输入选择！\n"); }void PrintTriplet(Triplet T){isTrue(T);printf("第一个元素为 ：%d\n", *T);printf("第二个元素为 ：%d\n", *(T+1));printf("第三个元素为 ：%d\n", *(T+2));}void InitTriplet(Triplet *T, Status v1, Status v2, Status v3){*T = (Status*)malloc(3*sizeof(Status));(*T)[0] = v1;(*T)[1] = v2;(*T)[2] = v3;}void DestroyTriplet(Triplet *T){isTrue(*T);if(NULL != *T){free(*T);*T = NULL; }}void Get(Triplet T, Status i){isTrue(T);if(i >= 0&&i<=3){printf("第%d个元素是%d\n", i, T[i - 1]);}else{printf("抱歉，你输入的数不在三元组范围");}}void Put(Triplet *T, Status i, Status e){isTrue(*T);if(i >= 0&&i<=3){**(T + i - 1) = e;printf("您改变第%d个位置的元素为%d\n", i, e);}else{printf("抱歉，你输入的数不在三元组范围");}}void isAscending(Triplet T){isTrue(T);if(T[0] < T[1] && T[1] < T[2]){printf("\n该三元组是升序排列\n");}else{printf("\n该三元组不是升序排列\n");} }void Max(Triplet T){isTrue(T);int i;i = T[0] > T[1]?T[0] : T[1];i = i > T[2]?i : T[2]; printf("\n三元组中最大值是%d\n", i);}void Logic(Triplet *T, char key){switch(key){case '0':printf("\n请输入三元组"); int i, j, k;scanf("%d %d %d", &i, &j, &k);InitTriplet(T, i, j, k);printf("\n初始化完成");printf("\n您初始化的数据为 %d %d %d\n", i, j, k);_sleep(Time);break; case '1':printf("\n您想获得第几个位置的元素？\n");printf("请输入\n");int m;scanf("%d", &m);Get(*T, m); _sleep(Time);break;case '2':isAscending(*T);_sleep(Time);break;case '3':Max(*T);_sleep(Time);break;case '4':printf("您想改变第几个位置的元素？\n");scanf("%d", &i);printf("改变为多少？\n");scanf("%d", &m); Put(T, i, m);system("cls"); printf("您已经改变第%d个元素为%d", i, m);_sleep(Time);break;case '5':printf("操作结束！");_sleep(Time);break;} }
二：顺序表
head：
#include<stdio.h>#include<stdlib.h>#include<string.h>#define MaxSize 100#define ElemType int#define Status inttypedef struct{ElemType data[MaxSize];int length; }SqList;Status InitList(SqList &L);bool CreateList(SqList &L, int n);bool InsertList(SqList &L, int i, ElemType e);bool ListDelete(SqList &L, int i);int LocateElem(SqList L, ElemType e);void ClearList(SqList &L);void PrintList(SqList L);void Create(SqList &L);void Insert(SqList &L);void Delete(SqList &L);void Search(SqList L);void menu();void Reverse(SqList &l); void qianqu(SqList l);void houji(SqList l);
main：t;t /9[9t 他9、【
#include "head.h"/* run this program using the console pauser or add your own getch, system("pause") or input loop */int main(int argc, char** argv) {SqList L; int choice;InitList(L);while (1){menu();printf("请输入序号：\n");scanf("%d", &choice);switch (choice){case 1:Create(L); break;case 2:Insert(L); break;case 3:Delete(L); break;case 4:Search(L); break;case 5:PrintList(L); break;case 6:ClearList(L); break;case 7:break;case 8:Reverse(L);break;case 9:qianqu(L);break;case 10:houji(L); break;}}return 0;}
函数：
#include "head.h"#include<stdio.h>#include<stdlib.h>#include<string.h>#define MaxSize 100#define ElemType int#define Status intStatus InitList(SqList &L){memset(L.data, 0, sizeof(L));L.length = 0;return 0;}//初始化bool CreateList(SqList &L, int n){if (n<0 || n>MaxSize){return false;}for (int i = 0; i<n; i++){scanf("%d", &L.data[i]);L.length++;}return true;}//插入值 bool InsertList(SqList &L, int i, ElemType e){if (i<1 || i>L.length + 1||L.length >= MaxSize){printf("无效\n");return false;}for (int j = L.length; j >= i; j--)//位置i及之后元素后移{L.data[j] = L.data[j - 1];}L.data[i - 1] = e;L.length++;return true;}//删除函数 bool ListDelete(SqList &L, int i){if (i<1 || i>L.length){printf("无效\n");return false;}for (int j = i; j <= L.length - 1; j++){L.data[j - 1] = L.data[j];}L.length--;return true;}//查找值int LocateElem(SqList L, ElemType e){for (int i = 0; i<L.length; i++){if (L.data[i] == e)return i + 1;}return 0;}void Reverse(SqList &l){int i,j,k;for(i=0,j=l.length-1;i<=j;i++,j--){k=l.data[i];l.data[i]=l.data[j];l.data[j]=k;}} //清空顺序表void ClearList(SqList &L) {L.length = 0;}//输出有元素void PrintList(SqList L){printf("所有元素:");for (int i = 0; i<L.length; i++){printf("%d ", L.data[i]);}printf("\n");}//创建顺序表函数void Create(SqList &L){int n; bool flag;L.length = 0;printf("请输入表的长度");scanf("%d", &n);printf("请输入%d个数:", n);flag = CreateList(L, n);if (flag) {printf("创建成功\n");PrintList(L);}else printf("输入无效\n");}//插入函数 void Insert(SqList &L){int place; ElemType e; bool flag;printf("请输入要插入的位置及元素:\n");scanf("%d%d", &place, &e);flag = InsertList(L, place, e);if (flag){printf("插入成功\n");PrintList(L);}}//删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果void Delete(SqList &L){int place; bool flag;printf("请输入要删除的位置(从1开始):\n");scanf("%d", &place);flag = ListDelete(L, place);if (flag){printf("删除成功\n");PrintList(L);}}//查找函数 void Search(SqList L){ElemType e; int flag;printf("请输入要查找的值:\n");scanf("%d", &e);flag = LocateElem(L, e);if (flag){printf("该元素为:%d\n", L.data[e-1]);}elseprintf("未找到该元素\n");}void qianqu(SqList l){printf("请输入你要查找哪个元素的前驱");int next,x;scanf("%d",&x);for(int i=0;i<l.length;i++){if(l.data[i]==x){if(i==0){printf("该元素没有前驱\n");return; }else{next=l.data[i-1];printf("前驱为%d\n",next);return;}}}printf("无该元素\n"); }void houji(SqList l){printf("请输入你要查找哪个元素的后继");int next,x;scanf("%d",&x);for(int i=0;i<l.length;i++){if(l.data[i]==x){if(i==l.length-1){printf("该元素没有后继");return; }else{next=l.data[i+1];printf("后继为%d\n",next);return;}}}printf("无该元素\n"); }//菜单void menu(){printf("1.创建 ");printf("2.插入 "); printf("3.删除\n\n"); printf("4.查找 "); printf("5.输出 "); printf("6.清空\n\n"); printf("7.退出 ");printf("8.倒置 ");printf("9.前驱\n\n");printf("10.后继\n");}
三：单链表
#include<stdio.h>#include<stdlib.h>#define OK 1#define TURE 1#define FALSE -1#include <string.h>typedef struct Node{int data;struct Node *next;}Node,*LinkList;int ListInit(LinkList *L){*L=(LinkList)malloc(sizeof(Node));(*L)->next=NULL;return OK;} LinkList *Create(LinkList *L){Node *r,*s;int c,n;int i;*L=(LinkList)malloc(sizeof(Node));r=*L;printf("你要输入多少个数:\n");scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&c);s=(LinkList)malloc(sizeof(Node));s->data=c;s->next=NULL;r->next=s;r=s;}return L;}//输出链表void PrintList(LinkList L){Node *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}//获取长度int GetLength(LinkList L){Node *p;int count=0;p=L->next;while(p!=NULL){count++;p=p->next;}return count;}void Getdata(LinkList L){int x;printf("请输入你要查找的值");scanf("%d",&x); Node *p;int count=0;p=L->next;while(p!=NULL){if(p->data==x){printf("该值在第%d位\n",count+1);return;}count++;p=p->next;}printf("没有找到该值\n");}//判断是否为空 void ListEmpty(LinkList L){Node *p;p=L->next;if(p==NULL)printf("为空\n");elseprintf("不为空\n");}//获取元素int Getelem(LinkList L,int i,int *e){Node *p;p=L->next;int j=1;while(p!=NULL&&j<i){p=p->next;j++;}if(p==NULL||j>i)return -1;*e=p->data;return OK;}//插入元素int ListInsert(LinkList *L,int i,int e){//在单链表L中第i个位置插入eNode *p,*s;int j=0;p=*L;while(p!=NULL&&j<i-1){//找到i-1个结点p=p->next;j++;}if(j!=i-1)return FALSE;//未找到插入位置，出错处理s=(LinkList)malloc(sizeof(Node));//生成新结点s->data=e;s->next=p->next;//插入新结点p->next=s;return TURE;}//删除元素int ListDelete(LinkList *L,int i,int *e){Node *p,*r;int j=0;p=*L;while(p->next!=NULL&&j<i-1){p=p->next;j++;}if(j!=i-1)return FALSE;r=p->next;p->next=p->next->next;*e=r->data;free(r);return TURE;}//查找元素 void houji(LinkList L){int x;printf("请输入你要查找哪个值的后继");scanf("%d",&x); Node *p;int count=0; p=L->next;while(p!=NULL){if(p->data==x){p=p->next;printf("该值的后继为%d\n",p->data);return;}count++;p=p->next;}printf("没有找到该值\n");}void qianqu(LinkList L){int x;printf("请输入你要查找哪个值的前驱");scanf("%d",&x); Node *p;int count=0; p=L->next;while(p!=NULL){if(p->next->data==x){//p=p->next;printf("该值的前驱为%d\n",p->data);return;}count++;p=p->next;}printf("没有找到该值\n");}void Reverse(Node * l) {Node * h, *u, *tmp; h = NULL; u = l->next;while (u){tmp = u->next;u->next = h;h = u;u = tmp;}l->next = h;PrintList(l);printf("\n"); }int main(int argc, char** argv) {LinkList L;int choice;do{printf("1.创建链表\n2.初始化链表\n3.打印链表\n4.输出链表长度\n5.判断是否为空\n6.获取元素\n7.插入元素\n");printf("8.删除元素\n9.前驱\n10.后继\n11.查找元素\n12.倒置\n13.思考题1（求倒数几位）\n14.思考题2（整体左移）\n");printf("15.思考题3（求最大值）\n16.思考题4（查找共同后缀）\n"); printf("\n请输入你的选择:\n");scanf("%d",&choice);switch(choice){system("cls");case 1:{L=*Create(&L);break;}case 2:{if(ListInit(&L)==OK)printf("success\n");elseprintf("flase\n");break;}case 3:{PrintList(L);printf("\n");break;}case 4:{int count;count=GetLength(L);printf("长度为:%d\n",count);break;}case 5:{ListEmpty(L);break;}case 6:{int i;int e;printf("请问你想要第几个数:\n");scanf("%d",&i);if(Getelem(L,i,&e)==OK)printf("第%d个数是:%d\n",i,e);elseprintf("没有这个数\n");break;}case 7:{int i,e;printf("请输入你要插入的位置和数据:\n");scanf("%d%d",&i,&e);if(ListInsert(&L,i,e)==TURE)printf("插入成功\n");elseprintf("插入失败");break;}case 8:{int i,e;printf("你想要删除第几个元素:\n");scanf("%d",&i);if(ListDelete(&L,i,&e)==TURE)printf("删除成功\n");elseprintf("删除失败\n");printf("第%d个数是:%d\n",i,e);break;}case 9:{qianqu(L);break;}case 10:{houji(L);break;}case 11:{Getdata(L);break;}case 12:{Node *p;p=L->next;if(p==NULL)printf("链表为空不能倒置\n");elseReverse(L);break;}case 13:{//便利一遍数组的同时将值储存在字符数组中并记录数组长度，再调用数组直接得到倒数的值 printf("请问要查询倒数多少位的数值");int q;scanf("%d",&q);char a[10000] [10];Node *p;p=L->next;int i=1;while(p!=NULL){itoa(p->data,a[i],10);p=p->next;i++;}printf("%s\n",a[i-q]);break;} case 14:{//将链表前n位的值直接移到链表最后即可 printf("请输入将链表向左移多少位：");int n;scanf("%d",&n);Node *p,*flag;p=L;flag=L;while(flag->next!=NULL){flag=flag->next;}flag->next=L->next;//找到尾节点让他指向第一个节点 for(int i=0;i<n;i++){p=p->next; }L->next=p->next; //将头节点指向第n+1个节点 p->next=NULL;//将第n个节点指向NULLPrintList(L);break;//2n*2——o（1？） }case 15:{//最大值 Node *p=L->next;int max=p->data;while(p!=NULL){if(p->data>max){max=p->data;}p=p->next;}printf("%d\n",max);break;}case 16:{//输入两个链表后倒置，然后用双指针想后遍历，找到第一个不同的值，返回这个值的前一个位置的值即可 LinkList p,q;p=*Create(&p);Reverse(p);q=*Create(&q);Reverse(q);Node *flag1=p,*flag2=q;while(flag1->next->data==flag2->next->data){flag1=flag1->next;flag2=flag2->next;}printf("起始位置的值为：%d\n",flag1->data);break;}default:printf("输入错误，请重新输入\n");break;system("pause");}}while(choice!=0);}
四：约瑟夫环(链表)
#include<stdio.h>#include<string.h>#include<stdlib.h> typedef int ElemType;typedef struct node{ElemType data;struct node *next;}LNode;void Josephus(int n,int m,int k){LNode *q,*p;int i;p=(LNode *)malloc(sizeof(LNode));//申请一个新节点q=p;for(i=1;i<n;i++) //for循环吧n-1个人排上号{q->data=k;//第一个节点为k，即从k开始k=k%n+1; //避免k=n的情况q->next=(LNode *)malloc(sizeof(LNode));q=q->next;//q一直指向最新的节点}//q指向第n个人，k也是第n个数q->next=p; //尾指针指向头结点，形成循环单链表printf("依次淘汰的人\n");while(p->next!=p) //判断是否剩余一个人{for(i=1;i<m;i++){q=p; //当从循环出来q在m-1处p=p->next;//当从循环出来的时候，p节点在m位置处}q->next=p->next;//q指向m+1的节点，即淘汰第m个人printf("%d ",p->data);free(p);p=q->next;}printf("\n剩的最后一人\n");printf("%d",p->data);}int main(){int n,m,k;printf("输入人数n，总报数m，开始号k\n");scanf("%d%d%d",&n,&m,&k);Josephus(n,m,k);return 0;}
五：顺序栈
#include <stdio.h>#include <stdlib.h>#include<string.h> #include <iostream>#include <malloc.h>#include <windows.h>#define STACK_INIT_SIZE100#define STACK_INCREMENT_SIZE 10 typedef int ElemType;typedef struct{ElemType *base; ElemType *top;int stacksize;}OrderStack;void InitStack(OrderStack &s){s.base=(ElemType*)malloc(sizeof(OrderStack)); if (!s.base)exit(0); s.top=s.base;s.stacksize=STACK_INIT_SIZE;}void GetTop(OrderStack s){ElemType e;if (s.top==s.base){printf("无元素");return;}else{printf("%d",*(s.top-1));}return;}void Push(OrderStack &s,ElemType e){if ((s.top-s.base)>=s.stacksize){s.base=(ElemType *)realloc(s.base,(s.stacksize+STACK_INCREMENT_SIZE)*sizeof(ElemType));if (!s.base){return;}s.top=s.base+s.stacksize;s.stacksize=s.stacksize+STACK_INCREMENT_SIZE;printf("%-6顺序栈长度不足!!!开始扩充元素--> %d\n",s.stacksize);}*s.top=e;s.top++;}void Pop(OrderStack &s){ElemType e;if (s.top==s.base){return ;}else{s.top--;e=*s.top;return ;}}void Conversion(OrderStack &s){int x,y;InitStack(s);printf("\n请输入十进制数：");scanf("%d",&x);printf("\n请输入要转化为什么进制：");scanf("%d",&y); printf("转换为%d进制数为：\n",y);while(x!= 0){Push(s,x%y);x=x/y;}while(s.top != s.base){s.top--;printf("%d",*s.top);}return ;}int main(){OrderStack s;printf("请输入选择：\n1.初始化 2.输入 3.输出 4.输出栈顶元素 5.删除栈顶元素 0.退出 6.进制转换\n"); while(1){int b;scanf("%d",&b);switch (b){case 1:{InitStack(s);printf("初始化成功\n");break;}case 2:{printf("请输入个数：");int y;scanf("%d",&y);for (int i=1;i<=y;i++){int x;scanf("%d",&x);Push(s,x);}break;}case 3:{int *flag=s.top;while(flag>s.base){printf("%d ",*(flag-1));flag--;}printf("\n");break;}case 4:{GetTop(s);printf("\n");break;}case 5:{Pop(s); printf("删除成功\n"); break;}case 6:{Conversion(s);break;}case 0:{exit(0);break;}}}}
链栈：
#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef struct node{int number;struct node *next;}node;typedef struct stack{node *top;int count;}stack;void initstack (stack *l){l->top=(node *)malloc(sizeof(node));l->top->next=NULL;l->count=0;}void push (stack *s,int x){node *l=(node *)malloc(sizeof(node)); l->number=x;l->next=s->top;s->top=l;s->count++; }void deletepop(stack *l){node *p;p=l->top;l->top=l->top->next;printf("%d\n",p->number);l->count--;} void printf(stack *l){if(l->count==0){printf("空\n");}else{node *p=l->top;while(p->next){printf("%d ",p->number);p=p->next;}printf("\n");}}void deleteall(stack *s){node *p,*q;p=s->top;while(p){q=p;p=p->next;free(q);} s->count=0;printf("删除成功\n");}void length(stack *s){printf("%d\n",s->count);}void gettop(stack *s){if (s->top->next==NULL)printf("栈空");elseprintf("%d",s->top->number); }int main(){node *p;stack l; initstack(&l); printf("1.初始化栈\n2.输入栈\n3.输出栈的长度\n4.输出栈顶元素\n5.输出栈\n");printf("6.输出栈顶元素（删除）\n7.删除整个栈\n");while(1){printf("请输入你要的选择：\n");int v;scanf("%d",&v);switch(v){case 1:{initstack(&l); printf("初始化成功\n");break;}case 2:{printf("请问要输入几位数值：\n");int x;scanf("%d",&x);for(int i=0;i<x;i++){printf("请输入值：\n");int y;scanf("%d",&y);push(&l,y);}break;}case 3:{length(&l);break;}case 4:{gettop(&l);break;}case 5:{printf(&l);break;}case 6:{deletepop(&l);break;}case 7:{deleteall(&l);break;}}}}
进制转换：（链栈实现）
#include <stdio.h>#include <stdlib.h>#include <string.h>const char f[]="0123456789ABCDEF";typedef struct StackNode {char data;struct StackNode *next; }SqStack,*LinkStack;void InitStack(LinkStack &S){S = (SqStack*)malloc(sizeof(SqStack));S = NULL;}int Push(LinkStack &S,char e){SqStack* p;p = (SqStack*)malloc(sizeof(SqStack));p->data = e;p->next = S;S = p;return 0; }void Pop(LinkStack &S){if(S==NULL){printf("栈空！");}else{SqStack* p;printf("%c",S->data);p = S;S = S->next;free(p);}}void Decimal(LinkStack S){int n,m,i=0;printf("请输入一个十进制数： ");scanf("%d",&n);while(1)if(getchar()=='\n')break;printf("请输入要转的进制： ");scanf("%d",&m);while(n){Push(S,f[n%m]);n=n/m;i++;}printf("结果：");while(i--) Pop(S);}int main(){LinkStack S;InitStack(S);Decimal(S); return 0;}
括号匹配：（顺序栈实现）
#include<stdio.h> #include<malloc.h> #include<process.h>#include<string.h> #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;typedef double SElemType;#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{SElemType *base; SElemType *top; int stacksize;}Stack;Status InitList_stack (Stack &s) {s.base = (SElemType*)malloc( STACK_INIT_SIZE*sizeof(SElemType));if (!s.base ) exit(0);s.stacksize = STACK_INIT_SIZE;s.top = s.base;return OK;}Status EmptyStack (Stack s) {if(s.base == s.top) return TRUE;else return FALSE;}//Status PushStack(Stack &s , SElemType e ){if(s.stacksize<(s.top-s.base) )return ERROR;if(s.stacksize==(s.top-s.base) )s.base = (SElemType*)malloc(( s.stacksize+STACKINCREMENT)*sizeof(SElemType));*(s.top) = e;s.top++;return OK;}Status GetLength(Stack s){return s.top-s.base;}Status DisplayStack(Stack &s){while(s.base != s.top){printf("%c ",*--(s.top));}printf("\n");}SElemType OutStack(Stack &s ){SElemType e;if(s.top != s.base)e= *(--s.top);return e;}SElemType TopStack(Stack &s ){SElemType e;if(s.top != s.base)e= *(s.top-1);return e;}Status DestroyStack ( Stack s) {if (!s.base) return ERROR; free (s.base); s.base = NULL;s.top = NULL;s.stacksize= 0;return OK;}// DestroyList_Sq int CheckMatch(char *s,Stack* opr_stack){int i= 0; int length = strlen(s);while(i<length){if(s[i]=='('||s[i]==')'||s[i]=='{'||s[i]=='}'||s[i]=='['||s[i]==']'){//如果当前字符是运算符.switch(s[i]){case '(':PushStack(*opr_stack,'(');break;case '[':PushStack(*opr_stack,'[');break;case '{':PushStack(*opr_stack,'{');break;case ')':if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='(')return 0;OutStack(*opr_stack);break;case ']':if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='[')return 0;OutStack(*opr_stack);break;case '}':+if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='{')return 0;OutStack(*opr_stack);break;default:break;}}i++;} if(EmptyStack(*opr_stack)==1) return 1;} int main(){Stack opr_stack;InitList_stack(opr_stack);char s[100] = {0};gets(s); printf("%s",CheckMatch(s,&opr_stack)==1?"匹配":"不匹配");return 0;}
链队列：
#include <stdio.h>#include <stdlib.h>#define TRUE1#define FALSE -1#define OK 1#define ERROR -1#define OVERFLOW -2/* ----单链队列----队列的链式存储结构 ---- */typedef struct Qnode{int date;struct Qnode *next;}QNode,* QueuePtr;typedef struct{QueuePtr head; //队头指针QueuePtr tail; //队尾指针}LinkQueue; /*构造一个空队列 */int InitQueue(LinkQueue *Q){Q->head = Q->tail = (QueuePtr)malloc(sizeof(QNode));if (Q->head == NULL){exit(OVERFLOW);}Q->tail->next = NULL;return OK;}/*销毁队列*/int DestoryQueue(LinkQueue *Q){while(Q->head){Q->tail = Q->head->next;free(Q->head);Q->head = Q->tail;}Q->head = Q->tail = NULL;return OK;}/* 将Q清空空队列 */int ClearQueue(LinkQueue *Q){QueuePtr temp;Q->tail = Q->head->next;while(Q->tail){temp = Q->tail->next; //指向下一个待释放的单元free(Q->tail);Q->tail = temp;}Q->tail = Q->head; //修改队尾指针return OK;}/* ---- 若队列Q为空队列,返回TRUE,否则返回FALSE ---- */int QueueEmpty(LinkQueue Q){if (Q.head == Q.tail && Q.head != NULL){return TRUE;}else{return FALSE;}}/* ---- 返回Q的元素个数,即队列的长度 ---- */int QueueLength(LinkQueue Q){if (Q.head == NULL){return 0;}QueuePtr temp;int count = 0;temp = Q.head->next;while(temp != NULL){temp = temp->next;++count;}return count;}/* ---- 显示当前队列的值从队头到队尾 ---- */void show_queue(LinkQueue Q){QueuePtr temp;temp = Q.head->next;printf(" 当前队列从头到尾：");while(temp != NULL){printf("%d ", temp->date);temp = temp->next;}printf("\n");}/* ---- 若队列不空,则用e返回Q的队头元素,并返回OK, 否则返回ERROR ---- */int GetHead(LinkQueue Q, int *e){if (QueueEmpty(Q) == TRUE){return ERROR;}*e = Q.head->next->date;return OK;}/* ---- 插入元素e为Q的新的对尾元素 ---- */int EnQueue(LinkQueue *Q, int e){if (Q->head == NULL || Q->tail == NULL){return ERROR;}QueuePtr ptr = (QueuePtr)malloc(sizeof(QNode));if (!ptr){exit(OVERFLOW);}ptr->date = e;ptr->next = NULL;Q->tail->next = ptr;Q->tail = ptr;return OK;}/* ---- 若队列不空,则删除Q的队头元素,并用e返回其值,并返回OK,否则返回ERROR ---- */int DeQueue(LinkQueue *Q, int *e){if (Q->head == Q->tail){return ERROR;}/* ptr为临时变量 */QueuePtr ptr = (QueuePtr)malloc(sizeof(QNode));//head->node1->node2->tail;// ptr//head->node2->tailptr = Q->head->next;*e = ptr->date;Q->head->next = ptr->next;if (Q->tail == ptr){Q->head = Q->tail;}free(ptr);return OK;}int main(){int i; //循环变量int count; //计数变量int outque; //出队元素值LinkQueue Q;/* 初始化队列 */InitQueue(&Q);/* 插入10个元素 */printf("________________入队10个元素________________\n\n");for (i = 0; i < 10; i++){/* 入队 */EnQueue(&Q, i);/* 获得当前队列中元素个数 */count = QueueLength(Q);printf("%2d 入队_当前队列中元素个数：%2d",i, count);show_queue(Q);}printf("________________出队5个元素________________\n\n");for (i = 0; i < 5; i++){/* 出队 */DeQueue(&Q, &outque);/* 获得当前队列中元素个数 */count = QueueLength(Q);printf("%2d 出队_当前队列中元素个数：%2d", outque, count);show_queue(Q);}/* 获得当前队头值 */GetHead(Q, &outque);printf("\n当前队头为：%d\n", outque);printf("________________清空队列_________________\n\n");ClearQueue(&Q);count = QueueLength(Q);printf("当前队列中元素个数：%2d", count);show_queue(Q);printf("________________销毁队列_________________\n\n");DestoryQueue(&Q);count = QueueLength(Q);printf("当前队列中元素个数：%2d\n\n", count);return 0;}
循环队列
#include<stdio.h>#include<iostream>#include<stdlib.h>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAXQSIZE 5 typedef int Status;typedef int QElemType;typedef struct {QElemType *base; int front; int rear; }SqQueue;void menu();Status InitQueue(SqQueue &Q);Status QueueLength(SqQueue Q);Status EnQueue(SqQueue &Q,QElemType e);Status DeQueue(SqQueue &Q,QElemType &e);Status GetHead(SqQueue Q);int main(){int select;SqQueue Q;QElemType e;menu();while (select!= 0){do{cin>>select;if (select<1||select>5) {cout <<"输入错误！请重试！"<<endl;}} while (select<1||select>5);switch (select){case 1:if(InitQueue(Q)) cout <<"顺序队列初始化成功"<< endl << endl;cout <<"请继续您的选择："<< endl;break;case 2:QueueLength(Q);cout<<"队列长度为："<<QueueLength(Q)<<endl;cout<<"请继续您的选择："<< endl;break; case 3:cout<<"请输入元素"<<endl; cin>>e;if (EnQueue(Q,e)) cout << "该元素入队成功！" << endl;else cout << "该元素入队失败！" << endl;cout << "请继续您的选择：" << endl;break;case 4:if (DeQueue(Q, e)) {cout << "您此时的出队元素为：" <<e<< endl;}elsecout << "此时队列已空!" << endl;cout << "请继续您的选择：" << endl;break;case 5:if(GetHead(Q)){cout<<"对头元素为："<<GetHead(Q)<<endl;}else{cout<<"此时队列已空!"<<endl;}cout << "请继续您的选择：" << endl;break;default:break;}}}void menu(){cout<<"*********************"<<endl;cout<<"**** 1.初始化 ******"<<endl; cout<<"**** 2.求队长 ******"<<endl; cout<<"**** 3.入队列 ******"<<endl; cout<<"**** 4.出队列 ******"<<endl; cout<<"**** 5.取队头 ******"<<endl; }Status InitQueue(SqQueue &Q){Q.base = (QElemType*)malloc(MAXQSIZE *sizeof (QElemType));if(!Q.base) exit (OVERFLOW);Q.front = Q.rear = 0;return OK;}Status QueueLength(SqQueue Q){return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; }Status EnQueue(SqQueue &Q, QElemType e){if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){if(Q.rear==Q.front)return ERROR; e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}Status GetHead(SqQueue Q){if (Q.front == Q.rear) return ERROR;else{return Q.base[Q.front];}return OK;}
kmp算法
当pos=x时，是从x位开始找，知道到的值所在位次依然不变
比如pos=2时，
输入：12345，1，输出：找不到
输入：12345，2，输出：2
#include <stdio.h>#include <string.h>void Next(char *string,int *next){int i=1,j=0;next[1]=0;while(i<strlen(string)){if(j==0||string[i]==string[j]){i++;j++;next[i]=j;}else{j=next[j];}}}int find(char *string,char *pattern,int pos){int i=1,j=1;int next[1000];Next(pattern,next);while(i<=strlen(string)&&j<=strlen(pattern)){if(j==0||string[i-1]==pattern[j-1]){//当从pattern【0】开始存时要减一，若pattern或者string【0】存的是长度时则不减i++;j++;}else{j=next[j];}}if(j>strlen(pattern)){return i-strlen(pattern);}return -1;}int main(){char string[1000];char pattern[1001];scanf("%s %s",string,pattern);int flag=find(string,pattern,1);printf("%d",flag);}
bf算法
#include <stdio.h>#include <string.h>int main(){char string[1000];char pattern[1001];int i=1,j=1;scanf("%s %s",string,pattern);while(i<=strlen(string)&&j<=strlen(pattern)){if(string[i]==pattern[j]){i++;j++;}else{i=i-j+2;j=1;}}if(j>strlen(pattern)){printf("%d",i-strlen(pattern));}else{printf("-1"); }}
树
#include <cstdlib>#include <stdio.h>typedef struct node{//树的结点int data;struct node* left;struct node* right;} Node;typedef struct queue{Node *x;struct queue *next;}queue;typedef struct dui{queue *head;queue *tail;};void push(dui *q,Node *tool){queue *p;p=(queue *)malloc(sizeof(queue));p->x=tool;q->tail->next=p;q->tail=p;p->next=NULL;}Node *pop(dui *q){queue *p=(queue *)malloc(sizeof(queue));Node *s=(Node *)malloc(sizeof(Node));p=q->head->next;q->head->next=p->next;if(q->tail==p){q->head=q->tail;}s=p->x;return s; }void createqueue(dui *q){q->head=q->tail=(queue *)malloc(sizeof(queue)); q->head->next=NULL;}void xian(Node *root){if(root==NULL){return;}printf("%d",root->data);xian(root->left);xian(root->right);}void zhong(Node *root){if(root==NULL){return;}zhong(root->left);printf("%d",root->data);zhong(root->right);}void hou(Node *root){if(root==NULL){return;}hou(root->left);hou(root->right);printf("%d",root->data);}int getdigui(Node *t,int &ans){if(t->left!=NULL&&t->right!=NULL) ans++;if(t->left) getdigui(t->left,ans);if(t->right) getdigui(t->right,ans);return ans;}int getdigui2(Node *t,int &ans){if((t->left!=NULL&&t->right==NULL)||(t->left==NULL&&t->right!=NULL)) ans++;if(t->left) getdigui(t->left,ans);if(t->right) getdigui(t->right,ans);return ans;}void create(Node **root){int flag;scanf("%d",&flag);if(flag==-1){*root=NULL;return;}*root =(node *)malloc(sizeof(node));(*root)->data=flag;create(&((*root)->left));create(&((*root)->right));} int depth(Node *root){if(root==NULL){return 0;}else return 1+(depth(root->left)>depth(root->right)?depth(root->left):depth(root->right));}int countall(Node *root){if(root==NULL){return 0;}else{return 1+(countall(root->left)+countall(root->right));}}int countye(Node *root){if(root==NULL){return 0;}if(root->left==NULL&&root->right==NULL){return 1;}return countye(root->left)+countye(root->right);}int empty(dui *q){if (q->head == q->tail){return 0;}else{return 1;}}void exchange(Node *root){Node *k;if(root!=NULL){exchange(root->left);exchange(root->right);k=root->left;root->left=root->right;root->right=k;}}void cengci(dui *q,Node *root){if(root!=NULL){push(q,root);}while(empty(q)!=0){Node *s=pop(q);printf("%d ",s->data);if(s->left!=NULL){push(q,s->left);}if(s->right!=NULL){push(q,s->right);}}printf("\n");} int main(){Node *root=(Node*)sizeof(Node);dui q;while(1){printf("1.创建二叉树\n2.节点总数\n3.叶子节点数\n4.深度\n5.交换左右子树\n6-8.先，中，后序遍历\n");int n;scanf("%d",&n);switch (n){case 1:{create(&root);break;}case 2:{printf("%d\n",countall(root));break;}case 3:{printf("%d\n",countye(root)); break;}case 4:{printf("%d\n",depth(root));break;}case 5:{exchange(root);break;}case 6:{xian(root);break;}case 7:{zhong(root);break;}case 8:{hou(root);break;}case 9:{createqueue(&q);break;}case 10:{cengci(&q,root);break;}case 11:{int ans=0;printf("%d\n",getdigui(root,ans));break;}case 12:{int ans=0;printf("%d\n",getdigui2(root,ans));break;}}}}
邻接表
#include <iostream>using namespace std;#define MAXVERTEX 100 //最大顶点数typedef char vertextype; //定义顶点的存储类型typedef int arctype; //定义边的权值类型typedef struct ArcNode //边表节点{int adjvex; //邻接点域，存储该顶点对应的下标arctype wigth; //用于存储权值struct ArcNode *next; //链域，指向下一个邻接点}ArcNode;typedef struct VertexNode //顶点表节点{vertextype data; //存储顶点数据的信息ArcNode *firstarc; //边表头指针}VertexNode, AdjList[MAXVERTEX];typedef struct{AdjList adjlist; //定义邻接表int numvertex; //当前邻接表的顶点数int numarc; //当前邻接表的边数}GraphAdjList;//建立图的邻接表void CreateAdjListGraph(GraphAdjList &G){ArcNode *e;cin >> G.numvertex; //输入当前图的顶点数cin >> G.numarc; //输入当前图的边数for(int i = 0; i < G.numvertex; i++) //建立顶点表{cin >> G.adjlist[i].data; //输入顶点信息G.adjlist[i].firstarc = NULL; //将表边指针置为空}for(int k = 0; k < G.numarc; k++){int i, j, w;cin >> i >> j >> w; //输入边两边的顶点和边上的权重e = new ArcNode; //创建一个表边节点指针e->adjvex = j;e->wigth = w;e->next = G.adjlist[i].firstarc;G.adjlist[i].firstarc = e;//因为是无向图，彼此相对称e = new ArcNode; //创建一个表边节点指针e->adjvex = i;e->wigth = w;e->next = G.adjlist[j].firstarc;G.adjlist[j].firstarc = e;}}//打印邻接表void PrintfGraphAdjList(GraphAdjList G){for(int i = 0; i < G.numvertex; i++){ArcNode *p = G.adjlist[i].firstarc;cout << G.adjlist[i].data << '\t';while(p){cout << p->adjvex << ' ' << p->wigth << '\t';p = p->next;}cout << endl;}}int main(){GraphAdjList G;CreateAdjListGraph(G);PrintfGraphAdjList(G);return 0;}
邻接矩阵
#include <bits/stdc++.h>using namespace std;void CreateUDN(AMGraph &G){int x, y;char c1, c2;cin >> G.vexnum >> G.arcnum;memset(G.arcs, 0, sizeof(G.arcs));for(int i=0; i<G.vexnum; i++){cin >> G.vexs[i];}for(int i=0; i<G.arcnum; i++){cin >> c1 >> c2; for(int j=0; j<G.vexnum; j++){if(c1==G.vexs[j])x = j;if(c2==G.vexs[j])y = j;}G.arcs[x][y] = G.arcs[y][x] = 1;//无向图 }}
遍历
邻接表的广度优先遍历 void BFS(ALGraph G, int v){int q[1000];int l = 0, r = 0;printf("%c ", G.vertices[v].data);visited[v] = 1;q[r++] = v;ArcNode* t;while (l < r){t = G.vertices[q[l++]].firstarc;while (t){int index = t->adjvex;if (!visited[index]){visited[index] = 1;printf("%c ", G.vertices[index].data);q[r++] = index;}t = t->nextarc;}}}邻接矩阵的广度优先遍历 void BFS(Graph G, int v){printf("%c ",G.vexs[v]);visited[v]=1;int i=0,j=0;int flag[1000];flag[j++]=v;while(i<j){v=flag[i++];for(int k=0;k<G.vexnum;k++){if(G.arcs[v][k]==1&&visited[k]!=1){visited[k]=1;flag[j++]=k;printf("%c ",G.vexs[k]);}}}}临界矩阵的深度优先遍历 void DFS(Graph G,int v){int i;visited[v] = 1;printf("%c ",G.vexs[v]);for(i = 0; i < G.vexnum ; i++)//遍历该顶点的行，即找与该顶点相连的顶点{if(G.arcs[v][i] ==1 && !visited[i])//找到且未访问DFS(G, i);//继续调用}return;//没找到就返回上一层}邻接表的深度优先遍历void DFS(Graph G,int v){printf("%c",对应的char类型);visit[v]=1;arcnode *p=v.firstarc;while(p){if(visit[p.下标]!=1){DFS(G,p.下标);}p=p->next; }}
查找
#include <stdio.h>#include <string.h>#include <malloc.h>#include <stdlib.h>typedef struct BSTNode{int data;BSTNode *lchild; BSTNode *rchild; }BSTNode, *BSTree;bool Search(BSTree bst, int key, BSTree f, BSTree *p);void InOderTraverse(BSTree bst) {if (NULL != bst){InOderTraverse(bst->lchild);printf("%d ", bst->data);InOderTraverse(bst->rchild);}}static BSTNode* BuyNode(int data) {BSTNode *pTmp = (BSTNode*)malloc(sizeof(BSTNode));if (NULL == pTmp){exit(0);}pTmp->data = data;pTmp->lchild = NULL;pTmp->rchild = NULL;return pTmp;}bool Insert(BSTree *bst, int key){if (NULL == *bst) {*bst = BuyNode(key); return true;}BSTNode *p;if (!Search(*bst, key, NULL, &p)) {BSTNode *pNew = BuyNode(key);if (key < p->data){p->lchild = pNew;}else if (key > p->data) {p->rchild = pNew;}return true; }else{printf("已经有%d这个元素了\n", key);}return false;}bool Search(BSTree bst, int key, BSTree f, BSTree *p) {if (!bst){*p = f;return false;}if (bst->data == key) {*p = bst;return true;}else if (bst->data < key){return Search(bst->rchild, key, bst, p);}return Search(bst->lchild, key, bst, p);}void Search2(BSTree bst,int key){if(bst==NULL){printf("没有找到此元素");}else{if(bst->data==key){printf("%d 已找到此元素\n",bst->data);}if(key>bst->data){printf("%d ",bst->data);Search2(bst->rchild,key);} if(key<bst->data){printf("%d ",bst->data);Search2(bst->lchild,key);} }}void paixushu(){BSTNode *root = NULL;int n;printf("请问要输入几位元素\n");scanf("%d",&n); for(int i=0;i<n;i++){int x;scanf("%d",&x);Insert(&root,x);}printf("此树的中序遍历是：\n");InOderTraverse(root); printf("\n");printf("请问要插入几位元素：\n");int flag;scanf("%d",&flag);for(int i=0;i<flag;i++){int x;scanf("%d",&x);Insert(&root,x);} printf("此树的中序遍历是：\n");InOderTraverse(root);printf("\n");Search2(root,4);return ;}void shaobin(){int a[1000];int length;int key;scanf("%d",&length);for(int i=1;i<=length;i++){scanf("%d",&a[i]);}scanf("%d",&key);a[0]=key;int i;for(i=length;a[i]!=key;i--){}printf("在第%d位\n",i);}void zheban(){int a[1000];int length,i,j,k;int low,mid,high;int key;scanf("%d",&length);for(i=1;i<=length;i++){scanf("%d",&a[i]);}scanf("%d",&key);for(i=0;i<length-1;i++){for(j=0;j<length-1-i;j++){if(a[j]>a[j+1]){k=a[j];a[j]=a[j+1];a[j+1]=a[j];}}}low=1;high=length;while(low<=high){mid=(high+low)/2;if(a[mid]==key){printf("在%d位\n",mid);break;}if(a[mid]<key){low=mid+1;}if(key<a[mid]){high=mid-1;}}}void QuickSort(int *arr, int begin, int end){if(begin >end)return;int tmp = arr[begin];int i = begin;int j = end;while(i != j){while(arr[j] >= tmp && j > i)j--;while(arr[i] <= tmp && j > i)i++;if(j > i){int t = arr[i];arr[i] = arr[j];arr[j] = t;}}arr[begin] = arr[i];arr[i] = tmp;QuickSort(arr, begin, i-1);QuickSort(arr, i+1, end);}void kuai(){int a[1000];int length;scanf("%d",&length);for(int i=0;i<length;i++){scanf("%d",&a[i]);}QuickSort(a,0,length-1);for(int i=0;i<length;i++){printf("%d ",a[i]);}printf("\n");}int main(){while(1){printf("1.哨兵2.折半查找\n3.快速排序4.二叉排序树\n");int flag;scanf("%d",&flag);switch (flag){case 1:{shaobin();break;}case 2:{zheban();break;} case 3:{kuai();break;}case 4:{paixushu();break;}} }}
排序
#include <stdio.h>#include <malloc.h>#include <string.h>void charu(){int a[1000];int x,i,j;scanf("%d",&x);for(i=0;i<x;i++){scanf("%d",&a[i]); } for(i=1;i<x;i++){int temp=a[i];for(j=i-1;j>=0&&a[j]>temp;j--){a[j+1]=a[j];}a[j+1]=temp;}for(i=0;i<x;i++){printf("%d ",a[i]);}}void erfencha(){int a[1000];int length,i,j,x;scanf("%d",&length);for(i=0;i<length;i++){scanf("%d",&a[i]); } for(i=1;i<length;i++){x=a[i];int high=i-1;int low=0;while(low<=high){int m=(low+high)/2;if(x>a[m]){low=m+1;//降序的话就是high=mid-1; }else{high=m-1;}}for(j=i-1;j>high;j--){a[j+1]=a[j]; }a[j+1]=x;}for(i=0;i<length;i++){printf("%d ",a[i]);}}void xuanze(){int a[1000];int length,i,j,x;scanf("%d",&length);for(i=0;i<length;i++){scanf("%d",&a[i]); } for(i=0;i<length-1;i++){for(j=i+1;j<length;j++){if(a[i]>a[j]){x=a[i];a[i]=a[j];a[j]=x;}}}for(i=0;i<length;i++){printf("%d ",a[i]);}}void maopao(){int a[1000];int length,i,j,x;scanf("%d",&length);for(i=0;i<length;i++){scanf("%d",&a[i]); } for(i=0;i<length-1;i++){for(j=0;j<length-i-1;j++){if(a[j]>a[j+1]){x=a[j];a[j]=a[j+1];a[j+1]=x;}}}for(i=0;i<length;i++){printf("%d ",a[i]);} }int main(){}
