美文网首页
16C++ 数据结构

16C++ 数据结构

作者: 任振铭 | 来源:发表于2019-09-20 08:33 被阅读0次

    线性表顺序存储

    sqlist.h

    #pragma once
#include <stdlib.h>

typedef void SeqList;
typedef void SeqListNode;

SeqList* SeqList_Create(int capacity);

void SeqList_Destroy(SeqList* list);

void SeqList_Clear(SeqList* list);

int SeqList_Length(SeqList* list);

int SeqList_Capacity(SeqList* list);

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

SeqListNode* SeqList_Get(SeqList* list, int pos);

SeqListNode* SeqList_Delete(SeqList* list, int pos);

    sqlist.c

    #include "seqlist.h"

typedef struct _tag_SeqList {
    int length;
    int capacity;
    unsigned int* node;
}TSeqList;

SeqList* SeqList_Create(int capacity) {
    int ret = 0;
    TSeqList* list = NULL;
    list = (TSeqList*)malloc(sizeof(TSeqList));
    if (list == NULL) {
        ret = -1;
        printf("func SeqList_Create failed ret =%d\n", ret);
        return NULL;
    }
    memset(list, 0, sizeof(TSeqList));
    //根据capacity大小指定节点空间大小
    list->node = (unsigned int*)malloc(sizeof(unsigned int*) * capacity);
    if (list->node == NULL) {
        ret = -1;
        printf("list->node malloc failed ret =%d\n", ret);
        return NULL;
    }

    list->capacity = capacity;
    list->length = 0;
    return list;
}

void SeqList_Destroy(SeqList* list) {
    if (list == NULL)
    {
        return;
    }
    TSeqList* tList = list;
    if (tList->node != NULL) {
        free(tList->node);
    }
    free(tList);
    return;
}

void SeqList_Clear(SeqList* list) {
    if (list == NULL)
    {
        return;
    }
    TSeqList* tList = list;
    tList->length = 0;
    return;
}

int SeqList_Length(SeqList* list) {
    int ret = 0;
    if (list == NULL)
    {
        return ret;
    }
    TSeqList* tList = list;
    return tList->length;
}

int SeqList_Capacity(SeqList* list) {
    int ret = 0;
    if (list == NULL)
    {
        return ret;
    }
    TSeqList* tList = list;
    return tList->capacity;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) {
    int ret = 0;
    if (list == NULL || pos < 0 || node == NULL)
    {
        printf("SeqList_Insert fail ret=", ret = -1);
        return ret = -1;
    }
    TSeqList* tList = list;
    if (tList->node == NULL) {
        printf("SeqList_Insert fail tList->node = null,ret=", ret = -1);
        return ret = -1;
    }

    //判断是否容量已满
    if (tList->length == tList->capacity) {
        printf("capacity full", ret = -2);
        return ret = -2;
    }

    //判断pos正确性
    if (pos > tList->length) {
        pos = tList->length;
    }
    for (int i = tList->length; i > pos; i--) {
        //从后往前，将每一个元素后移一位，然后将插入的元素放在pos位置上
        tList->node[i] = tList->node[i - 1];
    }
    tList->node[pos] =(unsigned int*)node;
    tList->length++;
    return ret;
}

SeqListNode* SeqList_Get(SeqList* list, int pos) {
    int ret = 0;
    if (list == NULL || pos < 0)
    {
        printf("SeqList_Get fail ret=", ret = -1);
        return ret = -1;
    }
    TSeqList* tList = list;
    if (tList->node == NULL) {
        printf("SeqList_Get fail tList->node = null,ret=", ret = -1);
        return ret = -1;
    }
    return tList->node[pos];
}

SeqListNode* SeqList_Delete(SeqList* list, int pos) {
    int ret = 0;
    if (list == NULL || pos < 0)
    {
        printf("SeqList_Delete fail ret=", ret = -1);
        return ret = -1;
    }
    TSeqList* tList = list;
    if (tList->node == NULL) {
        printf("SeqList_Delete fail tList->node = null,ret=", ret = -1);
        return ret = -1;
    }

    SeqListNode* node = (SeqListNode*)tList->node[pos];

    for (int i = pos; i < tList->length+1; i++) {
        tList->node[i] = tList->node[i + 1];
    }
    tList->length--;

    return node;
}

    test.c

    #include <stdlib.h>
