线性结构（笔记）

线性表

抽象数据类型描述

1、List MakeEmpty()：初始化一个空线性表L；
2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；
3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；
4、void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；
5、void Delete( int i, List L )：删除指定位序i的元素；
6、int Length( List L )：返回线性表L的长度n。

线性表的顺序存储实现

typedef  struct{   
	ElementType  Data[MAXSIZE];
	int  Last; 
} List; 
List L, *PtrL;

初始化（建立空的顺序表）

LIst *MakeEmpty()
{    List *PtrL;
     PtrL = (List *)malloc( sizeof(List));
     PtrL->Last = -1;
     return PtrL;
}

查找

查找成功的平均比较次数为(n+1)/2,平均时间性能为O(n)

int Find( ElementType X, List *PtrL ) 
{    int i = 0;
     while( i <= PtrL->Last && PtrL->Data[i]!= X )
         i++;
     if (i > PtrL->Last)  return -1; /* 如果没找到，返回-1 */
     else  return i;             /* 找到后返回的是存储位置 */ 
}

插入（第i(1≤i≤n+1)个位置插入一个值为X的新元素）

平均移动次数为n/2,平均时间性能为O(n)

int Insert( ElementType X, int i, List *PtrL ) 
{    int j;
     if(PtrL->Last == MAXSIZE-1){
         printf("表满");
         return;
     }
     if(i<1 || i>PtrLL->Last+2){
         printf("位置不合法");
         return;
     }
     for(j = PtrL->Last; j>=i-1;j--)
         PtrL->Data[j+1] = PtrL->Data[j];  /*将 ai～ an倒序向后移动*/
         PtrL->Data[i-1] = X;                     /*新元素插入*/
         PtrL->Last++;                              /*Last仍指向最后元素*/
         return; 
}

删除（删除表的第 i (1≤i≤n)个位置上的元素)

平均移动次数为(n-1)/2,平均时间性能为O(n)

void Delete( int  i, List *PtrL ) 
{      int  j;
       if( i < 1 || i > PtrL->Last+1 ) {        /*检查空表及删除位置的合法性*/
             printf (“不存在第%d个元素”, i );
             return ;
        }
        for ( j = i; j <= PtrL->Last; j++ )
             PtrL->Data[j-1] = PtrL->Data[j];     /*将 ai+1～ an顺序向前移动*/
        PtrL->Last--;                                        /*Last仍指向最后元素*/
        return;
}

线性表的链式存储实现

typedef  struct Node{
	ElementType  Data;
	struct Node *Next; 
} List; 
List L, *PtrL;

求表长

时间性能为O(n)

int Length (List *PtrL)
{    List *p = PtrL;  /*P指向表的第一个结点*/
     int j = 0;
     while(p){
         p = p->Next;
         j++;            /*当前P指向的第j个结点*/
     }
     return j;
}

查找

平均时间性能为O(n)
（1）按序号查找：FindKth;

List  *FindKth( int K, List *PtrL ) 
{      List  *p = PtrL;
       int  i = 1;
       while (p !=NULL && i < K ){
                p = p->Next;
                i++;
       }
       if ( i == K ) return p;                      /* 找到第K个，返回指针 */
       else  return NULL;                                 /* 否则返回空 */ 
}

（2）按值查找：Find;

List *Find( ElementType X, List *PtrL )
{    List  *p = PtrL;
     while ( p!=NULL && p->Data != X )
            p = p->Next;
     return p; 
}

插入（在第 i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)

（1）先构造一个新结点，用s指向；
（2）再找到链表的第 i-1个结点，用p指向；
（3）然后修改指针，插入结点 ( p之后插入新结点是 s)
平均查找次数为n/2,平均时间性能为O(n)

List *Insert( ElementType X, int i, List *PtrL )
 {       List  *p, *s;
         if ( i == 1 ) {                                                       /* 新结点插入在表头 */
              s = (List *)malloc(sizeof(List));                     /*申请、填装结点*/
              s->Data = X;
              s->Next = PtrL;
              return s;                                                            /*返回新表头指针*/
         }
         p = FindKth( i-1, PtrL );                                        /* 查找第i-1个结点 */
         if ( p == NULL ) {                                    /* 第i-1个不存在，不能插入 */
                  printf(＂参数i错＂);
                  return NULL;
          }else {
                 s = (List *)malloc(sizeof(List));                     /*申请、填装结点*/
                 s->Data = X;
                 s->Next = p->Next;                 /*新结点插入在第i-1个结点的后面*/
                 p->Next = s;
                 return PtrL;
        } 
}

删除（删除链表的第 i (1≤i≤n)个位置上的结点)

