顺序表

线性表：具有相同类型的n个数据元素的有限序列（个数有限、次序性）

 

物理存储与逻辑结构的关系：用数据元素的存放位置次序来表示数据之间的逻辑关系

定义形式

结构体定义

//存储的基址+存储的长度的+标识的当前分配的存储容量（再分配内存的时候需要用），别的的信息一概无用，因为别的这些信息只能存储在一个结构体中而且基本不做任何操作，本质上就是一个数组，只不过这个数组空间是用动态分配的内存空间，而通常定义的数组是静态变量空间（不管是全局，还是函数栈空间内）

Typedef struct 【结构体名】

{

   Elemtype *a;

   Int length；

   Int Listsize ;

}新结构体名

数组形式定义

//由系统分配的空间

Elemtype a[maxsize];

Int n;

顺序表的常见操作

初始化

1. 结构体形式

实质就是数组分配内存再赋值

新结构体变量名.a=（elemtype*）malloc（maxsize*sizeof（elemtype）//这里实际标识长度的是

新结构体变量名.length=0;

Listsize=maxsize;

1. 初始化数组：

int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个数组，同时初始化所有成员变量

       int a[10] = { 1, 2, 3 };//初始化前三个成员，后面所有元素都设置为0

       int a[10] = { 0 };//所有的成员都设置为0

        //[]中不定义元素个数，定义时必须初始化

          int a[] = { 1, 2, 3, 4, 5 };//定义了一个数组，有5个成员

n=0;

插入

需要的参数：插入的位置i，插入的值

涉及的操作：

1. 找到插入的位置（可能是按照关键字查找而得），判断是否超出数组的第一个位置和最后的位置
2. 使i后面的数组元素整体后移一个单位，这个过程中应当从最后一个元素开始元素逐个往后移动一个单位//如果正着来会发生元素覆盖形成脏数据，for循环使用 (length-i)—
3. Length+1

 

删除

参数：删除的位置 i，接受删除的元素的变量e

操作：

1. 找到删除的位置，判断是否在数组的第一个位置前面和最后的位置后面，如果是则返回error
2. 使i的位置的后面的元素逐个向前，从i+1位置的元素开始逐个往前移动，同样如果从最后一个位置的元素开始往前移动则会发生数据覆盖，形成脏数据,for循环使用（length-i）--
3. Length-1;
4. 

修改

参数：被修改元素的位置，存放修改的值的变量e，接受修改前的变量f

操作：

查找到位置

数组这个位置的值赋值给f变量

将e赋值给数组这个位置（这是一个变量）

查询

参数：查询的元素值，值所在的数组的位置

操作：

利用for循环，从i=0开始，i++

If (a[i]=值)//【新结构体名】.a[i]

{

Printf(“顺序表中有此值的位置有i0,i1,i2…\n”);

}

判空

参数：void

操作：

If（n!=0）

{

Printf(“顺序表不为空\n”)；

}

清空

参数：所要清空的顺序表的位置（值传递）

操作：将length=0;即可//因为清空就是整体重新赋值之前的一个状态

销毁

参数：所要销毁的顺序表的位置（值传递）

操作：

结构体

For循环下，从顺序表的最后的位置，不断释放内存空间

将length=0;listsize=0;elemtype*a=NULL;//释放掉了连续内存空间，但是结构体不能销毁

For（int i=【结构体变量名】.a[length];I>=0;i--）

{

Free(【结构体变量名】.a[i]);

}

length=0;listsize=0;elemtype*a=NULL

数组：

如果是全局变量，只能随程序的结束而释放

如果是局部变量，则随着定义这个数组的那个函数的结束而自动释放，局部栈空间上的数组程序结束程序系统自动回收

 

如果想动态定义使用、释放内存，则通过指针方式来实现就是调用free函数

 

实现两个线性表A、B的并集操作，即要使得集合

• 其实仔细思考一下，我们只需要循环遍历集合B中的每一个元素，判断当前元素是否在A中存在，若不存在，则插入A中即可。
• 综合分析，我们需要运用几个基本的操作组合即可：
  • ListLength(L);
  • GetElem(L,i,*e);
  • LocateElem(L,e);
  • ListInsert(*L,i,e);

//union.c
void unionL(List *La, list Lb)
{
    int La_len, Lb_len, i;
    ElemType e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for( i=1; i <= Lb_len; i++)
    {
        GetElem(Lb, i, &e);
        if( !LocateElem(*La, e))

{
            ListInsert(La, ++La_len, e);
        }
    }
}

善于利用基本的函数操作实现代码的简化

 

 

栈

逻辑关系：操作受限的线性表，输入和输出都在栈顶

物理存储：顺序栈（元素顺序存放的栈），链栈（元素信息以结点的形式存放）

栈的的数学性质：n个不同元进栈，出栈元素不同排列的个数为

 

上述公式称为卡特兰数，可采用数学归纳法证明，有兴趣的读者可参考组合数学教材

顺序栈

