[C++知识库]数据结构_链表表_基本操作的c++实现

#include <iostream>

using namespace std;

//链表
//基本操作

//定义单链表
typedef struct LNode{
    int data;//数据域
    struct LNode *next;//指针域,指向下一个节点
}LNode,*LinkList;
/*---------------------------等价于------------------------------
struct LNode{
    int data;
    struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
-------------------------------------------------------------*/

//初始化单链表（不带头节点）
bool InitList_1(LinkList &L){
    L=NULL;                    //空表，暂时还没有任何节点
    return true;
}
//判空（不带头节点）
bool Empty_1(LinkList L){
        return (L==NULL);
}

//初始化单链表（带头节点）   //带头结点写代码比较方便
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)                  //内存不足，分配失败
        return false;
    L->next = NULL;           //头结点之后暂时还没有结点
    return true;
}
//判空（带头结点）
bool Empty(LinkList L){
    if(L->next==NULL)
        return true;
    else
        return false;
}

//插入：
//按位序插入，在第i个位置插入元素e（不带头结点）
bool ListInsert_1(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    if(i==1){
        s->next=L;
        L=s;
        return true;
    }
    LNode *p=L;
    for(int j=1;p!=NULL&&j<i-1;j++) //循环找到第i-1个结点，因没有头结点，故结点数从1开始，j=1而非0，j代表p指向的结点为第几个（序号）
        p=p->next;
    if(p==NULL)                  //i值不合法，
        return false;
    s->next=p->next;
    p->next=s;
    return true;
}

//指定结点的后插操作
bool InsertNextNode(LNode *p,int e){
    if(p==NULL)          //给定结点不存在
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;//内存分配失败
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//按位序插入，在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0;
    p=L;//L指向头节点，头节点是第0个节点（不存数据）
    while(p!=NULL&&j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    InsertNextNode(p,e);
    /*
    if(p==NULL)  //i值不合法
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;//!顺序不
    p->next=s;    //!能颠倒
    */
    return true;
}

//指定结点的前插操作
bool InsertPriorNode(LNode *p,int e){
    if(p==NULL)
        return false;//给定结点不存在
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;//内存分配失败
    s->data=p->data;
    s->next=p->next;
    p->next=s;
    p->data=e;//偷天换日，嘻嘻！
    return true;
}

//删除启动！
//按位序删除,删除表中第i个位置的元素，并用e返回删除元素的值（带头结点）           时间复杂度为O(n)
bool ListDelete(LinkList &L,int i,int &e){
    //if(L==NULL)
      //  return false;//L为空表
    if(i<1)
        return false;//i值不合法
    LNode *p=L;
    for(int j=0;p!=NULL&&j<i-1;j++)//找到第i-1个结点
        p=p->next;
    if(p==NULL)
        return false;//i值不合法，在i之前的结点p已经为空，该判断语句包含了表L为空表这一情况
    LNode *q=p->next;    //必须还要一个指向第i个结点的指针才行
    p->next=q->next;
    e=q->data;
    free(q);
    return true;
}

//删除指定结点p
bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;//指定结点不存在
    LNode *q=p->next;  //时间复杂度为0(n),我狂偷！！！，，，，，但是如果p->next==NULL，就不行了，只能从第一个结点开始遍历，时间复杂度为O(n)
    p->next=q->next;
    p->data=q->data;
    free(q);
    return true;
}

//查找
//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L,int i){


    if(i<1)
        return NULL;
    LNode *p=L;//指针p指向当前扫描到的结点，L指向头结点，头结点是第0个结点（不存数据）
    int j=0;   //当前p指向的是第几个结点
    while(p!=NULL&&j<i){  //循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}

/*-----------和上面的GetElem函数等效
LNode *GetElem(LinkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0)
        return L;            //显示出该链表 带头结点
    if(i<1)
        return NULL;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}
*/

//按值查找，找到数据域==e的结点
LNode *LocateElem(LinkList L,int e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    return p;//找到后返回该结点指针，否则返回NULL
}

//求表的长度（带头结点）
int Length(LinkList L){
    LNode *p=L->next;
    int len=0;
    while(p!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));//建立头结点
    LNode *s,*r=L; //r为表尾指针
    scanf("%d",&x);
    while(x!=9999){  //输入9999表示结束，自定义的
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;             //指向新的表尾结点
        scanf("%d",&x);
    }
    r->next=NULL;    //尾结点指针置空
    return L;
}

