一、实验目的：
1、复习C语言程序设计中的知识。
2、掌握线性表的链式存储结构的表示和实现方法。
3、掌握单链表基本操作的算法实现。
二、实验内容：
1．建立单链表。
2．在单链表上实现插入、删除和查找等操作。
三、实验要求：
编写实现单链表的基本算法（初始化、查找、插入、删除等）的函数，并在此基础上设计一个主程序完成如下功能：
⑴初始化字符型单链表H;
⑵采用尾插法建立单链表H，如（a,b,c,d,c）；
⑶输出单链表H的长度；
⑷输出单链表H的第i个元素，如输出单链表H的第3个元素；
⑸输出给定元素的位置，如输出元素a的位置；
⑹在第i个元素前插入给定元素，如在第4个元素前插入元素f；
⑺删除单链表H的第i个元素，如删除单链表H的第3个元素。
⑻输出单链表
四、实验步骤：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
// 单链表结构类型的定义
typedef int elemtype; /结点的数据类型设为整形/
typedef struct node /定义单链表结点类型/
{
elemtype data;
/结点的数据域/
struct
node *next; /结点的指针域/
}LinkList; /单链表的类型名为LinkList/
//LinkList *head,p; / head 是指向单链表类型LinkList的指针变量/
//1 初始化单链表
LinkList *Init_LinkList()
{
LinkList
*head; //
head
= (LinkList*)malloc(sizeof(LinkList)); //生成头结点指针
if
(head == NULL) //如果申请空间失败，返回空指针
{
printf("初始化失败！\n");
return
0;
}
else
{
printf("初始化成功！\n");
return
head;
}
}
//2 用尾插法建立单链表
LinkList *Creat_LinkListR(LinkList
*head)
{
elemtype
ix;
LinkList *p, tail;
/ *head,*tail 分别为头指针和尾指针 */
head->next
= NULL; /置头结点指针域为空/
tail
= head;
printf(“请输入数据直到遇0终止：\n”);
scanf("%d",
&ix); //输入第一个数据
while
(ix != 0)
{
p
= (LinkList *)malloc(sizeof(LinkList));
if
(p == NULL)
{
printf("新结点申请空间失败，无法继续建立单链表！\n");
return
head;
}
p->data
= ix; /为新结点数据域赋值/
tail->next
= p;
tail
= p;
tail->next
= NULL;
scanf("%d",
&ix);
}
printf(“单链表建立成功！\n”);
return
head;
}
//3 求单链表的长度
int LinkList_Length(LinkList * head)
{
LinkList
*p = head; /p指向头结点/
int
j = 0;
while
(p->next != NULL)
{
p
= p->next; //指针不为空，指针后移，计数器加一
j++;
}
printf(“该单链表的长度为：%d\n”,j);
return
j;
}
//4 输出单链表的第i个元素
LinkList *GetData_LinkList(LinkList
*head, int i)
{
LinkList
*p;
int
j = 0;
if
(i <= 0) //指定的位置非法时返回空
{
printf("非法！\n");
return
NULL;
}
p
= head;
while
(p->next != NULL && j < i) // 不是目标节点且还有后继结点时继续查找
{
p
= p->next;
j++;
}
if
(i == j)
{
printf("要找的元素为：%d\n", *p);
return
p; //找到目标节点，返回当前指针
}
else
{
printf("非法！\n");
return
NULL;
}
}
//5 给定元素的值查找
LinkList *Search_LinkList(LinkList
*head, elemtype key)
{
LinkList
*p;
int
i = 0;
p
= head->next; //指针指向首结点
while
(p != NULL)
{
if
(p->data != key)
{
p
= p->next;
i++;
}
else
{
break; //找到结点退出循环
}
}
printf(“所查找的元素位置为：%d\n”, i+1);
return
p;
}
//6 在指定序号前插入运算
void InserAfter_LinkList(LinkList *p,
LinkList *s) //单链表的插入 后插运算
{
s->next
= p->next; //新结点连入链表
p->next
= s; //修改前趋结点的指针域
}
void InsertBefore_LinkList(LinkList
*head, LinkList *p, LinkList *s)
{
LinkList
*q;
q
= head;
while
(q->next != p)
{
q
= q->next;
}
s->next
= p;
q->next
= s; //修改相应结点的指针域
}
int InsertNo_LinkList(LinkList *head,
LinkList *s, int i)
{
LinkList
*p;
if
(i <= 0)
{
p
= NULL;
}
else
if (i == 1)
{
p
= head;
}
else
{
p
= GetData_LinkList(head, i - 1);//搜索第i-1个结点
}
if
(p == NULL)
{
printf("位置不合法！\n");
return
0;
}
else
{
InserAfter_LinkList(p,
s);
printf("插入成功！\n");
return
1;
}
}
//7 删除指定位置的结点
int DeleteNo_LinkList(LinkList *head,
int i)
{
LinkList
*p, *r;
if
(i <= 0)
{
p
= NULL;
}
else
if (i == 1)
{
p
= head;
}
else
{
p
= GetData_LinkList(head, i - 1);
}
if
(p == NULL)
{
return
0;
}
else
{
r
= p->next;
if
(r == NULL)
{
return
0;
}
p->next
= r->next;
free(r);
printf("删除成功!");
return
1;
}
}
//单链表的删除 删除后继结点
int DeleteAfter_LinkList(LinkList *p) //单链表的删除 删除后继结点 删除p的后继结点，成功返回1，否则返回0
{
LinkList
*r;
if
(!p)
{
return
0;
}
r
= p->next;
if
(!r)
{
return
0;
}
p->next
= r->next; //将结点r从链表上摘除
free®; //释放结点占用的内存空间
return
1;
}
//8 单链表的输出
int Print_LinkList(LinkList*head) //单链表的遍历
{
LinkList
*p = head->next; //
if
(p == NULL) //链表为空，返回值为0
{
printf("单链表为空！\n");
return
0; //
}
while
(p != NULL) //当前结点不为空
{
printf("%3d",
p->data); //输出当前结点的数据
p
= p->next; //移动指针指向下一个结点
}
printf("\n");
return
1;
}
//9 置空表
LinkList *SetNull_LinkList(LinkList
*head) //置空表
{
while
(head->next)
{
DeleteAfter_LinkList(head); //依次删除每个结点
}
printf(“单链表置空成功！\n”);
return
head;
}
int main()
{
LinkList
*s,*head;
int
key;
int
i;
int
num;
printf("\t\t---------------欢迎使用单链表的基本操作------------------\n");
printf("\t\t\t\t
1 初始化单链表 \n");
printf("\t\t\t\t
2 采用尾插法建立单链表 \n");
printf("\t\t\t\t
3 输出单链表的长度 \n");
printf("\t\t\t\t
4 输出单链表的第i个元素 \n");
printf("\t\t\t\t
5 输出给定的元素的位置 \n");
printf("\t\t\t\t
6 在第i个元素前插入给定的元素\n");
printf("\t\t\t\t
7 删除单链表的第i个元素 \n");
printf("\t\t\t\t
8 输出单链表 \n");
printf("\t\t\t\t
9 置空单链表 \n");
printf("\t\t\t\t
10 退出系统 \n");
printf("\t\t----------------------------------------------------------\n");
printf("\t\t请选择(1-10)?;
while
(1)
{
scanf("%d",
&num);
switch
(num)
{
case
1:
{
head
= Init_LinkList();
/*if
(head!= NULL) //如果申请空间失败，返回空指针
{
//printf("初始化成功！\n");
return
head;
}*/
break;
};
case
2:
{
Creat_LinkListR(head);
break;
};
case
3:
{
LinkList_Length(head);
break;
};
case
4:
{
printf("请输入要找的为第i个元素:");
scanf("%d",
&i);
*GetData_LinkList(head,
i);
//printf("要找的元素为：%d\n",p);
}break;
case
5:
{
printf("请输入链表中的元素:");
scanf("%d",&key);
*Search_LinkList(head,
key);
//printf("所查找的元素位置为：%d\n", key);
break;
};
case
6:
{
s = (LinkList*)malloc(sizeof(LinkList));
printf("在指定序号前插入运算:");
scanf("%d",
&i);
printf("插入的元素为：");
scanf("%d",
&s->data);
InsertNo_LinkList(head,
s, i);
break;
};
case
7:
{
printf("删除单链表的第i个元素: ");
scanf("%d",
&i);
DeleteNo_LinkList(head,
i);
break;
};
case
8:
{
printf("输出单链表");
Print_LinkList(head);
break;
};
case
9:
{
SetNull_LinkList(head);
break;
};
case
10:
{
printf("按任意键返回主菜单！\n");
break;
};
default:printf("\n
没有此功能，重新输入\n");
break;
}
}
}
五、实验结果：
六、实验总结：
链表是通过指针描述元素关系的一种数据结构，它可以是物理地址不连续的物理空间，不能随机访问链表元素，必须从表头开始，一步一步搜索元素。它的优点是：对于数组，可以动态的改变数组的长度，分配物理空间。