数据结构浙大陈姥姥版第二章

淡淡的烟草味﹌ 2023-06-30 02:56 5阅读 0赞

### 文章目录 ###

*  引子
 *   *  多项式的表示
 *  线性表(Linear List)
 *   *  线性表的定义
     *  线性表的顺序存储实现
     *   *  主要操作的实现
     *  线性表的链式存储实现
     *   *  主要操作的实现
     *  广义表（Generalized List)
     *  多重链表
 *  堆栈（stack）
 *   *   *  后缀表达式
         *  堆栈的抽象数据类型描述
         *  堆栈的顺序存储实现
     *  堆栈的链式存储实现
     *  堆栈应用：表达式求值

# 引子 #

## 多项式的表示 ##

多项式的关键数据：

多项式的项数 n

各项的系数a\_i、指数i

方法1：

顺序存储结构直接表示

方法2：

顺序存储结构表示非零项

结构数组表示：（a\_i, i)

方法3：

链表结构存储非零项

<table> 
 <thead> 
  <tr> 
   <th>…</th> 
   <th>…</th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>coef</td> 
   <td>expon</td> 
   <td>link</td> 
  </tr> 
 </tbody> 
</table>

typedef struct PolyNode \*Polynomial;

struct PolyNode\{

int coef;

int expon;

Polynomial link;

# 线性表(Linear List) #

## 线性表的定义 ##

由同类型数据元素构成有序序列的线性结构

表中元素的个数：线性表的长度

表中没有元素：空表

表起始位置：表头；表结束位置：表尾

线性表的抽象数据类型描述

**类型名称**： 线性表(List)

数据对象集：

操作集：

## 线性表的顺序存储实现 ##

**放在数组里面**

typedef struct LNode *List;
    struct LNode{ 
    	ElementType Data[MAXSIZE];
    	int Last;//数组的最后一个元素
    };
    struct LNode L;//定义一个链表
    List PtrL;//定义一个指向链表的指针；线性表结构的指针
    //通过线性表结构的指针可以知道数组是谁，Last位置

访问下标为i的元素：

L.Data[i];
    //或
    PtrL->Data[i];

线性表的长度：

L.Last + 1;
    //或
    PtrL->Last + 1

### 主要操作的实现 ###

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

List MakeEmpty()
    { 
    	//表的表示：1.数组
    	// 2.代表最后一个元素Last
    	List PtrL;
    	//数据类型是 struct LNode
    	//用malloc申请这样的结构
    	PtrL = (List)malloc(size0f(struct(LNode)));
    	//把结构的最后一个元素赋值为-1
    	//表里面没有元素 用 -1 表示
    	PtrL->Last = -1;
    	return PtrL;//返回这个结构的指针
    }

1.  查找

int Find(ElementType X, List PtrL)
    { 
    	int i = 0;
    	//循环查找X的位置
    	while(i < PtrL.Last && PtrL.Data[i] != X)
    		i++;
    	if(i > PtrL.Last)
    		return -1;
    	else
    		return i;
    }

1.  插入

int Insert(ElementType X, int i , List PtrL)
    { 
    	int j;
    	//判断表是不是已经存满
        //MAXSIZE - 1是数组大小
    	if(PtrL->Last == MAXSIZE - 1)
    	{ 
    		printf("full");
    		return;
    	}
    	//检查插入位置的合法性
    	if(i < 1 || i > PtrL -> Last + 2)
    	{ 
    		printf("not legal");
    		return;
    	}
    	//将ai ~ an 倒序往后移动
        //这里只有最后一个元素是能移动的所以先移动最后一个元素
    	if(j = PtrL->Last; j >= i - 1; j--)
    	{ 	
    		PtrL->Data[j + i] = PtrL -> Data[j];
    	}
    	//新元素X插入
    	PtrL -> Data[i - 1] = X;
    	//Last指向最后元素
    	PtrL -> Last++;
    	return;
    }

1.  删除

跟插入是相反的操作

int Delete(int i,List PtrL)
    { 
    	int j;
    	//检查空表以及删除位置的合法性
    	if(j < 1 || j > Last + 1)
    	{ 
    		printf("not legal");
    		return;
    	}
    	for(j = i; j <= Ptr->Last; j++)
    	{ 
        	PtrL->Data[j-1] = PtrL->Data[j];
    	}
    	PtrL->Last--;
    	return;
    }

## 线性表的链式存储实现 ##

*  不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起元素之间的逻辑关系
 *  插入、删除不需要移动数据元素，只需要修改“链”

typedef struct LNode *List;
    struct LNode{ 
    	ElementType Data;
    	List Next;//下一个结点的位置
    };
    
    struct LNode L;
    List PtrL;

### 主要操作的实现 ###

1.  求表长

//用链表来实现，我们只知道链表的头指针，而且是单向链表
    //遍历链表
    int Length(List PtrL)
        
