实验二链表的基本操作
一、实验目的
掌握链表的基本概念、结构的定义，通过设计程序掌握链表上的基本操作：建立、插入、删除、查找以及链表合并等，并理解线性表的两种存储结构：顺序表和链表的区别。
二、实验准备
1. 复习C语言中指针的用法，特别是结构体的指针的用法。
2. 了解链表（含带头结点的链表、循环链表）的概念，链表的结构定义方法。
单链表是线性表的链式存储表示，是用一组任意的存储单元依次存储线性表的数据元素。因此，为了表示每个数据元素a i与其直接后继元素a i+1之间的逻辑关系，对数据元素a i来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），而这部分就是用指针来完成的。
3. 掌握线性表在链式存储结构上实现基本操作：建立、查找、插入、删除等算法。
在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：
✧在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果
(查到时输出查到的数据，未查到时给出相关提示)。
✧在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以
它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，原因同实验
一，其次要注意插入的时候语句的顺序不可颠倒，否则出错。
例如：
p
s所指向结点要插入在p所指向的结点之后，则：
正确形式：s->next=p->next； p->next=s；
错误形式：p->next=s；
s->next=p->next(因为此时p->next已经指向s了)
在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删除后要回收空间。
例如：删除如上图所示s所指向的结点
p->next=p->next->next；
free(s);
4. 链表部分相关操作代码：
⑴单链表的结构定义：
#include
typedef int elemtype;
typedef struct lnode
{ elemtype data;
struct lnode *next;
}*linklist;
⑵建立单链表的算法
int n; /*n作为整个程序的全局变量*/
linklist *creat(void)
{ linklist *head, *p1, *p2;
n=0;
p1=p2=(linklist *)malloc(sizeof(linklist));
scanf(“%d”,&p1->data);
head=null;
while(p1->data!=0)
{ n=n+1;
if(n==1) head=p1;
else p2->next=p1;
p2=p1;
p1=(linklist *)malloc(sizeof(linklist));
scanf(“%d”,&p1->data);
}
p2->next=null;
return(head);
}
⑶单链表的插入算法
int insert(linklist *head, int i,elemtype e) { linklist *p, *s;
int j;
p=head; j=0;
while(p && j{ p=p->next;
++j;
}
if(!p||j>i-1)
{ printf(“无法插入”)；
return 0;
}
s=(linklist *)malloc(sizeof(lnode));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
⑷单链表的删除算法
int deltree(linklist *head,int i,elemtype e)
{ linklist *p, *q;
int j;l
p=head; j=0;
while(p->next && j{ p=p->next;
++j;
}
if(!(p->next)||j>i-1)
{ printf(“无法删除”);
return 0;
}
q=p->next;p->next=q->next;
e=q->data;
free(q);
return 1;
}
三、实验内容
1. /*函数link()的功能是将带头结点的单链表l2链接到l1的后面，程序中存在几处错误，
请改正并调试运行*/
#include "linklist.h"
void link(linklist l1,linklist l2)
{linklist p,q;
p=l1;
while (p->next)
p=q->next;
q=l2;
p->next=q;
free(l2);
}
void main()
{ linklist l1,l2;
l1=creat2(); /*生成带头结点的单链表l1*/
print(l1); /*输出单链表l1*/
l2=creat2(); /*生成带头结点的单链表l2*/
print(l2); /*输出单链表l2*/
link(l1,l2); /*将单链表l2链接到l1的后面*/
print(l1); /*输出单链表l1*/
}
2./* 编写一个函数perm,将带头结点单链表中的所有值为奇数的结点集中到链表的左边，
值为偶数的结点集中到链表的右边*/
#include "linklist.h"
linklist perm(linklist head)
{
linklist pre,p;
pre=head;
p=head->next;
while (p && p->data%2==1)
{ pre= p ;
p= p->next ;
}
while (p)
{ if (p->data%2==1)
{ pre->next=p->next;
p->next=head->next;
head->next=p;
p=pre->next;
}
else
{ pre=p;
p=p->next;
}
