网站优化需要什么,寺庙网站开发文案,wordpress 评论模块,安徽网站建设公司排名不带头结点的单链表
链表倒置 假设线性表#xff08;a1,a2,a3,…an#xff09;采用不带头结点的单链表存储#xff0c; 请设计算法函数linklist reverse1(linklist head)和 void reverse2(linklist *head)将不带头结点的单链表head就地倒置#xff0c; 使表变成#xff…不带头结点的单链表
链表倒置 假设线性表a1,a2,a3,…an采用不带头结点的单链表存储 请设计算法函数linklist reverse1(linklist head)和 void reverse2(linklist *head)将不带头结点的单链表head就地倒置 使表变成an,an-1,…a3.a2,a1。并构造测试用例进行测试。 linklist reverse1(linklist head)
{linklist p;linklist new_list;new_list NULL;p NULL;while (head NULL || head-next NULL) {return head;}while (head ! NULL) {p head;head head-next;p-next new_list;// p结点插入到链表头部new_list p;// 更新new_list指针在链表头部}return new_list;
}
插入结点 假设不带头结点的单链表head是升序排列的设计算法函数linklist insert(linklist head,datatype x) 将值为x的结点插入到链表head中并保持链表有序性。 分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。 linklist insert(linklist head ,datatype x)
{linklist p head;if(p-info x) { //判断表头linklist dummy (linklist*)malloc(sizeof(linklist));dummy-info x;dummy-next head;return dummy;}while(p-next) {if (p-next-info x) {linklist dummy (linklist*)malloc(sizeof(linklist));dummy-info x;dummy-next p-next;p-next dummy;return head;} else {p p-next;}}linklist dummy (linklist*)malloc(sizeof(linklist));dummy-info x;dummy-next NULL;p-next dummy;return head;
} 附录 #include stdio.h
#include stdlib.h
/**************************************/
/* 链表实现的头文件文件名slnklist.h */
/**************************************/typedef int datatype;typedef struct link_node{datatype info;struct link_node *next;}node;
typedef node *linklist;/**********************************/
/*函数名称creatbystack() */
/*函数功能头插法建立单链表 */
/**********************************/
linklist creatbystack()
{ linklist head,s;datatype x;headNULL;printf(请输入若干整数序列:\n);scanf(%d,x);while (x!0) /*以0结束输入*/{ s(linklist)malloc(sizeof(node)); /*生成待插入结点*/s-infox;s-nexthead; /*将新结点插入到链表最前面*/heads;scanf(%d,x);}return head; /*返回建立的单链表*/
}
/**********************************/
/*函数名称creatbyqueue() */
/*函数功能尾插法建立单链表 */
/**********************************/
linklist creatbyqueue()
{linklist head,r,s;datatype x;headrNULL;printf(请输入若干整数序列:\n);scanf(%d,x);while (x!0) /*以0结束输入*/{ s(linklist)malloc(sizeof(node));s-infox;if (headNULL) /*将新结点插入到链表最后面*/heads;elser-nexts;rs;scanf(%d,x);}if (r) r-nextNULL;return head; /*返回建立的单链表*/
}
/**********************************/
/*函数名称print() */
/*函数功能输出不带头结点的单链表 */
/**********************************/
void print(linklist head)
{ linklist p;int i0;phead;printf(List is:\n);while(p){printf(%5d,p-info);pp-next;i;if (i%100) printf(\n);}printf(\n);
}
/**********************************/
/*函数名称delList() */
/*函数功能释放不带头结点的单链表 */
/**********************************/
void delList(linklist head)
{ linklist phead;while (p){ headp-next;free(p);phead;}
}
带头结点的单链表
链表倒置 假设线性表a1,a2,a3,…an采用带头结点的单链表存储请设计算法函数void reverse(linklist head) 将带头结点的单链表head就地倒置使表变成an,an-1,…a3.a2,a1。并构造测试用例进行测试。 //例如h-1-2-3,h-1 2-3,h-2-1 3,h-3-2-1
void reverse(linklist head)
{//没有元素或者一个元素直接returnif (head-next NULL || head-next-next NULL) {return;}linklist pre,cur;cur head-next;pre NULL;//断开头结点head-next NULL;while(cur ! NULL) {//更新pre和cur指针pre cur;cur cur-next;//头插法插入节点pre-next head-next;head-next pre;}
}
插入结点 假设带头结点的单链表head是升序排列的设计算法函数linklist insert(linklist head,datatype x) 将值为x的结点插入到链表head中并保持链表有序性。 分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。 void insert(linklist head ,datatype x)
{linklist pre,cur,dummy;//创建插入的节点dummydummy (linklist*)malloc(sizeof(linklist));dummy-info x;pre head;cur head-next;//找到x插入的位置while (cur cur-info x) {pre cur;cur cur-next;}//插入dummy结点pre-next dummy;dummy-next cur;return head;
}
查找倒数第k个结点的地址 编写一个程序用尽可能快的方法返回带头结点单链表中倒数第k个结点的地址如果不存在则返回NULL。 linklist search(linklist head,int k)
{/*linklist p,x;p head-next;x p;int cnt 0;//计算链表的长度while (x) {cnt;x x-next;}//找不到结点if (k cnt) {return NULL;}//找到倒数第k个结点for (int i 0; i cnt - k; i) {p p-next;}return p;*/linklist fast head;linklist slow head;//flag用于记录k是否不在范围之内int flag 0;//快指针走k步for(int i 0; i k fast; i) {fast fast-next;}//慢指针快指针一起走while(fast) {fast fast-next;slow slow-next;flag 1;}return flag 1 ? slow : NULL;
}
多项式相加
#include stdlib.h
#include stdio.htypedef struct node
{ int coef; /*系数*/int expn; /*指数*/struct node *next;
}listnode; //多项式存储结构typedef listnode *linklist;
void delList(linklist head);/*函数名称 creat()函数功能建立多项式存储结构并且多项式在表中按所在项的指数递增存放*/
linklist creat() //建立多项式存储结构
{linklist head,s,p,pre,r;int coef;int expn;head(linklist)malloc(sizeof(listnode)); /*生成头结点*/head-nextNULL;printf(请输入多项式每一项只需输入系数指数(当输入的系数为0时结束输入)\n);scanf(%d,coef); //输入系数scanf(%d,expn); //输入指数p head;while (coef!0) //请在此处填上适当的代码{s (linklist)malloc(sizeof(listnode)); //插入新结点s-coef coef;s-expn expn;s-next NULL;head-next s; //head指针后移head s;scanf(%d,coef); //输入系数scanf(%d,expn); //输入指数//printf(while);}return p;
}void print(linklist head) //输出多项式{linklist p;phead-next;while (p){ printf(%d(X),p-coef);printf(%d ,p-expn);pp-next;}printf(\n);}/*函数名称 add()函数功能多项式相加入口参数a与b是存储多项式的带头结点单链表并且多项式在表中按所在项的指数递增存放*/
linklist add(linklist a,linklist b) //请将本函数补充完整
{linklist pa,pb,c,pc,r;pa a;pb b;c (linklist)malloc(sizeof(listnode));c-next NULL;pc c;while (pa pb) {if (pa-expn pb-expn) {r (linklist)malloc(sizeof(listnode));//两个多项式相加r-expn pa-expn;r-coef pa-coef pb-coef;r-next NULL;//插入进入c链表pc-next r;pc r;//双指针后移pa pa-next;pb pb-next;} else if (pa-expn pb-expn) {r (linklist)malloc(sizeof(listnode));//将a结点插入进cr-expn pa-expn;r-coef pa-coef;r-next NULL;pc-next r;pc r;//pa后移pa pa-next;} else {r (linklist)malloc(sizeof(listnode));//将b结点插入进cr-expn pb-expn;r-coef pb-coef;r-next NULL;pc-next r;pc r;//pb后移pb pb-next;}}pc-next pa ? pa : pb;return c-next;
}int main(){linklist a,b,c;acreat();printf(多项式a为);print(a);bcreat();printf(多项式b为);print(b);cadd(a,b);printf(两个多项式的和为\n);print(c);delList(c);return 0;}/***************************************/
/*函数名称delList() */
/*函数功能释放带头结点的单链表 */
/***************************************/
void delList(linklist head)
{ linklist phead;while (p){ headp-next;free(p);phead;}
}附录 #include stdio.h
#include stdlib.h
/****************************************/
/* 链表实现的头文件文件名slnklist.h */
/****************************************/typedef int datatype;typedef struct link_node{datatype info;struct link_node *next;}node;
typedef node *linklist;
/**********************************************/
/*函数名称creatbystack() */
/*函数功能头插法建立带头结点的单链表 */
/**********************************************/
linklist creatbystack()
{linklist head,s;datatype x;head(linklist)malloc(sizeof(node));head-nextNULL;printf(请输入整数序列空格分开以0结束:\n);scanf(%d,x);while (x!0){s(linklist)malloc(sizeof(node));s-infox;s-nexthead-next;head-nexts;scanf(%d,x);}return head;
}
/***************************************/
/*函数名称creatbyqueue() */
/*函数功能尾插法建立带头结点的单链表 */
/***************************************/
linklist creatbyqueue()
{linklist head,r,s;datatype x;headr(linklist)malloc(sizeof(node));head-nextNULL;printf(请输入整数序列空格分开以0结束:\n);scanf(%d,x);while (x!0){s(linklist)malloc(sizeof(node));s-infox;r-nexts;rs;scanf(%d,x);}r-nextNULL;return head;
}
/**********************************/
/*函数名称print() */
/*函数功能输出带头结点的单链表 */
/**********************************/
void print(linklist head)
{linklist p;int i0;phead-next;printf(List is:\n);while(p){printf(%7d,p-info);i;if (i%100) printf(\n);pp-next;}printf(\n);}/******************************************/
/*函数名称creatLink() */
/*函数功能从文件中读入n个数据构成单链表 */
/******************************************/
linklist creatLink(char *f, int n)
{FILE *fp;int i;linklist s,head,r;headr(linklist)malloc(sizeof(node));head-nextNULL;fpfopen(f,r);if (fpNULL)return head;else{for (i0;in;i){s(linklist)malloc(sizeof(node));fscanf(fp,%d,(s-info));r-nexts;rs;}r-nextNULL;fclose(fp);return head;}
}/*函数名称writetofile函数功能将链表内容存入文件f
*/
void writetofile(linklist head, char *f)
{FILE *fp;linklist p;int i0;fpfopen(f,w);if (fp!NULL){phead-next;fprintf(fp,%s,List is:\n);while(p){fprintf(fp,%7d,p-info);i;if (i%100) fprintf(fp,%c,\n);pp-next;}fprintf(fp,%c,\n);fclose(fp);}else printf(创建文件失败!);}/**********************************/
/*函数名称delList() */
/*函数功能释放带头结点的单链表 */
/**********************************/
void delList(linklist head)
{ linklist phead;while (p){ headp-next;free(p);phead;}
}
