c语言实现线性表的建立，初始化，插入，删除，查找，遍历以及时间复杂度分析

清疚 2022-06-10 14:15 246阅读 0赞

**c语言实现线性表的建立，初始化，插入，删除，查找，遍历以及时间复杂度分析**

顺序表的特点是元素的逻辑顺序与物理顺序相同  
顺序表结构：

#include <stdio.h>
    #define InitSize 100
    typedef int ElemType;
    
    typedef struct{
        ElemType * data;
        int MaxSize , length;
    }SeqList;
    
    int InitList(SeqList *L); //顺序表初始化
    int ListInsert(SeqList *L, int i, ElemType e);
    int ListDelete(SeqList *L, int i, ElemType *e);
    int LocateElem(SeqList L, ElemType e);//查找顺序表中第一个等于e的元素的位置

**顺序表初始化**

int InitList(SeqList *L){
        L->data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
        if(!L->data) return -1;
        L->length = 0;
        L->MaxSize = 50;
        return 1;
    }

**顺序表插入**  
**算法就是先后移，然后进行插入**

int ListInsert(SeqList *L, int i, ElemType e){
        if(i < 1 || i > L->length+1) return -1;
        if(L->length > L->MaxSize) return -1;
        for(int j = L->length ; j >= i ; j--)
            L->data[j] = L->data[j-1];
        L->data[i-1] = e;
        L->length++;
        return 1;
    }

**插入的时间复杂度的分析：**  
最好情况下不进行移动O(1)  
最坏的情况下移动n次，O(n)  
平均情况下，插入第i个位置要移动n+1-i次，根据全概率公式求和有平均时间复杂度O(n)

**顺序表删除**  
**先保存元素的值，然后再进行向前移动**

int ListDelete(SeqList *L, int i, ElemType *e){
        if(i < 1 || i > L->length+1) return -1;
        *e = L->data[i-1];
        for(int j = i; j < L->length; j++)
            L->data[j-1] = L->data[j];
        L->length--;
        return 1;
    }

**删除的时间复杂度的分析：**  
最好情况下不进行移动O(1)  
最坏的情况下移动n-1次，除了第一个，其余的都要移动，O(n)  
平均情况下，删除第i个位置要移动n-i次，根据全概率公式求和有平均时间复杂度O(n)

**注意保存e的值：\*e = data\[i-1\];**  
e是int\*类型的，也就是指针类型  
如果是e=data\[i-1\]则，e指向这个地址，而不是值  
\*e表示指针指向的内存地址中存放的内容  
&e表示取指针e的地址，&在c语言里面是取地址的符号，在c++里面才是引用。

**查找顺序表中第一个等于e的元素的位置**

int LocateElem(SeqList L, ElemType e){
        int i;
        for(i = 0; i < L.length; i++){
            if(L.data[i] == e)
                return i+1;
        }
        return -1;
    }