数据结构——单链表基本操作

布满荆棘的人生 2022-06-17 10:22 151阅读 0赞

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <malloc.h>  
// 定义链表中的节点  
typedef struct LinkedList  
\{  
int member; // 节点中的成员  
struct LinkedList\* Next; // 指向下一个节点的指针  
\} LinkListed,\*Linked;  
// 函数声明  
Linked CreateList(int); // 创建链表函数  
void print(Linked); // 打印数据  
void Insertnum(Linked,int,int); //第一个参数是头节点，第二个表示要插入的位置，第三个表示数据值  
void qiancha(Linked,int); //第一个参数是头节点，第二个表示数据值  
void houcha(Linked,int); // 第一个参数是头节点，第二个表示数据值  
void turn(Linked);  
int GetLength(Linked );  
void JudgeNULL(Linked Head);  
void ClearList(Linked);  
void Destory(Linked);  
int Delete(Linked,int);  
int main()  
\{  
Linked Head = NULL; // 定义初始化头节点，等价于 struct LinkedList \*Linked== NULL  
int data,choose,num,value,choose1,length,choose2; //data表示要输入的数据值，choose表示用户第一个选择，choose1表示用户第二个选择  
//num表示插入位置，value表示创建链表时每个数据成员的值，length表示链表长度  
printf("请输入数据个数：");  
scanf("%d",&length);  
Head=CreateList(length); // 创建一个非循环单链表，并将该链表的头结点的地址付给pHead  
printf("你输入的数据是：");  
print(Head); // 调用打印函数  
while(1)  
\{  
printf("是否还要进行其他操作：\\n");  
printf("是请输入1，不是输入2\\n");  
printf("请输入：");  
scanf("%d",&choose);  
if(choose==1)  
\{  
printf("进行普通插入请输入1\\n前插请输入2\\n后插请输入3\\n倒序链表请按4\\n给链表取长请按5\\n为链表判空按6\\n打印元素按7\\n清空链表按8\\n退出按9\\n");  
scanf("%d",&choose1);  
switch (choose1)  
\{  
case (1):\{  
printf("请输入要在第几个节点前插入数据：\\n");  
scanf("%d",&num);  
length=GetLength(Head);  
if(num<0||num>length)  
\{  
printf("您输入的位置无效！\\n");  
\}  
else  
\{  
printf("请输入要插入的数据：\\n");  
scanf("%d",&data);  
Insertnum(Head,num,data) ;  
printf("操作完成后的数据是：\\n");  
print(Head);  
\}  
break;  
\}  
case(2):\{  
printf("请输入要插入的数据：\\n");  
scanf("%d",&data);  
qiancha(Head,data);  
printf("操作完成后的数据是：\\n");  
print(Head);  
break;  
\}  
case(3):\{  
printf("请输入要插入的数据：\\n");  
scanf("%d",&data);  
houcha(Head,data);  
printf("完成后的数据是：\\n");  
print(Head);  
break;  
\}  
case(4):\{  
turn(Head);  
print(Head);  
break;  
\}  
case(5):\{  
length=GetLength(Head);  
printf("改链表包含头指针的长度为：%d",length);  
break;  
\}  
case(6):\{  
JudgeNULL(Head);  
break;  
\}  
case(7):\{  
print(Head);  
break;  
\}  
case(8):\{  
ClearList(Head);  
break;  
\}  
case(9):\{  
printf("您确定要退出吗？退出请按1，继续请按2\\n");  
scanf("%d",&choose2);  
if(choose2==1)  
\{  
return 0;  
\}  
break;  
\}  
case(10):\{  
int i;  
printf("请输入您要删除的元素位置：\\n");  
scanf("%d",&i);  
Delete(Head,i);  
break;  
\}  
default:\{  
printf("对不起，您的输入有误\\n！");  
break;  
\}  
\}   
\}  
else  
\{  
return 0;  
\}  
\}  
Destory(Head);  
\}  
// 创建链表函数  
Linked CreateList(int length)  
\{  
int i; // 用于下面循环  
int value; // 用于临时存放用户输入的数据  
Linked Head = (Linked)malloc(sizeof(Linked)); // 分配一个不存放有效数据的头结点  
Linked Tail = Head; // 链表的最后一个节点  
Tail->Next = NULL; // 最后一个节点的指针置为空  
for(i = 0; i < length; i++)  
\{  
printf("第 %d 个数据的数值：",i+1);  
scanf("%d",&value);  
Linked Newnum = (Linked)malloc(sizeof(Linked)); // 为节点分配空间  
Newnum->member =value; //将用户输入的数据赋给节点的成员  
Tail->Next = Newnum; //将最后一个节点的指针指向下一个新的节点  
Newnum->Next =NULL; //将新节点中的指针置为空  
Tail =Newnum;  
\} //将新节点赋给最后的一个节点  
return Head; //返回头节点  
\}  
int Delete(Linked Head,int i)  
\{  
int length,k;  
Linked p=Head;  
length=GetLength(Head);  
if(i<1||i>length)  
return false;  
for(k=0;k<i;k++)  
\{  
p=p->Next;  
\}  
p=p->Next;  
free(p);  
\}  
// 遍历链表函数  
void print(Linked Head)  
\{  
Linked p=Head->Next; //将头节点的指针给予临时节点p  
while(p!=NULL) //节点p不为空，循环  
\{  
printf("%d ",p->member);  
p = p->Next;  
\}  
printf("\\n");  
return ;  
\}  
// 链表节点插入函数  
// 第一个参数是头节点int num,int data)  
void Insertnum(Linked Head,int num,int data)//num表示插入位置，data 表示插入数据  
\{  
int i = 0;  
int before,after;  
before=GetLength(Head);  
Linked \_point =Head;  
Linked Swap; // 用于交换  
if ((num<1)&&(NULL!=\_point)) //判断用户输入的数据是否大于等于1,及\_point是否为空  
\{  
printf("对不起，您的输入有误！");  
\}  
while (i<num-1)  
\{  
\_point=\_point->Next;  
\++i;  
\}  
Linked Newnum = (Linked)malloc(sizeof(Linked));  
Newnum->member = data; // 把输入的数据赋给要插入的节点  
Swap = \_point->Next; // 把下一个节点的地址，给用于交换的pSwap  
// 把要插入的节点的地址，给上个节点的指针域  
Newnum->Next =Swap; // 把插入节点的下一个节点的地址，给插入节点的指针域  
\_point->Next =Newnum;  
after=GetLength(Head);  
if(before!=after-1)  
\{  
printf("对不起，插入失败！\\n");  
\}  
  
\}  
void qiancha(Linked Head,int data)  
\{  
int before,after;  
before=GetLength(Head);  
Linked newnum=(Linked )malloc(sizeof(Linked));  
newnum->member=data;  
newnum->Next=Head->Next;  
Head->Next=newnum;  
after=GetLength(Head);  
if(before!=after-1)  
\{  
printf("对不起，插入失败！\\n");  
\}  
\}  
void houcha(Linked Head,int data)  
\{  
int before,after;  
before=GetLength(Head);  
Linked newnum=(Linked)malloc(sizeof(Linked));  
Linked p=Head;  
newnum->member=data;  
while(p->Next!=NULL)  
\{  
p=p->Next;  
\}  
newnum->Next=NULL;  
p->Next=newnum;  
after=GetLength(Head);  
if(before!=after-1)  
\{  
printf("对不起，插入失败！\\n");  
\}  
  
\}  
int GetLength(Linked Head)  
\{  
int j=0;  
Linked p=Head;  
while (p!=NULL)  
\{  
p=p->Next;  
j++;  
\}  
return j;  
\}  
void turn(Linked Head)  
\{  
int length,i;  
Linked p=Head->Next;  
Head->Next=NULL;  
length=GetLength(p);  
for(i=0;i<length;i++)  
\{  
qiancha(Head,p->member);  
p=p->Next;  
\}  
\}  
void JudgeNULL(Linked Head)  
\{  
if(Head->Next==NULL)  
\{  
printf("该表为空表！\\n");  
\}  
else  
printf("该表非空！\\n");  
\}  
void ClearList(Linked Head)  
\{  
  
while(Head->Next!=NULL)  
\{  
Linked p=Head->Next;  
Head->Next=p->Next;  
free(p);   
\}  
\}  
void Destory(Linked Head)  
\{  
while(Head!=NULL)  
\{  
Linked p=Head;  
Head=Head->Next;  
free(p);  
\}  
\}