首页 > 其他分享 >顺序表和链式表

顺序表和链式表

时间：2023-08-18 16:01:27浏览次数：27  
标签：Node index arr 顺序 return next 链式 data

一、顺序表

数据项：

存储元素的内存首地址

表的容量

元素的数量

运算：

创建、销毁、清空、插入、删除、访问、查询、修改、排序、遍历

注意：

1、要确保数据元素的连续性

2、不能越界

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

#define TYPE int
#define PH "%d "

//    设计顺序表结构
typedef struct Array
{
    TYPE* ptr;        //    存储元素的内存首地址
    size_t cal;        //    表的容量
    size_t cnt;        //    元素的数量
}Array;

//    创建
Array* create_array(size_t cal)
{
    //    给顺序表结构分配内存
    Array* arr = malloc(sizeof(Array));
    //    给数据元素分配内存
    arr->ptr = malloc(sizeof(TYPE)*cal);
    //    记录表的容量
    arr->cal = cal;
    //    初始化元素的数量
    arr->cnt = 0;

    return arr;
}

//    销毁
void destroy_array(Array* arr)
{
    free(arr->ptr);
    free(arr);
}
//    清空
void clear_array(Array* arr)
{
    arr->cnt = 0;    
}

//    插入
bool insert_array(Array* arr,size_t index,TYPE data)
{
    //    判断表是否满
    if(arr->cnt >= arr->cal)    return false;
    //    判断下标是否能保持元素的连续性
    if(index > arr->cnt) return false;

/*
    //    数据向后移动
    for(int i=arr->cnt; i>index; i--)
    {
        arr->ptr[i] = arr->ptr[i-1];    
    }
*/
    memmove(arr->ptr+index+1,arr->ptr+index,(arr->cnt-index)*sizeof(TYPE));

    //    插入数据
    arr->ptr[index] = data;
    arr->cnt++;
    return true;
}

//    删除
bool delete_array(Array* arr,size_t index)
{
    if(index >= arr->cnt) return false;
    /*
    for(int i=index; i<arr->cnt-1; i++)
    {
        arr->ptr[i] = arr->ptr[i+1];
    }
    */
    memmove(arr->ptr+index,arr->ptr+index+1,(arr->cnt-index-1)*sizeof(TYPE));
    arr->cnt--;
    return true;
}

//    访问
bool access_array(Array* arr,size_t index,TYPE* data)
{
    if(index >= arr->cnt) return false;
    *data = arr->ptr[index];
    return true;
}

//    查询
int query_array(Array* arr,TYPE data)
{
    for(int i=0; i<arr->cnt; i++)
        if(arr->ptr[i] == data) return i;
    return -1;
}
//    修改
bool modify_array(Array* arr,size_t index,TYPE data)
{
    if(index >= arr->cnt) return false;
    arr->ptr[index] = data;
    return true;
}

//    排序
void sort_array(Array* arr)
{
    for(int i=0; i<arr->cnt-1; i++)
    {
        for(int j=i+1; j<arr->cnt; j++)    
        {
            if(arr->ptr[j] < arr->ptr[i])
            {
                TYPE temp = arr->ptr[j];
                arr->ptr[j] = arr->ptr[i];
                arr->ptr[i] = temp;
            }
        }
    }
}

//    遍历
void show_array(Array* arr)
{
    for(int i=0; i<arr->cnt; i++)
    {
        printf(PH,arr->ptr[i]);    
    }
    printf("\n");
}

int main(int argc,const char* argv[])
{
    Array* arr = create_array(10);    

    for(int i=0; i<5; i++)
    {
        insert_array(arr,0,i+1);    
    }

    insert_array(arr,1,8);    
    delete_array(arr,5);
    show_array(arr);

    int num = 0;
    if(access_array(arr,5,&num))
        printf("num=%d\n",num);
    else
        printf("index error\n");

    printf("index=%d\n",query_array(arr,80));

    sort_array(arr);
    clear_array(arr);
    show_array(arr);
    destroy_array(arr);
}

