数据结构 期中考试

水巷00001111

第一章   绪论
第二章   线性表
第三章   栈和队列
第四章   串
第五章   数组和线性表

--------------------------------------------第一章 绪论----------------------------------------------------
数据结构：非数值计算的程序设计问题。
研究主线：逻辑结构 存储结构 算法
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
数据结构（也称逻辑结构）是相互之间存在一种或多种特定关系的数据元素的集合。
结构（数据关系）：集合 线性 树 图
数据是对客观事物的符号表示。（计算机）所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位。可由若干个数据项组成。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据元素之间关系：顺序映像（物理地址相邻）和非顺序映像（借助指针）。
数据类型是一组性质相同的值的集合以及定义于这个值的一组操作。

抽象数据类型（ADT）是一个数学模型以及定义在该模型上的一组操作。
定义与实现无关。

ADT  抽象数据类型名{
数据对象：
数据关系：
基本操作：
}ADT抽象数据类型名

//函数结果状态代码
#define TRUE       1
#define FALSE       0
#define OK         1
#define ERROR      0
#define INFEASIBLE  -1
#define OVERFLOW  -2
算法：对特定问题求解步骤的一种描述。
描述算法：类C语言。
算法和程序的异同：
算法+数据结构=程序！
算法特性：5方面：有穷性 确定性 可行性 输入 输出
好的特性：4方面：正确性 可读性 健壮性 效率和低存储量

设计要求：效率和存储。  
效率：渐进时间复杂度。简称：时间复杂度。
频度是基本操作的执行次数。
                        计算过程：第一步：计算指定基本操作的执行次数（频度）
取出频度表达式支配项f（n）,放到T(n)=0(f(n))
for (i=1; i<=n; i++)
　　    for (j=1; j<=n; j++)
　　        x++;
T(n) = n2    f(n) = n2     时间复杂度为Ο(n2)    整个算法的时间复杂度为Ο(n+n2) = Ο(n2)。
例
public void printsum(int count){
    int sum = 1;
    for(int i= 0; i<n; i++){
       sum += i;
    }   
    System.out.print(sum);
}
只有可运行的语句才会增加时间复杂度，除了循环之外，其余的可运行语句的复杂度都是O(1)。
所以printsum的时间复杂度 = for的O(n)+O(1) = 忽略常量 = O(n)





O(1)<O(log n)<O(n)<O(n^2)<O(2^n)<O(n!)<O(n^n)
                        注意：特定情况下，本课程约定使用最坏情况下的时间复杂度。
                存储：空间复杂度 S(n)=O(f(n))
所需存储空间：算法本身 输入数据 （运行）临时占用

-------------------------------------------第二章 线性表--------------------------------------------------
线性表：概念（文字、形式）四个唯一(非空)
文字：一个线性表是n个数据元素的有限序列。
形式：(a1,a2,......,a i-1,a i,a i+1,......,a n).
四个唯一：
存在唯一的一个被称作“第一个”的数据元素;
存在唯一的一个被称作“最后一个”的数据元素;
除第一个之外的数据元素均只有一个前驱;
除最后一个之外的数据元素均只有一个后继。

一.顺序表示和实现
线性表的顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。（物理地址连续）
第i个数据元素a i 的存储位置为：
LOC（a i）= LOC(a 1)+(i - 1)*l

特点：以物理位置相邻表示逻辑关系；   任一元素均可随机存取。



------线性表的动态分配顺序存储结构-----
#include LIST_INIT_SIZE  100        //初始分配量
#include LISTINCREMENT  10        //分配增量
typedef  struct{
ElemType   *elem;
Int         length;
Int         listsize;
}SqList;
--C--
Typedef int ElemType;
#define INITSIZE 100
Typedef struct
{ ElemType * data;
int length;
int listsize;
}sqlist;

