实验二 单链表实现

1、实 验 报 告课程名称 数据结构课程设计 实验项目 单链表的实现 实验仪器 PC机一台 学 院_信息管理学院_专 业 电子商务 班级/学号_电子商务1401_学生姓名 _实验日期 _12.27_成 绩 _ 指导教师 _北京信息科技大学信息管理学院（课程上机）实验报告实验课程名称: 数据结构课程设计 专业: 电子商务 班级: 商务1401 学号: 姓名: 成绩: 实验名称单链表的实现实验地点小营学院机房实验时间12.291. 实验目的：1） 理解线性表的逻辑特点；2） 掌握单链表的定义及C语言实现； 3） 熟练掌握在单链表中实现各种基本操作；4） 掌握使用单链表解决一些简单应用问题的编程。2.

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插入到单链表的适当位置上，以保持单链表中元素的有序性；

3、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,ElemT

4、ype 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)mal

5、loc(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&&i>1)q=q->next;i-;if(q!=NULL)p->next=q->next;q->next=p;return OK;return Error; 删除操作int Delete_LinkList (LinkList *Head_p

6、ointer,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_Lin

7、kList(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)r

8、eturnTrue;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插入到单链表的适当位置上，以保持单链表中元素的有序性；将线性表元素进行就地逆置将两

9、个单链表合并为一个单链表。1.调用基本操作编写算法删除第i个开始的k个元素；#include "stdio.h"#include "stdlib.h"typedef 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&&i>1)n=

10、q;q=q->next;i-;p=*Head_pointer;while(p->next!=NULL&&j>1)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_po

11、inter; *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(

12、m=0;m<7;m+) if(!insert_First(&Head,m) break; Show_LinkList(Head); Delete_LinkList(&Head,i,k); Show_LinkList(Head); return 0; 2.计算单链表中值为x的元素的个数#include "stdio.h"#include "stdlib.h"typedef struct nodeint data;struct node *next;Node,*LinkList;int Location_LinkList(LinkLis

13、t Head,int x)Node *p;int sum=0;p=Head;while(p!=NULL)if(p->data=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(LinkLis

14、t 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;m<7;m+) if(!insert_First(&Head,m) break; Show_LinkList(Head

15、); sum=Location_LinkList(Head,x);printf("%dn",sum); return 0;3.将x插入到单链表的适当位置上，以保持单链表中元素的有序性#include "stdio.h"#include "stdlib.h"typedef struct nodeint data;struct node *next;Node,*LinkList;int Location_LinkList(LinkList Head,int x)Node *p;int sum=0;p=Head;while(p!=NULL)

16、if(p->data<=x)sum+;p=p->next;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&&i>1)q=q->nex

17、t;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; LinkLis

18、t Head; Head=NULL; scanf("%d",&x); for(i=0;i<7;i+) if(insert_i(&Head,ai,i)!=1) break; Show_LinkList(Head); sum=Location_LinkList(Head,x); if(insert_i(&Head,x,sum)!=1) printf("fail!n"); Show_LinkList(Head); return 0;4.将线性表元素进行就地逆置#include "stdio.h"#include

19、 "stdlib.h"typedef struct nodeint data;struct node *next;Node,*LinkList;LinkList op_LinkList(LinkList Head)Node *p,*q; p=Head; Head=NULL; while(p) q=p; p=p->next; q->next=Head; Head=q; return Head;int insert_First(LinkList *Head_pointer,int x) Node *p; p=(LinkList)malloc(sizeof(Node)

20、; 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; LinkL

21、ist HL; Head=NULL; for(m=0;m<7;m+) if(!insert_First(&Head,m) break; Show_LinkList(Head); HL=op_LinkList(Head); Show_LinkList(HL); return 0;5.将两个单链表合并为一个单链表#include "stdio.h"#include "stdlib.h"typedef struct nodeint data;struct node *next;Node,*LinkList;void contact(LinkList Head,LinkList HT)Node *p;p=Head;while(p->next)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_pointe