线性表单向循环链表C语音实现

实现要点

记录头尾节点和长度，以空间换时间，减少getLength()和add()尾插等方法的时间复杂度。

typedef int ElementType;
typedef int Result;

typedef struct Node{
    ElementType data;
    struct Node *next;
} SNode;

//记录头尾节点和长度，以空间换时间，减少getLength()和add尾插的时间复杂度
typedef struct {
    SNode *lastNode;
    int length;
    SNode *headerNode;
}mylinkList;


//1.1 线性表初始化
Result initlist(mylinkList* l){
    l->headerNode = NULL;
    l->lastNode = NULL;
    l->length = 0;
    return 1;
}

//1.2 线性表的插入, 插入下标前，下标从0开始非1
Result insert(mylinkList* l,int insertIndex, ElementType e){
    //这里insertIndex = getListCount(l)，就当是add兼容一下。
    if (insertIndex<0 || insertIndex > getListCount(l)) {
        //下标非法
        return 0;
    }
    //初始化插入前面的节点为lastNode
    SNode *preInsertNode = l->lastNode;
    //初始化插入的游标，然后移动至要插入的下标
    int index = 0;
    while (index<insertIndex) {
        preInsertNode = preInsertNode->next;
        index++;
    }
    //创建新节点
    SNode *newNode = (SNode*)malloc(sizeof(SNode));
    newNode->data = e;
    if (preInsertNode == NULL ) {
        //还没有首元节点
        //设置首元节点
        l->headerNode = newNode;
        newNode ->next = newNode;
    }else {
        newNode->next = preInsertNode->next;
        preInsertNode->next = newNode;
        //如果插入的是首元节点位置，重新赋值首元节点
        if ( insertIndex == 0) {
            l->headerNode = newNode;
        }
    }
    //设置尾节点
    if (insertIndex == getListCount(l)) {
        l->lastNode = newNode;
    }
    //长度++
    l->length++;
    return 1;
}

//1.2.2 线性表尾插，add最后
Result add(mylinkList* l, ElementType e){
    SNode *lastNode = l->lastNode;
    SNode *newNode = (SNode*)malloc(sizeof(SNode));
    if (newNode) {
        printf("分配内存失败");
        return 0;
    }
    newNode->data = e;
    lastNode->next = newNode;
    newNode->next = l->headerNode;
    l->length++;
    l->lastNode = newNode;
    return 1;
}

//1.3 线性表的取值,index从0开始
Result getElement(mylinkList *l,int getIndex, ElementType *e){
    if (getIndex<0 || getIndex>getListCount(l)-1) {
        //下标非法
        return 0;
    }
    SNode *headNode = l->headerNode;
    SNode *pNode = headNode;
    int index = 0;
    while (index<getIndex) {
        pNode = pNode->next;
        index++;
    }
    *e = pNode->data;
    return 1;
}

//1.4 顺序表删除
Result deleteElement(mylinkList *l,int index){
    if (index<0 || index> getListCount(l)-1) {
        //下标非法
        return 0;
    }
    SNode *preDeleteNode = l->lastNode;
    int deleteIndex = 0;
    while (deleteIndex<index) {
        preDeleteNode = preDeleteNode->next;
        deleteIndex++;
    }
    SNode *delete = preDeleteNode->next;
    //如果删除的是首元节点，则重新复制首元节点
    if (delete == l->headerNode) {
        l->headerNode = delete ->next;
    }
    //如果删除的尾节点，则重新赋值尾节点
    if (delete == l->lastNode){
        l->lastNode = preDeleteNode;
    }
    preDeleteNode->next = delete->next;
    free(delete);
    l->length--;
    return 1;
}

//1.5 清空顺序表
Result clearList(mylinkList *l){
    SNode *headNode = l->headerNode;
    SNode *freeNode = headNode;
    do {
        SNode *temp = freeNode;
        freeNode = freeNode->next;
        free(temp);
    } while (freeNode != l->lastNode);
    l->length = 0;
    return 1;
}

//1.6 判断顺序表清空
Result isEmpty(mylinkList *l){
    if (l->length == 0) {
        return 1;
    }else {
        return 0;
    }
}

//1.7 获取顺序表长度ListEmpty元素个数 */
int getListCount(mylinkList *l){
    return l->length;
}

//1.8 顺序输出List
Result traverseList(mylinkList *l){
    if (getListCount(l) == 0) {
        return 0;
    }
    SNode *pNode = l->headerNode;
    do {
        printf("%d \n",pNode->data);
        pNode = pNode->next;
    } while (pNode != l->lastNode);
    printf("%d \n",l->lastNode->data);
    return 1;
}

int main(int argc, const char * argv[]) {
   
}