线性表：顺序表和链表

  • 顺序表（数组）优缺点
优：
    1、用数组存储数据元素，操作方法简单，容易实现

    2、无须为表示结点间的逻辑关系而增加额外的存储开销

    3、存储密度高

    4、顺序表可按元素位序随机存取结点

缺：
    1、做插入、删除操作时，需大量移动数据元素，效率非常低
    2、要占用连续的存储空间，存储分配只能预先进行。分配过大，会导致空间浪费；分配过小将会造成数据溢出。
  • 链表优点

1、链表不用事先估计存储空间的大小，但其存储密度较低（存储密度：指一个结点中数据元素所占的存储单元数和整个结点所占的存储单元之比，顺序表的存储密度为1，链式存储密度小于1）
 
2、解决数组无法存储多种数据类型的问题。

3、解决数组中，元素个数无法改变的限制(C99的变长数组，C++也有变长数组可以实现)。

4、数组移动元素的过程中，要对元素进行大范围的移动，很耗时间，效率也不高。

单链表使用

  • 单链表结构
typedef int ElemType;

//定义结点类型
typedef struct Node
{
    ElemType data;              //单链表中的数据域
    struct Node *next;          //单链表的指针域
}Node,*LinkedList;
  • 单链表初始化
LinkedList LinkedListInit()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L == NULL)                       //判断是否有足够的内存空间
        printf("申请内存空间失败/n");
    L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表
    return L;
}
  • 单链表初始化
LinkedList LinkedListInit()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L == NULL)                       //判断是否有足够的内存空间
        printf("申请内存空间失败/n");
    L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表
    return L;
}
  • 单链表建立:
  • 头插法
LinkedList LinkedListCreatH()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
    
    ElemType x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF)
    {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}
  • 尾插法
LinkedList LinkedListCreatT()
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    
    ElemType x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF)
    {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    
    return L;
}
  • 单链表的插入（在链表的第i个位置插入x的元素）
LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)
{
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++)
        pre = pre->next;                 //查找第i个位置的前驱结点
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
    
    return L;
}
  • 单链表的删除（在链表中删除值为x的元素）
LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
    Node *p,*pre = NULL;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
    while(p->data != x)              //查找值为x的元素
    {
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
    return L;
}
  • 单链表就地反转（非递归）（利用头插法）
利用头插法.JPG
void list_reverse(LinkedList L)
{
    LinkedList p = L->next;
    L->next = NULL;
    while (p != NULL) {
        LinkedList save = p->next;
        p->next = L->next;
        L->next = p;
        p = save;
    }
}
  • 单链表就地反转（非递归）（类似于插入排序）
类似于插入排序.JPG
void list_reverse2(LinkedList head) {
    LinkedList begin = head;
    LinkedList end = head->next;
    while (end->next != NULL) {
        LinkedList save = end->next;
        end->next = save->next;
        save->next = begin->next;
        begin->next = save;
    }
}
  • 单链表就地反转（递归）
LinkedList list_reverse3(LinkedList L)
{
    if (L == NULL || L->next == NULL)       //链表为空直接返回，而H->next为空是递归基
        return L;
    LinkedList newHead = list_reverse3(L->next); //一直循环到链尾
    L->next->next = L;                       //翻转链表的指向
    L->next = NULL;                          //记得赋值NULL，防止链表错乱
    return newHead;                          //新链表头永远指向的是原链表的链尾
}
  • 合并两个有序的单链表
  • （非递归）
/*
思路：
1.第一步与递归一样，对空链表存在的情况进行处理，假如pHead1为空则返回pHead2，pHead2为空则返回pHead1。（两个都为空此情况在pHead1为空已经被拦截）
2.在两个链表无空链表的情况下确定第一个结点，比较链表1和链表2的第一个结点的值，将值小的结点保存下来为合并后的第一个结点。并且把第一个结点为最小的链表向后移动一个元素。
3.继续在剩下的元素中选择小的值，连接到第一个结点后面，并不断next将值小的结点连接到第一个结点后面，直到某一个链表为空。
4.当两个链表长度不一致时，也就是比较完成后其中一个链表为空，此时需要把另外一个链表剩下的元素都连接到第一个结点的后面。
*/

