〇、写在前面
小伙伴们要多多体会，不要全部借鉴哦！文章来源地址https://www.toymoban.com/news/detail-719951.html
一、顺序表的初始化、查找、插入、删除、输出、撤销
/*
_* _ coding : utf - 8 _ * _
Time : 2022/9/4 21 : 15
Author : Yan Fanyu
Version : V 0.1
File : main.cpp
Describe : Github link : https://github.com/YanFanYu2001
*/
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;
// 1、参照课本程序2.1～2.7，编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。
typedef struct {
int n; //顺序表的长度
int maxLength; //顺序表的最大长度
ElemType* element; //存放动态分配一维数组首地址
}SeqList;
//顺序表初始化
Status Init(SeqList* L, int mSize) {
L->maxLength = mSize; // 容量设为mSize
L->n = 0; // 大小设为0
L->element = (ElemType*)malloc(sizeof(ElemType) * mSize); // 申请容量大小的动态空间
if (L->element) // 如果申请成功，返回OK
return OK;
exit(0); // 申请不成功，退出
}
//顺序表的查找
Status Find(SeqList seqList, int i, ElemType* x) {
if (i < 0 || i > seqList.n - 1) {
return ERROR; //判断元素下标i是否越界
}
*x = seqList.element[i]; //取出element[i]的值通过参数x返回
return OK;
}
//初始化插入
Status Insert(SeqList* seqList, int i, ElemType x) {
int j;
if (i<-1 || i>seqList->n - 1) //判断下标i是否越界
return ERROR;
if (seqList->n == seqList->maxLength) //判断顺序表存储空间是否已满
return ERROR;
for (j = seqList->n - 1; j > i; j--) {
seqList->element[j + 1] = seqList->element[j]; //从后往前逐个后移元素
}
seqList->element[i + 1] = x; //将新元素放入下标为i+1的位置
seqList->n++; //长度+1
return OK;
}
//顺序表的删除
Status Delete(SeqList* seqList, int i) {
int j;
if (i<0 || i>seqList->n - 1) { //下标i是否越界
return ERROR;
}
if (!seqList->n) { //顺序表是否为空
return ERROR;
}
for (j = i + 1; j < seqList->n; j++) {
seqList->element[j - 1] = seqList->element[j]; //从前往后逐个前移元素
}
seqList->n--; //表长减1
return OK;
}
//顺序表输出
int Output(SeqList seqList) {
int i;
if (!seqList.n)
return ERROR; //判断顺序表是否为空
for (i = 0; i <= seqList.n - 1; i++)
printf("%d ", seqList.element[i]); //从前往后逐个输出元素
return OK;
}
// 顺序表的撤销
void Destroy(SeqList* L) {
(*L).n = 0;
(*L).maxLength = 0;
free((*L).element);
}
int main()
{
int i, findResult;
SeqList list;
Init(&list, 10);
//对线性表初始化，初始化容量为10
for (i = 0; i < 10; i++) {
Insert(&list, i - 1, i); //将0-8插入到顺序表中
}
printf("插入0~10后，表为：\n");
Output(list);
printf("\n");
Delete(&list, 0); //删除0
printf("删除下表为0处的元素后，表为：\n");
Output(list);
Find(list, 2, &findResult); //查找下标为2的元素并输出
printf("\n下表为2处的元素值为:");
printf("%d", findResult);
Destroy(&list);
return 0;
}
/*
1、数据结构：
顺序表SeqList的数据结构为C语言结构体,
内含三个数据成员n(线性表的实际大小), maxLength(线性表的存储容量), element(线性表存储元素的首地址)
核心算法:
1、首先创建一个线性表结构体变量SeqList list; 调用Init(SeqList* L, int mSize)对线性表进行存储容量的设置和
存储空间内存的申请。
2、插入算法：调用 Insert(SeqList* seqList, int i, ElemType x), 将传入的元素的值 x 放到 顺序表第 i+1 个位置上。
首先从线性表的最后一个元素开始从后往前逐个后移元素，直到将第i+1个元素移动到第i+2个位置，然后将要插入的元素插入到线性表的
第i+1个位置上。
3、删除算法： 调用 Delete(SeqList* seqList, int i), 传入坐标处的元素删除。
首先从线性表的第i+1的未知开始, 依次将元素前移。
Status Init(SeqList* L, int mSize);
Status Find(SeqList seqList, int i, ElemType* x);
Status Insert(SeqList* seqList, int i, ElemType x);
int Output(SeqList seqList);
void Destroy(SeqList* L);
*/
二、带表头结点单链表的初始化、查找、插入、删除、输出、撤销
/*
_* _ coding : utf - 8 _ * _
Time : 2022/9/4 21 : 15
Author : Yan Fanyu
Version : V 0.1
File : main.cpp
Describe : Github link : https://github.com/YanFanYu2001
*/
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;
//2、已知带表头结点单链表的类型定义如下：
//参照课本程序2.8～2.14，编写程序，完成带表头结点单链表的初始化、查找、插入、删除、输出、撤销等操作。
typedef struct Node {
ElemType element; //结点的数据域
struct Node* link; //结点的指针域
}Node;
typedef struct {
struct Node* head; //表头结点
int n;
}ListHeader;
Status Init(ListHeader* h);
Status Find(ListHeader* h, int i, ElemType* x);
Status Insert(ListHeader* h, int i, ElemType x);
Status Delete(ListHeader* h, int i);
Status Output(ListHeader* h);
void Destroy(ListHeader* h);
//带表头结点单链表的初始化
Status Init(ListHeader* h) {
h->head = (Node*)malloc(sizeof(Node)); //生成表头结点
if (!h->head) {
return ERROR;
}
h->head->link = NULL; //设置单链表为空表
h->n = 0;
return OK;
}
//带表头结点单链表的查找
Status Find(ListHeader* h, int i, ElemType* x) {
Node* p;
int j;
if (i < 0 || i > h->n - 1) {
return ERROR;
}
p = h->head->link;
for (j = 0; j < i; j++) {
p = p->link;
}
*x = p->element;
return OK;
}
//带表头结点单链表的插入
Status Insert(ListHeader* h, int i, ElemType x) {
Node* p, * q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head; //从头结点开始找ai元素所在的结点p
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node)); //生成新结点q
q->element = x;
// 将 q 插在 p 和 p->link 之间
q->link = p->link; //新结点q插在p之后
p->link = q;
h->n++;
return OK;
}
//带表头结点单链表的删除
Status Delete(ListHeader* h, int i) {
int j;
Node* p, * q;
if (!h->n) {
return ERROR;
if (i<0 || i>h->n - 1) {
return ERROR;
}
}
q = h->head;
for (j = 0; j < i; j++) {
q = q->link;
}
p = q->link;
// 将 q->link 改为 q->link->link; 即q的下一个节点的下一个，再将q的下一个节点删除
q->link = q->link->link;
free(p);
h->n--;
return OK;
}
//带表头结点单链表的输出
Status Output(ListHeader* h) {
Node* p;
if (!h->n)
return ERROR;
p = h->head->link;
printf("the linklist is:");
while (p) {
printf("%d ", p->element);
p = p->link;
}
printf("\n");
return OK;
}
//带表头结点单链表的撤销
void Destroy(ListHeader* h) {
Node* p, * q;
while (h->head->link) {
q = h->head->link;
p = h->head->link->link;
free(h->head->link);
h->head = q;
}
}
int main()
{
int i, x;
ListHeader list;
Init(&list);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i); //插入0~8
}
printf("插入0~8，表为：\n");
Output(&list);
printf("\n");
Delete(&list, 0); //删除0
printf("删除下标为0处的元素，表为：\n");
Output(&list);
printf("\n");
Delete(&list, 0); //删除0
printf("删除下标为0处的元素，表为：\n");
Output(&list);
printf("\n");
Find(&list, 0, &x); //查找下标为0的元素
printf("查找下标为0的元素值为：\n");
printf("%d ", x);
printf("\n");
Destroy(&list);
printf("\n\n\n");
return 0;
}
/*
参照课本程序2.8～2.14，编写程序，完成带表头结点单链表的初始化、查找、插入、删除、输出、撤销等操作。
1、初始化：先为表头节点申请一个节点的空间，
*/
三、多项式
/*
_* _ coding : utf - 8 _ * _
Time : 2022/9/4 21 : 15
Author : Yan Fanyu
Version : V 0.1
File : main.cpp
Describe : Github link : https://github.com/YanFanYu2001
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct PNode {
int coef; //系数
int exp; //指数
struct PNode* link;
}PNode;
typedef struct {
struct PNode* head;
}Polynominal;
//多项式的创建
void Create(Polynominal* p) {
PNode* pn, * pre, * q;
p->head = (PNode*)malloc(sizeof(PNode));
p->head->exp = -1;
p->head->link = p->head; //对教材做了修改
//p->head->link = NULL; //教材原代码
printf("请输入表达式的项数\n");
int nn = 0;
scanf_s("%d", &nn);
for (int i = 0; i < nn; i++)
{
pn = (PNode*)malloc(sizeof(PNode));
printf("\n请输入系数:\n");
scanf_s("%d", &pn->coef);
printf("请输入阶数:\n");
scanf_s("%d", &pn->exp);
if (pn->exp == -1) break;
pre = p->head;
q = p->head->link;
while (q && q->exp > pn->exp) {
pre = q;
q = q->link;
}
pn->link = q;
pre->link = pn;
}
}
//多项式输出
void Output(Polynominal p) {
printf("expression = ");
PNode* q;
int flag = 1; //打标记,记录是否为第一项
q = p.head->link;
if (!q) {
return;
}
while (q != p.head) {
if (!flag && (q->coef > 0)) printf("+"); //在非第一项的正系数前输出+号
flag = 0; //flag置为0,表示不是第一项
if (q->coef == 0) { //当前项系数为0
return;
}
if (q->coef != 1) { //当前项系数不为0&&不为1
printf("%d", q->coef);
}
switch (q->exp) { //判断当前项指数
case 0:break; //当前项指数为0,退出
case 1:printf("X"); break; //当前项指数为1,输出X
default:printf("X^%d", q->exp); break; //当前项指数不为0,也不为1
}
q = q->link;
}
printf("\n");
}
//多项式的相加,结果存入qx中
void Add(Polynominal* px, Polynominal* qx) {
PNode* q, * q1 = qx->head, * p, * p1, * temp; //q1指向qx的表头结点
p = px->head->link; //p指向多项式px的第一个结点
p1 = px->head;
q = q1->link; //q1是q的前驱
while (p->exp >= 0) {
while (p->exp < q->exp) { //跳过q->exp大的项
q1 = q;
q = q->link;
}
// 如果两多项式的阶数相等，则对应系数相加，结果存放在qx中
if (p->exp == q->exp) {
q->coef = q->coef + p->coef;
// 如果相加后系数为0
if (q->coef == 0) {
q1->link = q->link; //删除q
free(q); //释放q的空间
q = (PNode*)malloc(sizeof(PNode));
q = q1->link; //重置q指针
p = p->link;
}
else { //若相加后系数不为0
q1 = q; //q1后移
q = q->link;
p = p->link; //p也后移
}
}
else { //p->exp > q->exp的情况
temp = (PNode*)malloc(sizeof(PNode)); //以p的系数和指数生成新结点
temp->coef = p->coef;
temp->exp = p->exp;
temp->link = q1->link;
q1->link = temp;
q1 = q1->link;
p = p->link;
}
}
}
// 多项式乘法 (结果存放在qx1中)
void Multiply(Polynominal* px, Polynominal* qx) {
Polynominal qx1, qx2;
PNode* q1, * q2, * q3, * q4, * pre = (PNode*)malloc(sizeof(PNode)), * q;
qx1.head = (PNode*)malloc(sizeof(PNode)); //生成新多项式qx1
qx1.head->exp = -1;
qx1.head->link = qx1.head; //qx1改造成循环链表
q1 = px->head; //q1指向px的第一项
q2 = qx->head; //q2指向qx的第一项
while (q2->exp != -1) { //当q2的指数不为-1时,px先和qx的每一项相乘
q3 = (PNode*)malloc(sizeof(PNode)); //q3存放相乘的结果
// 系数相乘，阶数相加
q3->coef = q1->coef * q2->coef;
q3->exp = q1->exp + q2->exp;
if (qx1.head->link->exp == -1) { //q3插入到qx1多项式第一项中
q3->link = qx1.head->link;
qx1.head->link = q3;
pre = qx1.head->link;
}
else { //q3插入到qx1多项式最后一项中
q3->link = qx1.head;
pre->link = q3;
pre = pre->link;
}
q2 = q2->link;
}
// q1 指向 q1表达式的下一项
q1 = q1->link; //q1后移一位
while (q1->exp != -1) { //px剩下来每一项都和qx每一项相乘
q2 = q2->link;
qx2.head = (PNode*)malloc(sizeof(PNode)); //生成新多项式qx2
qx2.head->exp = -1;
qx2.head->link = qx2.head; // 指向自己
// 遍历 q2 的每一项
while (q2->exp != -1) {
q4 = (PNode*)malloc(sizeof(PNode));
q4->coef = q1->coef * q2->coef;
q4->exp = q1->exp + q2->exp;
if (qx2.head->link->exp == -1) {
q4->link = qx2.head->link;
qx2.head->link = q4;
pre = qx2.head->link;
}
else {
q4->link = qx2.head;
pre->link = q4;
pre = pre->link;
}
q2 = q2->link;
}
Add(&qx2, &qx1); //合并同类项
q1 = q1->link;
}
Output(qx1);
}
int main() {
Polynominal p, q;
int x;
printf("请输入第一个表达式:\n");
Create(&p);
Output(p);
printf("\n\n请输入第二个表达式\n");
Create(&q);
Output(q);
printf("请输入选项\n 1: 加法 2:乘法\n");
scanf_s("%d", &x);
switch (x) {
case 0: break;
//选择加法还是乘法功能
case 1:printf("加法结果:\n");
Add(&p, &q);
Output(q);
break;
case 2:printf("乘法结果:\n");
Multiply(&p, &q);
break;
default: break;
}
return 0;
}
/*
* typedef struct PNode {
int coef; //系数
int exp; //指数
struct PNode* link;
}PNode;
typedef struct {
struct PNode* head;
}Polynominal;
*
先创建结构体PNode 表示多项式的某一项，内含三个成员变量，分别是coef(项的系数)，exp(项的阶数)，link(下一项的地址)
再创建多项式结构体Polynominal，内含一个成员变量head（多项式首项的地址）
算法：
1、先创建两个表达式结构体指针变量Polynominal* p q;
2、p q 分别调用 Creat(Polynominal*) 函数对多形式进行初始化
初始化算法如下：
为多项式的头指针即多项式结构体的成员变量进行动态空间申请。将头指针即多项式的第一项的阶数初始化为-1
从控制台获取用户要输入的多项式的项数，记为nn
循环 nn 次，用户依次输入系数，阶数，系数，阶数······ 直至输入完毕
算法对输入的多项式实行按该项阶数降序的顺序进行顺序存储。
算法实现过程是：
1、多项式的创建
*/
文章来源：https://www.toymoban.com/news/detail-719951.html
到了这里，关于南京邮电大学数据结构实验一（线性表的基本运算及多项式的算术运算）（代码篇）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
