当前位置： 首页 > article >正文

c语言数据结构与算法--简单实现线性表（顺序表+链表）的插入与删除

article 2024/11/25 14:32:04

        老规矩，点赞+评论+收藏+关注！！！

目录

线性表

其特点是：

算法实现：

运行结果展示

链表

插入元素：

删除元素：

算法实现

运行结果

        线性表是由n个数据元素组成的有限序列，每个元素都有唯一的下标，下标从0开始递增。线性表的元素之间存在一对一的线性关系，即除首元素外，每个元素有且只有一个前驱元素，除尾元素外，每个元素有且只有一个后继元素。线性表可以通过顺序存储或链式存储来实现。线性表的基本操作包括初始化、创建、增加、删除和查找等。

        顺序表和链表是线性表的两种实现方式，都是用来存储逻辑关系为“一对一”的数据。它们的相同点是：都是线性表结构；元素逻辑存储上是连续的；每个元素都有唯一的前驱和唯一的后继。它们的不同点是：底层存储空间不一样，顺序表底层存储空间是连续的，而链表则是不连续的；插入和删除方式不同，顺序表任意位置进行插入和删除操作，需要搬运大量的元素，效率低，时间复杂度为O（N）。顺序表集中存储数据，适合访问、遍历数据，在数据量确定时空间利用率高；链表通过指针链接数据，适合插入、删除数据，在数据量不确定时空间利用率高。

线性表

线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。

其特点是：

1．第 i 个元素 a i 的存储位置可以用公式计 LOC(a i) = LOC(a1)+(i-1)*L

其中 LOC(a1)第一个元素a1 的存储位置，L 每个元素需占的存储单元

2．表中相邻的元素 a i和 a i+1赋以相邻的存 储位置 LOC(a i)和 LOC(a i+1)

3．是一种随机存储结构：只要知道线性表的 起始位置就可随机存取线性表中的任一元素。

​

        当我们要在线性表的顺序存储结构上的第 i 个位置上插入一个元素时，必须先将 线性表第 i 个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第 i 个元素时，也必须把第 i 个元素之后的所有元素前 移一个位置。

​

​

算法实现：

1、引入头文件、定义结构体

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INIT_SIZE 100  //初始分配量
#define INCRE_SIZE 10  //分配增量

typedef struct {
	int *pList;
	int length;
	int listSize;
}SqList;

2、创建顺序表

//顺序表的创建
void initial(SqList &L) {  //使pList指向连续存储空间的首地址
	L.pList = (int*)malloc(INIT_SIZE * sizeof(int));
	L.length = 0;  //目前元素的个数为0
	L.listSize = INIT_SIZE;  //空间最大存储的数量
}

3、定义插入函数

//第i个元素前插入e
void insert(int e,SqList &L,int i) {
	if (i <= L.length || L.length < L.listSize) {
		//将第i个元素开始依次往后移动一个位置，将L[i-1]的位置腾出
		for (int curIndex = L.length - 1; curIndex >= i - 1; --curIndex) {
			L.pList[curIndex + 1] = L.pList[curIndex];
		}
		L.pList[i - 1] = e;
		++L.length;  //多存了个数据，元素个数加一
	}
}

4、定义删除函数

void delete_(SqList &L,int i) {
	if (i <= L.length || L.length < L.listSize) {
		//将第i个元素开始依次往后移动一个位置
		for (int curIndex = i-1; curIndex <= L.length; ++curIndex) {
			L.pList[curIndex] = L.pList[curIndex + 1];
		}
		--L.length;  //多存了个数据，元素个数减一
	}
}

5、初始化输入表

//初始输入表
void initial_list(SqList* L) {
	int n,d;
	printf("请输入输入数字个数n(大于1的整数):");
	scanf_s("%d", &n);
	while (1) {
		if (n <= 0) {
			printf("请输入大于0的整数！！！");
			scanf_s("%d", &n);
		}
		else {
			break;
		}
	}
	//printf("%d", n);
	for (int i = 0; i <= n-1; i++) {
		printf("请输入第%d个数：",i+1);
		scanf_s("%d",&d);
		L->pList[i] = d;
	}
	L->length = n;
}

6、定义打印函数

//打印数组
void print_function(SqList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%d  ", L.pList[i]);
	}
	printf("\n");
}

7、主函数

int main() {
	SqList L;
	initial(L);
	initial_list(&L);
	printf("原数组:\n");
	print_function(L);
	printf("\n");
	while (1) {
		printf("请输入0/1/2对线性表进行操作(0是退出,1是插入,2是删除):\n");
		int num;
		scanf("%d", &num);
		if (num == 1) {
			printf("现在进入插入环节，请指定插入元素与插入位置:\n");
			int i, n;
			scanf("%d %d", &i, &n);
			insert(i, L, n);
			printf("插入后的数组:\n");
			print_function(L);
		}
		else if (num == 2) {
			printf("现在进入删除环节，请指定删除要元素位置:\n");
			int n;
			scanf("%d",&n);
			delete_(L, n);
			printf("删除后的数组:\n");
			print_function(L);
		}
		else if (num == 0) {
			break;
		}
		else {
			printf("请输入正确的操作（输入0/1/2）\n");
		}
		}
	return 0;
}

