C++单链表头插法和尾插法实现
#include <iostream>
using namespace std;
// 定义一些常用的符号常量
#define MAXSIZE 100 // 顺序表最大容量
#define ERROR 0 // 错误状态码
#define TRUE 1 // 真状态码
#define FALSE 0 // 假状态码
#define OK 1 // 正确状态码
#define INFEASIBLE -1 // 不可行状态码
#define OVERFLOW -2 // 溢出错误状态码
typedef int ElemType; // 定义数据类型ElemType为int
typedef int Status; // 定义状态类型Status为int
// 定义链表结点结构体
typedef struct LNode {
ElemType data; // 数据域
LNode* next; // 指针域
}LNode,*LinkList;
// 初始化链表
Status InitList(LinkList &L) {
L=new LNode; // 创建头结点
L->next=NULL; // 头结点的next指针置空
return OK; // 返回正确状态码
}
// 判断链表是否为空
int isEmpty(LinkList &L) {
if(L->next) { // 头结点的next指针不为空则链表非空
return 0; // 返回0表示非空
}else {
return 1; // 返回1表示空
}
}
// 销毁单链表
Status DestoryList(LinkList &L) {
while(L) {
LinkList p=L;
delete p;
L=L->next; // 向后移动指针
}
return OK;
}
// 清空单链表
Status ClearList(LinkList &L) {
while(L->next) {
LinkList p=L->next,q;
q=p->next;
delete p;
p=q; // 向后移动指针
}
return OK;
}
// 头插法建立链表
void H_Insert(LinkList &L,int n) {
cout<<"please input "<<n<<" num:"<<endl;
L->data=0; // 初始化链表长度为0
for(int i=0;i<n;i++) {
LinkList p=new LNode;
int k;
cin>>k;
p->data=k;
p->next=L->next; // 将新节点的next指针指向头结点的next指针所指向的节点
L->next=p; // 将头结点的next指针指向新节点
L->data++; // 链表长度加1
}
}
// 头插法建立链表（不指定长度）
void H_Insert(LinkList &L) {
L->data=0; // 初始化链表长度为0
int x;
cout<<"请连续输入要插入链表的值,输入一个按下回车,输入9999结束输入:"<<endl;
cin>>x;
while(x!=9999){
LinkList p=new LNode;
p->data=x;
p->next=L->next; // 将新节点的next指针指向头结点的next指针所指向的节点
L->next=p; // 将头结点的next指针指向新节点
L->data++; // 链表长度加1
cin>>x;
}
}
// 尾插法建立链表
void L_Insert(LinkList &L,int n) {
L->data=n; // 设置链表长度为n
cout<<"please input "<<n<<" num:"<<endl;
LinkList r=L;
for(int i=0;i<n;i++) {
LinkList p=new LNode;
int data;
cin>>data;
p->data=data;
r->next=p; // 将尾节点的next指针指向新节点
r=p; // 将尾节点指针指向新节点
}
r->next=NULL;
}
// 尾插法建立链表（不指定长度）
void L_Insert(LinkList &L) {
L->data=0; // 初始化链表长度为0
LinkList r=L;
cout<<"请连续输入要插入链表的值,输入一个按下回车,输入9999结束输入:"<<endl;
int x;
cin>>x;
while(x!=9999){
LinkList p=new LNode;
p->data=x;
r->next=p; // 将尾节点的next指针指向新节点
r=p; // 将尾节点指针指向新节点
L->data++; // 链表长度加1
cin>>x;
}
r->next=NULL;
}
// 打印链表
void PrintList(LinkList L) {
cout<<"the length of the list is : "<<L->data<<endl;
LinkList p=L->next;
int i=1;
while(p!=NULL) {
cout<<"the "<<i<<"TH element is "<<p->data<<endl;
p=p->next; // 向后移动指针
i++;
}
}
// 获取链表长度
int GetLength(LinkList L) {
int i=0;
LinkList p=L->next;
while(p) {
i++;
p=p->next; // 向后移动指针
}
return i;
}
// 在指定位置插入元素
Status List_Insert(LinkList &L,int x,ElemType e) {
if(x<=0||x>L->data) return ERROR;
LinkList p=new LNode;
LinkList q=L;
p->data=e;
for(int i=1;i<x;i++) {
q=q->next; // 向后移动指针
}
p->next=q->next; // 新节点的next指针指向q的下一个节点
q->next=p; // 将q的next指针指向新节点
L->data++; // 链表长度加1
return OK;
}
// 按位查找元素值
ElemType FindByPos(LinkList &L,int x) {
LinkList p=L;
if(x<=0||x>L->data) return ERROR;
for(int i=0;i<x;i++) {
p=p->next; // 向后移动指针
}
return p->data;
}
// 按值查找元素位置
int FindByVal(LinkList &L,int val) {
LinkList p=L;
for(int i=0;i<L->data;i++) {
p=p->next;
if(p->data==val) {
return i+1
}
}
cout<<"此链表中没有此值"<<endl;
return ERROR;
}
// 删除指定位置的元素
ElemType ListDelte(LinkList &L,int x) {
LinkList p=L;
for(int i=1;i<x;i++) {
p=p->next; // 移动指针到要删除节点的前一个节点
}
LinkList q=p->next;
p->next=q->next; // 将前一个节点的next指针指向被删除节点的下一个节点
ElemType e=q->data; // 保存被删除节点的值
L->data--; // 链表长度减1
delete q; // 释放被删除节点的内存
return e; // 返回被删除节点的值
}
// 主函数
int main() {
LinkList L;
InitList(L); // 初始化链表
L_Insert(L); // 尾插法建立链表
PrintList(L); // 打印链表
List_Insert(L,2,222222222); // 在第2个位置插入元素222222222
PrintList(L); // 打印链表
cout<<"length::::::::::::"<<GetLength(L)<<endl; // 输出链表长度
cout<<"第3位数是"<<FindByPos(L,3)<<endl; // 输出链表中第3个元素的值
cout<<"4在第几位::::::::"<<FindByVal(L,4)<<endl; // 输出值为4的元素在链表中的位置
cout<<"删除的数是"<<ListDelte(L,2)<<endl; // 删除链表中第2个位置的元素并输出其值
PrintList(L); // 打印链表
return 0; // 返回0表示成功
}