02、线性表

#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100
//顺序表操作注意下标的合法范围,越界与操作有没有全部包含，注意边界情况。
typedef int ElemType;
typedef struct{
    //顺序表
    ElemType *elem;
    int length;//当前表中元素长度
}SqList;

 int InitList(SqList &l){
     //顺序表的初始化
     l.elem = NULL;
     l.elem  = (ElemType*) malloc (MAXSIZE * sizeof(ElemType));
     if(l.elem == NULL) return 0;
     l.length = -1;
     return 1;
}


int ListAdd(SqList &l,ElemType x){
    //添加元素
    if(l.length >= MAXSIZE) return -1;
    l.elem[++l.length] = x;
    return 1;
}

int ListInsert(SqList &l,ElemType x,int i){
    //将元素插入在第i号位置(0 <= i <= l.length+1)
    if(l.length >= MAXSIZE) return -1;
    if(i > l.length+1 || i < 0)return -1;
    for(int j = l.length;j >= i;j--){
        l.elem[j+1] = l.elem[j];
    }
    l.elem[i] = x;
    l.length++;
    return 1;
}

int GetElem(SqList &l,int i,ElemType &e){
    //取第i号位置的元素的值
    if(i > l.length || i < 0) return -1;
    e = l.elem[i];
    return 1;
}

int ListDelete(SqList &l,int i){
    //删除第i号位置的元素(0 <= i <= l.length)
    if(i > l.length || i < 0) return -1;
    for(int j = i;j<l.length;j++)
        l.elem[j] = l.elem[j+1];
    l.length--;
    return 1;
}

int LocateList(SqList &l,ElemType x){
    //查找表中是否含有元素x，返回下标
    int i;
    for(i = 0;i <= l.length;i++)
        if(l.elem[i] == x) return i;
    return -1;
}

void PrintList(SqList &l){
    for(int i = 0;i <= l.length;i++)
        printf("%d  ",l.elem[i]);
    printf("\n");
}


int main(){
    SqList l;
    int i = InitList(l);
    ListAdd(l,0);
    ListAdd(l,1);
    ListAdd(l,2);
    //ListAdd(l,3);
    ListInsert(l,-1,1);
    i = LocateList(l,0);
    i = GetElem(l,4,i);
    printf("%d\n",i);
    PrintList(l);
    ListDelete(l,3);
    PrintList(l);

    return 0;
}

#include <stdio.h>
#include <malloc.h>
//线性表的链式存储结构

typedef int ElemType;
typedef struct Node{
    ElemType data;
    Node* next;
}List,*Lp;

typedef struct DuNode{
    //双向链表的存储结构
    ElemType data;
    DuNode* prior;  //直接前驱
    DuNode* next;   //直接后继
}DuList,*Dup;

int ListInit(Lp &l){
    //初始化，头节点没有保存数据，操作方便
    l = (Lp)malloc(sizeof(List));
    if(l == NULL) return -1;
    l->next = NULL;
    return  1;
}

int ListAdd(Lp &l,ElemType x){
    //增
    Lp p = l;
    while(p->next != NULL){
        p = p->next;
    }
    Lp t = (Lp)malloc(sizeof(List));
    if(t == NULL) return -1;
    t->data = x;
    t->next = NULL;
    p->next = t;
    return 1;
}
int ListAdd2(Lp &l,ElemType x){
    Lp t = (Lp)malloc(sizeof(List));
    if(t == NULL) return -1;
    t->data = x;
    t->next = l->next;
    l->next = t;
    return 1;
}

int ListLocate(Lp &l,ElemType x){
    //查 返回0代表未找到
    int i =  0;
    Lp t = l->next;
    while(t != NULL){
        i++;
        if(t->data == x){
            return i;
        }
        t = t->next;
    }
    return 0;
}

int  ListGet(Lp &l,int i,ElemType &e){
    //取值
    Lp p = l->next;
    for(int m = 1;m < i && p;m++ ){
        p = p->next;
    }
    if(p == NULL) return -1;
    e  = p->data;
    return 1;
}

int ListInsert(Lp &l,ElemType x,int i){
    //插入的合法下标（1 <= i <= n+1）头指针永远不能变
    Lp p = l;
    if(i < 1) return -1;
    int m = 1;
    while(p->next != NULL && m != i){
        p = p->next;
        m++;
    }
    if(m == i){
        Lp t = (Lp)malloc(sizeof(List));
        if(t == NULL) return -1;
        t->data = x;
        t->next = p->next;
        p->next = t;
        return 1;
    }
    return -1;
}

int ListDelete(Lp &l,int i){
    //删除的合法下标（1 <= n ）注意释放空间
    Lp p = l;
    if(i < 1) return -1;
    for(int m = 1;m < i && p->next;m++){
        p = p->next;
    }
    if(p->next == NULL) return -1;
    Lp q = p->next;
    p->next = q->next;
    free(q);
    return 1;
}

void ListDown(Lp &l){
    //单链表的(反转)转置
    Lp p = l->next;
    l->next = NULL;
    while(p){
        Lp q = p;
        p = p->next;
        q->next = l->next;
        l->next = q;
    }
}

void ListPrint(Lp &l){
    Lp p = l->next;
    while(p){
        int i = p->data;
        printf("%d  ",i);
        p = p->next;
    }
    printf("\n");
}

int main(){
    Lp a;
    int i,m;
    ListInit(a);
    ListAdd(a,1);
    ListPrint(a);
    ListAdd(a,2);
    ListPrint(a);
    ListAdd2(a,3);
    ListAdd2(a,4);
    ListPrint(a);
    ListInsert(a,5,1);
    ListPrint(a);
    ListDelete(a,6);
    ListPrint(a);
    return 0;
}