首页 > 其他分享 >C 语言整数单链表的表示和实现 数据结构课程设计报告

C 语言整数单链表的表示和实现 数据结构课程设计报告

时间：2024-03-08 17:44:54浏览次数：26  
标签：Node 结点 单链 list 课程设计 next 链表 数据结构 节点

 数据结构课程设计报告

专业名称：计算机科学与技术

 

课程名称：数据结构       

 

实训题目：整数单链表的表示和实现                           

实训环境：C 语言实现（ Dev C++ ）                          

实训内容：定义一个数据元素为整数类型的单链表并实现以下功能：

①  创建整数单链表，输入8个数据，并存储在单链表中；

② 遍历并输出单链表中所有数据元素；

③ 按序号查找，返回数据元素的值或地址；

④ 按值查找，返回数据元素的序号或地址；

⑤ 指定位置（序号）插入新的数据元素；

⑥ 删除指定位置（序号）数据元素。

 

实训小组

学号

姓名

分工

联系电话

小组组长

2xxxxxxx

QSZ

创建整数单链表，输入8个数据，并存储在单链表中；并最后输出整理等

备注：运行截图 自行添加

小组成员

 

QSZ

遍历并输出单链表中所有数据元素；

 

备注：运行截图 自行添加

 

QSZ

按序号查找，返回数据元素的值或地址；

 

 

QSZ

按值查找，返回数据元素的序号或地址；

 

 

 

QSZ

 

指定位置（序号）插入新的数据元素；

 

 

QSZ

删除指定位置（序号）数据元素。

 

 

 

 

 

1 整数单链表存储结构的表示

【注意】：定义数据结构体，并对每个域的功能给与解释说明

   整数单链表存储结构的表示如下所示：

 

typedef struct node{

    int data;                 //存放元素值的域

    struct node *next;        //指向下一节点的指针域

}Node;

 

其中，`data`为存放整数元素值的域，`next`为指向下一节点的指针域。对于链表中每个节点，其`data`域存放该节点的整数元素值，`next`指向下一个节点。链表的头节点`head`为指向链表第一个节点的指针。null节点为链表的结束标志，即链表结构中最后一个节点的`next`指针域为NULL。

 

 

2 整数单链表基本操作的实现

【注意】：首先描述每个功能模块的算法步骤，其次给出C语言实现代码，最后给出运行截图。

2.1 输入数据，创建整数单链表

  算法步骤：

  1. 定义一个结构体Node，包括数据元素data和指向下一个结点的指针next；
  2. 定义一个函数create_list()，用于创建单链表，函数中定义一个头结点head和一个尾结点tail，初始化为NULL；
  3. 逐个输入数据，创建新结点，将新结点插入到链表尾部；
  4. 返回头结点head。

 

C语言实现代码：

  

#include <stdio.h>

#include <stdlib.h>

typedef struct node{

    int data;

    struct node *next;

}Node;

 

Node *create_list(){

    Node *head, *tail, *pnew;

    head = tail = NULL;

    int i, num;

    for(i=0; i<8; i++){

        printf("请输入第%d个数：", i+1);

        scanf("%d", &num);

        pnew = (Node*)malloc(sizeof(Node)); //为新结点动态申请内存

        if(pnew == NULL){ //内存分配失败

            printf("内存分配失败!");

            exit(1);

        }

        pnew->data = num;

        pnew->next = NULL;

        if(head == NULL){ //链表为空

            head = tail = pnew; //头尾结点都指向新结点

        }

        else{

            tail->next = pnew; //尾结点指向新结点

            tail = pnew; //尾结点更新为新结点

        }

    }

    return head; //返回头结点

}

 

int main(){

  Node *head = create_list();

  return 0;

}

运行截图：

 

 

 

2.2 遍历和输出单链表所有数据元素

2.2.1 非递归遍历和输出

  

算法步骤：

  1. 定义一个指针p指向链表的头结点；
  2. 使用while循环遍历链表，当p不为NULL时，输出当前节点的数据元素，然后将p指向下一个节点；
  3. 输出完毕后，换行。

 

C语言实现代码：

void print_list(Node *list){

    Node *p;

    p = list;

    while(p != NULL){

        printf("%d ", p->data);

        p = p->next;

    }

    printf("\n");

}