（1）先找到链表的第 i-1个结点，用p指向；
（2）再用指针s指向要被删除的结点（p的下一个结点）;
（3）然后修改指针，删除s所指结点;
（4）最后释放s所指结点的空间。
平均查找次数为n/2,平均时间性能为O(n)

List *Delete( int  i, List *PtrL ) 
{       List  *p, *s;
        if ( i == 1 ) {                                     /* 若要删除的是表的第一个结点 */
                s = PtrL;                                                            /*s指向第1个结点*/
                if (PtrL!=NULL)  PtrL = PtrL->Next;                      /*从链表中删除*/
                else return NULL;
                free(s);                                                               /*释放被删除结点 */
                return PtrL;
        }
        p = FindKth( i-1, PtrL );                                      /*查找第i-1个结点*/
        if ( p == NULL ) {
                  printf(“第%d个结点不存在”, i-1);     return NULL;
        } else  if ( p->Next == NULL ){
                  printf(“第%d个结点不存在”, i);      return NULL;
        } else  {
                s = p->Next;                                                     /*s指向第i个结点*/
                p->Next = s->Next;                                          /*从链表中删除*/
                free(s);                                                             /*释放被删除结点 */
                return PtrL;
        } 
}

堆栈

中缀表达式：运算符号位于两个运算数之间。如 ，a+bc-d/e 
后缀表达式：运算符号位于两个运算数之后。如， abc+de/-

堆栈的抽象数据类型描述

堆栈（Stack）：具有一定操作约束的线性表
只在一端（栈顶，Top）做 插入、删除
插入数据：入栈（Push）
删除数据：出栈（Pop）
后入先出：Last In First Out（LIFO）
1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize；
2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；
3、void Push( Stack S, ElementType item )：将元素item压入堆栈；
4、int IsEmpty ( Stack S )：判断堆栈S是否为空；
5、ElementType Pop( Stack S )：删除并返回栈顶元素；
Push 和 Pop 可以穿插交替进行

栈的顺序存储实现

#define MaxSize  <储存数据元素的最大个数>
typedef struct {
	ElementType Data[MaxSize];
	int Top;
} Stack;

入栈

void Push( Stack *PtrS, ElementType item )
{	if ( PtrS->Top == MaxSize-1 ) {
	    printf(“堆栈满”);  return; 
	}else {
	    PtrS->Data[++(PtrS->Top)] = item;
	    return;
	 }
}

出栈

ElementType Pop( Stack *PtrS )
{     if ( PtrS->Top == -1 ) {
            printf(“堆栈空”);
            return ERROR;           /* ERROR是ElementType的特殊值，标志错误 */
     } else
             return ( PtrS->Data[(PtrS->Top)--] );
}

两个堆栈最大化利用数组空间

两头向中间生长

#define MaxSize <存储数据元素的最大个数>
struct DStack {
      ElementType Data[MaxSize];
      int Top1;      /* 堆栈１的栈顶指针 */
      int Top2;      /* 堆栈２的栈顶指针 */
}S;
S.Top1 =  -1;
S.Top2 = MaxSize;

入栈

void Push( struct DStack *PtrS, ElementType item, int Tag )
{  /* Tag作为区分两个堆栈的标志，取值为1和2 */
	if ( PtrS->Top2 – PtrS->Top1 == 1) {  /*堆栈满*/
 	  printf(“堆栈满”);   return ;
	}
	if ( Tag == 1 ) /* 对第一个堆栈操作 */
	    PtrS->Data[++(PtrS->Top1)] = item;
	else              /* 对第二个堆栈操作 */
	    PtrS->Data[--(PtrS->Top2)] = item;
}

出栈

ElementType Pop( struct DStack *PtrS, int Tag )
{  /* Tag作为区分两个堆栈的标志，取值为1和2  */
	if ( Tag == 1 ) {  /* 对第一个堆栈操作  */
	    if ( PtrS->Top1 == -1 ) { /*堆栈1空 */
		printf(“堆栈1空”);   return NULL;
	    } else return PtrS->Data[(PtrS->Top1)--]; 
	} else {          /* 对第二个堆栈操作 */
	    if ( PtrS->Top2 == MaxSize ) { /*堆栈2空 */
		printf(“堆栈2空”);  return NULL;
	    } else  return PtrS->Data[(PtrS->Top2)++]; 
    }
}

堆栈的链式存储实现

typedef struct Node{
	ElementType  Data;
	struct Node *Next;
} LinkStack;
LinkStack *Top;

(1) 堆栈初始化（建立空栈）
(2) 判断堆栈S是否为空

