数据结构与算法——线性表—双向链表操作（含代码）

缺乏、安全感 2022-02-27 23:50 216阅读 0赞

注意：这里的头指针是不包含数据的

双向链表（double linked list）的结点中有两个指针域，一个指向“直接后继”，另一个指向“直接前驱”。  
typedef struct DLNode\{  
ElemType data;  
DLNode \*prior;  
DLNode \*next;  
\}DLNode,\*DuLinkList;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70]  
\#include “DList.h”

#pragma once
    #include <iostream>
    using namespace std;
    
    typedef int ElemType ;
    
    typedef struct DLNode
    {
    	ElemType data;
    	DLNode *prior;
    	DLNode *next;
    
    }DLNode;
    
    void destoryDList(DLNode* &pHead)
    {
    	if (pHead == NULL)
    	{
    		return;
    	}
    
    	DLNode *p = pHead;
    	while (p)
    	{
    		p = p->next;
    		free(pHead);
    		if (p != NULL)
    			p->prior = NULL;
    		pHead = p;
    	}
    }
    
    void initDList(DLNode* & pHead)//创建一个新头
    {
    	if (pHead != NULL)
    	{
    		destoryDList(pHead);
    	}
    
    	DLNode *p = (DLNode*)malloc(sizeof(DLNode));
    	p->prior = NULL;
    	p->data = 0;
    	p->next = NULL;
    
    	pHead = p;
    	
    }
    
    void creatDList(DLNode* & pHead,ElemType* a,int len)//创建双链表
    {
    	if (pHead == NULL)
    	{
    		return;//zanshi 
    	}
    
    	DLNode *p = pHead;
    	DLNode *q = NULL;
    
    	for (int i = 0; i < len; ++i)
    	{
    		//创建一个结点
    		q = (DLNode*)malloc(sizeof(DLNode));
    		q->prior = NULL;
    		q->data = a[i];
    		q->next = NULL;
    
    		//连接
    		p->next = q;
    		q->prior = p;
    
    		//为下次准备
    		p = q;
    		q = NULL;
    
    	}
    	
    }
    void myPrintDList(const DLNode* pHead)
    {
    	if (pHead == NULL || pHead->next == NULL)
    	{
    		cout << "the DList is empty " << endl;
    		return;
    	}
    
    	DLNode* p = pHead->next;
    
    	cout << "the DList is: ";
    	while (p)
    	{
    		cout << p->data << " ";
    		p = p->next;
    	}
    
    	cout << endl;
    
    }
    
    
    void myReservePrintDList(DLNode* pHead)
    {
    	if (pHead == NULL || pHead->next == NULL)
    	{
    		cout << "the DList is empty " << endl;
    		return;
    	}
    
    	DLNode* p = pHead;
    
    	
    	while (p->next != NULL)
    	{
    		p = p->next;
    	}
    
    	cout << "the RDList is: ";
    	while (p != pHead)
    	{
    		cout << p->data << " ";
    		p = p->prior;
    	}
    	cout << endl;
    
    }
    
    
    
    int getLengDList(DLNode* pHead)
    {
    	if (pHead == NULL)
    	{
    		return 0;
    	}
    
    	DLNode* p = pHead->next;
    	int len = 0;
    
    	while (p)
    	{
    		++len;
    		p = p->next;
    		
    	}
    
    	return len;
    }
    
    void insertDList(DLNode* &pHead, int pos, ElemType val)
    {
    	if (pHead == NULL || pos < 0 || pos > getLengDList(pHead))
    	{
    		return;
    	}
    
    	//找到要插入的位置
    	DLNode* p = pHead;
    	while (pos > 0)
    	{
    		p = p->next;
    		--pos;
    	}
    
    	//创建结点
    	DLNode * q = (DLNode*)malloc(sizeof(DLNode));
    	q->prior = NULL;
    	q->data = val;
    	q->next = NULL;
    
    	//连接
    	q->next = p->next;//顺序很重要，一旦移动有可能后继前驱都会变
    	if (p->next != NULL)//不为尾元素
    	{
    		p->next->prior = q;
    	}
    	p->next = q;
    	q->prior = p;
    
    	p = NULL;
    	q = NULL;
    }
    
    void removeDList(DLNode* &pHead, int pos, ElemType& reRal)
    {
    	if (pHead == NULL || pHead->next == NULL || pos < 0 || pos >= getLengDList(pHead))
    	{
    		return;
    	}
    
    	//找到要插入的位置
    	DLNode *p = pHead;
    
    	while (pos > 0)
    	{
    		p = p->next;
    		--pos;
    	}
    
    	DLNode *q = p->next;
    	p->next = q->next;
    	if(q->next != NULL)//不为尾元素
    	{
    		q->next->prior = p;
    	}
    	
    	reRal = q->data;
    	q->next = NULL;
    	q->prior = NULL;
    	free(q);
    
    
    }

test.cpp

#pragma once
    #include <iostream>
    #include "DList.h"
    using namespace std;
    #include <vector>
    
    //创建销毁
    void test0()
    {
    	ElemType arr[5] = {0,1,2,3,4};
    	DLNode * head = NULL;
    
    	initDList(head);
    	myPrintDList(head);
    	creatDList(head,arr,sizeof(arr)/sizeof(arr[0]));
    	cout << "leng: " << getLengDList(head) << endl;
    	myPrintDList(head);
    	myReservePrintDList(head);
    	destoryDList(head);
    	cout << "leng: " << getLengDList(head) << endl;
    	myPrintDList(head);	
    }
    
    void test1()
    {
    	ElemType arr[5] = { 0,1,2,3,4 };
    	DLNode * head = NULL;
    
    	initDList(head);
    	myPrintDList(head);
    	creatDList(head, arr, sizeof(arr) / sizeof(arr[0]));
    	myPrintDList(head);
    	insertDList(head,5,5);
    	myPrintDList(head);
    	myReservePrintDList(head);
    
    	int removeVal;
    	removeDList(head, 5, removeVal);
    	myPrintDList(head);
    	myReservePrintDList(head);
    	cout << "removeVal: " << removeVal << endl;
    }
    
    bool Find(int target, vector<vector<int> > array) {
    
    	if (array.empty())
    	{
    		return false;
    	}
    	int row = 0;//判断行数
    	int col = array[0].size() - 1;
    	while (row < array.size() && col >= 0)
    	{
    		//总列数不等于总行数
    		//先判断目标值是否比该行最大值 小
    		if (target < array[row][col])//如果小就在本行查找
    		{
    			--col;
    		}
    		else if (target > array[row][col])
    		{
    			++row;
    		}
    		else//(target == array[row][col])
    		{
    			return true;
    		}
    	}
    	return false;
    }
    
    int main(void)
    {
    	vector<vector<int>> veci= { {1,2,3,4},{ 2,3,4,5 } };
    	cout << veci.size() << " " << veci[0].size() << endl;
    	cout << veci[0][0] << " "<< veci[veci.size() - 1][veci[0].size() - 1] << endl;
    
    	cout << Find(6, veci) << endl;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5NDc2NzU2NzY_size_16_color_FFFFFF_t_70]: /images/20220228/30fe9b3d5b6f49a58ff9ad5c47e8e099.png