运行截图：

 

 

2.2.2 递归遍历和输出

  算法步骤：

  1. 定义递归函数print_list递归遍历输出单链表中所有数据元素。
  2. 递归终止条件为链表为空。
  3. 递归输出当前节点的值，并且传入下一节点进行递归。

 

C语言实现代码：

 

void print_list(Node *list){

    if(list == NULL)

        return;

    printf("%d ", list->data);

    print_list(list->next);

    printf("\n");

}

 

运行截图：

 

 

2.3 按序号查找，返回数据元素的值或地址

  算法步骤：

 

  1. 定义一个指向链表开头的指针p，并将其初始化为链表的头节点。
  2. 从头节点开始循环遍历链表，如果当前位置的节点不为空且当前位置的位置小于目标位置index，则将指针p指向下一个节点，同时增加i的值。
  3. 如果i的值等于目标位置index，则返回节点p的地址。
  4. 如果循环结束仍未找到目标节点，则说明该序号不存在，返回空指针。

 

C语言实现代码：

 

Node *search_by_index(Node *list, int index){

    Node *p;

    p = list;

    int i = 0;

    while(p != NULL && i < index){

        p = p->next;

        i++;

    }

    return p;

}

 

运行截图：

 

 

2.4 按值查找，返回数据元素的序号或地址

  1. 从头节点开始遍历单链表，找到第一个data域等于给定值的节点。
  2. 返回该节点的地址或序号（从1开始计数）。

 

C语言实现代码：

 

Node *search_by_value(Node *list, int value){

    Node *p;

    p = list;

    int i = 1;

    while(p != NULL){

        if(p->data == value)

            return p;

        p = p->next;

        i++;

    }

    return NULL;

}

运行截图：

 

2.5 指定位置（序号）插入新的数据元素

 算法步骤：

  1. 创建一个新结点，存储要插入的数据元素。
  2. 查找要插入位置的前驱结点。
  3. 将新结点的next指针指向前驱结点的next指针所指向的结点。
  4. 将前驱结点的next指针指向新结点。

 

C语言代码实现：

void insert_by_index(Node *list, int index, int value){

    Node *pnew, *p;

    pnew = (Node*)malloc(sizeof(Node));

    if(pnew == NULL){

        printf("内存分配失败!");

        exit(1);

    }

    p = search_by_index(list, index);

    if(p == NULL){

        printf("位置错误!");

        exit(1);

    }

    pnew->data = value;

    pnew->next = p->next;

    p->next = pnew;

}

运行截图：

 

2.6 删除指定位置（序号）数据元素

  算法步骤：

 

  1. 找到待删除节点p和其前驱节点pre。
  2. 将pre的next指针指向p的next。
  3. 释放p节点。

 

C语言实现代码：

 

void delete_by_index(Node *list, int index){

    Node *p, *pre;

    p = search_by_index(list, index);

    if(p == NULL){

        printf("位置错误!");

        exit(1);

    }

    pre = search_by_index(list, index-1);

    pre->next = p->next;

    free(p);

}

 

运行截图：

 

3 拓展思考

如果您操作的是双向链表，针对以下功能请描述您的解决思路。

3.1 双向链表中指定位置插入元素如何实现？

  1. 如果链表为空，直接将要插入的元素作为头结点；
  2. 如果要插入的位置是头结点之前，直接将要插入的元素作为新的头结点，将原头结点的前继指针指向新的头结点；
  3. 如果要插入的位置是尾结点之后，直接将要插入的元素作为新的尾结点，将原尾结点的后继指针指向新的尾结点；
  4. 如果要插入的位置是在链表中部，则需要先找到该位置的前一个节点，然后将要插入的元素的后继指针指向该位置节点，将要插入的元素的前继指针指向该位置前一个节点，将该位置节点的前继指针指向要插入的元素，将该位置前一个节点的后继指针指向要插入的元素。

 

通过以上步骤即可在双向链表中指定位置插入元素。

 

 

