链表代码

代码

发布日期: 2020-08-26

更新日期: 2020-08-30

文章字数: 2.6k

阅读次数:

链表相关代码

1.单链表结点类型描述

typedef struct LNode{     //定义单链表结点类型
    int data;             //数据域
    struct LNode *next;   //指针域，指向下一个结点的指针
}LNode,*LinkList;         //LNode是结构体的别名，用LNode即可代替typedef struct LNode
                          //LinkList是结构体指针的别名，用LinkList指针代替struct LNode *next

2.链表创建（头插法）

每个结点插入的时间为 $O(1)$ ，设单链表长度为n，则总时间复杂度为 $O(n)$

sizeof函数计算数据（包括数组、变量、类型、结构体等）所占内存空间，用字节数表示

malloc函数用于在内存开辟了一段地址，而这段地址的首地址存在返回的那个指针变量里，由于不知道到底这段地址有多长，可以存什么变量，所以它的类型是空的，你可以强制类型转换，使其变成确定长度，固定存放一种数据类型的地址，而不管它是哪种类型，其首地址还是原来那个，还是存在一个指针变量中，指针变量就是放指针的嘛，指针是一个地址，指针变量是一个我们定义的，用来放那个地址的变量。

那么代码的意思就是说：

分配一个内存，大小是LNode的大小，并将这个内存地址转化为Linklist型，然后将赋给L，所以L为地址。是给L赋值，也就是L被改为指向malloc()新分配的地址

LinkList CreatList(LinkList &L){
    LNode *s;
    int x;                                  //待插入的数据x
    L = (LinkList)malloc(sizeof(LNode));    //创建LNode型头结点，并强制转换成LinkList类型，头结点
                                            //L是一个指针的地址，所以要转化成指针类型
    L -> next = NULL;                       //初始为空链表
    scanf("%d",x);                          //输入结点的值
    while(x!=9999){                         //输入9999表示结束
        //申请一个LNode大小的空间,得到的指针强制转换为指向Lnode类型的指针,然后赋值给s
        s = (LNode*)malloc(sizeof(LNode));  //创建新节点，这句话的作用是由系统生成一个LNode型链表
                                            //的结点，同时将该结点的起始位置赋给指针变量s
                                            //，s为LNode型的指针
        s -> data = x;                      //赋值
        s ->next = L -> next;
        L -> next = s;                      //将新结点插入表中，L为头指针，注意头插法的代码顺序
        scanf("%d",&x)                      //继续输入值
    }
    return L;
}

3.链表创建（尾插法）

每个结点插入的时间为 $O(1)$ ，设单链表长度为n，则总时间复杂度为 $O(n)$

LinkList CreatList(LinkList &L){
    int x;                                  //待插入数据
    L = (LinkList)maclloc(sizeof(LNode));   //创建头结点
    LNode *s, *r = L;                       //r为表尾指针
    scanf("%d",x);                          //输入结点的值
    while(x!=9999){
        s = (LNode*)malloc(sizeof(LNode));  //创建新结点
        s -> data = x;                      //赋值
        r -> next = s;                      //尾插法，插入的结点在尾指针的后边
        r = s;                              //尾指针r再指向新插入尾部的结点s
        scanf("%d",&x);                     //继续输入值
    }
    r -> next = NULL;                       //尾结点指针置空
    return L;
}

4.链表的排序（重点）不理解，要复习

void sort(LinkList &L){
    LNode *p = L -> next, *pre;
    LNode *r = p -> next;
    p -> next = NULL;
    p = r;
    while(p!=NULL){
        r = p -> next;
        pre = L;
        while(pre->next != NULL && pre->next->data < p->data){
            pre = pre -> next;
        }
        p -> next = pre -> next;
        pre -> next = p;
        p = r;
    }
}

5.链表的插入

将元素x插入到第n个位置上，需要先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点（链表带头结点）

bool Insert(LinkList &L,int n,int e){             //链表L引用型
    LNode *pre = L,*p = L->next;                  //LNode型pre指针指向头结点L，p指针指向next
    int i = 1;                                    //开始计数
    while(i<n && p){
        pre = p;                                  //直到到达n，找到前驱pre
        p = p -> next;
        i++
    }
    if(i == n){
        LNode *s = (LNode*)malloc(sizeof(LNode)); //新建指针s指向结点
        s -> data = e;                            //赋值为e
        s -> next = pre -> next;                  //新插入的s的后继指向pre的后继
        pre -> next = s;                          //pre的后继指向s
        return true;                              //完成插入
    }else{
        return false;
    }
}

