实现单链表、栈、队列功能

1、单链表实现增、删、改、查、排序功能，定义一个空的头结点，头指针指向头结点，头结点的指针域保存首节点

#include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef struct Node{ int data; struct Node* pNext; }NODE,*PNODE; PNODE creat_list(void); void traverse_list(PNODE pHead); int is_empty(PNODE pHead); int length_list(PNODE); int insert_list(PNODE,int,int); int delete_list(PNODE,int); void sort_list(PNODE); int main(int argc, char const *argv[]) { PNODE pHead = NULL; pHead = creat_list(); //创建一个非循环单链表头结点的地址赋给它 traverse_list(pHead); int len = length_list(pHead); printf("链表长度是%d\n",len); sort_list(pHead); traverse_list(pHead); return 0; } PNODE creat_list(void){ int len; int i; int val; PNODE pHead=(PNODE)malloc(sizeof(NODE));//创建节点所以需要malloc if(pHead == NULL){ printf("内存分配失败\n"); exit(-1); } PNODE pTail=pHead; pTail->pNext = NULL; printf("请输入节点个数："); scanf("%d",&len); for(i=0;i<len;i++){ printf("请输入第%d个节点的值\n",i+1); scanf("%d",&val); PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew){ printf("内存分配失败\n"); 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){ printf("%d",p->data); p = p->pNext; } printf("\n"); } int is_empty(PNODE pHead){ if(pHead->pNext == NULL){ return 1; } else { return -1; } } int length_list(PNODE pHead) { PNODE p=pHead->pNext; int len=0; while(p!=NULL) { ++len; p=p->pNext; } return len; } //插入节点必须要知道要插入的前一个节点的位置 int insert_list(PNODE pHead,int pos,int val){ int i=0; PNODE p = pHead; PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(pNew == NULL) { printf("内存分配失败\n"); exit(-1); } while(p!=NULL && i<pos) { p=p->pNext; ++i; } if(i>pos || p==NULL) { return -1; } pNew->pNext = p->pNext; p->pNext = pNew; pNew->data = val; return 1; } int delete_list(PNODE pHead,int pos){ int i=0; PNODE p=pHead; while(p!=NULL && i<pos) { p=p->pNext; ++i; } if(i>pos || NULL == p) { return -1; } PNODE q=p->pNext; p->pNext=p->pNext->pNext; q=NULL; return 1; } void sort_list(PNODE pHead) { int i,j,t; int len=length_list(pHead); PNODE p; PNODE q; 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; } } } } 2、栈

实现入栈和出栈操作，栈是先进后出的，我用的方法是每次入栈将节点放在首节点的位置，这样方便出栈，就可以不需要遍历到尾节点的位置

#include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef struct Node{ int data; struct Node* pNext; }NODE,*PNODE; PNODE push(void); void pop(PNODE); int main(int argc, char const *argv[]) { PNODE pHead = NULL; pHead =push(); traverse_list(pHead); return 0; } PNODE push(void) { int len; int val; int i; PNODE pHead = (PNODE)malloc(sizeof(NODE)); if(pHead == NULL) { printf("内存分配失败\n"); exit(-1); } printf("请输入节点个数:\n"); scanf("%d",&len); for(i=0;i<len;i++) { printf("请输入第%d个节点的值\n",i+1); scanf("%d",&val); PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew){ printf("内存分配失败\n"); exit(-1); } pNew->data = val; pNew->pNext = pHead->pNext; pHead->pNext = pNew; } return pHead; } void pop(PNODE pHead) { PNODE p=pHead->pNext; while(p){ printf("%d",p->data); p = p->pNext; } printf("\n"); } 3.队列

队列是先进先出的，每次输入的节点放在末尾，输出遍历输出就可以了

#include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef struct Node{ int data; struct Node* pNext; }NODE,*PNODE; PNODE push(void); void pop(PNODE); void sort_list(PNODE); int length_list(PNODE); int insert_list(PNODE,int,int); int delete_list(PNODE,int); int main(int argc, char const *argv[]) { PNODE pHead = NULL; pHead = push(); pop(pHead); sort_list(pHead); printf("排序后的数为：\n"); pop(pHead); return 0; } PNODE push(void) { int len; int val; int i; PNODE pHead=(PNODE)malloc(sizeof(NODE)); if(pHead==NULL) { printf("内存分配失败！"); exit(-1); } printf("请输入队列长度：\n"); scanf("%d",&len); PNODE pTail=pHead; pTail->pNext = NULL; for(i=0;i<len;i++) { printf("请输入第%d的值：",i+1); scanf("%d",&val); PNODE pNew = (PNODE)malloc(sizeof(NODE)); pNew->data=val; pTail->pNext=pNew; pNew->pNext = NULL; pTail=pNew; } return pHead; } void pop(PNODE pHead) { PNODE p=pHead->pNext; while(p){ printf("%d ",p->data); p = p->pNext; } printf("\n"); } 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; int len=length_list(pHead); PNODE p; PNODE q; 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; } } } } int insert_list(PNODE pHead,int pos,int val) { int i=0; PNODE p=pHead; PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(pNew == NULL) { printf("内存分配失败"); exit(-1); } while(p!=NULL && i<pos) { p=p->pNext; ++i; } if(i>pos || p==NULL) { return -1; } pNew->pNext = p->pNext; p->pNext = pNew; pNew->data = val; return 1; } int delete_list(PNODE pHead,int pos){ PNODE p=pHead; int i=0; while(p!=NULL && i<pos) { p=p->pNext; ++i; } if(i>pos || NULL == p) { return -1; } PNODE q =p->pNext; p->pNext=p->pNext->pNext; q=NULL; return 1; }