数据结构链表C语言实现.doc

数学与信息技术学院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<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
typedef int ElemType;
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode, *LinkList;

void print_node(LinkList L);

void color(const unsigned short color1)//颜色函数
{
if(color1>=0&&color1<=15)
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color1);
else
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}

LinkList create_linklist(LinkList L)//建立链表L，返回表头指针；
{
int i,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<n;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);
return L;
}

void print_node(LinkList L)//打印
{
Lnode *p;
p=L->next;
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
}

int count_node(LinkList L)//统计
{
int count=0;
Lnode *p;
p=L->next;
while(p)
{
p=p->next;
count++;
}
color(13);
printf("\n统计得总共记录为：%d条\n",count);
color(10);
return count;
}

void insert_node(Lnode *L,int i,ElemType x,int count)//插入；
{
Lnode *p,*q;
int k,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);
}

void delete_node(Lnode *L,int i,int count)
{
Lnode *p,*q;
p=L;
count=count_node(L);
int k;
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);
}

void LocateElem_node(Lnode *L,ElemType x)//查找操作
{
Lnode *p;
p=L->next;
int j=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);
}

void modify_node(Lnode *L,ElemType e1,ElemType e2) //修改操作
{
Lnode *p;
p=L->next;
int j=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);
}

void Menu()
{
printf(" 线性表的链式存储结构 \n\n");
printf(" ************************************菜单**************************************\n");
printf(" * 1.建表 2.统计 *\n");
printf(" * 3.插入 4.删除 *\n");
printf(" * 5.打印 6.修改 *\n");
printf(" * 7.查找 0.退出 *\n");
printf(" ******************************************************************************\n");
}

void main()
{
int e1=0,e2=0,c=0,e=0,i=0,n,flag; /*c=count*/
char a;
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)
{
case 1:create_linklist(L);break; /*建表*/
case 2:count_node(L);break; /*统计*/
case 3:insert_node(L,i,e,c);break; /*插入*/
case 4:delete_node(L,i,c);break; /*删除*/
case 5:printf("\n链表当前数据：");print_node(L);break; /*打印*/
case 6:modify_node(L,e1,e2);break; /*修改*/
case 7:LocateElem_node(L,e);break; /*查找*/
case 0:free(L);exit(0);break;
default:system("cls");goto start;
}
printf("\n是否继续进行(y or n): ");
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） 每次需用到链表长度时，重新调用统计函数统计链表长度
注：文件名为：学号+（次数）