博客

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
	int data;	  //数据域
	struct Node *pNext;//指针域
}Node,*pNode;

//函数声明
pNode create_list();
void traverse_list(pNode pHead);
bool is_empty(pNode pHead);
int  length_list(pNode pHead);
bool insert_list(pNode pHead, int pos, int  val);
bool delete_list(pNode pHead, int pos, int * val);
void sort_list(pNode pHead);


void main()
{
	pNode pHead=NULL;
	int val;

	pHead=create_list();//创建一个非循环的单链表，并将链表的头结点的地址赋给pHead
	traverse_list(pHead);//遍历
	//if (is_empty(pHead))  
    // printf("链表为空\n");  
    //else  
    // printf("链表不为空\n");  
	int len=length_list(pHead);
    printf("链表的长度为:%d\n",len );  

    sort_list(pHead);  
	printf("排序后的链表为:\n" );
    traverse_list(pHead); 

	insert_list(pHead, 3, 89);
	printf("插入后的链表为:\n" );
    traverse_list(pHead); 
	
    delete_list(pHead, 4, &val);  
	printf("删除后的链表为:\n" );
    traverse_list(pHead);  

}

pNode create_list(void)
{
	int len;//用来存放有效节点的个数
	int i;
	int val;//用来临时存放用户输入的结点的值

	pNode pHead=(pNode)malloc(sizeof(Node));
	if(pHead==NULL)
	{
		printf("分配失败，程序终止!\n");
		exit(-1);
	}

	/*创建尾节点*/  
    pNode pTail = pHead;  
  
    /*追加节点*/  
	printf("请输入你需要生成的链表节点的个数:len= ");
	scanf("%d",&len);
	for(i=0;i<len;i++)
	{
		printf("请输入第%d个节点的值:",i+1);
		scanf("%d",&val);

		pNode pNew=(pNode)malloc(sizeof(Node));
		if(pNew==NULL)
		{
		printf("分配失败，程序终止!\n");
		exit(-1);
		}
		pNew->data=val;
		pNew->pNext=NULL;
		pTail->pNext=pNew;
		pTail=pNew;
	}
	return pHead;

}
void traverse_list(pNode pHead)
{
	pNode p=pHead->pNext;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->pNext;
	}
	printf("\n");
	return;
}

bool is_empty(pNode pHead)
{

	if(pHead->pNext==NULL)
		return true;
	else
		return false;
}
int length_list(pNode pHead)
{
	pNode p=pHead->pNext;
	int len=0;
	while(p!=0)
	{
		len++;
		p=p->pNext;
	}
	return len;
}

void sort_list(pNode pHead)
{
	int i, j, t;  
    int len = length_list(pHead);  
    pNode p, q;  
    /*理解泛型的概念，用p=p->pNext代替了p++*/  
    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;  
                p->data = q->data;  
                q->data = t;  
            }  
        }  
    }  
	
}

bool insert_list(pNode pHead,int pos,int val)
{
	pNode p = pHead;  
    int i = 0;  
    /*把p的指针移到pos的前一个节点*/  
    while (i<pos-1 && NULL!=p)  
    {  
        p = p->pNext;  
        i++;  
    }  
    /*增强程序健壮性，避免【pos为-1】 或者 【pos大于length】的情况，程序崩溃*/  
    if (i>pos-1 || NULL==p)  
        return false;  
    pNode pNew = (pNode)malloc(sizeof(Node));  
    if (NULL == pNew)  
    {  
        printf("动态内存分配失败\n");  
        exit(-1);  
    }  
    pNew->data = val;  

	//pNode q=p->pNext;  //法一
   // p->pNext = pNew; 
   //pNew->pNext = q; 
	
	pNew->pNext = p->pNext;  //法二
    p->pNext = pNew;
    return true;  

}

bool delete_list(pNode pHead, int pos, int * pVal)  
{  
    int i = 0;  
    pNode p = pHead;  
    while (NULL!=p->pNext && i<pos-1)  
    {  
        p = p->pNext;  
        i++;  
    }  
    if (NULL==p->pNext || i>pos-1)  
        return false;  

    pNode q = p->pNext;
	*pVal=q->data;

	//删除p节点后面的节点
    p->pNext = p->pNext->pNext;//等价于p->pNext = q->pNext;  
    free(q);  
    q = NULL;  
    return true;  
}