头插法和尾插法建立单链表

Dear 丶 2022-05-09 02:44 162阅读 0赞

/*头插法和尾插法建立单链表*/ 
    #include <iostream>
    using namespace std;
    typedef int ElemType;
    typedef struct LNode {
    	ElemType data;//定义数据域，存放元素值 
    	struct LNode *next; 
    }LinkList;
     
     
    //头插法建表(从尾部一个一个往前插入)
    void CreateListHead(LinkList *&L, ElemType a[], int n){ //用来暂时存放数据 
    	LinkList *s;
    	L = (LinkList *)malloc(sizeof(LinkList));//创建头节点
    	L->next = NULL; //将头结点next域置空
    	for(int i = 0; i < n; i++) {	//循环建立数据结点
    		s = (LinkList *)malloc(sizeof(LinkList));
    		//将结点s插在原开始节点之前，头结点之后
    		s->data = a[i];//数据放到数据域 
    		s->next = L->next;//此时将s的next区域置为空
    		L->next = s;//指向数据域 
    		
    	} 
    }
    
    
    //尾插法建表(一个接一个从头插入） 
    void CreateListTail(LinkList *&L, ElemType a[], int n) {
    	LinkList *s, *r;
    	L = (LinkList *)malloc(sizeof(LinkList));//创建头节点
    	r=L;//r始终指向尾结点，开始时头结点和尾结点是同一个
    	for(int i = 0; i < n; i++) {
    		s = (LinkList *)malloc(sizeof(LinkList));//创建数据结点
    		s->data = a[i];//数据域 
    		r->next = s;//将s插入到r后 
    		r = s;//r每次指向最后一个节点 
    	} 
    	r->next = NULL; 
    }
    
    void DispList(LinkList *L) {
    	LinkList *p = L->next;//p指向开始节点 
    	while(p != NULL) {
    		cout << p->data << " ";//数据数据域 
    		p = p->next;
    	}
    }
    
    int main(){    
    	LinkList *L;	
    	int n;	
    	cout << "请输入链表元素的个数n:";	
    	cin >> n;
    	int a[10000];	
    	for(int i = 0;i < n; i++){	  
    		cin >> a[i];	
    	}	
    //头插法建表	
    	CreateListHead(L, a, n);		
    	cout << "头插法建表：";	
    	DispList(L);//输出 
    	cout << endl;	
    //尾插法建表	
    	CreateListTail(L, a, n);		
    	cout << "尾插法建表：";	
    	DispList(L);//输出
    	cout << endl;
    	return 0;
    }

![70][]

[70]: /images/20220509/e7a0ec48c2644dd1a0cc3c2e77a10210.png