部分数据结构试验源程序.doc

《部分数据结构试验源程序.doc》由会员分享，可在线阅读，更多相关《部分数据结构试验源程序.doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构实验什么都不说，直接上程序一 链表归并排序#includeusing namespace std;typedef struct Linklistint data;struct Linklist* next;Link,*link_pointer;void initialize(link_pointer p)/初始化函数p-data = 0;p-next = NULL;Link creatLink(int n) /构造链表函数,n是链表的长度,返回头结点Link head;initialize(&head); / 头结点headhead.data = n;head.next = (link

2、_pointer)malloc(sizeof(Link);link_pointer pointer = head.next;for(int i=0;in;i+)cout输入第i+1个 pointer-data;pointer-next=(link_pointer)malloc(sizeof(Link);pointer=pointer-next;initialize(pointer);return head; void show(Link head)link_pointer p=head.next;while(p-next)coutdatanext;coutnext!=0)&(pb-next!=

3、0)if(pa-datapb-data)pc-next = pb;pc = pb;pb = pb-next;continue;if(pa-data data)pc-next = pa;pc = pa;pa = pa-next;continue;if(pa-data = pb-data)if(pc-next = pa)pb=pb-next;elsepa=pa-next;continue;pc-next = (pa-next!=0)?pa:pb;int main()int n1,n2;cout请输入1链表长度: n1;Link head1=creatLink(n1);cout请输入2链表长度: n

4、2;Link head2 = creatLink(n2);merger(head1,head2);show(head1); return 0;二 二叉树遍历#include#include#includeusing namespace std;struct Bitreechar data;struct Bitree* lchild;struct Bitree* rchild;stack s;queue q;/先序遍历递归建立二叉树，用#表示空指针，Bitree* Build_Bitree()char ch;Bitree *root = NULL;cinch;if(ch = #)return r

5、oot;elseroot = (Bitree*)malloc(sizeof(Bitree);root-data = ch;root-lchild = Build_Bitree();root-rchild = Build_Bitree();return root;/先序遍历结果void PreOrder(Bitree* root)/递归方式if(root = NULL)return;elsecoutdatalchild);PreOrder(root-rchild);/非递归方式void PreVisit(Bitree* root)if(root = NULL)cout空二叉树lchild;whi

6、le(!s.empty()while(root = s.top() & (root != NULL)coutdatalchild);s.pop();if(!s.empty()root = s.top();s.pop();s.push(root-rchild);/中序遍历void InOrder(Bitree* root)if(root = NULL)return;elseInOrder(root-lchild);coutdatarchild);/非递归方式void InVisit(Bitree* root)if(root = NULL)cout空二叉树lchild;while(!s.empty

7、()while(root = s.top() & (root != NULL)s.push(root-lchild);s.pop();if(!s.empty()root = s.top();s.pop();coutdatarchild);/后序遍历void PostOrder(Bitree* root)if(root = NULL)return;elsePreOrder(root-lchild);PreOrder(root-rchild);coutdata ;/按层遍历void Visit(Bitree* root)if(root = NULL)cout空二叉树endl;q.push(root

8、);while(!q.empty()root = q.front();q.pop();coutdatalchild != NULL)q.push(root-lchild);if(root-rchild != NULL)q.push(root-rchild);int main()Bitree *root;root = Build_Bitree();/先序遍历cout先序递归：endl;PreOrder(root);coutendl先序非递归：endl;PreVisit(root);coutendl;/中序遍历cout中序递归：endl;InOrder(root);coutendl中序非递归：en

9、dl;InVisit(root);coutendl;/后序遍历cout后序：endl;PostOrder(root);coutendl按层：endl;/按层遍历Visit(root);coutendl;return 0;三 邻接表深搜广搜#include#include#includeusing namespace std;/用向量容器模拟链表，完成深搜/队列完成广搜#define M 10vector vM;queue q;bool visitedM;int n;/因为有标准数组，则向量中就算是存入两个相同的边也会只访问一次void dir()/以a，b输入值为-1,-1代表输入有向图结束i

10、nt a,b;while(cinab)if(a=-1 & b=-1)break;va.push_back(b);void no_dir()/以a，b输入值为-1,-1代表输入无向图结束int a,b;while(cinab)if(a=-1 & b=-1)break;va.push_back(b);vb.push_back(a);/无向图相当于两条来回边void dfs(int vex)/深搜if(visitedvex)return;elsevisitedvex = true;coutvex ;int j=0;while(jvvex.size()/对vex的所有邻接点进行深搜if(!visite

11、dvvexj)dfs(vvexj);j+;void bfs()for(int i=1;i=n;i+)if(!visitedi)visitedi = true;q.push(i);while(!q.empty()int vex = q.front();q.pop();coutvex ;int j=0;while(jvvex.size()if(!visitedvvexj)q.push(vvexj);visitedvvexj = true;j+;int main()coutA：有向图endlB：无向图endl请选择：ch;coutendl输入结点数:n;memset(visited,false,sizeof(visited);if(ch = A)dir();elseif(ch = B)no_dir();elsecout错入选择endl;system(pause);return 0;cout深搜结果：endl;int i;for(i=1;i=n;i+)if(!visitedi)dfs(i);/从结点1开始深搜/深搜结束memset(visited,false,sizeof(visited);/因前面深搜已经改过标志位，需要改回来coutendl广搜结果：endl;bfs();coutendl;return 0;