线性表

线性表

一、顺序表

（一）、定义

typedef struct {
    int data[max];
    int length;
}Sqlist;

（二）、常见的操作

1、按位置查找

int findElem(Sqlist L,int x){
    int i;
    for(i = 0 ;i < L.length;++i){ #从小到大进行判断
        if(x < L.data.[i]){ # x小于,返回当前的i
            return i;
        }
    }
    return i; #如果x都不小于，x插入表尾
}

2、插入

void insertElem(Sqlist &L,int x){
    int i,p;
    p = findElem(L,x);
    for(i = L.length;i >= p;--i){
        L.data[i+1] = L.data[i];
    }
    L.data[p] = x;
    ++L.length;
}

3、按元素查找

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

4、插入

int insertElem(Sqlist &L,int p,int e){
    int i;
    if(p < 0 || p > L.length || L.length == max ){
    return 0;
    }
    for(i = L.length;i >= p; --i){
        L.data[i+1] = L.data[i]; //依次移动元素的位置
    }
    L.data[p] = e;
    ++(L.length); //表长加1,
    return 1;
}

5、删除

int deleteElem(Sqlist &L,int p,int &e){//需要改变的变量用引用型
    int i;
    if(p < 0 || p > L.length)
        return 0;
    e = L.data[p]; //将删除元素的值赋值给e
    for(i = p;i < L.length; ++i){
        L.data[i] = L.data[i+1]; //前移一位
    }
    --L.length;
    return 1;
}

二、单链表

（一）、定义

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;

（二）、常见的操作

1、尾插法

void createlistH(LNode *&L,int a[],int n){
    LNode *s,*r;
    int i = 0;
    L = (LNode*)malloc(sizeof(LNode));
    L->next =NULL;
    r = L;
    for( i = 0; i< n; ++i){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        r->next = s;
        r = r->next;
    }
    r->next = NULL;
}

2、头插法

void createlsitF(LNode *&L;,int a[],int n){
    LNOde *s;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    for(i = 0;i<n;++i){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L-next;
        L->next = s;
    }
}

3、查找与删除

int findAndDel(LNOde *L,int x){
    LNode *q,*p;
    p=L;
    //查找
    while(p->next != NULL){
        if(p->next->data == x){
            break;
        }
        p = p -> next;
    }
    // 删除
    if(p->next = NULL){
        return 0;
    }else{
        q = p->next;
        p->next = p->next->next;
        free(q);
        return 1;
    }
}

三、双链表

（一）、定义

typedef struct DLNode{
    int data;
    struct DLNode *prior;
    struct DLNode *next;
}DLNode;

（二）、常见的操作

1、尾插法

void createDlistR(DLNode *&L,int a[],int n){
    LNode *s,*r;
    L = (LNode*)malloc(sizeof(LNode));
    L->prior = NULL;
    L->next = NULL;
    r = L;
    for(int i = 0;i < n;i++){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        r->next = s;
        s->prior = r;
        r = s;
    }
    r->next = NULL;
}

2、头插法

void createDlistF(DLNode *&L,int a[],int n){
    DLNode *s,*r;
    L = (DLNode*)malloc(sizeof(DLNode));
    L->prior = NULL;
    L->next = NULL;
    r = L;
    for(int i = 0;i < n;i++){
        s = (DLNode*)malloc(sizeof(DLNode));
        s->data = a[i];
        s->next = r;
        r->prior = s;
        r = s;
    }
}

3、查找

int findElem(DLNode *L,int x){
    DLNode *p = L->next;
    while(p != NULL){
        if(p->data == x)
            break;
        p = p->next;
    }
    return p;
}

4、插入

p结点后插入结点s。

s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;

5、删除

删除p结点的后继结点（s）

s = p->next;
p->next = s->next;
s->next->prior = p;
free(s);