数据结构--顺序表，单链表，循环链表C实现

- 顺序表

线性表有两种存储方式，一种是顺序存储方式，这就是顺序表。
①教材中使用一个 Status用来返回状态，表示当前的操作是否成功

#define MaxSize 20
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
typedef int Status;

②顺序表中使用一个结构体，该结构体内包含一个数组，用于顺序存放数据，还有一个用于记录当前数据的长度。使用typedef用于自己定义一个数据类型sqList

typedef struct {
    Elemtype date[MaxSize];
    int length;
}sqList;

③顺序表的初始化，就是数组的初始化，直接使用一个For循环便可

Status InitList(sqList *L,int i){
    if (i<=MaxSize){
        for(int j=0;j<i;j++){
            int temp;
            scanf("%d",&temp);
            L->date[j]=temp;
        }     
    }
    L->length=i;
    return OK;
}

④顺序表的输出，就是数组的输出

Status PrintList(sqList *L,int i){
    for(int j=0;j<i;j++){
        printf("%d",L->date[j]);
    }
    printf("\n");
    return OK;
} 

⑤获取一个数据，定义ListInsert函数，该函数传入该顺序表，sqList *L，用结构体的地址作为形参，以及传入要获取的数据位置，因为使用数组模拟，所以获取位置为i的数据直接使用数组的下标法即可，这里使用函数为了检测状态

Status ListInsert(sqList *L,int i,Elemtype e){
    if(i>L->length+1||L->length==MaxSize||i<1){
        return ERROR;
    }
    if(i<=L->length){
       for(int j=L->length-1;j>=i-1;j--){
           L->date[j+1]=L->date[j];
       }
    }
    L->date[i-1]=e;
    L->length++;
    return OK;
}

⑥插入和删除操作，这两个操作都要移动大量元素，插入操作，先将数组的最后一个元素移动，然后依次往前移动，移动到i-1，使用赋值将要插入的元素复制给下标为i-1的数据，这是要将L->length++；删除操作现将第i个元素赋值给第i-1的元素，然后依次往下赋值，这时要将L->length–

//插入操作
Status ListInsert(sqList *L,int i,Elemtype e){
    if(i>L->length+1||L->length==MaxSize||i<1){
        return ERROR;
    }
    if(i<=L->length){
       for(int j=L->length-1;j>=i-1;j--){
           L->date[j+1]=L->date[j];
       }
    }
    L->date[i-1]=e;
    L->length++;
    return OK;
}
//删除操作
Status ListDelete(sqList *L,int i){
    if (L->length==0){
        return ERROR;
    }
    
    if(i<=L->length-1){
        for(int j=i-1;j<L->length;j++){
            L->date[j]=L->date[j+1];
        }
    }
    L->length--;
    return OK;
}

- 单链表（链式存储）

①链表结构体的准备：这里使用typedef ，便可直接用link定义一个链表

typedef struct Link{
    int date;
    struct Link *next;
}link;

②创建链表：创建链表可以有两种方法，头插法，尾插法；
头插法指的是新节点永远处在第一位下面的事头插法，先创建一个临时节点a，输入 a->date，然后类似与链表的插入操作，

link* InitLIst(){
    link *head=(link*)malloc(sizeof(link)); //建立头指针
    head->next=NULL;
    link *temp=head;                        //建立一个指针用于遍历链表
    for(int i=1;i<=5;i++){                  //尾插法
        link *a=(link*)malloc(sizeof(link));
        int num;
        scanf("%d",&num);
        /*头插法
        *a->naxt=temp->next;
        *temp->next=a;
        */
        a->date=num;
        temp->next=a;       //尾插法中temp永远都指向最后一个节点
        temp=a;             //将当前节点设置为最后一个节点
    }
    temp->next=NULL;        //表示当前链表结束
    return head;
}

③获取链表的一个元素

Status GetElem(link *L,int i,Elemtype *e){
    int j=1;
    link *temp;         //遍历整个链表的指针
    temp=L->next;       //由于有头结点
    //使用while查找需要的节点i,此时的temp就是第i个节点
    while(temp&&j<i){
        temp=temp->next;
        ++j;
    }
    //是否有该节点
    if(!temp||j>i){
        return ERROR;
    }
    //返回该节点的元素
    *e=temp->date;
    return OK;
}

④插入，使用链式存储的最大优点便是插入和删除操作快，插入算法类似于头插法，p为要插入的节点，i为插入第i个节点

Status ListInsert(link *L,int i){
    int j=1;            //当j<i-1时就遍历链表，这是的插入插入的是及节点的前面
    link *temp,*s;      //temp指向当前节点
    s=(link*)malloc(sizeof(link));  //为s开辟空间
    scanf("%d",&s->date);
    s->next=NULL;
    temp=L->next;                   //temp指向第一个节点
    //查找第i-1个节点
    while(temp&&j<i-1){
        temp=temp->next;
        ++j;
    }
    if(!temp||j>i){
        return ERROR;
    }
    //插入核心算法，先让s节点与temp->next链接，再temp->next与s链接
    s->next=temp->next;
    temp->next=s;
    return OK;
}

⑤删除操作，要删除一个节点q其实就是讲q的前继节点跳过，指向q的后继节点即可，

Status ListDelect(link *L,int i,Elemtype *e){
    int j=1;
    link *temp,*q;
    temp=L->next;
    while(temp->next&&j<i-1){
        temp=temp->next;
        ++j;
    }
    //删除的是temp->next节点，只要将temp->next=temp->next->next即可
    q=temp->next;
    temp->next=q->next;
    *e=q->next;
    return OK;
}

⑥输出整个链表

Status Print(link *L,int n){
    link *temp;
    int j=1;
    temp=L->next;
    while(temp&&j<=n){
        printf("%d",temp->date);
        temp=temp->next;
    }
}

⑦删除整个单链表，删除单链表时，与输出链表大同小异，但是这时候要引入中间指针变量q，为啥不直接free(temp)呢，因为temp是含有指针域和数据域的，一下free直接把指针域给free掉，这时候就没法寻找下一个节点的位置了，所以引入一个中间变量储存起来，然后在释放掉，这样讲能寻找到下一个节点的地址

Status ClearList(link *L){
    link *temp,*q;
    int j=1;
    temp=L->next;
    while(temp){
        q=temp->next;
        free(temp);
        temp=q;
    }
    L->next=NULL;
    return OK;
}

转载：https://blog.csdn.net/weixin_44706647/article/details/101159904