单链表的基本操作——C++实现

#include<iostream>
#include<malloc.h>
using namespace std;

typedef int DataType;

/*定义链表数据结构*/
typedef struct node{
DataType data;
struct node * next;
}LNode,* LinkList;

int main(){
/*函数声明*/
LinkList Tail_Create_LinkList();/*尾插法-创建链表*/
int length(LinkList H);/*求单链表长度*/
LinkList Locate_LinkList_Pos(LinkList H,int i);/*查找单链表中的第i个节点*/
LinkList Locate_LinkList_Value(LinkList H,DataType x);/*查找单链表中数值为x的节点*/
void Insert_LinkList(LinkList H,int i,DataType x);/*在链表第i个元素前插入值x*/
void Del_LinkList(LinkList H,int i);/*删除单链表中第i个元素*/
void Show(LinkList H);/*输出链表*/
void Destory_LinkList(LinkList * H);/*销毁单链表*/


LinkList H=Tail_Create_LinkList();//创建任意长度的链表
cout<<"输出单链表：";
Show(H);

cout<<"\n\n单链表的长度为："<<length(H);

/*查找单链表中的第i个节点*/
int i;
cout<<"\n\n查找单链表中第i个元素,i=";
cin>>i;
LinkList p=Locate_LinkList_Pos(H,i);
cout<<"第"<<i<<"个元素的值为："<<p->data;

/*在链表第j个元素前插入值x*/
int j,x;
cout<<"\n\n在单链表中第j个元素前插入数值x,j和x分别为：";
cin>>j>>x;
Insert_LinkList(H,j,x);
cout<<"插入后的单链表为：";
Show(H);

/*删除单链表中第k个元素*/
int k;
cout<<"\n\n在单链表中删除第k个元素,k=";
cin>>k;
Del_LinkList(H,k);
cout<<"删除后的单链表为：";
Show(H);

/*销毁单链表*/
Destory_LinkList(&H);

return 0;
}

/*尾插法-创建链表*/
LinkList Tail_Create_LinkList(){
/*建一个空表*/
LinkList H;
H=(LinkList)malloc(sizeof(LNode));
if(!H){
cout<<"申请空间失败！";
return 0;
}
H->next=NULL;

cout<<"输入单链表元素(负数结束)：";
LinkList p,r;
p=r=(LinkList)malloc(sizeof(LNode));//利用malloc ( )函数向系统申请分配一个节点
cin>>p->data;//输入节点的值
p->next=NULL;//将新节点的指针置为空

while(p->data>0){//输入节点的数值大于0

if(!H->next)
H->next=p;//空表，接入表头
else
r->next=p;
r=p;

p=(LinkList)malloc(sizeof(LNode));//下一个新节点
cin>>p->data;
p->next=NULL;
}

return H;//返回链表的头指针
}

/*求单链表长度*/
int length(LinkList H){
LinkList p=H;
int count=-1;//H带头结点，从-1开始
while(p){
p=p->next;
count++;
}
return count;
}

/*查找单链表中的第i个节点*/
LinkList Locate_LinkList_Pos(LinkList H,int i){
LinkList p=H;
int j=0;
while(p && j<i){//查找第i个节点
p=p->next;
j++;
}
if(j!=i || !p){
cout<<"参数i错或单链表不存在！";
return 0;
}

return p;
}

/*查找单链表中数值为x的节点*/
LinkList Locate_LinkList_Value(LinkList H,DataType x){
LinkList p=H->next;
while(p && p->data!=x){
p=p->next;
}
return p;
}

/*在链表第i个元素前插入值x*/
void Insert_LinkList(LinkList H,int i,DataType x){
LinkList p,q;
p=Locate_LinkList_Pos(H,i-1);//寻找第i-1个节点
if(!p){
cout<<"插入位置有误！";
return;
}

q=(LinkList)malloc(sizeof(LNode));
if(!q){
cout<<"申请空间失败！";
return;
}
q->data=x;

q->next=p->next;//新节点插在第i-1个节点的后面
p->next=q;
}

/*删除单链表中第i个元素*/
void Del_LinkList(LinkList H,int i){
LinkList p,q;
if(H==NULL || H->next==NULL){
cout<<"单链表不存在或空表不能删除！";
return;
}
p=Locate_LinkList_Pos(H,i-1);//寻找第i-1个节点
if(p==NULL || p->next==NULL){
cout<<"删除位置有误！";
return;
}
q=p->next;//q指向第i个节点
p->next=q->next;//从链表中删除
free(q);//释放q
}

/*输出链表*/
void Show(LinkList H){
LinkList p=H->next;//取得链表第一个元素的指针
while(p){//只要是非空表
cout<<p->data<<" ";//输出链表节点的值
p=p->next;//跟踪链表增长
}
}

/*销毁单链表*/
void Destory_LinkList(LinkList * H){
/*
销毁后单链表的头指针变为空指针，
所以要将头指针的地址作为形参
*/
LinkList p,q;
p=* H;
while(p){//释放单链表的所有节点
q=p;
p=p->next;
free(q);
}
* H=NULL;
}