实验二 单链表实现

实 验 报 告课程名称 数据结构课程设计 实验项目 单链表的实现 实验仪器 PC机一台 学 院_信息管理学院_专 业 电子商务 班级/学号_电子商务1401_学生姓名 _实验日期 _12.27_成 绩 _ 指导教师 _北京信息科技大学信息管理学院（课程上机）实验报告实验课程名称: 数据结构课程设计 专业: 电子商务 班级: 商务1401 学号: 姓名: 成绩: 实验名称单链表的实现实验地点小营学院机房实验时间12.291. 实验目的：1） 理解线性表的逻辑特点；2） 掌握单链表的定义及C语言实现； 3） 熟练掌握在单链表中实现各种基本操作；4） 掌握使用单链表解决一些简单应用问题的编程。2. 实验要求：1) 学时为4学时；2）在上机前完成源程序； 3）能在机器上正确、调试运行程序；4）本实验需提交实验报告；5）实验报告文件命名方法：实验2_xx班_学号后两位_姓名.doc3. 实验内容和步骤：1) 基于单链表实现线性表的以下操作： a) 在表头插入元素b) 在表尾插入元素c) 在指定的位置i插入元素d) 删除操作e) 查找元素f) 求表长度g) 清空操作h) 判断线性表是否为空i) 按位序打印线性表中的元素2) 单链表的简单应用：a) 调用基本操作编写算法删除第i个开始的k个元素；b) 计算单链表中值为x的元素的个数；c) 将x插入到单链表的适当位置上，以保持单链表中元素的有序性；d) 将线性表元素进行就地逆置e) 将两个单链表合并为一个单链表。 4. 实验过程：1)基于单链表实现线性表的以下操作： 在表头插入元素int Insert_First(LinkList *Head_pointer,ElemType x)Node *p;P=(LinkList)malloc(sizeof(Node);if(p=NULL)return OverFlow;p-data=x;p-next=*Head_pointer;*Head_pointer=p;Return OK;在表尾插入元素int Insert_Last(LinkList *Head_pointer,ElemType x)Node *p,*q;P=(LinkList)malloc(sizeof(Node);if(p=NULL)return OverFlow;p-data=x;p-next=NULL;q=*Head_pointer;if(q=NULL)*Head_pointer=p;elsewhile(q-next!=NULL)q=q-next;q-next=p;Return OK;在指定的位置i插入元素int Insert_i (LinkList *Head_pointer,ElemType x,int i)Node *p,*q;P=(LinkList)malloc(sizeof(Node);if(p=NULL)return OverFlow;p-data=x;if(i=0)p-next=*Head_pointer;*Head_pointer=p;return OK;elseq=*Head_pointer;while(q-next!=NULL&i1)q=q-next;i-;if(q!=NULL)p-next=q-next;q-next=p;return OK;return Error; 删除操作int Delete_LinkList (LinkList *Head_pointer,ElemType x)Node *p,*q;p=*Head_pointer;if(p-data=x)*Head_pointer=(*Head_pointer)-next;free(p);return OK;q=p;p=p-next;return Error; 查找元素LinkList Location_LinkList(LinkList Head,ElemType x)LinkList p;p=Head;while(p!=NULL)if(p-data=x)break;p=p-next;return p; 求表长度int Length_LinkList(LinkList Head)Node *p;int sum=0;p=Head;while(p!=NULL)sum+;p=p-next;return sum; 清空操作void SetNull_LinkList(LinkList *Head_pointer)Node *p,*q;p=*Head_pointer;while(p!=NULL)q=p;p=p-next;free(q);*Head_pointer=NULL;判断线性表是否为空 void IfNull_LinkList(LinkList *Head_pointer)if(*Head_pointer=NULL)returnTrue;else return False; 按位序打印线性表中的元素void Show_LinkList(LinkList Head)Node *p;printf(n);p=Head;if(p=NULL)printf(n空表!);while(p!=NULL)printf(%d,p-data);p=p-next;2)单链表的简单应用：调用基本操作编写算法删除第i个开始的k个元素；计算单链表中值为x的元素的个数；将x插入到单链表的适当位置上，以保持单链表中元素的有序性；将线性表元素进行就地逆置将两个单链表合并为一个单链表。1.调用基本操作编写算法删除第i个开始的k个元素；#include stdio.h#include stdlib.htypedef struct nodeint data;struct node *next;Node,*LinkList;void Delete_LinkList(LinkList *Head_pointer,int i,int k) int j=i+k-1; Node *p,*q,*m,*n;q=*Head_pointer;while(q-next!=NULL&i1)n=q;q=q-next;i-;p=*Head_pointer;while(p-next!=NULL&j1)p=p-next;j-;while(q!=p)m=q;q=q-next;free(m); n-next=p-next;free(p);int insert_First(LinkList *Head_pointer,int x) Node *p; p=(LinkList)malloc(sizeof(Node); if(p=NULL) return -1; p-data=x; p-next=*Head_pointer; *Head_pointer=p; return 1;void Show_LinkList(LinkList Head) Node *p; printf(n);p=Head;if(p=NULL)printf(n NULL);while(p!=NULL)printf( %d,p-data);p=p-next;int main ()int m;int i,k; LinkList Head; Head=NULL; scanf(%d %d,&i,&k); for(m=0;mdata=x)sum+;p=p-next;return sum;int insert_First(LinkList *Head_pointer,int x) Node *p; p=(LinkList)malloc(sizeof(Node); if(p=NULL) return -1; p-data=x; p-next=*Head_pointer; *Head_pointer=p; return 1;void Show_LinkList(LinkList Head) Node *p; printf(n);p=Head;if(p=NULL)printf(n NULL);while(p!=NULL)printf( %dn,p-data);p=p-next;int main ()int m,x,sum; LinkList Head; Head=NULL; scanf(%d,&x); for(m=0;mdatanext;return sum;int insert_i(LinkList *Head_pointer,int x,int i)Node *p,*q;p=(LinkList)malloc(sizeof(Node);if(p=NULL)return -1;p-data=x;if(i=0)p-next=*Head_pointer;*Head_pointer=p;return 1;elseq=*Head_pointer;while(q-next!=NULL&i1)q=q-next;i-;if(q!=NULL)p-next=q-next;q-next=p;return 1;return -2;void Show_LinkList(LinkList Head) Node *p; printf(n);p=Head;if(p=NULL)printf(n NULL);while(p!=NULL)printf( %d,p-data);p=p-next;int main ()int i,a7=10,20,30,40,50,60,70;int x,sum; LinkList Head; Head=NULL; scanf(%d,&x); for(i=0;inext; q-next=Head; Head=q; return Head;int insert_First(LinkList *Head_pointer,int x) Node *p; p=(LinkList)malloc(sizeof(Node); if(p=NULL) return -1; p-data=x; p-next=*Head_pointer; *Head_pointer=p; return 1;void Show_LinkList(LinkList Head) Node *p; printf(n);p=Head;if(p=NULL)printf(n NULL);while(p!=NULL)printf( %dn,p-data);p=p-next;int main ()int m; LinkList Head; LinkList HL; Head=NULL; for(m=0;mnext)p=p-next;p-next=HT;int insert_First(LinkList *Head_pointer,int x) Node *p; p=(LinkList)malloc(sizeof(Node); if(p=NULL) return -1; p-data=x; p-next=*Head_pointer; *Head_pointer=p; return 1;void Show_LinkList(LinkList Head) Node *p; printf(n);p=Head;if(p=NULL)printf(n NULL);while(p!=NULL)printf( %d,p-data);p=p-next;int main ()int m; LinkList Head; LinkList HT; Head=NULL; HT=NULL; for(m=0;m20;m+) if(!insert_First(&Head,m) break; for(m=0;m10;m+) if(!insert_First(&HT,m) break;Show_LinkList(Head); Show_LinkList(HT); contact(Head,HT);Show_LinkList(Head); return 0;5. 实验总结：理解线性表的逻辑特点；掌握了单链表的定义及C语言实现。但是还有很多不清楚的地方运行时有许多错误。说明：1. 实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模版供学生使用；2. 实验准备由学生在实验或上机之前填写，教师应该在实验前检查；3. 实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；4. 实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；5. 源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。