数据结构实验---顺序表的合并---链表的基本操作

2023-07-12 244

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构实验---顺序表的合并---链表的基本操作

本篇展示数据结构的两个实验

对顺序表和链表不清楚有以下文章介绍

掌握顺序表和单链表后实验均为上述的简单应用

顺序表的合并

定义线性表的顺序存储结构，并使用定义的结构实现两个线性表的合并。（建立两个有序顺序表，将两个有序顺序表合并为一个有序顺序表）。
内容要求：
建立有序表：12，23，46，67，85
建立有序表：5，59，94
两个有序顺序表合并为一个有序顺序表，验证代码的正确性。

代码实现

//建立有序表：12，23，46，67，85
//建立有序表：5，59，94
//两个有序顺序表合并为一个有序顺序表，验证代码的正确性。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;
typedef struct SeqList
{
   
    SLDataType* a;
    int size;
    int capacity;
}SeqList;

void SListInit(SeqList* ps)
{
   
    //assert(ps);
    ps->size = 0;
    ps->capacity = 4;
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
    if (ps->a == NULL)
    {
   
        perror("malloc fail");
        return;
    }
}

void SListDestroy(SeqList* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

void SListCheckCapacity(SeqList* ps)
{
   
    assert(ps);
    if (ps->size == ps->capacity)
    {
   
        SLDataType* tmp = NULL;
        tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)*(ps->capacity) * 2);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        ps->a = tmp;
        ps->capacity *= 2;
        //printf("The capacity now:%d\n", ps->capacity);
    }
    else
    {
   
        return;
    }
}

void SListPushBack(SeqList* ps, SLDataType x)
{
   
    assert(ps);
    SListCheckCapacity(ps);
    ps->a[ps->size] = x;
    ps->size++;
}

void SListPrint(SeqList* ps)
{
   
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
   
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SListMerge(SeqList* ps1, SeqList* ps2)
{
   
    assert(ps1);
    assert(ps2);
    SeqList ps;
    SListInit(&ps);
    for (int i = 0; i < ps1->size; i++)
    {
   
        SListPushBack(&ps, ps1->a[i]);
    }
    for (int i = 0; i < ps2->size; i++)
    {
   
        SListPushBack(&ps, ps2->a[i]);
    }
    printf("The result of merging two seqlists is:\n");
    SListPrint(&ps);
}

int main()
{
   
    SeqList ps1;
    SeqList ps2;
    SListInit(&ps1);
    SListInit(&ps2);
    int quantity1 = 0, quantity2 = 0, input = 0;

    printf("Input quantity of seqlist1-> ");
    scanf("%d", &quantity1);
    for (int i = 0; i < quantity1; i++)
    {
   
        scanf("%d", &input);
        SListPushBack(&ps1, input);
    }

    printf("Input quantity of seqlist2-> ");
    scanf("%d", &quantity2);
    for (int i = 0; i < quantity2; i++)
    {
   
        scanf("%d", &input);
        SListPushBack(&ps2, input);
    }

    SListMerge(&ps1, &ps2);
    return 0;
}

代码下载

Gitee下载链接

链表的基本操作

定义线性表的链式存储结构，定义结点类型，并使用定义的结构实现链表的创建，插入，删除、查询、输出等基本操作。
通讯录管理（必做内容）；约瑟夫环（选做内容）
必做内容要求：
1.通讯者的结点类型定义如下：
typedef struct {
char num[5] ; //编号
char name[9] ; //姓名
char sex[3] ; //性别
char phone[13]; //电话
char addr[31] ; //地址
]DataType ;
2.线性表的链式存储结构定义如下：
typedef struct node { //结点类型定义
DataType data ; //结点数据域
struct node next ; //结点指针域
} ListNode ;
typedef ListNode LinkList ;
ListNode * p ; //定义一个指向结点的指针变量
LinkList head ; //定义指向单链表的头指针
3.主控菜单设计要求
程序运行后，给出6个菜单项的内容和输入提示：
通讯录链表的建立

通讯者结点的插入

通讯者结点的查询

通讯者结点的删除

通讯录链表的输出
退出管理系统
    请选择   0——5
使用数字0——5来选择菜单项，其他输入则不起作用。
选做内容要求：
约瑟夫（Joseph）问题的一种描述是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只好同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置？

1.利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。
2.为了不失一般性，将30改为一个任意输入的正整数n，而报数上限（原为9）也为一个任选的正整数k。这样该算法描述如下：
（1）创建含有n个结点的单循环链表；
（2）生者与死者的选择：
p指向链表第一个结点，初始i 置为1；
while (i<=n/2) //删除一半的结点
{ 从p指向的结点沿链前进k-1步；
删除第k个结点（q所指向的结点）；p指向q的下一个结点；
输出其位置q->data；
i自增1；
}
（3）输出所有生者的位置。

3.测试结果
对于总人数30，报数上限为9，则
死者编号为：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23
生者编号为：1，2，3，4，10，11，13，14，15，17，20，21，25，28，29

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

typedef  struct
{
   
    char  num[5];    //编号
    char  name[9];   //姓名
    char  sex[3];     //性别
    char  phone[13];  //电话
    char  addr[31];   //地址
}DataType;

typedef struct node
{
   
    DataType data;
    struct node* next;
}ListNode;

//头节点用head
//定义一个指向结点的指针变量 ListNode* p;

ListNode* BuyListNode(DataType x);

void ListNodePush(ListNode** phead);

DataType Buynewdata();

void ListNodePrint(ListNode** phead);

int ListNodeFind(ListNode* head, const char* Findname);

void ListNodePop(ListNode** phead, const char* Popname);

ListNode* BuyListNode(DataType x)
{
   
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
   
        perror("malloc fail");
        return NULL;
    }
    newnode->next = NULL;
    newnode->data = x;
    return newnode;
}