-------初始化----------
Status InitList_Sq(SqList &L){
//构造一个空的线性表
L.elem = (ElemType * )malloc(LIST_INIT_SIZE*sizeof(ElemType));
If(! L.elem) exit (OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}//InitList_Sq
--C--
创建一个空的顺序表L
void initlist(sqlist * L)
{ L->data=(ElemType *)malloc(sizeof(ElemType)* INITSIZE);
L->length=0;
     L->listsize= INITSIZE;
}
---------插入-------------
--类C--
一般情况下，在第i(1<=i<=n)个元素之间插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。
平均移动一半元素时间复杂度O(n)    平均移动n/2次
Status ListInsert_Sq(SqList &L, int i, ElemType e){
//在顺序表L中的第i个位置之前插入新的元素e；
If(i<1 || i> L.length + 1) return ERROR;
If(L.length>=L.listsize)
{//如果储存空间已满，增加空间
newbase=(ElemType*)realloc(L.elem,L.listsize+ LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);//“新”不出来内存！
L.elem = newbase;//新的基址（若旧基址无法new地址，重新创建）
L.listsize += LISTINCREMENT;//总容量
}
q =&(L.elem[i-1]);
for(p = &(L.elem[L.length-1]);p>=q;--p;)*(p+1)=*p;//插入位置及以后元素右移
*q = e;//插入e
++L.length;//表长增1
return OK;
}//ListInsert_Sq
0        1        2                4        5        6        7

3


--C--
int insert(sqList * L,int i,ElemType x)
{
int j;
If(i<1 || i>L->length+1)return 0;
If(L->length==L->listsize)
{
L->data=(ElemType *)realloc(L->data,(L->listsize+1)*sizeof(ElemType));
L->listsize++;
}
for(j=L->length-1;j>=i-1;j--)
L->data[j+1]=L->data[j];
L->data[i-1]=x;
L->length++;
return 1;
}

------------删除---------------
--类C--
一般情况下，删除第i（1<=i<=n）个元素时需将从第i+1至第n(共n-i)个元素依次向前移动一个位置。
平均移动一半元素(n-1)/2    时间复杂度O(n)   
Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
If((i<1) || (i>L.length)) return ERROR;
p = &(L.elem[i-1]);//p为被删除元素的位置（为何是i-1?  LOC(a i)=LOC(a1)+(i-1)*l）
e = * p;
q = L.elem+L.length - 1;//表尾元素的位置
for(++p;p<=q;++p;)*(p-1) = *p;//被删除元素之后的元素后移
--L.length;//表长减1
return OK;
}
--C--
int delete(sqlist * L,int i,ElemType * e)
{
int j;
If(i<1 || i>L->length)return 0;
* e =L->data[i-1];
for(j=i;j<L->length;j++)
L->data[j-1]=L->data[j];
L->length--;
return 1;
}
二、链式表示和实现
链式存储结构特点：用一组任意的存储单元存储线性表的数据元素。(逻辑次序连续、物理次序可连续可不连续)。
结点是本身信息(数据域)+直接后继信息(指针域)
N个结点链结成一个链表。
头结点：数据域：不存放任何数据   存放附加信息（链表的结点个数）。
指针域：存放第一个结点的地址。
A1                        A2                        A3                        A4                        A5                        A6                        A7                        A8               

单链表
单链表是非随机存取的存储结构。
---------存储结构----------
typedef struct LNode{
ElemType  data;
struct LNode  *next;
}LNode,* LinkList;
---C---
#include “stdio.h”
typedef int ElemType;
typedef struct node
{
ElemType data; //数据域
struct node * next;//指针域
}slink;
   基本操作：
查找O(n)非随机存取
定位O(n)
插入和删除无需移动结点，O(n)这里的时间费在了查找上
如果给定ai-1的位置，O(1)
（1）找到ai-1的位置
（2）修改指针（指针在修改前先保留）

---------------创建含n个元素带头结点的单链表head--------
---C---
slink * creslink(int n)
{
slink * head,* p,* s; //p指向新链入结点，s指向新开辟结点
int i;
p=head=(slink *)malloc(sizeof(slink));//创建头结点
for(i=1;i<=n;i++)
{
s=(slink *)malloc(sizeof(slink));
scanf(“&d”,&s->data);
p->next=s;
p=s;
}
p->next=NULL;//尾结点
return head;
}
-------------插入---------------
Status ListInsert_L(LinkList &L,int i, ElemType e)
{
p = L; j = 0;
while(p&&j<i-1){p = p->next;++j;}//寻找第i-1个结点
if(!p || j>i-1)return ERROR;
s = (LinkList) malloc (sizeof (LNode));//生成新结点
s->data = e; s->next = p->next;//1
p->next = s;//2
return 0K;
b       
}//ListInsert_L
   p
a       
x       
         1.q->next = p ->next;
               s
