数据结构——练习之双向链表实现

浅浅的花香味﹌ 2022-06-16 23:23 249阅读 0赞

# 数据结构——练习之双向链表实现 #

为了掌握并使用双向链表，就动手写了这个小程序，包括一些双向链表的基本操作以及求集合并

![SouthEast][]

源码：

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    /**双向链表**/
    typedef struct{
    	int number;
    }Node;
    typedef struct NodeList{
    	Node n;	//数据
    	NodeList* prior;	//指向前驱元素
    	NodeList* next;		//指向后继元素
    	int length;
    };
    /**初始化**/
    NodeList* InitList(){
    	NodeList *h = (NodeList*)malloc(sizeof(NodeList));
    	h->next = h;
    	h->prior = h;
    	h->length = 0;
    	return h;
    }
    /**创建链表**/
    void CreateList(NodeList* L){
    	int n;
    	printf("Input the number of the set: ");
    	scanf("%d",&n);
    	NodeList *p = L,*pre;
    	Node node;
    	for(int i = 0;i<n;i++){
    		printf("Input the %d number:",i+1);
    		scanf("%d",&node.number);
    		pre = (NodeList*)malloc(sizeof(NodeList));
    		pre->n = node;
    		p->next = pre;
    		pre ->prior = p;
    		pre ->next = L;
    		p = pre;
    		L->prior = pre;
    		L->length++;
    	}
    }
    /**打印链表**/
    void PrintList(NodeList *L){
    	NodeList *p = L;
    	int len = L->length;
    	printf("The set is :\n");
    	for(int i = 0;i<len;i++){
    		p = p->next;
    		printf("%d  ",(p->n.number));
    	}
    	printf("\n");
    }
    /**插入新元素**/
    void InsertList(NodeList *L,int i,Node n){
    	int len = L->length;
    	NodeList *pre = L;
    	int j = 0;
    	if(i<0||i>len){
    		printf("Error!Wrong position to insert!");
    		exit(0);
    	}else{
    		while(j<i){
    			pre = pre->next;
    			j++;
    		}
    		NodeList* p = (NodeList*)malloc(sizeof(NodeList));
    		p->n = n;
    		p->next = pre->next;
    		pre->prior = p;
    		p->prior = pre;
    		pre->next = p;
    		L->length++;
    	}
    }
    /**删除元素**/
    void DelteList(NodeList *L,int i){
    	int len = L->length;
    	NodeList *pre = L;
    	int j = 0;
    	if(i<0||i>len){
    		printf("Error!Wrong position to insert!");
    		exit(0);
    	}else{
    		while(j<i){
    			pre = pre->next;
    			j++;
    		}
    		pre->next = pre->next->next;
    		pre->next->next->prior = pre;
    		L->length--;
    	}
    }
    NodeList* MergeList(NodeList* A,NodeList* B){
    	NodeList* a = A->next;
    	NodeList* b;
    	Node an,bn;
    	int m = A->length;
    	int n;
    	for(int i =0;i<m;i++){
    		an = a->n;
    		n = B->length;
    		b = B->next;
    		for(int j =0;j<n;j++){
    			bn = b->n;
    			if(an.number==bn.number){
    				DelteList(B,j);
    				break;
    			}else{
    				b = b->next;
    			}
    		}
    		a = a->next;
    	}
    	A->prior->next = B->next;
    	a = B->prior;
    	B->prior = A->prior;
    	A->prior = a;
    	a->next = A;
    	A->length += B->length;
    	return A;
    }
    
    void main(){
    	NodeList *A = InitList();
    	printf("--------Create the set A--------\n");
    	CreateList(A);
    	Node n;
    	n.number = 222;
    	//InsertList(A,1,n);
    	PrintList(A);
    	NodeList *B = InitList();
    	printf("--------Create the set B--------\n");
    	CreateList(B);
    	PrintList(B);
    	printf("----------Merge A and B----------\n");
    	A = MergeList(A,B);
    	PrintList(A);
    	system("pause");
    }

[SouthEast]: /images/20220617/40c5eff192bc4cc2a77243e0c63075ed.png