C课件C语言链表应用

链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 应用 目标 · 熟练掌握单链表遍历 · 掌握单链表排序 · 掌握单链表查找 · 熟练掌握单链表删除 · 理解栈的定义及实现 单链表遍历2-1 · 计算单链表的长度： int GetLength() { struct student *temp=head; int len=0; while(temp!=NULL) { len++; temp=temp->next; } return len; } //也可以定义一个全局变量，每增加一个结点就加1 单链表遍历2-2 · 单链表的打印操作： void PrintAllStudent(){ struct student *temp=head; int count = 0; if(head == NULL){ printf(“nothing”);return;} while(temp != NULL){ printf(“%d:%s,%s,%d,%d,%d,%d,%d,%d\n”,count++, temp->info.sno,temp->info.sname, temp->info.age, temp->info.score[0], temp->info.score[1], temp->info.score[2], temp->info.score[3], temp->info.score[4]); temp = temp->next; } } 单链表排序 · 因单链表每一结点都有一数据域和指针域，所以排序操作可对数据域排序，也可对指针域排序 · 数据域排序 · 指针域排序 单链表的数据域排序 void OrderBySnoAsc(){ /* 以学号按升序排序 */ struct student *p,*q,*min; struct studentData temp; /* 交换时用到的临时变量 */ for( p = head;p != NULL; p = p->next ){ min = p; for( q = p->next;q != NULL;q = q->next) if(strcmp( min->info.sno, q->info.sno ) > 0) min = q; if( min != p ){ temp=min->info; min->info =p->info; p->info=temp; } } } 单链表查找 struct student *SearchStudent(char key[],struct Student **preNode){ struct student *temp; if(head == NULL){ return NULL; } *preNode = temp = head; while(temp != NULL){ if(strcmp(temp->info.sno,key) == 0) break; *preNode = temp; /* 向下移动时，保存当前结点的地址 */ temp = temp->next; } return temp; } 单链表删除2-1 单个结点的删除： bool DeleteOneStudent(char key[]){ //该函数删除第index个结点 struct student *preNode,*delNode; delNode=SearchStudent(key,&preNode); if(delNode!= NULL){ if(delNode==head) { head=head->next; //删除头结点} else { preNode ->next=delNode->next;} delete delNode; //释放节点空间 return true; } else return false; } /* 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：是否需要考虑删除尾结点的情况？ */ 单链表删除2-2 · 整个链表的删除： void DeleteAll(){ struct Student *temp = head,preNode = head; while(temp != NULL){ preNode = temp; temp = temp->next; delete preNode; } head = NULL; } 栈的概念 · 栈是一种特殊的线性表，这种表只在表头进行插入和删除操作 · 表头对于栈来说具有特殊的意义，称为栈顶；相应地，表尾称为栈底 · 不含任何元素的栈称为空栈 · 栈的元素操作是按后进先出的原则进行的，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈 栈的操作 · 初始化栈 · 判断是否为空栈 · 入栈 · 出栈 · 取栈顶元素 · 求栈大小 · 清空栈 栈的实现 · 可以用顺序存储或链式结构实现栈 · 链式结构实现栈结点定义 struct Node { int data; struct Node *next; }; · 如上定义，可以初始化一个栈： struct node *stack = NULL; 栈操作-入栈 struct Node *PushData(struct Node **stack,int data) { struct Node *p; p = (struct Node *)malloc(sizeof(struct Node)); if(p == NULL) { return NULL; } p->data = data; p->next = *stack; *stack = p; return p; } 栈操作-出栈及栈空判定 int PopupData(struct Node **stack) { struct Node * temp = *stack; int data; (*stack) = (*stack)->next; data = temp->data; free(temp); return data; } int IsEmpty(struct Node *stack) { return stack == NULL; } 栈操作-求栈大小 int GetStackLenght(struct Node *stack) { int len = 0; struct Node *temp = stack; while(temp!=NULL) { len ++; temp = temp->next; } return len; } 栈操作-清空栈 void ClearStack(struct Node *stack) { struct Node *temp; while(stack!=NULL)//即线性表中删除所有结点的操作 { temp = stack; stack = stack->next; free(temp); } } 栈应用-数的二进制表示法 void PrintBinaryString(int n){ struct Node *stack = NULL; int temp = n; while(temp!=0){ PushData(&stack,temp%2); temp/=2; } printf("\n%d binary mode is (",n); while(!IsEmpty(stack)){ printf("%2d ",PopupData(&stack)); } printf(")"); } 总结 · 单链表遍历 · 单链表排序 · 单链表查找 · 单链表删除 · 栈的实现及应用