2.p->next = q;
---C---
int insert(slink * head,int i,ElemType x)
{
slink * p,*q;
int j;
if(i<1)return 0;
p=head;j=0;
while(p!=NULL&&j<i-1)
{
p=p->next;
j++;
}
if(p==NULL)return 0;
q = (slink *)malloc(sizeof(slink));
q->data=x;
q->next=p->next;
p->next = q;
return 1;
}
插入算法时间消耗在查找上，时间复杂度为O(n)
--------------------------删除----------------------
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{   //删除第i个元素，并由e返回其值
p = L; j = 0;
while (p->next&&j<i-1)     1.空表  2.找到表尾
{
p=p->next;
++j;
}
if(!(p->next) || j>i-1) return ERROR;
q = p->next;  p->next = q->next; //删除并释放结点
e = q->data;  free(q);
return OK;
}//ListDelete_L
---C---         p         q
      
a i-1                        a i                        a i+1               




int delete(slink * head,int i,ElemType * e)
{
slink * p,*q;
int j;
if(i<1)return 0;
p=head;j=0;
while(p->next!=NULL&&j<i-1)
{ p=p->next;j++;}
if(p->next==NULL)return 0;
q=p->next;
p->next=q->next;
* e = q->data;
free(q);
return 1;
}


尾插法
   
循环链表   

--------------------------------------------第三章 栈和队列-------------------------------------------------
一、栈
栈是限定仅在表尾进行插入或删除操作的线性表。表尾（栈顶top） 表头（栈底bottom）
后进先出（LIFO）    出栈           入栈

  an
   .
   .
   .
  a1



b
a
   栈顶                      栈顶元素   

                                                                                                  
                                                                       

                   栈底                                         栈底元素                       base
ADT定义（9个基本操作
ADT实现（表示和实现）
顺序栈
  一组连续的储存单元依次存放自栈底到栈顶的数据元素。top指示栈顶
先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再扩大。
基本操作：（初始化、取栈顶、入栈、出栈）
        栈空 S.base==S.top
        栈满 S.top-S.base==S.stacksize
        栈的长度length=S.top-S.base


--------------------------存储表示-定义------------------------
typedef struct{
        SElemType  *base;//栈底指针（始终指向栈底的位置）
        SElemType  *top;//栈顶指针
        int    stacksize;//当前分配栈可使用的最大储存容量
}
---C---
#define INITSIZE 100
typedef int ElemType;
typedef struct
{
        int top;
    ElemType *base;
        int stacksize;
}sqstack;
---------------------初始化-------------------------------
Status InitStack(SqStack &S)
{//构造空栈
        S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if(!S.base)exit(OVERFLOW);
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
        return OK;
}//InitStack
---C---
//栈顶指针top初始化为0
void initstack(sqstack *S)
{
        S->base=(ElemType * )malloc(INITSIZE*sizeof(ElemType));//申请储存空间
        S->top = 0;//栈顶指针初始值为0
        S->stacksize = INITSIZE;//容量为初始值
}
--------------栈判空------------------------
Status GetTop(SqStack S,SElemType &e)
{
        if(S.top==S.base) return ERROR;
                e = *(S.top-1);                        top指向栈顶的上面的元素
                return OK;
}//GetTop
---C---
int emptystack(sqstack * S)
{
        if(S->top==0)return 1;
        else return 0;
}
------------------压栈(入栈)------------------------
Status Push(SqStack &S,SElemType e)
{
        if(S.top->S.base>= S.stacksize)
        {
S.base = (SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!S.base)exit(OVERFLOW);

        S.top = S.base+S.stacksize;
        S.stacksize += STACKINCREMENT;
        }
        *S.top++= e;
}
---C---
将入栈元素x存入top所指的位置上，然后栈顶指针top增1.
int push(sqstack * S,ElemType x)
{
        if(S->top>=S->stacksize)
        {
                S->base=(ElemType *)realloc(S->base,(S->stacksize+1)*sizeof(ElemType));
                if(!S->base)return 0;
                S->stacksize++;
        }
        S->base[S->top++]=x; //插入元素后，栈顶指针上移
        return 1;
}
-----------------出栈----------------------
Status Pop(SqStack &S,SElemType &e)
{
        if(S.top==S.base)return ERROR;
    e = * --S.top;                                                        e=*(S.top-1);  S.top=S.top -1;
        return OK;
}//Pop
---C---
取出栈S的栈顶元素值，同时栈顶指针减1.
int pop(sqstack * S,ElemType *e)
{
        if(S->top==0)return 0;
        * e=S->base[--S->top];
        return 1;
}


