数据结构—单链表的各种基本操作
/*
1.定义单链表中的结点类型
2.利用头插法建立带结点头的单链表
3.利用尾插法建立单链表
4.打印链表
5.按序查找结点的值
6.按值查找表节点
7.插入节点
8.删除结点
*/
#include<iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h> //malloc的头文件
/*
1.定义单链表中的结点类型
*/
typedef struct Lnode{ //自定义的结构体型
ElemType data; //结点的数据域
struct Lnode*next; //结点的指针域
}Lnode,*LinkList; //Lnode表示节点,LinkList表示指针。
2.利用头插法建立带结点头的单链表
*/
LinkList CreateList1(LinkList &L,int n){ //建立一个长n的链表L <这里L前一定要加取址符号,只要需要修改链表就必须取址>
LinkList s;
ElemType x;
L=(LinkList)malloc(sizeof(Lnode)); // 动态申请一个节点(头结点);
L->next=NULL; //初始化为空链表
printf("利用头插法开始建立链表:");
for(int i=1;i<=n;i++){
scanf("%d",&x); //输入节点的值
s=(LinkList)malloc(sizeof(Lnode)); //新建一个节点
s->data=x;
s->next=L->next;
L->next=s;
//printf("%d",L->next->data);
}
return L;
}
3.利用尾插法建立单链表
*/
LinkList CreateList2(LinkList &L, int n){
LinkList s,p;
int y;
L=(LinkList)malloc(sizeof(Lnode));
L->next=NULL;
p=L; //p为尾指针
printf("利用尾插法开始建立链表:");
for(int j=1;j<=n;j++){
scanf("%d",&y);
s=(LinkList)malloc(sizeof(Lnode));
s->data=y;
p->next=s;
p=s;
}
p->next=NULL; //尾指针指空
return L;
}
/*
4.打印链表
*/
void Printf_Link(LinkList L){ //<这里可以不加取值符号,因为是从已经建好的链表中取值,不需要改变链表>
LinkList p;
p=L->next;
while(p){
printf("%d",p->data);
p=p->next;
}
}
/*
5.按序查找结点的值
*/
Lnode * GetElem(LinkList L, int i){ //<这里L可以不加取值符号,因为是从已经建好的链表中取值,不需要改变链表>
// GetElem前需要加*好,因为后面有return p,即需要返回指针。如果不需要的话也可以不加*
int count=1; //设置计数值
LinkList p;
p=L;
if(L->next==NULL){
printf("这是一个空表,请先建立链表!");
}
if(i<1){
printf("您输入的结点无效,请重新输入!");
}
else{
while(p&&count<=i){
p=p->next;
count++;
}
return p;
}
}
/*
6.按值查找表节点
*/
Lnode *LocateElem(LinkList L, int e){
LinkList s;
s=L->next;
int count=1;
while(s&&s->data!=e){
s=s->next;
count++;
}
cout<<"您要找的数在第"<<count<<"个节点"<<endl;
return s;
}
/*
7.插入节点
*/
Lnode* Insert_LinkList(LinkList &L, int i){ //将新的节点插入到链表L的第i个位置
LinkList p;
p=GetElem(L,i-1); // 找到第i个节点的直接前驱
LinkList s=(LinkList)malloc(sizeof(Lnode)); //新建一个节点
int x;
scanf("%d",&x);
s->data=x;
s->next=p->next;
p->next=s;
return L;
}
/*
8、删除结点
*/
Lnode*Delete_LinkList(LinkList &L, int i){ //删除链表L的第i个结点
LinkList p,q;
p=GetElem(L,i-1); //找到第i个节点的直接前驱
q=p->next; //将q指向第i个结点
p->next=q->next; //令第i-1的节点直接与第i+1节点相连
free(q); //释放第i个结点
return L;
}
int main(){
LinkList L1,L2;
int m,j,e;
scanf("%d",&m);
//建立链表
CreateList1(L1,m);
CreateList2(L2,m);
//打印链表
cout<<"打印链表1:";
Printf_Link(L1);
printf("\n");
cout<<"打印链表2:";
Printf_Link(L2);
printf("\n");
// 按序查找结点的值
cout<<"查找链表某个节点的数:";
scanf("%d",&j);
LinkList p1,p2;
p1=GetElem(L1,j);
p2=GetElem(L2,j);
cout<<"输出1链表的第"<<j<<"个数:";
printf("%d\n",p1->data);
cout<<"输出2链表的第"<<j<<"个数:";
printf("%d\n",p2->data);
//按值查找表节点
cout<<"查找链表中某个数的位置:";
scanf("%d",&e) ;
LocateElem(L1, e);
LocateElem(L2, e);
//插入节点,并打印出新的链表
cout<<"在链表1的第2个结点插入节点值:";
Insert_LinkList(L1, 2);
cout<<"在链表2的第2个结点插入节点值:";
Insert_LinkList(L2, 2);
cout<<"打印新链表1:";
Printf_Link(L1);
printf("\n");
cout<<"打印新链表2:";
Printf_Link(L2);
printf("\n");
// 删除结点,并打印出新的链表
cout<<"删除链表1的第3个结点"<<endl;
Delete_LinkList(L1, 3);
cout<<"打印新链表1:";
Printf_Link(L1);
printf("\n");
cout<<"删除链表2的第3个结点"<<endl;
Delete_LinkList(L2, 3);
cout<<"打印新链表2:";
Printf_Link(L2);
printf("\n");
return 0;}
最后结果: