实验二链表的基本操作.doc

实验二 链表的基本操作学号：0700710319 姓名：梁浩然 实验日期：2009年4月25日1、 实验目的（1） 学会单链表结点的定义（2） 掌握单链表的基本运算，熟悉对单链表的一些基本操作和具体函数的定义。（3） 加深对链表的理解，逐步培养解决实际问题的编程能力。2、 实验要求（1） 熟练掌握链表的存储结构及其基本操作。（2） 理解所给出的算法，掌握链表在实际中的应用。（3） 将上机程序调试通过，并能独立完成一至两个拓展题目。3、 实验内容从键盘输入数据，创建一个初始链表。通过调用定义的基本操作函数来实现单链表上的插入、删除元素等操作。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对有关算法的理解。4、 实验方法第一步:定义单链表的存储结构。第二步：编写单链表操作的具体函数定义。第三步：使用定义的单链表并调用单链表的一些操作，实现具体运算。具体函数的定义有：1） insert(L,i,x)在单链表的第i个元素之前插入一个新元素x.2） deletet(L,i) 删除单链表的第i个元素。3） listprint(L) 输出单链表。5、实验步骤所给实例程序经调试修改如下：#include stdio.h#include malloc.h /*包含动态分配内存函数*/#define NULL 0#define TRUE 1#define FALSE 0typedef int elemtype;typedef struct node /*链表结点类型定义*/ elemtype data; /*结点数据域*/ struct node *next; /*结点的指针域*/ linklist;linklist *creatlist() /*创建链表函数-以按下任意建开始创建，以输入字符？表示结束标志*/ char ch; int x; linklist *head,*r,*p; p=(linklist*)malloc(sizeof(linklist); head=p; p-next=NULL; r=p; ch=getchar(); while(ch!=?) scanf(%d,&x); p=(linklist*)malloc(sizeof(linklist); p-data=x; p-next=NULL; r-next=p; r=r-next; ch=getchar(); return (head); int locate(linklist *head,elemtype k) /*定位检索函数-如链表中存在值为k的结点，则返回真，否则返回假*/ linklist *s; s=head-next; while(s!=NULL) if(s-data!=k)s=s-next; else return TRUE; return FALSE; void insert(linklist *head,int i,elemtype x) /*在链表head的第i个位置插入元素x*/ linklist *s,*p; int j; p=head; j=0; while(p-next&jnext;j+; if(!p|ji-1) printf(error!); s=(linklist *)malloc(sizeof(linklist); if(!s) printf(overflow!); s-data=x; s-next=p-next; p-next=s; void delete1(linklist *head,int i) /*删除链表的第i个结点*/ int j=0; linklist *p,*s,*q; p=head;j=0; while(p-next!=NULL)&(jnext; j+; if(p-next!=NULL) q=p-next; p-next=p-next-next; free(q); else printf(illegal delete position,delete failed!); void print(linklist *head) /*打印出链表head中各个结点的值*/ linklist *p; p=head-next; while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n); void main() /*主函数*/ linklist *head; /*定义指向链表的指针head*/ int x; int i,j; printf(please input the initial node and start by any key(?execpt)end with ?n); head=creatlist(); printf(we have created a linklist as follow:n); print(head); printf(now start search,please input the search value:); scanf(%d,&x); printf(n); if(locate(head,x) printf(exsist!n); else printf(not exsist!n); printf(start insert operation,please input insert position:); scanf(%d,&i); insert(head,i,x); printf(after insertion:n); print(head); printf(now start delete operation,input the delete position please:); scanf(%d,&j); delete1(head,j); printf(after deletion:n); print(head); 6、 思考题调试好上述程序，拓展内容：（1） 定义一个逆置函数diverse(L),把链表进行逆置。在主程序中调用该函数，分析操作结果。#include stdio.h#include malloc.h /*包含动态分配内存函数*/#define NULL 0#define TRUE 1#define FALSE 0typedef int elemtype;typedef struct node /*链表结点类型定义*/ elemtype data; /*结点数据域*/ struct node *next; /*结点的指针域*/ linklist;linklist *creatlist()/*创建链表函数-以按下任意建开始创建，以输入字符？表示结束标志*/ char ch; int x; linklist *head,*r,*p; p=(linklist*)malloc(sizeof(linklist); head=p; p-next=NULL; r=p; ch=getchar(); while(ch!=?) scanf(%d,&x); p=(linklist*)malloc(sizeof(linklist); p-data=x; p-next=NULL; r-next=p; r=r-next; ch=getchar(); return (head); void diverse(linklist *L) / 本算法将带头结点的单链表L逆置。 /算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。 linklist *p=L-next,*s; / p为工作指针，指向当前元素，s为p的后继指针 L-next=NULL; /头结点摘下，指针域置空。算法中头指针L始终不变 while (p) s=p-next; / 保留后继结点的指针 p-next=L-next; / 逆置 L-next=p; p=s; / 将p指向下个待逆置结点 / 算法结束void print(linklist *head) /*打印出链表head中各个结点的值*/ linklist *p; p=head-next; while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n); void main() linklist *head; /*定义指向链表的指针head*/ head=creatlist(); print(head); /打印出链表head中各结点的值 diverse(head); print(head); /打印出逆置后链表head中各结点的值运行结果如下：（2） 定义一个函数delsame(L),把链表中重复的元素删除掉，只保留一个。在主程序中调用该函数，分析操作结果。delsame(L)函数如下，其余部分的定义与函数与上题相同，在main函数中调用delsame（L）。void delsame(linklist *L) /*删除相同的元素*/ node *p,*q; int e; p=L-next; while(p!=NULL) q=p; e=p-data; p=p-next; while(p!=NULL) if(e=p-data) /*将相同的元素赋值为0 在下面判断如果元素值为0 释放这个接点*/ p-data=0; p=p-next; p=q; p=p-next; p=L;