链表的增删排序等操作

ゝ一纸荒年。 2022-06-08 05:19 126阅读 0赞

#include <stdio.h>
    #include <malloc.h>
    typedef struct Node{
    	int data;//数据域 
    	Node * pNext; //指针域 
    }NODE,*PNODE;//NODE等价于struct Node,PNODE等价于struct Node *
    
    PNODE create_list();//创建链表 
    void show_list(PNODE);//打印链表 
    int getSize(PNODE);//得到链表长度
    void delete_list(PNODE);//删除链表
    bool is_empty(PNODE);//判断是否为空 
    void insert_list(PNODE);//插入一个元素 
    void sort_list(PNODE);//对链表进行排序 
    
    int main(void){
    	PNODE pHead;
    	pHead = create_list(); 
    	show_list(pHead); 
    	delete_list(pHead);
    	show_list(pHead); 
    	insert_list(pHead);
    	show_list(pHead); 
    	sort_list(pHead);
    	show_list(pHead); 
    	return 0; 
    }
    //创建链表 
    PNODE create_list(){
    	printf("请输入你要创建的链表的元素个数\n");
    	printf("Len=");
    	int len;
    	scanf("%d",&len);
    	PNODE pHead = (PNODE)malloc( sizeof(NODE) );
    	if(pHead == NULL){
    		printf("分配失败，程序终止.");
    		exit(-1); 
    	} 
    	PNODE pTail = pHead;//令尾指针等于头指针 
    	pTail->pNext = NULL; 
    	PNODE p = pTail; 
    	int i,val; 
    	for(i=0; i<len; i++){
    		printf("请输入第%d个元素的值:",i+1);
    		scanf("%d",&val); 
    		p = (PNODE)malloc( sizeof(NODE) );
            p->data = val;
    		p->pNext = NULL;
    	 	pTail->pNext = p;
    		pTail = p; 
    	} 
        return pHead; 
    } 
    //打印链表 
    void show_list(PNODE pHead){
    	if(is_empty(pHead) ){ 
    		printf("链表为空,不能打印元素\n");
    		return; 
    	}
    	printf("\n该链表共有%d个元素\n",getSize(pHead) ); 
    	PNODE p = pHead->pNext; 
    	while(p != NULL){
    		printf("%d ",p->data);
    		p = p->pNext; 
    	} 
    	printf("\n"); 
    } 
    //得到链表长度
    int getSize(PNODE pHead){
    	if(is_empty(pHead) ){ 
    		return 0; 
    	}
    	int count=0; 
    	PNODE p = pHead->pNext; 
    	while(p != NULL){
    		count++; 
    		p = p->pNext; 
    	}
    	return count; 
    }
    //判断是否为空
    bool is_empty(PNODE pHead){
    	if(pHead==NULL || pHead->pNext==NULL){
    		return true; 
    	} 
    	return false; 
    } 
    //删除链表 
    void delete_list(PNODE pHead){
    	if(is_empty(pHead) ){ 
    		printf("链表为空，不能删除\n");
    		return; 
    	}
    	int size =  getSize(pHead); 
    	printf("\n该链表共有%d个元素\n", size); 
    	printf("请输入要删除第几个元素:");
    	int index;
    	scanf("%d",&index);
    	while( index<1 || index > size){
    		printf("你输入的值超过界限，请重新输入:");
    		scanf("%d",&index); 
    	} 
    	int i; 
    	PNODE p = pHead; 
    	PNODE temp; 
    	for(i=0; i<size; i++){
    		if( i == index-1 ){
    			temp = p->pNext; 
    			p->pNext = p->pNext->pNext;
    			free(temp); //把删除的节点释放,防止内存泄露 
    		} 
    		p = p->pNext; 
    	}
    } 
    //插入一个链表
    void insert_list(PNODE pHead){
    	 if(is_empty(pHead) ){ 
    		printf("链表为空，不能删除\n");
    		return; 
    	}
    	int size =  getSize(pHead); 
    	printf("\n该链表共有%d个元素\n", size); 
    	printf("请输入要插入为第几个元素 元素值:");
    	int index,val;
    	scanf("%d %d",&index,&val);
    	while( index<1 || index > size+1){
    		printf("你输入的值超过界限，请重新输入:");
    		scanf("%d",&index); 
    	}
    	int i; 
    	PNODE p = pHead; 
    //第一种插入的算法 
    /*	for(i=0; i<=size; i++){//因为是插入,所以可以i=size 
    		if( i == index-1 ){
    			PNODE temp = (PNODE)malloc( sizeof(NODE) );
    			temp->data = val; 
    			temp->pNext = p->pNext; 
    			p->pNext = temp;
    			
    		} 
    		p = p->pNext; 
    	}
    */	
    //第二种插入的算法 
    	i=0; 
    	while(p!=NULL && i < index-1){
    		p = p->pNext;
    		i++; 
    	}	
    	PNODE temp = (PNODE)malloc( sizeof(NODE) );
    	temp->data = val; 
    	temp->pNext = p->pNext; 
    	p->pNext = temp;
    } 
    //对链表进行排序
    void sort_list(PNODE pHead){
    	if(is_empty(pHead)){
    		printf("链表为空,排序失败"); 
    		return; 
    	} 
    	printf("\n链表排序的结果如下:\n");
    	int i,j,t;
    	PNODE p,q; 
    	int len=getSize(pHead);
    	for(i=0,p=pHead->pNext; i<len-1; i++,p=p->pNext){
    		for(j=i+1,q=p->pNext; j<len; j++,q=q->pNext){
    			if(p->data > q->data){//相当于数组的: a[i] > a[j]
    				t = p->data;      //相当于数组的: t = a[i];
    				p->data = q->data;//相当于数组的: a[i] = a[j];
    				q->data = t;      //相当于数组的: a[j] = t;
    			} 
    		} 
    	} 
    }

![1343556685_3305.jpg][]

[1343556685_3305.jpg]: https://img-my.csdn.net/uploads/201207/29/1343556685_3305.jpg