链表的增删改查的操作数据结构和算法

看来几篇博客，自己还没有实践

#include #include #define LEN sizeof(struct student)/*----------------数据定义----------------------*/ //定义一个学生信息的结构体,包括学号,姓名和结构体类型的指针 struct student { long num; //学号 char name[128]; //姓名 struct student *next; //结构体指针 }; typedef struct student * stuNode; int n=0; //全局变量,记录链表的长度 /*---------------函数声明---------------------*/ stuNode Create(); //创建一个新的链表void Print(stuNode head); //通过传入的链表头指针打印整个链表 stuNode Delete(stuNode head,int num); //通过传入的链表头指针和学生学号删除节点 stuNode Insert(stuNode head,stuNode newStu); //依照学生学号的顺序向链表中插入新元素 /*---------------函数定义----------------------*/struct student *Create() { struct student *head,*p1,*p2; //开辟一个LEN大小的空间,并让p1,p2指针指向它 p2=p1=(struct student *)malloc(LEN); //将头指针置为NULL head=NULL; //创建链表节点并给节点的元素赋值 printf("请输入学生的学号和姓名:"); scanf("%ld %s",&p1->num,p1->name); while(p1->num!=0) { n=n+1; if(NULL==head) { head=p1; } else { p2->next=p1; } p2=p1; p1=(struct student *)malloc(LEN); printf("请输入学生的学号和姓名:"); scanf("%ld %s",&p1->num,p1->name); } //将尾节点的指针置为NULL p2->next=NULL; return head; }void Print(struct student *head) { struct student * p; p=head; //判断链表是否为空 if(NULL==head) { printf("链表为空!\n"); return head; } else { //循环打印链表中的元素 printf("%d 个记录分别为:\n",n); while(p!=NULL) { printf("%ld %s\n",p->num,p->name); //指针指向下一个节点 p=p->next; } } }struct student *Delete(struct student * head,int num) { struct student *p1; struct student *p2; p1=head; //判断链表是否为空 if(NULL==head) { printf("链表为空!\n"); return head; } //遍历节点,判断当前节点是不是需要删除的节点及是否为尾节点 //如果找到相应节点,或者已经遍历到尾节点就跳出循环 while(p1->num!=num&&p1->next!=NULL) { p2=p1; p1=p1->next; } //判断是否找到相应节点 if(p1->num==num) { //要删除的节点是不是链表的第一个节点 //如果是,就将头指针指向该节点的后一个节点 //如果不是,就将该节点的前一个节点的指针指向该节点的后一个节点 if(head==p1) { head=p1->next; } else { p2->next=p1->next; } n=n-1; printf("%ld 节点已删除.\n",num); } else { printf("链表中没有要删除的元素.\n"); } return head; }struct student *Insert(struct student * head,struct student * newStu) { struct student *p0; struct student *p1; struct student *p2; p0=newStu; p1=head; //判断链表是否为空,如果是空链表,就将新节点作为第一个节点 if(NULL==head) { head=p0; p0->next=NULL; } else { //遍历每一个节点中的学号,与新学号比较大小 //如果找到一个学号比新学号大,就将新学号的节点插入它之前 //如果尾节点的学号仍比新学号小,就将新节点插入到链表尾部 while((p0->num > p1->num)&&(p1->next!=NULL)) { p2=p1; p1=p1->next; } //找到一个比新学号大的节点 if(p0->num <= p1->num) { //判断该节点是否为头节点,如果是,则将新节点设置为头节点 if(p1==head) { head=p0; } else { p2->next=p0; } p0->next=p1; } else { p1->next=p0; p0->next=NULL; } } //链表长度加1 n=n+1; printf("%ld 插入成功!\n",newStu->num); return head; }void main() { struct student *head; struct student *stu; int num; head=Create(); Print(head); printf("请输入要删除的学号:"); scanf("%ld",&num); while(num!=0) { head=Delete(head,num); Print(head); printf("请输入要删除的学号:"); scanf("%ld",&num); } printf("请输入要插入的节点:"); stu=(struct student *)malloc(LEN); scanf("%ld %s",&stu->num,stu->name); while(stu->num!=0) { head=Insert(head,stu); printf("请输入要插入的节点:"); stu=(struct student *)malloc(LEN); scanf("%ld %s",&stu->num,stu->name); } Print(head); }

　参考：

