【课堂回顾】数据结构之单链表

3/8/2017来源:ASP.NET技巧人气:315

敲代码三分钟,debeg三小时系列

实现了单链表的初始化,新建(头插法/尾插法),求表长,查找(按值查找/按位置查找),删除,插入,销毁,打印单链表。

第一次,纯手工写了个数据结构中的最简单的单链表一般操作。 最让我收获的是,我c语言字符串这一块学的真差。 (课堂上老师的结构体中数据类型,全部都用了int,大大减少了一些语法细节。)

字符串数组的数组名是一个常量指针,字符串复制首选strcpy_s; 字符串数组的数组名是一个常量指针,字符串复制首选strcpy_s; 字符串数组的数组名是一个常量指针,字符串复制首选strcpy_s;

//单链表的初始化,新建(头插法/尾插法),求表长,查找(按值查找/按位置查找),删除,插入,销毁,打印单链表 #include<stdio.h> #include<string.h> #include<stdlib.h> #define _SCL_SECURE_NO_WARNINGS typedef struct node { char name[5],*pname; struct node *next; } Lnode, *LinkList; //初始化带头结点的单链表 LinkList creat_LinkList(void) { LinkList H; H = (LinkList)malloc(sizeof(Lnode)); if (H) { H->next = NULL; PRintf("初始化成功!!!"); } else { printf("链表初始化失败"); } return H; } //尾插法新建带头结点的单链表 LinkList end_Build_LinkList(LinkList H, int length) { LinkList p, r; p = H; for (int i = 1; i <= length-1; i++) { //循环内的语句顺序不能交换 r = p; p = (LinkList)malloc(sizeof(Lnode)); scanf_s("%s", p->name, 5); r->next = p; } p->next = NULL; return H; } //头插法新建带头节点的单链表 LinkList head_Build_LinkList(LinkList H, int length) { LinkList q; for (int j = 1; j <= length; j++) { q = (LinkList)malloc(sizeof(Lnode)); q->next = H->next; scanf_s("%s", q->name,5); H->next = q; } return H; } //求表长(包括头结点) int count_LinkList(LinkList H) { int count = 1; LinkList l; l = H->next;//指向头结点的下一个结点 while (l->next != NULL) { count++; l = l->next; } return ++count; //修正while中没有算上最后一个结点 } //按值查找(查找首次出现的值) LinkList value_Location_LinkList(LinkList H,char* name) { int i = 1; LinkList search; search = H->next; while (search->next != NULL) { if (strcmp(search->name,name) == 0) { printf("FIND"); return search; } else { search = search->next; } } if (strcmp(search->name, name) == 0) { printf("FIND");//修正while循环中没有遍历到的尾结点 return search; } return NULL; } ////按位置查找 LinkList position_Location_LinkList(LinkList H, int position) { int place = 1; LinkList search; search = H->next; while (search->next != NULL && place<position) { search = search->next; place++; } if (!search->next) { printf("链表中不存在或者不存在这个位置"); } else { if (place > position) { printf("查找的位置是不合理的"); } else { if (place == position) { printf("FIND"); return search; } } } return NULL; } //删除单链表中的某结点(按指定位置删除) LinkList position_Delete_LinkList(LinkList H, int location) { LinkList before = position_Location_LinkList(H, location - 1); LinkList current = position_Location_LinkList(H, location); before->next = current->next; free(current); return H; } ////删除单链表中的某结点(按指定值删除且该指定值是再该链表中第一次出现) LinkList value_delete_linklist(LinkList H, char *name) { LinkList x, y; x = y = (LinkList)malloc(sizeof(Lnode)); y = H; x = H->next; while (x->next != NULL) { if (strcmp(x->name, name) == 0) { y->next = x->next; free(x); return H; } else { y = x; x = x->next; } } if(strcmp(x->name, name) == 0) {//修正while循环中未遍历到尾结点 y->next = x->next; free(x); return H; } return NULL; } //插入(只讨论按位置插入) LinkList insert_LinkList(LinkList H, int position, char* name) { LinkList node; node = (LinkList)malloc(sizeof(Lnode)); strcpy_s(node->name,6,name); LinkList f = position_Location_LinkList(H, position-1); node->next =f->next; f->next = node; return H; } //销毁链表 void destroy_LinkList(LinkList H) { LinkList des, troy; des = H->next; while(des->next!=NULL) { troy = des; des = des->next; free(troy); } free(des);//销毁尾结点 free(H);//销毁头结点 } void print_LinkList(LinkList H) {//length为包括头结点的表长 while(H->next!=NULL) {//头结点中的数据域为空,所以不需要i<=length H = H->next; printf("%s ", H->name); } } int main(void) { int length = 5;//不包括头节点 LinkList H = creat_LinkList(); //H = end_Build_LinkList(H, length); H=head_Build_LinkList(H, length); //int count_length = count_LinkList(H);//在这里,头结点也算在表长中 //printf("%d", count_length); //LinkList search=value_Location_LinkList(H, "chen"); //LinkList position=position_Location_LinkList(H,3); //printf("%s", position->name); //H=position_Delete_LinkList(H, 3); //H = value_delete_linklist(H, "dong"); print_LinkList(H, 6); printf("\n"); insert_LinkList(H,3, "dong"); print_LinkList(H); destroy_LinkList(H); return 0; }

有空再来弄下健壮性~