数据结构单链表实验报告.doc
*-洛阳理工学院实验报告系别计算机系班级 学号姓名课程名称数据结构实验日期11.7实验名称链表的基本操作成绩实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，Visual C+6.0实验内容：1. 问题描述以单链表为存储结构实现以下基本操作：(1) 在第i个元素前插入一个新元素。(2) 查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提示信息。(3) 删除第i个元素，若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息。2. 数据结构类型定义typedef struct LinkNodeint Value;struct LinkNode * Next;Node,*LinkList;3. 模块划分（1）初始化链表：void InitList(LinkList * L);（2）创建链表:尾插法：int CreateFromTail(LinkList L); （3）在指定位置插入元素：int InsList(LinkList L,int i,int e); （4）在指定位置删除元素：int DelList(LinkList L,int i,int *e); 返回值说明：返回ERROR插入失败，返回OK插入成功; （5）按位置查找链表元素：int GetList(LinkList L,int i,int *e);4. 详细设计void init_linklist(LinkList *l)/*对单链表进行初始化*/*l=(LinkList)malloc(sizeof(Node); /*申请结点空间*/(*l)->next=NULL; /*置为空表*/void CreateFromHead(LinkList L) Node *s;char c;int flag=1; while(flag) /* flag初值为1，当输入"$"时，置flag为0，建表结束*/c=getchar(); if(c!=$)s=(Node*)malloc(sizeof(Node); /*建立新结点s*/s->data=c;s->next=L->next;/*将s结点插入表头*/L->next=s;elseflag=0;void CreateFromTail(LinkList L) Node *r, *s;char c;int flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s->data=c;r->next=s;r=s;elseflag=0;r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ Node * Get (LinkList L, int i)/*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置; 否则返回NULL*/ int j;Node *p;p=L;j=0; /*从头结点开始扫描*/ while (p->next!=NULL)&&(j<i) p=p->next; /* 扫描下一结点*/j+; /* 已扫描结点计数器 */if(i = j)return p; /* 找到了第i个结点 */else return NULL; /* 找不到，i0或i>n */ Node *Locate( LinkList L,ElemType key)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/ Node *p;p=L->next; /*从表中第一个结点开始 */while (p!=NULL)if (p->data!=key)p=p->next; else break; /*找到结点值=key时退出循环 */return p; int InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/ Node *pre,*s;int k;pre=L; k=0; /*从"头"开始，查找第i-1个结点*/while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/ pre=pre->next;k=k+1; /*查找第i-1结点*/if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ printf("插入位置不合理!");return ERROR;s=(Node*)malloc(sizeof(Node); /*申请一个新的结点S */s->data=e; /*值e置入s的数据域*/s->next=pre->next;/*修改指针，完成插入操作*/pre->next=s;return OK;int DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/ Node *pre,*r;int k;pre=L;k=0;while(pre->next!=NULL && k<i-1)/*寻找被删除结点i的前驱结点i-1使p指向它*/ pre=pre->next; k=k+1;/*查找第i-1个结点*/if(!(pre->next) /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/printf("删除结点的位置i不合理!");return ERROR;r=pre->next;pre->next=pre->next->next; /*修改指针，删除结点r*/*e = r->data;free(r); /*释放被删除的结点所占的内存空间*/printf("成功删除结点!");return OK;intListLength(LinkList L)/*求带头结点的单链表L的长度*/ Node *p;int j;p=L->next;j=0; /*用来存放单链表的长度*/while(p!=NULL) p=p->next;j+;return j;/*j为求得的单链表长度*/ 5.测试数据及结果实验总结：在调试的时候发现在头插法的时候出现错误，经过逻辑思考与调试，发现错误所在，并且更改。
