数据结构实验报告.doc

数据结构实验报告1、 设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。源代码:#includeusing namespace std;struct Nodeint data;struct Node * next;void createstack(struct Node *headp)int n;struct Node * p;*headp=NULL;cinn;while(n!=0)p=(struct Node *)malloc(sizeof(struct Node);p-data=n;p-next=*headp;*headp=p;cinn;int outputNode(struct Node *head)int length=0;struct Node *p;p=head;while(p)coutdatanext;length+;coutendl;return length;void sortNod(struct Node * head,int n)int i,j,temp;struct Node *p1,*p2;p1=*head;for(i=0;inext)p2=p1-next;for(j=i+1;jnext)if(p1-datap2-data)temp=p2-data;p2-data=p1-data;p1-data=temp;bool isinclude(int n,struct Node *head)struct Node *p;p=*head;while(p!=NULL)if(n=p-data)return true;p=p-next;return false;struct Node * insertNode(int x,struct Node *headp)struct Node *other,*last,*current;other=(struct Node *)malloc(sizeof(struct Node);other-data=x;current=*headp;while(xcurrent-data¤t-next!=NULL)last=current;current=current-next;if(xdata)if(current=*headp)other-next=*headp;*headp=other;elseother-next=current;last-next=other;elseother-next=NULL;current-next=other;return other;void merge(struct Node *heada,struct Node *headb)struct Node *pa,*pb;pa=*heada;pb=*headb;while(pb!=NULL)if(!isinclude(pb-data,heada)insertNode(pb-data,heada);pb=pb-next;int main()struct Node *heada,*headb,*pa,*pb;int lengtha,lengthb;coutinput Node ha numbers end of 0:endl;createstack(&heada);coutinput Node hb numbers end of 0:endl;createstack(&headb);coutoutput Node ha: endl;lengtha=outputNode(heada);sortNod(&heada,lengtha);coutoutput Node hb: endl;lengthb=outputNode(headb);sortNod(&headb,lengthb);merge(&heada,&headb);pa=heada;pb=headb;coutinput Node ha numbers:n;while(pa)coutdatanext;coutendl;return 0;运行结果:2、 结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。源代码:#includeusing namespace std;void creatPolyn(struct PolynNod *head);void sortNod(struct PolynNod * head);bool isinclude(int n,struct PolynNod *head);struct PolynNod * insertNode(int x,double y,struct PolynNod *headp);int merge(struct PolynNod *heada,struct PolynNod *headb);struct PolynNoddouble coef;int expn;struct PolynNod * next; void creatPolyn(struct PolynNod *head)struct PolynNod *p;double c;int e;*head=NULL;cince;while(c!=0|e!=0)p=(struct PolynNod *)malloc(sizeof(struct PolynNod);p-coef=c;p-expn=e;p-next=*head;*head=p;cinc;cine;void sortNod(struct PolynNod * head)int i,j;int temp1;doubletemp2;struct PolynNod *p1,*p2;p1=*head;for(i=0;p1!=NULL;i+,p1=p1-next)p2=p1-next;for(j=i+1;p2!=NULL;j+,p2=p2-next)if(p1-expnp2-expn)temp1=p2-expn;p2-expn=p1-expn;p1-expn=temp1;temp2=p2-coef;p2-coef=p1-coef;p1-coef=temp2;bool isinclude(int n,struct PolynNod *head)struct PolynNod *p;p=*head;while(p!=NULL)if(n=p-expn)return true;p=p-next;return false;struct PolynNod * insertNode(int x,double y,struct PolynNod *headp)struct PolynNod *other,*last,*current;other=(struct PolynNod *)malloc(sizeof(struct PolynNod);other-expn=x;other-coef=y;current=*headp;while(xcurrent-expn¤t-next!=NULL)last=current;current=current-next;if(xexpn)if(current=*headp)other-next=*headp;*headp=other;elseother-next=current;last-next=other;elseother-next=NULL;current-next=other;return other;int merge(struct PolynNod *heada,struct PolynNod *headb)struct PolynNod *pa,*pb,*paa;bool temp;pa=*heada;pb=*headb;paa=*heada;while(pb!=NULL)temp=isinclude(pb-expn,heada);if(temp=false)insertNode(pb-expn,pb-coef,heada);elsewhile(paa)if(paa-expn=pb-expn)paa-coef=paa-coef+pb-coef;paa=*heada;break;paa=paa-next;pb=pb-next;return 0;int main()struct PolynNod *heada,*headb,*pa,*pb;coutinput Polynas information,end of 0:endl;creatPolyn(&heada);sortNod(&heada);coutinput Polynbs information,end of 0:endl;creatPolyn(&headb);sortNod(&heada);merge(&heada,&headb);pa=heada;pb=headb;coutcoef=0)pa=pa-next;continue;elsecoutcoef expnnext;coutendl;return 0;运行结果:3、 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild和rchild的类型为bitre。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，二叉树的静态二叉链表如上图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a1.n，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。源代码:#include#include#include#includeusing namespace std;struct treenode *createBiTree(struct treenode *p,int x);void traverse(struct treenode *p);int nodeNum(struct treenode *p);void initArray(struct treenode *p);void transform(struct treenode *p);struct treenodechar data;struct treenode *left,*right;int arrayorder;struct treenode *createBiTree(struct treenode *p,int x)if(*p=NULL)*p=(struct treenode *)malloc(sizeof(struct treenode);if (*p=NULL) printf(out of memory,press any key to quit.n);exit(0); (*p)-data=x;(*p)-left=(*p)-right=NULL;(*p)-arrayorder=0;else if(xdata)createBiTree(&(*p)-left,x);elsecreateBiTree(&(*p)-right,x);return (*p);static int length=0;int nodeNum(struct treenode *p)if(p!=NULL)length+;nodeNum(p-left);nodeNum(p-right);return length;void traverse(struct treenode *p)if(p!=NULL)coutdataleft);traverse(p-right);struct treeArraychar data;int lchild,rchild;static struct treeArray *a=NULL;static int num=0;void initArray(struct treenode *p)if(p!=NULL)anum.data=p-data;p-arrayorder=num;num+;initArray(p-left);initArray(p-right);static int i=0;void transform(struct treenode *p)if(p!=NULL)if(p-left!=NULL)ai.lchild=p-left-arrayorder;if(p-right!=NULL)ai.rchild=p-right-arrayorder;i+;transform(p-left);transform(p-right);void main(void)char x;struct treenode *root=NULL;printf(输入数据以#结束:n);cinx;while(x!=#)createBiTree(&root,x);cinx;printf(先序输出二叉树:);traverse(root);printf(n);length=nodeNum(root);a=(struct treeArray *)malloc(sizeof(struct treeArray)*length); if (a=NULL) printf(out of memory,press any key to quit.n); exit(0); /用0初始化数组for(int i=0;ilength;i+)ai.data=ai.lchild=ai.rchild=0;initArray(root);transform(root);printf(将二叉树转化为数组之后为:n);printf(下标 data lchild rchildn);for(int j=0;jlength;j+)cout j aj.data aj.lchild aj.rchildendl;free(a);运行结果:4、 设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。源代码:#include#include #include#include#define Max_Ver_Num 20 using namespace std;struct edgenodeint endver; edgenode* edgenext; ;struct vexnode char vertex; edgenode * edgelink; ;struct Graph vexnode adjlistsMax_Ver_Num;int vexnum, arcnum; ;struct QueueNodeint nData; QueueNode* next;struct QueueList QueueNode* front; QueueNode* rear;void EnQueue(QueueList* Q,int e) QueueNode *q=new QueueNode;q-nData=e;q-next=NULL;if(Q=NULL) return;if(Q-rear=NULL) Q-front=Q-rear=q;elseQ-rear-next=q;Q-rear=Q-rear-next;void DeQueue(QueueList* Q,int* e)if (Q=NULL) return;if (Q-front=Q-rear) *e=Q-front-nData;Q-front=Q-rear=NULL;else*e=Q-front-nData;Q-front=Q-front-next;void CreatAdjList(Graph* G)int i,j,k;edgenode * p1;edgenode * p2;cout请输入无向图的顶点数和边数:G-vexnumG-arcnum;coutendl;cout开始输入顶点表:endl;for (i=1;ivexnum;i+)cinG-adjlistsi.vertex;G-adjlistsi.edgelink=NULL;coutendl;cout开始输入边表信息:endl; coutendl;for (k=1;karcnum;k+)cout请输入边对应的顶点序号:;cinij; coutendver=j;p1-edgenext=G-adjlistsi.edgelink;G-adjlistsi.edgelink=p1;p2=new edgenode;p2-endver=i;p2-edgenext=G-adjlistsj.edgelink;G-adjlistsj.edgelink=p2;void PrintGaph(Graph * G)edgenode *p; for(int k=1;kvexnum;k+) coutadjlistsk. vertex; p=G-adjlistsk.edgelink; while(p!=NULL) coutendver; p=p-edgenext; if(p!=NULL)cout; coutendl; void DFS(Graph *G, int i, int visited)coutadjlistsi.vertexadjlistsi.edgelink; if(G-adjlistsi.edgelink & !visitedp-endver)DFS(G,p-endver,visited);void DFStraversal(Graph *G, char c)cout该图的深度优先遍历结果为:endl;int visitedMax_Ver_Num;int i;for(i=1; ivexnum; i+)visitedi=0; for (i=1;ivexnum;i+)if (G-adjlistsi.vertex=c) DFS(G,i,visited); break;for(i=1;ivexnum;i+)if(visitedi=0)DFS(G,i,visited);coutendl;void main()Graph * G=new Graph;CreatAdjList(G);PrintGaph(G);char Vi;cout请输入开始遍历的顶点:Vi;DFStraversal(G,Vi); coutendl;运行结果：5、 二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。源代码：#include#includetypedef struct nodeint key;struct node*lch,*rch;bitnode;bitnode*creat_bt(); bitnode*search(bitnode*root,int data); void searchx(bitnode*root,int data); void display(bitnode*t); bitnode*deletex(bitnode*t,int data); bitnode*add(bitnode*t,int k); int n=1; void main() bitnode*t;int a,key;t=creat_bt();display(t);printf(请输入所要删除的结点的key值:);scanf(%d,&key);t=deletex(t,key);display(t);bitnode*creat_bt() int k;bitnode*t=NULL,*s,*f;printf(请输第%d个关键字key的值(以输入0为结束):,n);scanf(%d,&k);while(k!=0)n+; s=(bitnode*)malloc(sizeof(bitnode);s-key=k;s-lch=NULL;s-rch=NULL;if(t=NULL)t=s; elsef=search(t,k);if(k=f-key) printf(n提示:已存在该元素，请重新输入);n-;else if(kkey)f-lch=s;else f-rch=s;printf(请输入第%d个关键字key的值(以输入0为结束):,n);scanf(%d,&k);return t;bitnode*search(bitnode*root,int data) bitnode*p=NULL,*q=root;while(q)p=q;if(data=q-key) return q; else if(datakey)