数据结构链表C语言实现.docx
《数据结构链表C语言实现.docx》由会员分享，可在线阅读，更多相关《数据结构链表C语言实现.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构链表C语言实现
数学与信息技术学院2016~2017（下）学年
计科专业2015级《数据结构》实验报告2
学号：
2015201018姓名：
汪继超
实验名称
线性表的链式存储结构
完成时间
一.实验目的
1．掌握单链表的概念及其各种运算的原理。
2．通过对单链表的建立及几种基本运算等的算法实现，掌握线性表的链式存储结构、各种运算和指针的表示及应用等内容。
初步掌握运用链式结构的编程和调试程序的能力。
3．用C语言实现并上机调试通过，认真填写实验报告
二.实验要求
4．采用链式存储结构完成。
5．注意类C和C的转换。
6．上机调试通过，认真书写实验报告。
三.实验原理
链表是一种动态存储结构。
线性表的链式存储结构的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。
线性表的一个结点由两个域组成：
存放自身的数据和存放直接后继结点存储位置的指针域。
用指针相连接的
结点序列称为链表，若逻表中每个结点只包含一个指针域，则此链表为线性链表或单链表。
通常链表中的每个结点可以有若干个数据域和多个链域。
我们常用C语言中的“指针”类型来描述线性链表。
四.实验内容
（1）定义函数create_linklist（）:
建立一个具有n个结点的单向链表L，要求返回表头指针；
（2）定义函数count_node（）:
统计结点个数，要求以表头指针作为调用函数，返回结点个数；
（3）定义函数insert_node（）:
在链表L的第I个结点前插入一个结点，要求以表头指针作为调用函数，无返回值；
（4）定义函数delete_node（）:
删除链表L的第I个元素，要求以表头指针作为调用函数，无返回值；
（5）定义函数print_node（）:
输出单链表;
（6）以上每次操作结束，输出单链表，要求以表头指针作为调用函数，无返回值。
实验过程：
#include
#include
#include
#include
typedefintElemType;
typedefstructLnode{
ElemTypedata;
structLnode*next;
}Lnode,*LinkList;
voidprint_node（LinkListL）;
voidcolor（constunsignedshortcolor1）//颜色函数
{
if（color1>=0&&color1<=15）
SetConsoleTextAttribute（GetStdHandle（STD_OUTPUT_HANDLE）,color1）;
else
SetConsoleTextAttribute（GetStdHandle（STD_OUTPUT_HANDLE）,7）;
}
LinkListcreate_linklist（LinkListL）//建立链表L，返回表头指针；
{
inti,n;
Lnode*p,*q;//L为头指针，p为新元素指针，q为表尾指针
q=L;
L->next=NULL;
color（13）;
printf（"\n请输入您要创建的数据条数：
"）;
scanf（"%d",&n）;
printf（"\n请输入数据：
"）;
for（i=0;i{
p=（Lnode*）malloc（sizeof（Lnode））;
scanf（"%d",&p->data）;
q->next=p;
q=p;
}
fflush（stdin）;//清空在此前输入缓冲区
q->next=NULL;
printf（"\n已创建数据：
"）;
print_node（L）;
color（10）;
returnL;
}
voidprint_node（LinkListL）//打印
{
Lnode*p;
p=L->next;
while（p）
{
printf（"%5d",p->data）;
p=p->next;
}
printf（"\n"）;
}
intcount_node（LinkListL）//统计
{
intcount=0;
Lnode*p;
p=L->next;
while（p）
{
p=p->next;
count++;
}
color（13）;
printf（"\n统计得总共记录为：
%d条\n",count）;
color（10）;
returncount;
}
voidinsert_node（Lnode*L,inti,ElemTypex,intcount）//插入；
{
Lnode*p,*q;
intk,s;
count=count_node（L）;
color（13）;
printf（"\n链表当前数据：
"）;
print_node（L）;
color（10）;
printf（"\n请输入插入的位置和元素，以空格隔开：
"）;
scanf（"%d%d",&k,&s）;
color（13）;
/*先判断位置是否合法，合法执行插入操作，反之则不执行。
*/
if（k<1||k>count-1）
{
printf（"\n插入元素的位置不合法！
\n"）;
}
else
{
printf（"\n链表插入元素前：
"）;
print_node（L）;
p=（LinkList）malloc（sizeof（Lnode））;//为插入元素开辟新空间
p->data=s;
for（q=L;k>1;k--）
q=q->next;
p->next=q->next;
q->next=p;
count++;
printf（"\n链表插入元素后：
"）;
print_node（L）;
}
color（10）;
}
voiddelete_node（Lnode*L,inti,intcount）
{
Lnode*p,*q;
p=L;
count=count_node（L）;
intk;
color（13）;
printf（"\n链表当前数据：
"）;
print_node（L）;
color（10）;
printf（"\n请输入删除元素的位置：
"）;
scanf（"%d",&k）;
color（13）;
if（k<1||k>count）printf（"\n您输入的元素位置不合法！
\n"）;
else
{
printf（"\n链表删除元素前：
"）;
print_node（L）;
while（--k>0）p=p->next;
q=p->next;
p->next=p->next->next;
free（q）;
count--;
printf（"\n链表删除元素后：
"）;
print_node（L）;
}
color（10）;
}
voidLocateElem_node（Lnode*L,ElemTypex）//查找操作
{
Lnode*p;
p=L->next;
intj=1,flag=0;
color（13）;
printf（"\n链表当前数据：
"）;
print_node（L）;
color（10）;
printf（"\n请输入要查找的元素：
"）;
scanf（"%d",&x）;
color（13）;
while（p）
{
if（p->data==x）
{
flag=1;
printf（"\n找到元素:
%d位置为%d\n",p->data,j）;
color（10）;
}
j++;
p=p->next;
}
if（flag==0）printf（"\n没有找到该元素\n"）;
color（10）;
}
voidmodify_node（Lnode*L,ElemTypee1,ElemTypee2）//修改操作
{
Lnode*p;
p=L->next;
intj=1,n,flag=0;
color（13）;
printf（"\n链表当前数据：
"）;
print_node（L）;
color（10）;
printf（"\n请输入要修改的元素：
"）;
scanf（"%d",&e1）;
color（13）;
while（p）
{
if（p->data==e1）
{
flag=1;
printf（"\n找到元素:
%d位置为%d\n",p->data,j）;
printf（"\n\n[1.修改2.不修改]请输入:
"）;
scanf（"%d",&n）;
if（n!
=1）break;
if（n==1）
{
printf（"\n元素%d改为:
",e1）;
scanf（"%d",&e2）;
p->data=e2;
printf（"\n修改成功！
\n"）;
printf（"\n修改后链表的数据：
"）;
print_node（L）;
break;
}
color（10）;
}
j++;
p=p->next;
}
if（flag==0）printf（"\n没有找到该元素\n"）;
color（10）;
}
voidMenu（）
{
printf（"线性表的链式存储结构\n\n"）;
printf（"************************************菜单**************************************\n"）;
printf（"*1.建表2.统计*\n"）;
printf（"*3.插入4.删除*\n"）;
printf（"*5.打印6.修改*\n"）;
printf（"*7.查找0.退出*\n"）;
printf（"******************************************************************************\n"）;
}
voidmain（）
{
inte1=0,e2=0,c=0,e=0,i=0,n,flag;/*c=count*/
chara;
Lnode*L;
L=（LinkList）malloc（sizeof（Lnode））;
color（10）;
start:
do
{
Menu（）;
printf（"\n请选择你需要操作的步骤（0--7）:
"）;
fflush（stdin）;/*清空在此前输入缓冲区*/
scanf（"%d",&n）;
if（n>=0&&n<=7）
{
flag=1;break;
}
else
{
flag=0;
system（"cls"）;
printf（"您输入有误，请重新选择!
\n"）;
}
}
while（flag==0）;
while（flag==1）
{
switch（n）
{
case1:
create_linklist（L）;break;/*建表*/
case2:
count_node（L）;break;/*统计*/
case3:
insert_node（L,i,e,c）;break;/*插入*/
case4:
delete_node（L,i,c）;break;/*删除*/
case5:
printf（"\n链表当前数据：
"）;print_node（L）;break;/*打印*/
case6:
modify_node（L,e1,e2）;break;/*修改*/
case7:
LocateElem_node（L,e）;break;/*查找*/
case0:
free（L）;exit（0）;break;
default:
system（"cls"）;gotostart;
}
printf（"\n是否继续进行（yorn）:
"）;
fflush（stdin）;//清空在此前输入缓冲区
a=getchar（）;
if（a=='y'||a=='Y'）
{
flag=1;
system（"cls"）;/*清屏*/
Menu（）;/*调用菜单函数*/
printf（"请再次选择你需要操作的步骤（0--7）:
"）;
fflush（stdin）;//清空在此前输入缓冲区
scanf（"%d",&n）;
}
else
{
free（L）;//释放链表
exit（0）;
}
}
}
实验结果：
1.建表：
注：
若以空格键隔开数据，多输入无影响，计算机读取完指定数目数据后，自动结束读取。
2.统计：
3-1.插入位置合法：
3-2.插入位置不合法：
4-1.删除位置合法：
4-1.删除位置不合法：
5.打印：
6-1.找到修改元素，并确定修改：
6-2.找到修改元素，不修改：
6-3.没找到修改元素：
7-1.查找成功：
7-2.查找-没有相应数据：
问题讨论：
1.删除操作执行出错：
问题分析：
找到位置，可能删除元素时链表指针指向出错。
问题解决：
将上图中p=p->next->next改为p->next=p->next->next
2.链表长度统计与调用中，注意各函数与统计函数的关系。
例如：
插入函数、删除函数等。
问题讨论与结论：
（1）插入、删除操作时同时增减已统计的链表长度
（2）每次需用到链表长度时，重新调用统计函数统计链表长度
注：
文件名为：
学号+（次数）
升级会员 