3.2 双向链表中删除某个元素如何实现？

  1. 如果链表为空，则直接返回空链表；
  2. 如果要删除的是头结点，则将头指针指向头结点的下一个节点，并将新的头结点的前继指针设置为空；
  3. 如果要删除的是尾结点，则将尾指针指向尾结点的前一个节点，并将新的尾结点的后继指针设置为空；
  4. 如果要删除的节点在链表中部，则需要先找到要删除的节点，将要删除节点前一个节点的后继指针指向要删除节点的后继节点，将要删除节点后一个节点的前继指针指向要删除节点的前继节点。

 

通过以上步骤即可在双向链表中删除某个元素。需要注意的是，在删除节点后需要释放该节点的内存空间，以避免内存泄漏。

声明：本网站所有代码类模块均为本人原创作品，未经许可不得用于商业用途。

 

标签：Node,结点,单链,list,课程设计,next,链表,数据结构,节点
From： https://www.cnblogs.com/qsz666/p/18061524

相关文章

  • 【学习笔记】 - 基础数据结构 ：Link-Cut Tree(进阶篇)
    前言LCT没题写可以去写树剖和一些线段树合并的题练手LCT的概念原本的树剖是对树进行剖分，剖分为重边和轻边LCT则是对于树分为虚边和实边，特殊的，LCT可以没有虚边(例：银河英雄传说v2)单独被包含在一个实链里的点称作孤立点在树剖中，我们使用线段树/树状数组来维护重链在Link-Cut......
  • 数据结构-绪论
    绪论️概念，特性，设计要求数据结构+算法=程序数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称，其分为：原子类型：其值不可再分。结构类型：其值可再分解为若干成分。抽象数据类型：抽象数据组织以及相关操作。易错题：1.可以用（）定义一个完整的数据结构。 答案A.......
  • 数据结构-线性表
    线性表由n（n>=0）个数据特性相同的元素构成的有限序列，称为线性表。他是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间通过一对一首尾相接的方式连接起来。特点：存在唯一一个被称为“第一个”的数据元素存在唯一一个被成为“最后一个”的数据元素。除了......
  • 2024 年春节集训 _ 第二课 - 数据结构优化动态规划
    【例题\(1\)】递增子序列\(\color{white}{link}\)考虑\(dp.\)\(dp[i][j]\)表示以元素\(i\)为结尾，长度为\(k\)的方案数。那么显而易见就有一个转移方程：\[dp[i][j]=\sum_{a[k]<a[i],\k<i}dp[k][j-1]\]先抛去第二维度的\(j\)，这是可以做一个关于\(a[i]\)值的大......
  • P5609 [Ynoi2013] 对数据结构的爱
    题面传送门好像搞了个神秘做法。考虑离线扫描线，用一个fhq-Treap维护所有的询问现在长什么样，然后每次操作就整体加\(A_i\)，\(\geqp\)的减去\(p\)，这个可以分裂之后打整体标记，然后用那个值域相交的fhq-Treap合并实现。然后你发现这样就过了。构造一下卡不掉，于是考虑给这个......
  • [数据结构] 树、森林及二叉树的应用
    树、森林树的存储结构双亲表示法双亲表示法的存储结构#defineMAX_TREE_SIZE100typedefstruct{intdata;intparent;}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;}PTree;【注】区别树的顺序存储结构与二叉树的顺序存储结......
  • [数据结构] 树与二叉树
    树的基本概念树的定义树是由\(n(n\geq0)\)个节点组成的有限集。当\(n=0\)时，称为空树。任意一棵非空树应满足以下两点：（1）有且仅有一个特定的称为根的节点；（2）当\(n>1\)时，其余节点可分为\(m(m>0)\)个互不相交的有限集\(T_1,T_2,\dots,T_m\)，其中每个集合本身又是一棵树，称为......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    写在前面比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出套话Sketch的基础是概要数据结构（SummaryDataStructure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行压缩、聚合或采样，以及使用一些统计方法......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    写在前面比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出套话Sketch的基础是概要数据结构（SummaryDataStructure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行压缩、聚合或采样，以及使用一些统计方法......
  • 现有Sketch数据结构|持续更新|菜鸟学习
    现有Sketch数据结构基本原理写在前面比较简略，偏差之类的理论推导建议去读论文，如果有误麻烦指出套话由GPT生成Sketch的基础是概要数据结构（SummaryDataStructure），它是一种可以以较小的内存消耗来表示和估计大规模数据集的某些属性的数据结构。概要数据结构通过对原始数据进行......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99