单链表练习
完成单链表操作，要求节点构造类型：
1、建立学生结构体（学号、姓名、成绩）；
2、循环调用头插法创建整表；
3、遍历单链表；
4、任意位置插入一个完整的学生信息；
5、任意位置删除一个学生；
6、单链表逆置；
7、单链表按照学生成绩排序。
main.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "link.h"
int main(int argc, const char *argv[])
{Stu arr[]={{1,"aaa", 5},{2,"bbb", 3},{3,"ccc", 9},{4,"ddd", 1},{5,"eee", 9},{6,"fff", 3},{7,"hhh", 1},{8,"iii", 5},{9,"ggg", 4}};int len=sizeof(arr)/sizeof(Stu);//创建链表PNode L = createLink();//构造原始数据for(int i=0;i<len;i++){//使用头插法插入数据insertHead(L, arr[i]); }//遍历单链表printLink(L);//在任意位置插入一名学生的信息Stu stu={50, "zzz", 100};insertStu(L, 5, stu);printf(">>任意位置插入一名学生信息\n");printLink(L);//在任意位置删除一名学生deleteStu(L, 5);printf(">>任意位置删除一名学生信息\n");printLink(L);//单链表逆置reverseLink(L);printf(">>单链表逆置\n");printLink(L);//根据成绩进行冒泡排序bubbleSortByScore(L);printf(">>根据成绩进行冒泡排序\n");printLink(L);//销毁destroyLink(L);return 0;
}link.h
#include "link.h"Stu createStu(int id, char* name, int score){PStu p = (PStu)malloc(sizeof(Stu)); p->id=id;strcpy(p->name, name);p->score=score;return *p;
}void printStu(Stu s){printf("id=[%d],name=[%s],score=[%d]\n",s.id, s.name, s.score);
}PNode createLink(){PNode p = (PNode)malloc(sizeof(Node));if(NULL == p){printf("链表创建失败!\n");return NULL;}p->len=0;p->next=NULL;printf("链表创建成功.\n");return p;
}void insertHead(PNode L, Stu stu){PNode p = (PNode)malloc(sizeof(Node));memcpy(&p->stu, &stu, sizeof(Stu));p->next=L->next;L->next=p;L->len++;
}void printLink(PNode L){printf(">>链表长度为[%d]\n", L->len);PNode p=L->next;for(int i=0;i<L->len;i++){printStu(p->stu);p=p->next;}
}void insertStu(PNode L, int pos, Stu stu){//TODO 异常判断，ignorePNode p = L;for(int i=0;i<pos;i++){p=p->next;}// 插入PNode e = (PNode)malloc(sizeof(Node));memcpy(&e->stu, &stu, sizeof(Stu));//e->next=p->next;p->next=e;L->len++;
}void deleteStu(PNode L, int pos){//TODO 异常判断,ignorePNode p = L;for(int i=0;i<pos;i++){p=p->next;}PNode temp=p->next;p->next=p->next->next;free(temp);temp=NULL;L->len--;
}void reverseLink(PNode L){//TODO 异常判断//if(L->len == 1){return;//无须逆置}PNode p = L->next;while(p->next){PNode q=p->next;p->next=q->next;q->next=L->next;L->next=q;}
}// 法一：交换元素内容的方法
//void bubbleSortByScore(PNode L){
// for(int i=0;i<L->len;i++){
// PNode p=L->next;
// int switched=0;
// for(int j=0;j<(L->len-i-1);j++){
// if(p->stu.score > p->next->stu.score){
// //交换
// Stu temp=p->stu;
// p->stu = p->next->stu;
// p->next->stu=temp;
// switched=1;
// }
// p=p->next;
// }
// if(!switched){
// return;//已经是有序的了
// }
// }
//}// 法二：更改指针指向的方法
void bubbleSortByScore(PNode L){for(int i=0;i<L->len;i++){PNode p=L->next;PNode pre=L;int switched=0;for(int j=0;j<L->len-i-1;j++){PNode q=p->next;if(p->stu.score > q->stu.score){p->next=q->next;q->next=p;pre->next=q;//pre=q;switched=1;continue;}pre=p;p=p->next;}if(!switched)return;}
}void destroyLink(PNode L){//TODO 异常判断int cnt=0; PNode p=L;while(p){L = p;free(L);L=NULL;p=p->next;cnt++;}printf("总共执行了[%d]次free操作\n", cnt);}link.c
#ifndef _LINK_H_
#define _LINK_H_#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef struct{int id;char name[100];int score;
}Stu, *PStu;typedef struct n{union{Stu stu;int len;};struct n *next;
}Node, *PNode;Stu createStu(int id, char* name, int score);
void printStu(Stu s);PNode createLink();
void insertHead(PNode L, Stu stu);
void printLink(PNode L);
void insertStu(PNode L, int pos, Stu stu);
void deleteStu(PNode L, int pos);
void reverseLink(PNode L);
void bubbleSortByScore(PNode L);
void destroyLink(PNode L);#endif运行结果：
链表创建成功.
>>链表长度为[9]
id=[9],name=[ggg],score=[4]
id=[8],name=[iii],score=[5]
id=[7],name=[hhh],score=[1]
id=[6],name=[fff],score=[3]
id=[5],name=[eee],score=[9]
id=[4],name=[ddd],score=[1]
id=[3],name=[ccc],score=[9]
id=[2],name=[bbb],score=[3]
id=[1],name=[aaa],score=[5]
>>任意位置插入一名学生信息
>>链表长度为[10]
id=[9],name=[ggg],score=[4]
id=[8],name=[iii],score=[5]
id=[7],name=[hhh],score=[1]
id=[6],name=[fff],score=[3]
id=[5],name=[eee],score=[9]
id=[50],name=[zzz],score=[100]
id=[4],name=[ddd],score=[1]
id=[3],name=[ccc],score=[9]
id=[2],name=[bbb],score=[3]
id=[1],name=[aaa],score=[5]
>>任意位置删除一名学生信息
>>链表长度为[9]
id=[9],name=[ggg],score=[4]
id=[8],name=[iii],score=[5]
id=[7],name=[hhh],score=[1]
id=[6],name=[fff],score=[3]
id=[5],name=[eee],score=[9]
id=[4],name=[ddd],score=[1]
id=[3],name=[ccc],score=[9]
id=[2],name=[bbb],score=[3]
id=[1],name=[aaa],score=[5]
>>单链表逆置
>>链表长度为[9]
id=[1],name=[aaa],score=[5]
id=[2],name=[bbb],score=[3]
id=[3],name=[ccc],score=[9]
id=[4],name=[ddd],score=[1]
id=[5],name=[eee],score=[9]
id=[6],name=[fff],score=[3]
id=[7],name=[hhh],score=[1]
id=[8],name=[iii],score=[5]
id=[9],name=[ggg],score=[4]
>>根据成绩进行冒泡排序
>>链表长度为[9]
id=[4],name=[ddd],score=[1]
id=[7],name=[hhh],score=[1]
id=[2],name=[bbb],score=[3]
id=[6],name=[fff],score=[3]
id=[9],name=[ggg],score=[4]
id=[1],name=[aaa],score=[5]
id=[8],name=[iii],score=[5]
id=[3],name=[ccc],score=[9]
id=[5],name=[eee],score=[9]
总共执行了[10]次free操作