数据结构实验——单链表

约定不等于承诺〃 2022-06-15 23:06 200阅读 0赞

## 链表结构体 ##

typedef struct NODE
    {
        int data;
        struct NODE *next;
    }List,*linkList;
    // List 为该结构体类型别名，linkList为该结构体指针类型别名

## 单链表思想 ##

1.  采用malloc函数动态分配空间
2.  将一个一个节点通过next进行连接
3.  链表头部为指针——head，尾部节点的next指向NULL

## 操作函数声明 ##

// 初始化单链表
    int initList(linkList *head);
    // 将一串数据输入至链表
    void inputList(linkList *head);
    // 通过索引插入新数据
    void insertByIndex(linkList *head,int index);
    // 通过索引删除数据
    void deleteByIndex(linkList *head,int index);
    // 打印链表中的数据
    void printList(linkList *head);
    // 获取链表的长度
    int getLength(linkList *head);
    // 判断链表是否为空
    int isEmpty(linkList *head);
    // 测试链表连接情况
    void test(linkList *t);

## 主函数实现 ##

int main(int argc, char *argv[])
    {
        linkList head;
    
        initList(&head);
    
        inputList(&head);
    
        printList(&head);
    
        insertByIndex(&head,3);
    
        printList(&head);
    
        deleteByIndex(&head,2);
    
        printList(&head);
    
        getLength(&head);
    
        return 0;
    }

## 各个功能函数实现 ##

int initList(linkList *head){
        *head = (linkList)malloc(sizeof(List));
        if((*head) == NULL){
            printf("无法分配空间，初始化失败\n");
            return 0;
        }
        (*head)->next = NULL;
        printf("初始化成功\n");
        return 1;
    }
    
    void inputList(linkList *head){
        linkList afterList = (*head);
    
        // 找出表的尾部,使得函数可以重复添加数据
        while(afterList->next != NULL){
            afterList = afterList->next;
        }
    
        int length = 0;
        printf("新数据的数量:\t");
        scanf("%d",&length);
    
        linkList p;
        // 如何将一个一个节点相互连接 head->p->p1->p2->p3->null？
        int temp;
        while(length>0){
            p = (linkList)malloc(sizeof(List));
            scanf("%d",&temp);
    
            p->data = temp;             // 存入数据
            p->next = afterList->next;  // 将新生成的节点的next赋值为NULL
            afterList->next = p;        // 将上一个节点的next指向新生成的
            afterList = p;              // 有新节点生成，将afterList指向新节点
    
            length--;
            if(isEmpty(head) == 1){
                (*head)->next = p;      // 保证头指针，指向第一个节点
            }
        }
    }
    
    void insertByIndex(linkList *head,int index){
        linkList theNew = (linkList)malloc(sizeof(List));// 新增节点一定要同时分配新空间
    
        int data;
        printf("请输入需要插入的数:\t");
        scanf("%d",&data);
    
        linkList theAfter = (*head);//防止头指针被破坏
        linkList theBefore;
        for(;index>0;index--){
            theBefore = theAfter;
            theAfter = theAfter->next;
        }
        theNew->data = data;
        theBefore->next = theNew;
        theNew->next = theAfter;
        printf("插入成功\n");
    }
    
    void deleteByIndex(linkList *head,int index){
    
        linkList theAfter = (*head);//防止头指针被破坏
        linkList theBefore,temp;
        for(;index>0;index--){
            theBefore = theAfter;
            theAfter = theAfter->next;
        }
        theBefore->next = theAfter->next;
        free(theAfter);
        printf("删除成功\n");
    }
    
    void printList(linkList *head){
        printf("表数据为:\t");
    
        if(isEmpty(head) == 1){
            return;
        }
    
        linkList temp = (*head)->next;
    
        do{
            printf("%d\t",temp->data);
            temp = temp->next; 
        }while(temp != NULL);
    
        printf("\n");
    }
    
    int getLength(linkList *head){
    
        int result = 0;
    
        if(isEmpty(head) == 1){
            return result;
        }
    
        linkList current = (*head)->next;
        do{
            result++;
            current = current->next;
        }while(current != NULL);
    
        printf("表长度为:%d\n",result);
        return result;
    }
    
    int isEmpty(linkList *head){
        if((*head)->next == NULL){
            //printf("表为空\n");
            return 1;
        }else{
            //printf("表不为空\n");
            return 0;
        }
    }
    
    void test(linkList *t){
        printf("\n-------测试-------\n");
        printf("self:%p\t",(*t));
        printf("data:%d\t",(*t)->data);
        printf("next:%p\n",(*t)->next);
        printf("-------结束-------\n\n");
    }