#include #include #define LEN sizeof(struct student) struct student{ int num; double score; struct student *next; }; //创建一个链表 struct student * create(void){ struct student *p1,*p2,*head; int n = 0; p1 = p2 = (struct student *)malloc(LEN); scanf("%d%lf",&(p1->num),&(p1->score)); while(p1->num!=0){ n++; if(n==1){ head = p1; }else{ p2 = p1; } p1 = (struct student *)malloc(LEN); scanf("%d%lf",&(p1->num),&(p1->score)); p2->next = p1; }p2->next = NULL; return head; } struct student *delw(struct student *start,int num){ struct student *p1,*p2; //链表为空 if(start==NULL){ printf("\nlist null!\n"); return NULL; } p1 = start; p2 = NULL; //链表不为空 //链表只有一个元素，且即为所要找的元素 /*if(p1->next==NULL&&p1->num == num){ printf("there is only one element and that is it!"); return NULL; }*/ while(p1->next!=NULL&&p1->num!=num){ p2 = p1; p1 = p1->next; }if(num == p1->num){ if(p1 == start){ return start->next; }else{ p2->next = p1->next; } }else{ printf("number not found!"); }return start; } struct student *del(struct student *head,long num){ struct student *p1, *p2; //链表为空 if(head == NULL){ printf("\nlist null!\n"); return head; } //链表不为空 p1 = head; while(p1->next!=NULL&&num!=p1->num){ p2 = p1; p1 = p1->next; } if(num == p1->num){ if(p1 == head){ head = p1->next; }else{ p2->next = p1->next; printf("delete:%ld\n",num); } }else printf("%ld not been found!\n",num); return head; } //删除一个节点 struct student * deleteNode(struct student *start,int num){ struct student *p1, *p2,*before,*after; //空表 if(start==NULL){ printf("the linktable is null"); return NULL; } p1 = p2 = start; //只有一个节点 if(start->next==NULL){ if(start->num==num){ return NULL; } } //链表不为空(两个以上的节点) //1:链表的第一个即为所要找的 if((start->num == num)&&(start->next!=NULL)){ return start->next; } while(p1!=NULL){ if(p1->num==num){ before = p2; after = p1->next; } p2 = p1; p1 = p1->next; } before->next = after; return start; } struct student * insert(struct student *head,struct student *stu){ struct student *p1,*p2, *p0; p1 = head; p0 = stu; //链表为空 if(head == NULL){ head = p0; p0->next = NULL; printf("the link is null\n"); return NULL; //链表不为空，比较num，（如22， 33， 55），44应插入至33后面 }else{ //一个元素 //printf("head.next is not null"); //两个以上元素: 22 55 88 while(p1->numnum&&p1->next!=NULL){ p2 = p1; p1 = p1->next; } if(p1->num>p0->num){// if(p1==head){//p0排到最前 head = p0; p0->next = p1; }else{ //p0排到中间 p2->next = p0; p0->next = p1; } }else{//p0排到最后 p1->next = p0; p0->next = NULL; } return head; } } void printLink(struct student *p){ struct student *p_afterDeal = p; p_afterDeal = p; while(p_afterDeal!=NULL){ printf("num = %d, score = %lf\n",p_afterDeal->num,p_afterDeal->score); p_afterDeal = p_afterDeal->next; } } int main(void){struct student * p_std, * p_afterDel,*p,*p_afterInsert; struct student newstd = {44,44.4,NULL}; //创建一个链表 printf("创建一个链表：\n"); p_std = create(); printf("创建的链表如下：\n"); printLink(p_std); //插入一个节点 printf("插入一个节点：44\n"); p = &newstd; p_afterInsert = insert(p_std,p); printf("插入一个节点后的列表如下：\n"); printLink(p_afterInsert); //删除一个节点 printf("删除一个节点：44\n"); p_afterDel = deleteNode(p_afterInsert,44); printf("删除一个节点后的列表如下：\n"); printLink(p_afterDel); system("pause"); }

/** *C语言实现，用了三个指针操作，没用构造函数 */ #include using namespace std; struct student { int data; struct student* next; }; int main() { int data; struct student *head,*tail,*temp; head = NULL; while(cin>>data && data!=-1) { temp = (struct student*)malloc(sizeof(struct student)); temp->data = https://www.it610.com/article/data; temp->next = NULL; if(head==NULL) { head = temp; tail = head; } else { tail->next = temp; tail = temp; } }tail = head; while(tail!=NULL) { cout<data<next; } system("pause"); return 0; }/** *C/C++实现，用了三个指针操作，用了构造函数 */ #include using namespace std; struct student { int data; struct student* next; student(int a) { this->data = https://www.it610.com/article/a; this->next = NULL; } }; int main() { int data; struct student *head,*tail,*temp; head = NULL; while(cin>>data && data!=-1) { if(head==NULL) { head = new student(data); tail = head; } else { temp = new student(data); //temp用来接收新节点，这样tail的next不会丢失 tail->next = temp; tail = temp; } }tail = head; while(tail!=NULL) { cout<data<next; } system("pause"); return 0; }/** *C/C++实现，用了两个指针操作，用了构造函数 */ #include using namespace std; struct student { int data; struct student* next; student(int a) { this->data = https://www.it610.com/article/a; this->next = NULL; } student(int a, struct student* p) { p->next = this; this->data = https://www.it610.com/article/a; this->next = NULL; } }; int main() { int data; struct student *head,*tail; head = NULL; while(cin>>data && data!=-1) { if(head==NULL) { head = new student(data); tail = head; } else { tail = new student(data, tail); } }tail = head; while(tail != NULL) { cout<data<next; } system("pause"); return 0; }

参考：http://www.cnblogs.com/yanghuahui/archive/2012/04/15/2451076.html
http://www.cnblogs.com/ligang305/archive/2012/08/25/2656343.html
http://www.cnblogs.com/wolfred7464/p/4335298.html
【链表的增删改查的操作】http://www.cnblogs.com/xnwyd/archive/2010/04/28/1723151.html