数据结构实验报告14820.doc

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 data ) pTmp = pa; pa = pa-next; else if ( pa-data pb-data ) LNode* Lr = (LNode*)malloc(

3、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; fre

4、e(head); return ha;int ListInsert(LinkList L,int i,int e) int j=0; LinkList p=L,s; while(p&jnext; j+; if(!p|ji-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(请输入

5、ha中数据的个数： );scanf(%d,&n);printf(请依次输入ha中的数据：n);for(int i = 1;i 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 next;while(p)printf(%d ,p-data);p = p-next;printf(n);printf(hb归并到ha后，新的ha=);p = Union(ha,hb)-next;wh

6、ile(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

7、项多项式void CreateList(LNode *L, int n)LNode *p;int i = 0;*L = (LNode *) malloc (sizeof(LNode);(*L)-next = NULL; for (i = 0; idata),&(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 =

8、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);pri

9、ntf(请输入多项式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. 实验总结合并多项式是指相同指数的项的系数相加，比较两个链表的节点的指数的大小，作为指针移动的条件

10、，同事合并的过程中应消除系数项为零的节点。 实验三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。例

11、如，二叉树的静态二叉链表如上图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表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 in

12、t 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

13、=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 data = x)re

14、turn 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 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 ma

15、in()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. 程

16、序核心代码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请输入无向图的顶点数和边数:G-vexnumG-arcnum;coutendl;cout开始输入顶点表:endl;for (i=

17、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.ed

18、gelink=p2;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;for(int i=1; ivexnum; i+)visitedi=0;for (int i=1;ivexnum;i+)if (G-

19、adjlistsi.vertex=c) DFS(G,i,visited);break;for(int i=1;ivexnum;i+)if(visitedi=0)DFS(G,i,visited);coutendl;/主程序int main()Graph * G=new Graph;CreatAdjList(G);PrintGaph(G);char Vi;cout请输入开始遍历的顶点:Vi;DFStraversal(G,Vi); coutdata=number;p-lchild =p-rchild=NULL;if(head=NULL) return p;else if(p-data data)he

20、ad-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 data) return searchParent(head-lchild ,p); else return searchParent(head-rc

21、hild ,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;fre

22、e(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(Hea

23、d-data = number) return Delete(Head);else if(number 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

24、(%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即可。