专题一：常用数据结构及其程序设计

程序设计基础——C语言1[主要内容]•线性表•栈和队列•二叉树专题一常用数据结构及其程序设计程序设计基础——C语言2线性表•线性表的定义和运算•顺序表•链表程序设计基础——C语言3线性表的定义•一个线性表是n个数据元素的有限序列。A，B，C，D，E，……，Z学号姓名高数数据结构C语言2004618501王明启8584922004618502陈平9245642004618503张建功8774732004618504刘立678377...程序设计基础——C语言4线性表的运算•插入：在两个确定元素之间插入一个新元素。•删除：删除线性表中某个元素。•查找：按某种要求查找线性表中的一个元素，需要时可以进行更新。•排序：按给定要求对表中元素重新排序。程序设计基础——C语言5顺序表的定义•顺序表：线性表的数据元素用一组地址连续的存储单元依次存储。#defineMAXSIZE100typedefintElemtype;typedefstructsequenctial_listLIST;structsequenctial_list/*定义顺序表类型*/{Elemtypeelem[MAXSIZE];/*数组域Elemtype表示数据类型,如int*/intlen;/*存放表长度*/};LISTlist;/*定义顺序表list*/例如，可以把数组和线性表的长度放在一个结构体中：程序设计基础——C语言6顺序表的基本操作•顺序表的创建例7.1建立顺序表函数voidcreate(){inti;printf(请输入线性表元素个数：);scanf(%d,&n);printf(请输入线性表元素值：);for(i=0;in;i++)scanf(%d,&list.elem[i]);list.len=n;}程序设计基础——C语言7•顺序表元素的插入插入操作是指在顺序表的第i－1个数据元素和第i个数据元素之间插入一个新的数据元素x，使长度为ｎ的顺序表（A0,…,Ai-1,Ai,…,An-1）变成长度为n+1的顺序表（A0,…,Ai-1,x,Ai,…,An-1）。插入操作应先把元素Ai,…,An-1向后各自移动一个位置，然后将x插在第i个位置上。顺序表的基本操作程序设计基础——C语言8例7.2顺序表插入元素函数voidinsert_data(inti,Elemtypex){intj;if((i0)||(ilist.len))printf(插入位置出错！);else{for(j=list.len-1;j=i;j--)list.elem[j+1]=list.elem[j];list.elem[i]=x;list.len=list.len+1;}}顺序表的基本操作程序设计基础——C语言9•顺序表元素的删除和插入操作类似,要删除顺序表中的第i个元素Ai。只要把元素Ai+1,…,An-1分别向前移动一个位置，使长度为ｎ的顺序表（A0,…,Ai-1,Ai,…,An-1）变成长度为n-1的顺序表（A0,…,Ai-1,Ai+1,…,An-1）即可。顺序表的基本操作程序设计基础——C语言10例7.3顺序表删除元素函数voiddelete_data(inti){intj;if((i0)||(ilist.len-1))printf(Notexistelse{for(j=i+1;j=list.len-1;j++)list.elem[j-1]=list.elem[j];list.len--;}}顺序表的基本操作程序设计基础——C语言11链表的定义•单链表：线性表的数据元素存储在任意物理位置的存储单元中，通过指针链接保证其逻辑上相邻。12509910167128012809910286131213129910474289528959910598NULL1250head程序设计基础——C语言12•链表结点可以由结构体类型定义。表示学生信息（学号、成绩）的单链表类型定义为：#defineN6/*学号长度*/#defineNULL0#defineLENsizeof(NODE)/*定义结点长度*/typedefstructstudent{charnum[N];/*学号*/floatscore;/*成绩*/structstudent*next;/*同结构体的指针*/}NODE;NODE*head;/*定义一个头指针变量*/链表的定义程序设计基础——C语言13•链表的存储分配在建立链表结构时，需要动态分配内存单元，即需要存储数据时才开辟一个结点的存储单元。那么如何在程序中实现存储单元的动态分配，建立以上链表呢？C语言提供了内存管理函数malloc()、calloc()和free()函数，它们包含在malloc.h或stdlib.h头文件中。链表的定义程序设计基础——C语言14链表的基本操作•链表的建立例7.4编写一个create()函数，创建一个存储学生信息（学号、成绩）的单链表（链表中的结点个数不限）。以输入学号“*”作为结束建立链表的标志。程序设计基础——C语言15链表的基本操作•链表的建立•head──头指针变量，指向链表的第一个结点，用作函数返回值。•newnode──指向新申请的结点。•tail──指向链表的尾结点，用tail-next=new，实现将新申请的结点，插入到链表尾，使之成为新的尾结点。基本思路：首先向系统申请一个结点的空间，然后输入结点数据域的（2个）数据项，并将指针域置为空（链尾标志），最后将新结点插入到链表尾。我们设置3个指针变量分别是：程序设计基础——C语言16链表的基本操作•链表的建立NODE*create(void){NODE*newnode,*tail;head=NULL;while(1){newnode=(NODE*)malloc(LEN);printf(请输入学号(5位字符,退出请输'*'):);scanf(%5s,newnode-num);if(strcmp(newnode-num,*)==0){free(newnode);break;}printf(请输入成绩:);scanf(%f,&newnode-score);if(head==NULL)head=newnode;elsetail-next=newnode;tail=newnode;}tail-next=NULL;return(head);}程序设计基础——C语言17•链表的输出当链表的头指针为NULL时说明是空链表，不输出。只有当链表非空时才从链表头部开始，将一个指针指向头部（p=head;）,然后往后移动记录指针（p=p-next;），输出结点数据，重复操作，直到链空。链表的基本操作程序设计基础——C语言18链表的基本操作•链表的建立voidprintlist(structstudent*head){structstudent*p;p=head;if(head==NULL){printf(Listisempty!\n);else{while(p!=NULL){printf(%5s%4.1f\n,p-no,p-score);p=p-next;}}}程序设计基础——C语言19•链表的插入b)结点插在表头aheadnewxbc^new-next=head;head=new;headnewx^a)空表插入head=new;new.next=NULL;pointeraheadnewxbc^pointer-next=new;new-next=pointer-next;c)结点插在任意位置（包括表尾）链表的基本操作程序设计基础——C语言20•例7.6编写一个insert()函数，完成在单链表的第i个结点后插入一个新结点的操作。当i=0时，表示新结点插入到第一个结点之前，成为链表新的首结点。基本思路：通过单链表的头指针，首先找到链表的第一个结点；然后顺着结点的指针域找到第i个结点，最后将新结点插入到第i个结点之后。链表的基本操作程序设计基础——C语言21链表的基本操作•链表的建立NODE*insert(NODE*head,NODE*newnode,inti){NODE*pointer;/*将新结点插入到链表中*/if(head==NULL)/*空链表*/{head=newnode;newnode-next=NULL;}else/*非空链表*/if(i==0)/*头结点插入*/{newnode-next=head;head=newnode;}else/*其他位置*/{pointer=head;for(;pointer!=NULL&&i1;pointer=pointer-next,i--);if(pointer==NULL)/*越界错*/printf(越界,不能插入新的结点!\n);else/*一般情况：pointer指向第i个结点*/{newnode-next=pointer-next;pointer-next=newnode;}}return(head);}程序设计基础——C语言22•链表的删除a)删除的是头结点frontaheadbc^front=head;head=head-next;cursorfrontaheadbc^front-next=cursor-next;b)删除的是其它结点（含表尾）链表的基本操作程序设计基础——C语言23链表的基本操作•链表的建立NODE*dellist(NODE*head,charnum[]){NODE*front;/*front表示要删除结点的前一结点*/NODE*cursor;/*cursor表示当前要删除结点*/if(head==NULL)/*空链表*/{printf(\n链表为空\n);return(head);}if(strcmp(head-num,num)==0){front=head;head=head-next;free(front);}else/*非表头结点*/{front=head;cursor=head-next;while(cursor!=NULL&&strcmp(cursor-num,num)!=0){front=cursor;cursor=cursor-next;}if(cursor!=NULL)/*表示找到了，进行删除操作*/{front-next=cursor-next;free(front);}else/*未找到时，显示未找到信息*/printf(%5s未找到!\n,*num);}return(head);}程序设计基础——C语言24栈和队列•栈的定义•栈的基本操作•队列的定义•顺序队列的基本操作程序设计基础——C语言25栈的定义•栈是限定仅在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。不含元素的空表称为空栈。顺序栈的类型定义如下：#defineMAXSIZE100typedefstructseqstackSEQSTACK;structseqstack{Elemtypedata[MAXSIZE];inttop;};定义一个指向顺序栈的指针：SEQSTACK*s;程序设计基础——C语言26栈的基本操作•例7.7建栈操作函数SEQSTACK*init_seqstack(){SEQSTACK*s;s=(SEQSTACK*)malloc(sizeof(SEQSTACK));s-top=0;returns;}程序设计基础——C语言27•例7.8入栈函数将数据元素x压入到栈s中，操作成功，返回1,否则为0。intpush_seqstack(SEQSTACK*s,Elemtypex){if(full_seqstack(s)){printf(“栈已满，入栈操作失败!”);return0;}else{s-data[s-top]=x;s-top++;return1;}}栈的基本操作程序设计基础——C语言28•例7.9定义一个检查栈是否满的函数，当栈s满时返回1，否则返回0数intfull_seqstack(SEQSTACK*s)