linkseqlist.c

数据结构线性表源代码

/*线性表链接存储的基本算法， 此链表没有头节点，直接指向数据*/
#include <stdio.h>
/* #include <malloc.h> */

typedef int ElemType;

/*定义单链表节点类型*/
struct Node
{
	ElemType data;
	struct Node *next;
};

/*初始化一个单向链表， 即 置单链表的表头指针为空*/
void InitList( struct Node **hl)
{
	*hl = NULL;
	return;
	
}

/*向单链表的表头插入一个元素*/
void InsertFirstList(struct Node **hl, ElemType x)
{
	/*开辟一个新节点，用来保存插入的元素*/
	struct Node *newpNode;
	newpNode = malloc( sizeof(struct Node) );
	if( newpNode == NULL)
	{
		printf("内存分配失败，退出程序\n");
		exit(1);
	}

	/*给新节点赋值*/
	newpNode->data = x;

	/*切记： 此链表是没有头节点的链表*/
	newpNode->next = *hl;/*新节点指向的下一个节点的位置与原来头节点指向的位置相同*/
	*hl = newpNode;
	return ;
}

/*向单链表表尾插入一个新节点*/
void InsertLastList(struct Node **hl, ElemType e)
{
	struct Node *newP;
	struct Node *temp;
	/*给 e 分配一个新节点*/
	newP = (struct Node*)malloc(sizeof(struct Node));
	if( newP == NULL )
	{
		printf("InsertLastList Error: malloc fun failed\n");
		exit(1);
	}

	/*给新节点赋值*/
	newP->data = e;
	/*因为要加入的是最后一个节点，所以next 为空*/
	newP->next = NULL;

	temp = *hl;
	
	/*如果单向链表不是空表，*/
	if(hl != NULL)
	{
		/* 则遍历到最后一个节点 */
		while(temp->next != NULL)
		{
			temp = temp->next;
		}
		
	}
	temp->next = newP;

}

/*向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０*/
int InsertPosList(struct Node **hl, int pos, ElemType e)
{
	struct Node *p, *newp;
	int count = 1;

	newp = malloc( sizeof(struct Node));
	if(newp == NULL)
	{
		printf("InsertPosList Error: malloc fun error\n");
		exit(1);
	}

	/*给新节点添加数据*/
	newp->data = e;


	/*判断链表是否为空*/

	p = *hl;
	if( p== NULL)
	{
		p->next = newp;
		newp->next = NULL;
	}
	
	while( p != NULL && count < pos-1)
	{
		count++;
		p = p->next;

	}

	/*如果pos 位置过大*/
	if(!p)
	return -1;

	/*退出循环的时候，p 指向pos 的前一个节点。比如pos 为3， p指向第2个节点*/
	newp->next = p->next;
	p->next = newp;

}

/*对单向链表进行排序*/
int OrderLinkList( struct Node **hl)
{
	/*采用直接插入排序*/
	struct Node *pPailast, *pPaihead, *pDaipaihead;
	struct Node *pPaipre;
	struct Node *pShaobing;
	struct Node *ptemp;

	int found = 0;

	if(*hl == NULL)
	{
		printf("待排链表为空\n");
		return -1;
	}
	
	/*如果待排链表只有一个元素，则直接返回*/
	if( (*hl)->next == NULL)
	{
		return 0;
	}

	/*对指针进行初始化*/
	pDaipaihead = pPailast = *hl;
	pPaihead = *hl;

	/*记录待排记录的第一个元素，即链表的第二个链表值*/
	pDaipaihead = pDaipaihead->next;
	/*一开始第一个元素为已经排好序的表，所以后面NEXT 要为空*/
	pPaihead->next = NULL;

	

	
		/*这里不是顺序存储，可以从后向前操作，这里是链表*/
		/*直接在前面的排序好的链表中，比较数值，直接插入排序好的链表中即可*/

		/*指向待查入记录的前一个记录*/
		
		while( pDaipaihead != NULL)
		{
			pShaobing = pDaipaihead;
			ptemp = pDaipaihead->next;

		
			pPailast = pPaihead;
			/*如果前面排序好的链表不为空*/

			/*如果第一个元素大，那么直接查入表头*/
			if(pShaobing->data < pPailast->data)
			{
				pShaobing->next = pPaihead;
				pPaihead = pShaobing;
			}
			else
			{
				/*查找要插入的位置*/

				/*如果排序的表只有一个元素，直接插入表尾*/
				if(pPailast->next == NULL)
				{
					pShaobing->next = NULL;
					pPailast->next =pShaobing;

				}
				else
				{
					pPaipre = NULL;
					found = 0;

					while( pPailast != NULL && found == 0 )
					{
						if(pPailast->data < pShaobing->data)
						{
							pPaipre = pPailast;
							found == 0;

						}
						else
						{
							found = 1;
						}
						
						
						pPailast = pPailast->next;

					}
					/*找到插入的位置，进行插入*/
					pShaobing->next = pPaipre->next;
					pPaipre->next = pShaobing;
				}
		
			}
			/*对待排链表的下一个元素进行比较插入*/
				pDaipaihead = ptemp;
		}

		/*对最初的指针赋值*/
		*hl = pPaihead;
  	return 0;

}

