数据结构-实验二（不带头节点的单链表）
#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;
else
r->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;
}
}
1.编写函数slnklist delx(linklist head, datatype x)，删除不带头结点单链表head中第一个值为x 的结点。并构造测试用例进行测试。
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist delx(linklist head,datatype x)
{
node *pre=NULL,*p;
if(head==NULL)
{
printf("单链表是空的！");
return head;
}else
{
p=head;
while(p&&p->info!=x)
{
pre=p;
p=p->next;
}
if(p!=NULL)
{
if(pre!=NULL)
{
pre->next=p->next;
}else
{
head=head->next;
}
free(p);
}
return head;
}
}
int main()
{ datatype x;
linklist head;
head=creatbyqueue();/*尾插入法建立单链表*/
print(head);
printf("请输入要删除的值：");
scanf("%d",&x);
head=delx(head,x);/*删除单链表的第一个值为x的结点*/
print(head);
delList(head);/*释放单链表空间*/
return 0;
}2.假设线性表（a1,a2,a3,…an）采用不带头结点的单链表存储，请设计算法函数linklist reverse1(linklist head)和void reverse2(linklist *head)将不带头结点的单链表head就地倒置，
使表变成（an,an-1,…a3.a2,a1）。并构造测试用例进行测试。
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist reverse1(linklist head)
{
node *p,*s;
p=head;
head=NULL;
while(p)
{
s=p;
p=p->next;
s->next=head;
head=s;
}
return head;
}
void reverse2(linklist *head)
{
linklist p,s;
p=*head;
*head=NULL;
while(p)
{
s=p;
p=p->next;
s->next=*head;
*head=s;
}
}
int main()
{ datatype x;
linklist head;
head=creatbystack();/*头插入法建立单链表*/
print(head);/*输出原链表*/
head= reverse1(head);/*倒置单链表*/
print(head);/*输出倒置后的链表*/
reverse2(&head);/*倒置单链表*/
print(head);
delList(head);
return 0;
}3.假设不带头结点的单链表head是升序排列的，设计算法函数linklist insert(linklist head,datatype x)，将值为x的结点插入到链表head中，并保持链表有序性。分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist insert(linklist head ,datatype x)
{
linklist s,p,pre;
p=head;
while(p&&p->info<x)
{
pre=p;
p=p->next;
}
s=(linklist)malloc(sizeof(node));
s->info=x;
if(pre==NULL)
{
s->next=head;
head=s;
}else
{
s->next=pre->next;
pre->next=s;
}
return head;
}
int main()
{ datatype x;
linklist head;
printf("输入一组升序排列的整数：\n");
head=creatbyqueue();/*尾插入法建立单链表*/
print(head);
printf("请输入要插入的值：");
scanf("%d",&x);
head=insert(head,x);/*将输入的值插入到单链表适当位置*/
print(head);
delList(head);
return 0;
}4.编写算法函数linklist delallx(linklist head, int x)，删除不带头结点单链表head中所有值为x的结点。
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist delallx(linklist head,int x)
{
linklist p,s,pre;
p=head;
while(p)
{
while(p&&p->info!=x)
{
pre=p;
p=p->next;
}
if(p)
{
if(pre==NULL)
{
head=p->next;
free(p);
p=head;
}
else
{
pre->next=p->next;
free(p);
p=pre->next;
}
}
}
return head;
}
int main()
{ datatype x;
linklist head;
head=creatbyqueue();/*尾插入法建立单链表*/
print(head);
printf("请输入要删除的值：");
scanf("%d",&x);
head=delallx(head,x);
print(head);
delList(head);
return 0;
}
原文地址：https://blog.csdn.net/2301_80281749/article/details/143780368
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！