数据结构-单链表

资讯 2023-12-06 17:15:12

#include<stdio.h>
#include<stdlib.h>

//单链表结构
typedef struct LNode{
    int data;//数据域
    struct LNode* next;//指针域
}LNode,*LinkList;

//初始化带头结点
bool InitList(LinkList &L){
    L= (LNode*)malloc(sizeof(LNode));
    if(L==NULL)
        return false;//内存不足
    L->next=NULL;//头结点之后,暂时没有结点
    return true;
}

//判空
bool Empty(LinkList L){
    return(L->next==NULL);
}

//指定结点的后插操作//前插的话直接后插完换数据就好了
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;
}

//获取一个元素
LNode* GetElem(LinkList L,int i){
    if(i<1)
    return false;
    LNode* p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    return p;
}
        
//按位序插入
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode* p;
    p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    InsertNextNode(p,e);
    return true;
}

//指定结点的删除
bool DeleteNode(LNode*p){
    if(p==NULL)
        return false;
    LNode* q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
    return true;
}
//按位序删除
bool ListDelete(LinkList &L,int i,int &e){
    LNode*p=GetElem(L,i);
    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;
}

//尾插法可以用后插操作实现,可是每次都要循环找到i的前i-1个结点,时间复杂度n²,所以设立尾指针
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;
}

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

 

int main(){
    
    return 0;
}
声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。