单链表

作者: sooxie | 来源:发表于2018-08-15 16:52 被阅读0次

单链表 C++
线性表：顺序表和链表
单向链表算法
链表基本操作
25_静态单链表的实现
线性表的链式存储-单链表
Algorithm小白入门 -- 单链表
单链表反转
JavaScript数据结构2——单链表
链表

链式存储结构的特点

优点：

存储空间动态分配，可以根据实际需要使用。
不需要地址连续的存储空间。
插入/删除操作只须通过修改指针实现,不必移动数据元素，操作的时间效率较高。

缺点：

每个链结点需要设置指针域(存储密度小)。
是一种非随机存储结构，查找、定位等操作要通过顺序扫描链表实现，时间效率较低。

三、单链表表的基本操作

1. 定义

//typedef struct {
//    int Num;
//    char Name[10];
//    int Age;
//}ElemType;

typedef int ElemType;

typedef struct node {
    ElemType data;
    struct node *link;
}LNode,*LinkList;

2. 创建

void READ(int &a) {
    a = rand()%30;
}

//建立一个长度为n的线性链表, 时间复杂度O(n)
LinkList CREATE(int n) {
    //r指向新创建的节点
    LinkList p,r = NULL,list=NULL;
    for (int i=1; i<=n; i++) {
        //读取一个数据
        ElemType a;
        READ(a);
        p = (LinkList)malloc(sizeof(LNode));
        p->data = a;
        p->link = NULL;
        if (list == NULL) {
            //list指向头部
            list = p;
        }else {
            r->link = p;  /* 将新结点链接在链表尾部 */
        }
        //初始时r指向头部，一直往后移动
        r = p;
    }
    return list;
}

3. 销毁一个线性链表

//销毁一个线性链表
void DELETELIST(LinkList &list) {
    LinkList p = list;
    while (p != NULL) {
        list = p->link; //保存下一个链节点位置
        free(p);        //删除并释放当前节点
        p = list;       //下一个链节点成为当前节点
    }
}

4. 线性链表的长度

// 1.求线性链表的长度,时间复杂度O(n)
int LENGTH(LinkList list) {
    LinkList p = list;
    int n = 0;   /*链表的长度置初值0 */
    while (p != NULL) {
        p = p->link;
        n++;
    }
    return n;    /*返回链表的长度n */
};

//递归算法 递归算法的时 间效率通常比非递归算法要低
int LENGTH1(LinkList list) {
    if (list != NULL) {
        return 1 + LENGTH1(list->link);
    }
    return 0;
}

5.逆转一个线性链表

void INVERT(LinkList &list) {
    //辅助指针
    LinkList r,p = list,q = NULL;
    // r | q | p
    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    list = q;
}

6.头插法

//在非空线性链表的第一个结点前插入一个数据信息为item的新结点,时间复杂度O(1)  头插法
//传递的是引用&list，为list的地址，而不是值，新链节点指向地址时才能正确插入 ,不使用引用，list为中间变量，list=p，只是修改了中间变量的指向，而原链表指针没改变
void INSERTLINK1(LinkList &list,ElemType item) {
    /* list指向链表第一个链结点 */
    //创建节点
    LinkList p = (LinkList)malloc(sizeof(LNode));
    p->data = item;     /* 将item送新结点数据域 */
    p->link = list;     /* 将list送新结点指针域 */
    list = p;           /* 修改指针list的指向 */
}

7.尾插法

//非空链表的末尾插入一个节点
void INSERTLINK2(LinkList &list,ElemType item) {
    LinkList p,r;
    r = list;
    while (r->link != NULL) {
        r = r->link;
    }
    p = (LinkList)malloc(sizeof(LNode));
    p->data = item;
    p->link = NULL;
    r->link = p;
}

8.q指的链结点之后插入

//在线性链表中由指针q指的链结点之后插入一个数据信息为item 的链结点,时间复杂度O(1)
void INSERTLINK3(LinkList &list,LinkList q,ElemType item) {
    //创建节点
    LinkList p = (LinkList)malloc(sizeof(LNode));
    p->data = item;
    if (list == NULL) {
        list = p;
        p->link = NULL;
    }else {
        p->link = q->link;
        q->link = p;
    }
}

9.第i(i>0)个结点后面插入

//在线性链表中第i(i>0)个结点后面插入一个数据信息为item的新结点,时间复杂度O(n)
void INSERTLINK4(LinkList &list,int i,ElemType item) {
    LinkList q = list;
    //执行i-1次，q = q->link,移动q的指向
    int j;
    for (j = 1; j <= i-1; j++) {
        q = q->link;
    }
    LinkList p = (LinkList)malloc(sizeof(LNode));
    p->data = item;
    p->link = q->link;
    q->link = p;
}

10.按值有序，假设非递减，插入一个信息为item的节点

void INSERTLINK5(LinkList &list,ElemType item) {
   
    LinkList p,q,r = NULL;
    p = (LinkList)malloc(sizeof(LNode));
    p->data = item;
    //检查是否为空或者和第一个节点比较
    if (list == NULL || item < list->data) {
        p->link = list;
        list = p;
    }else {
        q = list;
        while (q != NULL && item >= q->data) {
            r = q;
            q = q->link;
        }
        p->link = q;
        r->link = p;
    }
}

11.利用线性链表对数组进行排序

void LINKSORT(ElemType A[],int n) {
    LinkList p,list = NULL;
    int i;
    for (i = 0; i < n; i++) {
        INSERTLINK5(list, A[i]);
    }
    p = list;
    i = 0;
    while (p != NULL) {
        A[i++] = p->data;
        p = p->link;
    }
}