双向链表的建立及基本操作

布满荆棘的人生 2023-07-13 12:10 2阅读 0赞

#include<windows.h>
    #include<iostream>
    #define N 5
    using namespace std;
    typedef struct DuLnode
    {
        
    	int data;    //数据域
    	struct DuLnode *prior;  //直接前驱
    	struct DuLnode *next;  //直接后继
    }DuLnode, *DuLinklist;//双链表的类型定义
    
    DuLinklist InitDulist(int a[N])//初始化双链表
    {
        
    	int i;
    	DuLinklist L;
    	L = (DuLnode*)malloc(sizeof(DuLnode));
    	if (L == NULL)
    	{
        
    		cout << "error";
    		exit(0);
    	}
    	else L->next = NULL;
    	DuLinklist p;
    	p = L;
    	for (i = 0; i < N; i++)
    	{
        
    		DuLinklist q;
    		q = (DuLnode*)malloc(sizeof(DuLnode));
    		if (q == NULL)
    		{
        
    			cout << "error";
    			exit(0);
    		}
    		else q->next = NULL;
    		q->data = a[i];
    		p->next = q;
    		q->prior = p;
    		p = q;
    	}
    	p->next = NULL;
    	return L;
    }
    
    void putDulist(DuLinklist L)//输出双链表
    {
        
    	cout << "当前链表元素为：";
    	DuLinklist p;
    	p = L->next;
    	while (p)
    	{
        
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }
    
    void GetDulinklist(DuLinklist L)//获取链表的第i个元素
    {
        
    	int i, j = 0;
    	cout << "请输入你要获取第__个元素：";
    	cin >> i;
    	DuLinklist p;
    	p = L->next;
    	while (p&&j < i - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	cout << "第" << i << "个元素为：";
    	if (j > i - 1) cout << "error";
    	else cout << p->data;
    	cout << endl;
    }
    
    DuLinklist DeleteDulist(DuLinklist L)//删除链表中的第i个元素
    {
        
    	int i, j = 0;
    	cout << "请输入你要删除第__个元素";
    	cin >> i;
    	DuLinklist p, q;
    	p = L->next;
    	while (p&&j < i - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	q = L;
    	while (q&&q->next != p)
    	{
        
    		q = q->next;
    	}
    	q->next = p->next;
    	p->next->prior = q;
    	free(p);
    	return L;
    }
    
    DuLinklist InsertDulist(DuLinklist L)//在第i个元素前插入一个元素
    {
        
    	int i, j = 0, x;
    	cout << "你要在第__个元素前插入一个值为__的元素，请依次输入：";
    	cin >> i >> x;
    	DuLinklist p, q;
    	p = L->next;
    	q = L;
    	while (p&&j < i - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	while (q&&q->next != p)
    	{
        
    		q = q->next;
    	}
    	DuLinklist s;
    	s = (DuLnode*)malloc(sizeof(DuLnode));
    	if (s == NULL)
    	{
        
    		cout << "error";
    		exit(0);
    	}
    	else s->next = NULL;
    	s->data = x;
    	s->next = p;
    	s->prior = q;
    	q->next = s;
    	p->prior = s;
    	return L;
    }
    
    int main()
    {
        
    	int i, a[N], M;
    	DuLinklist L;
    	cout << "请输入" << N << "个链表元素：";
    	for (i = 0; i < N; i++)
    	{
        
    		cin >> a[i];
    	}
    	L = InitDulist(a);
    	while (1)
    	{
        
    		Sleep(1000);
    		cout << "1:获取链表的第i个元素" << endl;
    		cout << "2:在第i个元素前插入一个元素" << endl;
    		cout << "3:删除链表中的第i个元素" << endl;
    		void putDulist(DuLinklist L);//输出双链表
    		cout << "4:输出双链表" << endl;
    		cout << "5:退出操作" << endl;
    		cout << "请输入你要操作的代号：";
    		cin >> M;
    		switch (M)
    		{
        
    		case 1:
    			GetDulinklist(L);
    			break;
    		case 2:
    			InsertDulist(L);
    			break;
    		case 3:
    			DeleteDulist(L);
    			break;
    		case 4:
    			putDulist(L);
    			break;
    		}
    		if (M == 5)break;
    	}
    	return 0;
    }