#include<string.h>
#include <stdio.h>
#include "seqlist.h"

typedef struct _Teacher{
    int age;
    char name[64];
}Teacher;

void main() {
    int ret = 0;
    SeqList* list = NULL;

    Teacher t1, t2, t3, t4, t5;
    t1.age = 10;
    t2.age = 20;
    t3.age = 40;
    t4.age = 50;
    t5.age = 60;

    list = SeqList_Create(10);
    if (list == NULL) {
        printf("SeqList_Create fail ret =%d", ret);
        return;
    }
    else {
        printf("Create success");
    }

    ret = SeqList_Insert(list, (SeqListNode*)&t1, 0);
    ret = SeqList_Insert(list, (SeqListNode*)&t2, 0);
    ret = SeqList_Insert(list, (SeqListNode*)&t3, 0);
    ret = SeqList_Insert(list, (SeqListNode*)&t4, 0);
    ret = SeqList_Insert(list, (SeqListNode*)&t5, 0);

    for (int i = 0; i < SeqList_Length(list); i++) {
        Teacher*temp = (Teacher*)SeqList_Get(list, i);
        if (temp == NULL) {
            return;
        }
        printf("temp->age:%d", temp->age);
    }

    SeqList_Delete(list, 0);
    for (int i = 0; i < SeqList_Length(list); i++) {
        Teacher* temp = (Teacher*)SeqList_Get(list, i);
        if (temp == NULL) {
            return;
        }
        printf("temp2->age:%d", temp->age);
    }
    system("pause");
}

    线性表链式存储

    test.c

    #include <stdlib.h>
#include<string.h>
#include <stdio.h>
#include "seqlist.h"
#include "linklist.h"

typedef struct Teacher{
    LinkListNode node;
    int age;
}Teacher;

void main() {
    LinkList* list = LinkList_Create();
    if (list == NULL) {
        printf("创建链表失败");
        return;
    }
    Teacher t1, t2, t3;
    t1.age = 10;
    t2.age = 20;
    t3.age = 30;

    LinkList_Insert(list, (LinkListNode*)& t1, 0);
    LinkList_Insert(list, (LinkListNode*)& t2, 0);
    LinkList_Insert(list, (LinkListNode*)& t3, 0);
     
    for (int i = 0; i < LinkList_Length(list); i++) {
        Teacher * node = (Teacher*)LinkList_Get(list, i);
        if (node == NULL) {
            continue;
        }
        printf("node.age = %d\n", node->age);
    }

    int length = LinkList_Length(list);
    printf("链表长度为%d\n", length);

    LinkListNode* node = LinkList_Delete(list, 0);
    for (int i = 0; i < LinkList_Length(list); i++) {
        Teacher* node = (Teacher*)LinkList_Get(list, i);
        if (node == NULL) {
            continue;
        }
        printf("node.age = %d\n", node->age);
    }

    LinkList_Destroy(list);
    system("pause");
}

    linklist.h

    #pragma once
#include <stdlib.h>

typedef void LinkList;

typedef struct _tag_LinkListNode {
    struct _tag_LinkListNode* next;
}LinkListNode;

LinkList* LinkList_Create();

void LinkList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList*list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

    linklist.c

    #include "linklist.h"

typedef struct _tag_LinkList {
    int length;
    LinkListNode header;
}TLinkList;

LinkList* LinkList_Create() {
    TLinkList* tList = (TLinkList*)malloc(sizeof(TLinkList));
    memset(tList, 0, sizeof(TLinkList));
    tList->header.next = NULL;
    tList->length = 0;
    return tList;
}

void LinkList_Destroy(LinkList* list) {
    if (list != NULL) {
        free(list);
        list = NULL;
    }
    return;
}

void LinkList_Clear(LinkList* list) {
    TLinkList* tList = NULL;
    if (list == NULL) {
        return;
    }
    tList = (TLinkList*)list;
    tList->header.next = NULL;
    tList->length = 0;
    return;
}