将元素x插入到有序链表中，使其仍然有序（链表带头结点）

void Insert(LinkList &L, int e){
    LNode *pre = L,*p = L->next;
    while(p){                                     //判断p指针的数据和元素e的大小
        if(p->data < e){
            pre = p;                              //直到找到
            p = p -> next;
        }else{
            break;                                //当找到后，跳出循环
        }
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));     //分配s指针的结点
    s -> data = e;                                //插入数据
    s -> next = pre -> next;
    pre ->next = s;
}

5.链表的删除

删除链表中值为x的结点

void Del(LinkList &L,int x){
    LNode *pre = L;                   //pre指针指向头结点
    LNode *p = L -> next;             //p指针指向头结点的next
    while(p){                         //p不为空时
        if(p->data != x){             //如果没有查询到
            pre = p;                  //两个指针依次往后移
            p = p -> next;
        }else{                        //直到p指针的值与x的相同
            pre -> next = p -> next;  //删除节点
            free(p);                  //free多余的结点
            p = pre -> next;
        }
    }
    return L;
}

删除链表中最大值的结点（多加入两个确定最大值的指针即可）

LinkList Del(LinkList &L, int x){
    LNode *pre = L, *p = L -> next, *mpre = pre, *mp = p; //建立结点
    while(p){
        if(p->data > mp->data){                           //比较数据的大小
            mpre = pre;                                   //如果大于，最大值指向p
            mp = p;
        }
        pre = p;                                          //一次往后查找
        p = p -> next;
    }
    mpre -> next = mp -> next;                            //删除节点
    free(mp);
    return L;
}

删除有序链表中重复值节点

LinkList Del(LinkList &L, int x){
    LNode *pre = L, *p = L -> next;
    while(p){
        if(pre->next && pre->next->data == p->data){
            pre -> next = p -> next;
            free(p);
            p = pre -> next;
        }else{
            pre = p;
            p = p -> next;
        }
    }
    return L;
}

6. 链表的逆置

将链表L的所有结点逆置（采用头插法）

LinkList Inversion(LinkList &L){
    LNode *p = L -> next, *r;
    L -> next = NULL;
    while(p){
        r = p -> next;
        p -> next = L -> next;
        L -> next = p;
        p = r;
    }
    return L;
}

7. 链表的合并

将两个有序链表合并为一个有序链表

LinkList Merge(LinkList &L1, LinkList &L2){
    LNode *p = L1 -> next, *q = L2 -> next, *r = L1;
    L1 -> next = NULL;
    while(p && q){
        if(p->data < q->data){
            r -> next = p;
            r = p;
            p = p -> next;
        }else{
            r -> next = q;
            r = q;
            q = q -> next;
        }
    }
    return L1;
}

将两个有序链表合并为一个有序链表（取交集）

LinkList Merge(LinkList &L1, LinkList &L2){
    LNode *p = L1 -> next, *q = L2 -> next, *r = L1;
    L1 -> next = NULL;
    while(p && q){
        if(p->data < q->data){
            p = p -> next;
        }else if(p->data > q->data){
            q = q -> next;
        }else{
            r -> next = p;
            r = p;
            p = p -> next;
            q = q -> next;
        }
    }
    return L1;
}

将两个有序链表合并为一个有序链表（并集）

LinkList Merge(LinkList &L1, LinkList &L2){
    LNode *p = L1 -> next, *q = L2 -> next, *r = L1;
    L1 -> next = NULL;
    while(p && q){
        if(p->data < q->data){
            r -> next = p;
            r = p;
            p = p -> next;
        }else if(p->data > q->data){
            r -> next = p;
            r = q;
            q = q -> next;
        }else{
            r -> next = p;
            r = p;
            p = p -> next;
            q = q -> next;
        }
    }
    while(p){
        r -> next = p;
    }
    while(q){
        r -> next = q;
    }
    return L1;
}

8. 链表拆分问题

设C = {a1,b1,a2,b2,...,an,bn}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，讲其拆分为两个线性表，使得A={a1,a2,...,an},B={bn,...,b2,b1}

LinkList Merge(LinkList &L){
    LNode *p = L -> next, *r;
    int i = 1;
    LinkList A = L, *s = A;                      //尾插需要个尾指针，指向头指针
    LinkList B = (LNode*)malloc(sizeof(LNode));  //创建B表表头
    B -> next = NULL;                            //B表的初始化
    while(p){
        r = p -> next;
        if(i%2 == 1){                            //基数位时
            s -> next = p;                       //尾插法，正序
            s = p;
            p = r;
            i++;
        }else{                                   //偶数时
            p -> next = B -> next;               //头插法，因为要倒序
            B -> next = p;                      
            p = r;
            i++;
        }
    }
    s -> next =NULL;
    return A,B;

}