/*在有序链表中插入一个元素，使插入后的有序链表仍然有序*/
void InsertOrderList( struct Node **hl, ElemType e )
{
	struct Node *php,*pre, *newp;
	int i;
	php = *hl;
	/*创建一个新的节点*/
	newp = malloc(sizeof(struct Node));
	if( NULL == newp)
	{
		printf("InsertOrderList Error:内存分配失败");
		exit(1);
	}

	newp->data = e;
	newp->next = NULL;

	/*如果链表为空 或者第一个节点最大， 那么插入到表头*/
	if(*hl == NULL || (*hl)->data > e)
	{
		newp->next = *hl;
		*hl = newp;
		return;
	}
	
	while(php != NULL)
	{
		if(php->data > e)
		{
			break;
		}
		/*记录小于e 的最后一个记录*/
		pre = php;

		php = php->next;
		
	}
	/*插入记录*/
	newp->next = pre->next;
	pre->next = newp;
	
}


/*遍历输出整个链表*/
void PrintList(struct Node **hl)
{
	int i;
	struct Node *temp;
	ElemType e;
	temp = *hl;
	while(temp != NULL)
	{
		e = temp->data;
		printf("%d\n", e);
		temp = temp->next;

	}

	/********
	   //如果这样做，hl 的指针将要改变，不再指向头节点

          while(hl!=NULL){
  　　　　 printf("%5d",hl->data);
  　　　　 hl=hl->next;
  　　 }
   *********/
}

/*从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/
ElemType DeleteFirstList(struct Node **hl)
{
	struct Node *p_temp;
	ElemType e;
	if( NULL == *hl)
	{
		printf("链表为空\n");
		return -1;
	}

	p_temp = *hl;
	e = p_temp->data;
	*hl = (*hl)->next;

	/*释放节点*/
	free(p_temp);
	p_temp = NULL;

	return e;

}
/*从单链表中删除表尾结点，并把该结点的值返回，若删除失败则停止程序运行*/
ElemType DeleteLastList( struct Node **hl)
{
	struct Node *p, *pre;
	ElemType e;

	p = *hl;

	if(p == NULL)
	{
		printf("The list is empty!\n");
		return -1;
	}
	if(p->next == NULL)
	{
		e = p->data;
		free(p);
		p = NULL;
		free(*hl);
		hl = NULL;
		return e;
	}
	while(p ->next != NULL)
	{
		pre = p;
		p = p->next;
	}
	pre->next = NULL;
	e = p->data;
	free(p);
	p = NULL;

}

/*从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/
ElemType DeletePosList( struct Node **hl, int pos)
{
	int i = 0;
	struct Node *p, *pre;
	ElemType e;
	p = *hl;
	pre = NULL;

	if( pos < 1)
	{
		printf("pos is not a right data.\n");
		return -1;
	}

	/*如果是删除表头的值*/
	if( pos == 1)
	{
		e = p->data;
		*hl = NULL;

		/*释放节点空间*/
		free(p);
		p= NULL;
		return e;
	}

	/*遍历链表*/
	while(p != NULL )
	{
		i++;
		/*发现要删除的元素*/
		if( i == pos)
		{
			e = p->data;
			/*被删除的前一个元素直接指向 被删除的下一个元素*/
			pre->next = p->next;

			free(p);
			p = NULL;
			return e;
		}
		pre = p;
		p = p->next;
	}
	/*如果一直都没有发现pos 值*/
	if(p == NULL)
	{
		printf("没有发现pos 值，请确认删除的位置是否正确\n");
		return -1;
	}
}