int LinkList_Length(LinkList* list) {
    TLinkList* tList = NULL;
    if (list == NULL) {
        return;
    }
    tList = (TLinkList*)list;
    return tList->length;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) {
    int ret = 0, i = 0;
    LinkListNode* current = NULL;
    if (list == NULL || node == NULL || pos < 0) {
        return ret = -1;
    }
    TLinkList* tList = list;
    //定义一个指针指向链表的头节点
    current = (LinkListNode*)&(tList->header);
    //将指针移动到pos位置
    for (i = 0; i < pos; i++) {
        current = current->next;
    }

    //插入节点
    node->next = current->next;
    current->next = node;
    tList->length++;
    return 0;
}

LinkListNode* LinkList_Get(LinkList* list, int pos) {
    if (list == NULL || pos < 0) {
        return NULL;
    }
    TLinkList* tList = list;
    LinkListNode* current = (LinkListNode*)&(tList->header);
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }

    return current->next;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos) {
    if (list == NULL || pos < 0) {
        return NULL;
    }
    TLinkList* tList = list;
    LinkListNode* current = &(tList->header);
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    LinkListNode* temp = current->next;
    current->next = current->next->next;
    return temp;
}

    循环单链表

    CircleList.h

    #pragma once

typedef void CircleList;

typedef struct _tag_CircleListNode {
    struct _tag_CircleListNode* next;
}CircleListNode;

CircleList* CircleListCreate();

void CircleList_Destroy(CircleList* list);

void CircleList_Clear(CircleList* list);

int CircleList_Length(CircleList* list);

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);

CircleListNode* CircleList_Get(CircleList* list,int pos);

CircleListNode* CircleList_Delete(CircleList* list, int pos);

CircleListNode* CircleList_Delete_Node(CircleList* list, CircleListNode* node);

CircleListNode* CircleList_Reset(CircleList* list);

CircleListNode* CircleList_Current(CircleList* list);

CircleListNode* CircleList_Next(CircleList* list);

    CircleList.c

    #include "CircleList.h"
#include <stdio.h>

typedef struct _tag_CircleList {
    CircleListNode header;
    CircleListNode* slider;
    int length;
}TCircleList;

CircleList* CircleListCreate() {
    TCircleList* list = (TCircleList*)malloc(sizeof(TCircleList));
    if (list == NULL) {
        return NULL;
    }
    list->header.next = NULL;
    list->slider = NULL;
    list->length = 0;
    return list;
}

void CircleList_Destroy(CircleList* list) {
    if (list == NULL) {
        return;
    }
    free(list);
}

void CircleList_Clear(CircleList* list) {
    if (list == NULL) {
        return;
    } 
    TCircleList* tList = (TCircleList*)list;
    tList->header.next = NULL;
    tList->length = 0;
    tList->slider = NULL;
    return;
}

int CircleList_Length(CircleList* list) {
    if (list == NULL) {
        return 0;
    }
    TCircleList* tList = (TCircleList*)list;
    return tList->length;
}

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) {
    
    TCircleList* tList = (TCircleList*)list;
    if (tList == NULL || node == NULL || pos<0) {
        return -1;
    }
    //CircleListNode* current = (CircleListNode*)(&(tList->header));
    CircleListNode* current = (CircleListNode*)tList;
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    node->next = current->next;
    current->next = node;

    //如果是第一次插入节点
    if (tList->length == 0)
    {
        tList->slider = node;
    }

    tList->length++;

    //如果是头插法插入，current仍然指向头部，
    if (current == (CircleListNode*)tList) {
        CircleListNode*last = CircleList_Get(tList, tList->length - 1);
        last->next = current->next;
    }
    return 0;
}

CircleListNode* CircleList_Get(CircleList* list, int pos) {
    TCircleList* tList = (TCircleList*)list;
    if (tList == NULL || pos < 0) {
        return -1;
    }
    CircleListNode* current = (CircleListNode*)(&(tList->header));
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    return current->next;
}

CircleListNode* CircleList_Delete(CircleList* list, int pos) {
    TCircleList* tList = (TCircleList*)list;
    CircleListNode* temp = NULL;
    if (tList == NULL || tList->length == 0|| pos < 0) {
        return -1;
    }
    CircleListNode* last = NULL;
    CircleListNode* current = (CircleListNode*)(&(tList->header));
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    //如果删除的是第一个元素(pos == 0)
    if (current == (CircleListNode*)tList) {
        last = (CircleListNode*)CircleList_Get(tList, tList->length - 1);
    }

    //记录要删除的元素
    temp = current->next;
    current->next = temp->next;
    tList->length--;

    //链表不为空
    if (last != NULL) {
        tList->header.next = temp->next;
        last->next = temp->next;
    }

    //如果删除的元素是游标所指的元素
    if (tList->slider = temp) {
        tList->slider = temp->next;
    }

    //如果删除后长度变为0
    if (tList->length == 0) {
        tList->header.next = NULL;
        tList->slider = NULL;
    }
    return temp;
}

