尧图网页设计 
SList.h#pragmaonce#includestdio.h#includeassert.h#includestdlib.h#includestdbool.h// 实现带头的单链表(头结点可以看做第0个结点因为它的数据域不存储有效数据)// 定义单链表的结点typedefintElemType;typedefstructLNode{//每个结点中存储一个数据以及下一个结点的地址ElemType data;structLNode*next;}LNode,*LinkList;// 将struct LNode重命名为LNode将struct LNode*重命名为LinkList// 单链表的初始化boolListInit(LinkListL);// L是头结点的地址的别名L的值变了头结点的地址也就变了// 将数据域为e的新结点插到第i个存储有效数据的位置(i1且i原链表中有效结点个数1)boolListInsert(LinkListL,inti,ElemType e);// i原链表中有效结点个数1时表示把新结点插在链表的尾部// 本项目实现的是带头的单链表插入新结点时头结点的地址不会变化因此这里的形参可以不加// 但如果实现的是不带头的单链表这里的形参必须加// 后插操作在p指向的结点后插入数据域为e的新结点boolInsertNextNode(LNode*p,ElemType e);// 前插操作在p指向的结点之前插入数据域为e的新结点boolInsertPriorNode(LNode*p,ElemType e);// 如果形参部分给了头结点的地址则可以从头结点遍历到p指向的结点的前一个结点再插入新结点// 删除第i个存储有效数据的结点并把该结点中数据域的值赋值给变量eboolListDelete(LinkListL,inti,ElemTypee);// 本项目实现的是带头结点的单链表删除存储有效数据的结点时头结点的地址不会变化因此这里的形参也可以不加// 但如果实现的是不带头结点的单链表这里的形参必须加// 删除p指向的结点boolDeleteNode(LNode*p);// 若形参部分给了头结点的地址可以从头结点遍历到p指向的结点的前一个结点再删除p指向的结点。时间复杂度为O(n)// 若形参的部分没有给头结点的地址则可以通过“偷天换日”的操作从逻辑上删除该结点时间复杂度为O(1)// 虽然通过“偷天换日”的操作使得时间复杂度降低了但是这种方式不能删除尾结点程序会报错// 查找第i个存储实际数据的结点,若找到了就返回该结点的地址否则返回NULLLNode*GetElem(LinkList L,inti);// L接收头结点的地址// 按值查找:查找有效结点中第一个数据域的值为e的结点如果找到了就返回该结点的地址没找到就返回NULLLNode*LocateElem(LinkList L,ElemType e);// 求单链表的长度(即有效结点的个数)intLength(LinkList L);SList.cpp#define_CRT_SECURE_NO_WARNINGS1#includeSList.h// 单链表的初始化boolListInit(LinkListL)// L是头结点的地址的别名(也就是test函数中plist的别名)L的值变了头结点的地址也就变了{// 申请头结点的空间L(LNode*)malloc(sizeof(LNode));// L接收头结点的地址if(LNULL)// L NULL时表示头结点的空间申请失败returnfalse;L-nextNULL;returntrue;}// 将数据域为e的新结点插到第i个存储有效数据的位置(i1且i原链表中有效结点个数1)// i原链表中有效结点个数1时表示把新结点插在链表的尾部boolListInsert(LinkListL,inti,ElemType e){// 本项目实现的是带头的单链表插入新结点时头结点的地址不会变化因此这里的形参可以不加// 但如果实现的是不带头的单链表这里的形参必须加if(i1)returnfalse;// 先找到第i-1个存储有效数据的结点再将新结点查到它后面intj0;LNode*pL;while(p!NULLji-1)// j从0变化到i-2循环i-1次{pp-next;j;}if(pNULL)// 当pNULL时说明i的值不合法说明此时i原链表中有效结点的个数1returnfalse;//此时p指向第i-1个存储有效数据的结点// 申请新结点的空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)// 如果新结点的空间申请失败returnfalse;s-datae;s-nextp-next;p-nexts;returntrue;}// 后插操作在p指向的结点后插入数据域为e的新结点boolInsertNextNode(LNode*p,ElemType e){if(pNULL)returnfalse;// 表示插入失败// 插入新结点前申请新结点的空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;//表示新结点的空间申请失败s-datae;s-nextp-next;p-nexts;returntrue;}// 前插操作在p指向的结点之前插入数据域为e的新结点boolInsertPriorNode(LNode*p,ElemType e){if(pNULL)returnfalse;//说明p指向的是无效结点插入失败// 申请新结点的空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)// 如果新结点的空间申请失败returnfalse;// 先将新结点插入到p指向的结点后面再交换这两个结点中数据域的值实现偷天换日的效果s-nextp-next;p-nexts;s-datap-data;p-datae;returntrue;}// 删除第i个存储有效数据的结点并把该结点中数据域的值赋值给变量eboolListDelete(LinkListL,inti,ElemTypee){if(i1)returnfalse;// 先找到第i-1个存储有效数据的结点再删除第i个结点LNode*pL;// p此时指向头结点intj0;while(p!NULLji-1)// j从0增加到i-2循环i-1次{pp-next;j;}if(pNULL)// 当pNULL时说明i原链表中有效结点的个数i的值不合法returnfalse;if(p-nextNULL)// 当p-nextNULL时说明p指向尾结点需要删除尾结点后面的结点显然是非法行为returnfalse;// 此时p指向第i-1个存储有效数据的结点LNode*delep-next;//dele指向需要删除的结点edele-data;// 将需要删除的结点中数据域的值赋给变量e并修改该函数调用时实参(m)的值p-nextdele-next;free(dele);// 释放需要删除的结点的空间deleNULL;returntrue;}// 删除p指向的结点(该代码不能删除尾结点否则会导致对空指针解引用)boolDeleteNode(LNode*p){if(pNULL)returnfalse;// 若p指向的是无效结点则返回NULLLNode*qp-next;// q指向待删除结点的后面一个结点// 先将q指向的结点中数据域的值赋给p指向的结点再删除q指向的结点。// 这种操作在逻辑上等价于删除p指向的结点p-dataq-data;p-nextq-next;free(q);// 释放q指向的结点的空间qNULL;returntrue;}// 查找第i个存储实际数据的结点,若找到了就返回该结点的地址否则返回NULLLNode*GetElem(LinkList L,inti)// L接收头结点的地址{if(i0)// 比如i-1时表示查找第-1个存储实际数据的结点显然是非法操作返回NULLreturnNULL;LNode*pL;// p此时指向头结点若要找到第i个存储有效数据的结点需要向后遍历i次intj0;while(p!NULLji)// j从0增加到i-1循环i次{pp-next;j;}returnp;/* 补充1当i0时表示查找第头结点因为头结点后面的结点才是第1个存储有效数据的结点 此时while循环会循环0次最后返回头结点的地址 补充2当i链表中有效结点的个数时p最终会等于NULL直接退出while循环返回p,即返回NULL */}// 按值查找:查找有效结点中第一个数据域的值为e的结点如果找到了就返回该结点的地址没找到就返回NULLLNode*LocateElem(LinkList L,ElemType e){LNode*pL-next;// p指向第一个存储有效数据的结点while(p!NULLp-data!e)pp-next;returnp;// 若找到该结点就返回该结点的地址否则返回NULL}// 求单链表的长度(即有效结点的个数)intLength(LinkList L){LNode*pL;// p此时指向头结点intcount0;while(p-next!NULL){pp-next;count;}returncount;}Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeSList.hvoidTest(){// 创建一个空的带头单链表即一个头结点LNode*plistNULL;// plist是头指针指向头结点// 测试单链表的初始化ListInit(plist);// 分别插入数据域的值为1、2、3的结点 即头结点-1-2-3for(inti1;i3;i){ListInsert(plist,i,i);}// 删除第2个存储有效数据的结点ElemType m;ListDelete(plist,2,m);printf(删除的结点中存储的数据是%d\n,m);// 求单链表的长度(即有效结点的个数)printf(单链表的长度为:%d,Length(plist));}intmain(){Test();return0;} 采用链式结构实现线性表（实现带头结点的单链表）
SList.h#pragmaonce#includestdio.h#includeassert.h#includestdlib.h#includestdbool.h// 实现带头的单链表(头结点可以看做第0个结点因为它的数据域不存储有效数据)// 定义单链表的结点typedefintElemType;typedefstructLNode{//每个结点中存储一个数据以及下一个结点的地址ElemType data;structLNode*next;}LNode,*LinkList;// 将struct LNode重命名为LNode将struct LNode*重命名为LinkList// 单链表的初始化boolListInit(LinkListL);// L是头结点的地址的别名L的值变了头结点的地址也就变了// 将数据域为e的新结点插到第i个存储有效数据的位置(i1且i原链表中有效结点个数1)boolListInsert(LinkListL,inti,ElemType e);// i原链表中有效结点个数1时表示把新结点插在链表的尾部// 本项目实现的是带头的单链表插入新结点时头结点的地址不会变化因此这里的形参可以不加// 但如果实现的是不带头的单链表这里的形参必须加// 后插操作在p指向的结点后插入数据域为e的新结点boolInsertNextNode(LNode*p,ElemType e);// 前插操作在p指向的结点之前插入数据域为e的新结点boolInsertPriorNode(LNode*p,ElemType e);// 如果形参部分给了头结点的地址则可以从头结点遍历到p指向的结点的前一个结点再插入新结点// 删除第i个存储有效数据的结点并把该结点中数据域的值赋值给变量eboolListDelete(LinkListL,inti,ElemTypee);// 本项目实现的是带头结点的单链表删除存储有效数据的结点时头结点的地址不会变化因此这里的形参也可以不加// 但如果实现的是不带头结点的单链表这里的形参必须加// 删除p指向的结点boolDeleteNode(LNode*p);// 若形参部分给了头结点的地址可以从头结点遍历到p指向的结点的前一个结点再删除p指向的结点。时间复杂度为O(n)// 若形参的部分没有给头结点的地址则可以通过“偷天换日”的操作从逻辑上删除该结点时间复杂度为O(1)// 虽然通过“偷天换日”的操作使得时间复杂度降低了但是这种方式不能删除尾结点程序会报错// 查找第i个存储实际数据的结点,若找到了就返回该结点的地址否则返回NULLLNode*GetElem(LinkList L,inti);// L接收头结点的地址// 按值查找:查找有效结点中第一个数据域的值为e的结点如果找到了就返回该结点的地址没找到就返回NULLLNode*LocateElem(LinkList L,ElemType e);// 求单链表的长度(即有效结点的个数)intLength(LinkList L);SList.cpp#define_CRT_SECURE_NO_WARNINGS1#includeSList.h// 单链表的初始化boolListInit(LinkListL)// L是头结点的地址的别名(也就是test函数中plist的别名)L的值变了头结点的地址也就变了{// 申请头结点的空间L(LNode*)malloc(sizeof(LNode));// L接收头结点的地址if(LNULL)// L NULL时表示头结点的空间申请失败returnfalse;L-nextNULL;returntrue;}// 将数据域为e的新结点插到第i个存储有效数据的位置(i1且i原链表中有效结点个数1)// i原链表中有效结点个数1时表示把新结点插在链表的尾部boolListInsert(LinkListL,inti,ElemType e){// 本项目实现的是带头的单链表插入新结点时头结点的地址不会变化因此这里的形参可以不加// 但如果实现的是不带头的单链表这里的形参必须加if(i1)returnfalse;// 先找到第i-1个存储有效数据的结点再将新结点查到它后面intj0;LNode*pL;while(p!NULLji-1)// j从0变化到i-2循环i-1次{pp-next;j;}if(pNULL)// 当pNULL时说明i的值不合法说明此时i原链表中有效结点的个数1returnfalse;//此时p指向第i-1个存储有效数据的结点// 申请新结点的空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)// 如果新结点的空间申请失败returnfalse;s-datae;s-nextp-next;p-nexts;returntrue;}// 后插操作在p指向的结点后插入数据域为e的新结点boolInsertNextNode(LNode*p,ElemType e){if(pNULL)returnfalse;// 表示插入失败// 插入新结点前申请新结点的空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;//表示新结点的空间申请失败s-datae;s-nextp-next;p-nexts;returntrue;}// 前插操作在p指向的结点之前插入数据域为e的新结点boolInsertPriorNode(LNode*p,ElemType e){if(pNULL)returnfalse;//说明p指向的是无效结点插入失败// 申请新结点的空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)// 如果新结点的空间申请失败returnfalse;// 先将新结点插入到p指向的结点后面再交换这两个结点中数据域的值实现偷天换日的效果s-nextp-next;p-nexts;s-datap-data;p-datae;returntrue;}// 删除第i个存储有效数据的结点并把该结点中数据域的值赋值给变量eboolListDelete(LinkListL,inti,ElemTypee){if(i1)returnfalse;// 先找到第i-1个存储有效数据的结点再删除第i个结点LNode*pL;// p此时指向头结点intj0;while(p!NULLji-1)// j从0增加到i-2循环i-1次{pp-next;j;}if(pNULL)// 当pNULL时说明i原链表中有效结点的个数i的值不合法returnfalse;if(p-nextNULL)// 当p-nextNULL时说明p指向尾结点需要删除尾结点后面的结点显然是非法行为returnfalse;// 此时p指向第i-1个存储有效数据的结点LNode*delep-next;//dele指向需要删除的结点edele-data;// 将需要删除的结点中数据域的值赋给变量e并修改该函数调用时实参(m)的值p-nextdele-next;free(dele);// 释放需要删除的结点的空间deleNULL;returntrue;}// 删除p指向的结点(该代码不能删除尾结点否则会导致对空指针解引用)boolDeleteNode(LNode*p){if(pNULL)returnfalse;// 若p指向的是无效结点则返回NULLLNode*qp-next;// q指向待删除结点的后面一个结点// 先将q指向的结点中数据域的值赋给p指向的结点再删除q指向的结点。// 这种操作在逻辑上等价于删除p指向的结点p-dataq-data;p-nextq-next;free(q);// 释放q指向的结点的空间qNULL;returntrue;}// 查找第i个存储实际数据的结点,若找到了就返回该结点的地址否则返回NULLLNode*GetElem(LinkList L,inti)// L接收头结点的地址{if(i0)// 比如i-1时表示查找第-1个存储实际数据的结点显然是非法操作返回NULLreturnNULL;LNode*pL;// p此时指向头结点若要找到第i个存储有效数据的结点需要向后遍历i次intj0;while(p!NULLji)// j从0增加到i-1循环i次{pp-next;j;}returnp;/* 补充1当i0时表示查找第头结点因为头结点后面的结点才是第1个存储有效数据的结点 此时while循环会循环0次最后返回头结点的地址 补充2当i链表中有效结点的个数时p最终会等于NULL直接退出while循环返回p,即返回NULL */}// 按值查找:查找有效结点中第一个数据域的值为e的结点如果找到了就返回该结点的地址没找到就返回NULLLNode*LocateElem(LinkList L,ElemType e){LNode*pL-next;// p指向第一个存储有效数据的结点while(p!NULLp-data!e)pp-next;returnp;// 若找到该结点就返回该结点的地址否则返回NULL}// 求单链表的长度(即有效结点的个数)intLength(LinkList L){LNode*pL;// p此时指向头结点intcount0;while(p-next!NULL){pp-next;count;}returncount;}Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeSList.hvoidTest(){// 创建一个空的带头单链表即一个头结点LNode*plistNULL;// plist是头指针指向头结点// 测试单链表的初始化ListInit(plist);// 分别插入数据域的值为1、2、3的结点 即头结点-1-2-3for(inti1;i3;i){ListInsert(plist,i,i);}// 删除第2个存储有效数据的结点ElemType m;ListDelete(plist,2,m);printf(删除的结点中存储的数据是%d\n,m);// 求单链表的长度(即有效结点的个数)printf(单链表的长度为:%d,Length(plist));}intmain(){Test();return0;}