链栈
        链栈是一个仅在表头进行操作的单链表。
                                        栈顶结点                    栈底结点
top                                an                        an-1                  ...        a1        ^                               


-------------------------定义-----------------------------------
typedef int ElemType;
typedef struct node
{ElemType data;     //数据域
struct node * next;  //指针域
}linkstack;
--------------------------初始化-------------------------------
创建一个带头结点的空栈S
linkstack * initstack(void)
{
        linkstack * S;
        S=(linkstack * )malloc(sizeof(linkstack));
        S->next=NULL;
        return S;
}
--------------------------入栈------------------------------------
将值为x的数据元素插入栈S中，使x成为新的栈顶元素。
int push(linkstack *S,ElemType x)
{
        linkstack *p;
        p=(linkstack *)malloc(sizeof(linkstack));
        if(!p)return 0;
        p->data=x;
        p->next=S->next;
        S->next=p;
        return 1;
}
------------------------------------出栈----------------------------------------
int pop(linkstack * S,ElemType * e)
{
        linkstack * p;
        if(S->next==NULL)return 0;
        p=S->next;
        *e=p->data;
        S->next=p->next;
        free(p);
        return 1;
}
栈的应用
        数制转换
        表达式求值（规则和过程）

递归的实现----递归工作栈
        入栈：实参和返回地址
        出栈：调用结束

栈的应用集合
        数学模型递归（阶乘）
        数据结构递归（二叉树）
        问题解法递归（折半查找、汉诺塔）

递归的优点：代码简洁，结构清晰，正确性易证明
递归的缺点：T(n)和S(n)不好

清除递归的方法：
        循环（阶乘）
        模拟内存工作栈（push,pop）（二叉树）
        尾递归（略）
          
   Hanoi塔问题
        （1）每次只能移动一个圆盘；
        （2）圆盘可以插在X、Y、Z中的任一塔座上；
        （3）任何时刻都不能将一个较大的圆盘压在较小的圆盘上

            
main()
{
    int n;
    printf("请输入数字n以解决n阶汉诺塔问题：\n");
    scanf("%d",&n);
    hanoi(n,'A','B','C');
}
void hanoi(char A,char B,char C,int n)
{
    if(n==1)
    {
      printf("Move disk %d from %c to %c\n",A,C,n);
    }
    else
    {
      hanoi(A,C,B, n-1);
      printf("Move disk %d from %c to %c\n",n,A,C);
      hanoi(B,A,C,n-1,);
    }
}

二、队列
        队列：只允许在表一端插入，另一端删除元素的线性表。FIFO
        允许插入的一端叫做队尾(rear),允许删除的一端叫做队头(front).
       a1    a2    a3  ...   an
       
       出队列                                                                 入队列

                     队头                    队尾

ADT定义（DSP（9个））
双端队列（定义、变化灵活）

队列的表示和实现
链队列-链式存储
循环队列-顺序存储

链队列
  存储结构
  基本循环解决假溢出问题

  存储结构P64
空：Q.rear==Q.front
满：（Q.rear+1）%M==Q.front
入队或者出队，rear和front循环意义加1
     例如(rear+1)%M
       Front同理
循环队列的基本操作                                 
   初始化
   求队列的长度
   插入
   删除
循环队列要事先确定最大长度，如果不能确定用链队列。

队列的应用：栈


链表-------链式存储的线性表
物理位置任意  靠指针表示逻辑关系

链接角度分为：单链表、循环链表和双向链表
实现角度分为：指针（动态链表）和游标（静态链表）

动态单链表
储存结构P28
基本操作
查找O(n)
定位O(n)
插入和删除无需移动结点，O(n)这里的时间费在查找上
如果给定ai-1的位置，0（1）
（1）找到ai-1的位置
（2）修改指针。

刘喜斌

这是考试大纲吗？

刘喜斌

这是考试大纲吗？

水巷00001111

自己总结的，可以看看。

编程好难

哇塞，，这看不懂

漫步Roam

哇，这么多，完全看不懂。。。