数据结构所有实验综合打印版复习版.doc

/ 链表。#include #include using namespace std;struct node int num;node *next;node *creat()/链表建立int n=0;node *p1,*p2,*head;p1=p2=new node;cinp1-num;head=NULL;while(p1-num!=0)if(n=0)head=new node;head-next=p1;elsep2-next=p1;p2=p1;p1=new node;cinp1-num;n+;p2-next=NULL;return head;int listlength(node *l)/计算长度node *p=l-next;int count=0;while (p)count+;p=p-next;return count;int search(node *l,int value)/链表的查找node *p=l;int index=0;while(p)if(p-num=value)return index;p=p-next;index+;return 0;void print(node *head)/打印链表node* p=head-next;while(p)coutnumnext;coutnext;delete temp;couthad been destructed.next-next;q=p-next; if(p=NULL) return; r=l-next; r-next =NULL; while(p-next!=NULL) /每次将未逆置的链表中的首结点*p，挂在部分逆置好的链表首结点*r之前，/在改变p-next之前，将p的后继结点存储在q之中 p-next=r; r=p; p=q;q=p-next; p-next=r; /最后一结点的处理 l-next=p;node *Merge(node *head1 , node *head2) /合并两个有序链表node *head; if ( head1 = NULL) return head2 ; if ( head2 = NULL) return head1 ; if ( head1-num num ) head = head1 ; head1= head1-next; else head = head2 ; head2 = head2-next ; node *temp = head ; while ( head1 != NULL & head2 != NULL) if ( head1-num num ) temp-next = head1 ; head1 = head1-next ; temp =temp-next; else temp-next = head2; head2 = head2-next ; temp =temp-next; if (head1 = NULL) temp-next = head2; if (head2 = NULL) temp-next = head1; return head-next;node* Delete(node* head , int num) /删除节点 if (head=NULL) coutList is Nullnum!=num & p1-next) p2=p1; p1=p1-next; if (p1-num=num) if (p1=head) head=p1-next; else p2-next=p1-next; else coutDo not Find The Num numnum=num; if (head=NULL) head=p0; p0-next=NULL; return head; while (p1-num num & p1-next) p2=p1; p1=p1-next; if (p1-num=p0-num) if (p1=head) head=p0; else p2-next=p0; p0-next=p1; else p1-next=p0; p0-next=NULL; return head; void main()node *a,*c;int b;cout请输入链表，以0结束：endl;a=creat();cout输出链表：endl;print(a);cout链表长度为listlength(a)endl;cout请输入要查找的值：b;coutb的下标为search(a,b)endl;reverselist(a);cout逆序后的链表：endl;print(a);cout请输入要删除的节点:n;Delete(a,n);cout删除节点后的链表：endl;print(a);cout请输入要插入的节点：m;Insert(a,m);cout添加节点后的链表：endl;print(a);destruct(a);/cout清空后的链表长度为：listlength(a)endl;node *d,*e,*f;cout请输入第一个有序链表：endl;d=creat();cout请输入第二个有序链表：endl;e=creat();f=Merge(d,e);print(f); system(pause);/约瑟夫环#includeusing namespace std;struct nodeint num;int password;node *next;node *create(int num)cout请输入num人的密码：endl;node *p1,*p2,*head;p1=p2=new node;head=NULL;for(int i=0;ip1-password;if(head=NULL)p1-num=1;head=p1;/ifelse p2-next=p1;p2=p1;p1=new node;p1-num=i+2;/forp2-next=head;return head;/nodeint main()int num,maxnum;cout请输入M的初始值：maxnum;cout请输入人数：num;node * head;head=create(num);node*play=head;node*temp=head;for(int j=0;jnum;j+)for(int i=1;inext;maxnum=play-password;coutnumnext=play-next;play=temp-next;return 1;/线性表的顺序存储的创建，删除，插入和遍历操作#include #include using namespace std;const int LIST_INIT_SIZE=100;/线性表的初始存储空间const int LISTADD=20;/线性表的增量存储空间typedef struct int number;int score;Node;typedef Node Elemtype;typedef struct/int number;Elemtype *List;/基地址指针int Length;/线性表的长度int Listsize;/线性表的存储容量SqList;/-初始化空线性表-void InitSqList(SqList &L,int ms)L.List=new Elemtypems;if(!L.List )cout分配存储失败!endl;L.Length =0;L.Listsize =LIST_INIT_SIZE;/-创建线性表-void CreateSqList(SqList &L)cout请输入创建的线性表的长度:L.Length;cout请输入线性表结点的内容(中间用空格隔开）：endl;for(int i=0;iab;L.Listi.number=a;L.Listi.score =b;temp=getchar();/-输出线性表-void PrintSqList(SqList &L)cout顺序表为(number,score)：endl;for(int i=0;iL.Length;i+)cout(L.Listi.number，L.Listi.score) ;coutendl;/-插入元素(后插法）-void InsertSqList(SqList &L,int a,Elemtype e)if(aL.Length +1)coutERROR!=L.Listsize )/扩增数组int newsize=L.Listsize+LISTADD;L.List=(Elemtype*)realloc(L.List,newsize*sizeof(Elemtype);if(!L.List)coutERROR!=q;p-)*(p+1)=*p;/向右移一位*q=e;L.Length +;void DeleteSqList(SqList &L,int a)if(a=L.Length )coutERROR!number;e.score =q-score;cout被删除的元素为：(e.number，e.score )endl; for(Elemtype *p=q;pq;/迷宫#define OVERFLOW -2#define ERROR 0#define NULL 0#define true 1#define TRUE 1#define false 0#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include #include #include int maze1110= 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,1,1, 1,0,1,1,1,0,0,1,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,1,1, 1,0,1,1,1,1,0,0,1,1, 1,1,1,0,0,0,1,0,1,1, 1,1,1,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1 ;typedef struct MStackElem int x; int y; int d;MStackElem;typedef struct MStackElem * base; MStackElem * top; int stackSize;MStack;void initStack(MStack *s) s-base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem); if (!s-base) exit(OVERFLOW); s-top = s-base; s-stackSize = STACK_INIT_SIZE;void push(MStack *s,MStackElem e) if (s-top - s-base = s-stackSize) s-base = (MStackElem *)realloc(s-base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem); if (!s-base) exit(OVERFLOW); s-top = s-base + s-stackSize; s-stackSize += STACKINCREMENT; *(s-top+) = e;MStackElem getTop(MStack *s) if (s-top = s-base) exit(ERROR);else return *(s-top - 1);void pop(MStack *s) if (s-top = s-base) exit(ERROR); else -(s-top); MStack s;void print(MStack *s)cout坐标及方向：base); mazee.xe.y=3; cout(e.x,e.ybase top-1) e = *(s-base+1); mazee.xe.y=3; coute.d); cout(e.x,e.ybase)+; e = *(s-base); mazee.xe.y=3; coute.d; cout(e.x,e.y,e.d)endl; cout的迷宫：endl;for(int b=0;b11;b+)for(int c=0;c10;c+) if(mazebc=3) cout; else if(mazebc=1) cout* ; else cout ;coutendl;void path()cout未走过的迷宫：endl;for(int b=0;b11;b+)for(int c=0;c10;c+)if(mazebc=0) cout ;else cout* ;coutendl;initStack(&s); MStackElem cur; cur.x=1; cur.y=1;cur.d=1;int i=1,j=1;push(&s,cur);mazeij=2;while(!(i=9&j=8)if(cur.dd=cur.d;push(&s,cur);cur.d=1;mazeij=2;else i=cur.x;j=cur.y;cur.d+;/ifelsepop(&s);cur=getTop(&s);i=cur.x;j=cur.y;cur.d+;/break;/whilevoid main()path();print(&s);/二叉树#include #include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;BiTree CreateBiTree(BiTree &T) char p; cinp; if(p=#) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); T-data=p; T-lchild=CreateBiTree(T-lchild); T-rchild=CreateBiTree(T-rchild); return (T);/非递归法/*typedef struct SqStack BiTNode *base; BiTNode *top; int stacksize; SqStack;void InitStack(SqStack *S) S-base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode); S-top=S-base; S-stacksize=STACK_INIT_SIZE;void Push(SqStack *S,BiTNode e) if(S-top-S-base=S-stacksize) S-base=(BiTNode*)realloc(S-base, (S-stacksize+STACKINCREMENT)*sizeof(BiTNode); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *(S-top)=e; S-top+;BiTNode Pop(SqStack *S) S-top -; return *S-top;int StackEmpty(SqStack *S) if(S-top = S-base ) return 1; else return 0;void PreOrder(BiTree T)/先序SqStack S;BiTree p=T;InitStack(&S); if(p) Push(&S,*p); while(!StackEmpty(&S) p=(BiTNode *)malloc(sizeof(BiTNode); *p=Pop(&S); coutdata; if(p-rchild) Push(&S,*p-rchild); if(p-lchild) Push(&S,*p-lchild); void InOrder(BiTree T)/中序SqStack S;BiTree p=T;InitStack(&S); while(p|!StackEmpty(&S) if(p) Push(&S,*p); p=p-lchild; else p=(BiTNode *)malloc(sizeof(BiTNode); *p=Pop(&S); coutdata; p=p-rchild; void PostOrder(BiTree T)/后序 SqStack S; BiTNode p, *l, *r; InitStack(&S); Push(&S, *T); while(!StackEmpty(&S) p = Pop(&S); l = p.lchild; r = p.rchild; if (l = NULL & r = NULL) coutp.data; else p.lchild = NULL; p.rchild = NULL; Push(&S, p); if (r != NULL) Push(&S, *r); if (l != NULL) Push(&S, *l); / */递归法:/*void PreOrder2 (BiTNode* T) if(T) coutdata; PreOrder2(T-lchild); PreOrder2(T-rchild); void InOrder2 (BiTNode* T) if(T) InOrder2(T-lchild); coutdata; InOrder2(T-rchild); void PostOrder2 (BiTNode* T) if(T) PostOrder2(T-lchild); PostOrder2(T-rchild); coutdata; int Leaves1(BiTNode *T)/* 计算叶子结点个数 */ int num1,num2;if(T=NULL)return(0);if(T-lchild=NULL&T-rchild=NULL)return(1);num1=Leaves1(T-lchild);num2=Leaves1(T-rchild);return(num2+num1);int Leaves2(BiTNode *t) /非递归计算叶子节点个数int m=0,top=-1;BiTNode *data100;if(t)top+;datatop=t;while(top-1)t=datatop;top-;if(t-lchild=NULL&t-rchild=NULL)m+;elseif(t-lchild!=NULL)top+;datatop=t-lchild;if(t-rchild!=NULL)top+;datatop=t-rchild;return m;void Display_Leaves(BiTree t)/按从左至右的顺序遍历叶子结点if(t!=NULL)if(t-lchild=NULL&t-rchild=NULL)coutdata;elseDisplay_Leaves(t-lchild);Display_Leaves(t-rchild);void DeleteBiTree(BiTree T)/删除二叉树中的一个结点（待修改）if(T!=NULL)DeleteBiTree(T-lchild);DeleteBiTree(T-rchild);delete T;void ClearBiTree(BiTree &T)/清空二叉树DeleteBiTree(T);T =NULL;int depth(BiTree T)/求二叉树的深度int i,j;if(T=NULL)return 0;elsei=depth(T-lchild);j=depth(T-rchild);if(ij)return i+1;else return j+1;void main() cout创建一颗树：endl; BiTree t; t=CreateBiTree(t); cout非递归先序遍历：; PreOrder(t); coutendl非递归中序遍历：; InOrder(t); coutendl非递归后序遍历：; PostOrder(t); coutendl; cout递归先序遍历：; PreOrder2(t); coutendl递归中序遍历：; InOrder2(t); coutendl递归后序遍历：; PostOrder2(t); coutendl; cout叶子节点个数：Leaves1(t)endl; cout非递归求叶子节点个数：Leaves2(t)endl; cout树的所有叶子节点：; Display_Leaves(t); coutendl树的深度depth(t)endl; /DeleteBiTree(t); ClearBiTree(t); cout叶子节点个数：Leaves1(t)endl; cout非递归求叶子节点个数：Leaves2(t)endl; /哈夫曼树#include#include#define MAX 1000#define MAXSYMBS 30#define MAXNODE 59typedef struct int weight; int flag; int parent; int lchild; int rchild;huffnode;typedef struct int bitsMAXSYMBS; int start;huffcode;main() huffnode huff_nodeMAXNODE; huffcode huff_codeMAXSYMBS,cd; int i,j,m1,m2,x1,x2,n,c,p; /char symbsMAXSYMBS, symb; 数组 huff_node 初始化 cout请输入数中叶子的数目:n; for(i=0;i2*n-1; i+) huff_nodei.weight=0; huff_nodei.parent=0; huff_nodei.flag=0; huff_nodei.lchild=0; huff_nodei.rchild=0; /for cout请输入每片叶子的权值：endl; for(i=0;ihuff_nodei.weight; /构造哈夫曼树 for(i=0;in-1;i+) m1=m2=MAX; x1=x2=0; for(j=0;jn+i;j+) if(huff_nodej.weightm1&huff_nodej.flag=0) m2=m1; x2=x1; m1=huff_nodej.weight; x1=j; /if else if(huff_nodej.weightm2&huff_nodej.flag=0) m2=huff_nodej.weight; x2=j; /else if /for huff_nodex1.parent=n+i; huff_nodex2.parent=n+i; huff_nodex1.flag=1; huff_nodex2.flag=1; huff_noden+i.weight=huff_nodex1.weight+huff_nodex2.weight; huff_noden+i.lchild=x1; huff_noden+i.rchild=x2; /for /求字符的哈弗曼编码 for(i=0;in;i+) cd.start=n; c=i; p=huff_nodec.parent; while(p!=0) if(huff_nodep.lchild=c) cd.bitscd.start=1; else cd.bitscd.start=0; cd.start=cd.start-1; c=p; p=huff_nodep.parent; /while cd.start+; for(j=cd.start;j=n;j+) huff_codei.bitsj=cd.bitsj; huff_codei.start=cd.start; /for /输出字符的哈弗曼编码 puts(各叶子节点的编码:); for(i=0;in;i+) for(j=huff_codei.start;j=n;j+) couthuff_codei.bitsj;coutendl; /for/图的遍历#define INFINITY INT_MAX#define MAX_VERTEX_NUM 30#define NULL 0#define OK 1#include using namespace std;/邻接矩阵typedef struct ArcCell int adj; ArcCell *info;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; char kind;MGraph;/邻接表typedef struct ArcNode /定义边结点 int adjvex; ArcNode *nextarc;ArcNode;typedef struct VNode /定义顶点结点 char data; ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct /定义无向图 AdjList vertices; int vexnum,arcnum;ALGraph;typedef struct node /定义结点 char data; node *next;*Link;typedef struct /定义链表 Link head,tail; int len;LinkList;int LocateVex(MGraph G,char v)for(int i=0;iG.vexnum;+i)if(G.vexsi = v)return i;/找到return -1;/不存在int FirstAdjVex(MGraph G,int v)for(int i=0;iG.vexnum;i+)if(G.arcsvi.adj) return i;if(i=G.vexnum) return 0;int NextAdjVex(MGraph G,int v,int w)for(int i=w+1;inext=L.tail=new node; L.tail-next=NULL; L.len=0; return 0;void add(LinkList &L,int e)/在线性链表L的结尾添加一个结点 Link q=new node; L.tail-next=q; L.tail-data=e; L.tail=q; L.tail-next=NULL; L.len+;void Delete(LinkList &L,int &e)/出列，并将出列的元素值用e返回 if(L.head-next=L.tail) cout队列为空next; q=p-next; L.head-next=q; e=p-data; delete p; L.len-; void ArcAdd(ALGr