C语言链表的实现

  • A+
所属分类:binary C++学习

唉,总得水点啥。

0x00 啥是链表

链表是区别于数组的非连续结构,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。相比于插入或删除数据时数组的复杂度O(n),链表只需要O(1)。且由于其非连续的特点可以充分利用内存中的碎片空间。

C语言链表的实现

分析

这个例子来自《C Primer Plus》,由于原文代码骚操作太多,写不来,就大概说个意思吧...

假设需要存入n部电影的信息,这些信息包括片名、评级,那么我们第一反应一定是想到结构体数组。那么100部电影就需要预先申请大于100的空间,生成的链表数组不仅占用空间多,而且向其中插入或删去项目需要O(n)的复杂度。

此时我们构造一种新的数据结构,简而言之,需要的时候才向内存申请空间。假如一个结构中除了存有数据外还存有指向下一个结构的指针,纳闷我们就可以借助这个指针访问分散在内存中各个位置的结构,实现一个“链”的作用,同时,该结构插入或删除一个项目只需O(1)复杂度

0x01 构造一个简单链表

基本结构

用我第一次写的垃圾玩意儿做示例吧.....槽点太多,轻喷

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

struct linklist
{
    int num;
    char name[40];
    struct linklist *next; //指向下一单元的指针
};



int s_get(char *in)
{
    gets(in); //没错,就是不检查溢出,咋滴~
    if (strlen(in) < 1)
        return 0; //no input
    else
        return 1;
}


int main()
{

    struct linklist *head = NULL;    //初始化头指针
    struct linklist *prev, *current; //prev是指向上一个结构的结构体指针哦~

    char input[40]; //用来缓存输入内容

    puts("please input the name or input nothing to quit:");

    while (s_get(input) != 0)
    {
        //检测到有输入后新开一个内存区域并把地址缓存在current里面
        current = (struct linklist *)malloc(sizeof(struct linklist));
        //malloc开辟出来的内存位置,即使没有指针指向,只要不free,就会一直存在到运行结束

        if (head == NULL)//判断是否为首项
            head = current;
        else
            prev->next = current;

        current->next = NULL; //初始化新数组的next指针

        strcpy(current->name, input);
        puts("please input the num:");
        scanf("%d", ¤t->num); //输入节点数据
        getchar(); //骚操作,消除数字输入的换行符,避免下一次输入误判
        puts("input the next name:");

        prev = current; //即将结束一个结构的输入,给prev指针赋值,使其指向这个新的结构
    }

    /*显示输入内容*/
    if (head == NULL)
        printf("No more\n");
    else
        printf("LIST:\n");

    current = head; //不管是否为NULL都赋值
    while (current != NULL)
    {
        printf("num:%d name:%s\n", current->num, current->name);
        current = current->next;
    }

    /*释放内存*/
    current = head;
    struct linklist *temp; 
    while (current != NULL)
    {
        temp = current->next;
        free(current);
        current = temp;
    }

    return 0;
}
 

分析

懒得分析

0x02 水平稍微长进之后,写个双向链表

这次稍微花了点时间实现:增加、插入、删除、查找显示、节点编辑,代码也简洁了许多,在这里留个备份以后用来复习

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

typedef struct Node{
    int num;
    char name[20];
    struct Node *next;
    struct Node *pre;
} node;

struct Head{
    int length=0;
    struct Node *next=NULL;
} head;

int isEmpty(struct Head *head){
    if(head->length==0 && head->next==NULL)
        return 1;
    else{
        if((head->length==0 && head->next!=NULL) || (head->length!=0 && head->next==NULL)){
            printf("List state error!\nPre exit...");
            exit(-1);
        }
        else
            return 0;
    }
}

int checkIndex(struct Head *head,int index){
    if(index>(head->length)){
        puts("Out of range!");
        return -1;
    }
    if(isEmpty(head)){
        puts("Blank list!");
        return -1;
    }
    return 1;
}

node* indexPosition(struct Head *head,int index){
    node *p;
    p=head->next;
    for(int i=0;i<index-1;i++)
        p=p->next;
    return p;
}

int initList(struct Head *head){
    if(head->length==0 && head->next==NULL)
        return 0; //already empty
    if((head->length==0 && head->next!=NULL) || (head->length!=0 && head->next==NULL)){
        printf("List state error!\nPre exit...");
        exit(-1);
    }
    else{
        node *p;
        int i=0;
        p=head->next;
        while(p!=NULL && i<head->length){
            p=p->next;
            printf("Pre free node [%d]",p->num);
            free(p);
            i++;
        }
        head->length=0;
        head->next=NULL;
        return 1;
    }
}

int getInput(node *p,int maxLen){
    if(p==NULL || maxLen>20)
        return -1;
    int ch,i=0;
    char temp[22];
    printf("Please input the name:\n");
    while(ch=getchar()){
        if((ch=='\n' && i!=0) || i==maxLen-1){  //非行首换行符才能结束输入
            temp[i]='\0';
            break;
        }
        if(ch!='\n'){   //过滤行首换行符
            temp[i]=ch;
            i++;
        }
    }
    strcpy(p->name,temp);
    return 1;
}

