网站链接改名怎做301,天津百度推广公司地址,网站改版 价格,闲置tp路由自己做网站文章目录验证性实验实现顺序表各种基本运算的算法放码sqlist.hsqlist.cppexp2-1.cpp结果实现单链表各种基本运算的算法放码linklist.hlinklist.cppexp2-2.cpp结果实现双链表各种基本运算的算法放码dlinklist.hdlinklist.cppexp2-3.cpp结果实现循环单链表各种基本运算的算法放码…
文章目录验证性实验实现顺序表各种基本运算的算法放码sqlist.hsqlist.cppexp2-1.cpp结果实现单链表各种基本运算的算法放码linklist.hlinklist.cppexp2-2.cpp结果实现双链表各种基本运算的算法放码dlinklist.hdlinklist.cppexp2-3.cpp结果实现循环单链表各种基本运算的算法放码clinklist.hclinklist.cppexp2-4.cpp结果实现循环双链表各种基本运算的算法放码cdlinklist.hcdlinklist.cppexp2-5.cpp结果设计性实验将单链表按基准划分说明放码结果将两个单链表合并为一个单链表说明放码结果求集合用单链表表示的并、交和差运算说明放码结果实现两个多项式相加运算说明放码结果综合性实验实现两个多项式相乘运算说明放码结果职工信息的综合运算说明放码结果用单链表实现两个大整数相加运算说明放码结果验证性实验
实现顺序表各种基本运算的算法
放码
sqlist.h
#ifndef SQLIST_H
#define SQLIST_H#define MaxSize 50
typedef char ElemType;
typedef struct
{ElemType data[MaxSize]; //存放顺序表元素int length; //存放顺序表的长度
} SqList; //声明顺序表的类型void CreateList(SqList *L, ElemType a[], int n); //整体建立顺序表
void InitList(SqList *L); //初始化线性表
void DestroyList(SqList *L); //销毁线性表
bool ListEmpty(SqList *L); //判线性表是否为空表
int ListLength(SqList *L); //求线性表的长度
void DispList(SqList *L); //输出线性表
bool GetElem(SqList *L, int i, ElemType e); //求线性表中第i个元素值
int LocateElem(SqList *L, ElemType e); //查找第一个值域为e的元素序号
bool ListInsert(SqList *L, int i, ElemType e); //插入第i个元素
bool ListDelete(SqList *L, int i, ElemType e); //删除第i个元素#endifsqlist.cpp
//顺序表运算算法
#include stdio.h
#include malloc.h
#include sqlist.hvoid CreateList(SqList * L, ElemType a[], int n) //整体建立顺序表
{L (SqList *)malloc(sizeof(SqList));for (int i 0; i n; i)L-data[i] a[i];L-length n;
}void InitList(SqList * L) //初始化线性表
{L (SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间L-length 0;
}void DestroyList(SqList * L) //销毁线性表
{free(L);
}bool ListEmpty(SqList * L) //判线性表是否为空表
{return (L-length 0);
}int ListLength(SqList * L) //求线性表的长度
{return (L-length);
}void DispList(SqList * L) //输出线性表
{for (int i 0; i L-length; i)printf(%c , L-data[i]);printf(\n);
}bool GetElem(SqList * L, int i, ElemType e) //求线性表中第i个元素值
{if (i 1 || i L-length)return false;e L-data[i - 1];return true;
}int LocateElem(SqList * L, ElemType e) //查找第一个值域为e的元素序号
{int i 0;while (i L-length L-data[i] ! e) i;if (i L-length)return 0;elsereturn i 1;
}bool ListInsert(SqList * L, int i, ElemType e) //插入第i个元素
{int j;if (i 1 || i L-length 1)return false;i--; //将顺序表位序转化为elem下标for (j L-length; j i; j--) //将data[i]及后面元素后移一个位置L-data[j] L-data[j - 1];L-data[i] e;L-length; //顺序表长度增1return true;
}bool ListDelete(SqList * L, int i, ElemType e) //删除第i个元素
{int j;if (i 1 || i L-length)return false;i--; //将顺序表位序转化为elem下标e L-data[i];for (j i; j L-length - 1; j) //将data[i]之后的元素前移一个位置L-data[j] L-data[j 1];L-length--; //顺序表长度减1return true;
}exp2-1.cpp
//文件名:exp2-1.cpp
#include sqlist.h
#include stdio.hint main()
{SqList *L;ElemType e;printf(顺序表的基本运算如下:\n);printf( (1)初始化顺序表L\n);InitList(L);printf( (2)依次插入a,b,c,d,e元素\n);ListInsert(L,1,a);ListInsert(L,2,b);ListInsert(L,3,c);ListInsert(L,4,d);ListInsert(L,5,e);printf( (3)输出顺序表L:);DispList(L);printf( (4)顺序表L长度:%d\n,ListLength(L));printf( (5)顺序表L为%s\n,(ListEmpty(L)?空:非空));GetElem(L,3,e);printf( (6)顺序表L的第3个元素:%c\n,e);printf( (7)元素a的位置:%d\n, LocateElem(L,a));printf( (8)在第4个元素位置上插入f元素\n);ListInsert(L, 4, f);printf( (9)输出顺序表L:);DispList(L);printf( (10)删除L的第3个元素\n);ListDelete(L,3,e);printf( (11)输出顺序表L:);DispList(L);printf( (12)释放顺序表L\n);DestroyList(L);return 1;
}结果
顺序表的基本运算如下:(1)初始化顺序表L(2)依次插入a,b,c,d,e元素(3)输出顺序表L:a b c d e(4)顺序表L长度:5(5)顺序表L为非空(6)顺序表L的第3个元素:c(7)元素a的位置:1(8)在第4个元素位置上插入f元素(9)输出顺序表L:a b c f d e(10)删除L的第3个元素(11)输出顺序表L:a b f d e(12)释放顺序表L
请按任意键继续. . .实现单链表各种基本运算的算法
放码
linklist.h
#ifndef LINKLIST_H
#define LINKLIST_Htypedef int ElemType;
typedef struct LNode {ElemType data;struct LNode *next; //指向后继结点
}LinkNode; //声明双链表结点类型void CreateListF(LinkNode *L, ElemType a[], int n); //头插法建双链表
void CreateListR(LinkNode *L, ElemType a[], int n); //尾插法建双链表
void InitList(LinkNode *L); //初始化线性表
void DestroyList(LinkNode *L); //销毁线性表
bool ListEmpty(LinkNode *L); //判线性表是否为空表
int ListLength(LinkNode *L); //求线性表的长度
void DispList(LinkNode *L); //输出线性表
bool GetElem(LinkNode *L, int i, ElemType e); //求线性表中第i个元素值
int LocateElem(LinkNode *L, ElemType e); //查找第一个值域为e的元素序号
bool ListInsert(LinkNode *L, int i, ElemType e); //插入第i个元素
bool ListDelete(LinkNode *L, int i, ElemType e); //删除第i个元素#endiflinklist.cpp
//单链表运算算法
#include stdio.h
#include malloc.h
#include linklist.hvoid CreateListF(LinkNode *L, ElemType a[], int n) //头插法建立单链表
{LinkNode *s;L (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-next NULL;for (int i 0; i n; i) {s (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点ss-data a[i];s-next L-next; //将结点s插在原开始结点之前,头结点之后L-next s;}
}void CreateListR(LinkNode *L, ElemType a[], int n) //尾插法建立单链表
{LinkNode *s, *r;L (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-next NULL;r L; //r始终指向尾结点,开始时指向头结点for (int i 0; i n; i) {s (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点ss-data a[i];r-next s; //将结点s插入r结点之后r s;}r-next NULL; //尾结点next域置为NULL
}void InitList(LinkNode *L) //初始化线性表
{L (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-next NULL; //单链表置为空表
}void DestroyList(LinkNode *L) //销毁线性表
{LinkNode *pre L, *p pre-next;while (p ! NULL) {free(pre);pre p; //pre、p同步后移一个结点 p pre-next;}free(pre); //此时p为NULL,pre指向尾结点,释放它
}bool ListEmpty(LinkNode *L) //判线性表是否为空表
{return (L-next NULL);
}int ListLength(LinkNode *L) //求线性表的长度
{int i 0;LinkNode *p L; //p指向头结点,n置为0(即头结点的序号为0)while (p-next ! NULL) {i;p p-next;}return (i); //循环结束,p指向尾结点,其序号i为结点个数
}void DispList(LinkNode *L) //输出线性表
{LinkNode *p L-next; //p指向首结点while (p ! NULL) //p不为NULL,输出p结点的data域{printf(%c , p-data);p p-next; //p移向下一个结点}printf(\n);
}bool GetElem(LinkNode *L, int i, ElemType e) //求线性表中第i个元素值
{int j 0;if (i 0) return false; //i错误返回假LinkNode *p L; //p指向头结点,j置为0(即头结点的序号为0)while (j i p ! NULL) //找第i个结点p{j;p p-next;}if (p NULL) //不存在第i个数据结点,返回falsereturn false;else //存在第i个数据结点,返回true{e p-data;return true;}
}int LocateElem(LinkNode *L, ElemType e) //查找第一个值域为e的元素序号
{int i 1;LinkNode *p L-next; //p指向首结点,i置为1(即首结点的序号为1)while (p ! NULL p-data ! e) //查找data值为e的结点,其序号为i{p p-next;i;}if (p NULL) //不存在值为e的结点,返回0return (0);else //存在值为e的结点,返回其逻辑序号ireturn (i);
}bool ListInsert(LinkNode *L, int i, ElemType e) //插入第i个元素
{int j 0;if (i 0) return false; //i错误返回假LinkNode *p L, *s; //p指向头结点,j置为0(即头结点的序号为0)while (j i - 1 p ! NULL) //查找第i-1个结点p{j;p p-next;}if (p NULL) //未找到第i-1个结点,返回falsereturn false;else //找到第i-1个结点p,插入新结点并返回true{s (LinkNode *)malloc(sizeof(LinkNode));s-data e; //创建新结点s,其data域置为es-next p-next; //将结点s插入到结点p之后p-next s;return true;}
}bool ListDelete(LinkNode *L, int i, ElemType e) //删除第i个元素
{int j 0;if (i 0) return false; //i错误返回假LinkNode *p L, *q; //p指向头结点,j置为0(即头结点的序号为0)while (j i - 1 p ! NULL) //查找第i-1个结点{j;p p-next;}if (p NULL) //未找到第i-1个结点,返回falsereturn false;else //找到第i-1个结点p{q p-next; //q指向第i个结点if (q NULL) //若不存在第i个结点,返回falsereturn false;e q-data;p-next q-next; //从单链表中删除q结点free(q); //释放q结点return true; //返回true表示成功删除第i个结点}
}exp2-2.cpp
//文件名:exp2-2.cpp
#include stdio.h
#include linklist.hint main() {LinkNode * h;ElemType e;printf(单链表的基本运算如下:\n);printf( (1)初始化单链表h\n);InitList(h);printf( (2)依次采用尾插法插入a,b,c,d,e元素\n);ListInsert(h, 1, a);ListInsert(h, 2, b);ListInsert(h, 3, c);ListInsert(h, 4, d);ListInsert(h, 5, e);printf( (3)输出单链表h:);DispList(h);printf( (4)单链表h长度:%d\n, ListLength(h));printf( (5)单链表h为%s\n, (ListEmpty(h) ? 空 : 非空));GetElem(h, 3, e);printf( (6)单链表h的第3个元素:%c\n, e);printf( (7)元素a的位置:%d\n, LocateElem(h, a));printf( (8)在第4个元素位置上插入f元素\n);ListInsert(h, 4, f);printf( (9)输出单链表h:);DispList(h);printf( (10)删除h的第3个元素\n);ListDelete(h, 3, e);printf( (11)输出单链表h:);DispList(h);printf( (12)释放单链表h\n);DestroyList(h);return 1;
}结果
单链表的基本运算如下:(1)初始化单链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出单链表h:a b c d e(4)单链表h长度:5(5)单链表h为非空(6)单链表h的第3个元素:c(7)元素a的位置:1(8)在第4个元素位置上插入f元素(9)输出单链表h:a b c f d e(10)删除h的第3个元素(11)输出单链表h:a b f d e(12)释放单链表h
请按任意键继续. . .实现双链表各种基本运算的算法
放码
dlinklist.h
#ifndef DLINKLIST_H
#define DLINKLIST_Htypedef int ElemType;
typedef struct DNode {ElemType data;struct DNode *prior; //指向前驱结点struct DNode *next; //指向后继结点
}DLinkNode; //声明双链表结点类型void CreateListF(DLinkNode *L, ElemType a[], int n); //头插法建双链表
void CreateListR(DLinkNode *L, ElemType a[], int n); //尾插法建双链表
void InitList(DLinkNode *L); //初始化线性表
void DestroyList(DLinkNode *L); //销毁线性表
bool ListEmpty(DLinkNode *L); //判线性表是否为空表
int ListLength(DLinkNode *L); //求线性表的长度
void DispList(DLinkNode *L); //输出线性表
bool GetElem(DLinkNode *L, int i, ElemType e); //求线性表中第i个元素值
int LocateElem(DLinkNode *L, ElemType e); //查找第一个值域为e的元素序号
bool ListInsert(DLinkNode *L, int i, ElemType e); //插入第i个元素
bool ListDelete(DLinkNode *L, int i, ElemType e); //删除第i个元素#endifdlinklist.cpp
//双链表运算算法
#include stdio.h
#include malloc.h
#include dlinklist.hvoid CreateListF(DLinkNode *L, ElemType a[], int n) //头插法建双链表
{DLinkNode *s;L (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-prior L-next NULL;for (int i 0; i n; i) {s (DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s-data a[i];s-next L-next; //将结点s插在原开始结点之前,头结点之后if (L-next ! NULL) L-next-prior s;L-next s;s-prior L;}
}void CreateListR(DLinkNode *L, ElemType a[], int n) //尾插法建双链表
{DLinkNode *s, *r;L (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-prior L-next NULL;r L; //r始终指向终端结点,开始时指向头结点for (int i 0; i n; i) {s (DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s-data a[i];r-next s;s-prior r; //将结点s插入结点r之后r s;}r-next NULL; //尾结点next域置为NULL
}void InitList(DLinkNode *L) //初始化线性表
{L (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-prior L-next NULL;
}void DestroyList(DLinkNode *L) //销毁线性表
{DLinkNode *pre L, *p pre-next;while (p ! NULL) {free(pre);pre p; //pre、p同步后移一个结点p pre-next;}free(p);
}bool ListEmpty(DLinkNode *L) //判线性表是否为空表
{return (L-next NULL);
}int ListLength(DLinkNode *L) //求线性表的长度
{DLinkNode *p L;int i 0; //p指向头结点,i设置为0while (p-next ! NULL) //找尾结点p{i; //i对应结点p的序号p p-next;}return (i);
}void DispList(DLinkNode *L) //输出线性表
{DLinkNode *p L-next;while (p ! NULL) {printf(%c , p-data);p p-next;}printf(\n);
}bool GetElem(DLinkNode *L, int i, ElemType e) //求线性表中第i个元素值
{int j 0;DLinkNode *p L;if (i 0) return false; //i错误返回假while (j i p ! NULL) //查找第i个结点p{j;p p-next;}if (p NULL) //没有找到返回假 return false;else //找到了提取值并返回真{e p-data;return true;}
}int LocateElem(DLinkNode *L, ElemType e) //查找第一个值域为e的元素序号
{int i 1;DLinkNode *p L-next;while (p ! NULL p-data ! e) //查找第一个值域为e的结点p{i; //i对应结点p的序号p p-next;}if (p NULL) //没有找到返回0return (0);else //找到了返回其序号return (i);
}bool ListInsert(DLinkNode *L, int i, ElemType e) //插入第i个元素
{int j 0;DLinkNode *p L, *s; //p指向头结点,j设置为0if (i 0) return false; //i错误返回假while (j i - 1 p ! NULL) //查找第i-1个结点p{j;p p-next;}if (p NULL) //未找到第i-1个结点return false;else //找到第i-1个结点p{s (DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点ss-data e;s-next p-next; //将结点s插入到结点p之后if (p-next ! NULL)p-next-prior s;s-prior p;p-next s;return true;}
}bool ListDelete(DLinkNode *L, int i, ElemType e) //删除第i个元素
{int j 0;DLinkNode *p L, *q; //p指向头结点,j设置为0if (i 0) return false; //i错误返回假while (j i - 1 p ! NULL) //查找第i-1个结点p{j;p p-next;}if (p NULL) //未找到第i-1个结点return false;else //找到第i-1个节p{q p-next; //q指向第i个结点if (q NULL) //当不存在第i个结点时返回falsereturn false;e q-data;p-next q-next; //从双链表中删除结点qif (p-next ! NULL) //若p结点存在后继结点,修改其前驱指针p-next-prior p;free(q); //释放q结点return true;}
}exp2-3.cpp
//文件名:exp2-3.cpp
#include dlinklist.h
#include stdio.hint main() {DLinkNode *h;ElemType e;printf(双链表的基本运算如下:\n);printf( (1)初始化双链表h\n);InitList(h);printf( (2)依次采用尾插法插入a,b,c,d,e元素\n);ListInsert(h, 1, a);ListInsert(h, 2, b);ListInsert(h, 3, c);ListInsert(h, 4, d);ListInsert(h, 5, e);printf( (3)输出双链表h:);DispList(h);printf( (4)双链表h长度:%d\n, ListLength(h));printf( (5)双链表h为%s\n, (ListEmpty(h) ? 空 : 非空));GetElem(h, 3, e);printf( (6)双链表h的第3个元素:%c\n, e);printf( (7)元素a的位置:%d\n, LocateElem(h, a));printf( (8)在第4个元素位置上插入f元素\n);ListInsert(h, 4, f);printf( (9)输出双链表h:);DispList(h);printf( (10)删除h的第3个元素\n);ListDelete(h, 3, e);printf( (11)输出双链表h:);DispList(h);printf( (12)释放双链表h\n);DestroyList(h);return 1;
}结果
双链表的基本运算如下:(1)初始化双链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出双链表h:a b c d e(4)双链表h长度:5(5)双链表h为非空(6)双链表h的第3个元素:c(7)元素a的位置:1(8)在第4个元素位置上插入f元素(9)输出双链表h:a b c f d e(10)删除h的第3个元素(11)输出双链表h:a b f d e(12)释放双链表h
请按任意键继续. . .实现循环单链表各种基本运算的算法
放码
clinklist.h
#ifndef CLINKLIST_H
#define CLINKLIST_Htypedef int ElemType;
typedef struct LNode //定义单链表结点类型
{ElemType data;struct LNode *next;
} LinkNode;void CreateListF(LinkNode *L, ElemType a[], int n); //头插法建立循环单链表
void CreateListR(LinkNode *L, ElemType a[], int n); //尾插法建立循环单链表
void InitList(LinkNode *L); //初始化线性表
void DestroyList(LinkNode *L); //销毁线性表
bool ListEmpty(LinkNode *L); //判线性表是否为空表
int ListLength(LinkNode *L); //求线性表的长度
void DispList(LinkNode *L); //输出线性表
bool GetElem(LinkNode *L, int i, ElemType e); //求线性表中第i个元素值
int LocateElem(LinkNode *L, ElemType e); //查找第一个值域为e的元素序号
bool ListInsert(LinkNode *L, int i, ElemType e); //插入第i个元素
bool ListDelete(LinkNode *L, int i, ElemType e); //删除第i个元素#endif // !CLINKLIST_Hclinklist.cpp
//循环单链表运算算法
#include stdio.h
#include malloc.h
#include clinklist.hvoid CreateListF(LinkNode *L, ElemType a[], int n) //头插法建立循环单链表
{LinkNode *s; int i;L (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-next NULL;for (i 0; i n; i){s (LinkNode *)malloc(sizeof(LinkNode));//创建新结点s-data a[i];s-next L-next; //将结点s插在原开始结点之前,头结点之后L-next s;}s L-next;while (s-next ! NULL) //查找尾结点,由s指向它s s-next;s-next L; //尾结点next域指向头结点}void CreateListR(LinkNode *L, ElemType a[], int n) //尾插法建立循环单链表
{LinkNode *s, *r; int i;L (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-next NULL;r L; //r始终指向终端结点,开始时指向头结点for (i 0; i n; i){s (LinkNode *)malloc(sizeof(LinkNode));//创建新结点s-data a[i];r-next s; //将结点s插入结点r之后r s;}r-next L; //尾结点next域指向头结点
}void InitList(LinkNode *L) //初始化线性表
{L (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L-next L;
}void DestroyList(LinkNode *L) //销毁线性表
{LinkNode *pre L, *p pre-next;while (p ! L){free(pre);pre p; //pre、p同步后移一个结点p pre-next;}free(pre); //此时pL,pre指向尾结点,释放它
}bool ListEmpty(LinkNode *L) //判线性表是否为空表
{return(L-next L);
}int ListLength(LinkNode *L) //求线性表的长度
{LinkNode *p L; int i 0; //p指向头结点,n置为0(即头结点的序号为0)while (p-next ! L){i;p p-next;}return(i); //循环结束,p指向尾结点,其序号n为结点个数
}void DispList(LinkNode *L) //输出线性表
{LinkNode *p L-next;while (p ! L) //p不为L,输出p结点的data域{printf(%c , p-data);p p-next;}printf(\n);
}bool GetElem(LinkNode *L, int i, ElemType e) //求线性表中第i个元素值
{int j 1;LinkNode *p L-next;if (i 0 || L-next L) //i错误或者空表返回假return false;if (i 1) //求第1个结点值作为特殊情况处理{e L-next-data;return true;}else //i不为1时{while (j i - 1 p ! L) //找第i个结点p{j;p p-next;}if (p L) //没有找到返回假return false;else //找到了提取它的值并返回整{e p-data;return true;}}
}int LocateElem(LinkNode *L, ElemType e) //查找第一个值域为e的元素序号
{LinkNode *p L-next;int i 1;while (p ! L p-data ! e) //查找第一个值域为e的结点p{p p-next;i; //i对应结点p的序号}if (p L)return(0); //没有找到返回0elsereturn(i); //找到了返回其序号
}bool ListInsert(LinkNode *L, int i, ElemType e) //插入第i个元素
{int j 1;LinkNode *p L, *s;if (i 0) return false; //i错误返回假if (p-next L || i 1) //原单链表为空表或i1作为特殊情况处理{s (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点ss-data e;s-next p-next; //将结点s插入到结点p之后p-next s;return true;}else{p L-next;while (j i - 2 p ! L) //找第i-1个结点p{j;p p-next;}if (p L) //未找到第i-1个结点return false;else //找到第i-1个结点p{s (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点ss-data e;s-next p-next; //将结点s插入到结点p之后p-next s;return true;}}
}bool ListDelete(LinkNode *L, int i, ElemType e) //删除第i个元素
{int j 1;LinkNode *p L, *q;if (i 0 || L-next L)return false; //i错误或者空表返回假if (i 1) //i1作为特殊情况处理{q L-next; //删除第1个结点e q-data;L-next q-next;free(q);return true;}else //i不为1时{p L-next;while (j i - 2 p ! L) //找第i-1个结点p{j;p p-next;}if (p L) //未找到第i-1个结点return false;else //找到第i-1个结点p{q p-next; //q指向要删除的结点e q-data;p-next q-next; //从单链表中删除q结点free(q); //释放q结点return true;}}
}exp2-4.cpp
//文件名:exp2-4.cpp
#include clinklist.h
#include stdio.hint main()
{LinkNode *h;ElemType e;printf(循环单链表的基本运算如下:\n);printf( (1)初始化循环单链表h\n);InitList(h);printf( (2)依次采用尾插法插入a,b,c,d,e元素\n);ListInsert(h, 1, a);ListInsert(h, 2, b);ListInsert(h, 3, c);ListInsert(h, 4, d);ListInsert(h, 5, e);printf( (3)输出循环单链表h:);DispList(h);printf( (4)循环单链表h长度:%d\n, ListLength(h));printf( (5)循环单链表h为%s\n, (ListEmpty(h) ? 空 : 非空));GetElem(h, 3, e);printf( (6)循环单链表h的第3个元素:%c\n, e);printf( (7)元素a的位置:%d\n, LocateElem(h, a));printf( (8)在第4个元素位置上插入f元素\n);ListInsert(h, 4, f);printf( (9)输出循环单链表h:);DispList(h);printf( (10)删除h的第3个元素\n);ListDelete(h, 3, e);printf( (11)输出循环单链表h:);DispList(h);printf( (12)释放循环单链表h\n);DestroyList(h);return 1;
}结果
循环单链表的基本运算如下:(1)初始化循环单链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出循环单链表h:a b c d e(4)循环单链表h长度:5(5)循环单链表h为非空(6)循环单链表h的第3个元素:c(7)元素a的位置:1(8)在第4个元素位置上插入f元素(9)输出循环单链表h:a b c f d e(10)删除h的第3个元素(11)输出循环单链表h:a b f d e(12)释放循环单链表h
请按任意键继续. . .实现循环双链表各种基本运算的算法
放码
cdlinklist.h
#ifndef CDLINKLIST_H
#define CDLINKLIST_Htypedef int ElemType;
typedef struct DNode //定义双链表结点类型
{ElemType data;struct DNode *prior; //指向前驱结点struct DNode *next; //指向后继结点
} DLinkNode;void CreateListF(DLinkNode *L, ElemType a[], int n); //头插法建立循环双链表
void CreateListR(DLinkNode *L, ElemType a[], int n); //尾插法建立循环双链表
void InitList(DLinkNode *L); //初始化线性表
void DestroyList(DLinkNode *L); //销毁线性表
bool ListEmpty(DLinkNode *L); //判线性表是否为空表
int ListLength(DLinkNode *L); //求线性表的长度
void DispList(DLinkNode *L); //输出线性表
bool GetElem(DLinkNode *L, int i, ElemType e); //求线性表中第i个元素值
int LocateElem(DLinkNode *L, ElemType e); //查找第一个值域为e的元素序号
bool ListInsert(DLinkNode *L, int i, ElemType e); //插入第i个元素
bool ListDelete(DLinkNode *L, int i, ElemType e); //删除第i个元素#endif // !CDLINKLIST_Hcdlinklist.cpp
//循环双链表运算算法
#include stdio.h
#include malloc.h
#include cdlinklist.hvoid CreateListF(DLinkNode *L, ElemType a[], int n) //头插法建立循环双链表
{DLinkNode *s;L (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-next NULL;for (int i 0; i n; i){s (DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点s-data a[i];s-next L-next; //将结点s插在原开始结点之前,头结点之后if (L-next ! NULL) L-next-prior s;L-next s; s-prior L;}s L-next;while (s-next ! NULL) //查找尾结点,由s指向它s s-next;s-next L; //尾结点next域指向头结点L-prior s; //头结点的prior域指向尾结点}void CreateListR(DLinkNode *L, ElemType a[], int n) //尾插法建立循环双链表
{DLinkNode *s, *r;L (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-next NULL;r L; //r始终指向尾结点,开始时指向头结点for (int i 0; i n; i){s (DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点s-data a[i];r-next s; s-prior r; //将结点s插入结点r之后r s;}r-next L; //尾结点next域指向头结点L-prior r; //头结点的prior域指向尾结点
}void InitList(DLinkNode *L) //初始化线性表
{L (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点L-prior L-next L;
}void DestroyList(DLinkNode *L) //销毁线性表
{DLinkNode *pre L, *p pre-next;while (p ! L){free(pre);pre p; //pre、p同步后移一个结点p pre-next;}free(pre); //此时pL,pre指向尾结点,释放它
}bool ListEmpty(DLinkNode *L) //判线性表是否为空表
{return(L-next L);
}int ListLength(DLinkNode *L) //求线性表的长度
{DLinkNode *p L;int i 0;while (p-next ! L){i;p p-next;}return(i); //循环结束,p指向尾结点,其序号i为结点个数
}void DispList(DLinkNode *L) //输出线性表
{DLinkNode *p L-next;while (p ! L){printf(%c , p-data);p p-next;}printf(\n);
}bool GetElem(DLinkNode *L, int i, ElemType e) //求线性表中第i个元素值
{int j 1;DLinkNode *p L-next;if (i 0 || L-next L)return false; //i错误或者L为空表返回假if (i 1) //i1作为特殊情况处理{e L-next-data;return true;}else //i不为1时{while (j i - 1 p ! L) //查找第i个结点p{j;p p-next;}if (p L) //没有找到第i个节返回假return false;else //找到了第i个节返回真{e p-data;return true;}}
}int LocateElem(DLinkNode *L, ElemType e) //查找第一个值域为e的元素序号
{int i 1;DLinkNode *p L-next;while (p ! NULL p-data ! e){i;p p-next;}if (p NULL) //不存在值为e的结点,返回0return(0);else //存在值为e的结点,返回其逻辑序号ireturn(i);
}bool ListInsert(DLinkNode *L, int i, ElemType e) //插入第i个元素
{int j 1;DLinkNode *p L, *s;if (i 0) return false; //i错误返回假if (p-next L) //原双链表为空表时{s (DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点ss-data e;p-next s; s-next p;p-prior s; s-prior p;return true;}else if (i 1) //L不为空i1作为特殊情况处理{s (DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点ss-data e;s-next p-next; p-next s; //将结点s插入到结点p之后s-next-prior s; s-prior p;return true;}else //i不为1时{p L-next;while (j i - 2 p ! L) //查找第i-1个结点p{j;p p-next;}if (p L) //未找到第i-1个结点return false;else //找到第i-1个结点*p{s (DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点ss-data e;s-next p-next; //将结点s插入到结点p之后if (p-next ! NULL) p-next-prior s;s-prior p;p-next s;return true;}}
}bool ListDelete(DLinkNode *L, int i, ElemType e) //删除第i个元素
{int j 1;DLinkNode *p L, *q;if (i 0 || L-next L)return false; //i错误或者为空表返回假if (i 1) //i1作为特殊情况处理{q L-next; //删除第1个结点e q-data;L-next q-next;q-next-prior L;free(q);return true;}else //i不为1时{p L-next;while (j i - 2 p ! NULL) //查找到第i-1个结点p {j;p p-next;}if (p NULL) //未找到第i-1个结点return false;else //找到第i-1个结点p{q p-next; //q指向要删除的结点if (q NULL) return 0; //不存在第i个结点e q-data;p-next q-next; //从单链表中删除q结点if (p-next ! NULL) p-next-prior p;free(q); //释放q结点return true;}}
}exp2-5.cpp
//文件名:exp2-5.cpp
#include cdlinklist.h
#include stdio.hint main()
{DLinkNode *h;ElemType e;printf(循环双链表的基本运算如下:\n);printf( (1)初始化循环双链表h\n);InitList(h);printf( (2)依次采用尾插法插入a,b,c,d,e元素\n);ListInsert(h, 1, a);ListInsert(h, 2, b);ListInsert(h, 3, c);ListInsert(h, 4, d);ListInsert(h, 5, e);printf( (3)输出循环双链表h:);DispList(h);printf( (4)循环双链表h长度:%d\n, ListLength(h));printf( (5)循环双链表h为%s\n, (ListEmpty(h) ? 空 : 非空));GetElem(h, 3, e);printf( (6)循环双链表h的第3个元素:%c\n, e);printf( (7)元素a的位置:%d\n, LocateElem(h, a));printf( (8)在第4个元素位置上插入f元素\n);ListInsert(h, 4, f);printf( (9)输出循环双链表h:);DispList(h);printf( (10)删除h的第3个元素\n);ListDelete(h, 3, e);printf( (11)输出循环双链表h:);DispList(h);printf( (12)释放循环双链表h\n);DestroyList(h);return 1;
}结果
循环双链表的基本运算如下:(1)初始化循环双链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出循环双链表h:a b c d e(4)循环双链表h长度:5(5)循环双链表h为非空(6)循环双链表h的第3个元素:c(7)元素a的位置:1(8)在第4个元素位置上插入f元素(9)输出循环双链表h:a b c f d e(10)删除h的第3个元素(11)输出循环双链表h:a b f d e(12)释放循环双链表h
请按任意键继续. . .设计性实验
将单链表按基准划分
说明
以给定值x为基准将单链表分割为两部分所有小于x的结点排在大于或等于x的结点之前。
放码
//文件名:exp2-6.cpp
#include linklist.h //包含单链表的基本运算算法
#include stdio.hvoid Split(LinkNode *L, ElemType x) //将L中所有数据结点按x进行划分
{LinkNode *p L-next, *q, *r; L-next NULL; //L变为空链表, 表头无内容r L;while (p ! NULL){if (p-data x) //若p结点值小于x将其插入在开头{q p-next;p-next L-next;L-next p;if (p-next NULL) //若p结点是第一个在开头插入的结点r p; //则它是尾结点p q;}else //若p结点值大于或等于x将其插入到末尾{r-next p;r p;p p-next;}}r-next NULL;
}int main()
{LinkNode *L;ElemType a[] { a, b, c, d, e, f, g, h };// abcdefgh;int n 8;CreateListR(L, a, n);printf(L:); DispList(L);ElemType x d;printf(以%c进行划分\n, x);Split(L, x);printf(L:); DispList(L);DestroyList(L);return 1;
}
结果
L:a b c d e f g h
以d进行划分
L:c b a d e f g h
请按任意键继续. . .将两个单链表合并为一个单链表
说明
令L1(x1,x2,…,xn)L1(x_1, x_2, \dots, x_n)L1(x1,x2,…,xn)L2(y1,y2,…,ym)L2(y_1, y_2, \dots, y_m)L2(y1,y2,…,ym)是两个线性表采用带头结点的单链表存储设计一个算法合并L1、L2结果放 在线性表L3中要求如下 L3{(x1,y1,x2,y2,…,xm,ym,xm1,…,xn)当m⩽n时(x1,y1,x2,y2,…,xn,yn,yn1,…,ym)当mn时L3\begin{cases} (x_1,y_1,x_2,y_2,\dots,x_m,y_m,x_{m1},\dots,x_n) 当m \leqslant n时\\ (x_1,y_1,x_2,y_2,\dots,x_n,y_n,y_{n1},\dots,y_m) 当m \gt n时 \end{cases} L3{(x1,y1,x2,y2,…,xm,ym,xm1,…,xn)(x1,y1,x2,y2,…,xn,yn,yn1,…,ym)当m⩽n时当mn时 L3仍采用单链表存储算法的空间复杂度为O(1)。
放码
//文件名:exp2-7.cpp
#include linklist.h //包含单链表的基本运算算法
#include stdio.h
#include malloc.hvoid Merge(LinkNode *L1, LinkNode *L2, LinkNode *L3) //L1和L2合并产生L3
{LinkNode *p L1-next, *q L2-next, *r;L3 L1;r L3; //r指向新建单链表L3的尾结点free(L2); //释放L2的头结点while (p ! NULL q ! NULL){r-next p; r p; p p-next;r-next q; r q; q q-next;}r-next NULL;if (q ! NULL) p q;r-next p;
}int main()
{LinkNode *L1, *L2, *L3;ElemType a[] { a, b, c, d, e, f, g, h };// abcdefgh;int n 8;CreateListR(L1, a, n);printf(L1:); DispList(L1);ElemType b[] { 1, 2, 3, 4, 5 };n 5;CreateListR(L2, b, n);printf(L2:); DispList(L2);printf(L1和L2合并产生L3\n);Merge(L1, L2, L3);printf(L3:); DispList(L3);DestroyList(L3);return 1;
}结果
L1:a b c d e f g h
L2:1 2 3 4 5
L1和L2合并产生L3
L3:a 1 b 2 c 3 d 4 e 5 f g h
请按任意键继续. . .求集合用单链表表示的并、交和差运算
说明
采用单链表表示集合假设同一个集合中不存在重复的元素将其按递增方式排序构成有序单链表并求这样的两个集合的并、交和差。
放码
//文件名:exp2-8.cpp
#include linklist.h
#include stdio.h
#include malloc.hvoid sort(LinkNode *L) //单链表元素递增排序
{LinkNode *p, *pre, *q;p L-next-next; //p指向L的第2个数据结点L-next-next NULL; //构造只含一个数据结点的有序表while (p ! NULL){q p-next; //q保存p结点的后继结点pre L; //从有序表开头进行比较,pre指向插入结点p的前驱结点while (pre-next ! NULL pre-next-data p-data)pre pre-next; //在有序表中找pre结点p-next pre-next; //将结点pre之后插入p结点pre-next p;p q; //扫描原单链表余下的结点}
}void Union(LinkNode *ha, LinkNode *hb, LinkNode *hc) //求两有序集合的并
{LinkNode *pa ha-next, *pb hb-next, *s, *tc;hc (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点tc hc;while (pa ! NULL pb ! NULL){if (pa-data pb-data){s (LinkNode *)malloc(sizeof(LinkNode)); //复制结点s-data pa-data;tc-next s; tc s;pa pa-next;}else if (pa-data pb-data){s (LinkNode *)malloc(sizeof(LinkNode)); //复制结点s-data pb-data;tc-next s; tc s;pb pb-next;}else{s (LinkNode *)malloc(sizeof(LinkNode)); //复制结点s-data pa-data;tc-next s; tc s;pa pa-next; //重复的元素只复制一个pb pb-next;}}if (pb ! NULL) pa pb; //复制余下的结点while (pa ! NULL){s (LinkNode *)malloc(sizeof(LinkNode)); //复制结点s-data pa-data;tc-next s; tc s;pa pa-next;}tc-next NULL;
}
void InterSect(LinkNode *ha, LinkNode *hb, LinkNode *hc) //求两有序集合的交
{LinkNode *pa ha-next, *pb, *s, *tc;hc (LinkNode *)malloc(sizeof(LinkNode));tc hc;while (pa ! NULL){pb hb-next;while (pb ! NULL pb-data pa-data)pb pb-next;if (pb ! NULL pb-data pa-data) //若pa结点值在B中{s (LinkNode *)malloc(sizeof(LinkNode)); //复制结点s-data pa-data;tc-next s; tc s;}pa pa-next;}tc-next NULL;
}
void Subs(LinkNode *ha, LinkNode *hb, LinkNode *hc) //求两有序集合的差
{LinkNode *pa ha-next, *pb, *s, *tc;hc (LinkNode *)malloc(sizeof(LinkNode));tc hc;while (pa ! NULL){pb hb-next;while (pb ! NULL pb-data pa-data)pb pb-next;if (!(pb ! NULL pb-data pa-data)) //若pa结点值不在B中{s (LinkNode *)malloc(sizeof(LinkNode)); //复制结点s-data pa-data;tc-next s; tc s;}pa pa-next;}tc-next NULL;
}
int main()
{LinkNode *ha, *hb, *hc;ElemType a[] { c, a, e, h };ElemType b[] { f, h, b, g, d, a };printf(集合的运算如下:\n);CreateListR(ha, a, 4);CreateListR(hb, b, 6);printf( 原 集 合A: ); DispList(ha);printf( 原 集 合B: ); DispList(hb);sort(ha);sort(hb);printf( 有序集合A: ); DispList(ha);printf( 有序集合B: ); DispList(hb);Union(ha, hb, hc);printf( 集合的并C: ); DispList(hc);InterSect(ha, hb, hc);printf( 集合的交C: ); DispList(hc);Subs(ha, hb, hc);printf( 集合的差C: ); DispList(hc);DestroyList(ha);DestroyList(hb);DestroyList(hc);return 1;
}结果
集合的运算如下:原 集 合A: c a e h原 集 合B: f h b g d a有序集合A: a c e h有序集合B: a b d f g h集合的并C: a b c d e f g h集合的交C: a h集合的差C: c e
请按任意键继续. . .实现两个多项式相加运算
说明
用单链表存储一元多项式并实现两个多项式相加运算。
放码
//文件名:exp2-9.cpp
#include stdio.h
#include malloc.h
#define MAX 100 //多项式最多项数
typedef struct
{double coef; //系数int exp; //指数
} PolyArray; //存放多项式的数组类型typedef struct pnode
{double coef; //系数int exp; //指数struct pnode *next;
} PolyNode; //声明多项式单链表结点类型void DispPoly(PolyNode *L) //输出多项式单链表
{bool first true; //first为true表示是第一项PolyNode *p L-next;while (p ! NULL){if (first)first false;else if (p-coef 0)printf();if (p-exp 0)printf(%g, p-coef);else if (p-exp 1)printf(%gx, p-coef);elseprintf(%gx^%d, p-coef, p-exp);p p-next;}printf(\n);
}void DestroyPoly(PolyNode *L) //销毁多项式单链表
{PolyNode *pre L, *p pre-next;while (p ! NULL){free(pre);pre p;p pre-next;}free(pre);
}void CreatePolyR(PolyNode *L, PolyArray a[], int n) //尾插法建表
{PolyNode *s, *r; int i;L (PolyNode *)malloc(sizeof(PolyNode)); //创建头结点L-next NULL;r L; //r始终指向尾结点,开始时指向头结点for (i 0; i n; i){s (PolyNode *)malloc(sizeof(PolyNode));//创建新结点s-coef a[i].coef;s-exp a[i].exp;r-next s; //将结点s插入结点r之后r s;}r-next NULL; //尾结点next域置为NULL
}void Sort(PolyNode *L) //将多项式单链表按指数递减排序
{PolyNode *p L-next, *pre, *q;if (p ! NULL) //L有一个或以上的数据结点{q p-next; //q保存p结点的后继结点p-next NULL; //构造只含一个数据结点的有序表p q;while (p ! NULL) //扫描原L中余下的数据结点{q p-next; //q保存p结点的后继结点pre L;while (pre-next ! NULL pre-next-exp p-exp)pre pre-next; //在有序表中找插入结点p的前驱结点prep-next pre-next; //将结点p插入到结点pre之后pre-next p;p q; //扫描原单链表余下的结点}}
}void Add(PolyNode *ha, PolyNode *hb, PolyNode *hc) //ha和bh相加得到hc
{PolyNode *pa ha-next, *pb hb-next, *s, *r;double c;hc (PolyNode *)malloc(sizeof(PolyNode));r hc; //r指向尾结点初始时指向头结点while (pa ! NULL pb ! NULL) //pa、pb均没有扫描完{if (pa-exp pb-exp) //将指数较大的pa结点复制到hc中{s (PolyNode *)malloc(sizeof(PolyNode));s-exp pa-exp; s-coef pa-coef;r-next s; r s;pa pa-next;}else if (pa-exp pb-exp) //将指数较大的pb结点复制到hc中{s (PolyNode *)malloc(sizeof(PolyNode));s-exp pb-exp; s-coef pb-coef;r-next s; r s;pb pb-next;}else //pa、pb结点的指数相等时{c pa-coef pb-coef; //求两个结点的系数和cif (c ! 0) //若系数和不为0时创建新结点{s (PolyNode *)malloc(sizeof(PolyNode));s-exp pa-exp; s-coef c;r-next s; r s;}pa pa-next; //pa、pb均后移一个结点pb pb-next;}}if (pb ! NULL) pa pb; //复制余下的结点while (pa ! NULL){s (PolyNode *)malloc(sizeof(PolyNode));s-exp pa-exp;s-coef pa-coef;r-next s; r s;pa pa-next;}r-next NULL; //尾结点next设置为空
}int main()
{PolyNode *ha, *hb, *hc;PolyArray a[] { { 1.2, 0 }, { 2.5, 1 }, { 3.2, 3 }, { -2.5, 5 } };PolyArray b[] { { -1.2, 0 }, { 2.5, 1 }, { 3.2, 3 }, { 2.5, 5 }, { 5.4, 10 } };CreatePolyR(ha, a, 4);CreatePolyR(hb, b, 5);printf(原多项式A: ); DispPoly(ha);printf(原多项式B: ); DispPoly(hb);Sort(ha);Sort(hb);printf(有序多项式A: ); DispPoly(ha);printf(有序多项式B: ); DispPoly(hb);Add(ha, hb, hc);printf(多项式相加: ); DispPoly(hc);DestroyPoly(ha);DestroyPoly(hb);DestroyPoly(hc);return 1;
}结果
原多项式A: 1.22.5x3.2x^3-2.5x^5
原多项式B: -1.22.5x3.2x^32.5x^55.4x^10
有序多项式A: -2.5x^53.2x^32.5x1.2
有序多项式B: 5.4x^102.5x^53.2x^32.5x-1.2
多项式相加: 5.4x^106.4x^35x
请按任意键继续. . .综合性实验
实现两个多项式相乘运算
说明
用单链表存储一元多项式并实现两个多项式相乘运算。
放码
//文件名:exp2-10.cpp#include stdio.h
#include malloc.h
#define MAX 20typedef struct node
{double coef; //系数int exp; //指数struct node *next;
} PolyNode; //声明多项式单链表结点类型\void CreatePolyR(PolyNode *L, double a[], int b[], int n) //尾插法创建多项式单链表
{PolyNode *s, *r; int i;L (PolyNode *)malloc(sizeof(PolyNode));L-next NULL;r L; //r始终指向终端结点,开始时指向头结点for (i 0; i n; i){s (PolyNode *)malloc(sizeof(PolyNode));s-coef a[i];s-exp b[i];r-next s; //将结点s插入结点r之后r s;}r-next NULL; //尾结点next域置为NULL
}
void DestroyPoly(PolyNode *L) //销毁单链表
{PolyNode *pre L, *p pre-next;while (p ! NULL){free(pre);pre p;p pre-next;}free(pre);
}
void DispPoly(PolyNode *L) //输出多项式单链表
{bool first true; //first为true表示是第一项PolyNode *p L-next;while (p ! NULL){if (first)first false;else if (p-coef 0)printf();if (p-exp 0)printf(%g, p-coef);else if (p-exp 1)printf(%gx, p-coef);elseprintf(%gx^%d, p-coef, p-exp);p p-next;}printf(\n);
}
void Sort(PolyNode *L) //将多项式单链表按指数递减排序
{PolyNode *p L-next, *pre, *q;if (p ! NULL) //L有一个或以上的数据结点{q p-next; //q保存p结点的后继结点p-next NULL; //构造只含一个数据结点的有序表p q;while (p ! NULL) //扫描原L中余下的数据结点{q p-next; //q保存p结点的后继结点pre L;while (pre-next ! NULL pre-next-exp p-exp)pre pre-next; //在有序表中找插入结点p的前驱结点prep-next pre-next; //将结点p插入到结点pre之后pre-next p;p q; //扫描原单链表余下的结点}}
}void Mult1(PolyNode *ha, PolyNode *hb, PolyNode *hc) //ha和bh简单相乘得到hc
{PolyNode *pa ha-next, *pb, *s, *tc;hc (PolyNode *)malloc(sizeof(PolyNode));tc hc;while (pa ! NULL){pb hb-next;while (pb ! NULL){s (PolyNode *)malloc(sizeof(PolyNode));s-coef pa-coef*pb-coef;s-exp pa-exp pb-exp;tc-next s;tc s;pb pb-next;}pa pa-next;}tc-next NULL;
}void Comb(PolyNode *L) //合并指数相同的项
{PolyNode *pre L-next, *p;if (pre NULL) return;p pre-next;while (p ! NULL){while (p-exp pre-exp){pre-coef p-coef;pre-next p-next;free(p);p pre-next;}pre p;p p-next;}
}void DelZero(PolyNode *L) //删除系数为0的项
{PolyNode *pre L, *p pre-next;while (p ! NULL){if (p-coef 0.0){pre-next p-next;free(p);}pre p;p p-next;}
}void Mult(PolyNode *ha, PolyNode *hb, PolyNode *hc) //ha和bh相乘得到最终的hc
{Mult1(ha, hb, hc);printf(相乘结果: ); DispPoly(hc);Sort(hc);printf(按指数排序后: ); DispPoly(hc);Comb(hc);printf(合并重复指数项:); DispPoly(hc);DelZero(hc);printf(删除序数为0项: ); DispPoly(hc);
}int main()
{PolyNode *Poly1, *Poly2, *Poly3;double a[MAX];int b[MAX], n;//----创建第1个多项单链表并排序-----a[0] 2; b[0] 3; a[1] 1; b[1] 0; a[2] 3; b[2] 1;n 3;printf(第1个多项式:\n);CreatePolyR(Poly1, a, b, n);printf( 排序前多项式1:); DispPoly(Poly1);Sort(Poly1);printf( 排序后多项式1:); DispPoly(Poly1);//----创建第2个多项单链表并排序-----printf(第2个多项式:\n);a[0] 2; b[0] 3; a[1] -3; b[1] 2;a[2] 5; b[2] 4; a[3] -3; b[3] 0;n 4;CreatePolyR(Poly2, a, b, n);printf( 排序前多项式2:); DispPoly(Poly2);Sort(Poly2);printf( 排序后多项式2:); DispPoly(Poly2);Mult(Poly1, Poly2, Poly3);printf(相乘后多项式3: ); DispPoly(Poly3);DestroyPoly(Poly1);DestroyPoly(Poly2);DestroyPoly(Poly3);return 1;
}结果
第1个多项式:排序前多项式1:2x^313x排序后多项式1:2x^33x1
第2个多项式:排序前多项式2:2x^3-3x^25x^4-3排序后多项式2:5x^42x^3-3x^2-3
相乘结果: 10x^74x^6-6x^5-6x^315x^56x^4-9x^3-9x5x^42x^3-3x^2-3
按指数排序后: 10x^74x^615x^5-6x^55x^46x^42x^3-9x^3-6x^3-3x^2-9x-3
合并重复指数项:10x^74x^69x^511x^4-13x^3-3x^2-9x-3
删除序数为0项: 10x^74x^69x^511x^4-13x^3-3x^2-9x-3
相乘后多项式3: 10x^74x^69x^511x^4-13x^3-3x^2-9x-3
请按任意键继续. . .职工信息的综合运算
说明
设有一个职工文件 emp.dat每个职工记录包含职工编号no姓名name、部门号depno和工资数salary信息。完成如下功能
从emp.dat 文件中读出职工记录,并建立一个带头结点的单链表L。输人一个职工记录。显示所有职工记录。按编号no对所有职工记录进行递增排序。按部门号depno对所有职工记录进行递增排序。按工资数salary对所有职工记录进行递增排序。删除指定的职工号的职工记录。删除职工文件中的全部记录。将单链表L中的所有职工记录存储到职工文件emp.dat 中。
放码
//文件名:exp2-11.cpp
#include stdio.h
#include malloc.h
typedef struct
{int no; //职工号char name[10]; //姓名int depno; //部门号float salary; //工资数
} EmpType; //职工类型typedef struct node
{EmpType data; //存放职工信息struct node *next; //指向下一个结点的指针
} EmpList; //职工单链表结点类型void DestroyEmp(EmpList *L) //释放职工单链表L
{EmpList *pre L, *p pre-next;while (p ! NULL){free(pre);pre p;p p-next;}free(pre);
}void DelAll(EmpList *L) //删除职工文件中全部记录
{FILE *fp;if ((fp fopen(emp.dat, wb)) NULL) //重写清空emp.dat文件{printf( 提示:不能打开职工文件\n);return;}fclose(fp);DestroyEmp(L); //释放职工单链表LL (EmpList *)malloc(sizeof(EmpList));L-next NULL; //建立一个空的职工单链表Lprintf( 提示:职工数据清除完毕\n);
}void ReadFile(EmpList *L) //读emp.dat文件建立职工单键表L
{FILE *fp;EmpType emp;EmpList *p, *r;int n 0;L (EmpList *)malloc(sizeof(EmpList)); //建立头结点r L;if ((fp fopen(emp.dat, rb)) NULL) //不存在emp.dat文件{if ((fp fopen(emp.dat, wb)) NULL)printf( 提示:不能创建emp.dat文件\n);}else //若存在emp.dat文件{while (fread(emp, sizeof(EmpType), 1, fp) 1){ //采用尾插法建立单链表Lp (EmpList *)malloc(sizeof(EmpList));p-data emp;r-next p;r p;n;}}r-next NULL;printf( 提示:职工单键表L建立完毕,有%d个记录\n, n);fclose(fp);
}void SaveFile(EmpList *L) //将职工单链表数据存入数据文件
{EmpList *p L-next;int n 0;FILE *fp;if ((fp fopen(emp.dat, wb)) NULL){printf( 提示:不能创建文件emp.dat\n);return;}while (p ! NULL){fwrite(p-data, sizeof(EmpType), 1, fp);p p-next;n;}fclose(fp);DestroyEmp(L); //释放职工单链表Lif (n 0)printf( 提示:%d个职工记录写入emp.dat文件\n, n);elseprintf( 提示:没有任何职工记录写入emp.dat文件\n);
}void InputEmp(EmpList *L) //添加一个职工记录
{EmpType p;EmpList *s;printf( 输入职工号(-1返回):);scanf(%d, p.no);if (p.no -1) return;printf( 输入姓名 部门号 工资:);scanf(%s%d%f, p.name, p.depno, p.salary);s (EmpList *)malloc(sizeof(EmpList));s-data p;s-next L-next; //采用头插法插入结点sL-next s;printf( 提示:添加成功\n);
}void DelEmp(EmpList *L) //删除一个职工记录
{EmpList *pre L, *p L-next;int no;printf( 输入职工号(-1返回):);scanf(%d, no);if (no -1) return;while (p ! NULL p-data.no ! no){pre p;p p-next;}if (p NULL)printf( 提示:指定的职工记录不存在\n);else{pre-next p-next;free(p);printf( 提示:删除成功\n);}
}void Sortno(EmpList *L) //采用直接插入法单链表L按no递增有序排序
{EmpList *p, *pre, *q;p L-next-next;if (p ! NULL){L-next-next NULL;while (p ! NULL){q p-next;pre L;while (pre-next ! NULL pre-next-data.no p-data.no)pre pre-next;p-next pre-next;pre-next p;p q;}}printf( 提示:按no递增排序完毕\n);
}void Sortdepno(EmpList *L) //采用直接插入法单链表L按depno递增有序排序
{EmpList *p, *pre, *q;p L-next-next;if (p ! NULL){L-next-next NULL;while (p ! NULL){q p-next;pre L;while (pre-next ! NULL pre-next-data.depno p-data.depno)pre pre-next;p-next pre-next;pre-next p;p q;}}printf( 提示:按depno递增排序完毕\n);
}void Sortsalary(EmpList *L) //采用直接插入法单链表L按salary递增有序排序
{EmpList *p, *pre, *q;p L-next-next;if (p ! NULL){L-next-next NULL;while (p ! NULL){q p-next;pre L;while (pre-next ! NULL pre-next-data.salary p-data.salary)pre pre-next;p-next pre-next;pre-next p;p q;}}printf( 提示:按salary递增排序完毕\n);
}void DispEmp(EmpList *L) //输出所有职工记录
{EmpList *p L-next;if (p NULL)printf( 提示:没有任何职工记录\n);else{printf( 职工号 姓名 部门号 工资\n);printf( ----------------------------------\n);while (p ! NULL){printf( %3d%10s %-8d%7.2f\n, p-data.no, p-data.name, p-data.depno, p-data.salary);p p-next;}printf( ----------------------------------\n);}
}int main()
{EmpList *L;int sel;printf(由emp.dat文件建立职工单键表L\n);ReadFile(L);do{printf(1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序\n);printf(6:删除 9:全删 0:退出 请选择:);scanf(%d, sel);switch (sel){case 9:DelAll(L);break;case 1:InputEmp(L);break;case 2:DispEmp(L);break;case 3:Sortno(L);break;case 4:Sortdepno(L);break;case 5:Sortsalary(L);break;case 6:DelEmp(L);break;}} while (sel ! 0);SaveFile(L);return 1;
}
结果
由emp.dat文件建立职工单键表L提示:职工单键表L建立完毕,有4个记录
1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序
6:删除 9:全删 0:退出 请选择:2职工号 姓名 部门号 工资----------------------------------3 李明 2 5865.002 程功 3 6856.001 王华 1 7250.004 许启 2 8246.00----------------------------------
1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序
6:删除 9:全删 0:退出 请选择:3提示:按no递增排序完毕
1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序
6:删除 9:全删 0:退出 请选择:2职工号 姓名 部门号 工资----------------------------------1 王华 1 7250.002 程功 3 6856.003 李明 2 5865.004 许启 2 8246.00----------------------------------
1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序
6:删除 9:全删 0:退出 请选择:5提示:按salary递增排序完毕
1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序
6:删除 9:全删 0:退出 请选择:2职工号 姓名 部门号 工资----------------------------------3 李明 2 5865.002 程功 3 6856.001 王华 1 7250.004 许启 2 8246.00----------------------------------
1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序
6:删除 9:全删 0:退出 请选择:0提示:4个职工记录写入emp.dat文件
请按任意键继续. . .用单链表实现两个大整数相加运算
说明
完成如下功能:
将用户输入的十进制整数字符串转化为带头结点的单链表,每个结点存放一个整数位。求两个整数单链表相加的结果单链表。求结果单链表的中间位如 123 的中间位为21234 的中间位为2。
放码
//文件名:exp2-12.cpp
#include stdio.h
#include malloc.h
#include string.h#define MaxSize 50
typedef struct node
{int data;struct node *next;
} NodeType;void CreateLink(NodeType *h, char a[], int n) //创建整数单链表
{NodeType *p, *r;int i 0;h (NodeType *)malloc(sizeof(NodeType));r h;while (i n){p (NodeType *)malloc(sizeof(NodeType));p-data a[n - i - 1] - 0;r-next p; r p;i;}r-next NULL;
}void DestroyLink(NodeType *h) //释放整数单链表
{NodeType *pre h, *p pre-next;while (p ! NULL){free(pre);pre p;p p-next;}free(pre);
}void DispLink(NodeType *h) //输出整数单链表
{NodeType *p h-next;while (p ! NULL){printf(%d , p-data);p p-next;}printf(\n);
}void Add(NodeType *h1, NodeType *h2, NodeType *h) //两整数值单链表h1和h2相加得到h
{NodeType *p1 h1-next, *p2 h2-next, *p, *r;int carry 0;h (NodeType *)malloc(sizeof(NodeType));r h;while (p1 ! NULL p2 ! NULL){p (NodeType *)malloc(sizeof(NodeType));p-data (p1-data p2-data carry) % 10;r-next p; r p;carry (p1-data p2-data carry) / 10;p1 p1-next;p2 p2-next;}if (p1 NULL) p1 p2;while (p1 ! NULL){p (NodeType *)malloc(sizeof(NodeType));p-data (p1-data carry) % 10;r-next p; r p;carry (p1-data carry) / 10;p1 p1-next;}if (carry 0) //最后carry不为0时创建一个结点存放它{p (NodeType *)malloc(sizeof(NodeType));p-data carry;r-next p; r p;}r-next NULL;
}void Reverse(NodeType *h) //逆置整数单链表h
{NodeType *p h-next, *q;h-next NULL;while (p ! NULL){q p-next;p-next h-next; h-next p;p q;}
}int Mid(NodeType *h) //求整数单链表h的中间位
{NodeType *slow h, *quick h;while (quick ! NULL quick-next ! NULL){slow slow-next;quick quick-next-next;}return slow-data;
}int main()
{NodeType *h1, *h2, *h;char s[MaxSize], t[MaxSize];printf(操作步骤:\n);printf( (1)输入整数1: ); scanf(%s, s);printf( (2)输入整数2: ); scanf(%s, t);CreateLink(h1, s, strlen(s));CreateLink(h2, t, strlen(t));printf( (3)整数单链表1: ); DispLink(h1);printf( (4)整数单链表2: ); DispLink(h2);Add(h1, h2, h);printf( (5)结果单链表: ); DispLink(h);Reverse(h);printf( (6)对应的整数: ); DispLink(h);printf( (7)中间位:%d\n, Mid(h));DestroyLink(h);DestroyLink(h1);DestroyLink(h2);return 1;
}结果
操作步骤:(1)输入整数1: 99999999(2)输入整数2: 666666661(3)整数单链表1: 9 9 9 9 9 9 9 9(4)整数单链表2: 1 6 6 6 6 6 6 6 6(5)结果单链表: 0 6 6 6 6 6 6 6 7(6)对应的整数: 7 6 6 6 6 6 6 6 0(7)中间位:6
请按任意键继续. . .
