线性表的链式存储结构完整版-数据结构版.docx

#include "stdio.h"
//standard input output的缩写即标准输入输出,它封装了标准输入输出
//里面包含有一些通用的工具函数,此程序主要用到了它里面包含的
等一些常用函数
#include
"stdlib.h"
system("cls"),system("cls")和 exit()函数
#include "string.h"
//里面包含有一些常用的字符串函数,此程序主要用到了它里面包含的
strcmp()和 strcpy()函数
typedef struct LNode{
int ID;
//序号为整型
char name[20];
//姓名为字符型数组
char age[10];
struct LNode *next; //struct LNode的直接后继指针
}LNode, *LinkList; //LNode为结构体名,*LinkList为指针型结构体名
//年龄为字符型数组
int AgeJudge(char ch1[10]){
//输入的 ch1必须为大于 0的整数
char ch2[10];
int a;
//定义 ch2字符型数组存放一个整型数据
//用于保存 ch1转换为整型的数据
while(1){
//无限循环使用户可以无限输入直到输入正确
scanf("%s",ch1);
//输入 ch1
a=atoi(ch1);
//将 ch1转换为整型
itoa(a,ch2,10);
//将 ch1转换为整型后的数据再存放到 ch2当中
if(strcmp(ch1,ch2)==0&&a>0){break;}
//当输入的数据为大于 0的整数时跳出死循
else{printf("请输入一个人大于 0的整数: ");} //输入数据有误
return a; //返回输入的大于 0的整数
环
}
}//AgeJudge
void CreateList_L(LinkList &L, int n){
//顺位序输入 n个元素的值,建立带表头节点的单链线性表 L
int i;
//用作循环变量
LinkList p,s,p1;
//p为第一个节点的结构体指针,s为第一个以后节点的结构体指针,p1为
临时结构体指针
L=(LinkList)malloc(sizeof(LNode));
//生成头结点
if(!L){printf("空间申请失败!");}
//生成头结点失败
L->next=NULL;
for(i=0;i<n;i++){
printf("\n");
//先建立一个带头结点的空的单链表
if(i==0){
//当输入第一组数据时
p=(LinkList)malloc(sizeof(LNode)); //生成新结点
if(!p){printf("空间申请失败!");} //生成新结点失败
printf("请输入第%d个人的姓名: ",i+1);

scanf("%s",p->name);
//输入姓名
printf("请输入第%d个人的年龄: ",i+1);
AgeJudge(p->age);
L->next=p;p->next=NULL;
//链到表头后面
}
else{
//当输入非第一组数据时
s=(LinkList)malloc(sizeof(LNode)); //生成新结点
if(!s){printf("空间申请失败!");}
printf("请输入第%d个人的姓名: ",i+1);
while(1){
//生成新结点失败
int flag=0;
scanf("%s",s->name);
p1=L->next;
//输入姓名
while(p1){
if(strcmp(s->name,p1->name)==0)
//线性表中已经存在目前输入的姓
名
{flag=1;break;}
p1=p1->next;}
if(flag==1){
printf("此姓名已存在,请重新输入: "); //名字已存在,返回重新输入
}
if(flag==0){break;}
//名字不存在,跳出死循环
//输入大于 0的整数的年龄
}
printf("请输入第%d个人的年龄: ",i+1);
AgeJudge(s->age);
p->next=s;s->next=NULL;
//将输入的数据链到目前已存在的数据后面,并使下一指针为空,为下一次输入
做好准备
p=p->next;
//指针后移
}
}
printf("\n信息录入完成!\n\n");
//链表创建完成
}//CreateList_L
void PrintElem_L(LinkList L){
//输出单链表中的数据
LinkList p;
int i=0;
//计数器,计算链表中结构体数组数据的个数
if(L->next==NULL){printf("\tIt's Empty!\n\n");} //空链表
else{
//不为空链表
p=L->next;
//从头结点的下一个节点开始
printf("\t%-7s%-10s%-4s\n","序号","姓名","年龄");
while(p){
//当指针不为空
i++;p->ID=i;
//将计数器的值赋值给结构体中的序号

printf("\t %-6d%-10s %-3s\n",p->ID,p->name,p->age); //输出数值
p=p->next; //指针后移
}
}
printf("\n");
}//PrintElem_L
void GetElem_L(LinkList L,int i){
//L为头结点的单链线性表的头指针
//当第 i个元素存在时,取出它的值
LinkList p;
p=L->next;int j=1;
while(p&&j<i){
//初始化,p指向第一个节点,j为计数器
//顺指针向后查找,直到 p指向第 i个元素
或 p为空
p=p->next;++j;
}
if(!p||j>i){printf("\n没有找到你输入的序号信息!\n\n");}
//第 i个元素不存在
else{
printf("\n\t你要查找的信息如下:\n\n");
printf("\t%-7s%-10s%-4s\n","序号","姓名","年龄");
printf("\t %-6d%-10s %-3s\n\n",i,p->name,p->age);
}
//输出找到的值
}//GetElem_L
void ListInsert_L(LinkList &L,int i){
//在带头结点的单链线性表 L中第 i个位置之前插入元素 e
LinkList s,p,p1;
p=L;
//从头节点开始
//计数器
int j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1){
//寻找第 i-1个结点
//i小于 1或者大于表长加 1
printf("\n插入位置错误!\n\n");}
else{
//已经找到对应的结点
//生成新结点
s=(LinkList)malloc(sizeof(LNode));
if(!s){printf("空间申请失败!");}
printf("请输入新的姓名: ");
while(1){
//生成新结点失败
int flag=0;
scanf("%s",s->name);
p1=L->next;
//输入姓名
while(p1){
if(strcmp(s->name,p1->name)==0)
//输入的姓名链表中已经存在
{flag=1;break;}
p1=p1->next;}

if(flag==1){
printf("此姓名已存在,请重新输入: ");//姓名已存在重新输入
}
if(flag==0){break;}
//输入姓名不存在跳出死循环
}
printf("请输入年龄: ");
AgeJudge(s->age);
//输入一个大于 0的整型的年龄
s->next=p->next;
//插入 L中
p->next=s;
printf("\n插入信息成功!");
printf("\n\n
插入数据之后的数据如下: \n\n");
PrintElem_L(L); //输出插入后线性表中的数据
}
}//ListInsert_L
void ListDelete_L(LinkList &L, int i){
//在带头结点的单链线性表 L中,删除第 i个元素,并有 e返回其值
LinkList q,p;
p=L;
//从头结点开始
//计数器
//用于存放要删除的数值
//寻找第 i个结点,并令 p指向其前趋
int j=0;
char name[20],age[10];
while(p->next&&j<i-1){
p=p->next;++j;
}
if(!(p->next)||j>i-1){
//删除位置不合理
printf("\n\n删除位置错误!\n\n");}
else{
q=p->next;p->next=q->next;
//删除并释放结点
strcpy(name,q->name);strcpy(age,q->age);
free(q);
//保存要删除的数据
printf("\n你所删除的数据信息如下: \n\n");
printf("\t%-7s%-10s%-4s\n","序号","姓名","年龄");
printf("\t %-6d%-10s %-3s\n\n",i,name,age);//输出要删除的数据
printf("\n\n
删除数据之后的数据如下: \n\n");
PrintElem_L(L);//输出删除后线性表中的数据
}
}//ListDelete_L
int menu(){
int choose;
char ch[10];
while(1){
//界面菜单函数
system("cls");

printf("\n\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");
printf("\t\t\t(1)建立新的线性表\n\n");
printf("\t\t\t(2)查找第 i个位置数据信息\n\n");
printf("\t\t\t(3)第 i个位置之前插入数据\n\n");
printf("\t\t\t(4)删除第 i个元素\n\n");
printf("\t\t\t(5)输出当前线性表中的数据\n\n");
printf("\t\t\t(0)退出程序\n");
printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");
printf("\t\t请输入你的选择: ");
scanf("%s",ch);
//输入选择
if(strcmp(ch,"0")==0||strcmp(ch,"1")==0||strcmp(ch,"2")==0
||strcmp(ch,"3")==0||strcmp(ch,"4")==0||strcmp(ch,"5")==0){
//当输入的是 0,1,2,3,4或 5时
choose=atoi(ch);//将字符串型 0,1,2,3,4,5转换为整型
break;}
//跳出菜单选择
else{printf("\n\t选择错误,请重新选择!\n\n");//菜单选择错误,重新选择
system("pause");
//程序暂停,使用户能看见上面的提示语
}
}
return choose;
//返回用户的菜单选择
}
void main(){
char ch[10];
LinkList L=NULL;//定义 L为结构体的头指针,初始值为空
system("color a0");
//改变运行窗口背景颜色和字体颜色,第一个为背景颜色,第二个为文字颜色背景
设置为绿色,字体颜色设置为黑色
while(1){
switch(menu()){
case 1: system("cls");
//运行到此处清屏,屏幕只显示此处以下运行界面,此
处以上运行界面清空
printf("\n\n请输入要输入数据的个数: ");
CreateList_L(L,AgeJudge(ch));
//输入的个数必须是一个大于 0的整数,创
建线性表
printf("\n
你输入的数据如下: \n\n");
PrintElem_L(L);
system("pause");break;
//输出创建的线性表信息
//让用户看到输出结果后跳出 switch选择
case 2: system("cls");
if(L==NULL||L->next==NULL){printf("\n\nIt's Empty!\n\n");}//目前不存在
线性表
else{
//目前存在线性表
请输入查找数据的位置序号: ");
//输入的序号必须是大于 0的整数,执行
printf("\n\n\n
GetElem_L(L,AgeJudge(ch));}

查找功能
system("pause");break;
//让用户看到查找结果后跳出 switch选择
case 3: system("cls");
if(L==NULL){printf("\n\nIt's Empty!\n\n");}//目前不存在线性表
else{
//目前存在线性表
printf("\n\n
插入数据之前的数据如下: \n\n");
PrintElem_L(L);
//输出插入数据之前线性表中的数据
请问你要在第几个位置序号前插入数据: ");
ListInsert_L(L,AgeJudge(ch)); } //输入的序号必须是大于 0的整数,执行插
printf("\n\n
入功能
线性表
system("pause");break;
//让用户看到插入结果后跳出 switch选择
case 4: system("cls");
if(L==NULL||L->next==NULL){printf("\n\nIt's Empty!\n\n");}//目前不存在
else{
//目前存在线性表
printf("\n\n
删除数据之前的数据如下: \n\n");
PrintElem_L(L);
//输出删除数据之前线性表中的数据
请输入要删除数据的位置序号: ");
ListDelete_L(L,AgeJudge(ch));}//输入的序号必须是大于 0的整数,执行删
printf("
除功能
system("pause");break;
//让用户看到删除结果后跳出 switch选择
case 5: system("cls");
if(L==NULL){printf("\n\nIt's Empty!\n\n");}//目前不存在线性表
else{
//目前存在线性表
printf("
线性表中目前数据如下:\n\n ");
PrintElem_L(L);}
system("pause");break;
//让用户看到删除结果后跳出 switch选择
case 0: printf("\n\t谢谢使用本程序!\n\n");
exit(0);
//终止程序
default:printf("程序执行错误!\n");
//只有当 menu()返回值为 0,1,2,3或 4时才能执行此 switch语句,若能执行此
default语句,说明程序执行错误
}
}
}