1 #include<stdio.h> 2 #include<malloc.h> 3 #include<stdlib.h> 4 5 //函数声明 6 PNODE create_list();//返回值是链表头结点的地址 7 void traverse_list(PNODE pHead); 8 bool is_empty(PNODE pHead); 9 int length_list(PNODE pHead); 10 bool insert_list(PNODE,int,int);//此处可以不定义形参,只声明形参类型 11 bool delete_list(PNODE,int,int *); 12 void sort_list(PNODE pHead); 13 14 15 typedef struct Node{ 16 int data;//数据域 17 struct Node * pNext;//指针域 18 }NODE,*PNODE;//NODE等价于struct Node PNODE等价于struct Node* 19 20 int main(){ 21 PNODE pHead = NULL;//等价于struct Node * pHead = NULL; 22 23 pHead = create_list();//创建一个非循环单链表,并将该链表的头结点的地址赋值给pHead 24 25 traverse_list(pHead);//遍历 26 27 sort_list(pHead);//排序 28 29 insert_list(pHead,4,33);在第个节点的位置插入数据33 30 31 int val; 32 if(delete_list(pHead,4,&val)){ 33 //删除第四个节点的数据,并返回删除的数据,由于是直接在地址上操作,所以无需返回值 34 printf("删除成功,删除的数据是%d",val); 35 } 36 else{ 37 printf("删除失败,数据不存在"); 38 } 39 if(is_empty(pHead)){ 40 printf("链表为空"); 41 } 42 else{ 43 printf("链表不空"); 44 } 45 46 int len = length_list(pHead); 47 printf("链表长度是%d",len); 48 49 50 51 return 0; 52 } 53 54 PNODE create_list(){ 55 int len;//有效节点的个数 56 int i; 57 int val;//临时存放用户输入的结点的值 58 59 //分配一个不存放有效数据的头结点 60 PNODE pHead = (PNODE)malloc(sizeof(NODE)); 61 if(pHead==NULL){ 62 printf("分配失败,程序终止"); 63 exit(-1); 64 } 65 66 PNODE pTail = pHead; 67 pTail->PNext = NULL;//若只有一个结点,此时就为尾节点,指针域应当为空 68 printf("链表节点个数:"); 69 scanf("%d",&len); 70 71 for(i=0;i<len;i++){ 72 printf("请输入第%d个节点的值:",i+1); 73 scanf("%d",&val); 74 75 PNODE pNew = (PNODE)malloc(sizeof(NODE));//生成新结点 76 if(pNew==NULL){ 77 printf("分配失败,程序终止"); 78 exit(-1); 79 } 80 pNew->data = val;//把数据存放进新结点的数据域 81 pNew->pNext = NULL;//把新结点指针域赋值为空 82 pTail->pNext = pNew;//把新结点地址赋值给尾节点指针域 83 pTail = pNew;//最后一步把新结点地址复制给尾节点(就是让新结点成为尾节点) 84 // pHead->pNext = pNew; 85 // pNew->pNext=NULL;//最后一个结点的指针域为空 86 } 87 return pHead; 88 } 89 90 void traverse_list(PNODE pHead){ 91 PNODE p = pHead->pNext;//若链表为空,则头结点指针域就为空,则p就为空 92 93 while(p!=NULL){ 94 printf("%d ",p->data); 95 p=p->pNext; 96 } 97 printf("\n"); 98 return; 99 } 100 101 bool is_empty(PNODE pHead){ 102 if(pHead->pNext==NULL){//如果头结点的指针域为空,则链表为空 103 return true; 104 } 105 else{ 106 return false; 107 } 108 } 109 110 int length_list(PNODE pHead){ 111 PNODE p = pHead->pNext; 112 int len = 0; 113 while(p!=NULL){ 114 len++; 115 p=p->pNext; 116 } 117 } 118 119 void sort_list(PNODE pHead){ 120 int i ,j , t; 121 int len = length_list(pHead); 122 PNODE p,q; 123 //重点!!! 124 for(i=0,p=pHead->pNext; i<len-1; i++,p=p->pNext){ 125 for(j=j+1,q=p->pNext;j<len;j++,q=q->pNext){ 126 if(p->data > q->data){ //类似于数组的:a[i]>a[j] 127 t = p->data; //t=a[i]; 128 p->data = q->data; //a[i]=a[j]; 129 q->data = t; //a[j]=t; 130 } 131 } 132 } 133 } 134 135 //在pHead所指向链表的第pos个节点前面插入新节点,值是val,pos从1开始 136 bool insert_list(PNODE pHead,int pos,int val){ 137 int i = 0; 138 PNODE p=pHead; 139 140 while(p!=NULL&&i<pos-1){//找到第pos前面一个节点的指针域,所指向的为插入的节点位置 141 p=p->pNext; 142 i++; 143 } 144 145 if(i>pos-1||p==NULL){ 146 return false; 147 } 148 149 PNODE pNew=(PNODE)malloc(sizeof(NODE));//动态分配内存生成一个新节点 150 if(pNew==NULL){ 151 printf("动态分配内存失败"); 152 exit(-1); 153 } 154 //重点 155 pNew->data = val;//把数据存放进插入的新结点的数据域 156 PNODE q=p->pNext;//临时节点q指向节点p的指针域,即插入新结点之后的节点地址 157 p->pNext=pNew;//节点p的指针域指向新节点地址 158 pNew->pNext=q;//新结点的指针域指向原来p节点的指针域 159 160 return true; 161 } 162 163 bool delete_list(PNODE pHead,int pos,int *pVal){ 164 int i = 0; 165 PNODE p=pHead; 166 167 while(p->pNext!=NULL&&i<pos-1){//找到要删除的第pos个节点之前的节点的指针域 168 p=p->pNext; //假如要删除第五个节点,需要找到第四个节点的指针域,这样就指向了第五个节点 169 i++; 170 } 171 172 if(i>pos-1||p->pNext==NULL){ 173 return false; 174 } 175 176 PNODE q=p->pNext;//临时节点q指向即将删除节点的地址(即p节点的指针域指向的节点),以便最后释放内存地址 177 *pVal = q->data;//保存即将删除节点的数据域 178 p->pNext=p->pNext->pNext; 179 //重新使p节点指向p节点之后节点的指针域(p节点后面的节点被删,所以p节点的下一个的下一个节点地址) 180 free(q);//释放q节点内存 181 q=NULL; 182 return true; 183 }