首页 > 其他分享 >线性表学习1

线性表学习1

时间：2024-10-19 09:43:54浏览次数：7  
标签：Node 线性表 int list next 学习 length numlist

  • 线性结构
    若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且除了首尾节点外所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：(a1,a2,a3,...)
    特点：只有一个首结点和尾结点
    本质特征：除首尾结点外，其他结点只有一个直接前驱和一个直
    接后继。
    简言之，线性结构反映结点间的逻辑关系是二对一（1:1）的
    线性结构包括：线性表、 堆栈、 队列、 字符串、 数组
    等，其中最典型、 最常用的是线性表

线性表

线性表逻辑结构

alt text

PS：空表分配了内存空间但是没有元素，不是不存在这个表

线性表的顺序表示和逻辑实现

顺序表的表示

线性表的顺序表的表示又叫顺序存储结构顺序映像
alt text

线性表顺序存储的特点

  1. 逻辑上相邻的数据元素，其物理存储上也相邻；
  2. 若已知表中首元素在存储器中的位置则其他元素存放位置亦可求出
    alt text

LOC(ai)=LOC(a0)+L*(i)

顺序表的实现

（增删改查）

  1. 修改
    alt text

O(1)指的是对同一个元素只进行一次操作

  1. 增加
    遍历是从第i个到第L.length个元素
    在表的第i个元素前面插入一个元素
    alt text

  2. 删除
    删除线性表的第个位置上的元素
    alt text

  3. 清空和删除表

  4. 排序

  5. 查找
    下标查找即可

顺序表的运算效率分析

alt text

alt text

同理可证： 顺序表删除一元素的时间效率（时间复杂度）为
T (n)=(n-1)/2约等于o(n)

空间复杂度：0=o(1)，因为没有使用辅助数据

深入讨论

顺序表各种操作的通式如何写？？

写了一个晚上，思路不难，就是一些语法细节要注意（C语言基础不够牢导致的）

#include <stdio.h>
#include <stdlib.h>
typedef struct{
	int *numlist;
	int length;
	
}chatDemo;
//冒泡排序
void bubble(int *arr,int length){
	int temp=0;
	for(int i=0;i<length-1;i++){
		for(int j=0;j<length-i-1;j++){
			if(arr[j]>arr[j+1]){
				temp=arr[j+1];
				arr[j+1]=arr[j];
				arr[j]=temp;
			}
		}
	}

}
void search(chatDemo list,int tofind){//二分法查找
	int start=0;
	int end=list.length-1;
	int mid;
	while(start<=end){
		 mid=(start+end)/2;
		if(tofind>list.numlist[mid]){
			start=mid;
		}else if(tofind<list.numlist[mid]){
			end=mid;
		}
		else if(tofind==list.numlist[mid]){
		
			printf("the index is %d",mid);
			return;
		}
	}
	printf("404 not found");
}
void del(chatDemo *list,int position){
	if(position<0||position>=list->length){
		printf("OutoffpositionError");
		return;
	}
	for(int i=position;i<list->length;i++){
        	list->numlist[i-1]=list->numlist[i];
	}
	list->numlist[list->length-1]=0;
    list->length-=1;
	
	list->numlist=(int*)realloc(list->numlist,list->length*sizeof(int));
	printf("after del length:%d\n",list->length);
}
void add(chatDemo *list,int position,int addnum){
	if(position<1||position>list->length){
		printf("OutoffpositionError");
		return;
	}
	list->length+=1;
	
	list->numlist=(int*)realloc(list->numlist,list->length*(sizeof(int)));
	list->numlist[list->length-1]=0;
    for(int i=list->length-1;i>position-1;i--){
		list->numlist[i]=list->numlist[i-1];
	}
	list->numlist[position-1]=addnum;
	printf("after add length:%d\n",list->length);
}
int main(){
	chatDemo demo;
	demo.length=10;
	demo.numlist=(int*)calloc(demo.length,sizeof(int));
  int initial_values[] = {9, 2, 8, 3, 1, 4, 5, 6, 10, 7};
  for (int i = 0; i < demo.length; i++) {
	  demo.numlist[i] = initial_values[i];
  }
  bubble(demo.numlist,demo.length);
  printf("排序后数组\n");
	for (int i = 0; i < demo.length; i++) {
		
		printf("%d\n",demo.numlist[i]);
	}
	del(&demo,4);
	printf("数组长度是%d\n",demo.length);
	for(int i=0;i<demo.length;i++){
		printf("%d\n",demo.numlist[i]);
	}
	
	add(&demo,4,4);
	printf("数组长度是%d\n",demo.length);
	for(int i=0;i<demo.length;i++){
		printf("%d\n",demo.numlist[i]);
	}
	
	
	search(demo,8);
	free(demo.numlist);
	return 0;
}

