总结第一章线性表

typedef int ElemTyp；
typedef struct {
    ElemType *elem; 
    int length; 
    int listsize; 
} SqList;

Status InitList(SqList &L){
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));//（ElemType*)是强制转换，这个就是便成为同一类型，malloc就是创建的函数需要stdlib，里面是计算需要分配多少个空间，初始空间乘一个空间的大小。
    if(!L.elem){
        printf("初始化失败");
        exit(OVERFLOW);
    }
    L.length = 0;//表长一开始就是0
    L.listsize = LIST_INIT_SIZE;//空表的初始空间为LIST_INIT_SIZE，这个需要在main之前声明
    return OK;
}

Status ListInsert(SqList &L, int pos, ElemType e) {
    for (int i = L.length; i >= pos; i--) {
        L.elem[i] = L.elem[i - 1];
    }
    L.elem[pos - 1] = e;
    L.length++;//一定要维护表长
    return OK;
}

Status ListDelete_Sq(SqList &L, int pos, ElemType &e)
{
    for (int i = pos; i < L.length; i++) {
        L.elem[i-1] = L.elem[i];
    }
    L.length--;
    return OK;
}//就是将后一个位置的元素覆盖到前一个位置上的元素，注意修改表长

bool Del_Min(SqList &L, ElemType &min_value){
    if(L.length == 0) return false; //表空，中止操作返回
    min_value = L.elem[0];//假定0号元素元素的值最小
    int pos = 1;//假定0号元素元素的值最小，位置为1
    for(int i=1; i 
顺序表元素逆置 
void Reverse1(SqList &L){
    SqList Lb;//构造一个辅助数组Lb
    InitList_Sq(Lb);//对Lb进行初始化
    for(int i=0; i 
#include "head.h"
void Reverse(SqList &L){
    for(int i=0; i 
删除顺序表L中所有值为x的元素 
方法1 
void del_x(SqList &L, ElemType x){
    int k=0;//用k记录等于x的元素个数
    for (int i = 0; i < L.length; ++i) {
        if(L.elem[i]==x) k++;
        else L.elem[i-k] = L.elem[i];
    }
    L.length -= k;
}
//确定有几个与x相等的元素设置为k，k一开始为0，用一个for循环，如果发现第1个元素与x相等，则让k自增1，这个时候将i后一个元素赋值给i-k的位置上，就可以将x覆盖掉

 
法2 
void del_x_3(SqList &L, ElemType x){
    int k = 0;//用k记录不等于x的元素个数
    for (int i = 0; i < L.length; ++i) {
        if(L.elem[i] != x){
            L.elem[k++] = L.elem[i];
        }
    }
    L.length = k;
}

 
法3 
void deleteData_1(SqList &L,int number){
    int k = 0;
    int i ;
    int length = L.length;
    for(i = 0;i 
有序顺序表删除s到t 
bool Del_s_t(SqList &L, ElemType s, ElemType t){
    int m = 0, n = 0;
    for (int i = 0; i < L.length; ++i) {
        if(L.elem[i] < s)   m++;//这个是看小于s的值有多少个
        if(L.elem[i] <= t)    n++;//这个是看小于t的值有多少个
    }
    for (int j = n; j < L.length; j++)
        L.elem[m++] = L.elem[j];//从n位置后面的元素依次赋值给m位置后面，进行一次就让m自增1.
    L.length = m;//这个就是让表长等于最后的m中间有几个元素
    return true;
}
 
顺序表（不一定有序）删除s到t 
bool Del_s_t_Sq(SqList &L, ElemType s, ElemType t){
    int i, k = 0;
    if (L.length == 0 || s >= t) return false;//判断是否健壮
    for (i = 0; i < L.length; ++i) {
        if(L.elem[i] >= s && L.elem[i] <= t)//判断元素是否在这里面，并记录有几个元素在里面设为k；
            k++;
        else
            L.elem[i-k] = L.elem[i];
            
    }
    L.length -= k;//最后一定不能忘记更改表的长度
    return true;
}
 
有序顺序表中删除值重复的元素 
bool Delete_same(SqList &L){
    if(L.length == 0) return false;
    int i,j;
    for(i=0,j=1; j 
无序顺序表删除值重复的元素 
时间复杂度小的方法 
bool Delete_same_3(SqList &L) {
    int i, j = 0, k;
    for (i = 1; i < L.length; ++i) {//i记录遍历L中的每一个元素
        k = 0;//每次循环k都从0开始
        while (k <= j && L.elem[k] != L.elem[i]) 
            k++;
        if (k > j)//表示L.elem[i]与L.elem[0..j]中的元素都不相同
            L.elem[++j] = L.elem[i];//j记录结果的下标
    }
    L.length = j + 1;
}
/*这个就是设置三个量，ijk，i的任务就是遍历表，j的任务就是确定下一个覆盖的位置，k的任务就是在循环中都是从第一个元素开始遍历，有点抽象
 
暴力解题 
void deleteData_2(SqList &L) {
    for (int i = 0; i < L.length; i++) //遍历表
    {
        for (int j = 0; j < L.length; j++) //用j找与i相等的位置
        {
            if (i == j) {}//这个防止j小于等于i
            else {
                if (L.elem[i] == L.elem[j]) {
                    if(j==L.length-1) L.length--;
                    else{
                 for (int k = j; k < L.length; ++k) {
                            L.elem[k-1] = L.elem[k];
                        }
                        L.length--;
                    }
                }
            }
        }
    }
} 	
 
合并两个有序顺序表 
bool Merge(SqList La, SqList Lb, SqList &Lc){
    Lc.listsize = La.length +Lb.length;
    Lc.length = Lc.listsize;
    Lc.elem = (ElemType *)malloc(sizeof (ElemType) * Lc.listsize);
    if(!Lc.elem) exit(OVERFLOW);

    int i=0, j=0, k=0;
    while(i