数据结构（C语言）实验

数据结构（C语言）实验"/>

数据结构（C语言）实验

不带头结点的单链表

链表倒置

假设线性表（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;head=NULL;printf("请输入若干整数序列:\n");scanf("%d",&x);while (x!=0)		/*以0结束输入*/{   s=(linklist)malloc(sizeof(node));  /*生成待插入结点*/s->info=x;s->next=head;			/*将新结点插入到链表最前面*/head=s;scanf("%d",&x);}return head;				/*返回建立的单链表*/
}
/**********************************/
/*函数名称：creatbyqueue() 			 */
/*函数功能：尾插法建立单链表            */
/**********************************/
linklist creatbyqueue()
{linklist head,r,s;datatype x;head=r=NULL;printf("请输入若干整数序列:\n");scanf("%d",&x);while (x!=0) /*以0结束输入*/{    s=(linklist)malloc(sizeof(node));s->info=x;if (head==NULL)		/*将新结点插入到链表最后面*/head=s;elser->next=s;r=s;scanf("%d",&x);}if (r)  r->next=NULL;return head;					/*返回建立的单链表*/
}
/**********************************/
/*函数名称：print()		 			 */
/*函数功能：输出不带头结点的单链表      */
/**********************************/
void print(linklist head)
{   linklist p;int i=0;p=head;printf("List is:\n");while(p){printf("%5d",p->info);p=p->next;i++;if (i%10==0) printf("\n");}printf("\n");
}
/**********************************/
/*函数名称：delList()		 		 */
/*函数功能：释放不带头结点的单链表      */
/**********************************/
void delList(linklist head)
{ linklist p=head;while (p){ head=p->next;free(p);p=head;}
}

带头结点的单链表

链表倒置

假设线性表（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.h>typedef 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->next=NULL;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;p=head->next;while (p){   printf("%d(X)",p->coef);printf("%d    ",p->expn);p=p->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;a=creat();printf("多项式a为：");print(a);b=creat();printf("多项式b为：");print(b);c=add(a,b);printf("两个多项式的和为：\n");print(c);delList(c);return 0;}/***************************************/
/*函数名称：delList()		 	                	 */
/*函数功能：释放带头结点的单链表      */
/***************************************/
void delList(linklist head)
{ linklist p=head;while (p){ head=p->next;free(p);p=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;head=(linklist)malloc(sizeof(node));head->next=NULL;printf("请输入整数序列（空格分开，以0结束）:\n");scanf("%d",&x);while (x!=0){s=(linklist)malloc(sizeof(node));s->info=x;s->next=head->next;head->next=s;scanf("%d",&x);}return head;
}
/***************************************/
/*函数名称：creatbyqueue() 			   */
/*函数功能：尾插法建立带头结点的单链表 */
/***************************************/
linklist creatbyqueue()
{linklist head,r,s;datatype x;head=r=(linklist)malloc(sizeof(node));head->next=NULL;printf("请输入整数序列（空格分开，以0结束）:\n");scanf("%d",&x);while (x!=0){s=(linklist)malloc(sizeof(node));s->info=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;return head;
}
/**********************************/
/*函数名称：print()		 			 */
/*函数功能：输出带头结点的单链表      */
/**********************************/
void print(linklist head)
{linklist p;int i=0;p=head->next;printf("List is:\n");while(p){printf("%7d",p->info);i++;if (i%10==0)    printf("\n");p=p->next;}printf("\n");}/******************************************/
/*函数名称：creatLink() 			      */
/*函数功能：从文件中读入n个数据构成单链表 */
/******************************************/
linklist creatLink(char *f, int n)
{FILE *fp;int i;linklist s,head,r;head=r=(linklist)malloc(sizeof(node));head->next=NULL;fp=fopen(f,"r");if (fp==NULL)return head;else{for (i=0;i<n;i++){s=(linklist)malloc(sizeof(node));fscanf(fp,"%d",&(s->info));r->next=s;r=s;}r->next=NULL;fclose(fp);return head;}
}/*函数名称：writetofile函数功能：将链表内容存入文件f
*/
void writetofile(linklist head, char *f)
{FILE *fp;linklist p;int i=0;fp=fopen(f,"w");if (fp!=NULL){p=head->next;fprintf(fp,"%s","List is:\n");while(p){fprintf(fp,"%7d",p->info);i++;if (i%10==0)    fprintf(fp,"%c",'\n');p=p->next;}fprintf(fp,"%c",'\n');fclose(fp);}else    printf("创建文件失败!");}/**********************************/
/*函数名称：delList()		 		 */
/*函数功能：释放带头结点的单链表      */
/**********************************/
void delList(linklist head)
{ linklist p=head;while (p){ head=p->next;free(p);p=head;}
}