``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> /* 离散存储:链表 定义: n个节点离散分配 彼此通过指针相连 每个节点只有一个前驱与后继节点 除第一个与最后一个 专业术语: 首节点、尾节点、头指针、尾指针、头结点 头结点: 没有存放数据、没有存放位数,头结点的数据类型与首节点的一样 作用:方便对链表进行操作 头指针:指向头结点的指针变量 尾指针:指向头节点的指针变量 尾节点:指针域为空 确定一个链表需要几个参数: 只需要头指针 分类: 单链表 双链表:每一个节点有两个指针域 循环链表:能通过任何一个节点能找到其他所有的节点 非循环链表 算法: 创建 遍历 查找 清空 销毁 求长度 排序 删除节点 插入节点 */ typedef struct Noode { int data;//数据域 struct Node * pNext;//指针域 } NODE,*PNODE; //struct Noode,struct Noode * 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);//插入pos位节点之后(头结点为0) bool delete_list(PNODE pHead,int pos);//删除pos节点 void sort_list(PNODE pHead);//排序 int main() { PNODE pHead = NULL; pHead = create_list();//创建一个非循环单链表 if(is_empty(pHead)) { printf("链表为空!\n"); } else { printf("链表不为空!\n"); } traverse_list(pHead); printf("\n链表长度为:%d\n",length_list(pHead)); printf("节点插入:\n"); if(insert_list(pHead,3,123)) { traverse_list(pHead); } else { printf("插入节点失败!\n"); } sort_list(pHead); traverse_list(pHead); if(delete_list(pHead,2)) { printf("删除节点成功!\n"); } return 0; } void sort_list(PNODE pHead) { PNODE p,q; int i,j,t; int len=length_list(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) { t=p->data; p->data=q->data; q->data=t; } } } } bool delete_list(PNODE pHead,int pos) { int i; PNODE p = pHead; //循环到p指向pos-1的位置 while( NULL != p->pNext && i<pos-1) { p = p->pNext; ++i; } if (NULL == p->pNext || i > pos -1) { return false; } PNODE q = p->pNext; p->pNext=q->pNext; free(q); q=NULL; return true; } bool insert_list(PNODE pHead,int pos,int val) { if(is_empty(pHead)||pos<0) { return false; } else { PNODE pNew = (PNODE)malloc(sizeof(NODE)); pNew->data=val; PNODE pMove = pHead; if(pos==0) { pNew->pNext=pMove->pNext; pMove->pNext=pNew; return true; } else if(pos<=length_list(pHead)) { while(pos>0) { pos--; pMove = pMove->pNext; } pNew->pNext=pMove->pNext; pMove->pNext=pNew; return true; } else { return false; } } } int length_list(PNODE pHead) { PNODE pLen = pHead->pNext; int sum=0; if(is_empty(pHead)) { return 0; } else { while(pLen!=NULL) { sum++; pLen = pLen->pNext; } return sum; } } bool is_empty(PNODE pHead) { if(pHead->pNext==NULL) { return true; } else { return false; } } PNODE create_list() { int len=0;//有效节点的个数 int i; int val;//用来存放用户输入的节点的值 //1.分配了一个链表所需的头结点 PNODE pHead = (PNODE)malloc(sizeof(NODE)); //判断头结点是否分配了空间 if(NULL == pHead) { printf("分配失败,程序终止!\n"); exit(-1); } //使pTail永远指向尾节点 PNODE pTail = pHead; pTail->pNext=NULL; //需要多少了节点 printf("需要生成的链表节点的个数:len = "); scanf("%d",&len); //循环输入各节点的data,形成链表 for(i=0; i<len; i++) { printf("请输入第%d个节点的值:",i+1); scanf("%d",&val); //生成一个新的节点,存放data,连接链表 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!=NULL) { printf("%d ",p->data); p = p->pNext; } printf("\n"); } ```
Click here to view the copyright notice of this site(点击此处查看本站版权声明)
必须 注册 为本站用户, 登录 后才可以发表评论!