【数据结构】《大话数据结构》线性表代码总结

//线性表存储的结构代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 1000//静态链表部分的
#define MAX_SIZE 20//最大长度
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//线性表顺序存储结构
//自定义的类型 以描述返回状态值
typedef int Status;//Status是函数的类型，其值是函数结果的状态代码
typedef int ElemType;//ElemType元素的存储类型 现在ElemType定义的变量也是Int类型的
typedef struct
{
    ElemType data[MAX_SIZE];//数组存储数据元素，最大值为MAX_SIZE
    int length;//线性表当前的长度
}SqList;//SqList-顺序线性表
typedef struct//静态链表
{
    ElemType data;
    int cur;//游标为0时表示无指向
    // 游标就相当于 链式存储结构的指针域
}Component, StaticLinkList[MAXSIZE];
        //////P50创建一个叫做L的顺序存储表
Status GetElem(SqList L, int i, ElemType* e)
{
    if (L.length == 0 || i <1 || i > L.length)
    {
        return ERROR;
    }
    *e = L.data[i - 1];
    return OK;
}
//P52插入操作
//e是要插入的新元素（int）
//i插入元素的位置
//L是线性表(struct结构体)
//->访问结构体中的成员
Status ListInsert(SqList* L, int i, ElemType e)
{
    int k;
    if (L->length == MAX_SIZE)
    {
        return ERROR;//当顺序线性表已满
    }
    if (i<1 || i > L->length + 1)
    {
        return ERROR;//当 i不在范围之内时
    }
    if (i <= L->length)//若插入的数据位置不在表尾时
    {
        for (k = L->length - 1; k >= i - 1; k--)
        {
            //将要插入位置后元素数据向后移动一位
            L->data[k + 1] = L->data[k];
        }
    }
    L->data[i - 1] = e;//将新元素插入
    L->length++;//增加元素后长度+1、
    return OK;
}
//删除操作p53
Status ListDelet(SqList* L, int i, ElemType* e)
{
    int k;
    if (L->length == 0)//如果表为空
    {
        return ERROR;
    }
    if (i < 1 || i > L->length)//如果删除位置不正确
    {
        return ERROR;
    }
    if (i < L->length)//如果要删除的不是最后一个元素
    {
        for (k = i; k < L->length; k++)//将要删除元素后面的元素位置往前移动1位
        {
            L->data[k - 1] = L->data[k];
        }
    L->length--;
    return OK;
    }
}
//线性表的链式存储结构
//线性表的单链表存储结构
//Node-结点
typedef struct Node
{
    ElemType data;
    struct Node* next;
}Node;
typedef struct Node* LinkList;//定义LinkList(结点)
//单链表的读取
Status GetElem(LinkList L, int i, ElemType* e)
{
int j;//定义一个j做计数器
LinkList p;//声明一结点p
p = L->next;//让p指向链表L的第一个结点
j = 1;//计数器
while (p && j < i)//当p不为空或者计数器j还没有等于i的时候，循环继续
{
    p = p->next;//让p指向下一结点
    ++j;
}
if (!p || j > i)//!---非
{
    return ERROR;//第i个元素不存在
}
*e = p->data;//取第i个元素的数据
return OK;
}
//单链表的插入
Status ListInsert(LinkList* L, int i, ElemType e)
{
    int j;
    LinkList p, s;
    p = *L;
    j = 1;
    while (p && j < i)//寻找第i个结点
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
    {
        return ERROR;//第i个元素不存在
    }
    s = (LinkList)malloc(sizeof(Node));//生成新结点
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;//将s插入到p的后面，p原来的指针域存放到了s的指针域内
    //将s赋值给p的后继
    p->next = s;
    return OK;
}
//单链表的删除
Status ListDelete(LinkList* L, int i, ElemType* e)
{
    int j;
    LinkList p, q;
    p = *L;
    j = 1;
    while (p->next && j < i)//遍历寻找第i个元素
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i)
    {
        return ERROR;//第i个元素不存在
    }
    q = p->next;
    p->next = q->next;//将q的后继赋值给p的后继
    *e = q->data;//将q结点中的数据给e
    free(q);//释放内存
    return OK;
}
//单链表的整表创建
//头插法
void CreateListHead(LinkList* L, int n)
{
    LinkList p;//结点
    int i;//计数器
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;//建立一个带头结点的单链表
    for (i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand() % 100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;//插入到表头
    }
}
//尾插法
void CreatListTail(LinkList* L, int n)
{
    LinkList p, r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;//r为指向尾部的结点
    for (int i = 0; i < n; i++)
    {
        p = (Node*)malloc(sizeof(Node));//生成新结点)
        p->data = rand() % 100 + 1;
        r->next = p;
        r = p;
    }
    r->next = NULL;//表示当前链表结束
}
//单链表的整表删除
//就是在内存把他释放了
//将L重置为空表

Status ClearList(LinkList* L)
{
    LinkList p, q;
    p = (*L)->next;//p指向第一个结点
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}
//线性表的静态链表存储结构
//静态链表的初始化
//将一维数组space中各分量链成一条备用链表
Status InitList(StaticLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE - 1; i++)
    {
        space[i].cur = i + 1;
    }
    space[MAXSIZE - 1].cur = 0;//目前静态链表为空，最后一个元素的cur为0
    return OK;
}
//静态链表的插入
//把未被使用过的及已被删除的分量用游标链成一个备用的链表
//若备用空间链表非空，则返回分配的结点下标，否则返回0
//就是自定义实现malloc函数
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;//当前数组一个元素的cur值
                        //就是第一个备用空间的下标
    if (space[0].cur)
    {
        //由于要拿出一个分量来使用，所以我们就得把它的下一个分量用来做备用
        space[0].cur = space[i].cur;
    }
    return i;
}
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j, k, l;
    k = MAX_SIZE - 1;//k是最后一个元素的下标
    if (i < 1 || i > ListLength(L) + 1)
    {
        return ERROR;
    }
    j = Malloc_SLL(L);//获得空闲分量的下标
    if (j)
    {
        L[j].data = e;//将数组赋值给此分量的data
        for (l = 1; l <= i - 1; l++)///找到第i个元素之前的位置
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;//把第i个元素之前的cur赋值给新元素的cur
        L[k].cur = j;//把新元素的下标赋值给第i个元素之前的元素cur
        return OK;
    }
    return ERROR;
}
//静态链表的删除操作
//自定义一个free来释放内存
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if(i < i || i> i > ListLength(L);
    {
        return ERROR;
    }
    k = MAXSIZE -1;
    for(j = 1; j <= i -1 ;j++)
    {
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    return OK;
}
//将下标为k的空闲结点回收到备用链表
void Free_SSL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur;//把第一个元素cur值赋给要删除的分量cur
    space[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur
}
//上面未定义的报错的ListLength
//返回L中的数据元素个数
int ListLengt(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while (i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}
//双向链表
typedef struct DulNode
{
    ElemType data;
    struct DulNode* prior;//直接前驱指针
    struct DulNode* next;//直接后继指针
}DulNode,*DuLinkList;

int main(void)
{

    return 0;
}

总结