二、链式表

数据元素(节点)的数据项：

数据域：可以是各种类型的若干项数据项

指针域：指向下一个节点的指针

由若干个节点通过指针域连接起来就形成了链表

不带头节点的链表：

定义：第一个节点的数据域存储的是有效数据

缺点：当插入、删除时可能会改变第一个有效节点，传递的参数需要传递二级指针，实现时需要区分是否是操作第一个有效节点，较为麻烦

带头节点的链表：

定义：第一个节点作为头节点，数据域不使用不存储有效数据，它的指针域永远指向链表的第一个有效数据节点，就算链表长度为0，头节点依然存在

优点：当插入、删除时是不会改变头节点的指向，只需要改变它的next，因此无需传递头节点的二级指针，并且实现时无需区分两种情况

注意：有效节点的处理必须从头节点的next开始

注意：笔试题时，如果题目没有说明链表是否带头节点，应该两种情况都进行分析

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

#define TYPE int

//	设计链表的节点结构
typedef struct Node
{
	TYPE data;			//	节点的数据域
	struct Node* next;	//	节点的指针域
}Node;

//	创建节点
Node* create_node(TYPE data)
{ 
	//	申请节点的内存
	Node* node = malloc(sizeof(Node));
	node->data = data;
	node->next = NULL;
	return node;
}

//	头添加
void add_head_list(Node** head,TYPE data)
{
	//	创建待添加的节点
	Node* node = create_node(data);
	node->next = *head;
	*head = node;
}

//	按值删除
bool del_value_list(Node** head,TYPE data)
{
	if((*head)->data == data)
	{
		Node* temp = *head;
		*head = (*head)->next;
		free(temp);
		return true;
	}
	//	遍历找到待删除节点的前一个节点
	for(Node* n=*head; n->next; n=n->next)
	{
		if(n->next->data == data)
		{
			Node* temp = n->next;
			n->next = n->next->next;
			free(temp);
			return true;
		}
	}
	return false;
}

//	遍历链表
void show_list(Node* head)
{
	for(Node* n=head; n; n=n->next)
	{
		printf("%d ",n->data);	
	}
	printf("\n");
}

//	访问
bool access_list(Node* head,size_t index,TYPE* data)
{
	int i = 0;
	for(Node* n = head; n; n=n->next,i++)
	{
		if(i == index) 
		{
			*data = n->data;
			return true;
		}
	}
	return false;
}

//	排序
void sort_list(Node* head)
{
	for(Node* i=head; i->next; i=i->next)
	{
		for(Node* j=i->next; j; j=j->next)
		{
			if(j->data < i->data)
			{
				TYPE temp = j->data;
				j->data = i->data;
				i->data = temp;
			}
		}
	}
}

//	按位置删除
bool del_index_list(Node** head,size_t index)
{
	if(0 == index)
	{
		Node* temp = *head;
		*head = temp->next;
		free(temp);
		return true;
	}

	Node* n = *head;
	for(int i=1; n->next; n=n->next,i++)
	{
		if(i == index)
		{
			Node* temp = n->next;
			n->next = temp->next;
			free(temp);
			return true;
		}
	}
	return false;
	/*
	while(--index)
	{
		n = n->next;
		if(NULL == n) return false;
	}

	if(NULL == n->next) return false;
	Node* temp = n->next;
	n->next = temp->next;
	free(temp);
	*/
	return true;
}


int main(int argc,const char* argv[])
{
	Node* head = create_node(10);

	for(int i=0; i<5; i++)
	{
		add_head_list(&head,i+1);	
	}
	show_list(head);
	del_value_list(&head,100);
	show_list(head);
	int num = 0;
	access_list(head,20,&num);
	printf("num=%d\n",num);
	sort_list(head);
	show_list(head);
	del_index_list(&head,2);
	show_list(head);

	/*	理解链表的本质
	Node* n1 = create_node(10);
	Node* n2 = create_node(20);
	Node* n3 = create_node(30);
	Node* n4 = create_node(40);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;

	for(Node* n=n1; n; n = n->next)
	{
		printf("%d ",n->data);	
	}
	*/
}

