UESTC数据结构线性表总结提高

数据结构课程的自我复习顺带练练手敲敲代码，有兴趣的可以点进来康康嗷！

---

关于线性表的一些题目：

如何删除一个顺序表中的所有特定元素（时间复杂度为n,空间复杂度为1）:

> 首先的想法一个个找，但是顺序表的时间耗费主要在移动元素的过程中，可否不通过每次移动元素的方式来实现呢？

结论是可以的，利用同一个顺序表，设置两个位置的指针来对元素进行再操作即可，不用新的任何的东西。(前面遍历过的表可以被现有的数据覆盖形成新的表)

void delx(SeqList *L,ElemType x){
    i = 0; j = 0
    while(i<=L->last){
        if(L->elem[i]!=x){L->elem[j]=L->elem[i];i++;j++}
        else i++;
    }
    L->last = j-1;
}

逆置带头结点的单链表:

>利用头插法和尾插法的特点是可以进行实现的。

void ReverList(LinkList L){
    p = L->next;
    L->next = NULL //新的表的表头沿用之前表的表头，p设置好位置之后只需要对于元素进行重新插入
    while(p!=NULL){
        q = p->next;         //q相当于保留了p的下一个结点，此时由于q的存在，使得原链表的后续部分不会丢失，因此可以操作p
        p->next = L->next;   //相当于头插法
        L->next = p;
        p = q;               //p任务完成，把q给p，相当于p后移，继续进行插入操作
    }
}

以第一个元素大小为标准，小的放左边，大的放在右边:

void changeList(LinkList L){
    if(L->next==NULL) return ERROR;
    p1 = L->next;
    pre = p1;              //保留遍历结点之前的结点，回溯很困难，如果删掉对应的p结点的话，链表就连不起来了。
    p = p1->next;
    while(p){
        //比p小的移到左边，比p大的不做处理
        if(p->data>=p1->data){
            pre = p;
            p = p->next;
        }
        else{
            pre->next = p->next;
            p->next = L->next;
            L->next = p;
            p = pre->next;
        }
    }
}

将二进制数字用线性链表储存:

操作规则：

1.储存：第一个结点存最高位，依次储存，最后一个结点储存二进制数字的最低位。
2.加法规则：从低到高找到第一个值为0的位置，从该位开始，对于所有低位求反运算。（这个是核心，注意一下嗷！）
3.实现：高位往低位运算的方向正好反过来，找出最后一个位为0的结点，其赋值为1，其后的1，全部赋值为0.
4.特殊情况：全部都是1的时候，这时候加法就应该，申请一个新的结点（头插法），值赋予1，其余后面各位赋值为0；

void BinAdd(LinkList L){
    Node *p,*r;     //用于找最后一个值为0的结点
    Node *s;        //s用于分配新的结点
    q = l->next;
    r = l;
    while(q!=NULL){
        if(q->data==0)
            r = q;
        q = q->next;
    }
    if(r!=l)
        r->data = 1;
    else{
        s = (Node*)malloc(sizeof(Node));
        s->data = 1;
        s->next = L->next;
        L->next = s;
        r = s;
    }
    r = r->next;
    while(r!=NULL){
        r->data = 0;
        r = r->next;
    }
}

其余线性表知识:

//线性表的顺序存储：
//在顺序表中查找是否存在对应元素
int Locate(SeqList L, ElemType e)
{
    int i = 0;
    while (i <= L.last)
    {
        if (L.elem[i] == e)
        {
            return i;
        }
        i++;
    }

    return -1;
}

//顺序表的插入操作
int InsList(SeqList *L, int i, ElemType e)
{
    int k;
    if (L->last == MAXSIZE - 1)
        return false;
    if (i < 1 || i > L->last + 2)
        return false;

    for (k = L->last; k >= i - 1; k--)
    {
        L->elem[k + 1] = L->elem[k];
    }
    L->elem[i - 1] = e;
    return true;
}

//顺序表的删除操作
int DelList(SeqList *L, int i, ElemType e)
{
    if (L->last == 0)
    {
        printf("表中没有元素，无法删除。");
        return false;
    }

    if (i - 1 < 0 || i - 1 > L->last)
        return false;

    for (int k = i; k <= L->last; k++)
    {
        L->elem[k - 1] = L->elem[k];
    }
    L->last--;
    return true;
}

//线性表的合并运算
void mergeList(SeqList *LA, SeqList *LB, SeqList *LC)