一、顺序表

自定义:

#define MaxSize 10
typedef int ElemType;

1、静态分配

1)定义:

typedef struct {
    ElemType data[MaxSize];
    int len;
}SqList;

2)初始化顺序表:

void InitList(SqList& L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;
    }
    L.len = 0;
}

3)插入数据:

bool ListInsert(SqList& L, int i, ElemType e) {
    if (L.len + 1 >= MaxSize || i<1 || i > L.len+1) {
        return false;
    }
    for (int j = L.len; j >= i; j--) {
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.len++;
    return true;
}

4)删除:

bool ListDelete(SqList& L, int i, ElemType& e) {
    if (i < 1 || i > L.len) {
        return false;
    }
    e = L.data[i - 1];
    for (int j = i; j < L.len; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.len--;
    return true;
}

5)查找:

  • 按值查找:
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.len; i++) {
        if (L.data[i] == e) {
            return i + 1; //返回的是该元素的位序
        }
    }
    return 0;
}
  • 按位查找:
ElemType GetElem(SqList L, int i) { //i是位序
    if (i > L.len || i < 0) {
        return (ElemType)0;
    }
    return L.data[i - 1];
}

2、动态分配

自定义:

#define InitSize 10
typedef int ElemType;

1)定义:

typedef struct {
    ElemType* data;
    int MaxSize;
    int len;
}SeqList;

2)初始化顺序表:

void InitList(SeqList& L) {
    //用malloc函数申请一片连续空间
    L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
    L.MaxSize = InitSize;
    L.len = 0;
}

3)插入数据:
因为是动态分配,当数据超过最大空间MaxSize时,需要重新申请一个更大的空间,并把数据复制到新空间上。

//动态分配,所以得再申请大一片的空间然后把数据搬过去
void ExpandList(SeqList& L, SeqList& L_temp) {
    L_temp.data = (ElemType*)malloc(L.MaxSize * 2 * sizeof(ElemType));
    L_temp.MaxSize = L.MaxSize * 2;
    L_temp.len = L.len;
    //将L的值赋给L_temp
    for (int i = 0; i < L.len; i++) {
        L_temp.data[i] = L.data[i];
    }
    free(L.data);
    L = L_temp;
    // free(L_temp.data); 这一步是错误的!!!
}
//插入
bool ListInsert(SeqList& L, int i, ElemType e) {
    if (i<1 || i > L.len + 1)
        return false;
    if (L.len + 1 >= L.MaxSize) {//扩展空间后再进行下一步
        SeqList L_temp;
        ExpandList(L, L_temp);
    }
    for (int j = L.len; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.len++;
    return true;
}

在实现ExpandList时,我犯了一个低级错误,本来认为新空间赋给L后L_temp.data需要释放掉,运行发现L也跟着释放了。因为L=L_temp后,L.data是直接指向新的空间,并不是再复制一份数据给L.data。其实是我将L_temp与新申请的空间混淆了,L_temp是一个结构体,在ExpandList运行结束后就自动释放了。

4)删除、查找
代码与静态分配一模一样!!!

二、链表

1、单链表

1) 带头结点单链表

1)定义

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next; //指向下一个结点
}LNode, *LinkList; //结点和链表

2)初始化一个单链表

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) //内存不足分配失败
        return false; 
    L->next = NULL;
    return true;
}

3)获取链表长度

int L_Length(LinkList L) {
    int count = 0;
    while (L->next != NULL)
    {
        count++;
        L = L->next;
    }
    return count;
}

4)查找

  • 按位查找
LNode* GetElem(LinkList L, int i) {
    if (i < 0)
        return NULL;
    int j = 1; //记录当前结点位置
    LNode* ergodic = L; //扫描结点到i-1的位置
    while (ergodic != NULL && j <= i) {
        ergodic = ergodic->next;
        j++;
    }
    return ergodic;
}
  • 按值查找
LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p; //找不到返回null
}

5)插入

  • 指定结点的前插操作
// 在p结点之前插入元素e
bool InsertPriorNode(LNode* p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode* temp = (LNode*)malloc(sizeof(LNode));
    if (temp == NULL)
        return false;
    //无法获取p结点之前的结点,所以使用数据的替换
    temp->data = p->data;
    p->data = e;
    temp->next = p->next;
    p->next = temp;
    return true;
}
  • 指定结点的后插操作
//在p节点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode* temp = (LNode*)malloc(sizeof(LNode));
    if (temp == NULL)
        return false;
    temp->data = e;
    temp->next = p->next;
    p->next = temp;
    return true;
}
  • 按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i<1)
        return false;
    LNode* ergodic; //遍历寻找位置为i的结点的指针
    ergodic = GetElem(L, i-1);
    if (ergodic == NULL)
        return false;
    return InsertNextNode(ergodic, e);
}

6)删除

  • 按位序删除