## 运行结果展示 ##

![这里写图片描述][SouthEast]

## 源代码参考 ##

#include <stdio.h>
    #include <malloc.h>
    
    typedef struct NODE
    {
        int data;
        struct NODE *next;
    }List,*linkList;
    
    // 初始化单链表
    int initList(linkList *head);
    // 将一串数据输入至链表
    void inputList(linkList *head);
    // 通过索引插入新数据
    void insertByIndex(linkList *head,int index);
    // 通过索引删除数据
    void deleteByIndex(linkList *head,int index);
    // 打印链表中的数据
    void printList(linkList *head);
    // 获取链表的长度
    int getLength(linkList *head);
    // 判断链表是否为空
    int isEmpty(linkList *head);
    // 测试链表连接情况
    void test(linkList *t);
    
    int main(int argc, char *argv[])
    {
        linkList head;
    
        initList(&head);
    
        inputList(&head);
    
        printList(&head);
    
        insertByIndex(&head,3);
    
        printList(&head);
    
        deleteByIndex(&head,2);
    
        printList(&head);
    
        getLength(&head);
    
        return 0;
    }
    
    int initList(linkList *head){
        *head = (linkList)malloc(sizeof(List));
        if((*head) == NULL){
            printf("无法分配空间，初始化失败\n");
            return 0;
        }
        (*head)->next = NULL;
        printf("初始化成功\n");
        return 1;
    }
    
    void inputList(linkList *head){
        linkList afterList = (*head);
    
        // 找出表的尾部,使得函数可以重复添加数据
        while(afterList->next != NULL){
            afterList = afterList->next;
        }
    
        int length = 0;
        printf("新数据的数量:\t");
        scanf("%d",&length);
    
        linkList p;
        // 如何将一个一个节点相互连接 head->p->p1->p2->p3->null？
        int temp;
        while(length>0){
            p = (linkList)malloc(sizeof(List));
            scanf("%d",&temp);
    
            p->data = temp;             // 存入数据
            p->next = afterList->next;  // 将新生成的节点的next赋值为NULL
            afterList->next = p;        // 将上一个节点的next指向新生成的
            afterList = p;              // 有新节点生成，将afterList指向新节点
    
            length--;
            if(isEmpty(head) == 1){
                (*head)->next = p;      // 保证头指针，指向第一个节点
            }
        }
    }
    
    void insertByIndex(linkList *head,int index){
        linkList theNew = (linkList)malloc(sizeof(List));// 新增节点一定要同时分配新空间
    
        int data;
        printf("请输入需要插入的数:\t");
        scanf("%d",&data);
    
        linkList theAfter = (*head);//防止头指针被破坏
        linkList theBefore;
        for(;index>0;index--){
            theBefore = theAfter;
            theAfter = theAfter->next;
        }
        theNew->data = data;
        theBefore->next = theNew;
        theNew->next = theAfter;
        printf("插入成功\n");
    }
    
    void deleteByIndex(linkList *head,int index){
    
        linkList theAfter = (*head);//防止头指针被破坏
        linkList theBefore,temp;
        for(;index>0;index--){
            theBefore = theAfter;
            theAfter = theAfter->next;
        }
        theBefore->next = theAfter->next;
        free(theAfter);
        printf("删除成功\n");
    }
    
    void printList(linkList *head){
        printf("表数据为:\t");
    
        if(isEmpty(head) == 1){
            return;
        }
    
        linkList temp = (*head)->next;
    
        do{
            printf("%d\t",temp->data);
            temp = temp->next; 
        }while(temp != NULL);
    
        printf("\n");
    }
    
    int getLength(linkList *head){
    
        int result = 0;
    
        if(isEmpty(head) == 1){
            return result;
        }
    
        linkList current = (*head)->next;
        do{
            result++;
            current = current->next;
        }while(current != NULL);
    
        printf("表长度为:%d\n",result);
        return result;
    }
    
    int isEmpty(linkList *head){
        if((*head)->next == NULL){
            //printf("表为空\n");
            return 1;
        }else{
            //printf("表不为空\n");
            return 0;
        }
    }
    
    void test(linkList *t){
        printf("\n-------测试-------\n");
        printf("self:%p\t",(*t));
        printf("data:%d\t",(*t)->data);
        printf("next:%p\n",(*t)->next);
        printf("-------结束-------\n\n");
    }

[SouthEast]: /images/20220616/7bd12f6240a4410d9659af5ffbef0083.png