c++ 链表及其相关操作

《仅供自己学习参考》
链表，线性表的链式储存结构。

  • 用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续 的，也可以不连续）
  • 数据元素之间逻辑上相邻，物理位置可不相邻

前提：

typedef struct LNode
{int data;//存放数据元素的值struct LNode * next;//指针，指向后继结点
}LNode,*LinkList;

单链表的创建及其相关操作

  • 头插法建表
    （注意数据元素顺序）
void creatlist(LinkList &L,int n)//头插法--创建链表6 5 4 3 2 1，有头结点  
{LNode *p=NULL;//定义一个LNode类型的指针，为后续操作做准备L=(LinkList)malloc(sizeof(LNode));//为头指针分配内存--创建相应的头结点L->next=NULL;//将头结点指针域置空for(int i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));p->data =i;p->next =L->next;L->next=p;}
}
  • 尾插法建表
void creatlist2(LinkList &L,int n)//尾插法--创建链表4 5 6 7 8 9 ，有头结点 
{LNode *p=NULL;//定义一个LNode类型的指针，为后续操作做准备LinkList r;//定义一个尾指针，指向链表的表尾结点L=(LinkList)malloc(sizeof(LNode));//为头指针分配内存--创建相应的头结点L->next =NULL;//头结点指针域置空r=L;//初始时期，尾结点即为头结点for(int i=4;i<=4+n-1;i++){p=(LinkList)malloc(sizeof(LNode));p->data =i;r->next =p;r=r->next ;}p->next =NULL;//链表表尾指针域置空 
}
  • 插入操作
    （如果要在第i个元素前插入，可以相应修改）
Status Lsitinsert(LinkList &L, int i, int e)//在第i个元素之后插入e 
{LinkList p;//定义一个LNode类型的指针，便于指向要插入的位置LNode *s=NULL;//用来创建要插入的元素的结点int j=0;//头结点p=L ;while(p&&j<i){p=p->next;j++;}if(!p) return ERROR;s=(LinkList)malloc(sizeof(LNode));s->next =p->next;s->data =e;p->next=s;return OK;
}
  • 删除操作
Status Listdelete(LinkList L,int i)//删除第i个元素
{LinkList p;//定义一个LNode类型的指针，便于指向要删除的位置LinkList q;//用来记录删除位置int j=0;//头结点开始，因为i可以为1p=L;while(p&&j<i-1){p=p->next;j++;}if(!(p->next )) return ERROR;q=p->next;p->next =q ->next;free(q);return OK;
}
  • 链表长度
int llength(LinkList L)
{int x=0;LinkList p;p=L;while(p->next ){p=p->next ;x++;}return x;
}
  • 显示链表元素
void show(LinkList L)
{int x=llength(L);L=L->next ;for(int i=1;i<=x;i++){cout<<L->data<<" " ;L=L->next ;}cout<<endl;
}
  • 合并两个有序递增链表
void merge(LinkList &l1,LinkList &l2,LinkList &l3)//合并两个有序链表，并返回 
{LinkList p1,p2,p3;l3=(LinkList)malloc(sizeof(LNode));p1=l1->next ;p2=l2->next ;p3=l3;while(p1&&p2){if(p1->data <=p2->data ){p3->next =p1 ;p3=p1;p1=p1->next ;}else{p3->next =p2;p3=p2;p2=p2->next ;}}p3->next=p1?p1:p2;}
  • 获取链表元素
Status GetElem(LinkList &L,int i,int &e)  //获取第i个元素的值 
{LinkList p;int j=0;int xx=llength(L);if(i>xx) return ERROR;p=L;while(p&&j<i){p=p->next;j++;}if(!p) return ERROR;e=p->data ;return OK;
}
  • 主函数
int main()
{LNode* l1;LNode *l2;LNode*l3;LNode * l4;int e=0;creatlist(l1,6);creatlist2(l2,6);creatlist2(l4,6);show(l1);show(l2);show(l4);cout<<llength(l1)<<endl;merge(l2,l4,l3);show(l3);Lsitinsert(l1, 6, 0);show(l1);Listdelete(l1,1);show(l1);GetElem(l1,2,e);cout<<e<<endl;return 0;
}
  • 运行结果

完