1.链表的介绍1.1 什么是单链表单链表是用一组任意的存储单元来存放线性表的结点这组存储单元既可以是连续的的也可以是不连续的甚至零散地分布在内存中的任何位置上。为了能正确表示结点的逻错关系在存储每个结点值的同时还必须存储指示其后继结点的地址(或位置)息这个信息称为指针或链。这两部分信息组成了链表中的结点结构。链式存储结构的优点1空间利用率高需要一个空间就分配一个空间2数据元素的逻辑次序靠节点的指针来指示插入和删除时不需要移动数据结点,任意位置插入删除时间复杂度为O(1)单链表的定义typedef struct SListNode { DateType data; //结点的数据域 struct SListNode *next; //结点的指针域 }SListNode;结点空间开辟执行 SListNode*p之后该指针变量指向的结点变量并未开辟空间程序执行过程中当需要时才产生需要执行p(SListNode*)malloc(sizeof(SListNode))后分配一个类型为ListNode的结点变量的空间。结点空间释放当p指向的结点变量不再需要的时候可以通过执行free(p)释放。1.2 什么是循环链表循环链表是一种特殊的链表数据结构与单向链表或双向链表相比循环链表的最后一个节点的下一个节点指向第一个节点从而形成一个环形结构。因此循环链表可以在最后一个节点后继续添加节点并且可以像单向链表或双向链表一样遍历、查找和删除节点。循环链表通常有一个头指针和一个尾指针它们指向第一个节点和最后一个节点以便在添加或删除节点时快速定位。循环链表可以用于解决某些问题例如模拟一个环形队列或者用于实现循环播放的音乐列表等。循环链表的优点在于它具有链表的灵活性同时可以避免在添加或删除节点时需要遍历整个链表的缺点循环链表的任意元素都有一个前驱和一个后继所有数据元素在关系上构成逻辑上的环。循环链表是一种特殊的单链表尾结点的指针指向首结点的地址。1.3 单链表和循环列表的区别1循环链表的操作和单链表基本一致。2差别仅在于当遍历链表时判别当前指针P是否指向表尾结点的终止条件不同。3由于循环链表中没有NULL指针故涉及遍历操作时其终止条件就不再像单链表那样判断p或p-next是否为空而是判断它们是否等于头指针。2.循环链表的基本运算循环链表的基本运算包括以下几种1. 初始化链表创建一个空的链表。2. 插入结点在链表中插入一个新的结点。3. 删除结点从链表中删除一个指定的结点。4. 遍历链表遍历链表中的所有结点并对每个结点执行某些操作。5. 查找结点在链表中查找一个指定的结点。6. 修改结点修改链表中一个指定的结点的数据。这些基本运算可以帮助我们实现各种不同的链表应用例如实现栈、队列、优先队列等数据结构。3.代码的实现循环链表的初始化int init(SingleLinkList **Head) { if(Head ! NULL) { /*申请内存*/ (*Head) (SingleLinkList*)malloc(sizeof(SingleLinkList)); /*判断内存申请是否成功*/ if(*Head NULL) { printf(申请内存错误 初始化失败[100001]\n); return 100001; } // (*Head)-next NULL; /*循环链表*/ /* (*Head)-next *Head; */ (*Head)-next *Head; return 0; } else { printf(该链表已经初始化请删除后再执行此操作[100002]\n); return 100002; } }插入元素之头插法int insert_head(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; newNode-next (*Head)-next; (*Head)-next newNode; return 0; }插入元素之尾插法int insert_tail(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; SingleLinkNode *p; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; // newNode-next NULL; /* 循环链表 newNode-next *Head; */ newNode-next *Head; p (*Head); while(p-next ! NULL p-next ! *Head) { p p-next; } p-next newNode; return 0; }插入元素在位置i处插入元素xint insert(SingleLinkList **Head, int i, DataType x) { int j; SingleLinkNode *p; SingleLinkNode *newNode; /*对i进行判断0ilength1*/ if(i1 || ilength(*Head)1) { printf(位置i不是链表有效位置[100005]\n); return 100005; } p (*Head); j 1; while(ji) { j; p p-next; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); /*此处省略检测newNode是否申请成功*/ newNode-data x; newNode-next p-next; p-next newNode; return 0; }查找值为x的元素返回位置iint find(SingleLinkList *Head, DataType x) { int i; SingleLinkNode *p; i 1; p Head-next; while(p p-data ! x) /*while( p! Head p-data ! x) */ { i; p p-next; } if(!p) /* if(p-next Head) */ { return 0; } else { return i; } }链表长度int length(SingleLinkList *Head) { int len0; SingleLinkNode *p; p Head-next; // while(p) /* while(p!Head) */ while(p!Head) { len; p p-next; } return len; }输出链表void print(SingleLinkList *Head) { SingleLinkNode *p; int i0; p Head-next; if(!p) /* if(p!Head) */ { printf(链表为空\n); return; } // while(p!Head) // { // p p-next; // } // while(p) /* while(p!Head) */ while(p ! Head) { printf(Node[%d]. %d\n, i, p-data); p p-next; } }删除元素值为x的元素int delete(SingleLinkList **Head, DataType x) { int i; int j; SingleLinkNode *p; SingleLinkNode *q; /*要删除的元素x*/ i find(*Head,x); if(!i) { printf(元素x【%d】不存在100006\n, x); return 100006; } p (*Head); j1; while(ji) { j; p p-next; } q p-next; p-next q-next; free(q); /*释放内存*/ return 0; }4.完整的demomain.c#include stdio.h #include string.h #include SingleLinkList.c #include welcome.h int main(int argc, char argv[]) { SingleLinkList Head; DataType x; int i,m,n,cmd; for(i0;istrlen(welcome);i) { printf(%c,welcome[i]); for(m0;m1000;m) for(n0;n1000;n) { ; } } printf(-----------简单链表演示程序----------n); do { printf(1. 初始化链表表n); printf(2. 插入元素头插法n); printf(3. 插入元素尾插法n); printf(4. 插入元素在位置i插入n); printf(5. 查找元素xn); printf(6. 求链表长度n); printf(7. 输出链表n); printf(8. 删除元素n); printf(10. 帮助n); printf(0. 退出n); printf(请输入您要进行的操作1~6,0退出); scanf(%d, cmd); switch(cmd) { case 1 if(!init(Head)) { printf(链表已初始化n); } break; case 2 printf(请输入插入元素xx); scanf(%d,x); if(!insert_head(Head,x)) { printf(元素%d已插入n, x); } break; case 3 printf(请输入插入元素xx); scanf(%d,x); if(!insert_tail(Head,x)) { printf(元素%d已插入n, x); } break; case 4 printf(请输入插入元素位置i和元素xix); scanf(%d,%d, i, x); if(!insert(Head, i, x)) { printf(已在位置%d插入元素%dn,i, x); } break; case 5 printf(请输入要查找的元素x); scanf(%d, x); if((i find(Head,x))) { printf(元素%d存在在链表位置%d.n, x, i); } else { printf(在链表中未找到元素x。n); } break; case 6 printf(链表的长度为%dn, length(Head)); break; case 7 print(Head); break; case 8 printf(请输入要删除的元素x); scanf(%d, x); if(!delete(Head, x)) { printf(元素x【%d】已删除!n, x); } break; case 10 printf( 本程序为链表的演示程序由张亚辉设计开发程序完成了链表运算功能。。。n); break; } }while(cmd ! 0); return 0; }SingleLinkList.c/* SingleLinkList.c */ #include SingleLinkList.h #include stdlib.h #include stdio.h /*1. 初始化*/ int init(SingleLinkList **Head) { if(Head ! NULL) { /*申请内存*/ (*Head) (SingleLinkList*)malloc(sizeof(SingleLinkList)); /*判断内存申请是否成功*/ if(*Head NULL) { printf(申请内存错误 初始化失败[100001]\n); return 100001; } // (*Head)-next NULL; /*循环链表*/ /* (*Head)-next *Head; */ (*Head)-next *Head; return 0; } else { printf(该链表已经初始化请删除后再执行此操作[100002]\n); return 100002; } } /*2. 插入元素,头插法*/ int insert_head(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; newNode-next (*Head)-next; (*Head)-next newNode; return 0; } /*2. 插入元素 尾插法*/ int insert_tail(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; SingleLinkNode *p; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; // newNode-next NULL; /* 循环链表 newNode-next *Head; */ newNode-next *Head; p (*Head); while(p-next ! NULL p-next ! *Head) { p p-next; } p-next newNode; return 0; } /*2. 插入元素在位置i处插入元素x */ int insert(SingleLinkList **Head, int i, DataType x) { int j; SingleLinkNode *p; SingleLinkNode *newNode; /*对i进行判断0ilength1*/ if(i1 || ilength(*Head)1) { printf(位置i不是链表有效位置[100005]\n); return 100005; } p (*Head); j 1; while(ji) { j; p p-next; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); /*此处省略检测newNode是否申请成功*/ newNode-data x; newNode-next p-next; p-next newNode; return 0; } /*3. 删除元素, 删除值为x的元素*/ int delete(SingleLinkList **Head, DataType x) { int i; int j; SingleLinkNode *p; SingleLinkNode *q; /*要删除的元素x*/ i find(*Head,x); if(!i) { printf(元素x【%d】不存在100006\n, x); return 100006; } p (*Head); j1; while(ji) { j; p p-next; } q p-next; p-next q-next; free(q); /*释放内存*/ return 0; } /*5. 查找值为x的元素返回位置i */ int find(SingleLinkList *Head, DataType x) { int i; SingleLinkNode *p; i 1; p Head-next; while(p p-data ! x) /*while( p! Head p-data ! x) */ { i; p p-next; } if(!p) /* if(p-next Head) */ { return 0; } else { return i; } } /*4. 链表长度*/ int length(SingleLinkList *Head) { int len0; SingleLinkNode *p; p Head-next; // while(p) /* while(p!Head) */ while(p!Head) { len; p p-next; } return len; } /*6.输出链表*/ void print(SingleLinkList *Head) { SingleLinkNode *p; int i0; p Head-next; if(!p) /* if(p!Head) */ { printf(链表为空\n); return; } // while(p!Head) // { // p p-next; // } // while(p) /* while(p!Head) */ while(p ! Head) { printf(Node[%d]. %d\n, i, p-data); p p-next; } }SingleLinkList.h/* SingleLinkList.h */ typedef int DataType; typedef struct node { DataType data; /*数据域*/ struct node *next; /*指针域*/ }SingleLinkList, SingleLinkNode; /*1. 初始化*/ int init(SingleLinkList **Head); /*2. 插入元素,头插法*/ int insert_head(SingleLinkList **Head, DataType x); /*2. 插入元素 尾插法*/ int insert_tail(SingleLinkList **Head, DataType x); /*3. 删除元素*/ /*6.输出链表*/ void print(SingleLinkList *Head);welcome.hchar welcome[] \n\ /\ \n\ ( *)/\ \n\ )( / \ \n\ __________/ ) / \ \n\ \___ / / \\ \ \n\ \____ _/ / (**) \ \n\ / \__/ (----------) \n\ /____|__//_ ( 送给您- ) \n\ | ( 亲爱的 ) \n\ | ( )\n\ | (____)\n\ _|__\n\ \\ ☆新年 . 快乐☆\n\n;5.知识拓展——一元多项式设计及加法运算#include stdio.h #includestdlib.h typedef struct node//一元多项式定义 { float coef; // 系数 int expn; // 指数 struct node *next; // 后继 } pnode, *polynomial; // 一元多项式的创建 polynomial createpolyn(polynomial p, int m) { int i; polynomial q, pre, s; // 节点 qpres p (polynomial)malloc(sizeof(pnode)); // 生成新节点 p-next 0; // 先建立一个头节点的单链表 p-expn -1; // 头节点指数值设为-1 for (i 0; i m; i) // 依次输入m个非零值 { s (polynomial)malloc(sizeof(pnode)); // 生成新节点 printf(输入系数和指数); scanf(%f%d, s-coef, s-expn); // 输入系数和指数 pre p; // pre来保存q的前驱 q p-next; // q初值为首节点 while (q q-expn s-expn) // 找到第一个大于输入项指数的项q { pre q; q q-next; } s-next q;pre-next s; // 将输入项s插入到q和pre之间 } printf(--创建成功--\n); return p; }// 一元多项式打印 void pri(polynomial p) { polynomial q; int id 1; q p-next; // 第一项首结点 printf(加法运算后结果为:\n); while (q) { printf(第%d个结点系数%f,指数%d\n, id, q-coef, q-expn); // 结点后移 q q-next; id; } // 一元多项式相加 return ; } polynomial addpolyn(polynomial pa, polynomial pb) { polynomial p1, p2, p3, q; int sum; // 系数和 sum p1 pa-next;p2 pb-next; p3 pa; // p3 指向和多项式的当前结点 while (p1 p2) // p1和p2均非空 { if (p1-expn p2-expn) // 指数相同 { sum p1-coef p2-coef; // sum 保存两项的系数和 if (sum) // 系数和不为0 { p1-coef sum; // 修改结点p1的系数值 p3-next p1; p3 p1; // 将修改后的结点p1链在p3之后 p1 p1-next; // p1 指向后一项 q p2; p2 p2-next;free(q); // 删除pb当前结点q } else // 系数和为0 { q p1; p1 p1-next;free(q); // 删除pa当前结点pl q p2; p2 p2-next; free(q); // 删除pb当前结点p2 } } else { if (p1-expn p2-expn) // pa当前结点p1的指数值小 { p3-next p1; // 将p1链在p3之后 p3 p1; // p3 指向pl p1 p1-next; // p1 指向后一场 } else { p3-next p2; // pb当前结点p2的指数值小 p3 p2; // 将p2链接在p3之后 p2 p2-next; // p2指向后一项 } } } p3-next p1 ? p1 : p2; // 插入非空多项式的剩余段 free(pb); // 释放pb的头结点 return pa; // 返回和多项式 } main() { printf(一元多项式演示程序由张亚辉完成\n\n\n); int m; polynomial pa, pb, pc; // 声明一元多项式 printf(创建一元多项式\n); printf(创建 A 项数:\n); scanf(%d, m); // 创建pa项数 pa createpolyn(pa, m); // 创建一元多项式pa printf(创建 B 项数:\n); scanf(%d, m); // 创建pb项数 pb createpolyn(pb, m); // 创建一元多项式pb printf(一元多项式相加\n); pc addpolyn(pa, pb); // 一元多项式相加 pri(pc); // 打印一元多项式 printf(END\n); }6.小结对于我这个刚学数据结构和C语言的萌新来说这次的任务难度是有点大看课本就像看天书一样然后又去网上搜索各种资料和相关知识结合老师在课堂上所讲的内容并在线下与室友讨论总算有了一点点的了解。7.参考文献《数据结构C语言版》百度百科CSDN知乎菜鸟教程无所不能的互联网 链式存储结构
1.链表的介绍1.1 什么是单链表单链表是用一组任意的存储单元来存放线性表的结点这组存储单元既可以是连续的的也可以是不连续的甚至零散地分布在内存中的任何位置上。为了能正确表示结点的逻错关系在存储每个结点值的同时还必须存储指示其后继结点的地址(或位置)息这个信息称为指针或链。这两部分信息组成了链表中的结点结构。链式存储结构的优点1空间利用率高需要一个空间就分配一个空间2数据元素的逻辑次序靠节点的指针来指示插入和删除时不需要移动数据结点,任意位置插入删除时间复杂度为O(1)单链表的定义typedef struct SListNode { DateType data; //结点的数据域 struct SListNode *next; //结点的指针域 }SListNode;结点空间开辟执行 SListNode*p之后该指针变量指向的结点变量并未开辟空间程序执行过程中当需要时才产生需要执行p(SListNode*)malloc(sizeof(SListNode))后分配一个类型为ListNode的结点变量的空间。结点空间释放当p指向的结点变量不再需要的时候可以通过执行free(p)释放。1.2 什么是循环链表循环链表是一种特殊的链表数据结构与单向链表或双向链表相比循环链表的最后一个节点的下一个节点指向第一个节点从而形成一个环形结构。因此循环链表可以在最后一个节点后继续添加节点并且可以像单向链表或双向链表一样遍历、查找和删除节点。循环链表通常有一个头指针和一个尾指针它们指向第一个节点和最后一个节点以便在添加或删除节点时快速定位。循环链表可以用于解决某些问题例如模拟一个环形队列或者用于实现循环播放的音乐列表等。循环链表的优点在于它具有链表的灵活性同时可以避免在添加或删除节点时需要遍历整个链表的缺点循环链表的任意元素都有一个前驱和一个后继所有数据元素在关系上构成逻辑上的环。循环链表是一种特殊的单链表尾结点的指针指向首结点的地址。1.3 单链表和循环列表的区别1循环链表的操作和单链表基本一致。2差别仅在于当遍历链表时判别当前指针P是否指向表尾结点的终止条件不同。3由于循环链表中没有NULL指针故涉及遍历操作时其终止条件就不再像单链表那样判断p或p-next是否为空而是判断它们是否等于头指针。2.循环链表的基本运算循环链表的基本运算包括以下几种1. 初始化链表创建一个空的链表。2. 插入结点在链表中插入一个新的结点。3. 删除结点从链表中删除一个指定的结点。4. 遍历链表遍历链表中的所有结点并对每个结点执行某些操作。5. 查找结点在链表中查找一个指定的结点。6. 修改结点修改链表中一个指定的结点的数据。这些基本运算可以帮助我们实现各种不同的链表应用例如实现栈、队列、优先队列等数据结构。3.代码的实现循环链表的初始化int init(SingleLinkList **Head) { if(Head ! NULL) { /*申请内存*/ (*Head) (SingleLinkList*)malloc(sizeof(SingleLinkList)); /*判断内存申请是否成功*/ if(*Head NULL) { printf(申请内存错误 初始化失败[100001]\n); return 100001; } // (*Head)-next NULL; /*循环链表*/ /* (*Head)-next *Head; */ (*Head)-next *Head; return 0; } else { printf(该链表已经初始化请删除后再执行此操作[100002]\n); return 100002; } }插入元素之头插法int insert_head(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; newNode-next (*Head)-next; (*Head)-next newNode; return 0; }插入元素之尾插法int insert_tail(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; SingleLinkNode *p; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; // newNode-next NULL; /* 循环链表 newNode-next *Head; */ newNode-next *Head; p (*Head); while(p-next ! NULL p-next ! *Head) { p p-next; } p-next newNode; return 0; }插入元素在位置i处插入元素xint insert(SingleLinkList **Head, int i, DataType x) { int j; SingleLinkNode *p; SingleLinkNode *newNode; /*对i进行判断0ilength1*/ if(i1 || ilength(*Head)1) { printf(位置i不是链表有效位置[100005]\n); return 100005; } p (*Head); j 1; while(ji) { j; p p-next; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); /*此处省略检测newNode是否申请成功*/ newNode-data x; newNode-next p-next; p-next newNode; return 0; }查找值为x的元素返回位置iint find(SingleLinkList *Head, DataType x) { int i; SingleLinkNode *p; i 1; p Head-next; while(p p-data ! x) /*while( p! Head p-data ! x) */ { i; p p-next; } if(!p) /* if(p-next Head) */ { return 0; } else { return i; } }链表长度int length(SingleLinkList *Head) { int len0; SingleLinkNode *p; p Head-next; // while(p) /* while(p!Head) */ while(p!Head) { len; p p-next; } return len; }输出链表void print(SingleLinkList *Head) { SingleLinkNode *p; int i0; p Head-next; if(!p) /* if(p!Head) */ { printf(链表为空\n); return; } // while(p!Head) // { // p p-next; // } // while(p) /* while(p!Head) */ while(p ! Head) { printf(Node[%d]. %d\n, i, p-data); p p-next; } }删除元素值为x的元素int delete(SingleLinkList **Head, DataType x) { int i; int j; SingleLinkNode *p; SingleLinkNode *q; /*要删除的元素x*/ i find(*Head,x); if(!i) { printf(元素x【%d】不存在100006\n, x); return 100006; } p (*Head); j1; while(ji) { j; p p-next; } q p-next; p-next q-next; free(q); /*释放内存*/ return 0; }4.完整的demomain.c#include stdio.h #include string.h #include SingleLinkList.c #include welcome.h int main(int argc, char argv[]) { SingleLinkList Head; DataType x; int i,m,n,cmd; for(i0;istrlen(welcome);i) { printf(%c,welcome[i]); for(m0;m1000;m) for(n0;n1000;n) { ; } } printf(-----------简单链表演示程序----------n); do { printf(1. 初始化链表表n); printf(2. 插入元素头插法n); printf(3. 插入元素尾插法n); printf(4. 插入元素在位置i插入n); printf(5. 查找元素xn); printf(6. 求链表长度n); printf(7. 输出链表n); printf(8. 删除元素n); printf(10. 帮助n); printf(0. 退出n); printf(请输入您要进行的操作1~6,0退出); scanf(%d, cmd); switch(cmd) { case 1 if(!init(Head)) { printf(链表已初始化n); } break; case 2 printf(请输入插入元素xx); scanf(%d,x); if(!insert_head(Head,x)) { printf(元素%d已插入n, x); } break; case 3 printf(请输入插入元素xx); scanf(%d,x); if(!insert_tail(Head,x)) { printf(元素%d已插入n, x); } break; case 4 printf(请输入插入元素位置i和元素xix); scanf(%d,%d, i, x); if(!insert(Head, i, x)) { printf(已在位置%d插入元素%dn,i, x); } break; case 5 printf(请输入要查找的元素x); scanf(%d, x); if((i find(Head,x))) { printf(元素%d存在在链表位置%d.n, x, i); } else { printf(在链表中未找到元素x。n); } break; case 6 printf(链表的长度为%dn, length(Head)); break; case 7 print(Head); break; case 8 printf(请输入要删除的元素x); scanf(%d, x); if(!delete(Head, x)) { printf(元素x【%d】已删除!n, x); } break; case 10 printf( 本程序为链表的演示程序由张亚辉设计开发程序完成了链表运算功能。。。n); break; } }while(cmd ! 0); return 0; }SingleLinkList.c/* SingleLinkList.c */ #include SingleLinkList.h #include stdlib.h #include stdio.h /*1. 初始化*/ int init(SingleLinkList **Head) { if(Head ! NULL) { /*申请内存*/ (*Head) (SingleLinkList*)malloc(sizeof(SingleLinkList)); /*判断内存申请是否成功*/ if(*Head NULL) { printf(申请内存错误 初始化失败[100001]\n); return 100001; } // (*Head)-next NULL; /*循环链表*/ /* (*Head)-next *Head; */ (*Head)-next *Head; return 0; } else { printf(该链表已经初始化请删除后再执行此操作[100002]\n); return 100002; } } /*2. 插入元素,头插法*/ int insert_head(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; newNode-next (*Head)-next; (*Head)-next newNode; return 0; } /*2. 插入元素 尾插法*/ int insert_tail(SingleLinkList **Head, DataType x) { SingleLinkNode *newNode; SingleLinkNode *p; if(0) { printf(链表未初始化[100003]\n); return 100003; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf(申请节点内存空间失败[100004]\n); return 100004; } newNode-data x; // newNode-next NULL; /* 循环链表 newNode-next *Head; */ newNode-next *Head; p (*Head); while(p-next ! NULL p-next ! *Head) { p p-next; } p-next newNode; return 0; } /*2. 插入元素在位置i处插入元素x */ int insert(SingleLinkList **Head, int i, DataType x) { int j; SingleLinkNode *p; SingleLinkNode *newNode; /*对i进行判断0ilength1*/ if(i1 || ilength(*Head)1) { printf(位置i不是链表有效位置[100005]\n); return 100005; } p (*Head); j 1; while(ji) { j; p p-next; } newNode (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); /*此处省略检测newNode是否申请成功*/ newNode-data x; newNode-next p-next; p-next newNode; return 0; } /*3. 删除元素, 删除值为x的元素*/ int delete(SingleLinkList **Head, DataType x) { int i; int j; SingleLinkNode *p; SingleLinkNode *q; /*要删除的元素x*/ i find(*Head,x); if(!i) { printf(元素x【%d】不存在100006\n, x); return 100006; } p (*Head); j1; while(ji) { j; p p-next; } q p-next; p-next q-next; free(q); /*释放内存*/ return 0; } /*5. 查找值为x的元素返回位置i */ int find(SingleLinkList *Head, DataType x) { int i; SingleLinkNode *p; i 1; p Head-next; while(p p-data ! x) /*while( p! Head p-data ! x) */ { i; p p-next; } if(!p) /* if(p-next Head) */ { return 0; } else { return i; } } /*4. 链表长度*/ int length(SingleLinkList *Head) { int len0; SingleLinkNode *p; p Head-next; // while(p) /* while(p!Head) */ while(p!Head) { len; p p-next; } return len; } /*6.输出链表*/ void print(SingleLinkList *Head) { SingleLinkNode *p; int i0; p Head-next; if(!p) /* if(p!Head) */ { printf(链表为空\n); return; } // while(p!Head) // { // p p-next; // } // while(p) /* while(p!Head) */ while(p ! Head) { printf(Node[%d]. %d\n, i, p-data); p p-next; } }SingleLinkList.h/* SingleLinkList.h */ typedef int DataType; typedef struct node { DataType data; /*数据域*/ struct node *next; /*指针域*/ }SingleLinkList, SingleLinkNode; /*1. 初始化*/ int init(SingleLinkList **Head); /*2. 插入元素,头插法*/ int insert_head(SingleLinkList **Head, DataType x); /*2. 插入元素 尾插法*/ int insert_tail(SingleLinkList **Head, DataType x); /*3. 删除元素*/ /*6.输出链表*/ void print(SingleLinkList *Head);welcome.hchar welcome[] \n\ /\ \n\ ( *)/\ \n\ )( / \ \n\ __________/ ) / \ \n\ \___ / / \\ \ \n\ \____ _/ / (**) \ \n\ / \__/ (----------) \n\ /____|__//_ ( 送给您- ) \n\ | ( 亲爱的 ) \n\ | ( )\n\ | (____)\n\ _|__\n\ \\ ☆新年 . 快乐☆\n\n;5.知识拓展——一元多项式设计及加法运算#include stdio.h #includestdlib.h typedef struct node//一元多项式定义 { float coef; // 系数 int expn; // 指数 struct node *next; // 后继 } pnode, *polynomial; // 一元多项式的创建 polynomial createpolyn(polynomial p, int m) { int i; polynomial q, pre, s; // 节点 qpres p (polynomial)malloc(sizeof(pnode)); // 生成新节点 p-next 0; // 先建立一个头节点的单链表 p-expn -1; // 头节点指数值设为-1 for (i 0; i m; i) // 依次输入m个非零值 { s (polynomial)malloc(sizeof(pnode)); // 生成新节点 printf(输入系数和指数); scanf(%f%d, s-coef, s-expn); // 输入系数和指数 pre p; // pre来保存q的前驱 q p-next; // q初值为首节点 while (q q-expn s-expn) // 找到第一个大于输入项指数的项q { pre q; q q-next; } s-next q;pre-next s; // 将输入项s插入到q和pre之间 } printf(--创建成功--\n); return p; }// 一元多项式打印 void pri(polynomial p) { polynomial q; int id 1; q p-next; // 第一项首结点 printf(加法运算后结果为:\n); while (q) { printf(第%d个结点系数%f,指数%d\n, id, q-coef, q-expn); // 结点后移 q q-next; id; } // 一元多项式相加 return ; } polynomial addpolyn(polynomial pa, polynomial pb) { polynomial p1, p2, p3, q; int sum; // 系数和 sum p1 pa-next;p2 pb-next; p3 pa; // p3 指向和多项式的当前结点 while (p1 p2) // p1和p2均非空 { if (p1-expn p2-expn) // 指数相同 { sum p1-coef p2-coef; // sum 保存两项的系数和 if (sum) // 系数和不为0 { p1-coef sum; // 修改结点p1的系数值 p3-next p1; p3 p1; // 将修改后的结点p1链在p3之后 p1 p1-next; // p1 指向后一项 q p2; p2 p2-next;free(q); // 删除pb当前结点q } else // 系数和为0 { q p1; p1 p1-next;free(q); // 删除pa当前结点pl q p2; p2 p2-next; free(q); // 删除pb当前结点p2 } } else { if (p1-expn p2-expn) // pa当前结点p1的指数值小 { p3-next p1; // 将p1链在p3之后 p3 p1; // p3 指向pl p1 p1-next; // p1 指向后一场 } else { p3-next p2; // pb当前结点p2的指数值小 p3 p2; // 将p2链接在p3之后 p2 p2-next; // p2指向后一项 } } } p3-next p1 ? p1 : p2; // 插入非空多项式的剩余段 free(pb); // 释放pb的头结点 return pa; // 返回和多项式 } main() { printf(一元多项式演示程序由张亚辉完成\n\n\n); int m; polynomial pa, pb, pc; // 声明一元多项式 printf(创建一元多项式\n); printf(创建 A 项数:\n); scanf(%d, m); // 创建pa项数 pa createpolyn(pa, m); // 创建一元多项式pa printf(创建 B 项数:\n); scanf(%d, m); // 创建pb项数 pb createpolyn(pb, m); // 创建一元多项式pb printf(一元多项式相加\n); pc addpolyn(pa, pb); // 一元多项式相加 pri(pc); // 打印一元多项式 printf(END\n); }6.小结对于我这个刚学数据结构和C语言的萌新来说这次的任务难度是有点大看课本就像看天书一样然后又去网上搜索各种资料和相关知识结合老师在课堂上所讲的内容并在线下与室友讨论总算有了一点点的了解。7.参考文献《数据结构C语言版》百度百科CSDN知乎菜鸟教程无所不能的互联网