CircleListNode* CircleList_Delete_Node(CircleList* list, CircleListNode* node) {

}

CircleListNode* CircleList_Reset(CircleList* list) {

    //邮标重新指向头部位置
    TCircleList* tList = (TCircleList*)list;
    CircleListNode* ret=NULL;
    if (tList == NULL) {
        return -1;
    }
    tList->slider = tList->header.next;
    ret = tList->slider;
    return ret;
}

CircleListNode* CircleList_Current(CircleList* list) {
    TCircleList* tList = (TCircleList*)list;
    if (tList == NULL) {
        return NULL;
    }
    return tList->slider;
}

//把当前位置返回并且游标下移
CircleListNode* CircleList_Next(CircleList* list) {
    TCircleList* tList = (TCircleList*)list;
    CircleListNode* ret = NULL;
    if (tList == NULL || tList->slider == NULL) {
        return NULL;
    }
    ret = tList->slider;
    tList->slider = ret->next;
    return ret;
}

    test.c

    #include <stdlib.h>
#include<string.h>
#include <stdio.h>
#include "seqlist.h"
#include "linklist.h"
#include "CircleList.h"

struct Value
{
    CircleListNode circleListNode;
    int v;
};

void main() {
    CircleList* list = CircleListCreate();
    struct Value v1;
    struct Value v2;
    struct Value v3;
    struct Value v4;
    struct Value v5;
    struct Value v6;

    v1.v = 1;
    v2.v = 2;
    v3.v = 3;
    v4.v = 4;
    v5.v = 5;
    v6.v = 6;
    printf("开始插入元素\n");
    CircleList_Insert(list, &v1,0);
    CircleList_Insert(list, &v2, 0);
    CircleList_Insert(list, &v3, 0);
    CircleList_Insert(list, &v4, 0);
    CircleList_Insert(list, &v5, 0);
    CircleList_Insert(list, &v6, 0);

    for (int i = 0; i < 2 * CircleList_Length(list); i++) {
        struct Value* v = CircleList_Get(list, i);
        printf("打印元素：%d\n", v->v);
    }

    while (CircleList_Length(list) > 0) {
        struct Value* v = CircleList_Delete(list, 0);
        printf("删除元素：%d\n", v->v);
    }

    printf("\n");

    printf("销毁\n");
    CircleList_Destroy(list);

    printf("完成\n");
    system("pause");
}


typedef struct Teacher {
    LinkListNode node;
    int age;
}Teacher;

void main2() {
    LinkList* list = LinkList_Create();
    if (list == NULL) {
        printf("创建链表失败");
        return;
    }
    Teacher t1, t2, t3;
    t1.age = 10;
    t2.age = 20;
    t3.age = 30;

    LinkList_Insert(list, (LinkListNode*)& t1, 0);
    LinkList_Insert(list, (LinkListNode*)& t2, 0);
    LinkList_Insert(list, (LinkListNode*)& t3, 0);

    for (int i = 0; i < LinkList_Length(list); i++) {
        Teacher* node = (Teacher*)LinkList_Get(list, i);
        if (node == NULL) {
            continue;
        }
        printf("node.age = %d\n", node->age);
    }

    int length = LinkList_Length(list);
    printf("链表长度为%d\n", length);

    LinkListNode* node = LinkList_Delete(list, 0);
    for (int i = 0; i < LinkList_Length(list); i++) {
        Teacher* node = (Teacher*)LinkList_Get(list, i);
        if (node == NULL) {
            continue;
        }
        printf("node.age = %d\n", node->age);
    }

    LinkList_Destroy(list);
    system("pause");
}

    相关文章

      网友评论

          本文标题：16C++ 数据结构

          本文链接：https://www.haomeiwen.com/subject/xpfzectx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|16C++ 数据结构|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！