int addNew(struct Head *head){
    node *p;
    int i=0;
    if(head->next==NULL){
        if((p=(node *)malloc(sizeof(node)))!=NULL){
            if(getInput(p,20)==1){
                p->num=++(head->length);
                p->next=NULL;
                p->pre=NULL;
                head->next=p;
                puts("Successfully add new node!");
                return 1;
            }
            else{
                free(p);
                puts("Filed to get input!");
                return -1;
            }
        }
        else{
            printf("Cread node error!\nPre exit...");
            initList(head);
            exit(-1);
        }
    }
    else{
        int i=0;
        p=head->next;
        while(p->next!=NULL && i<head->length){
            p=p->next;
            i++;
        }
        if(p->next!=NULL){
            puts("Filed to add new node!");
            return -1;
        }
        if((p->next=(node *)malloc(sizeof(node)))!=NULL){
            if(getInput(p->next,20)==1){
                p->next->num=++(head->length);
                p->next->next=NULL;
                p->next->pre=p;
                puts("Successfully add new node!");
                return 1;
            }
            else{
                free(p->next);
                p->next=NULL;
                puts("Filed to get input!");
                return -1;
            }
        }
        else{
            printf("Cread node error!\nPre exit...");
            initList(head);
            exit(-1);
        }
    }
}

int Insert(struct Head *head,int index){
    node *p,*np;
    if(checkIndex(head,index)!=1)
        return -1;
    p=indexPosition(head,index);
    if((np=(node *)malloc(sizeof(node)))!=NULL){
        if(getInput(np,20)==1){
            np->num=p->num;
            np->next=p;
            np->pre=p->pre;
            p->pre=np;
            if(np->pre!=NULL)
                np->pre->next=np;
            else
                head->next=np;
            (head->length)++;
            for(int j=index;j<head->length;j++){
                (p->num)++;
                p=p->next;
            }
            puts("Successfully insert new node!");
            return 1;
        }
        else{
            free(np);
            puts("Filed to get input!");
            return -1;
        }
    }
    else{
        printf("Cread node error!\nPre exit...");
        initList(head);
        exit(-1);
    }

}

int Edit(struct Head *head,int index){
    node *p;
    if(checkIndex(head,index)!=1)
        return -1;
    p=indexPosition(head,index);
    if(getInput(p,20)==1){
        printf("Successfully to edit [%d]\n",index);
        return 1;
    }
    else{
        puts("Filed to edit this node!");
        return -1;
    }
}

int Delete(struct Head *head,int index){
    node *p,*temp;
    if(checkIndex(head,index)!=1)
        return -1;
    p=indexPosition(head,index);
    temp=p->next;
    if(p->next==NULL){
        if(p->pre==NULL){
            head->next=NULL;
            free(p);
        }
        else{
            p->pre->next=NULL;
            free(p);
        }
    }
    else{
        if(p->pre==NULL){
            head->next=p->next;
            p->next->pre=NULL;
            free(p);
        }
        else{
            p->next->pre=p->pre;
            p->pre->next=p->next;
            free(p);
        }
    }
    for(int i=index;i<head->length;i++){
        temp->num--;
        temp=temp->next;
    }
    head->length--;
    return 1;
}

void showAll(struct Head *head){
    node *p;
    int i=0;
    if(isEmpty(head))
        puts("None");
    else{
        p=head->next;
        printf("[Head len:%d]\n",head->length);
        printf("  ↑↓\n");
        while(p!=NULL && i<head->length){
            printf("[%d] %s\n",p->num,p->name);
            if(p->next!=NULL)
                printf("  ↑↓\n");
            p=p->next;
            i++;
        }
    }
}

int main(){
    int command,insertNum,editNum,delNum;
    while(1){
        puts("---------------------------------");
        puts("0. Init the list.");
        puts("1. Add a new node in the end.");
        puts("2. Insert a new node before [num].");
        puts("3. Edit a node from [num].");
        puts("4. Del a node from [num].");
        puts("5. Show all.");
        puts("6. Exit.");
        puts("---------------------------------");
        printf("Input the command num:\n>>>");
        scanf("%d",&command);
        switch(command){
            case 0:
                if(isEmpty(&head))
                    printf("Already init.\n");
                else{
                    if(initList(&head)==1)
                        printf("Successfully init.");
                    else
                        printf("Already init.\n");
                }
                break;
            case 1:
                addNew(&head);
                showAll(&head);
                break;
            case 2:
                puts("Input the num you want to insert before:");
                scanf("%d",&insertNum);
                Insert(&head,insertNum);
                showAll(&head);
                break;
            case 3:
                puts("Input the num you want to edit:");
                scanf("%d",&editNum);
                Edit(&head,editNum);
                showAll(&head);
                break;     
            case 4:
                puts("Input the num you want to delete:");
                scanf("%d",&delNum);
                Delete(&head,delNum);
                showAll(&head);
                break;                                
            case 5:
                showAll(&head);
                break;
            case 6:
                initList(&head);
                break;
            default:
                printf("Not this command~\n");
                break;
        }
    }
    return 0;
}
eqqie

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:1   其中:访客  1   博主  0

    • Reverier Reverier 1

      大佬太强了!!!!!!!!!!!