标签：Node,index,arr,顺序,return,next,链式,data
From： https://www.cnblogs.com/wangqiuji/p/17640728.html

相关文章

  • WPF初始化顺序
    WPF的初始化的顺序///<summary>///MainWindow.xaml的交互逻辑///</summary>publicpartialclassMainWindow:Window{publicMainWindow(){InitializeComponent();}privatevoidWindow_A......
  • 1.C++入门以及简单顺序结构
    C++入门以及简单顺序结构一、编写一个简单的C++程序#include<iostream>#include<cstdio>usingnamespacestd;intmain(){return0;}二、基础语法变量1.变量的概念变量本质上是一个装东西的盒子，并且只能存放一个值。2.变量的定义变量必须先定义，才可以......
  • 1.C++入门以及简单顺序结构
    C++入门以及简单顺序结构一、编写一个简单的C++程序#include<iostream>usingnamespacestd;intmain(){ return0;}二、基础语法变量1.变量的概念变量本质上是一个装东西的盒子，并且只能存放一个值。2.变量的定义变量必须先定义，才可以使用。inta=5;......
  • 英语形容词的排列顺序
      英语形容词的排列顺序作者：未知 发布会员：kuangshiyi 版权：原创 添加时间：2007-6-11 阅读：25272次【字体：大中小】 英语形容词的排列顺序   当两个以上形容词修饰一个名词，形容词该如何排列?为什么不能说ablacknewpen，而是说成anewb......
  • 【剑指Offer】59、按之字形顺序打印二叉树
    【剑指Offer】59、按之字形顺序打印二叉树题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。解题思路：这道题仍然是二叉树的遍历，相当于层次遍历，可以和第22题：从上往下打印二......
  • 顺序表与链表
    顺序表与链表前言  基础数据结构的学习主要包括两个部分，即【结构定义】与【结构操作】。顾名思义，结构定义就是定义某种或多种性质，再通过相关的结构操作去维护这种性质。对于初学者来说数据结构的学习不能抽象的理解，还需要结合动态的、可视化的工具去理解。下面给出美国旧金山......
  • c/c++参数入栈顺序和参数计算顺序
    如果大家细心的话应该知道c/c++语言函数参数入栈顺序为从右至左，那么为什么这样呢？来看看两个知识点：参数的计算顺序与压栈顺序。参数入栈顺序c/c++中规定了函数参数的压栈顺序是从右至左，函数调用协议会影响函数参数的入栈方式、栈内数据的清除方式、编译器函数名的修饰规则等。参......
  • 1.C++入门以及简单顺序结构
    C++入门以及简单顺序结构一.编写一个简单的C++程序#include<iostream>usingnamespacestd;intmain(){ return0;}二.基础语法变量1.变量的概念变量本质上是一个装东西的盒子，并且只能存放一个值。2.变量的定义变量必须先定义，才可以使用inta=5;3.变量......
  • RabbitMQ如何保证顺序消费
    面试官：你能说说RabbitMQ是如何保证消息顺序消费的吗？老任：如果我们想要保证消息是按照顺序进行发送的，发送到队列后，队列的消息应该是先进先出的，我们只需要一个队列配置一个消费者即可(窃喜中......)。面试官：我们的项目一般都是集群部署的，一个队列就会有多个消费者，怎么实现一个队列中所......
  • 《高级程序员 面试攻略 》RocketMQ 如何保证顺序性
    RocketMQ提供了一种称为顺序消息的机制来确保消息的顺序性。下面是一些关键的方法和概念：1.顺序消息：顺序消息是指在发送和消费过程中，消息按照特定的顺序进行处理。RocketMQ通过将消息发送到同一个消息队列（MessageQueue）来实现顺序消息。每个消息队列都有一个全局唯一的标识符（Me......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99