6-2有序表的插入【有题解视频】分数10全屏浏览题目切换布局作者CUIT通信DS课程组单位成都信息工程大学设顺序表中的数据元素是按值非递减有序排列的，试编写一算法，将x插入到顺序表的适当位置上，以保持顺序表的有序性。函数接口定义：voidListInsertSort;其中L和x都是用户传入的参数。L表示顺序表，x是要插入的元素。裁判测试程序样例：#include"stdio.h"#defineLISTSIZE100typedefintDataType;typedefstruct{DataTypeitems[LISTSIZE];intlength;}SqList;/*本题要求函数*/voidListInsertSort;intInitList{/*L为指向顺序表的指针*/L->length=0;return1;}intListLength{/*L为顺序表*/returnL.length;}intListInsert{/*L为指向顺序表的指针,pos为插入位置,item为待插入的数据元素*/inti;if{printf;return0;}if{printf;return0;}for/*移动数据元素*/L->items[i+1]=L->items[i];L->items[pos-1]=item;/*插入*/L->length++;/*表长增一*/return1;}intTraverseList{/*L为顺序表*/inti;forprintf;printf;return1;}voidmain{inti,input,x;SqListL1;//定义顺序表InitList;//初始化建空表for{scanf;ifbreak;ListInsert;//插入数据}scanf;ListInsertSort;//本题要求函数在主函数中的调用TraverseList;//遍历}/*请在这里填写答案*/输入样例：在这里给出一组输入。例如：136789-13输出样例：在这里给出相应的输出。例如：1336789代码长度限制16KB时间限制400ms内存限制64MB代码voidListInsertSort{intinsertPoint=-1;while;//寻找插入位置ListInsert;//调用题目给的函数进行插入}
6-1线性表元素的区间删除分数20全屏浏览题目切换布局作者DS课程组单位浙江大学给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。函数接口定义：ListDelete;其中List结构定义如下：typedefintPosition;typedefstructLNode*List;structLNode{ElementTypeData[MAXSIZE];PositionLast;/*保存线性表中最后一个元素在数组中的位置*/};L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较；minD和maxD分别为待删除元素的值域的下、上界。函数Delete应将Data[]中所有值大于minD而且小于maxD的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表。裁判测试程序样例：#include#defineMAXSIZE20typedefintElementType;typedefintPosition;typedefstructLNode*List;structLNode{ElementTypeData[MAXSIZE];PositionLast;/*保存线性表中最后一个元素的位置*/};ListReadInput;/*裁判实现，细节不表。元素从下标0开始存储*/voidPrintList;/*裁判实现，细节不表*/ListDelete;intmain{ListL;ElementTypeminD,maxD;inti;L=ReadInput;scanf;L=Delete;PrintList;return0;}/*你的代码将被嵌在这里*/输入样例：104-8212159331004输出样例：4-8125910代码长度限制16KB时间限制200ms内存限制64MB代码ListDelete{intendNum=0;intlength=L->Last+1;int*remain=malloc*length);intj=0;for{if{//保留需要删除的区间之外的值endNum++;remain[j++]=L->Data[i];}}Listlist=malloc);memset);for{//用保留的值重新创建一个链表list->Data[i]=remain[i];}list->Last=endNum-1;returnlist;}
6-6删除单链表偶数节点
6-3合并两个有序数组分数20全屏浏览题目切换布局作者李廷元单位中国民用航空飞行学院要求实现一个函数merge，将长度为m的升序数组a和长度为n的升序数组b合并到一个新的数组c，合并后的数组仍然按升序排列。函数接口定义：voidprintArray;/*打印数组,细节不表*/voidmerge;/*合并a和b为c*/其中a和b是按升序排列的数组，m和n分别为数组a、b的长度；c为合并后的升序数组。裁判测试程序样例：#include#includevoidprintArray;/*打印数组,细节不表*/voidmerge;/*合并a和b为c*/intmain{intm,n,i;int*a,*b,*c;scanf;a=malloc);for{scanf;}scanf;b=malloc);for{scanf;}c=malloc*sizeof);merge;printArray;return0;}/*请在这里填写答案*/输入样例：输入包含两行。第一行为有序数组a，其中第一个数为数组a的长度m，紧接着m个整数。第二行为有序数组b，其中第一个数为数组b的长度n，紧接着n个整数。71214253373841156172768687479808587输出样例：输出为合并后按升序排列的数组。12561417252733686873747980848587代码长度限制16KB时间限制400ms内存限制64MB代码voidmerge{intj=0,k=0;for{if//以有序放完a为前提，尽量放符合条件的ba[i]6-7逆序数据建立链表分数20全屏浏览题目切换布局作者C课程组单位浙江大学本题要求实现一个函数，按输入数据的逆序建立一个链表。函数接口定义：structListNode*createlist;函数createlist利用scanf从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。链表节点结构定义如下：structListNode{intdata;structListNode*next;};裁判测试程序样例：#include#includestructListNode{intdata;structListNode*next;};structListNode*createlist;intmain{structListNode*p,*head=NULL;head=createlist;forprintf;printf;return0;}/*你的代码将被嵌在这里*/输入样例：1234567-1输出样例：7654321代码长度限制16KB时间限制400ms内存限制64MB代码//头插，其他的和上一题的创建道理一样structListNode*createlist{intn;structListNode*head=NULL;scanf;if{head=malloc);head->data=n;head->next=NULL;while,n!=-{structListNode*p=malloc);;p->data=n;p->next=head;//头插head=p;//更新头}}returnhead;}
6-7逆序数据建立链表
7-1一元多项式的乘法与加法运算
6-5递增的整数序列链表的插入分数15全屏浏览题目切换布局作者DS课程组单位浙江大学本题要求实现一个函数，在递增的整数序列链表中插入一个新整数，并保持该序列的有序性。函数接口定义：ListInsert;其中List结构定义如下：typedefstructNode*PtrToNode;structNode{ElementTypeData;/*存储结点数据*/PtrToNodeNext;/*指向下一个结点的指针*/};typedefPtrToNodeList;/*定义单链表类型*/L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。裁判测试程序样例：#include#includetypedefintElementType;typedefstructNode*PtrToNode;structNode{ElementTypeData;PtrToNodeNext;};typedefPtrToNodeList;ListRead;/*细节在此不表*/voidPrint;/*细节在此不表*/ListInsert;intmain{ListL;ElementTypeX;L=Read;scanf;L=Insert;Print;return0;}/*你的代码将被嵌在这里*/输入样例：5124563输出样例：123456代码长度限制16KB时间限制400ms内存限制64MB代码ListInsert{PtrToNodep=L;while){//寻找插入位置p=p->Next;}PtrToNodex=malloc);//插入x->Data=X;x->Next=p->Next;p->Next=x;returnL;}
6-4顺序表操作集分数20全屏浏览题目切换布局作者陈越单位浙江大学本题要求实现顺序表的操作集。函数接口定义：ListMakeEmpty;PositionFind;boolInsert;boolDelete;其中List结构定义如下：typedefintPosition;typedefstructLNode*List;structLNode{ElementTypeData[MAXSIZE];PositionLast;/*保存线性表中最后一个元素的位置*/};各个操作函数的定义为：ListMakeEmpty：创建并返回一个空的线性表；PositionFind：返回线性表中X的位置。若找不到则返回ERROR；boolInsert：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGALPOSITION”并返回false；boolDelete：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITIONPEMPTY”并返回false。裁判测试程序样例：#include#include#defineMAXSIZE5#defineERROR-1typedefenum{false,true}bool;typedefintElementType;typedefintPosition;typedefstructLNode*List;structLNode{ElementTypeData[MAXSIZE];PositionLast;/*保存线性表中最后一个元素的位置*/};ListMakeEmpty;PositionFind;boolInsert;boolDelete;intmain{ListL;ElementTypeX;PositionP;intN;L=MakeEmpty;scanf;while{scanf;if==false)printf;}scanf;while{scanf;P=Find;ifprintf;elseprintf;}scanf;while{scanf;if==false)printf;if==false)printf;}return0;}/*你的代码将被嵌在这里*/输入样例：612345636512-16输出样例：FULLInsertionError:6isnotin.FindingError:6isnotin.5isatposition0.1isatpositionPOSITION-1EMPTYDeletionError.FULLInsertionError:0isnotin.POSITION6EMPTYDeletionError.FULLInsertionError:0isnotin.代码长度限制16KB时间限制400ms内存限制64MB代码ListMakeEmpty{//创建空表Listlist=malloc);memset);//初始化数据域list->Last=-1;//初始化尾指针returnlist;}PositionFind{intpos=-1;while{//遍历表if//找到数据returnpos;}returnERROR;}boolInsert{if{//表已满printf;returnfalse;}if{//越界printf;returnfalse;}for{//移动元素L->Data[i+1]=L->Data[i];}L->Data[P]=X;//插入L->Last++;//更新属性returntrue;}boolDelete{if{//越界printf;returnfalse;}for{//移动元素L->Data[i]=L->Data[i+1];}L->Last--;//更新属性returntrue;}
6-9两个有序链表序列的合并分数15全屏浏览题目切换布局作者DS课程组单位浙江大学本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。函数接口定义：ListMerge;其中List结构定义如下：typedefstructNode*PtrToNode;structNode{ElementTypeData;/*存储结点数据*/PtrToNodeNext;/*指向下一个结点的指针*/};typedefPtrToNodeList;/*定义单链表类型*/L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。裁判测试程序样例：#include#includetypedefintElementType;typedefstructNode*PtrToNode;structNode{ElementTypeData;PtrToNodeNext;};typedefPtrToNodeList;ListRead;/*细节在此不表*/voidPrint;/*细节在此不表；空链表将输出NULL*/ListMerge;intmain{ListL1,L2,L;L1=Read;L2=Read;L=Merge;Print;Print;Print;return0;}/*你的代码将被嵌在这里*/输入样例：31355246810输出样例：123456810NULLNULL代码长度限制16KB时间限制400ms内存限制64MB代码ListMerge{Listans=malloc));Listbody1=L1->Next,body2=L2->Next;Listhead=ans;//任意一个链表的数据判断完就停while{if{ans->Next=body1;body1=body1->Next;}else{ans->Next=body2;body2=body2->Next;}ans=ans->Next;}//剩下没判断的数据必然相对于新链表尾有序，直接接上即可body1?:;//题目要求，合并后原链表头将失去访问权限L1->Next=NULL;L2->Next=NULL;returnhead;}
6-5递增的整数序列链表的插入
6-8求链表的倒数第m个元素分数20全屏浏览题目切换布局作者DS课程组单位浙江大学请设计时间和空间上都尽可能高效的算法，在不改变链表的前提下，求链式存储的线性表的倒数第m个元素。函数接口定义：ElementTypeFind;其中List结构定义如下：typedefstructNode*PtrToNode;structNode{ElementTypeData;/*存储结点数据*/PtrToNodeNext;/*指向下一个结点的指针*/};typedefPtrToNodeList;/*定义单链表类型*/L是给定的带头结点的单链表；函数Find要将L的倒数第m个元素返回，并不改变原链表。如果这样的元素不存在，则返回一个错误标志ERROR。裁判测试程序样例：#include#include#defineERROR-1typedefintElementType;typedefstructNode*PtrToNode;structNode{ElementTypeData;PtrToNodeNext;};typedefPtrToNodeList;ListRead;/*细节在此不表*/voidPrint;/*细节在此不表*/ElementTypeFind;intmain{ListL;intm;L=Read;scanf;printf);Print;return0;}/*你的代码将被嵌在这里*/输入样例：5124563输出样例：412456代码长度限制16KB时间限制400ms内存限制64MB代码/**思路：*使用两个指针依次开始遍历链表，让两个指针产生长为m的区间差*当第一个指针遍历到链表尾时，第二个指针恰好在倒数m处。：*若有链表：1->2->3->4->5->m=则：*p2↓p1↓*1->2->3->4->5->6*|----3----|**/ElementTypeFind{PtrToNodep=L;inti=0;while){if{//产生区间p=p->Next;}}if{//没有倒数第mreturnERROR;}returnp->Data;}
7-2符号配对
6-4顺序表操作集
6-6删除单链表偶数节点分数20全屏浏览题目切换布局作者C课程组单位浙江大学本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中偶数值的结点删除。链表结点定义如下：structListNode{intdata;structListNode*next;};函数接口定义：structListNode*createlist;structListNode*deleteeven;函数createlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。函数deleteeven将单链表head中偶数值的结点删除，返回结果链表的头指针。裁判测试程序样例：#include#includestructListNode{intdata;structListNode*next;};structListNode*createlist;structListNode*deleteeven;voidprintlist{structListNode*p=head;while{printf;p=p->next;}printf;}intmain{structListNode*head;head=createlist;head=deleteeven;printlist;return0;}/*你的代码将被嵌在这里*/输入样例：12234567-1输出样例：1357代码长度限制16KB时间限制400ms内存限制64MB代码structListNode*createlist{intn;structListNode*head=NULL;scanf;if{//题目要求//先独立创建一个节点，在使用while创建其他节点，防止多分配内存head=malloc);//创建头指针structListNode*body=head;body->data=n;body->next=NULL;while,n!=-{//继续读入//继续创建body->next=malloc);body=body->next;body->data=n;body->next=NULL;}}returnhead;}structListNode*deleteeven{while){//先删除从开头便存在并且连续出现的偶数节点structListNode*p=head;head=head->next;free;}//第一个while过后，链表开头便不是偶数节点，方便继续删除structListNode*body=head;while{//再删除剩余的偶数节点if){structListNode*p=body->next;body->next=body->next->next;free;}else{body=body->next;}}returnhead;}
6-3合并两个有序数组
6-8求链表的倒数第m个元素
6-9两个有序链表序列的合并
6-2有序表的插入
文章为作者独立观点，不代表股票交易接口观点
