2022年数据结构与算法基本程序合集终版

《2022年数据结构与算法基本程序合集终版》由会员分享，可在线阅读，更多相关《2022年数据结构与算法基本程序合集终版（45页珍藏版）》请在装配图网上搜索。

1、数据结构与算法基本程序目录一、线性表及其操作1、尾插法建立一个单链表，并按顺序输出2、单链表的元素查找，按内容查找3、元素插入操作4、按内容元素删除操作5、按位置删除元素6、建立双向链表7、单链表就地逆置8、约瑟夫环问题二、栈及其操作1、建立堆栈2、进栈与出栈3、栈的应用，括号匹配三、队及其操作1、链队列的建立2、入队和出队3、循环队列建立4、循环队列的入队和出队操作四、串及其操作1、串的朴素匹配五、树（二叉树）及其操作1、二叉排序树2、哈夫曼编码六、排序1、冒泡排序2、直接选择排序法一、线性表及其操作/All copyright are preserved by cobby/*尾插法建立一个

2、单链表，并按顺序输出*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/char c;/*数据域，类型为字符型*/struct node*next;/*指针域，类型为本结构体类型*/*L;/*类型重定义，即Node 和*L 和 struct node等价*/main()L l,p,q;/*用指针类型定义三个结点类型的指针*/名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 45 页 -char ch;l=(L)malloc(sizeof(L);/*分配内存空间*/l-c=0;/*为头结点的数据域赋值，值为空*/l-n

3、ext=NULL;/*指明下一个结点目前不存在*/q=l;/*q为游动指针，链表结点的连结要用*/printf(Input a character:n);scanf(%c,&ch);getchar();/此语句用来吸收键盘输入的回车符，没有其它含义 while(ch!=!)/*输入!表示输入结束*/p=(L)malloc(sizeof(L);/*为新输入的数据分配内存空间*/p-c=ch;p-next=NULL;/*新输入的结点在链表的最后，即它的后面没有其它元素*/q-next=p;/*q用于将上一个元素链接至当前新元素*/q=p;/*q自己移到当前最后一个元素，以备继续链接所用*/scan

4、f(%c,&ch);getchar();q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/All copyright are preserved bycobby/*单链表的元素查找，按内容查找*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构

5、*/char c;/*数据域，类型为字符型*/struct node*next;/*指针域，类型为本结构体类型*/*L;/*类型重定义，即Node 和*L 和 struct node等价*/名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 45 页 -main()L l,p,q;/*用指针类型定义三个结点类型的指针*/char ch;int n;l=(L)malloc(sizeof(L);/*分配内存空间*/l-c=0;/*为头结点的数据域赋值，值为空*/l-next=NULL;/*指明下一个结点目前不存在*/q=l;/*q为游动指针，链表结点的连结要用*/printf(Input

6、 a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*输入!表示输入结束*/p=(L)malloc(sizeof(L);/*为新输入的数据分配内存空间*/p-c=ch;p-next=NULL;/*新输入的结点在链表的最后，即它的后面没有其它元素*/q-next=p;/*q用于将上一个元素链接至当前新元素*/q=p;/*q自己移到当前最后一个元素，以备继续链接所用*/scanf(%c,&ch);getchar();q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面

7、还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/*-以上为建立一个单链表-*/printf(nInput a character you wanna findn);scanf(%c,&ch);printf(nthe character you wanna find is%cn,ch);q=l-next;/*q移至头结点的后一个元素，即实际第一个数据点*/n=1;/位置计数器 while(q!=NULL)/*若 q 不为空，即该结点

8、存在*/名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 45 页 -if(q-c=ch)/*字符匹配*/printf(character found in position%dn,n);q=q-next;/*移至下一个元素继续查找*/n+;/All copyright are preserved bycobby/*元素插入操作*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/char c;/*数据域，类型为字符型*/struct node*next;/*指针域，类型为本结构体类型*/Node,*L;/*类型重定义

9、，即Node和*L 和 struct node等价*/main()L l,p,q;/*用指针类型定义三个结点类型的指针*/char ch;int pos,n;l=(L)malloc(sizeof(Node);/*分配内存空间*/l-c=0;/*为头结点的数据域赋值，值为空*/l-next=NULL;/*指明下一个结点目前不存在*/q=l;/*q为游动指针，链表结点的连结要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*输入!表示输入结束*/p=(L)malloc(sizeof(Node);/*为新输入的数

10、据分配内存空间*/p-c=ch;p-next=NULL;/*新输入的结点在链表的最后，即它的后面没有其它元素*/q-next=p;/*q用于将上一个元素链接至当前新元素*/q=p;/*q自己移到当前最后一个元素，以备继续链接所用*/scanf(%c,&ch);getchar();q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 45 页 -数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向

11、的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/*以上为建立一个单链表*/printf(Input the character and its position,such as s,3nn);scanf(%c,%d,&ch,&pos);q=l;n=1;while(n!=pos&q-next!=NULL)/*未找到插入位置，且后面还有元素*/q=q-next;n+;/*退出循环后，要么找到插入位置，要么表已到最后，输入的插入位置过大*/if(nc=ch;p-next=q-next;q-next=p;/*操作完成，然后输出新表*/q=l;/*输入整

12、个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 45 页 -/All copyright are preserved bycobby/*按内容元素删除操作*/#include#include#define NULL 0 /*宏定义*/typedef struc

13、t node /*定义结点类型的数据结构*/char c;/*数据域，类型为字符型*/struct node*next;/*指针域，类型为本结构体类型*/Node,*L;/*类型重定义，即Node和*L 和 struct node等价*/main()L l,p,q;/*用指针类型定义三个结点类型的指针*/char ch;int n;l=(L)malloc(sizeof(Node);/*分配内存空间*/l-c=0;/*为头结点的数据域赋值，值为空*/l-next=NULL;/*指明下一个结点目前不存在*/q=l;/*q为游动指针，链表结点的连结要用*/printf(Input a charact

14、er:n);scanf(%c,&ch);getchar();while(ch!=!)/*输入!表示输入结束*/p=(L)malloc(sizeof(Node);/*为新输入的数据分配内存空间*/p-c=ch;p-next=NULL;/*新输入的结点在链表的最后，即它的后面没有其它元素*/q-next=p;/*q用于将上一个元素链接至当前新元素*/q=p;/*q自己移到当前最后一个元素，以备继续链接所用*/scanf(%c,&ch);getchar();q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，

15、则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 45 页 -q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/*以上为建立单链表*/printf(input the character you wanna deletenn);scanf(%c,&ch);printf(the element you wanna delete is%cnn,ch);q=l-next;p=l;n=1;while(q!=NULL&q-c!=ch)p=q;q

16、=q-next;n+;/*退出循环时可能找到指定元素，也可能表读完，需要进一步判断*/if(q=NULL)printf(element not found,delete failednn);else p-next=q-next;q=l-next;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/All copyright are p

17、reserved bycobby/*按位置删除元素*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/char c;/*数据域，类型为字符型*/名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 45 页 -struct node*next;/*指针域，类型为本结构体类型*/Node,*L;/*类型重定义，即Node和*L 和 struct node等价*/main()L l,p,q;/*用指针类型定义三个结点类型的指针*/char ch;int pos,n;l=(L)malloc(sizeof(Node);/*分配内

18、存空间*/l-c=0;/*为头结点的数据域赋值，值为空*/l-next=NULL;/*指明下一个结点目前不存在*/q=l;/*q为游动指针，链表结点的连结要用*/printf(Input a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*输入!表示输入结束*/p=(L)malloc(sizeof(Node);/*为新输入的数据分配内存空间*/p-c=ch;p-next=NULL;/*新输入的结点在链表的最后，即它的后面没有其它元素*/q-next=p;/*q用于将上一个元素链接至当前新元素*/q=p;/*q自己移到当前最后一个元素，以备继

19、续链接所用*/scanf(%c,&ch);getchar();q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/*以上为建立单链表*/printf(Input the positionn);scanf(%d,&pos);p=l;n=1;while(p-next!=NULL&n!=pos)名师资料总结-精品

20、资料欢迎下载-名师精心整理-第 8 页，共 45 页 -p=p-next;n+;/*退出循环后，可能找到删除的元素位置，可能表读完，需要进一步判断*/if(n=pos)/*删除位置找到，删除该位置上的元素*/p-next=p-next-next;/free(p);else printf(incorrect position,delete failedn);q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所

21、指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/建立双向链表#include#include#include#define NULL 0 typedef struct dlnode char ch;struct dlnode*pri,*next;dnode,*dl;main()dl l,p,q;char c;l=(dl)malloc(sizeof(dnode);l-ch=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 45 页 -l-next=NULL;l-pri=NULL;q=l;printf(输入字符建立双向链表n);

22、scanf(%c,&c);getchar();while(c!=!)p=(dl)malloc(sizeof(dnode);p-ch=c;p-pri=q;p-next=NULL;q-next=p;q=p;scanf(%c,&c);getchar();q=l;while(q-next!=NULL)q=q-next;printf(%c-,q-ch);printf(n);while(q-pri!=NULL)printf(%c-,q-ch);q=q-pri;printf(n);/单链表就地逆置#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*

23、/char c;/*数据域，类型为字符型*/struct node*next;/*指针域，类型为本结构体类型*/Node,*L;/*类型重定义，即Node和*L 和 struct node等价*/名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 45 页 -main()L l,p,q,r;/*用指针类型定义三个结点类型的指针*/char ch;l=(L)malloc(sizeof(Node);/*分配内存空间*/l-c=0;/*为头结点的数据域赋值，值为空*/l-next=NULL;/*指明下一个结点目前不存在*/q=l;/*q为游动指针，链表结点的连结要用*/printf(In

24、put a character:n);scanf(%c,&ch);getchar();while(ch!=!)/*输入!表示输入结束*/p=(L)malloc(sizeof(Node);/*为新输入的数据分配内存空间*/p-c=ch;p-next=NULL;/*新输入的结点在链表的最后，即它的后面没有其它元素*/q-next=p;/*q用于将上一个元素链接至当前新元素*/q=p;/*q自己移到当前最后一个元素，以备继续链接所用*/scanf(%c,&ch);getchar();q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指

25、向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/printf(n);/以上完成了单链表的创建 q=l-next;p=q-next;r=p-next;q-next=NULL;while(r!=NULL)p-next=q;q=p;p=r;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 45 页 -if(r-next!=NULL)/r后面还有结点，则逆置继续 r=r-next;else break;r-nex

26、t=q;l-next=r;/头结点指向最后一个结点 q=l;/*输入整个链表前，先将q 移到链表头，l 一般不动*/while(q-next!=NULL)/*若 q 所指向的元素后面还有其它元素，则将该元素的数据输出*/printf(%c-,q-next-c);/*q-next-c表示 q 所指向的下一个元素的数据*/q=q-next;/*完成该元素的输出后，q 移至下一个元素重复输出操作*/printf(n);/约瑟夫环问题#include#include typedef struct lnode int num;struct lnode*next;node,*L;main()int amo

27、unt,start,circle,n,c;L p,l,q;printf(一共有几个人围成一圈？n);scanf(%d,&amount);getchar();printf(从第几个开始计数？n);scanf(%d,&start);getchar();printf(每几人一次循环？n);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 45 页 -scanf(%d,&circle);getchar();l=(L)malloc(sizeof(node);/头结点 l-next=NULL;l-num=0;q=l;n=0;while(n+next=NULL;p-num=n;q-next=p

28、;q=p;q-next=l-next;/形成循环链表 /以上完成了单向循环链表的建立 p=l-next;q=l;n=1;while(n+next;q=q-next;/退出循环时p,q 分别位于指定位置 /接下去进行周期性结点删除，直到链表只余一个结点为止 n=1;/n计算被删除的结点的数量，当n=amount-1 时删除结束 while(n+amount)c=1;/c作为循环临时变量 while(c+next;q=q-next;/删除当前 p 指向的结点 printf(删除结点%dt,p-num);q-next=p-next;p=p-next;名师资料总结-精品资料欢迎下载-名师精心整理-第

29、13 页，共 45 页 -printf(n最后剩下%dn,p-num);二、栈及其操作/All copyright are preserved bycobby/*建立堆栈*/#include#include#define NULL 0 typedef struct node char ch;struct node*next;Snode,*stack;main()stack s,top,p;char ch;s=(stack)malloc(sizeof(Snode);s-ch=0;s-next=NULL;/*建立栈底指针*/top=s;scanf(%c,&ch);getchar();while(c

30、h!=!)p=(stack)malloc(sizeof(Snode);p-ch=ch;p-next=top;top=p;scanf(%c,&ch);getchar();while(top-next!=NULL)printf(%c-,top-ch);top=top-next;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 45 页 -printf(n);/All copyright are preserved bycobby/*进栈与出栈*/#include#include#define NULL 0 typedef struct node char ch;struct node

31、*next;Snode,*stack;main()stack s,top,p;char ch;int choice;s=(stack)malloc(sizeof(Snode);s-ch=!;s-next=NULL;/*建立栈底指针*/top=s;scanf(%c,&ch);getchar();while(ch!=!)p=(stack)malloc(sizeof(Snode);p-ch=ch;p-next=top;top=p;scanf(%c,&ch);getchar();while(p-next!=NULL)/此处 p 可用 top 代替 printf(%c-,p-ch);名师资料总结-精品资

32、料欢迎下载-名师精心整理-第 15 页，共 45 页 -p=p-next;printf(n);/*以上建立了一个堆栈*/printf(进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退出程序n);scanf(%d,&choice);getchar();while(choice=1|choice=2)/若不是输入1 或 2，则不做任何操作 if(choice=1)/*进栈*/printf(n输入要入栈的元素n);scanf(%c,&ch);getchar();p=(stack)malloc(sizeof(Snode);p-ch=ch;p-next=top;top=p;else if(cho

33、ice=2)if(top-next!=NULL)top=top-next;else printf(栈已清空 n);exit();/*出栈*/printf(%c-,top-ch);p=top;while(p-next!=NULL)printf(%c-,p-ch);p=p-next;printf(n);printf(进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退出程序n);名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 45 页 -scanf(%d,&choice);getchar();/All copyright are preserved bycobby/栈的应用，括

34、号匹配#include#include#define NULL 0 typedef struct node char ch;struct node*next;snode,*stack;main()stack s,top,p;char*string,ch100=;s=(stack)malloc(sizeof(snode);/建立栈底元素 s-ch=0;s-next=NULL;top=s;printf(输入一个含括号的四则运算表达式：n);scanf(%s,ch);string=ch;while(*string!=0)if(*string=(|*string=|*string=)/遇到左括号，入栈

35、 p=(stack)malloc(sizeof(snode);p-ch=*string;p-next=top;top=p;else if(*string=)|*string=|*string=)/遇到右括号 if(*string=)if(top-ch=()/括号匹配名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 45 页 -top=top-next;else printf(小括号不匹配);exit(0);else if(*string=)if(top-ch=)/括号匹配 top=top-next;else printf(中括号不匹配);exit(0);else if(top-c

36、h=)/括号匹配 top=top-next;else printf(大括号不匹配);exit(0);string+;if(top-ch!=0)printf(多出左括号%cn,top-ch);三、队及其操作/All copyright are preserved bycobby/链队列的建立#include#include#include#define NULL 0 typedef struct node /队列结点的基本数据结构，即队列中每个结点的类型 char c;名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 45 页 -struct node*next;qnode,*ba

37、sic_node;typedef struct /队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定 qnode*head;qnode*rear;queue,*Q;main()Q q;/定义队列，结构体变量q 中含有头指针head 和尾指针 rear，所以 q 是一个完整的队列（只不过队列为空）/事实上，任何由Q定义的结构体变量都是一个独立完整的队列 basic_node p,l;/basic_node是基本结点类型，即是独立的结点，它是组成队列的基本元素。/基本结点p,l和队列 q 的关系可由下图表示：/(q-head)-p-l-p-l-,-p-l-(q-rea

38、r)char ch;q=(Q)malloc(sizeof(queue);q-head=NULL;/初始化时队列为空 q-rear=NULL;printf(输入队列元素:n);scanf(%c,&ch);getchar();while(ch!=!)p=(qnode*)malloc(sizeof(qnode);p-c=ch;p-next=NULL;/新来的元素一定在队列的最后，它的后面没有其它元素 if(q-head=NULL)q-head=p;/第一个元素入队时，队头指针指向它 l=q-head;/l指向第一个元素 l-next=p;/使前一个元素指向当前入队的新元素 l=p;/l移动到当前新元

39、素，以备用下次入队操作 q-rear=p;/修改队尾指针，使其总是指向当前最后一个队列元素 scanf(%c,&ch);getchar();名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 45 页 -l=q-head;while(l!=NULL)printf(%cc);l=l-next;printf(n);printf(头指针指向元素为%ct 尾指针指向元素为%cn,q-head-c,q-rear-c);/All copyright are preserved bycobby/入队和出队#include#include#include#define NULL 0 typedef

40、 struct node /队列结点的基本数据结构，即队列中每个结点的类型 char c;struct node*next;qnode,*basic_node;typedef struct /队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定 qnode*head;qnode*rear;queue,*Q;main()Q q;/定义队列，结构体变量q 中含有头指针head 和尾指针 rear，所以 q 是一个完整的队列（只不过队列为空）/事实上，任何由Q定义的结构体变量都是一个独立完整的队列 basic_node p,l;/basic_node是基本结点类型，即是独

41、立的结点，它是组成队列的基本元素。/基本结点p,l和队列 q 的关系可由下图表示：/(q-head)-p-l-p-l-,-p-l-(q-rear)名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 45 页 -char ch;int choice;q=(Q)malloc(sizeof(queue);q-head=NULL;/初始化时队列为空 q-rear=NULL;printf(输入队列元素:n);scanf(%c,&ch);getchar();while(ch!=!)p=(qnode*)malloc(sizeof(qnode);p-c=ch;p-next=NULL;/新来的元素一

42、定在队列的最后，它的后面没有其它元素 if(q-head=NULL)q-head=p;/第一个元素入队时，队头指针指向它 l=q-head;/l指向第一个元素 l-next=p;/使前一个元素指向当前入队的新元素 l=p;/l移动到当前新元素，以备用下次入队操作 q-rear=p;/修改队尾指针，使其总是指向当前最后一个队列元素 scanf(%c,&ch);getchar();l=q-head;while(l!=NULL)printf(%cc);l=l-next;printf(n);printf(头指针指向元素为%ct 尾指针指向元素为%cn,q-head-c,q-rear-c);/以上建立了

43、一个队列 printf(输入 1 进行入队，输入2 进行出队:n);scanf(%d,&choice);getchar();名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 45 页 -if(choice=1)printf(n输入要入队的元素:n);scanf(%c,&ch);getchar();p=(qnode*)malloc(sizeof(qnode);/给新入队的元素分配内存空间 p-c=ch;p-next=NULL;/新元素为最后一个元素 q-rear-next=p;/原来最后一个元素指向新入队的元素 q-rear=p;/修改队尾指针，使其指向当前最后一个元素 else

44、if(choice=2)q-head=q-head-next;else exit(0);l=q-head;while(l!=NULL)printf(%cc);l=l-next;printf(n);printf(头指针指向元素为%ct 尾指针指向元素为%cn,q-head-c,q-rear-c);/All copyright are preserved bycobby/循环队列建立#include#include#define MAX 8 typedef struct char cMAX;/循环队列是顺序队列的一种，它的核心就是一个数组 int front;/整形变量，作为头指针用 int re

45、ar;/整形变量，作为尾指针用queue;main()queue*q;名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 45 页 -char ch;int i;q=(queue*)malloc(sizeof(queue);/生成一个空循环队列 for(i=0;ici=0;q-front=0;q-rear=0;printf(输入要入队的元素:n);scanf(%c,&ch);getchar();while(ch!=!)if(q-rear+1)%MAX=q-front)/若队列已满 printf(队列已满，无法入队n);break;else q-cq-rear=ch;/rear指向当

46、前可入队的数组元素位置 q-rear=(q-rear+1)%MAX;/修改尾指针，向后移动一个位置 /注意，不能简单使用q-rear+，不然会导致队列溢出 scanf(%c,&ch);getchar();for(i=q-front;irear;i=(i+1)%MAX)/能够用 for循环，说明了顺序队列和链式队列的区别 printf(%cci);printf(n);/All copyright are preserved bycobby/循环队列的入队和出队操作#include#include#define MAX 8 名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 45 页

47、-typedef structd char cMAX;/循环队列是顺序队列的一种，它的核心就是一个数组 int front;/整形变量，作为头指针用 int rear;/整形变量，作为尾指针用queue;main()queue*q;char ch;int i,choice;q=(queue*)malloc(sizeof(queue);/生成一个空循环队列 for(i=0;ici=0;q-front=0;q-rear=0;printf(输入要入队的元素:n);scanf(%c,&ch);getchar();while(ch!=!)if(q-rear+1)%MAX=q-front)/若队列已满 p

48、rintf(队列已满，无法入队n);break;else q-cq-rear=ch;/rear指向当前可入队的数组元素位置 q-rear=(q-rear+1)%MAX;/修改尾指针，向后移动一个位置 /注意，不能简单使用q-rear+，不然会导致队列溢出 scanf(%c,&ch);getchar();printf(头指针指向元素为%dt 尾指针指向元素为%dn,q-front,q-rear);for(i=q-front;irear;i=(i+1)%MAX)/能够用 for循环，说明了顺序队列和链式队列的区别名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 45 页 -print

49、f(%c-,q-ci);printf(n);/以上建立了一个循环队列 printf(输入 1 入队，输入2 出队:n);scanf(%d,&choice);getchar();while(choice=1|choice=2)if(choice=1)printf(输入要入队的元素n);scanf(%c,&ch);getchar();if(q-rear+1)%MAX=q-front)/若队列已满 printf(队列已满，无法入队n);break;else q-cq-rear=ch;/rear指向当前可入队的数组元素位置 q-rear=(q-rear+1)%MAX;/修改尾指针，向后移动一个位置 /

50、注意，不能简单使用q-rear+，不然会导致队列溢出 else if(choice=2)if(q-front+1)%MAX!=q-rear)/队非空 q-cq-front=0;/删除元素 q-front=(q-front+1)%MAX;/修改队头指针 else printf(队已清空 n);break;名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 45 页 -if(q-rearq-front)/尾指针在头指针的右边 for(i=q-front;irear;i=(i+1)%MAX)/能够用 for循环，说明了顺序队列和链式队列的区别 printf(%cci);printf(n)

51、;else /尾指针在头指针的左边 for(i=q-front;irear+MAX);i+)/能够用 for循环，说明了顺序队列和链式队列的区别 printf(%cci%MAX);printf(n);printf(头指针指向元素为%dt 尾指针指向元素为%dn,q-front,q-rear);printf(输入 1 入队，输入2 出队:n);scanf(%d,&choice);getchar();四、串及其操作/串的朴素匹配#include main()char str1100,str2100,*p;int i=0,j=0,len_str1=0,len_str2=0,num=0;printf(

52、输入母串:n);scanf(%s,str1);getchar();printf(%输入子串:n);scanf(%s,str2);getchar();p=str1;while(*p!=0)/获取母串长度 len_str1+;名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 45 页 -p+;p=str2;/获取子串长度 while(*p!=0)len_str2+;p+;for(i=0;ilen_str1;i+)/i为母串下标 for(j=0;jlen_str2;j+)/j为子串下标 num+;if(str1i+j!=str2j)break;/若当前字符不匹配，则指针向母串下一个字符

53、移动 if(j=len_str2)printf(子串在母串中的位置为%dn,i+1);/break;/若子串在母串中多次出现，则全部找到其位置。若恢复break 语句则只找出最前的一个匹配子串 printf(母串长度为%d,子串长度为%dn 核心语句执行次数为%dn,len_str1,len_str2,num);五、树（二叉树）及其操作/二叉排序树#include#include typedef struct tnode int num;struct tnode*Lchild,*Rchild;Tnode,*Btree;typedef struct snode int num;名师资料总结-精品

54、资料欢迎下载-名师精心整理-第 27 页，共 45 页 -Btree r;struct snode*next;Snode,*stack;Btree root;void describe_tree()/交互式显示哈夫曼树 Btree t;stack s,top,temp;int choice;s=(stack)malloc(sizeof(Snode);s-num=0;s-next=NULL;s-r=NULL;top=s;t=root;/t指向哈夫曼树的根结点 temp=(stack)malloc(sizeof(Snode);/分配新栈结点 temp-num=t-num;temp-next=top

55、;/结点入栈 temp-r=t;/将当前二叉树结点指针给栈顶结点 top=temp;/修改栈顶指针 printf(输入 1 往左子树，输入2 往右子树，输入3 返回父结点，其它输入退出程序n);scanf(%d,&choice);getchar();while(choice=1|choice=2|choice=3)if(choice=1)/往左子树 if(t-Lchild!=NULL)t=t-Lchild;temp=(stack)malloc(sizeof(Snode);/分配新栈结点 /新结点入栈 temp-num=t-num;temp-next=top;/结点入栈 temp-r=t;/将当

56、前二叉树结点指针给栈顶结点 top=temp;/修改栈顶指针名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 45 页 -printf(值为%dn,t-num);else /左子树不存在，当前结点已经是叶子结点 printf(无左孩子！n);else if(choice=2)/往右子树 if(t-Rchild!=NULL)t=t-Rchild;temp=(stack)malloc(sizeof(Snode);/分配新栈结点 /新结点入栈 temp-num=t-num;temp-next=top;/结点入栈 temp-r=t;/将当前二叉树结点指针给栈顶结点 top=temp;/修

57、改栈顶指针 printf(值为%dn,t-num);else /右子树不存在，当前结点已经是叶子结点 printf(无右孩子！n);else if(choice=3)/返回父结点 if(top-next!=s)/栈非空 top=top-next;t=top-r;printf(值为%dn,t-num);else printf(已经在根结点了！n);scanf(%d,&choice);getchar();void inorder(Btree r)/中序递归遍历 if(r!=NULL)inorder(r-Lchild);名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 45 页 -pr

58、intf(%d num);inorder(r-Rchild);main()int array100,n=0,i,choice;Btree p,q;for(i=0;inum=arrayn;root-Lchild=NULL;root-Rchild=NULL;n+;else exit(0);while(arrayn!=0)p=(Btree)malloc(sizeof(Tnode);/依次给每个整数分配结点 p-num=arrayn;p-Lchild=NULL;p-Rchild=NULL;/分配完结点后，要插入到二叉树中合适的位置 q=root;/q初始化到根结点 while(q!=NULL)if(q

59、-numnum)/若新结点的值大于根结点的值，则往右子树 名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 45 页 -if(q-Rchild!=NULL)/当前结点有右孩子，则指针移向右孩子继续比较 q=q-Rchild;else /当前结点没有右孩子，则新结点为当前结点的右孩子 q-Rchild=p;break;else if(q-Lchild!=NULL)/当前结点有左孩子，则指针移向左孩子继续比较 q=q-Lchild;else /当前结点没有左孩子，则新结点为当前结点的左孩子 q-Lchild=p;break;n+;/建立二叉排序树完毕 /对其进行中序遍历 printf

60、(n哈夫曼树构造完成，是否查看哈夫曼树，输入1 查看，其它输入跳过);scanf(%d,&choice);getchar();if(choice=1)describe_tree();inorder(root);printf(n);哈夫曼算法程序太大，一个贴放不下，下面两个贴均为哈夫曼编码程序./2005/4/28/All Copyright Are Reserved By cobby/哈夫曼编码名师资料总结-精品资料欢迎下载-名师精心整理-第 31 页，共 45 页 -#include#include#include#define NULL 0 typedef struct huff_code

61、_node /存储编码的链表 char ch;/编码对应的字符 char code100;/字符对应的哈夫曼码 struct huff_code_node*next;hnode,*huff;typedef struct tree_Node /二叉树结点 char ch;/字符内容 int amount;/字符在字符串中出现的次数 struct tree_Node*left,*right;/指向左子树与右子树tnode,*bt;typedef struct list_node /链表结点 char ch;/存储字符串中的字符 int amount;/字符在字符串中出现的次数 tnode*son;

62、/链表结点带有二叉子树的根结点指针 struct list_node*next;/指向链表中下一个结点Node,*L;typedef struct stack_node char ch;/存储字符 int amount;/出现次数 bt son;/指向二叉树的某结点 struct stack_node*next;snode,*stack;char t200,*str,*c;/用于存储和处理输入的字符串bt root=NULL;/哈夫曼树L l,p,q,new_node;/链表结点huff hlist;/计算得到的编码表int char_num;/输入的不同字符数量int char_amount

63、;/输入的所有字符数量int code_sum;/哈夫曼编码总长名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 45 页 -void initial()/初始化操作 l=(Node*)malloc(sizeof(Node);/建立空链表 l-ch=0;l-amount=0;l-son=NULL;l-next=NULL;str=t;/将字符串指针指向字符串的第一个位置 /键盘输入字符串 printf(输入字符串进行哈夫曼编码:n);scanf(%s,str);getchar();void pull_in_list()int exist;/表示当前字符是否存在于链表中，0 为不存在

64、，1 为已存在 int n;/计算输入不同字符的数量，计算后赋值给全局变量char_num int m;/计算输入所有字符的数量，计算后赋值给全局变量char_amount c=str;/c指向第一个字符 while(*c!=0)/若字符串未读完 exist=0;p=l;/p指向链表头结点 /寻找该字符是否已经在链表中 while(p-next!=NULL)/若链表非空 p=p-next;if(p-ch=*c)/若当前字符已经在链表中 exist=1;p-amount+;/字符出现次数加1 break;if(exist=0)/若当前字符不存在于链表中，则分配一个结点入表 new_node=(N

65、ode*)malloc(sizeof(Node);名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 45 页 -new_node-ch=*c;new_node-amount=1;new_node-next=NULL;new_node-son=NULL;p-next=new_node;p=new_node;c+;/读下一个字符 printf(统计结果:n);p=l;n=0;m=0;while(p-next!=NULL)n+;p=p-next;m+=p-amount;printf(%c%dn,p-ch,p-amount);char_num=n;char_amount=m;printf

66、(一共有%d种字符输入，字符总数%dn,char_num,char_amount);int list_element_amount()/计算链表中结点的数量（不包括头结点）L temp;/定义临时指针 int n=0;/结点数量 temp=l;while(temp-next!=NULL)/后面还有结点 n+;temp=temp-next;return n;bt create()/建立最优二叉树 /=/这些变量用于寻找最小结点名师资料总结-精品资料欢迎下载-名师精心整理-第 34 页，共 45 页 -L min1_pos,min2_pos,t,min_pri;bt min1_son,min2_son;int min1,min2;char min1_c,min2_c;/=/=/这些变量用于构造二叉子树 bt left,right,root;/=/=/这些变量用于将二叉子树信息插入链表 L made,temp_p;/=while(list_element_amount()=2)/若表中还有两个或以上结点，则归并继续 /选择次数值最小的两个结点 /=/先寻找第一个小结点 t=l-next;mi