/*郭睿玥第二次算法实验作业*/
/*实验原理
链表是一种动态存储结构。线性表的链式存储结构的特点是用一组任意的存储单元（可以是
连续的，也可以是不连续的）存放线性表的数据元素。线性表的一个结点由两个域组成：存
放自身的数据和存放直接后继结点存储位置的指针域 。用指针相连接的结点序列称为链表，
若逻表中每个结点只包含一个指针域，则此链表为线性链表或单链表。通常链表中的每个结
点可以有若干个数据域 和多个链域 。我们常用C语言中的“指针”类型来描述线性链表。*/
/*实验环境
CodeBlocks*/
/*实验目的
1．掌握单链表的概念及其各种运算的原理。
2．通过对单链表的建立及几种基本运算等的算法实现，掌握线性表的链式存储结构、各种
运算和指针的表示及应用等内容。初步掌握运用链式结构的编程的能力。
3．用C语言实现并上机调试通过，认真填写实验报告
*/
/*实验内容
（1）定义函数：建立一个具有n个结点的单向链表L，要求返回表头指针；
（2）定义函数：统计结点个数，要求以表头指针作为调用函数，返回结点个数；
（3）定义函数：在链表L的第I个结点前插入一个结点，要求以表头指针作为调用函数，无返回值；
（4）定义函数：删除链表L的第I个元素，要求以表头指针作为调用函数，无返回值；
（5）定义函数：输出单链表;
（6）定义函数：链表中查找某结点;
（7）定义函数：链表中更改某结点的数据域;
（8）主函数中对上述函数进行调用。
（9）根据自己的理解添加更多的内容。
*/
/*算法实现如下*/
#include <stdio.h>
#include <stdlib.h>
typedef int Status;// 定义函数返回值类型
typedef int ElemType;// 定义每条数据的结构体类型
typedef struct
{
int data1;
}DATA;//定义数据域内数据
typedef struct Node//定义结点
{
DATA data;//数据域
struct LNODE*next;//指针域
}LNode,*Linklist;
LNode *head;//建立头结点
Linklist buildlist(){// 构造空链表
LNode*p,*r;//建立结点p，r
int data,i=1;
head=(LNode*)malloc(sizeof(LNode));// 申请空间
r=head;// 建立头结点
r->next=NULL;
int length;// 需要建立的链表的长度（包括头结点)
printf("请输入链表长度");//用户输入需要建立的链表的长度
scanf("%d", &length);
while (i<length) {/*按照结点顺序输入第i+1个结点数据域*/
printf("请输入第%d个节点的值",i+1);
scanf("%d",&data);
p=(LNode*)malloc(sizeof(LNode));// 申请空间
p->data.data1 =data;// 使p的数据域为输入的数据
r->next=p;// 用指针链接r与p
p->next = NULL;// 由于p为最后一个结点因此p的指针域为空
r=p;// r后移
i++;
}
return head;//返回头节点
}
int getlength(Linklist L){ /*显示链表结点个数头节点包含其中*/
Linklist p;//建立结点p
p=L->next;//p为首元结点
int i=1;
while(p){/*统计结点个数，p每向后移动一个结点i加1已统计结点数*/
i++;
p=p->next;
}
return i;//返回结点个数
}
void proinsert(LNode*L){/*插入一个结点函数*/
printf("* 郭睿玥 算法与数据结构第二次作业 \n");
LNode *p,*prt,*q;
p=L;//使结点p为都头结点
prt=(LNode*)malloc(sizeof(LNode));// 申请空间
int location,i=2,need,j=getlength(L)+1;//location是要插入的结点位置，need是要插入的数据域
printf("请输入需要插入的位置：");
scanf("%d",&location);
while(location<=1||location>j){//不允许在头结点之前和最后一个结点后但可以在最后一个结点之后插入一个结点插入结点
printf("ERROR\n");
printf("请重新输入\n");
scanf("%d",&location);
}
while(p!=NULL){/*寻找需要插入的结点的位置*/
if(location==j){/*如果插入的位置是第一个空结点结点*/
printf("所要需要插入的值");
scanf("%d",&need);
prt->data.data1=need;/*构建需要插入的结点*/
prt->next=NULL;/*构建需要插入的结点*/
while(i!=j){/*使p指向最后一个结点*/
i++;
p=p->next;
}
p->next=prt;/*勾链*/
p=prt;
return 0;
}
if(i==location){/*如果所插入的位置是首元结点则直接构建结点并插入*/
printf("所要需要插入的值");
scanf("%d",&need);
prt->data.data1=need;/*构建需要插入的结点*/
q=p->next;/*勾链*/
p->next=prt;
prt->next=q;
return 0;
}
p=p->next;
i++;
}
}
void delete_one_node(LNode*L){/*删除结点函数*/
printf("* 郭睿玥 算法与数据结构第二次作业 \n");
LNode *p,*q,*prt;
p=L;//让p指向头结点
int location,i=1;
printf("请输入需要删除的元素的位置：");
scanf("%d",&location);
while(location<=1||location>getlength(L)){/*限定删除范围*/
printf("ERROR\n");
printf("请重新输入\n");
scanf("%d",&location);
}
while(NULL!=p->next&&i<location-1){/*寻找要删除的位置*/
p=p->next;
i++;
}
prt=p->next;//链接要删除的结点的前驱和后继
q=prt->next;
p->next=q;
free(prt);/*释放要删除的结点空间*/
prt=NULL;
return 0;
}
void outputsqlist(LNode*L){/*输出链表函数*/
int i=1;
LNode *p;
p=L->next;//使结点p指向首元结点
while (p!=NULL){/*通过移动结点p的的次数统计结点个数*/
printf("第%d个节点的值",i+1);
printf("%d\n",p->data.data1);
p=p->next;
i++;
}
}
void saerchnode(LNode*L){/*根据数据域查找结点位置函数*/
int need,j=2,num=0;//need指需要查找的数据域，j表示循环次数或所需要查找的结点的位置，num表示是否查找成功
printf("所要需要查找的值");
scanf("%d",&need);
LNode*p;
p=L->next;//使结点p指向首元结点
while(p!=NULL){/*通过移动p的指向结点来控制循环以找到所需要查找的结点*/
if(p->data.data1==need){/*比较当前结点数据域和需要查找的值*/
printf("查找成功，位于第%d个\n",j);//
num++;//
}
j++;
p=p->next;//
}
if(!num)printf("查找失败");//
return 0;
}
void changenode(LNode*L){/*改变结点数据域函数*/
int location,change,j=getlength(head);//
LNode*p;
p=L;//让p指向头结点
printf("所要改变的值的位置");
scanf("%d",&location);
while(location<=1||location>j){/*限定范围*/
printf("ERROR\n");
printf("请重新输入\n");
scanf("%d",&location);//输入需要查找的位置
}
printf("所要改变的成的值");
scanf("%d",&change);//输入数据域改变后的值
int i=1;
while(p){/*通过移动p来寻找和需要查找的位置一致的结点*/
i++;
p=p->next;//
if(i==location){//
p->data.data1=change;
printf("成功");
return 0;
}
}
return 0;
}
int main(){
int choice;
do {/*显示操作界面*/
printf("********************************************************************\n");
printf("*（1）建立具有n个结点的单向链表L（计入头结点）; \n");
printf("*（2）统计结点个数（计入头结点）; \n");
printf("*（3）在链表第I个结点前插入一个结点; \n");
printf("*（4）删除链表L的第I个元素; \n");
printf("*（5）输出单链表; \n");
printf("*（6）查找某结点; \n");
printf("*（7）更改某结点的数据域; \n");
printf("* (0）退出。 \n");
printf("* 郭睿玥 算法与数据结构第二次作业 \n");
printf("********************************************************************\n");
printf("\n");
printf("请选择你要操作的选项:");
scanf("%d", &choice);//输入需要进行的选项
printf("\n");
switch (choice) {
case 1:{/*建立具有n个结点的单向链表L（计入头结点）*/
buildlist();
break;
}
case 2:{/*统计结点个数（计入头结点）*/
printf("%d\n",getlength(head));
break;
}
case 3:{/*在链表第I个结点前插入一个结点;*/
proinsert(head);
break;
}
case 4:{/*删除结点*/
delete_one_node(head);
break;
}
case 5:{/*输出单链表; */
outputsqlist(head);
break;
}
case 6:{/*查找某结点*/
saerchnode(head);
break;
}
case 7:{/*更改某结点的数据域*/
changenode(head);
break;
}
case 0:{/*退出*/
printf("\n退出系统成功！请按任意键结束！\n");
exit(0);
}
break;
}
} while (choice);//只要选择不为需要进行的功能不为0则该程序可以一直进行下去
return 0;
}
/*
以下是实验结果
操作界面如下
（1）建立具有n个结点的单向链表L（计入头结点）
（2）统计结点个数（计入头结点）;
（3）在链表第I个结点前插入一个结点;
（4）删除链表L的第I个元素;
（5）输出单链表;
（6）查找某结点;
（7）更改某结点的数据域;
(0）退出。
郭睿玥 算法与数据结构第二次作业
（以下内容中操作界面的显示已经省略）
输入
请选择你要操作的选项:1
请输入链表长度：5
请输入第2个结点的值3
请输入第3个结点的值4
请输入第4个结点的值5
请输入第5个结点的值6
请选择你要操作的选项:2
显示为 5
请选择你要操作的选项:3
请输入你要插入的位置 4
插入的值 8
请选择你要操作的选项:4
你要删除的位置；3
请选择你要操作的选项:5
第2个结点的值3
第3个结点的值8
第4个结点的值5
第5个结点的值6
请选择你要操作的选项:6
所需要查找的值 8
查找成功，位于第3个
请选择你要操作的选项:7
所要改变值的位置3
所要改变成值11
请选择你要操作的选项:5
请输入第2个结点的值3
请输入第3个结点的值11
请输入第4个结点的值5
请输入第5个结点的值6
请选择你要操作的选项:0
退出系统成功！
*/