数据结构(严蔚敏)2.3.2双向链表(循环)

资讯 2023-12-06 17:23:30

学习记录,仅作参考,希望可以指出错误

数据结构(严蔚敏)2.3.2双向链表(循环)

 

 

#include<stdio.h>
#include<stdlib.h>
//双向链表(循环
typedef float elemtype;

typedef struct lnode{
    elemtype data;
    struct lnode *prior;
    struct lnode *next;
}lnode,*linklist;


void initlist_sx(linklist &l){
    l=new lnode;
    l->data=0;
    l->next=l;
    l->prior=l;
}

void insertlist_sx(linklist &l,elemtype e,int num){//插为第num个
    int i=1;
    linklist ll=l;
    while(i<=num){//循环到要插入位置的下一个
        ll=ll->next;
        i++;
    }
    linklist li=new lnode;
    li->data=e;
    
    li->next=ll;
    li->prior=ll->prior;
    ll->prior->next=li;
    ll->prior=li;

    l->data=l->data+1;
}

linklist getelem_sx(linklist l,int num){//获取原第Num的地址
    int i=1;
    linklist ll=l;
    while(i<=num){
        ll=ll->next;
        i++;
    }
    return ll;

}
//算法2.18
int listinsert_dul(linklist &l,int num,elemtype e){
    linklist p;
    if(!(p=getelem_sx(l,num)))return 1;
    linklist s;
    if(!(s=(linklist)malloc(sizeof(lnode))))return 1;
    s->data=e;

    s->prior=p->prior;//p是要插入位置的下一个
    p->prior->next=s;
    s->next=p;
    p->prior=s;

    l->data=l->data+1;
    return 0;
}
//算法2.19
int listdelete_dul(linklist &l,int num,elemtype &e){
    linklist p;
    if(!(p=getelem_sx(l,num)))return 1;
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    l->data=l->data-1;
    return 0;
}
int length_sx(linklist l){
    return (int)l->data;
}
elemtype deletelist_sx(linklist &l,int num){
    if(num>l->data) return NULL;
    linklist ll=l;
    for(int i=1;i<num;i++) ll=ll->next;//循环到要删除的位置的前一个
    linklist deleteid=ll->next;
    elemtype e=deleteid->data;

    if(deleteid->next!=NULL){//如果要删除的不是最后一个,就会有修改prior的过程
    ll->next=ll->next->next;
    ll->next->prior=ll;}
    else{
        ll->next=NULL;
    }
    free(deleteid);
    l->data=l->data-1;
    return e;

}



void printf_sx(linklist l){
    printf("\n开始输出 %d个\n",length_sx(l));
    int num=length_sx(l);
    for(int i=0;i<num;i++){
        l=l->next;
        printf("%f    ",l->data);
    }
    printf("\n");
}
void printfx2_sx(linklist l){//输出10个
    printf("\n开始输出 %d个\n",length_sx(l));
    linklist ll=l;
    while(ll->next!=l){
        ll=ll->next;
        printf("%f    ",ll->data);
    }
    printf("\n");
    ll=l;
    for(int i=0;i<10;i++){
        ll=ll->next;
        printf("%f    ",ll->data);
    }
    printf("\n");
}
void printfx3_sx(linklist l){//逆着输出
    printf("\n开始逆着输出 %d个\n",length_sx(l));
    linklist ll=l;
    while(true){
        ll=ll->prior;
        if(ll==l){ break;printf("\n退出\n");}
        printf("%f    ",ll->data);

    }
}

void scanf_sx(linklist &l){
    printf("输入你要输入的个数:\n");
    int num;
    scanf("%d",&num);
    printf("开始输入:\n");
    for(int i=1;i<=num;i++){
        elemtype e;
        scanf("%f",&e);
        
        insertlist_sx(l,e,i);
        //listinsert_dul(l,i,e);//书上的
    }
}

void main(){
    linklist l;
    printf("*****************测试initlist_sx\n");
    initlist_sx(l);
    printf("\n*****************测试scanf_sx\n");
    scanf_sx(l);
    printf("\n*****************测试printf_sx\n");
    printf_sx(l);
    //printf("\n*****************测试printfx2_sx\n");
    //printfx2_sx(l);
    printf("\n*****************测试printfx3_sx\n");
    printfx3_sx(l);
    //printf("\n*****************测试deletelist_sx(删除第3个\n");
    //printf("删除的为%f    ",deletelist_sx(l,3));
    //printf_sx(l);
    printf("\n*****************测试listdelete_dul(删除第3个\n");
    elemtype e;listdelete_dul(l,3,e);
    printf("删除的为%f    ",e);
    printf_sx(l);
}

 

声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。