数据结构核心算法大全

1线性表单链表逆置//已知单链表H，写一个算法将其逆置//H-head-32-63-18-50-26-NULL#includestdio.h#includestdlib.htypedefstructnode{chardata;//data为结点数据信息structnode*next;//next为指向后继结点的指针}LNode;//单链表数据类型LNode*CreateLinkList()//生成单链表{LNode*head,*p,*q;charx;head=(LNode*)malloc(sizeof(LNode));//生成头结点head-next=NULL;p=head;q=p;//q始终指向链尾结点printf(Inputanycharstring:\n);scanf(%c,&x);while(x!='\n'){p=(LNode*)malloc(sizeof(LNode));p-data=x;p-next=NULL;q-next=p;//在链尾插入q=p;scanf(%c,&x);}returnhead;//返回指向单链表的头指针head}voidConvert(LNode*H)//单链表的逆置{LNode*p,*q;p=H-next;//p指向剩余结点链表的第一个数据结点H-next=NULL;//新链表H初始为空while(p!=NULL){q=p;//从剩余结点链表中取出第一个结点p=p-next;//p继续指向剩余结点链表新的第一个数据结点2q-next=H-next;//将取出的结点*q插入到新链表H的链首H-next=q;}}voidmain(){LNode*A,*p;A=CreateLinkList();//生成单链表AConvert(A);//单链表逆置p=A-next;//输出逆置后的单链表while(p!=NULL){printf(%c,p-data);p=p-next;}printf(\n);}双链表合并//对两个元素递增有序的单链表A和B，编写算法将A、B合并成一个按元素递减有序的单链表C，要求算法使用A\B中原有的结点，不允许增加新结点#includestdio.h#includestdlib.htypedefstructnode{intdata;//data为结点的数据信息structnode*next;//next为指向后继结点的指针}LNode;LNode*CreateLinkList()//生成单链表{LNode*head,*p,*q;inti,n;head=(LNode*)malloc(sizeof(LNode));//生成头结点head-next=NULL;p=head;q=p;//指针q始终指向链尾结点printf(Inputlengthoflist:\n);scanf(%d,&n);//读入节点数据printf(Inputdataoflist:\n);for(i=1;i=n;i++)//生成链表的数据结点{p=(LNode*)malloc(sizeof(LNode));//申请一个节点空间scanf(%d,&p-data);p-next=NULL;q-next=p;//在链尾插3入q=p;}returnhead;//返回单链表的头指针head}voidMerge(LNode*A,LNode*B,LNode**C)//将升序链表A\B合并成降序链表C{LNode*p,*q,*s;p=A-next;//p始终指向链表A的第一个未比较的数据结点q=B-next;//q时钟指向链表B的第一个未比较的数据节点*C=A;//生成的链表的*C的头结点(*C)-next=NULL;free(B);//回收链表B的头结点空间while(p!=NULL&&q!=NULL)//将A、B两链表中当前比较节点中值小者赋给*S{if(p-dataq-data){s=p;p=p-next;}else{s=q;q=q-next;}s-next=(*C)-next;//用头插法将结点*S插到链表*C的头结点之后(*C)-next=s;}if(p==NULL)//如果指向链表A的指针*P为空，则使*P指向链表Bp=q;while(p!=NULL)//将*P所指链表中剩余结点依次摘下插入的链表C的链首{s=p;p=p-next;s-next=(*C)-next;(*C)-next=s;}}voidprint(LNode*p)//输出单链表{p=p-next;while(p!=NULL){4printf(%4d,p-data);p=p-next;}printf(\n);}voidmain(){LNode*A,*B,*C;printf(Inputdataoflist:\n);A=CreateLinkList();//生成单链表Aprintf(OutputlistA:\n);print(A);//输出单链表Aprintf(InputdataofB:\n);B=CreateLinkList();printf(OutputlistofB:\n);print(B);printf(MakelistC:\n);Merge(A,B,&C);//将升序链表A、B合并成降序链表Cprintf(OutputlistofC:\n);print(C);}静态链表#includestdio.h#includestdlib.h#defineMAXSIZE30typedefstruct{chardata;//data为结点数据信息intcursor;//cursor标示直接后继结点}SNode;voidInsertList(SNodeL[],inti,charx)//在静态链表中插入元素{intj,j1,j2,k;j=L[0].cursor;//j指向第一个数据结点if(i==1)//作为第一个数据结点插入{if(j==0)//静态链表为空{L[1].data=x;//将x放入结点L[1]中L[0].cursor=1;//头指针cursor指向这个新插入的结点L[1].cursor=0;//置链尾标示}else5{k=j+1;while(k!=j)//在数组中循环查找存放x的位置if(L[k].cursor==-1)//找到空位置break;elsek=(k+1)%MAXSIZE;//否则查找下一个位置if(k!=j)//在数组中查找一个空位子来存放x{L[k].data=x;L[k].cursor=L[0].cursor;//将其插入到静态链表表头L[0].cursor=k;}elseprintf(Listoverflow!\n);//链表已满无法插入}}else//不是作为第一个结点插入时{k=0;while(ki-2&&j!=0)//查找第i-1个结点，j不等于0则表示未到链尾{k++;j=L[j].cursor;}if(j==0)//查完整个静态链表未找到第i-1个结点，即链表长度小于i-1个结点printf(Inserterror\n);else{j1=j;//找到第i-1个结点j2=L[j].cursor;//用j2保存原L[j].cursor值，此值为第i个结点的位置值k=j+1;while(k!=j)//在数组中循环查找存放x的位置if(L[k].cursor==-1)//找到空位置break;elsek=(k+1)%MAXSIZE;//否则查找下一个位置if(k!=j)//在数组中找到一个空位置来存放x{L[k].data=x;L[j1].cursor=k;//作为第i个结点链入到静态链表L[k].cursor=j2;//新结点之后再连接上原第i个结点}else6printf(Listoverflow!\n);//链表已满，无法插入}}}voidprint(SNode*L)//输出静态链表{inti;i=L[0].cursor;//从静态链表的表头元素开始输出while(i!=0){printf(%c,L[i].data);i=L[i].cursor;}printf(\n);}voidmain(){SNodeL[MAXSIZE];inti;charx;for(i=1;iMAXSIZE;i++)//静态链表初始化L[i].cursor=-1;L[0].cursor=0;//静态链表初始为空标志i=1;printf(Inputelementoflist\n);//建立静态链表scanf(%c,&x);while(x!='\n');{InsertList(L,i,x);i++;scanf(%c,&x);}printf(Inputsiteandelementofinsert\n);scanf(%d.%c,&i,&x);//输入要插入的元素的位置InsertList(L,i,x);//在静态链表中插入元素printf(Outputlist:\n);print(L);//输出静态链表}链表的基本运算#includestdio.h#includestdlib.htypedefstructnode7{chardata;//data为结点数据信息structnode*next;//next为指向后继结点的指针}LNode;//单链表结点类型LNode*CreateLinkList()//在表尾生成单链表{LNode*head,*p,*q;charx;head=(LNode*)malloc(sizeof(LNode));//生成头结点head-next=NULL;p=head;q=p;//指针q始终指向尾结点printf(Inputanycharstring:\n);scanf(%c,&x);//读入结点数据while(x!='\n')//生成链表的其他结点{p=(LNode*)malloc(sizeof(LNode));//生成待插入结点的存储空间p-data=x;//将读入的数据赋给待插入结点*pp-next=NULL;//待插入结点*p作为连尾结点时其后继结点为空q-next=p;//在链尾插入*p结点q=p;//q继续指向新的链尾节点*pscanf(%c,&x);}returnhead;//返回链表表头指针}intLength_LinkList(LNode*head)//求单链表的长度{LNode*p=head;//p指向单链表头结点inti=0;//i为结点计数器while(p-next!=NULL){p=p-next;i++;}returni;}LNode*Get_LinkList(LNode*head,inti){//在单链表head中按序号查找第i个结点LNode*p=head;intj=0;while(p!=NULL&&ji)//由第一个数据结点开始查找{p=p-next;j++;8}returnp;//找到则返回指向i结点的指针值，找不到则p已为空返回空值}LNode*Locate_LinkList(LNode*head,charx){//在单链表中查找结点值为x的元素LNode*p=head-next;while(p!=NULL&&p-data!=x)//由第一个数据结点开始查找p=p-next;returnp;}voidInsert_LinkList(LNode*head,inti,charx){//在单链表head的第i个位置上插入值为x的元素LNode*p,*s;p=Get_LinkList(head,i-1);//查找第i-1个结点if(p==NULL)printf(Error!\n);//第i-1个位置不存在而无法插入else{s=(LNode*)malloc(sizeof(LNode));//申请节点空间s-data=x;s-next=p-next;p-next=s;}}voidDel_LinkList(LNode*head,inti)//删除单链表h