数据结构之线性结构知识点总结_数据结构线性表知识点总结

目录

一、前置函数clock()

二、时间复杂度

三、线性表及其实现

1.数组

2.链表

3.广义表

四、堆栈

1.数组

2.二栈数组

3.链表

4.堆栈的应用

 五、队列

1.数组

2.链表

六、实例

1.多项式加法运算

2.一元多项式的加法与乘法运算

​

---

一、前置函数clock()

C语言提供clock()函数可以捕捉从程序开始运行到clock()函数被调用时所耗费的时间，通过clock()函数可以得到程序执行的时间，具体实现如下：

clock_t start,stop; //定义变量类型
double duration;
 
int main()
{
    start = clock();
    MyFunction();
    stop = clock();
    duration = ((double)(stop - start))/CLK_TCK; 
    //CLK_TCK：机器时钟每秒走的打点数
    return 0;
}

二、时间复杂度

三、线性表及其实现

1.数组

①头文件

#include<stdio.h>
#define ERROR -1
#define ElementType int
 
typedef int Position;    //数组元素类型
typedef struct LNode *List;    //List:结构体指针
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};

②初始化

List MakeEmpty()
{
    List L;
 
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
 
    return L;
}

③查找

Position Find( List L, ElementType X )
{
    Position i = 0;
 
    while( i <= L->Last && L->Data[i]!= X )
        i++;
    if ( i > L->Last )  return ERROR;    //如果没找到，返回错误信息 
    else  return i;    //找到后返回的是存储位置
}

④插入

bool Insert( List L, ElementType X, Position P ) 
{ /* 在L的指定位置P前插入一个新元素X */
    Position i;
 
    if ( L->Last == MAXSIZE-1) {
        /* 表空间已满，不能插入 */
        printf("表满"); 
        return false; 
    }  
    if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */
        printf("位置不合法");
        return false; 
    } 
    for( i=L->Last; i>=P; i-- )
        L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */
    L->Data[P] = X;  /* 新元素插入 */
    L->Last++;       /* Last仍指向最后元素 */
    return true; 
} 

⑤删除

bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */
    Position i;
 
    if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */
        printf("位置%d不存在元素", P ); 
        return false; 
    }
    for( i=P+1; i<=L->Last; i++ )
        L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */
    L->Last--; /* Last仍指向最后元素 */
    return true;   
}

2.链表

①头文件

#include <stdio.h>
#define ElementType int
 
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

②查找

Position Find( List L, ElementType X )
{
    Position p = L; /* p指向L的第1个结点 */
 
    while ( p && p->Data!=X )
        p = p->Next;
 
    return p;
}

③插入

bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;
 
    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL ) { /* P所指的结点不在L中 */
        printf("插入位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 在P前插入新结点 */
        tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
        tmp->Data = X; 
        tmp->Next = P;
        pre->Next = tmp;
        return true;
    }
}

④删除

bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
    Position pre;
 
    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
        printf("删除位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 将P位置的结点删除 */
        pre->Next = P->Next;
        free(P);
        return true;
    }
}

3.广义表

 

四、堆栈

1.数组

①头文件

#include<stdio.h>
#define ERROR -1
#define ElementType int
typedef int Position;
typedef struct SNode *Stack;
 
struct SNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Top;      /* 栈顶指针 */
    int MaxSize;       /* 堆栈最大容量 */
};

②初始化

Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}

③判断是否空/满

bool IsFull( Stack S )
{
    return (S->Top == S->MaxSize-1);
}
 
bool IsEmpty( Stack S )
{
    return (S->Top == -1);
}

④入栈

bool Push( Stack S, ElementType X )
{
    if ( IsFull(S) ) {
        printf("堆栈满");
        return false;
    }
    else {
        S->Data[++(S->Top)] = X;
        return true;
    }
}

⑤出栈

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

2.二栈数组

①初始化

②出入栈

3.链表

①头文件

#include<stdio.h>
#define ERROR -1
#define ElementType int
typedef struct SNode *PtrToSNode;
typedef PtrToSNode Stack;
 
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};

②初始化

Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;
 
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

③判断是否为空

bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}

④入栈

bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;
 
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

⑤出栈

ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;
 
    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

4.堆栈的应用

 五、队列

1.数组

①头文件

#include<stdio.h>
#define ERROR -1
#define ElementType int
typedef int Position;
typedef struct QNode *Queue;
 
struct QNode {
    ElementType *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};

②初始化

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = MaxSize - 1;
    Q->Rear = -1;
    Q->MaxSize = MaxSize;
    return Q;
}

③判断是否满/空

bool IsFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}
 
bool IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}

④入列

bool AddQ( Queue Q, ElementType X )
{
    if ( IsFull(Q) ) {
        printf("队列满");
        return false;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return true;
    }
}

⑤出列

ElementType DeleteQ( Queue Q )
{
    if ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
}

2.链表

①头文件

#include<stdio.h>
#define ERROR -1
#define ElementType int
typedef struct Node *PtrToNode;
typedef PtrToNode Position;
typedef struct QNode *Queue;
 
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
 
struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};

②判断是否为空

bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}

③出队 

ElementType DeleteQ( Queue Q )
{
    Position FrontCell;
    ElementType FrontElem;
    
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;
        
        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}

六、实例

1.多项式加法运算

 

 

2.一元多项式的加法与乘法运算