数据结构与算法2---链表

embedded/2024/10/10 9:42:43/

线性表：1.有限的序列⒉.序列中的每一个元素都有唯一的前驱和后继，除了开头和结尾两个节点

顺序表：分配一块连续的内存去存放这些元素，例如编程语言中的数组

链表:内存是不连续的，元素会各自被分配一块内存，内存和内存之间用指针进行相连


1、单链表

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>  
#include <stdlib.h>   //开辟空间typedef struct Node {int data;struct Node* next;
}Node;//带头结点的初始化单链表
Node* initList() {Node* list = (Node*)malloc(sizeof(Node));list->data = 0;list->next = NULL;return list;
}//头插法
void headInsert(Node* list, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = list->next;list->next = node;list->data++;
}//尾插法
void tailInsert(Node* list, int data) {Node* head = list;Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;list = list->next;while (list->next) {list = list->next;}	//找到最后的结点list->next = node;head->data++;
}//删除
void delete(Node* list, int data) {Node* pre = list;Node* current = list->next;while (current) {if (current->data == data) {pre->next = current->next;free(current);break;}pre = current;current = current->next;}list->data--;
}void printList(Node* list) {list = list->next;while (list) {printf("%d ", list->data);list = list->next;}printf("\n");
}int main() {Node* list = initList();headInsert(list, 1);headInsert(list, 2);headInsert(list, 3);printList(list);tailInsert(list, 4);tailInsert(list, 5);tailInsert(list, 6);printList(list);delete(list, 3);printList(list);return 0;
}

这里说一下，头插尾插的时候，都当作有很多的时候插入，最后处理开始会好很多

2、单循环链表

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>  
#include <stdlib.h>   //开辟空间typedef struct Node {int data;struct Node* next;
}Node;Node* initList() {Node* L = (Node*)malloc(sizeof(Node));L->data = 0;L->next = L;return L;
}//头插法
void headInsert(Node* L, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = L->next;L->next = node;L->data++;
}//尾插法
void tailInsert(Node* L, int data) {Node* n = L;Node* node = (Node*)malloc(sizeof(Node));node->data = data;while (n->next != L) {n = n->next;}node->next = L;n->next = node;L->data++;
}//删除
int delete(Node* L, int data) {Node* pre = L;Node* node = L->next;while (node != L) {if (node->data == data) {pre->next = node->next;free(node);L->data--;return 1;}pre = node;node = node->next;}return 0;
}void printList(Node* L) {Node* node = L->next;while (node != L) {printf("%d ", node->data);node = node->next;}printf("NULL\n");
}int main() {Node* L = initList();headInsert(L, 1);headInsert(L, 2);headInsert(L, 3);printList(L);tailInsert(L, 4);tailInsert(L, 5);tailInsert(L, 6);printList(L);delete(L, 3);printList(L);return 0;
}