运行结果展示

        输入数字个数n,并输入这n个数

        选择下一步操作（0退出，1插入，2删除）

链表

双向链表

        结点有两个指针域：一个指向直接后继，另一个指向直接前驱。目的是克服单链 表的单向寻查的缺点。

插入元素：

        当插入数据元素时，首先生成一个结点，结点的数据域为插入的元素；然后找到元素的插入位置；最后修改指针域。例如下图中，在 p 结点后插入新生 成结点 s，则修改指针的语句为：

s ->data = e; s->next = p->next;  p->next = s;

删除元素：

        当删除数据元素时，仅修改待删除结点的前一个结点的指针。例如下 图中，待删除的结点为 q，q 的前一个结点为 p，删除后结点 q 的数据赋给 e，则修改 指针的语句为：

q= p ->next;  p->next = q->next; e = q-> data;  free(q);

算法实现

1、头文件、结构体的定义

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>  
#include <stdlib.h>  

typedef struct Node {
    int data;
    struct Node* prior;
    struct Node* next;
} Node;

2、双链表中添加节点

// 在双链表末尾添加节点  
void append(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    }
    else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prior = temp;
    }
}

3、定义打印函数

// 打印双链表  
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

4、指定位置插入元素

// 在指定位置插入节点  
void insertAtPosition(Node** head, int position, int data) {
    Node* newNode = createNode(data);
    if (position == 1) {
        newNode->next = *head;
        if (*head != NULL) {
            (*head)->prior = newNode;
        }
        *head = newNode;
    }
    else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position out of bounds\n");
            free(newNode);
            return;
        }
        newNode->next = temp->next;
        newNode->prior = temp;
        if (temp->next != NULL) {
            temp->next->prior = newNode;
        }
        temp->next = newNode;
    }
}

5、删除元素

// 删除指定值的节点  
void deleteValue(Node** head, int data) {
    Node* temp = *head;
    Node* prior = NULL;

    while (temp != NULL && temp->data != data) {
        prior = temp;
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Value not found\n");
        return;
    }
    if (prior == NULL) {
        *head = temp->next;
    }
    else {
        prior->next = temp->next;
    }
    if (temp->next != NULL) {
        temp->next->prior = prior;
    }
    free(temp);
}

6、主函数

int main() {
    Node* list = NULL;
    int n, choice, position, data;
    printf("请输入数字n: ");
    scanf("%d", &n);
    printf("请输入%d个数字:\n", n);
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        append(&list, num);
    }
    printf("当前列表: ");
    printList(list);
    printf("请输入1和2选择操作（1：插入 2：删除）\n");
    scanf("%d", &choice);
    if (choice == 1) {
        printf("请输入插入位置和插入的数字: ");
        scanf("%d %d", &position, &data);
        insertAtPosition(&list, position, data);
    }
    else if (choice == 2) {
        printf("请输入要删除的数字: ");
        scanf("%d", &data);
        deleteValue(&list, data);
    }
    else {
        printf("无效选择\n");
    }
    printf("最终列表: ");
    printList(list);
    // 释放链表内存  
    Node* temp;
    while (list != NULL) {
        temp = list;
        list = list->next;
        free(temp);
    }
    return 0;
}

运行结果

        输入数字个数n，并依次输入这n个元素

        选择下一步操作（1插入，2删除）

您的点赞和关注是我持续更新下去的动力！！


http://www.kler.cn/a/402759.html

相关文章：

  • (动画)Qt控件 QLCDNumer
  • 【数据结构 | C++】部落
  • logstash 解析数组格式json数据：split, json
  • C语言中const char *字符进行切割实现
  • 「Mac玩转仓颉内测版30」基础篇10 - 区间类型详解
  • map和redis关系
  • pcap_set_timeout()函数
  • 文件 IO：高效读取文件的一些注意事项
  • SQL面试题——复杂窗口定义
  • 【机器学习chp5】线性回归
  • 【Python】30个Python爬虫的实战项目！！！(附源码)
  • 蓝牙电话-如何自动切换手机SIM卡（预研方向）
  • 985研一学习日记 - 2024.11.17
  • Map接口的特点
  • 使用 Postman 设置 Bearer Token 进行身份验证
  • 优化算法：粒子群算法
  • AI编程入门指南002：API、数据库和应用部署
  • 02向量与矩阵方程
  • Python学习30天
  • spring为何要用三级缓存
  • elasticsearch7.10.2集群部署带认证
  • 查找redis数据库的路径
  • 百度世界2024精选公开课：基于地图智能体的导航出行AI应用创新实践
  • K8S资源限制之ResourceQuota
  • 【qt】控件QLabel
  • Spring事务——针对实习面试