C语言中单向非循环链表的生成，遍历，排序，插入和删除

#include <stdio.h> #include <malloc.h> #include <stdlib.h> //链表中一个节点 typedef struct Node { int data;//存储数据的变量 struct Node *pNext;//下一个节点地址 }NODE,*PNODE;//NODE等价于struct Node,PNODE等价于struct Node * //不要忘记函数的声明 ------------------- PNODE create_list(); void traverse_list(PNODE pHead);//遍历输出 bool is_empty(PNODE pHead);//是否为空 int length_list(PNODE pHead);//数组长度 //在第pos个节点的前面插入一个数据为value的节点 bool insert_list(PNODE pHead,int pos,int value); bool delete_list(PNODE pHead,int pos,int *); void sort_list(PNODE); //----------------------------------------- //下面是主函数 int main(void){ PNODE pHead=NULL;//等价于struct Node *=NULL int val;//存放删除的数据 pHead=create_list(); traverse_list(pHead); sort_list(pHead);//数组排序 printf("排序后的链表：\n"); traverse_list(pHead); //在第一个节点位置前面插入一个节点，可以更改第二个参数改变插入位置 if(!insert_list(pHead,0,111)){ printf("insert失败\n"); } printf("insert后的链表：\n"); traverse_list(pHead); //删除第一个节点 if(!delete_list(pHead,0,&val)){ printf("delete失败\n"); }else{ printf("delete成功，删除的数据：%d\n",val); } printf("delete后的链表：\n"); traverse_list(pHead); return 0; } //创建链表 PNODE create_list(){ int len; int i; int val;//用来临时存放用户输入的节点的值 //这是一个临时节点 ,是不存放有效数据的头结点 PNODE pHead=(PNODE)malloc(sizeof(NODE)); // 分配失败则退出 if(pHead==NULL){ exit(-1); } PNODE pTail=pHead;//尾节点 pTail->pNext=NULL; printf("请输入您需要的链表节点个数："); scanf("%d",&len); for(i=0;i<len;++i){ printf("请输入第%d个节点的值：",i+1); scanf("%d",&val); PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(pHead==NULL){ exit(-1); } pNew->data=val; pTail->pNext=pNew; pNew->pNext=NULL; 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!=NULL){ ++len; p=p->pNext; } return len; } //链表中数据的排序 void sort_list(PNODE pHead){ int i,j,t; PNODE p,q; //链表的长度 int len=length_list(pHead); //使用i和j当做循环是否结束的标志，p=p->pNext在循环一次后指向下一个 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) { t=p->data; p->data=q->data; q->data=t; } } } } //在第pos个节点的前面插入一个数据为value的节点 //为了符合编程习惯，这里pos=0时代表第一个 bool insert_list(PNODE pHead,int pos,int value) { int i=0; PNODE p=pHead; //链表的长度 int len=length_list(pHead); /* 如果给出的pos小于0，或者头结点为空 ，或者给出的pos位置大于链表长度 那么不符合规则 ，直接返回 */ if(pos<0||p==NULL||pos>len) { return false; } //通过循环得到第pos个节点前面的节点 while(p!=NULL && i<=pos-1) { p=p->pNext; i++; } //新建节点 PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(pNew==NULL) { printf("动态分配内存失败"); exit(-1); } //把数据放入节点 pNew->data=value; //得到第pos个节点 PNODE q=p->pNext; //把新建的节点放在pos节点前面 p->pNext=pNew; //把pos 节点放在新插入的节点后面 pNew->pNext=q; return true; } //删除第pos个节点 bool delete_list(PNODE pHead,int pos,int * pVal) { int i=0; PNODE p=pHead; //链表的长度 int len=length_list(pHead); /* 如果给出的pos小于0， 或者头结点为空 ， 或者给出的pos位置大于等于链表长度 ， 那么不符合规则 ，直接返回 */ if(pos<0||p==NULL||pos>=len) { return false; } //通过循环得到第pos个节点前面的节点 while(p!=NULL && i<=pos-1) { p=p->pNext; i++; } PNODE q=p->pNext; *pVal=q->data; //删除p节点后面的节点 p->pNext=p->pNext->pNext; free(q); q=NULL; return true; }