抽象数据类型

线性表的链式表示和逻辑实现

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

typedef struct Node
{
	int data;      //数据域
	struct Node *next;  //指针域,构建递归结构
}Node;
typedef struct {
	Node *head;  // 头指针
	Node *tail;
	size_t length;
	// 尾指针
} List;
void InitList(List *list);//初始化
void push_tail(List *list,int x);//尾插
void push_head(List *list,int x);//头插
void show_list(List *list);//打印链表
void delAimval(List *list,int x,int ifone);//删除指定元素
void add(List *list,int x,int position,int fa);//指定位置前或后插入
void reverse(List*list);//逆序
Node *find(List *list,int x);//查找元素第一次出现位置，修改//
int main(){
	int numlist[]={0,1,2,5,5,6,7,8,9,8,5,2,1,1};
	int len=(int)(sizeof(numlist)/sizeof(int));
	int i=0;
	List demo,demox;
	InitList(&demo);
	InitList(&demox);
	while(i<len){
		push_tail(&demo,numlist[i++]);
	}
	printf("尾插法创建\n");
	show_list(&demo);
	i--;
	
	while(i>=0){
		push_head(&demox,numlist[i--]);
	}
	printf("头插法创建\n");
	show_list(&demox);
	reverse(&demox);
	printf("逆序后\n");
	show_list(&demox);
	delAimval(&demox,5,1);
	printf("删除一次指定元素5后\n");
	show_list(&demox);
	delAimval(&demox,5,0);
	printf("删除全部指定元素5后\n");
	show_list(&demox);
	printf("后插元素\n");
	add(&demox,99,6,1);
	show_list(&demox);
	printf("前插元素\n");
	add(&demox,99,6,0);
    show_list(&demox);
	find(&demox,2);
	return 0;
}
//初始化
void InitList(List *list)
{
  
  Node* headNode=(Node*)malloc(sizeof(Node));//此时头指针指向头节点
  list->head=headNode;
  assert(list->head!=NULL);
  list->head->next=NULL;
  list->tail = list->head; //尾指针也一起指向头节点。
  list->length=0;
  
}
void push_head(List *list,int x){
	
	Node *new_node=(Node*)malloc(sizeof(Node));
	assert(new_node!=NULL);
	new_node->data=x;
	new_node->next=NULL;
	//第一个节点的插入需要改尾指针的指向
	if(list->length==0){
		list->tail=new_node;
	}
	new_node->next=list->head->next;
	list->head->next=new_node;
	list->length++;
	
}
void push_tail(List *list,int x){
	Node *new_node=(Node*)malloc(sizeof(Node));
	assert(new_node!=NULL);
	new_node->data=x;
	new_node->next=NULL;
	// 将当前尾节点的next指向新节点
	list->tail->next = new_node;
	// 更新尾指针
	list->tail = new_node;
	list->length++;
}
void show_list(List *list)
{
	Node *p = list->head->next;
    while(p!=NULL){
	printf("%d-->",p->data);
	p=p->next;
}
printf("NULL\n");
}
Node *find(List *list,int x){
	int j=1;
	Node *p=list->head->next;
	while(p){
		if(p->data==x){
			//可以同时修改元素，这里就不实现了
			break;
		}else{
			j++;
			p=p->next;
		}
	}
	printf("%d是第%d个元素",x,j);
	return p;
}
void delAimval(List*list,int x,int ifone){
	
		Node *p=list->head;
		while(p!=NULL&&p->next!=NULL){
			if(p->next->data==x){
				Node *p2=p->next->next;
				Node *p1=p->next;
				p->next=p2;
				free(p1);
			    list->length--;
				if(ifone==1){break;}else if(ifone==0){
					p=list->head;
					continue;
				}else{printf("ffsr");}
			}else{
				p=p->next;
			}
		}
}
void add(List *list,int x,int position,int fa){
	int j=1;
	
	Node *new_node=(Node*)malloc(sizeof(Node));
	new_node->data=x;
	if(position<1||position>(int)list->length){
		printf("DIANLAO");
		
	    return;
	}
	if(fa==0){
		//前插
		Node *p=list->head;
		while(p&&p->next){
			if(j==position){
				new_node->next=p->next;
				p->next=new_node;
				list->length++;
				break;
			}else{p=p->next;j++;}
		}
	}else if(fa==1){
		//后插
		Node *p=list->head->next;
		while(p){
			if(j==position){
			   new_node->next=p->next;
			   p->next=new_node;
			   list->length++;
			   break;
			}else{
				p=p->next;
				j++;
			}
		}
	}
}
void reverse(List*list){
	Node* previous=NULL;
	Node* current=list->head->next;
	Node*next=NULL;
	while(current!=NULL){
		next=current->next;// 保存下一个节点
		current->next=previous;// 当前节点指向前一个节点
		previous=current;// 前一个节点移动到当前节点
		current=next;// 当前节点移动到下一个节点
	}
	list->head->next=previous;
}