DataType Buynewdata()
{
   
    DataType newdata;
    printf("请依次输入编号 姓名 性别 电话 地址\n");
    scanf("%s %s %s %s %s",
        newdata.num, newdata.name, newdata.sex, newdata.phone, newdata.addr);
    return  newdata;
}

void ListNodePush(ListNode** phead)
{
   
    assert(phead);
    ListNode* newnode = BuyListNode(Buynewdata());
    if (*phead == NULL)
    {
   
        *phead = newnode;
    }
    else
    {
   
        newnode->next = *phead;
        *phead = newnode;
    }
}

void ListNodePrint(ListNode** phead)
{
   
    ListNode* cur = *phead;
    printf("%-5s%-10s%-8s%-13s%-31s\n",
        "编号", "姓名", "性别", "电话", "地址");
    while (cur)
    {
   
        printf("%-5s%-10s%-8s%-13s%-31s\n",
            cur->data.num, cur->data.name, cur->data.sex,
            cur->data.phone, cur->data.addr);
        cur = cur->next;
    }
}

int ListNodeFind(ListNode* head, const char* Findname)
{
   
    ListNode* cur = head;
    while (cur)
    {
   
        if (strcmp(Findname, cur->data.name) == 0)
        {
   
            printf("找到了,该人的信息如下\n");
            printf("%-5s%-10s%-8s%-13s%-31s\n",
                "编号", "姓名", "性别", "电话", "地址");
            printf("%-5s%-10s%-8s%-13s%-31s\n",
                cur->data.num, cur->data.name, cur->data.sex,
                cur->data.phone, cur->data.addr);
            return 1;
        }
        else
        {
   
            cur = cur->next;
        }
    }
    printf("找不到信息\n");
    return 0;
}

void ListNodePop(ListNode** phead, const char* Popname)
{
   
    assert(*phead);
    assert(phead);
    if (ListNodeFind(*phead, Popname))
    {
   
        ListNode* Findnode = *phead;
        ListNode* prev = *phead;
        while (strcmp(Findnode->data.name, Popname) != 0)
        {
   
            prev = Findnode;
            Findnode = Findnode->next;
        }
        prev->next = Findnode->next;
        free(Findnode);
        Findnode = NULL;
        printf("删除该人信息成功\n");
        return;
    }
    else
    {
   
        printf("找不到该人信息\n");
        return;
    }
}

void menu()
{
   
    printf("*********************************************\n");
    printf("****1.建立信息表************** 2.插入信息 ****\n");
    printf("****3.查询信息  ************** 4.删除信息 ****\n");
    printf("****5.打印信息  ************** 0.退出     ****\n");
    printf("*********************************************\n");
}

void SetupListNode(ListNode** phead)
{
   
    int num = 0;
    printf("建立链表成功，开始录入信息\n");
    printf("输入要录取信息的个数->");
    scanf("%d", &num);
    while (num--)
    {
   
        ListNodePush(phead);
    }
}

void FindFunction(ListNode* head)
{
   
    char Findname[20] = {
    0 };
    printf("输入要查找的人名");
    scanf("%s", Findname);
    ListNodeFind(head, Findname);
}

void PopFunction(ListNode** phead)
{
   
    char Popname[20] = {
    0 };
    printf("输入要查找的人名");
    scanf("%s", Popname);
    ListNodePop(phead, Popname);
}

int main()
{
   
    menu();
    int input = 0;
    ListNode* head = NULL;
    do
    {
   
        printf("请选择->");
        scanf("%d", &input);
        switch (input)
        {
   
        case 1:
            SetupListNode(&head);
            break;
        case 2:
            if (head == NULL)
            {
   
                printf("通讯录还未建立，请先建立\n");
                break;
            }
            else
            {
   
                ListNodePush(&head);
                break;
            }
        case 3:
            if (head == NULL)
            {
   
                printf("通讯录还未建立，请先建立\n");
                break;
            }
            else
            {
   
                FindFunction(head);
                break;
            }
        case 4:
            if (head == NULL)
            {
   
                printf("通讯录还未建立，请先建立\n");
                break;
            }
            else
            {
   
                PopFunction(&head);
                break;
            }
        case 5:
            if (head == NULL)
            {
   
                printf("通讯录还未建立，请先建立\n");
                break;
            }
            else
            {
   
                ListNodePrint(&head);
                break;
            }
        case 0:
            break;
        default:
            printf("请重新选择\n");
            break;
        }
        menu();
    } while (input);
    return 0;
}

数据结构实验---顺序表的合并---链表的基本操作

顺序表的合并

代码实现

代码下载

链表的基本操作

代码实现

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构实验---顺序表的合并---链表的基本操作

顺序表的合并

代码实现

代码下载

链表的基本操作

代码实现

热门文章

最新文章

相关课程

相关电子书