bool ListDelete(LinkList& L, int i, ElemType &e) {
    if (i < 1)
        return false;
    LNode* ergodic; //扫描结点到i-1的位置
    ergodic = GetElem(L, i - 1);
    if (ergodic == NULL || ergodic->next == NULL)
        return false;
    LNode* temp = ergodic->next;
    e = temp->data;
    ergodic->next = temp->next;
    free(temp);
    return true;
}
  • 指定结点删除
//未知前面区域的结点,所以使用数据的替换(当p为最后一个结点时不可用)
bool DeleteNode(LNode* p) {
    if (p == NULL)
        return false;
    LNode* temp = p->next;
    p->data = temp->data;
    p->next = temp->next;
    free(temp);
    return false;
}

7)建立单链表

  • 单链表建立——尾插法
LinkList List_TailInsert(LinkList& L) {
    int x;
    //L = (LinkList)malloc(sizeof(LNode));//建立头结点
    LNode* temp, * r = L; //r为尾指针
    scanf("%d", &x);
    while (x != 9999) {
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        r->next = temp;
        r = temp;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
  • 单链表建立——头插法
LinkList List_HeadInsert(LinkList& L) {
    LNode* temp;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        temp->next = L;
        L = temp;
        scanf("%d", &x);
    }
    return L;
}

2)不带头结点单链表

1)判断单链表是否为空

bool Empty(LinkList L) {
    if (L == NULL)
        return true;
    else
        return false;
}

2)初始化单链表

bool InitList(LinkList& L) {
    L = NULL;
    return true;
}

3)获取链表长度

int L_Length(LinkList L) {
    if (Empty(L))
        return 0;
    int count = 1;
    while (L->next != NULL)
    {
        count++;
        L = L->next;
    }
    return count;
}

4)查找

  • 按位查找
LNode* GetElem(LinkList L, int i) {
    if (i < 0)
        return NULL;
    int j = 1;//记录当前结点位置
    LNode* ergodic = L;//扫描结点到i-1的位置
    while (ergodic != NULL && j < i) {
        ergodic = ergodic->next;
        j++;
    }
    return ergodic;
}
  • 按值查找
LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L;
    while (p != NULL && p->data != e)
        p = p->next;
    return p; //找不到返回null
}

5)建立链表

  • 尾插法
LinkList List_TailInsert(LinkList& L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));//建立头结点
    scanf("%d", &x);
    L->data = x;
    L->next = NULL;
    LNode* temp, * r = L; //r为尾指针
    while (true) {
        scanf("%d", &x);
        if (x == 9999)
            break;
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        r->next = temp;
        r = temp;
    }
    r->next = NULL;
    return L;
}
  • 头插法
LinkList List_HeadInsert(LinkList& L) {
    LNode* temp;
    int x;
    scanf("%d", &x);
    L = (LinkList)malloc(sizeof(LNode));
    L->data = x;
    L->next = NULL;
    while (true) {
        scanf("%d", &x);
        if (x == 9999)
            break;
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        temp->next = L;
        L = temp;
    }
    return L;
}

3)小调试

int main(){
    LinkList L;
    InitList(L);
    List_HeadInsert(L);
    //List_TailInsert(L);

    //获取链表长度
    int len = L_Length(L);
    printf("长度为%d",len);
    //查找——按位查找
    LNode* p = GetElem(L, 2);
    //查找——按值查找
    LNode* p2 = LocateElem(L, 4);
    // 在p结点之前插入元素e
    LNode* p3 = L->next->next->next;
    InsertPriorNode(p3, 11);
    //插入——按位序插入
    ListInsert(L, 3, 12);
    //按位序删除
    ElemType e;
    ListDelete(L, 3, e);
    //指定结点删除
    LNode* p4 = L->next->next;
    DeleteNode(p4);
}

可以用此主函数断点调试,查看数据的改变过程。

2、双链表

1)定义

typedef int ElemType;
typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
}DNode, *DLinklist;

2)初始化双链表

bool InitDLinkList(DLinklist& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL)
        return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

3)判空

bool Empty(DLinklist L) {
    if (L->next == NULL)
        return true;
    else
        return false;
}

4)插入

bool InsertNextNode(DNode* p, DNode* s) {
    if (p == NULL || s == NULL)
        return false;
    s->next = p->next;
    s->prior = p;
    if (p->next != NULL)
        p->next->prior = s;
    p->next = s;
    return true;
}

5)删除

//删除p结点
bool DeleteNextNode(DNode* p) {
    if (p == NULL)
        return false;
    if (p->next != NULL) {
        p->prior->next = p->next;
        p->next->prior = p->prior;
    }
    else
    {
        p->prior->next = NULL;
    }
    free(p);
    return true;
}

3、循环链表

1)循环单链表初始化

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = L;
    return true;
}

2)循环双链表初始化

bool InitList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL)
        return false;
    L->next = L;
    L->prior = L;
    return true;
}

4、静态链表

#define MaxSize 10
typedef int ElemType;
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];
最后编辑:2022年04月15日 ©著作权归作者所有