运行结果

alt text

标签：Node,线性表,int,list,next,学习,length,numlist
From： https://www.cnblogs.com/hackzz/p/18429846

相关文章

  • 特征工程在营销组合建模中的应用：基于因果推断的机器学习方法优化渠道效应估计
    在机器学习领域，特征工程是提升模型性能的关键步骤。它涉及选择、创建和转换输入变量，以构建最能代表底层问题结构的特征集。然而，在许多实际应用中，仅仅依靠统计相关性进行特征选择可能导致误导性的结果，特别是在我们需要理解因果关系的场景中。因果推断方法为特征工程提供了一个更深......
  • 学习 gradle 基础
    简介Gradle的优势一款最新的，功能最强大的构建工具，用它逼格更高使用Groovy或者Kotlin代替XML，使用程序代替传统的XML配置，项目构建更灵活丰富的第三方插件，让你随心所欲使用完善Android，Java开发技术体系下载和安装官网地址https://services.gradle.org/distributi......
  • R语言机器学习算法实战系列（五）GBM算法+SHAP值 (Gradient Boosting Machines)
    禁止商业或二改转载，仅供自学使用，侵权必究，如需截取部分内容请后台联系作者!文章目录介绍教程下载数据加载R包导入数据数据预处理数据描述数据切割调节参数构建模型预测测试数据评估模型模型准确性混淆矩阵模型评估指标ROCCurvePRCCurve特......
  • 乘风破浪，乘风出海，学习英语之English Pod
    什么是EnglishPodhttps://learnenglishpod.comEnglishPod是一个专门为英语学习者设计的在线学习平台，提供各种各样的英语学习播客(podcast)和教学资源。其目标是帮助不同水平的学习者通过日常对话和实用内容提高英语听力、口语、词汇和语法能力。EnglishPod的课程通常包括......
  • 【AI学习】Mamba学习（八）：HiPPO通用框架定义和方法
    在大概了解了《HiPPO通用框架介绍》后，继续看HiPPO通用框架的相关定义和方法。相关内容在论文《HiPPO:RecurrentMemorywithOptimalPolynomialProjections》的第二章描述。2TheHiPPOFramework:High-orderPolynomialProjectionOperators作者将投影作为学习记忆......
  • 【AI学习】Mamba学习（七）：HiPPO通用框架介绍
    HiPPO这篇论文《HiPPO:RecurrentMemorywithOptimalPolynomialProjections》，提出了一个通用框架。我们再重新看一下论文的摘要：从连续数据中学习的一个核心问题是，随着更多数据的处理，以增量方式表示累积历史。我们介绍了一个通用框架（HiPPO），用于通过投影到多项式基上对连......
  • 深度学习_多层感知机基于Heart Disease UCI 数据集中的processed.cleveland.data训练
    多层感知机(Muti-Layerperceptron)#1.数据导入importpandasaspdnames=["age","sex","cp","trestbps","chol","fbs","restecg",......
  • Python学习的自我理解和想法（15）
    学的是b站的课程（千锋教育），跟老师写程序，不是自创的代码！今天是学Python的第15天，从今天开始，每天一到两个常用模块，更完恢复到原来的，开学了，时间不多，写得不多，见谅。目录OS模块(1).获取当前目录(2)获取当前路径(3)创建文件夹(4)删除文件夹(5)重命名文件或者文件夹(6)删除文件......
  • Typora超详细教程学习总结界面与功能详解
    一、章节目录Typora简介Typora界面与功能Typora编辑技巧Typora主题与样式Typora与其他工具的配合学习Typora的方法Typora资源简介与总结二、各章节知识点总结Typora简介Typora是一款简洁高效的Markdown编辑器，支持实时预览，让用户在编辑文本的同时可以立即......
  • OpenGL高级特性超详细入门教程知识点总结攻略学习目录
    OpenGL知识点目录一、OpenGL简介与基本概念二、OpenGL渲染管线与流程三、OpenGL着色器编程四、OpenGL纹理与材质五、OpenGL灯光与阴影六、OpenGL缓冲区与帧缓存七、OpenGL高级特性与最新发展八、如何学习OpenGL九、OpenGL资源简介一、OpenGL简介与基本概念重点详细内容知......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99