结构体形式定义：

Typedef struct 【结构体名】//长度，链接指针，分配的存量

{

Elemtype *base;

Elemtype *top;

Int       Listsize;

}

【新结构体名】;

【新结构体名】 S;

数组形式定义：

#define   STACK_INIT_SIZE   100

#define   STACKINCREMENT   10

#define   OK   1

#define   OVERFLOW   -1

#define   ERROR   0

 

Int [maxsize] ;

Int n;

Int *base;

Int *top;

基本操作：

    InitStack(&S);               DestroyStack(&S);

     ClearStack(&S);              StackEmpty(S);

     StackLength(S) ;             GetTop(S,  &e);

     Push(&S,  e);                 Pop(&S,  &e);

     StackTraverse(S,  visit ( ))

 

初始化

1. 分配内存空间
2. 标注初始容量

Status Initlist (S*S1)

{

  Elemtype *base=(elemtype*)malloc(maxsize*sizeof(int))

  If (!S1.base){exit {overflow};//内存空间分配失败，退出程序}

  S1.*top=S.base;

  S.stacksize=maxsize;

}

插入

判断栈的空间，如果top>maxsize，则栈满，重新分配内存，if失败则exit[-1];//异常并退出

*top=e;

Top ++;

取栈顶元素

GetTop(S,  &e)

{

  e=*(S.Top)

}

删除

判断栈的空间，如果栈空，即top=base；则exit[-1];异常并退出

之后，--top;e=*top;//先top—然后再赋值

判空

StackEmpty(S)

{

  If(S.top==S,base) printf(“此栈为空”);

return OK;

}

 

清空

ClearStack(&S);//

{

Top=base;

}

销毁

DestroyStack(&S);

{

for(int i=1;I<=s.top-s.base;i++)

{

  S.base++;

  Free(S.base);

}

S->base=S->top=null;

Return OK;

}

栈的遍历

StackTraverse(S,  visit ( ))

{

Int *j=S.base;

  For(int i=0;i<=S.top-S.base;i++)

{

  Printf(“%d”\n，*j);

  ++j;

}

Return OK;

}

 

利用栈数制转换

   数制专换（应该掌握的问题）

void conversion()

{

    // 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数

    InitStack(S);   // 构造空栈S

    scanf ("%d", &N);//输入数值N

while (N)

{

         Push(S, N%8);//对数值N除8的余数入栈

         N = N/8;    //不断的除以8，得到的是N的8进制数字

    }

while ( !StackEmpty(S)) 

{

          Pop(S, e);出栈

          printf ( "%d", e);

    }

} // conversion

上面的代码需要掌握

 

以下是两种定义方法下的算法

void conversion(int N, int r)

{ 

SeqStack  *s;

datatype  x;

s=Init_SeqStack();

   while(N) {

       Push_SeqStack(s, N % r);

       N = N/r;

 }

   while (!Empty_SeqStack(s))

   {

       Pop_SeqStack(s, &x);

       printf("%d", x);

   }

}

这个是结构体

#define  L  10

void conversion(int N, int r)

{  int s[L], top; /*定义顺序栈 */

    int x;

    top = -1; /*初始化栈 */

        while(N) {

        s[++top] = N % r;

        N = N/r;

 }

    while(top != -1)

    {

         x = s[top--];

         printf("%d", x);

    }

}

 

表达式求值

这里仅讨论：含+、-、*、/ 4种运算符和左右括号的简单算术表达式。

表达式的表示形式：前缀、中缀和后缀3种

设  Exp = S1 + OP + S2

则称    OP + S1 + S2      为前缀表示法

S1 + OP + S2      为中缀表示法

S1 + S2 + OP      为后缀表示法

例如:    Exp = a ´ b + (c - d / e) ´ f

前缀式:           + ´ a b ´ - c / d e f

中缀式:           a ´ b + c - d / e ´ f

后缀式:           a b ´ c d e / - f ´ +    

顺序队列

由于顺序队列存在假满的情况，所以将之改造为循环队列

定义一个循环队列

#define MAXSIZE 100
typedef struct
{
    ElemType *base; //用于存放内存分配基地址
    int front;
    int rear;//这里是整型
}

初始化一个循环队列

initQueue(cycleQueue *q)
{
    q->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
 

   if( !q->base )
 

        exit(0);
    q->front = q->rear = 0;
}

入队列操作

InsertQueue(cycleQueue *q, ElemType e)
{
    if( (q->rear+1)%MAXSIZE == q->front ) //判断是否满了， 1%3=1（1除以3除不尽 取1）这个是顺序循环队列满的标志
        return; //队列已满
    q->base[q->rear] = e;
    q->rear = (q->rear+1) % MAXSZIE;
}

出队列操作

DeleteQueue(cycleQueue *q, ElemType *e)
{
    if( q->front == q->rear ) //判断队列是否为空
    {
        return;
    }
    *e = q->base[q->front];  

q->front = (q->front + 1) % MAXSIZE;

}