/*从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0*/
int DeleteValueList( struct Node **hl, ElemType e)
{
	struct Node *p, *p_pre;
	p = *hl;
	p_pre = NULL;

	/*如果元素与链表中的第一个节点相同*/
	if( (*hl)->data == e)
	{
		/*删除头节点*/
		*hl = (*hl)->next;
		free(p);
		p = NULL;
		return 1;
	}

	while( p != NULL)
	{
		if(p->data == e)
		{
			/*删除p节点*/
			p_pre->next = p->next;
			free(p);
			p = NULL;
			return 1;
			
		}
		p_pre = p;
		p = p->next;
		
	}
	if(p == NULL)
	{
		printf("Not found e, please try another data\n");
		return 0;
	}
}

/*把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０*/
int ChangePosList( struct Node **hl, int pos, ElemType x)
{
	int num ;
	struct Node *p;
	num = 0;
	p = *hl;

	/*链表为空， 或者pos 为非法数据*/
	if(pos < 1 || *hl == NULL)
	{
		printf("Error: pos < 1 or hl is empty\n");
		return 0;
	}

	while( p != NULL)
	{
		num++;
		/*找到pos位置*/
		if(num == pos)
		{
			p->data = x;
			return 1;
		}
		p=p->next;
	}
	/*如果没有找到pos的位置*/
	if( p == NULL)
	{
		printf("The pos is error, please try another pos\n");
		return 0;

	}

}

/*返回单链表的长度*/
int LengthList1( struct Node **hl)
{
	struct Node *p;
	int len;
	len = 0;
	p = *hl;

	while( p != NULL)
	{
		len++;
		p = p->next;
	}
	return len;
}

/*返回单链表的长度*/
int sizeList2(struct Node *hl)
{
	int count=0;
	while(hl!=NULL)
	{
		count++;
		hl = hl->next;
	}
	return count;
}



/*清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/
int ClearList(struct Node **hl)
{
	struct Node *p,*q;
	p = *hl;

	while( p!= NULL )
	{
		q = p->next;

		/*释放当前节点*/
		free(p);

		/*指向下一个节点*/
		p = q;
	}
	/*当链表赋值为空*/
	*hl = NULL;
}

void main()
{
	int i,j,k;
	/*首先声明一个单向链表*/
	struct Node *pHead;
	int afirst[10]={11,13,21,9,7,36,55,8,80,25};
	int blast[5] = {101, 125, 155, 111, 102};


	/*初始化 一个单向链表*/
	InitList(&pHead);

	/*向表头插入10个元素*/
	for(i=0; i<10; i++)
	{
		InsertFirstList(&pHead, afirst[i]);
		
	}
	/*输出整个单向链表*/
	printf("向表头插入10个元素,输出整个单向链表\n");
	PrintList(&pHead);

	/*向表尾插入5个元素*/
	for(i=0; i<5; i++)
	{
		InsertLastList(&pHead, blast[i]);
		
	}
	/*输出整个单向链表*/
	printf("向表尾插入5个元素,输出整个单向链表\n");
	PrintList(&pHead);

	/*向单向链表的第 11 位置加入一个元素 2100*/
	InsertPosList(&pHead, 11, 2100);
	/*输出整个单向链表*/
	printf("向单向链表的第 11 位置加入一个元素 2100,输出整个单向链表\n");
	PrintList(&pHead);

	/*对链表进行从小到大排列*/
	OrderLinkList(&pHead);
	printf("排序后输出\n");
	PrintList(&pHead);

	/*在有序链表中插入一个元素，使插入后的有序链表仍然有序*/
	printf("在有序链表中插入99\n");
	InsertOrderList(&pHead, 99);
	PrintList(&pHead);

	/*删除表头元素*/
	printf("删除表头元素后输出表\n");
	DeleteFirstList(&pHead);
	PrintList(&pHead);

	/*删除表尾元素*/
	printf("删除表尾元素后输出表\n");
	DeleteLastList(&pHead);
	PrintList(&pHead);

	/*删除指定位置的元素*/
	
	printf("删除制定元素，第2个元素后输出表\n");
	DeletePosList(&pHead, 2);
	PrintList(&pHead);
	
	/*删除与给定值相同的元素*/
	printf("删除与给定值相同的元素后输出表\n");
	DeleteValueList(&pHead,99);
	PrintList(&pHead);
    
	/*改变与给定位置相同的元素，输入新值*/
	printf("改变与给定位置相同的元素，输入新值，改变第5个元素，使之变为8888后输出表\n");
	ChangePosList(&pHead,5, 8888);
	PrintList(&pHead);
}