创建链栈

LinkStack *CreateStack()
{  /* 构建一个堆栈的头结点，返回指针 */
    LinkStack *S;
    S = malloc( sizeof(struct Node ));
    S->Next = NULL;
    return S;
}
int IsEmpty( LinkStack *S )
{  /*判断堆栈S是否为空，若为空函数返回整数 1，否则返回0 */
  return ( S->Next == NULL );
}

入栈

void Push( ElementType item, LinkStack *S )
{  /* 将元素item压入堆栈S  */
	struct Node *TmpCell;
	TmpCell = malloc( sizeof( struct Node ) );
	TmpCell->Element = item;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}

出栈

ElementType Pop( LinkStack *S )
{  /* 删除并返回堆栈S的栈顶元素 */
	struct Node *FirstCell;
	ElementType TopElem;
	if( IsEmpty( S ) ) {
	    printf(“堆栈空”);  return NULL;
	} else {
	    FirstCell = S->Next;
	    S->Next = FirstCell->Next;
	    TopElem = FirstCell ->Element;
	    free(FirstCell);
	    return TopElem;
    }
}

队列

队列的抽象数据类型描述

队列(Queue)：具有一定操作约束的线性表
插入和删除操作：只能在一端插入，而在另一端删除。
数据插入：入队列（AddQ）
数据删除：出队列（DeleteQ）
先来先服务
先进先出：FIFO
1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；
2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；
3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；
4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；
5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

队列的顺序存储实现

#define MaxSize  <储存数据元素的最大个数> 
typedef  struct  {
	ElementType  Data[ MaxSize ];
	int  rear;
	int  front;
} Queue;

入队列

void AddQ( Queue *PtrQ, ElementType item)
{          if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
               printf(“队列满”);
               return; 
            }       
            PtrQ->rear = (PtrQ->rear+1)% MaxSize;
            PtrQ->Data[PtrQ->rear] = item;
}

出队列

ElementType DeleteQ ( Queue *PtrQ ) 
{
	if ( PtrQ->front == PtrQ->rear ) 
{	    printf(“队列空”);
                    return ERROR;
	}  else  {
	    PtrQ->front = (PtrQ->front+1)% MaxSize;
	    return  PtrQ->Data[PtrQ->front];
        }
}

队列的链式结构存储实现

typedef struct Node{
       ElementType  Data;
       struct Node  *Next;
}QNode; 
typedef  struct {        /* 链队列结构  */
      QNode  *rear;      /* 指向队尾结点 */
      QNode  *front;     /* 指向队头结点 */
} LinkQueue;
LinkQueue  *PtrQ ;

多项式加法运算

typedef  struct  PolyNode {
	int  coef;         // 系数
	int  expon;     // 指数
	struct node *link;   // 指向下一个节点的指针
}*Polynomial; 

Polynomial  P1, P2;

Polynomial  PolyAdd (Polynomial P1, Polynomial P2)
{ 
	Polynomial front, rear, temp; 
	int sum; 
	rear = (Polynomial) malloc(sizeof(PolyNode));   
	front = rear;        /* 由front 记录结果多项式链表头结点 */
	while ( P1 && P2 )  /* 当两个多项式都有非零项待处理时 */
	    switch ( Compare(P1->expon, P2->expon) ) {
	    case 1:  
		Attach( P1->coef, P1->expon, &rear); 
		P1 = P1->link; 
		break; 
	    case -1:   
		Attach(P2->coef, P2->expon, &rear);  
		P2 = P2->link; 
		break; 
	    case 0:   
		sum = P1->coef + P2->coef;
		if ( sum ) Attach(sum, P1->expon, &rear);
		P1 = P1->link;
		P2 = P2->link;
		break; 
	    } 
/* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */
	for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear); 
	for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear); 
	rear->link = NULL;  
	temp = front; 
	front = front->link; /*令front指向结果多项式第一个非零项 */
	free(temp);            /* 释放临时空表头结点 */
	return front; 
}

void Attach( int coef, int expon, Polynomial *PtrRear )   
{      /* 由于在本函数中需要改变当前结果表达式尾项指针的值， */ 
/* 所以函数传递进来的是结点指针的地址，*PtrRear指向尾项*/
	Polynomial P;

	P =(Polynomial)malloc(sizeof(PolyNode)); /* 申请新结点 */
	P->coef = coef;                               /* 对新结点赋值  */
	P->expon = expon;      /* 将P指向的新结点插入到当前结果表达式尾项的后面  */
	(*PtrRear)->link = P;
	*PtrRear = P;           /* 修改PtrRear值 */
}