    { 
    	List p = PtrL;//临时指针p指向链表头；即p指向表的第一个结点
    	int j = 0;//计数器
    	while(p)//p != NULL
    	{ 
    		p = p->Next;//链表指针往后挪一位
    		j++;
    	}
    	return j;
    }

1.  查找
    
     *  按序号查找：FindKth
    
        List FindKth(int K, List PtrL)
        { 
        	List p = PtrL;//p设为链表表头
        	int i = 1;
            //查找范围
        	while(p != NULL && i < K)//表不是空的，还没找到K
        	{ 
        		p = p -> Next;
        		i++;
        	}
        	if(i == K)//找到K
        		return p;
        	else return NULL;
        }
    
     *  按值查找：Find
    
        List Find(ElementType X, List PtrL)
        { 
        	List p = PtrL;
        	while(p != NULL && p -> Data[i] != X)
        	{ 
        		p = p -> Next;
        	}
        	return p;//返回值所在的地址
        }
2.  插入（在第 i - 1 个结点后插入一个值为X的新结点）

步骤：

*   先构造一个新的结点，用s指向；（malloc)
 *   找到链表的第 i - 1个结点，用p指向；
 *   修改指针，插入节点

List Insert(ElementType X, int i, List PtrL)
    { 
    	List s, p;
        //情况一：新结点插在标头
        if(i == 0)
        { 
            //申请填装结点
            s = (List)malloc(sizeof(struct LNode));
            s -> Data = X;
            s -> Next = PtrL;
            return s;//返回新链表头指针
        }
        //查找第i-1个结点的位置
        p = FindKth(i - 1, PtrL);
        //第i - 1 不存在， 不能插入
        if(p == NULL)
        { 
            printf("参数 i 错误")；
                return NULL;
        }
        else
        { 
            s = (List)malloc(sizeof(struct LNode));
            s -> Data = X;
            //这里不能调换 之前的地址会丢失掉
            s -> Next = p -> Next;//s的结点指向p的下一个结点
            p -> Next = s;//p的结点指向s
            return PtrL;//返回新链表头指针
        }
    }

1.  删除（删除链表第 i 个位置上的结点）

前面的结点接到第 i 个结点的后面

步骤：

*  找到第 i - 1个结点，用 p 指向；
 *  再用指针 s 指向被删除的结点（ p 的下一个结点）；
 *  修改 指针(p的指针指向i 后面的位置)， 删除 s 结点；
 *  释放s所指的空间；

List Delete(int i, List PtrL)
    { 
    	List s, p;
        //若删除的头节点
        //两种可能 PtrL 本身就是空的 返回NULL
        // 不为空 ，结点挪到下一个位置
        if(i == 1)
        { 
            s = PtrL;//被删除的是头结点
            if(PtrL != NULL)
            { 
                PtrL = PtrL -> Next;
            }
            else
            { 
                return NULL;
            }
            free(s);
            return PtrL;
        }
    	p = FindKth(i - 1, PtrL);
    	
    	if(p == NULL)
    	{ 
    		printf("参数 i 错误, 结点"%d"不存在", i - 1);
            return NULL;
    	}
        else if(p -> Next == NULL)
        { 
    		printf("参数 i 错误, 结点"%d"不存在", i - 1);
            return NULL;
        }
    	else
    	{ 
            s  = p -> Next;//第一步 s 指针指向被删除的结点
    		p -> Next = s -> Next;//修改指针， p的结点指向s指针后面这个结点
    		free(s);
    		
    		return PtrL;
    	}
    }

## 广义表（Generalized List) ##

*  广义表是线性表的推广
 *  对线性表而言，n个元素都是基本的单元素
 *  对广义表，这些元素不仅可以是单元素也可使是另一个广义表

//union 可以把不同类型的元素组织在一起
    //可以把一个空间理解为一个类型，也可以理解为另外一个类型
    //使用标记来区分不同的类型
    
    typedef struct GNode *GList;
    struct GNode{ 
        int Tag; //标志域：0表示结点是单元素；1表示结点时广义表
        //子表 指针域SubList和单元素数据域Data复用，共用存储空间
        union{ 
            ElementType Data;
            GList SubList;
        }URegion;
        GList Next; //指向后面结点
    }

## 多重链表 ##

定义: 链表中的结点可能隶属于多个链

**十字链表**来存储稀疏矩阵

*  只存储矩阵非0元素项
    
    结点的数据域：Row Col Value

**矩阵行跟行，列跟列之间的关系通过结点间的指针来建立关系**

*  每个结点通过两个指针域，把同行，同列串起来\*\*\[这里用到多重链表\]\*\*
    
     *  行指针 Right
     *  列指针 Down

# 堆栈（stack） #

**a pile of dishes**

是一种特殊的线性表

计算机如何进行表达式求值？

### 后缀表达式 ###

`a + b * c - d / e`

`a b c * + d e / -`

### 堆栈的抽象数据类型描述 ###

