实验二 不带头结点的单链表

前言

熟练掌握动态链表结构及有关算法的设计方法

头文件

#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;

/*头插法建立单链表*/

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;				/*返回建立的单链表*/
}

/*函数功能：尾插法建立单链表   */
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;					/*返回建立的单链表*/
}


/*函数功能：输出不带头结点的单链表      */

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");
}

/*释放不带头结点的单链表 */
void delList(linklist head)
{ linklist p=head;
  while (p)
  { head=p->next;
    free(p);
    p=head;
  }
}

1.删除不带头结点的单链表的第一个值为x的节点

#include"slnklist.h"
linklist delx(linklist head, datatype x)
{
	linklist p,pre;
	if (!head)
	{
		printf("链表为空！\n");
	}
	p = head;
	pre = NULL;
	while (p&&p->info != x)
	{
		pre = p;
		p = p->next;
	}
	if (!p)
	{
		printf("链表中没有%d这个值的节点！\n", x);
	}
	else {
		if (pre==NULL)
		{
			head = NULL;
			free(p);
		}
		else
		{
			pre->next = p->next;
			free(p);
		}
	}
	return head;
}
int main()
{
	datatype x;
	linklist head;
	head = creatbyqueue();
	print(head);
	printf("请输入要删除的值:");
	scanf("%d", &x);
	head = delx(head, x);
	print(head);
	delList(head);
	system("pause");
	return 0;
}

2.倒置单链表

#include"slnklist.h"
linklist reverse1(linklist head)
{
	//这里注意linklist就是node *
	/*法一，最容易想到的，也是最傻的，用两个for循环反复交换信息域的值，*/
	linklist p;
	p = head;
	int n = 0;
	int m;
	while (p) { p = p->next; n++; }//得出总结点个数
	m = n;
	p = head;//重新上链
	for (int i = 0; i < n - 1; i++)
	{
		for (int i = 0; i < m-1; i++)
		{
			datatype temp = p->info;
			p->info = p->next->info;
			p->next->info = temp;
			p = p->next;
		}
		m--;
		p = head;
	}
	return head;
}
void reverse2(linklist *head)
{
	/*之后想到的法2，通过改变head指向原来链表最后一个节点，然后只要更改每个节点的指针域即可*/
	linklist p, pre;
	p = *head;
	*head = NULL;//注意这里是为了将原来链表的指针域设为空指针
	while (p)
	{
		pre = p;
		p = p->next;
		pre->next = *head;
		*head = pre;
	}
}
int main()
{
	datatype x;
	linklist head;
	head = creatbystack();
	print(head);
	head = reverse1(head);
	printf("reverse1:\n");
	print(head);
	printf("reverse2:\n");
	reverse2(&head);
	print(head);
	delList(head);
	system("pause");
	return 0;
}

3.插入新节点后依旧保持原链表的有序性

#include"slnklist.h"
linklist insert(linklist head, datatype x)
{
	/*法一*/
	linklist q, p, pre;
	q = (linklist)malloc(sizeof(linklist));
	q->info = x;
	pre = NULL;
	p = head;
	while (p)
	{
		pre = p;
		p = p->next;
		if (p)
		{
			if (pre->info <= q->info)
			{
				if (q->info <= p->info)//插入的节点作为中间节点
				{
					q->next = p;
					pre->next = q;
					break;
				}
			}
			else//插入的节点作为头结点
			{
				q->next = pre;
				head = q;
				break;
			}

		}
		else//插入的节点作为尾节点
		{
			if(pre->info>=q->info)//只有一个节点，而插入的节点值小于它
			{
				q->next = pre;
				head = q;
				break;
			}
			pre->next = q;
			q->next = NULL;
		}
	}
	return head;
}
/*
法二
*/
linklist insert2(linklist head, datatype x)
{
	linklist pre, p, q;
	q = (linklist)malloc(sizeof(linklist));
	q->info = x;
	pre = NULL;
	p = head;
	while (p&&p->info < q->info)
	{
		pre = p;
		p = p->next;
	}
	if (pre == NULL)//插入的节点值做头结点
	{
		q->next = p;
		head = q;
	}
	else//插入的节点做中间节点或尾节点
	{
		pre->next = q;
		q->next = p;
	}
	return head;
}
int main()
{
	datatype x;
	linklist head;
	printf("输入一组升序排序的数:\n");
	head = creatbyqueue();
	print(head);
	printf("请输入要插入的值:\n");
	scanf("%d", &x);
	head = insert2(head, x);
	print(head);
	//delList(head);
	system("pause");
}

4.删除不带头节点中所有值为x的节点

#include"slnklist.h"
linklist delallx(linklist head, datatype x)
{
	//相对于删除第一个值为x的节点来说，加个while循环和p继续下滑即可
	linklist  pre, p;
	pre = NULL;
	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);
	system("pause");
}

后记

Afraid to miss will never meet such a person.