《数据结构(C语言版)实验报告》由会员分享，可在线阅读，更多相关《数据结构(C语言版)实验报告（25页珍藏版）》请在金锄头文库上搜索。
1、数据结构(C语言版) 实验报告学院 计算机科学与技术专业 计算机大类强化学号 xxx班级 xxx姓名 xxx指导教师 xxx实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤：1、 分析、理解给出的示例程序。2、 调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结
2、点并删除。3、 修改程序：（1） 增加插入结点的功能。（2） 将建立链表的方法改为头插入法。程序代码:#includestdio.h#includestring.h#includestdlib.h#includectype.htypedef struct node /定义结点char data10; /结点的数据域为字符串struct node *next; /结点的指针域ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表LinkList Crea
3、tList(void); /函数，用头插入法建立带头结点的单链表ListNode *LocateNode(); /函数，按值查找结点void DeleteList(); /函数，删除指定值的结点void printlist(); /函数，打印链表中的所有值void DeleteAll(); /函数，删除所有结点，释放内存ListNode * AddNode(); /修改程序：增加节点。用头插法，返回头指针/=主函数=void main()char ch10,num5;LinkList head;head=CreatList(); /用头插入法建立单链表，返回头指针printlist(head)
4、; /遍历链表输出其值printf( Delete node (y/n):); /输入y或n去选择是否删除结点scanf(%s,num);if(strcmp(num,y)=0 | strcmp(num,Y)=0)printf(Please input Delete_data:);scanf(%s,ch); /输入要删除的字符串DeleteList(head,ch);printlist(head);printf( Add node ? (y/n):); /输入y或n去选择是否增加结点scanf(%s,num);if(strcmp(num,y)=0 | strcmp(num,Y)=0)head=A
5、ddNode(head);printlist(head);DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(void) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 ListNode *s,*r,*pp; r=head; r-next=NULL; printf(Input # to end ); /输入#代表输入结束 printf(nPlease input Node_data:); scanf(%s,ch); /输入各结
6、点的字符串 while(strcmp(ch,#)!=0) pp=LocateNode(head,ch); /按值查找结点，返回结点指针if(pp=NULL) /没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode);strcpy(s-data,ch);r-next=s;r=s;r-next=NULL;printf(Input # to end );printf(Please input Node_data:);scanf(%s,ch); return head; /返回头指针/=用头插入法建立带头结点的单链表=LinkList CreatLis
7、t(void)char ch100;LinkList head,p;head=(LinkList)malloc(sizeof(ListNode); head-next=NULL;while(1)printf(Input # to end ); printf(Please input Node_data:);scanf(%s,ch); if(strcmp(ch,#) if(LocateNode(head,ch)=NULL) strcpy(head-data,ch);p=(LinkList)malloc(sizeof(ListNode); p-next=head;head=p;else break
8、;return head; /=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode *p=head-next; /从开始结点比较 while(p!=NULL & strcmp(p-data,key)!=0) /直到p为NULL或p-data为key止p=p-next; /扫描下一个结点 return p; /若p=NULL则查找失败，否则p指向找到的值为key的结点/=修改程序：增加节点=ListNode * AddNode(LinkList head) char ch10;Li
9、stNode *s,*pp; printf(nPlease input a New Node_data:); scanf(%s,ch); /输入各结点的字符串pp=LocateNode(head,ch); /按值查找结点，返回结点指针printf(ok2n);if(pp=NULL) /没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode);strcpy(s-data,ch);printf(ok3n);s-next=head-next;head-next=s;return head;/=删除带头结点的单链表中的指定结点=void DeleteLi
10、st(LinkList head,char *key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找结点的 if(p=NULL ) /若没有找到结点，退出printf(position error);exit(0); while(q-next!=p) /p为要删除的结点，q为p的前结点q=q-next; r=q-next; q-next=r-next; free(r); /释放结点/=打印链表=void printlist(LinkList head) ListNode *p=head-next; /从开始结点打印 while
11、(p)printf(%s, ,p-data);p=p-next; printf(n);/=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p-next)r=p-next;free(p);p=r;free(p);实验结果：Input # to end Please input Node_data:batInput # to end Please input Node_data:catInput # to end Please input Node_data:eatInput # to end Please
12、input Node_data:fatInput # to end Please input Node_data:hatInput # to end Please input Node_data:jatInput # to end Please input Node_data:latInput # to end Please input Node_data:matInput # to end Please input Node_data:#mat, lat, jat, hat, fat, eat, cat, bat, Delete node (y/n):yPlease input Delete_