堆栈：具有一定操作约束的线性表 **\[只在一段（栈顶，Top）做插入、删除\]**

*  插入数据：入栈(Push)
 *  删除数据：出栈(Pop)
 *  后入先出：Last In First Out (LIFO)

**类型名称**：堆栈(stack)

数据对象集：一个有0或多个元素的有穷线性表

操作集：

### 堆栈的顺序存储实现 ###

栈的顺序存储结构通常由一个**一维数组**和一个记录**栈顶**元素位置的变量组成

#define MaxSize <存储数据元素的最大个数>
    typedef struct SNode *Stack;//结构指针
    struct SNode{ 
    	ElementType Data[MaxSize];//数组
    	int Top;//栈顶位置数组下标
    };

1.  入栈

//用数组表示堆栈的时候 
    //Top[-1] 表示堆栈空
    void Push(Stack PtrS, ElementType item)//堆栈本身
    { 
        //判断堆栈有没有满 数组范围 [0, MaxSize - 1]
    	if(PtrS -> Top == MaxSize - 1)//表示堆栈全部放满了
    	{ 
    		printf("full");
    		return;
    	}
    	else
    	{ 
            //item 放 Top 上面那个位置
    		PtrS -> Data[++(PtrS -> Top)] = item;
            //(PtrS -> Top)++;
            //PtrS -> Data[PtrS -> Top] = item;
    		return;
    	}
    }

1.  出栈

ElementType Pop(Stack PtrS)
    { 
        if(PtrS->Top == -1){ 
            printf("empty");
            return ERROR;
        }
        else
            //1 先返回下标为Pop的这个值
            //2 Pop减一
            return(PtrS->Data[((PtrS->Pop)--]);
    }

用一个数组实现两个堆栈，要求最大利用数组空间，只要数组有空余空间就能进行入栈操作。

分析：使两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时候，就表示两个栈就满了

#define MaxSize <存储数据元素的最大个数>
    struct DStack{ 
    	ElementType Data[MaxSize];
    	int Top1;
    	int Top2;
    }S;
    S.Top1 = -1;//第一个堆栈为空的条件
    S.Top2 = MaxSize;//第er个堆栈为空的条件
    
    void Push(struct DStack *PtrS, ElementType item, int Tag)
    { 
        //tag 是区分堆栈1和堆栈2 的标志， 取值 1和2
        //堆栈满
        if(PtrS->Top2 - PtrS->Top1 == 1)
        { 
    		printf("full");
            return;
        }
        //第一个堆栈的操作
        if(Tag == 1)
        { 
        	PtrS->Data[++(PtrS->Top1)] = item;    	
        }
        //第二个堆栈操作
        else
        { 
            PtrS->Data[--(PtrS->Top2)] = item;
        }
    }
    
    
    void Pop(struct DStruct *PtrS, ElementType item, int Tag)
    { 
        if(Tag == 1)
        {  //第一个堆栈为空
            if(PtrS->Top == -1)
                printf("full");
        		return NULL;
        	else
            	return PtrS->Data[(PtrS->Top1)--];
        }
        else
        {   
            if(PtrS->Top2 == MaxSize)
                printf("full");
        		return NULL;
            else
                return PtrS->Data[(PtrS->Top2)++];
        }
    }

## 堆栈的链式存储实现 ##

不像数组，在操作使要判断满不满。链表只需要判断是否为空

Top在链表头上

typedef struct SNode *Stack;
    struct SNode{ 
    	ElementType Data;
    	struct SNode *Next;
    };

1） 堆栈初始化（创建空栈）

2） 判断堆栈S是否为空

Stack CreateStack()
    {  
    	//创建堆栈的头结点，返回指针
        //不代表堆栈里的任何元素；主要是方便找到堆栈里的元素
    	Stack S;
    	S = (Stack)malloc(sizeof(struct SNode));
    	return S;
    }
    int IsEmpty(Stack S)
    { 
    	//判断S是否为空，是空 返回1； 否则返回0
    	return (S->Next == NULL)	
    }

1.  Push

**就是往堆栈的头上插入结点**

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

1.  Pop

ElementType Pop(Stack S)
    { 
    	//删除并返回堆栈S的栈顶元素
    	struct SNode *FirstCell;//堆栈的第一个元素;堆栈的Top
    	ElementType TopElem;//堆栈要删除的那个元素， 待会要返回
    	if(IsEmpty(S))
    	{ 
    		printf("stack is empty");
    		return NULL;
    	}
    	else
    	{ 
            //为了释放这个空间
            //先把要删掉的结点赋值给一个变量 ---》 FirstCell
    		FirstCell = S->Next;
            S->Next = FirstCell->Next;//把要删除的结点(FirstCell)的下一个结点给S
            TopElem = FirstCell->Element; //保存要删除的元素，把它赋值给一个变量 ---》TopElem
    		free(FirstCell);
            return TopElem;//返回删除的元素
        }
    }

## 堆栈应用：表达式求值 ##