数据结构--线性表

一、顺序表

常考算法大题，要求特定时间复杂度或最优性能，在不限定空间复杂度的情况下可以以空间换时间。充分利用每一次循环。

typedef struct{
    ElemType data[maxSize];
    int length;
}Sqlist;
//动态创建
typedef struct{
    ElemType *data;
    int length;
}Sqlist;

baseFunc.cpp

int insertSingle(Sqlist &L,ElemType element,int cursor){
    if(L.length>cursor-1){
        for (int i = L.length; i > cursor-1; i--) {
            L.data[i]=L.data[i-1];
        }
        L.data[cursor-1] = element;
        L.length++;
        return 1;
    }else return 0;
}

void searchElem(Sqlist &L){
    for (int i = 0; i < L.length; ++i) {
        cout <<L.data[i]<<endl;
    }
}
void initElem(Sqlist &L){
    int length;
    cout<<"请输入线性表长度：";
    cin >>length;
    L.length = length;
    for (int i = 0; i < length; ++i) {
        cout<<"请为线性表赋值：";
        cin>>L.data[i];
    }
    cout<<"done!"<<endl;
}
void deleteElem(Sqlist &L,int cursor){
    for (int i = cursor; i < L.length; ++i) {
        L.data[i-1] = L.data[i];
    }
    L.length--;
}
void rename(Sqlist &L,ElemType elem,int cursor){
    L.data[cursor-1] = elem;
}

[例1] 对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度O(1)的算法，用以删除表中元素x。

void theThirdquest(Sqlist &L,ElemType x){
    int k=0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i]==x){
            k++;
        }else{
            L.data[i-k] = L.data[i];
        }
    }
    L.length = L.length-k;

}

[例2] 有序顺序表合并

Sqlist seven(Sqlist &A,Sqlist &B){
    int i=0,j=0,k=0;
    Sqlist C;
    while (i<A.length&&j<B.length){
        if (A.data[i]<B.data[j]){
            C.data[k++] = A.data[i++];
        }else{
            C.data[k++] = B.data[j++];
        }
    }
    while (i<A.length){
        C.data[k++] = A.data[i++];
    }
    while (j<B.length){
        C.data[k++] = B.data[j++];
    }
    C.length = k;
    return C;
}

[例3] (有序+二分法) 有序表在最短时间内查找元素x。

int nine(Sqlist &L,ElemType x){
    int low = 0,high = L.length-1,mid;
    while(low<=high){
        mid = (low+high)/2;
        if (L.data[mid]==x){
            return mid;
        }
        else if(L.data[mid]>x) high = mid-1;
        else low = mid+1;
    }
}

二、单链表

一般默认具有头结点的单链表，方便操作。故考题一般要求编写不带头结点的单链表，这时困难的是删除指定元素的节点的操作

以下代码建立 带有头结点 的链表

typedef struct LNode{
    ElementType data;
    struct LNode *next;
}*LinkList;

baseFunc.cpp

LinkList initList(LinkList &L){
    L = new LNode;
    LinkList s,p;
    p = L;
    for (int i = 1; i < 5; i++) {
        s = new LNode;
        s->data = i;
        s->next = nullptr;
        p->next = s;
        p = p->next;
    }
    return p;
}
//p就相当于一个游标，其地址与L将要创建的节点的地址相同。

void insertLater(LinkList &L,ElementType x,int n){
    LinkList p,q;
    q = L;
    p = new LNode;
    p->data = x;
    for (int i = 0; i < n-1; ++i) {
        q = q->next;
    }
    p->next = q->next;
    q->next = p;
}
void deleteElem(LinkList &L,ElementType x){
    LinkList p,q;
    p = L;
    while (p){

        if (p->data == x){
            q = p->next;
            p->next = q->next;
            delete q;
        }
        p = p->next;
    }
}
void getElem(LinkList &L){
    LinkList  temp = L;
    while (temp->next) {
        temp = temp->next;
        cout<<temp->data<<endl;
    }
}