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

计算机科学与技术学院 实验报告课程名称：数据结构 专 业：计算机科学与技术班 级：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 struct 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->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(LNode); 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); /* 生成新结点 */ 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);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("%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("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 *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 *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)->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");scanf("%d",&m);printf("请输入多项式B的系数及对应位幂次：n");CreateList(&p2,m);printf("B");PolyoPrint(&p2);PolyoAdd(&p1,&p2);printf("相加后的");PolyoPrint(&p2);system("pause");return 0;3. 运行结果4. 实验总结合并多项式是指相同指数的项的系数相加，比较两个链表的节点的指数的大小，作为指针移动的条件，同事合并的过程中应消除系数项为零的节点。 实验三1. 实验题目 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild下标datalchildrchild 1 A 2 6 2 B 3 4 3 C 0 0 4 D 5 0 5 E 0 0 6 F 0 7 7 G 0 0和rchild的类型为bitree。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为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容量足够大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->rchild); / 构造右子树 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 front,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+)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);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 vexnode/头结点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<<"开始输入顶点表:"<<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>>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->adjlistsi.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=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<<"请输入开始遍历的顶点:"<<endl;cin>>Vi;DFStraversal(G,Vi); cout<<endl; return 0;3. 运行结果4. 实验体会在输入边表关系时，要注意因为是无向图，所以有两次建立边表的过程，不需要重复输入。 实验五1. 实验题目 二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。2. 程序核心代码typedef struct BiTNodeElemType data;struct BiTNode *lchild,*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); elsehead->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->rchild ,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->rchild)q=s;s=s->rchild;p->data=s->data;if(q!=p) q->rchild=s->lchild;else q->lchild=s->lchild;delete s;return true;bool deleteBST(BiTree Head,int number)if(!Head) return false;elseif(Head->data = number) return Delete(Head);else if(number < Head->data) return deleteBST(Head->lchild,number);else return deleteBST(Head->rchild,number);/主程序int main()BiTree Head;printf("建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): n");Head=NULL;int number,n;scanf("%d",&number);while(number!=-1)Head=createBST(Head,number);scanf("%d",&number); head=Head;printf("中序遍历二叉排序树为： n");printBST(Head);printf("n");printf("请输入要删除的结点: ");scanf("%d",&n);if(deleteBST(Head,n) printf("删除成功！n");else printf("删除失败！n");printf("删除之后的二叉排序树中序遍历为：n");printBST(Head);printf("n"); return 0;3. 运行结果 4. 实验体会二叉排序树的删除要注意分类讨论，删除的节点p为叶子节点时，不能简单的直接删除p，而要找到p的双亲节点，令双亲节点指向p的指针为NULL即可。