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

1、实验1 ADT表的编程与实现C语言，是一种通用的、过程式的编程语言，广泛用于系统与应用软件的开发。具有高 效、灵活、功能丰富、表达力强和较高的可移植性等特点，在程序员中备受青睐。MicrosoftVisual C+是Microsoft公司推出的开发 Win32环境程序具有集成开发环境，可提供编辑C语言，C+以及C+/CLI语言等可视化集成编程系统。它不但具有程序框架自动生成、 灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，Win Sock网络、3D控制界面。本课程实验要求学生运用C语言编程完成数据结构课

2、程中抽象数据类型及排序算法的编程实现，加深对教学内容的理解。实验目的：加深对抽象数据类型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 nodeint data;struct node *pNe

3、xt;/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,

4、int c); void FreeLinkList(pNode pHead);/遍历链表，获取链表中的数值/获取链表长度/删除元素/插入元素/释放链表空间/int main()/主函数 int a,b,c,x,length;pNode pHead = NULL;/pHead = CreateLinkList();/if (IsEmpty(pHead)/初始化头节点pHead为NULL创建一个非循环单链表，并将该链表的头结点的地址赋给判断链表是否为空pHeadprintf ( 链表为空！ n);return 0; elseTraverseLinkList(pHead);链表为非空！ n);/遍历

5、链表printf (length=GetLengthLinklist(pHead);/获取链表长度while(1)printf( 获取第i个节点的内容,scanf(%d, &a);i=);if(FindTheNode(pHead,a,length)break;/找岀第i个节点的值while(1)printf(请输入要删除的元素:);scanf(%d, &x);if(Delete(pHead,x) printf( 删除元素 4后,x);break; /在链表中将元素x删除printf(”未找到该元素，删除失败n); TraverseLinkList(pHead);while(1)/创建链表函数/

6、动态分配内存/令链尾指向NULL:）;/创建新节点/pTail 中的指针pNext指向pNew/新建的节点变为链尾/判断列表是否为空/找岀某一个节点的值/判断要查找的节点位置是否正确printf（”请输入插入节点的位置：）;scanf(%d,&b);printf(请输入插入节点的数值：)；scanf(%d, &c);if(lnsert(pHead,b,c)/在链表中插入元素 printf( 在位置 4插入元素 4后”,b,c);break; printf(未找到该位置，插入失败n);TraverseLinkList(pHead);FreeLinkList(pHead);/ 释放链表空间retu

7、rn 0; /pNode CreateLinkList() int LEN,a;pNode pHead = (pNode)malloc(sizeof(Node);pNode pTail = pHead;pTail-p Next = NULL;printf(请输入创建的单向链表的节点个数scanf(%d,&LEN);for(int i = 0; i data = a;pTail-pNext = pNew;pNew- p Next = NULL;pTail = pNew;return pHead;/bool lsEmpty(pNode pHead)return pHead-pNext=NULL;/

8、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-

9、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;while(p)if(p-data=x)/遍历链表，获取链表中的数值/知道最后一个节点循环才停止/获取链表长度/删除元素/p指向头结点后第一个元素/找到要删除的元素q_pNext=p_pNext;free(p);r

10、eturn 1;else q=p;p=p_pNext;return 0;/int lnsert(pNode pHead,int b,int c)pNode p,q;q=p=pHead;p=p-pNext;if(b0 & bi;i+)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 !=

11、NULL) q=p-pNext;free(p);p=q; pHead-pNext=NULL;/释放该元素所在节点的空间/q始终指向p上一个节点/插入元素/判断要求插入元素的位置是否正确/q 始终指向p上一个节点/创建新节点并动态分配内存/释放链表空间/释放各节点的空间实验结果：1）判断表是否为空创建链表，链表不为空。 链表为空。2）获取第i个节点的内容 输入要求获取的节点内容的位置正确，比如i=2，则得到第2个节点的内容为22。输入要求获取的节点内容的位置不在链表中，比如i=8，则显示链表中没有此节点。1 rr= 若输入节点位置不在链表中，则需继续输入正确位置，不然系统会一直要求输入 节点i的

12、值直到我们输入正确的节点位置。: 11:22;33B - 6B亞 33 44 56 eei=121 - - X IJ !u 1 I Is3）删除11、 输入要删除的元素在链表中，比如删除元素44,则链表中剩下的元素有22、33、55、66.6=2s!sB5r7IT44y-*容 fl-66弓5 胡33112233釜関若输入要删除的元素不在链表中，比如要删除元素-44各节点的值依次为：1L 22 33 55 6S77,则显示未找到该元素,删除失败。2212 3 4 5 6 12 3 4 r&TT-m-TTT-TTT 一旨 HSS肃 边注0 若输入要删除的元素不在链表中，则需继续输入在链表中的元素，不然系统会一直要求输入要删除的元素。K 2 3 4 5 6 U Tli 2 3 4 -5 .6 -li :：61 L t着胃ME青青665644332211 PP用44血4）插入输入要插入的位置正确，比如插入到位置1中，则在位置1插入元素0后链表中各节点的数值依次为0、11、22