山东大学数据结构第一次实验实验报告.docx

实验1 ADT表的编程与实现C语言，是一种通用的、过程式的编程语言，广泛用于系统与应用软件的开发。具有高效、灵活、功能丰富、表达力强和较高的可移植性等特点，在程序员中备受青睐。Microsoft Visual C+是Microsoft公司推出的开发Win32环境程序具有集成开发环境，可提供编辑C语言，C+以及C+/CLI语言等可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock网络、3D控制界面。 本课程实验要求学生运用C语言编程完成数据结构课程中抽象数据类型及排序算法的编程实现，加深对教学内容的理解。实验目的：加深对抽象数据类型ADT表的理解；实验原理：参照课本p.44-49，及Figure3.6-3.13.实验内容：编写程序实现ADT表的定义，及常用操作：1) 判断表是否为空；2) 获取第i个节点的内容3) 删除4) 插入实验要求：1）复习C语言相关知识；2）实现完整的ADT表结构及操作，并给出应用。实验源程序： #include stdafx.h #include stdio.h #include stdlib.h #include malloc.htypedef struct node int data; struct node *pNext; /pNext为指向下一个节点的指针Node,*pNode; pNode CreateLinkList(); /创建链表函数bool IsEmpty(pNode); /定义IsEmpty(pNode)为布尔值，判断链表是否为空int FindTheNode(pNode pHead,int a,int length); /找出某一个节点的值void TraverseLinkList(pNode pHead); /遍历链表，获取链表中的数值int GetLengthLinklist(pNode pHead); /获取链表长度int Delete(pNode pHead,int x) ; /删除元素int Insert(pNode pHead,int b,int c); /插入元素void FreeLinkList(pNode pHead); /释放链表空间/int main() /主函数 int a,b,c,x,length; pNode pHead = NULL; /初始化头节点pHead为NULL pHead = CreateLinkList(); / 创建一个非循环单链表，并将该链表的头结点的地址赋给pHead if (IsEmpty(pHead) / 判断链表是否为空 printf (链表为空！n); return 0;else TraverseLinkList(pHead); /遍历链表 printf (链表为非空！n); length=GetLengthLinklist(pHead); /获取链表长度while(1) printf(获取第i个节点的内容，i=); scanf(%d,&a);if(FindTheNode(pHead,a,length)break; /找出第i个节点的值while(1) printf(请输入要删除的元素:); scanf(%d,&x); if(Delete(pHead,x) /在链表中将元素x删除 printf(删除元素%d后,x);break; printf(未找到该元素，删除失败n); TraverseLinkList(pHead);while(1) printf(请输入插入节点的位置:); scanf(%d,&b); printf(请输入插入节点的数值:); scanf(%d,&c);if(Insert(pHead,b,c) /在链表中插入元素 printf(在位置%d插入元素%d后,b,c);break; printf(未找到该位置，插入失败n);TraverseLinkList(pHead);FreeLinkList(pHead); /释放链表空间 return 0; /pNode CreateLinkList() /创建链表函数 int LEN,a; pNode pHead = (pNode)malloc(sizeof(Node); /动态分配内存 pNode pTail = pHead; pTail-pNext = NULL; /令链尾指向NULL printf(请输入创建的单向链表的节点个数:); scanf(%d,&LEN); for(int i = 0; i data = a; pTail-pNext = pNew; /pTail中的指针pNext指向pNew pNew-pNext = NULL; pTail = pNew; /新建的节点变为链尾 return pHead; /bool IsEmpty(pNode pHead) / 判断列表是否为空 return pHead-pNext=NULL; /int FindTheNode(pNode pHead,int a,int length) /找出某一个节点的值 if(alength) /判断要查找的节点位置是否正确 printf(链表中没有此节点n);return 0;else pNode p = pHead-pNext; for(int i = 0; i data);/当找到该节点时输出它的值 p = p-pNext; printf(n); return 1; /void TraverseLinkList(pNode pHead) /遍历链表，获取链表中的数值 printf(链表中各节点的值依次为：); pNode p = pHead-pNext; while(p!=NULL) /知道最后一个节点循环才停止 printf(%d ,p-data); p = p-pNext; printf(n); /int GetLengthLinklist(pNode pHead) /获取链表长度 int length=0; pNode p=pHead-pNext; while(p!=NULL) length+; p = p-pNext; return length;/int Delete(pNode pHead,int x) /删除元素 pNode p,q; q=p=pHead; p=p-pNext; /p指向头结点后第一个元素while(p) if(p-data=x) /找到要删除的元素 q-pNext=p-pNext; free(p); /释放该元素所在节点的空间 return 1; else q=p; /q始终指向p上一个节点 p=p-pNext; return 0; /int Insert(pNode pHead,int b,int c) /插入元素 pNode p,q; q=p=pHead; p=p-pNext; if(b0 & bi;i+) q=p; /q始终指向p上一个节点 p=p-pNext; pNode pNew = (pNode)malloc(sizeof(Node); /创建新节点并动态分配内存 pNew-data=c; pNew-pNext=p; q-pNext=pNew; return 1;else return 0;/ void FreeLinkList(pNode pHead) /释放链表空间 pNode p,q ; p=pHead-pNext; while (p != NULL) q=p-pNext; free(p); /释放各节点的空间 p=q; pHead-pNext=NULL; 实验结果：1)判断表是否为空创建链表，链表不为空。 链表为空。 2）获取第i个节点的内容输入要求获取的节点内容的位置正确，比如i=2，则得到第2个节点的内容为22。 输入要求获取的节点内容的位置不在链表中，比如i=8，则显示链表中没有此节点。 若输入节点位置不在链表中，则需继续输入正确位置，不然系统会一直要求输入节点i的值直到我们输入正确的节点位置。 3）删除输入要删除的元素在链表中，比如删除元素44，则链表中剩下的元素有11、22、33、55、66. 若输入要删除的元素不在链表中，比如要删除元素77，则显示未找到该元素，删除失败。 若输入要删除的元素不在链表中，则需继续输