数据结构实验报告201最新整理

1、 计算机科学与技术学院 实验报告课程名称：数据结构 专 业：计算机科学与技术班 级：2011 级 1 班 学 号： 201113137024 姓 名： 镇方权 指导老师： 邱奕敏 20 实验一1. 实验题目设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。2. 程序核心代码struct lnode int data; struct lnode *next; ; typedef stru

2、ct lnode *linklist;linklist union( linklist ha, linklist hb ) linklist head = (lnode*)malloc(sizeof(lnode); head->next = ha; lnode* pa,*pb,*ptmp; pa = ha->next; pb = hb->next; ptmp = ha; while ( pa&&pb ) if ( pa->data < pb->data ) ptmp = pa; pa = pa->next; else if ( pa-&

3、gt;data > pb->data ) lnode* lr = (lnode*)malloc(sizeof(lnode); lr->data = pb->data; lr->next = pa; ptmp->next = lr; ptmp = lr; pb = pb->next; else ptmp = pa; pa = pa->next; pb = pb->next; if ( pa ) ptmp->next = pa; else while ( pb ) lnode* lr = (lnode*)malloc(sizeof(lno

4、de); lr->data = pb->data; ptmp->next = lr; ptmp = lr; pb = pb->next; ptmp->next = null; free(head); return ha;int listinsert(linklist l,int i,int e) int j=0; linklist p=l,s; while(p&&j<i-1) p=p->next; j+; if(!p|j>i-1) return 0; s=(linklist)malloc(sizeof(struct lnode);

5、 /* 生成新结点 */ s->data=e; /* 插入l中 */ s->next=p->next; p->next=s; return 1; int main()linklist ha,hb;int n,i;int data; initlist(&ha);printf("请输入ha中数据的个数： ");scanf("%d",&n);printf("请依次输入ha中的数据：n");for(int i = 1;i <= n;i+)scanf("%d",&data

6、);listinsert(ha,i,data);printf("ha= ");linklist p = ha->next;while(p)printf("%d ",p->data);p = p->next;printf("n"); initlist(&hb);printf("请输入hb中数据的个数： ");scanf("%d",&n);printf("请依次输入hb中的数据：n");for(i = 1;i <= n;i+)scanf(&

7、quot;%d",&data);listinsert(hb,i,data);printf("hb= ");p = hb->next;while(p)printf("%d ",p->data);p = p->next;printf("n");printf("hb归并到ha后，新的ha=");p = union(ha,hb)->next;while(p)printf("%d ",p->data);p = p->next;printf("

8、n");system("pause");return 0;3. 运行结果 4.实验总结 要注意归并时若ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。 实验二1. 实验题目 结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。2. 程序核心代码typedef struct lnodeint data; /存储系数int flag; /存储对应幂数struct lnode *next;lnode;/建立带头结点的单链表，n项多项式void createlist(lnode

9、 *l, int n)lnode *p;int i = 0;*l = (lnode *) malloc (sizeof(lnode);(*l)->next = null; for (i = 0; i<n; +i)p = (lnode *) malloc (sizeof(lnode); scanf("%d%d",&(p->data),&(p->flag); p->next = (*l)->next;(*l)->next = p; /插入链表/多项式l1与l2对应项相加得到新的l2void polyoadd(lnode

10、*l1, lnode *l2) int ck;lnode *p,*q;p = null;q = null;q = (*l1)->next;while(q)ck = 0;p = (*l2)->next;while(p) if (q->flag = p->flag) ck = 1; break; p = p->next;if (ck = 1) /同类项合并p->data += q->data;q = q->next;else /否则，直接将非同类项插到l2最前面(*l1)->next = q->next;q->next = (*l2

11、)->next;(*l2)->next = q;q = (*l1)->next;int main()int m=0;lnode *p1,*p2;p1 = null;p2 = null;printf("设定多项式a的项数：n");scanf("%d",&m);printf("请输入多项式a的系数及对应位幂次：n");createlist(&p1,m);printf("a");polyoprint(&p1);printf("设定多项式b的项数：n");sca

12、nf("%d",&m);printf("请输入多项式b的系数及对应位幂次：n");createlist(&p2,m);printf("b");polyoprint(&p2);polyoadd(&p1,&p2);printf("相加后的");polyoprint(&p2);system("pause");return 0;3. 运行结果4. 实验总结合并多项式是指相同指数的项的系数相加，比较两个链表的节点的指数的大小，作为指针移动的条件，同事合并的过

13、程中应消除系数项为零的节点。 实验三1. 实验题目 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild下标datalchildrchild   1   a   2   6   2   b   3   4   3   c   0   0   4   d &

14、#160; 5   0   5   e   0   0   6   f   0   7   7   g   0   0和rchild的类型为bitree。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用

15、于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，二叉树的静态二叉链表如上图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a1.n，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。2. 程序核心代码 typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode, *bitree;typedef struct node /静态链表结点结构 char data; /结点数据 int row,lchild,rchild ; /下标，左右孩子node;node *st; /st容量足够大

16、static int length=0;static int num=0;void createbitree(bitree &t) char ch; scanf("%c",&ch); if (ch='#') t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) printf("error"); t->data = ch; / 生成根结点 createbitree(t->lchild); / 构造左子树 createbitree(t->rchi

17、ld); / 构造右子树 void preorder(bitree bt)/ 先序遍历二叉树，填写静态链表的“下标”和data域if (bt) st+num.data=bt->data;stnum.row=num;preorder(bt->lchild);preorder(bt->rchild);int locate(char x) /在静态链表中查二叉树结点的下标 int i; for (i=1;i<=num;i+)if (sti.data=x)return (i); bitree levelorderlocatep(bitree root,char x)int fr

18、ont,rear;bitree queuemaxsize,p;p = root;front = rear =0;if(p)queuerear+ = p;while(front < rear)p = queuefront+;if(p->data = x)return p;if(p->lchild)queuerear+ = p->lchild;if(p->rchild)queuerear+ = p->rchild;void dynatost (bitree t) int i;bitree p;preorder(t);for(i = 1;i <= num;i

19、+)p = levelorderlocatep(t,sti.data);if(p->lchild)sti.lchild = locate(p->lchild->data);elsesti.lchild=0;/无左孩子，其lchild域填0if(p->rchild)sti.rchild = locate(p->rchild->data);elsesti.rchild=0;/无右孩子，其rchild域填0int main()bitree t;printf("请输入二叉树各结点的值:n");createbitree(t);nodenum(t);

20、st = (node*)malloc(sizeof(struct node)*length);dynatost(t);show(st);return 0;3. 运行结果4. 实验体会 二叉树的建立是按照先序遍历的方式递归的建立的，因此在输入二叉树的节点中的值时，要注意#字符的个数。 实验四1. 实验题目 设无向图g有n个点e条边，编写算法建立g的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为o（n+e），且除邻接表本身所占空间之外只用o（1）辅助空间。2. 程序核心代码struct edgenode/表结点int endver;edgenode* edgenext;struct v

21、exnode/头结点char vertex;edgenode * edgelink;struct graph/无向图vexnode adjlistsmax_ver_num;int vexnum, arcnum;void creatadjlist(graph* g)int i,j,k;edgenode * p1;edgenode * p2;cout<<"请输入无向图的顶点数和边数:"<<endl;cin>>g->vexnum>>g->arcnum;cout<<endl;cout<<"

22、开始输入顶点表:"<<endl;for (i=1;i<=g->vexnum;i+)cin>>g->adjlistsi.vertex;g->adjlistsi.edgelink=null;cout<<endl;cout<<"开始输入边表信息:"<<endl; cout<<endl;for (k=1;k<=g->arcnum;k+)cout<<"请输入边<vi,vj>对应的顶点序号:"cin>>i>&

23、gt;j; cout<<endl;p1=new edgenode;p1->endver=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 dfs(graph *g, int i, int visited)cout<<g->adjlis

24、tsi.vertex<<" "visitedi=1;edgenode *p=new edgenode;p=g->adjlistsi.edgelink;if(g->adjlistsi.edgelink && !visitedp->endver)dfs(g,p->endver,visited);void dfstraversal(graph *g, char c)cout<<"该图的深度优先遍历结果为:"<<endl;int visitedmax_ver_num;for(int i=

25、1; i<=g->vexnum; i+)visitedi=0;for (int i=1;i<=g->vexnum;i+)if (g->adjlistsi.vertex=c) dfs(g,i,visited);break;for(int i=1;i<=g->vexnum;i+)if(visitedi=0)dfs(g,i,visited);cout<<endl;/主程序int main()graph * g=new graph;creatadjlist(g);printgaph(g);char vi;cout<<"请输入开

26、始遍历的顶点:"<<endl;cin>>vi;dfstraversal(g,vi); cout<<endl; return 0;3. 运行结果4. 实验体会在输入边表关系时，要注意因为是无向图，所以有两次建立边表的过程，不需要重复输入。 实验五1. 实验题目 二叉排序树采用二叉链表存储。写一个算法，删除结点值是x的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。2. 程序核心代码typedef struct bitnodeelemtype data;struct bitnode *lchil

27、d,*rchild;bitnode,*bitree;static bitree head;/建二叉排序树bitree createbst(bitree head,int number)bitree p;p=(bitree)malloc(sizeof(bitnode); p->data=number;p->lchild =p->rchild=null;if(head=null) return p;else if(p->data < head->data)head->lchild=createbst(head->lchild,number); els

28、ehead->rchild=createbst(head->rchild,number); return head;/求p的双亲bitree searchparent(bitree head,bitree p) if(head->lchild=p|head->rchild=p|head=p|head=null) return head; else if(p->data < head->data) return searchparent(head->lchild ,p); else return searchparent(head->rchi

29、ld ,p); /删除二叉排序树中结点pbool delete(bitree p)bitree q,s;q=(bitree)malloc(sizeof(bitnode);s=(bitree)malloc(sizeof(bitnode);if(!p->rchild&&!p->lchild) /删除的节点是叶子节点q=searchparent(head,p);if(q->lchild=p) q->lchild=null;else q->rchild=null;else if(!p->rchild) /左子树不为空，右子树为空searchparent(head,p)->lchild = p->lchild;free(p);else if(!p->lchild) /右子树不为空，左子树为空 searchparent(head,p)->rchild = p->rchild;free(p);else /左右子树都不为空q=p;s=p->lchild;while(s-