线性表：顺序表和链表

---

• 顺序表（数组）优缺点

优：
    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...