408数据结构

Linear 线性表

Linklist 链表

一·Single_linked_list.cpp单链表

1.单链表结构体

typedef struct LNode{//单链表结构体
    Elemtype data;
    struct LNode *next;
}LNode,*LinkList;

2.初始化单链表

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

3.初始化循环单链表

bool InitList(LinkList &L){//初始化循环单链表
    L=(LNode *) malloc(sizeof (LNode));
    if(L==NULL)
        return false;
    L->next=L;
    return true;
}

4.判断是否为空

bool Empty(LinkList L){//判断是否为空
    if(L->next==NULL)
        return true;
    else
        return false;
}

5.判断循环单链表是否为空

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

6.按位查找

LNode * GetElem(LinkList L,int i){//按位查找
    if(i<0)
        return NULL;
    LNode *p;
    int j=0;
    p=L;
    while (p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

7.后插法

bool InsertNextNode(LNode *p,Elemtype e){//后插法
    if(p==NULL)
        return false;
    LNode *s=(LNode *) malloc(sizeof (LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

8.前插法

bool InsertPriorNode(LNode *p,Elemtype e){//前插法
    if(p==NULL)
        return false;
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true;
}

9.按位插入

bool ListInsert(LinkList &L,int i,Elemtype e){//按位插入
    if(i<1)
        return false;
//    LNode *p;
//    int j=0;
//    p=L;
//    while (p!=NULL&&j<i-1){
//        p=p->next;
//        j++;
//    }
    LNode *p= GetElem(L,i-1);
//    if(p==NULL)
//        return false;
//    LNode *s=(LNode *) malloc(sizeof (LNode));
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
    return InsertNextNode(p,e);
}

10.删除第i位

bool ListDelete(LinkList &L,int i,Elemtype &e){//删除第i位置元素
    if(i<1)
        return false;
//    LNode *p;
//    int j=0;
//    p=L;
//    while (p!=NULL&&j<i-1){
//        p=p->next;
//        j++;
//    }
    LNode *p= GetElem(L,i-1);
    if(p==NULL)
        return false;
    if(p->next==NULL)
        return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

11.删除指定节点

bool DeleteNode(LNode *p){//删除指定节点
    if(p==NULL)
        return false;
    LNode *q=p->next;
    p->data=p->next->data;//有小bug，当最后删除最后一个节点时失效。
    p->next=q->next;
    free(q);
    return true;
}

12.按值查找

LNode *LocateElme(LinkList L,Elemtype e){//按值查找
    LNode *p=L->next;
    while (p!=NULL&&p->data!=8)
        p=p->next;
    return p;
}

13.求表长

int Length(LinkList L){//求表长
    int len=0;
    LNode *p=L;
    while(p->next!=NULL){
        p=p->next;
        len++;
    }
    return  len;
}

14.尾插法

LinkList List_TailInsert(LinkList &L){//尾插法
    int x;
    L=(LinkList) malloc(sizeof (LNode));
    LNode *s,*r=L;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

15.头插法

LinkList List_HeadInsert(LinkList &L){//头插法
    LNode *s;
    int x;
    L=(LinkList) malloc(sizeof (LNode));
    L->next=NULL;
    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;
}

二.Double_linked_list.cpp双链表

1.双链表结构体

typedef struct DNode{//双链表结构体
    Elemtype data;
    struct DNode *prior,*next;
}DNode,*DLinklist;

2.初始化双链表

bool InitDLinkList(DLinklist &L){//初始化双链表
    L=(DNode *) malloc(sizeof (DNode));
    if(L==NULL)
        return false;
    L->prior=NULL;
    L->next=NULL;
    return true;
}

3.初始化循环双链表

//bool InitDLinkList(DLinklist &L){//初始化循环双链表
//    L=(DNode *) malloc(sizeof (DNode));
//    if(L==NULL)
//        return false;
//    L->prior=L;
//    L->next=L;
//    return true;
//}

4.判断双链表是否为空

bool Empty(DLinklist L){//判断双链表是否为空
    if(L->next==NULL)
        return true;
    else
        return false;
}

5.判断循环双链表是否为空

//bool Empty(DLinklist L){//判断循环双链表是否为空
//    if(L->next==L)
//        return true;
//    else
//        return false;
//}

6.双链表插入

bool InserNextDNode(DNode *p,DNode *s){//双链表插入
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    if(p->next != NULL)
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

7.删除p节点的后继节点

bool DeleteNextDNode(DNode *p){//删除p节点的后继节点
    if(p==NULL)
        return false;
    DNode *q=p->next;
    if(q==NULL)
        return false;
    p->next=q->next;
    if(q->next!=NULL)
        q->next->prior=p;
    free(q);
    return true;
}

8.销毁双链表

void DestoryList(DLinklist &L){//销毁双链表
    while (L->next!=NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

三.Static_linked_list.cpp静态链表

1.定义静态链表结构体

#define MaxSize 10//静态链表最大长度
typedef struct {
    Elemtype data;
    int next;
}SLinkList[MaxSize];

四、源代码见github:Linklist 链表：https://github.com/3190704121/link_list

代码是使用CLion编写,有需要可以跳转github获取

• 还没有人评论，欢迎说说您的想法！