数据结构P46（2-1~2-4）

2023-10-07 00:12
文章标签 数据结构 p46

本文主要是介绍数据结构P46（2-1~2-4），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2-1编写算法查找顺序表中值最小的结点，并删除该结点

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct List
{int Max;//最大元素 int n;//实际元素个数 DataType *elem;//首地址 
};
typedef struct List*SeqList;//顺序表类型定义
SeqList SetNullList_Seq(int m)
{SeqList slist=(SeqList)malloc(sizeof(struct List));if(slist!=NULL){slist->elem=(DataType*)malloc(sizeof(DataType)*m);//申请顺序表空间，大小为m个DataType空间 if(slist->elem){slist->Max=m;//顺序表赋予的最大值 slist->n=0;//顺序表长度赋值为0 return(slist);}else free(slist);}printf("Alloc failure!\n");return NULL;}int IsNullList_seq(SeqList slist)
{return(slist->n==0);
} /*int InsertPre_seq(SeqList slist ,int p, DataType x)
{int q;if (slist->n>=slist->Max)//顺序表满了 {printf("overflow");return 0;}if(p<0||p>slist->n)//下标不存在 {printf("not exist!\n");return 0;}for(q=slist->n-1;q>=p;q--){slist->elem[q+1]=slist->elem[q];}slist->elem[p]=x;slist->n=slist->n+1;return 1;
}*/int DelIndex_seq(SeqList slist,int p)
{int i=0,q=0;for(i=0;i<slist->n;i++){if(slist->elem[i]==p){for(q=i;q<slist->n-1;q++){slist->elem[q]=slist->elem[q+1];}slist->n=slist->n-1;return 1;}}
}
void Print(SeqList slist)
{int i;for(i=0;i<slist->n;i++){printf("%d\n",slist->elem[i]);}
}int Insert_min(SeqList slist)
{int min=0,i=0;min=slist->elem[0];for(i=0;i<slist->n;i++){if(slist->elem[i]<min){min=slist->elem[i];}}return min;
}
int main()
{SeqList alist;int max,len,i,x,p;printf("\n please input the max value(<100) of max=");scanf("%d",&max);alist=SetNullList_Seq(max);printf("%d\n",IsNullList_seq(alist));if(alist!=NULL){printf("\n please input the length of list len =");scanf("%d",&len);for(i=0;i<len;i++){scanf("%d",&x);alist->elem[i]=x;alist->n=i+1;}}printf("The List is:\n"); Print(alist);p=Insert_min(alist);DelIndex_seq(alist,p);printf("After deleting the min the list is :\n");Print(alist);return 1;
}

在这里插入图片描述

2-2编写算法查找单链表中值最大的结点，并将该结点移至链表尾部


#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node
{DataType      data; struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   void MoveMaxToTail(head);LinkList SetNullList_Link() //设置头结点
{LinkList head = (LinkList)malloc(sizeof(struct Node));if (head != NULL) head->next = NULL;else printf("alloc failure");return head; 
}void CreateList_Tail(struct Node* head)//利用尾插法
{PNode p = NULL;PNode q = head;DataType data;scanf("%d", &data);while (data != -1){   p = (struct Node*)malloc(sizeof(struct Node));p->data = data;p->next = NULL;q->next = p;q = p;scanf("%d", &data);}
}
void  MoveMaxToTail(LinkList head)//移动到最后
{PNode pmax=NULL,p=NULL,pre=NULL,end=NULL;pmax=head->next;p=head->next->next;while(p){if(p->data>pmax->data){pmax=p;}p=p->next;}if(pmax->next==NULL){return 1;}else{p=head;while(p){if(p->next==pmax){pre=p;}if(p->next==NULL){end=p;}p=p->next;}pre->next=pmax->next;pmax->next=end->next;end->next=pmax;} return 0;
}
void print(LinkList head)   //打印
{PNode  p = head->next;while (p){printf("%d ", p->data);p = p->next;}
}
void DestoryList_Link(LinkList head)  //销毁链表
{PNode  pre = head; PNode p = pre->next;while (p){free(pre);pre = p;p = pre->next;}free(pre);
}int main()
{LinkList head = NULL;head = SetNullList_Link();CreateList_Tail(head);MoveMaxToTail(head);print(head);DestoryList_Link(head);return 0;
}

在这里插入图片描述

2-3编写算法实现顺序表的就地逆序置，即利用原表的存储空间将线性表（a1.a2,…,an）逆置为（an,an-1,…,a1），并分析设计的算法时间复杂度

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct List
{int Max;//最大元素 int n;//实际元素个数 DataType *elem;//首地址 
};
typedef struct List*SeqList;//顺序表类型定义
SeqList SetNullList_Seq(int m)
{SeqList slist=(SeqList)malloc(sizeof(struct List));if(slist!=NULL){slist->elem=(DataType*)malloc(sizeof(DataType)*m);//申请顺序表空间，大小为m个DataType空间 if(slist->elem){slist->Max=m;//顺序表赋予的最大值 slist->n=0;//顺序表长度赋值为0 return(slist);}else free(slist);}printf("Alloc failure!\n");return NULL;}int IsNullList_seq(SeqList slist)
{return(slist->n==0);
} void Print(SeqList slist)
{int i;for(i=0;i<slist->n;i++){printf("%d\n",slist->elem[i]);}
}void DispList(SeqList slist)
{int i,x;for(i=0;i<slist->n/2;i++)// 只需要遍历原表的一半就可以实现数据元素位置的交换{x=slist->elem[i];slist->elem[i]=slist->elem[slist->n-i-1];slist->elem[slist->n-i-1]=x;}
}int main()
{SeqList alist;int max,len,i,x,p;printf("\n please input the max value(<100) of max=");scanf("%d",&max);alist=SetNullList_Seq(max);printf("%d\n",IsNullList_seq(alist));if(alist!=NULL){printf("\n please input the length of list len =");scanf("%d",&len);for(i=0;i<len;i++){scanf("%d",&x);alist->elem[i]=x;alist->n=i+1;}}printf("The List is:\n"); Print(alist);DispList(alist);printf("The dispList is:\n"); Print(alist);return 1;
}

在这里插入图片描述
这段代码实现了一个顺序表，其中包括初始化、判断是否为空表、打印表元素、反转表元素等功能。算法时间复杂度如下：

  1. SetNullList_Seq：申请顺序表空间，时间复杂度为O(1)。
  2. IsNullList_seq：判断是否为空表，时间复杂度为O(1)。
  3. Print：遍历表元素并打印，时间复杂度为O(n)，其中n为表的长度。
  4. DispList：遍历表元素并交换位置，时间复杂度为O(n/2)，其中n为表的长度。

所以，整个代码的时间复杂度取决于最耗时的操作，即遍历表元素和交换位置。因此，整体的时间复杂度为O(n)。

2-4编写算法实现链表得到就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an），逆置为（an,an-1,…,a1），并分析设计的算法时间复杂度

#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node
{DataType      data; struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   LinkList SetNullList_Link() //设置头结点
{LinkList head = (LinkList)malloc(sizeof(struct Node));if (head != NULL) head->next = NULL;else printf("alloc failure");return head; 
}void CreateList_Tail(struct Node* head)//利用尾插法
{PNode p = NULL;PNode q = head;DataType data;scanf("%d", &data);while (data != -1){   p = (struct Node*)malloc(sizeof(struct Node));p->data = data;p->next = NULL;q->next = p;q = p;scanf("%d", &data);}
}
void ListOppose(LinkList head)//逆置 
{LinkList p,t;p=head->next;while(p->next!=NULL){t=p->next;p->next=t->next;//此时跳过了t结点元素，也就是说t结点元素脱离了链表t->next=head->next; //将t结点元素放在头结点后面，即t结点元素成为第一个结点head->next=t; //头结点的指针指向t}
}
void print(LinkList head)   //打印
{PNode  p = head->next;while (p){printf("%d ", p->data);p = p->next;}
}
void DestoryList_Link(LinkList head)  //销毁链表
{PNode  pre = head; PNode p = pre->next;while (p){free(pre);pre = p;p = pre->next;}free(pre);
}int main()
{LinkList head = NULL;head = SetNullList_Link();CreateList_Tail(head);print(head);printf("\n");ListOppose(head);print(head);return 0;
}

在这里插入图片描述
这段代码实现了一个链表，并包括了创建链表、逆置（反转）链表、打印链表和销毁链表等功能。算法的时间复杂度如下：

  1. SetNullList_Link：创建头结点，时间复杂度为O(1)。
  2. CreateList_Tail：利用尾插法创建链表，时间复杂度为O(n)，其中n为输入的元素个数。
  3. ListOppose：逆置链表，时间复杂度为O(n)，其中n为链表的长度。
  4. print：遍历链表并打印，时间复杂度为O(n)，其中n为链表的长度。
  5. DestroyList_Link：销毁链表，时间复杂度为O(n)，其中n为链表的长度。

因此，整个代码的时间复杂度取决于具有最高时间复杂度的操作，即创建链表、逆置链表和销毁链表，这三者的时间复杂度均为O(n)。所以，整体的时间复杂度为O(n)。

这篇关于数据结构P46（2-1~2-4）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/154822。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2