- 设`C = {a1,b1,a2,b2,...,an,bn}`为线性表，采用带头结点的hc单链表存放，计一个就地算法，讲其拆分为两个线性表，使得`A={a1,a2,...,an},B={b1,...,bn-1,bn}`

- 与上一题相比，只有链表B变为尾插（保证正序即可）

```c
LinkList Merge(LinkList &L){
    LNode *p = L -> next, *r;
    int i = 1;
    LinkList A = L; *s = A;
    LinkList B = (LNode*)malloc(sizeof(LNode)), *s1 = b;  //创建B表表头,并指向头指针
    while(p){
        r = p -> next;
        if(i%2 == 1){                            //基数位时
            s -> next = p;                       //尾插法，正序
            s = p;
            p = r;
            i++;
        }else{                                   //偶数时
            s1 -> next = p;                       //尾插法，正序
            s = p;
            p = r;
            i++;
        }
    }
    s -> next =NULL;
    s1 -> next =NULL;
    return A,B;
}

设C = {a1,b1,a2,b2,...,an,bn}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，讲其拆分为两个线性表，使得A={an,an-1,...,a1},B={bn,...,b2,b1}

LinkList Merge(LinkList &L){
    LNode *p = L -> next, *r;
    int i = 1;
    LinkList A = L; 
    LinkList B = (LNode*)malloc(sizeof(LNode));  //创建B表表头
    A -> next = NULL;
    A -> next = NULL;
    while(p){
        r = p -> next;
        if(i%2 == 1){                            //基数位时
            p -> next = A -> next;               //头插法，因为要倒序
            A -> next = p;                      
            p = r;
            i++;
        }else{                                   //偶数时
            p -> next = B -> next;               //头插法，因为要倒序
            B -> next = p;                      
            p = r;
            i++;
        }
    }
    return A,B;
}

9. 判断两个链表是否有相同结点（找出相同结点）

int Length(LinkList &L){  //计算链表长度
    int num = 0;
    while(L != NULL){
        num++;
        L = L -> next;
    }
    return num;
}
bool Judeg(LinkList &L1, LinkList &L2){
    int len1 = Length(L1);
    int len2 = Length(L2);
    if(len1 > len2){                   //让两个链表拥有相同的尾部长度
        int num = len1 - len2;
        for(int i = 0; i < num; i++){
            L1 = L1 -> next;
        }
    }else{
        int num = len2 - len1;
        for(int i = 0; i < num; i++){
            L2 = L2 -> next;
    }
    while(L1){
        if(L1 == L2){
            return 1;
        }
        L1 = L1 -> next;
        L2 = L2 -> next;
    }
    return 0;
}

10. 栈的基本操作

栈的顺序存储类型描述

#define Maxsize 50       //定义栈中元素的最大个数
typedef struct{
    int data[Maxsize];   //存放栈中元素
    int top;             //栈顶指针
}SqStack;

初始化

void InitStack(Sqstack &S){
    S.top = -1;               //初始化栈顶指针
}

判断栈空

bool StackEmpty(S){
    if(S.top == -1){
        return true;
    }else{
        return false;
    }
}

进栈

bool Push(SqStack &S, int x){
    if(S.top == MaxSize - 1){
        return false;
    }
    S.data[++S.top] = x;       //指针先加1，再入栈
    return true;
}

出栈

bool Pop（SqStack &S, int &x){
    if(S.top == -1){
        return false;
    }
    x = S.data[S.top--];
    return true;
}

读栈顶元素

bool GetTop(SqStack S, int &x){
    if(S.top == MaxSize - 1){
        return false;
    }
    x = S.data[S.top];
    return true;
}

小冷同学

http://www.bangbangbangbang.top/posts/d09f.html/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源小冷同学 !

代码考研链表

用户交流区

温馨提示: 遵纪守法, 友善评论!

强化计网第一章-概述

(强化)第一章绪论

2020-08-27 计网

总结考研计网强化

计网第八章-TCP/IP协议

第八章 TCP/IP协议

2020-08-23 计网

总结考研计网

链表相关代码

1.单链表结点类型描述

2.链表创建（头插法）

3.链表创建（尾插法）

4.链表的排序（重点）不理解，要复习

5.链表的插入

5.链表的删除

6. 链表的逆置

7. 链表的合并

8. 链表拆分问题

9. 判断两个链表是否有相同结点（找出相同结点）

10. 栈的基本操作

你的赏识是我前进的动力