数据结构(C语言版)期末复习汇总第一章绪论数据结构:是一门研究非数值计算程序设计中的操作对象,以及这些对象之间的关系和操作的学科。
数据结构分为:逻辑结构、物理结构、操作三部分逻辑结构:集合、线性结构、树形结构、图(网)状结构物理结构(存储结构):顺序存储结构、链式存储结构算法:是为了解决某类问题而规定的一个有限长的操作序列。
算法五个特性:有穷性、确定性、可行性、输入、输出评价算法优劣的基本标准(4个):正确性、可读性、健壮性、高效性及低存储量语句频度的计算。
算法的时间复杂度:常见有:O(1),O(n),O(n2),O(log2n),O(nlog2n),O(2n)第二章线性表线性表的定义和特点:线性表:由n(n≥0)个数据特性相同的元素构成的有限序列。
线性表中元素个数n(n≥0)定义为线性表的长度,n=0时称为空表。
非空线性表或线性结构,其特点:(1)存在唯一的一个被称作“第一个”的数据元素;(2)存在唯一的一个被称作“最有一个”的数据元素;(3)除第一个之外,结构中的每个数据元素均只有一个前驱;(4)除最后一个之外,结构中的每个数据元素均只有一个后继。
顺序表的插入:共计n个元素,在第i位插入,应移动(n-i+1)位元素。
顺序表的删除:共计n个元素,删除第i位,应移动(n-i)位元素。
线性表的两种存储方式:顺序存储、链式存储。
顺序存储概念:以一组连续的存储空间存放线性表;优点:逻辑相邻,物理相邻;可随机存取任一元素;存储空间使用紧凑;缺点:插入、删除操作需要移动大量的元素;预先分配空间需按最大空间分配,利用不充分;表容量难以扩充;操作:查找、插入、删除等查找:ListSearch(SqlList L,ElemType x,int n){int i;for (i=0;i<n;i++){if(x==L .elem[i]) break; }if(i==n) return(0);elsereturn(i+1);}//ListSearch删除:ListDelete(SqlList &L,int i,ElemType &e){if (i<1||i>L.length)return ERROR; //i值不合法p=&(L.elem[i-1]); //p为被删除元素的位置e=*p; //被删除元素的值赋给eq=L.elem+L.length-1 //表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p; //被删除元素之后的元素左移--L.length; //表长减1return e;}//ListDelete插入:ListInsert(SqlList &L, int i, ElemType e){ if (i<1||i>L.length+1)return ERROR; //i值不合法。
if (L.length>=Listsize) //当前存储空间已满,增加分配{ newbase=(ElemType*)realloc(L.elem,(L.Listsize+LISTINCREMENT)*sizeof(ElemType));//realloc(void * p,unsigned size)该函数将p所指出的已分配内存区的大小改为size, size可以比原来分配的空间大或小//If (!newbase) exit(OVERFLOW); //存储分配失败L.elem=newbase; //新基址L.Listsize+=LISTINCREMENT; );//增加存储容量}q=&(L.elem[i-1]); //q为插入位置for(p=&L. elem[L.length-1];p>=q;- - p) *(p+1)=*p; //插入位置之后的元素右移*q=e; //插入e++L.length; //表长增加1return OK;}//ListInsert单链表——线性表的链式存储结构之一概念:线性链表又称单链表,结点:数据域,指针域;头指针,头结点。
单链表特点:用指针表示数据之间的逻辑关系(逻辑相邻的元素物理位置不一定相邻)。
它是一种动态结构,不需预先分配空间;不足:指针占用额外存储空间;不能随机存取,查找速度慢。
节点定义:“数据+ 指针”typedef struct LNode { DataType data; struct LNode *next; } LNode, *LinkList;单链表的插入:元素x 结点应预先生成: S=(test*)malloc(m); S->data=x;S->next=p->next p->next=s 单链表删除:q = p->next; //保存b 的指针,靠它才能指向c p->next=q->next; //a 、c 两结点相连free(q) ; //删除b 结点,彻底释放线性表的应用:(1):用单链表结构存放26个英文字母组成的线性表(a ,b ,c ,…,z ),请写出C 语言程序。
#include<stdio.h> #include<stdlib.h>/*将全局变量及函数提前说明:*/ typedef struct liu{ char data;struct liu *next; }test;test *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数int m=sizeof(test); /*结构类型定义好之后,每个变量的长度就固定了,m 求一次即可*/void build( ) //字母链表的生成。
要一个一个链入 {int i;p=(test*)malloc(m); //m=sizeof(test) 前面已求出head =p; //头指针,没有头结点 for(i=1;i<26;i++)//因尾结点要特殊处理,故i≠26 {p->data=i+‘a’-1; // 第一个结点值为字符ap->next=(test*)malloc(m); //为后继结点开新空间!p=p->next;//让指针变量P改为指向后继结点}p->data=i+‘a’-1; //最后一个元素要单独处理p->next=NULL ; //单链表尾结点的指针域要置空!}void display()/*字母链表的输出*/{ p=head;while (p) /* 只要没到最后一个元素,就不停地“顺藤摸瓜”输出*/{ printf("%c",p->data);p=p->next;}}(2)线性表的合并:(顺序储存结构)算法2.1:LA=(7,5,3,11) LB=(2,6,3)合并后LA=(7,5,3,11,2,6)算法思想:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。
只要从线性表LB中依次取得每个数据元素,并依值在线性表LA中进行查访,若不存在,则插入之。
void union(List &LA, List &LB)//主函数,参数为两个线性表{La_len = ListLength(LA); // 求得线性表LA 的长度while (!ListEmpty(LB)) // 依次处理LB 中元素直至LB 为空表止{ListDelete(LB,1,e); // 从LB 中删除第1个数据元素并赋给eif (!LocateElem(LA,e,equal( ))ListInsert(LA,++La_len,e);// 当LA中不存在和 e 值相同的数据元素时进行插入} //DestroyList(LB);// 销毁线性表LB} // union第三章栈和队列栈的类型定义:栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。
当表中没有元素时称为空栈。
假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。
栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。
即,栈的修改是按后进先出的原则进行的。
因此,栈称为后进先出表(LIFO)。
栈的进栈(push)操作:Status Push(Stack &S, SElemType e){//插入元素e为新的栈顶元素if (S.top-S.bottom>=S.stacksize){//栈满,追加存储空间S.bottom=(SElemType)realloc(S.bottom,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if (!S.bottom) exit(overflow); //存储分配失败S.top=S.bottom+S.stacksize; //设置新栈的栈顶S.stacksize+=STACKINCREMENT;} //设置新栈的大小*S.top++=e; //先赋值,后加1Return OK;}//Push出栈(pop)操作:Status Pop(Stack &S, SElemType &e){//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERRORif (S.top==S.bottom) Return ERROR;S.top-- ; e=*S. top ;Return OK;}//Pop进栈、出栈顺序:对于一个栈,给出输入项A、B、C,如果输入项序列由ABC组成,试给出所有可能的输出序列。
A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB栈的应用:数值转换算法思想:首先将按照上述计算过程中得到的八进制数的各位依次进栈,然后将栈中的八进制数依次出栈输出,输出结果就是该是十进制数转换得到的八进制数。
N=(N div d)×d + N mod d (其中:div 为整除运算,mod 为求余运算)例如(1348)10=(2504)8,其运算过程如下:N N div 8 N mod 81348 168 4168 21 021 2 52 0 2算法:void conversion(int n , int d) /*将十进制整数N转换为d(2或8)进制数*/ { SqStack S ; int k, *e ; //建立堆栈SS=Init_Stack(); //堆栈S初始化while (n>0) { k=n%d ; push(S , k) ; n=n/d ; }/* 求出所有的余数,进栈*/while (S.top!=0) /* 栈不空时出栈,输出*/{ pop(S, e) ;printf(“%1d” , *e) ;}}队列的类型定义:定义:队列是限定只能在表的一端进行插入,在表的另一端进行删除的线性表 队尾(rear):允许插入的一端 队头(front):允许删除的一端 队列特点:先进先出 ( FIFO ) 队列储存结构:顺序队、链队 顺序队列操作: 插入:insertseq(Sequeue *q,Elemtype x){/*将元素x 插入到队列q 中,作为q 的新队尾,即入队操作*/ if (q->rear>Maxsize-1) return FALSE; /*队列满*/ else { q->data[q->rear]=x; //先插入数据 q->rear++; //再移动指针 return TRUE; }}//insertseq 删除:Elemtype deleteseq(Sequeue *q){/*若队列q 不为空,则删除队头元素,即出队列操作*/Elemtype x; //定义数据元素变量,存放删除元素 if (q->rear= =q->front) return NULL; //队列空 else { x=q->data[q->front]; //先删除数据 q->front++; //再移动指针 return x; }}//deleteseq循环顺序队插入、删除分析:(c) BC 入队front(b)A 入队frontfront(a) 初始状态 front=rear=0(d) A 出队(f) DEFG 入队第四章 串串的类型定义:串是字符串的简称。