3、双链表

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>  
#include <stdlib.h>   //开辟空间typedef struct Node {int data;struct Node* pre;struct Node* next;
}Node;//带头结点
Node* initList() {Node* L = (Node*)malloc(sizeof(Node));L->data = 0;L->pre = NULL;L->next = NULL;return L;
}void headInsert(Node* L, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;if (L->data == 0) {//链表为空node->next = L->next;	//NULLnode->pre = L;L->next = node;L->data++;}else {node->pre = L;node->next = L->next;L->next->pre = node;L->next = node;L->data++;}
}void tailInsert(Node* L, int data) {Node* node = L;Node* n = (Node*)malloc(sizeof(Node));n->data = data;while (node->next) {node = node->next;}	//找到最后一个n->next = node->next;	//NULLnode->next = n;n->pre = node;L->data++;
}int delete(Node* L, int data) {Node* node = L->next;while (node) {if (node->data == data && node->next != NULL) {node->pre->next = node->next;node->next->pre = node->pre;free(node);L->data--;return 1;}if (node->data == data && node->next == NULL) {node->pre->next = node->next;free(node);L->data--;return 1;}node = node->next;}return 0;
}void printList(Node* L) {Node* node = L->next;while (node) {printf("%d ", node->data);node = node->next;}printf("NULL\n");
}int main() {Node* L = initList();headInsert(L, 1);headInsert(L, 2);headInsert(L, 3);printList(L);tailInsert(L, 4);tailInsert(L, 5);tailInsert(L, 6);printList(L);delete(L, 1);printList(L);delete(L, 6);printList(L);return 0;
}

4、双循环链表

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>  
#include <stdlib.h>   //开辟空间typedef struct Node {int data;struct Node* pre;struct Node* next;
}Node;Node* initList() {Node* L = (Node*)malloc(sizeof(Node));L->data = 0;L->pre = L;L->next = L;return L;
}void headInsert(Node* L, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;if (L->data == 0) {//链表为空node->pre = L;node->next = L->next;L->next = node;L->pre = node;L->data++;}else {//链表不为空node->pre = L;node->next = L->next;L->next->pre = node;L->next = node;L->data++;}
}void tailInsert(Node* L, int data) {Node* node = L->pre;Node* n = (Node*)malloc(sizeof(Node));n->data = data;n->pre = node;n->next = L;node->next = n;L->pre = n;L->data++;
}int delete(Node* L, int data) {Node* node = L->next;while (node != L) {if (node->data == data) {node->pre->next = node->next;node->next->pre = node->pre;L->data--;return 1;}node = node->next;}return 0;
}void printList(Node* L) {Node* node = L->next;while (node != L) {printf("%d ", node->data);node = node->next;}printf("NULL\n");
}int main() {Node* L = initList();headInsert(L, 1);headInsert(L, 2);headInsert(L, 3);printList(L);tailInsert(L, 4);tailInsert(L, 5);tailInsert(L, 6);printList(L);delete(L, 1);printList(L);delete(L, 6);printList(L);return 0;
}

五、多项式相加

【问题描述】编写一个程序用单链表存储多项式，并实现两个一元多项式A与B相加的函数。A，B刚开始是无序的，A与B之和按降序排列。例如：
                        多项式A:  1.2X^0  2.5X^1  3.2X^3  -2.5X^5
                        多项式B:  -1.2X^0  2.5X^1  3.2X^3   2.5X^5   5.4X^10
                        多项式A与B之和：5.4X^10  6.4X^3  5X^1
【输入形式】第一行第一个数据n代表多项式的总项数，后面的2*n个数据，每一对代表对应的某一项的系数和指数，第二行类似，第三行的数据x要查询第几项
【输出形式】多项式中某一项的系数与指数，系数保留一位小数

【输入样例】
4 1.2 0 2.5 1 3.2 3 -2.5 5
5 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 10
2

【输出样例】

6.4 3

【样例说明】
第一个多项式的系数与指数对，以空格隔开
第二个多项式的系数与指数对，以空格隔开
输出第２项的系数与指数，系数与指数间用空格隔开，系数保留一位小数

【评分标准】必须用链表实现

#include<stdio.h>
#include<stdlib.h>
typedef struct node* list;
struct node {float coef;int expon;list next;
};
list create()//最基本的构建其实是最好的方法 我也不多说了
{list q, r, head;int i;head = (list)malloc(sizeof(struct node));r = head;int n;scanf("%d", &n);for (i = 0; i < n; i++){q = (list)malloc(sizeof(struct node));scanf("%f %d", &q->coef, &q->expon);r->next = q;r = q;}r->next = NULL;return head;
}
list sort(list head)//这是一个排序的函数
{list p = head->next, q, r;if (p != NULL){r = p->next;p->next = NULL;p = r;while (p != NULL){r = p->next;q = head;while (q->next != NULL && q->next->expon > p->expon)q = q->next;p->next = q->next;q->next = p;p = r;}}return head;}
list add(list a, list b)//排好序的多项式相加
{list p, q, r, c, s;p = a->next;q = b->next;c = (list)malloc(sizeof(struct node));r = c;while (p && q) {if (p->expon < q->expon) {s = (list)malloc(sizeof(struct node));s->expon = q->expon;s->coef = q->coef;r->next = s;r = s;q = q->next;}else if (p->expon > q->expon) {s = (list)malloc(sizeof(struct node));s->expon = p->expon;s->coef = p->coef;r->next = s;r = s;p = p->next;}else {double sum = p->coef + q->coef;if (sum != 0) {s = (list)malloc(sizeof(struct node));s->coef = sum;s->expon = p->expon;r->next = s;r = s;p = p->next;q = q->next;}else {p = p->next;q = q->next;}}}if (p == NULL && q == NULL)r->next = NULL;if (p != NULL) {r->next = p;}if (q != NULL) {r->next = q;}return c;
}
void show(list l)//输出函数
{int n;list p = l;scanf("%d", &n);while (n--) {p = p->next;}printf("%.1f %d", p->coef, p->expon);//这个格式十分重要啊printf("\n");
}
int main()
{list a, b, c, d, e;a = create();b = create();d = sort(a);e = sort(b);c = add(d, e);show(c);return 0;}


http://www.ppmy.cn/embedded/50590.html

相关文章

Web前端设计工程师：挑战与机遇并存的职业探索

Web前端设计工程师：挑战与机遇并存的职业探索

Web前端设计工程师&#xff1a;挑战与机遇并存的职业探索 在数字化浪潮的推动下&#xff0c;Web前端设计工程师成为了互联网行业的核心力量。他们不仅需要掌握深厚的技术功底&#xff0c;还需具备出色的设计思维与创新能力。本文将从四个方面、五个方面、六个方面和七个方面&a…
阅读更多...
微信小程序学习（六）：常用原生 API

微信小程序学习（六）：常用原生 API

&#x1f517;API官方文档 1、网络请求 wx.request({// 接口地址&#xff0c;仅为示例&#xff0c;并非真实的接口地址url: example.php,// 请求的参数data: { x: },// 请求方式 GET|POST|PUT|DELETEmethod: GET,success (res) {console.log(res.data)},fail(err) {console.…
阅读更多...
C# —— while循环语句

C# —— while循环语句

作用 让顺序执行的代码 可以停下来 循环执行某一代码块 // 条件分支语句: 让代码产生分支 进行执行 // 循环语句 : 让代码可以重复执行 语法 while循环 while (bool值) { 循环体(条件满足时执行的代码块) …
阅读更多...
LeetCode 每日一题 2748. 美丽下标对的数目

LeetCode 每日一题 2748. 美丽下标对的数目

Hey编程小伙伴们&#x1f44b;&#xff0c;今天我要带大家一起解锁力扣上的一道有趣题目—— 美丽下标对的数目 - 力扣 (LeetCode)。这不仅是一次编程挑战&#xff0c;更是一次深入理解欧几里得算法判断互质的绝佳机会&#xff01;&#x1f389; 问题简介 题目要求我们给定一…
阅读更多...
LLM自动化对齐技术

LLM自动化对齐技术

近年来&#xff0c;大语言模型&#xff08;LLMs&#xff09;的快速发展&#xff0c;极大地重塑了人工智能的格局。一致性是塑造与人类意图和价值观相对应的LLMs行为的核心&#xff0c;例如&#xff0c;教导LLMs遵循响应过程中“有帮助&#xff08;Helpful&#xff09;、无害(Ha…
阅读更多...
ACM算法学习路线、清单

ACM算法学习路线、清单

入门 模拟、暴力、贪心、高精度、排序 图论 搜索 BFS、DFS、IDDFS、IDA*、A*、双向BFS、记忆化 最短路 SPFA、bellman-fort(队列优化)、Dijkstra(堆优化)、Johnson、Floyd、差分约束、第k短路 树 树的重心和直径、dfs序、树链刨分与动态树、LCA、Prufer编码及Cayley定理…
阅读更多...
Linux系统之配置Nginx负载均衡

Linux系统之配置Nginx负载均衡

Linux系统之配置Nginx负载均衡 一、Nginx介绍1.1 Nginx简介1.2 Nginx反向代理1.3 相关概念二、本次实践介绍2.1 本次实践简介2.2 本次实践环境规划三、部署两台web服务器3.1 运行两个Docker容器3.2 编辑测试文件四、配置负载均衡4.1 安装nginx软件4.2 编辑nginx配置文件4.3 启动…
阅读更多...
四十九、openlayers官网示例Immediate Rendering (Geographic)——在地图上绘制星空动画效果

四十九、openlayers官网示例Immediate Rendering (Geographic)——在地图上绘制星空动画效果

官网demo地址&#xff1a; Immediate Rendering (Geographic) 首先先创建1000个随机点&#xff0c;创建点对象。 const n 1000;const geometries new Array(n);for (let i 0; i < n; i) {const lon 360 * Math.random() - 180;const lat 180 * Math.random() - 90;ge…
阅读更多...
最新文章

Copyright @ 2022~2023