//头插法建立单链表    !!!!!重要应用：链表的逆置
LinkList List_HeadInsert(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *s;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

//头插法建立单链表（不带头结点）
LinkList List_HeadInsert_1(LinkList &L){
    int x;
    LNode *s;
    L=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L;
        L=s;
        scanf("%d",&x);
    }
    return L;
}

/*-----------------------------双链表-------------------------------*/
//双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)
//定义
typedef struct DNode{   //double
    int data;
    struct DNode *prior,*next;   //前驱和后继
}DNode,*DLinkList;

//初始化双链表（带头结点）
bool InitDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=NULL;
    L->next=NULL;
    return true;
}

//双链表的插入（在p结点之后插入s结点）
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    s->prior=p;
    if(p->next!=NULL){  //如果p结点有后继结点
        p->next->prior=s;
    }
    p->next=s;   //这一步一定在最后
    return true;
}

//双链表的删除（删除p结点的后继结点q）
bool DeleteNextDNode(DNode *p){
    DNode *q=p->next;
    if(p==NULL||q==NULL)
        return false;
    p->next=q->next;
    if(q->next!=NULL)
        q->next->prior=p;
    free(q);
    return true;
}

//销毁双链表
void DestoryDList(DLinkList &L){
    //循环释放各个数据结点
    while(L->next!=NULL)
        DeleteNextDNode(L);
    free(L); //释放头结点
    L=NULL;  //头指针指向NULL
}

//双链表的遍历
void Travel(DNode *p){
    //后向遍历
    while(p!=NULL)
        p=p->next;
    //前向遍历
    while(p!=NULL)
        p=p->prior;
    //跳过头结点的前向遍历
    while(p->prior!=NULL)
        p=p->prior;
}

/*----------------------循环单链表----------------------------------------------*/
//表尾指针的next指向头结点
//从表尾找到表头时间复杂度仅为O(1),故可以让L指向表尾元素（插入、删除时可能需要修改L）
//定义同单链表相同

//初始化
bool InitCycleList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)
        return false;
    L->next=L;       //!
    return true;
}

//判断循环单链表是否为空
bool CycleEmpty(LinkList L){
        return (L->next==L);
}

//判断结点p是否为循环单链表的表尾结点
bool CycleisTail(LinkList L,LNode *p){
    return (p->next==L);
}

/*----------------------循环双链表----------------------------------------------*/
//表头结点的prior指向表尾结点
//表尾结点的next指向表头结点

//初始化
bool InitCycleDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=L;
    L->next=L;
    return true;
}

//循环双链表的判空
bool CycleDEmpty(DLinkList L){
    return (L->prior==L&&L->next==L);
}

//判断结点p是否为循环双链表的表尾结点
bool CycleDisTail(LinkList L,LNode *p){
    return (p->next==L);
}

/*---------------------------------静态链表-----------------------*/
//用数组的方式实现的链表
//定义
#define MaxSize 10
typedef struct{
    int data;
    int next;
}SLinkList[MaxSize];//调用时 SLinkList a;等价于 struct Node a[MaxSize];

//初始化
bool InitSLinkList(SLinkList &a){
    a[0].next=-1;
    return true;
}

//查找：从头结点出发挨个儿往后遍历结点

//插入位序为i的结点：
//1.找到一个空的结点，存入数据元素
//2.从头结点出发找到位序为i-1的结点
//3.修改新结点的next
//4.修改i-1号结点的next

//删除某个结点：
//1.从头结点出发找到前驱结点
//修改前驱结点的游标
//被删除结点next设为-2（-2代表该结点已被回收，里面已经没有数据了）

int main()
{
    int *a;
    int c=20;
    a=&c;
    int *b=a;


    cout << b << endl;
    cout <<a << endl;
    cout << *a << endl;
    cout << *b << endl;
    return 0;
}