实验一：单链表的插入和删除
实验目的：
单链表的数据域是字符串，且不允许重复的串插入表中，删除操作是根据输入的字符串，先找到相应的结点，后删除之。
预习要求：
要求熟悉并且掌握单链表的建表、插入、查找和删除算法以及单链表数据结构的实现等。
实验步骤：
下面给出单链表的建表、插入、查找和删除算法以及单链表的数据结构，请学员根据下面给出的算法编程，完成这次实验。
1.链表的建立
在线性链表上进行的任何操作，其前提是必须建立这条链。建立链表我们可以利用C语言中所提供的标准函数来实现。
链表的结点结构可以定义如下：
typedef struct node
{
elemtype data; /* elemtype可以是任何类型 */
struct node * next;
}sInode;
下面给出建立n个结点的线性链表的算法：
void creatlink(sInode head,int n)
{
sInode *p,*q;
int i;
if (n==0)
return;
head=(sInode*) malloc(sizeof(sInode));
p=head;
scanf("%c",&p->data);
for (i=2;i<=n;i++)
{
q=(sInode*)malloc(sizeof(sInode));
p->next=q;
p=q;
scanf("%c",&p->data);
}
p->next=NULL;
}
2.链表的插入
一般地，链表结构实现的手稿操作所插位置可能有以下四种情况： （设head为头指针）
1)原来的链表是空表，则插入结点应作为表头结点，其操作：
head=x,x->next=NULL
2)在链表中第一个结点位置之前插入，则插入结点应作为新的表头结点，其操作：
x->next=head,head=x
3)在链表中间某个位置插入，在q结点之后，p结点之前，其操作：
q->next=x;x->next=p
4)如果链表中根本不存在所指定的结点，则将新结点在链表尾插入。其操作：
x->next=p->next,p->next=x; 或 p->next=x,x->next=NULL
在插入操作中需要确定插入的位置，因此常常包含查询操作，即在链表中查找数据域中关键值为key的结点，然后实施插入运算，要根据上面假设的四种情况，下面给出线性表的插入算法：
void inserlist(head,key,b)
sInode *head;
elemtype key,b;
/* 在head为入口的链表中，在与key值相同结点之前插入数值b的结点 */
{
sInode *x,*p,*q;
x=(sInode *) malloc(sizeof(sInode));
x->data=b;/* 建立新结点Ｘ，数值为b */
if(head==NULL)
{
head=x;
x->next=NULL; /* 链表空，新结点作为链表唯一一个结点心＊／
}
else
{
if (head->data==key)
{
x->next=head;
head=x; /* 插入在链表第一个结点之前，插入结为新的表头 */
}
else
{
p=head;
while(p->data!=key&&p->next!=NULL)
{
/* 循环查找，q是p的前趋结点心 */
q=p;
p=p->next;
}
if (p->data=key)
{
q->next=x;
x->next=p; /* 插入在表末，新结点作为新的表尾 */
}
}
}
}
该算法的循环查询中设置变量q是一旦访问到p->data=key的存储结点p的前趋地点，从而能实现在q和p之间插入。
3.链表的查找
在链表的操作中，往往只知道某一结点的关键值，因此需要确定该结点的地址，因为一旦结点的地址确定，那么就能知道该结点的全部信息；而且还能通过链指针找到该结点后继结点的情况，这对结点的插入和删除都是非常必要的。因此，只有通过查找才能确定所需要结点的地址，则，第一，查找是否成功，即被查结点是否在链表中；第二，经过查找，得到查找结点的地址和该结点的前趋结点地址。下面就来介绍链表的查找。
设线性链表的数值是有序的，且从小到大排列，链表入口为head，客观存在查找结点的关键值为key。通过查找可确定该结点是否链表中，若在链中，则显示“查找成功”，不在链表中，则显示“查找失败”。若查找成功，就能得到被查找结点的地址和前趋结点地址。下面给出线性链表查找的算法：
void searchli(head,key)
sInode * head;
elemtype key;
{
sInode *p,*q;
p=head;
q=p;
while(p!=NULL&&p->data<key)
{
q=p;
p=p->next;
}
if(p->data==key&&p!=NULL)
{
printf("查找成功");
return;
}
else
printf("查找失败");
}
该算法若查找成功，p是关键值为key结点的地址，q是p的前趋结点的地址。 若被查找链表的数据是无序的，则可修改while语句中的条件，去掉(p->data<key),改为(p->data!=key)。这样查找的效率就大大降低。原因很简单，无序的链表，一旦查找失败，必须查遍全表，而有序链表中就不必这样，如有n个结点链表，其查找的平均概率为n/2。
4.链表的删除
链表的删除操作，需要从头到到尾查找链表以找到数据域值等x的结点，若查找到指定的结点，则删除该结点后，只要将其前趋结点的指针域修改为指向被删除结点的后继结点即可；同时，把被删除的结点送还空间，以备再次使用。若查找不到指定结点，则给出提示信息。
删除某一结点，则必须知道被删除结点的前趋结点。设p指向被删除结点，q指向p的前趋结点，则删除的基本操作步骤为
q->next=p->next
同时为了充分利用被删除结点的空间，可用C语言中的标准函数free()来释放空间。
下面讨论被删除结点在链表中的位置有四种删除的情况。
1)链表只有一个结点，该结点就是被删除的结点，其操作：
head=NULL 或 head=head->next
2)被删除的结点是链中第一个结点，其操作：
head=head->next
3)被删除的结点在链表的中间，其中删除结点为p，前趋结点为p，其操作：
q->next=p->next
4)被删除的结点在链尾，其中删除结点为p，前趋结点为q，其操作：
q->next=NULL 或 q->next=p->next
以上四种操作中，不难看出第一、第二种情况的操作可以用head=head->next表示，而第三、第四种情况可以用q->next=p->next来表示。下面给出链表删除的完整算法：
void deletelink(head,key)
sInode * head;
elemtype key;
/* 在head为入口的链表中删除值为key的结点 */
{
sInode *p,*q;
p=head;
q=p;/* 设置前趋结点 */
while(p!=NULL&&p->data!=key) /* 查找删除结点的位置 */
{
q=p;
p=p->next;
}
if(head==NULL)
{
printf("无此结点");
return;
}
else
if (head==p)
head=p->next;/* 删除结点 */
else
q->next=p->next; /* 删除链中间或链尾结点 */
free(p);/* 释放空间单元 */
}
对于长度为n 的链表，删除的主要时间是花费在查找数据域值为指定的关键值key的结点上。假若在线性表各位置上的删除概率相等，则查找时的平均比较次数为：
(1+2+……+n)/n=(n+1)/2
而每次的比较时间是一个常数，所以插入和删除的时间复杂度为O(n)。
实验内容：
1． 单链表的连接：设la,lb为两个数据域为整数的单链表的头结点，且其中的数据都是递增有序的，现在要求将两个单链表连接在一起，连接后的单链表以lc为头结点，且其中的数据是递减有序的(允许有相同的元素出现)。(设la中的数据元素个数为10个(0,2,4,6,8,10,12,14,16,18)，lb中的数据元素个数为10个(0，3，6，9，12，15，18，21，24，27)。)
2． 单链表的交集：设la,lb为两个数据域为整数的单链表的头结点，且其中的数据都是递增有序的，现在要求这两个单链表的交集，将结果保存在以lc为头结点的单链表中。(设la 中的数据元素个数为10个(1,3,5,7,9,11,13,15,17,19)，lb中的数据元素个数为10个(0,3,6,9,12,15,18,21,24,27))
因为两个实验是在同一种数据结构上操作的，所以可以将两者合并成一个程序，并分别用两个函数来实现上述两个操作。
//main.cpp 主程序
#include "node.h" //包含单链表数据结构的头文件
void exercise1(void) //实现实验1的函数 |