LinkedList MergeTwoOrderedLists2(LinkedList pHead1, LinkedList pHead2)
{
    LinkedList pTail = NULL;//指向新链表的最后一个结点 pTail->next去连接
    LinkedList newHead = NULL;//指向合并后链表第一个结点
    
    if (NULL == pHead1)
    {
        return pHead2;
    }
    else if(NULL == pHead2)
    {
        return pHead1;
    }
    else
    {
        //确定头指针
        if ( pHead1->data < pHead2->data)
        {
            newHead = pHead1;
            pHead1 = pHead1->next;  //指向链表的第二个结点
        }
        else
        {
            newHead = pHead2;
            pHead2 = pHead2->next;
        }
        pTail = newHead;    //指向第一个结点
        while ( pHead1 && pHead2)
        {
            if ( pHead1->data <= pHead2->data )
            {
                pTail->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                pTail->next = pHead2;
                pHead2 = pHead2->next;
            }
            pTail = pTail->next;
        }
        
        if(NULL == pHead1)
        {
            pTail->next = pHead2;
        }
        else if(NULL == pHead2)
        {
            pTail->next = pHead1;
        }
        return newHead;
    }
}
  • （递归）
/*
思路:
1.链表L1的第一个结点的值小于链表L2的第一个结点的值，因此链表1的头结点是合并后链表的头结点。
2.在剩下的结点中链表L2的第一个结点的值小于链表L1的第一个结点的值，因此将链表二的第一个结点与第一步的头结点连接。
3.然后继续在剩下的结点中重复第二、三步，直到有链表为空。
*/

LinkedList MergeTwoOrderedLists1(LinkedList pHead1, LinkedList pHead2)
{
    LinkedList newHead = NULL;
    if (NULL == pHead1)
    {
        return pHead2;
    }
    else if(NULL ==pHead2)
    {
        return pHead2;
    }
    else
    {
        if (pHead1->data < pHead2->data)
        {
            newHead = pHead1;
            newHead->next = MergeTwoOrderedLists1(pHead1->next, pHead2);
        }
        else
        {
            newHead = pHead2;
            newHead->next = MergeTwoOrderedLists1(pHead1, pHead2->next);
        }
        return newHead;
    }
}
  • 判断链表是否有环，并找出环的入口

解决思路

LinkedList EntryNodeOfLoop2(LinkedList pHead){
    LinkedList fast = pHead;
    LinkedList slow = pHead;
    while(fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;//当 快指针（每次走两步）与 慢指针（每次走一步）相遇时
        if(fast == slow) {
            fast = pHead;//再次相遇（fast和slow每次走一步）
            while(fast != slow){
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return NULL;
}
  • 单链表快速排序
单链表快速排序思路
思路：
（在算法思想上，对于单链表的快速排序和对于数组的快速排序基本一致，但是同时也存在很大的区别，导致的原因我们也很容易明白，那就是单链表不支持像数组那样的方便的访问下标，也就是说我们无法对其进行从末尾向前遍历。）

1.所以我们将第一个链表第一个结点的值作为左轴，然后向右进行遍历，设置一个small指针指向左轴的下一个元素，然后比较如果比左轴小的话，使small指针指向的数据与遍历到的数据进行交换。
2.最后将左轴元素与small指针指向的元素交换即可。
3.之后就是递归。
void quicksort(LinkedList head, LinkedList end){
    if(head == NULL || head == end)             //如果头指针为空或者链表为空，直接返回
        return ;
    int t;
    LinkedList p = head -> next;                  //用来遍历的指针
    LinkedList small = head;
    while( p != end){
        if( p -> data < head -> data){      //对于小于轴的元素放在左边
            small = small -> next;
            t = small -> data;
            small -> data = p -> data;
            p -> data = t;
        }
        p = p -> next;
    }
    t = head -> data;                           //遍历完后，对左轴元素与small指向的元素交换
    head -> data = small -> data;
    small -> data = t;
    quicksort(head, small);                     //对左右进行递归
    quicksort(small -> next, end);
}
  • 单链表从尾到头打印（用栈或递归）
//从尾到头打印链表（递归）
void printfList(LinkedList L) {
    L = L->next;//跳过头节点
    if (NULL == L->next) {
        printf("%d ",L->data);
        return;
    }
    printfList(L);
    printf("%d ",L->data);
}

and so on...

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 218,036评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,046评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,411评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,622评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,661评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,521评论 1赞 304
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,288评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,200评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,644评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,837评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,953评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,673评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,281评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,889评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,011评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,119评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,901评论 2赞 355