双向链表实现队列的入队、出队、查找元素

喜欢ヅ旅行 2022-08-08 17:54 180阅读 0赞

typedef int DItemType;
    typedef struct SDoubleList
    {
    	DItemType iValue;
    	SDoubleList *prev;
    	SDoubleList *next;
    
    } DLinkedList,*pDLinkedList;
    
    
    /* 创建双链表 */
    DLinkedList *InitDoubleList()
    {
    	DLinkedList *doublelist = (DLinkedList*)malloc(sizeof(DLinkedList));
    	if (NULL == doublelist)
    		exit(1);
    	doublelist->prev = NULL;
    	doublelist->next = NULL;
    	return doublelist;
    }
    
    /* 双链表实现队列入队 */
    bool DLinkedList_Push(DLinkedList* DL, DItemType value)
    {
    	if (NULL==DL)
    	{
    		puts("队列不存在，无法插入！\n");
    		return false;
    	}
    	DLinkedList *temp = (DLinkedList *)malloc(sizeof(DLinkedList));
    	if (NULL == temp) {
    		puts("插入失败！");
    		return false;
    	}
    	temp->iValue = value;
    	temp->next = NULL;
    	temp->prev = NULL;
    
    	DLinkedList *ttemp = DL;
    	while (NULL != ttemp->next)
    	{
    		ttemp = ttemp->next;
    	}
    	ttemp->next = temp;
    	temp->prev = ttemp;
    
    	return true;
    }
    
    /* 双链表实现队列出队 */
    bool DLinkedList_Pop(DLinkedList *DL)
    {
    	if (NULL==DL || NULL==DL->next) {
    		puts("队列为空，无法出队！");
    		return false;
    	}
    
    	DLinkedList *temp = DL->next;
    	DL->next = temp->next;
    	if (NULL==temp->next) {
    		free(temp);
    		return true;
    	}
    	temp->next->prev = DL;
    	free(temp);
    
    	return true;
    }
    
    /* 遍历队列 */
    void VisitDLinkedList(DLinkedList *DL)
    {
    	if (NULL==DL || NULL == DL->next) {
    		puts("队列为空！");
    		return;
    	}
    	DLinkedList *temp = DL->next;
    	while (NULL !=temp)
    	{
    		printf("%d ", temp->iValue);
    		temp = temp->next;
    	}
    	printf("\n");
    }
    
    /* 查找某一元素 */
    bool findItem(DLinkedList *DL, DItemType value)
    {
    	if (NULL==DL || NULL==DL->next) {
    		puts("队列为空,查找失败！");
    		return false;
    	}
    	DLinkedList *temp = DL->next;
    	while (temp)
    	{
    		if (value==temp->iValue)
    			return true;
    		temp = temp->next;
    	}
    	return false;
    }
    
    void main()
    {
    	DLinkedList *DL;
    	DL = InitDoubleList();
    	DLinkedList_Push(DL, 10);
    	DLinkedList_Push(DL, 20);
    	DLinkedList_Push(DL, 30);
    
    	VisitDLinkedList(DL);
    	DLinkedList_Pop(DL);
    	DLinkedList_Pop(DL);
    	VisitDLinkedList(DL);
    	if (findItem(DL,30))
    		puts("查找成功！");
    	else puts("查找失败！");
    
    }