2020年考研数据结构复习——单链表

╰+哭是因爲堅強的太久メ 2021-12-03 05:04 231阅读 0赞

2020年考研数据结构复习——单链表

代码

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <cstring>
    #include "malloc.h"
    
    //单链表存储结构
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    
    } LNode, *LinkList;
    
    //头插法
    void CreateList_L(LinkList &L)
    {
        //头插法建立带头节点的链表
        L->next = NULL;//先建立一个带头节点的单链表
        int x;
        scanf("%d", &x); //输入元素值
        while(x!=-1)
        {
            LNode *p = (LNode*)malloc(sizeof(LNode));
            p -> data = x;
            p -> next = L->next;
            L->next = p; //插入
            scanf("%d", &x);
        }
    }
    
    
    void CreateList_L2(LinkList &L)
    {
        //尾插法建立带头节点的链表
        L->next = NULL;//先建立一个带头节点的单链表
        LNode *q = L;
        int x;
        scanf("%d", &x); //输入元素值
        while(x!=-1)
        {
            LNode *p = (LNode*)malloc(sizeof(LNode));
            p -> data = x;
            p -> next = NULL;
            q -> next = p;
            q = p; //q用于保存最后一个链表节点
            scanf("%d", &x);
        }
    }
    
    //计算链表的长度
    int Link_length(LinkList L)
    {
        //计算链表的长度
        LNode *p = L->next;
        int length = 0;
        while(p!=NULL)
        {
            length++;
            p = p->next;
        }
        return length;
    }
    
    //取得第i项的值，按位置查找
    int GetElem(int i, LinkList L)
    {
        if(i<0&&i>Link_length(L))
            return -1;//查询位置不合法，返回-1
        LNode *p = L->next;
        int l = 1;
        while(p!=NULL)
        {
            if(l==i)
                return p->data;
            p = p->next;
            l++;
        }
    
    }
    //返回最后一个LNode节点
    LNode* lastlnode(LinkList L)
    {
    
        LNode *p = L;
        while(p->next!=NULL)
        {
            p = p->next;
        }
        return p;
    }
    
    //头插法
    void insert_head(LinkList &L, int x)
    {
        LNode *p = (LNode*)malloc(sizeof(LNode));
        if (p==NULL)
            return;
        p->data = x;
        p->next = L->next;//新建节点指向头节点的下一个
        L->next = p; //p指向头节点后，即将新节点插入链表中
    }
    
    //尾插法
    void insert_tail(LinkList &L, int x)
    {
        LNode *p = (LNode*)malloc(sizeof(LNode));
        if (p==NULL)
            return;
        p->data = x;
        p->next = NULL;
        LNode *q = lastlnode(L);
        q->next = p; //将新节点插入链表中
    }
    
    //删除指定位置的节点,并返回其值
    void delete_head(int i,int &x,LinkList &L)
    {
        if(i<0&&i>Link_length(L))
            return;//删除位置不合法，返回-1
        LNode *p = L;
        LNode *q = L;
    
        int l = 0;
        while(p!=NULL)
        {
            q = p->next;
            if(l+1==i)
                p->next=q->next;
            x=p->data;
            free(q);
            char str[10]="删除成功";
            printf("%s\n",str);
            return;
            p = p->next;
            l++;
        }
    }
    
    //转置
    void reserve(LinkList &L)
    {
        if(L==NULL||L->next==NULL||L->next->next==NULL)
            return;
        LNode *p = L->next;
        LNode *q = p->next;
        p->next = NULL; //第一个p相当于最后一个，其指针域指向空
        LNode *l;
        while(q->next != NULL)
        {
            l = q->next;
            q->next = p;
            p = q;
            q = l;
        }
        //q->next == NULL 即q是最后一个结点
        q->next = p;
        L->next = q; //头结点指向原来的最后一个
    }
    
    //单链表的升序排序（采用冒泡排序）
    void sort_list(LinkList L)
    {
        if(L==NULL||L->next->next==NULL)
            return;
    
        LNode *p,*q,*temp,*l,*tail;
        p = L;
        q = p->next;
        tail = NULL;
        while(L->next!=tail)
        {
            p = L;
            q = p->next;
            while(q->next!=tail)
            {
                l = q->next;
                if(l->data < q->data) //逆序
                {
                    q->next=l->next;
                    l->next=q;
                    p->next=l;
                    temp=l;
                    l=q;
                    q=temp;
                }
                p=q;
                q=l;
            }
            tail=q;//q->next==NULL,则q是最后一个
        }
    
    }
    
    //打印
    void print(LinkList L)
    {
        LinkList p = L;
        while(p!=NULL)
        {
            p= p->next;
            printf("%d\n",(p->data));
        }
    }
    
    int main()
    {
        LinkList L = NULL; //这里表示的已经是已经个指针了
        L = (LinkList )malloc(sizeof(LNode));
        if(L==NULL)
        {
            return -1;
        }
        CreateList_L(L); //头插法建立单链表
        //CreateList_L2(L); //尾插法建立单链表
        //printf("%d\n",Link_length(L)); //测试，输出链表长度
        //printf("%d\n",GetElem(2,L)); //取得第二项元素对应的值
        //insert_head(L,4);
        //insert_tail(L,5);
        //int x;
        //delete_head(1,x,L);//测试删除是否成功
        //reserve(L);//倒置的测试
        //sort_list(L);//排序测试
        print(L);
    }

//还要写单链表的排序

//逆置单链表

知识点

结构体的别名问题：

Node定义了一个Node型的节点对象，

PNode定义了一个指向Node型节点对象的Node型指针；

给这个指向node结构体指针类型的node定义了一个别名，

任何使用node\*的地方都可以直接用PNode代替。

因使用时可能会忘记该别名是指针类型的，易犯错，不建议使用。

**其他链表**

循环链表

与单链表的区别仅在于，判别链表中最后一个结点的条件由“后继是否为空”变为“后继是否为头结点”