欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表

程序员文章站 2022-03-11 21:42:19
...

c语言中除了数组以外,比较常见的数据结构就是链表了。

链表和数组的不同点在于一个是连续存储,一个是不连续的。

数组更改元素的相对位置比较慢,比如把数组第k个元素去掉,然后k以后的元素整体前移。

链表只需释放节点,更改指针就行

此篇是最简单的单项链表的几个功能。



首先是数据结构

typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
}LNode;



建立链表

LNode *creat_L(){
    LNode *h,*p,*s;
    ElemType x;
    h=(LNode*)malloc(sizeof(LNode));
    h->next=NULL;
    p=h;
    printf("\n  data=?");
    scanf("%d",&x);
    while(x!=-111){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->data=x;
        s->next=NULL;
        p->next=s;p=s;
        printf("data=? (-111 end)");
        scanf("%d",&x);    
    }
    return h;    
}



输出链表

void out_L(LNode *L){
    LNode *p;char ch;
    p=L->next;
    printf("\n\n");
    while(p!=NULL){
        printf("%5d",p->data);
        p=p->next;
    }
    printf("\n\n按Enter键,继续");
    ch=getchar();
}



插入

void insert_L(LNode*L,int i,ElemType e){
    LNode *s,*p,*q;int j;
    p=L;
    j=0;
    while(p!=NULL){
        p=p->next;
        j++;
        if(j==i-1)
            break;
    }
    if(p==NULL||j>i-1)
        printf("\n i ERROR!");
    else{
        s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
    }
    
}



删除节点

ElemType delete_L(LNode    *L,int i){
    LNode *p,*q;int j;ElemType x;
    p=L;j=0;
    while(p->next!=NULL&&j<i-1){
        p=p->next;j++;
    }
    if(p->next==NULL){
        printf("\n i ERROR!");
        return -1;
    }
    else{
        q=p->next;
        x=q->data;
        p->next=q->next;free(q);
        return x;
    }    
}



查找

int locat_L(LNode*L,ElemType e){
    LNode *p;int j=1;
    p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
        j++;
    }
    if(p!=NULL)
        return j;
    else
        return -1;
}



最后是全部代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
}LNode;
LNode * L;
LNode *creat_L();
void out_L(LNode *L);
void insert_L(LNode *L,int i,ElemType e);
ElemType delete_L(LNode *L,int i);
int locat_L(LNode *L,ElemType e);
int main(int argc, char *argv[])
{
    int i,k,loc;
    ElemType e,x;
    char ch;
    do{ 
        printf("\n\n    1.建立线性链表");
        printf("\n\n    2.在i位置插入元素");
        printf("\n\n    3.删除第i个元素,返回其值");
        printf("\n\n    4.查找值为e的元素");
        printf("\n\n    5.结束程序运行");
        printf("\n=====================");
        printf("\n    请输入你的选择:(1,2,3,4,5)");
        scanf("%d",&k);
        switch(k)
        {
            case 1:{
                L=creat_L();
                out_L(L);
            }break;
            case 2:{
                printf("\n i,e=?");
                scanf("%d,%d",&i,&e);
                insert_L(L,i,e);
                out_L(L);
            }break;
            case 3:{
                printf("\n i=?");
                scanf("%d",&i);
                x=delete_L(L,i);
                out_L(L);
                if(x!=-1)
                    printf("\n x=%d\n",x);
            }break;
            case 4:{
                printf("\n e=?");
                scanf("%d",&e);
                loc=locat_L(L,e);
                if(loc==-1)
                    printf("\n 未找到%d",loc);
                else
                    printf("\n 已找到,元素位置是%d",loc);
            }break;
        }
        getchar();
        printf("\n-----------------");
    }while(k>=1&&k<5);
    printf("\n    再见!");
    printf("\n    按enter键,返回");
    ch=getchar(); 
    return 0;
}

LNode *creat_L(){
    LNode *h,*p,*s;
    ElemType x;
    h=(LNode*)malloc(sizeof(LNode));
    h->next=NULL;
    p=h;
    printf("\n  data=?");
    scanf("%d",&x);
    while(x!=-111){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->data=x;
        s->next=NULL;
        p->next=s;p=s;
        printf("data=? (-111 end)");
        scanf("%d",&x);    
    }
    return h;    
}
void out_L(LNode *L){
    LNode *p;char ch;
    p=L->next;
    printf("\n\n");
    while(p!=NULL){
        printf("%5d",p->data);
        p=p->next;
    }
    printf("\n\n按Enter键,继续");
    ch=getchar();
}
void insert_L(LNode*L,int i,ElemType e){
    LNode *s,*p,*q;int j;
    p=L;
    j=0;
    while(p!=NULL){
        p=p->next;
        j++;
        if(j==i-1)
            break;
    }
    if(p==NULL||j>i-1)
        printf("\n i ERROR!");
    else{
        s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
    }
    
}
ElemType delete_L(LNode    *L,int i){
    LNode *p,*q;int j;ElemType x;
    p=L;j=0;
    while(p->next!=NULL&&j<i-1){
        p=p->next;j++;
    }
    if(p->next==NULL){
        printf("\n i ERROR!");
        return -1;
    }
    else{
        q=p->next;
        x=q->data;
        p->next=q->next;free(q);
        return x;
    }    
}
int locat_L(LNode*L,ElemType e){
    LNode *p;int j=1;
    p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
        j++;
    }
    if(p!=NULL)
        return j;
    else
        return -1;
}
相关标签: 链表