数据结构---线性结构
线性表
“线性表”：是由同类型数据元素构成有序序列的线性结构
- 表中元素个数称为线性表的长度
- 线性表中没有元素的时候，称为空表
- 表的起始位置称为空表，表的结束位置称为表尾
线性表的顺序存储实现
利用数组的连续存储空间顺序存放线性表的各元素
LAST存储线性表中最后一个元素的位置
线性表的长度为LAST+1
主要操作实现
初始化（建立空的顺序表）
LIST MakeEmpty（） { List Ptrl; Ptrl = (List)malloc(sizeof(struct LNode)); Ptrl ->Last = -1 //-1代表无元素，0代表有一个元素 return Ptrl; }查找
int Find (ELementType X,List Ptrl) { int i = 0; while (i<= Ptrl->Last && Ptrl->DAta[i]!=X) i++; if (i>Ptrl->Last) return -1; //未找到 else return i; // 找到 }插入（第i个位置上插入一个X，实际上是数组中的i-1）
要先把i-1空出来，所以先移动，在插入 ```cvoid Insert (ElementType X,int i ,List Ptrl)
{int j; if (Ptrl->Last == MAXSIZE-1){ print("表满"); return; } if (i<1||i>Ptrl->Last+2){ pint("位置不合法"); return; } for(j = Ptrl->Last;j>=i-1;j--) Ptrl->DAta[j+1] = Ptrl->Data[j];//村后往前移动 Ptrl->Data[i-1] = X; Ptrl->Last++;//Last仍然指向最后一个元素 return;}
4. 删除（删除表中第i位置上的元素） i-1删除掉，并把后面的移动到前面void Delete(int i,List Ptrl){ int j; if(i<1||i>Ptrl->Last+1){ print("不存在这个位置"); return;} for(j=i;j<=Ptrl->Last;j++) Ptrl->Data[j-1] = Ptrl->Data[j];//从i前往后移动 Ptrl->Last--; return; } ```
线性表的链式存储实现
主要操作的实现
求表长
int Length(List Ptrl)//遍历链表来求表长 { List p= Ptrl; int j = 0; while(p){ p=p->Next; j++; } return j; }查找
(1) 按序号查找，找到第K个
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; else return NULL; }(2) 按值查找
List Find(ElementType X,List Ptrl){ List p = Ptrl; while(p!NULL&&p->Data!=X) p=p->Next; return p; }插入
List Insert(ElementType X,int i ,List Ptrl) { List p,s; if(i == 1){ //如果是插在表头，那么返回的就不是原来的表头指针Ptrl了，而是s了。 s = (List)malloc(sizeof(struct LNode)); s->Data = X; s->Next = Ptrl; return s; } p = FindKth(i-1,Ptrl);//找到要插入的前一个的位置 if(p == NULL){ print("参数错误"); return NULL; }else{ s=(List)malloc(sizeof(struct LNode)); s->Data = X; s-Next = p->Next; p->Next = s; return Ptrl; } }删除(删除链表上第i个位置的结点)
List Delete(int i, List Ptrl){ List p,s; 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){ print("节点不存在"); return NULL; }else if(p->Next == NULL){ print("节点不存在"); return NULL; }else{ s=p->Next; p->Next=s->Next; free(s);//删除后一定要释放空间 return Ptrl; } }
广义表
- 广义表是线性表的推广
- 对于线性表而言，n个元素都是基本的单元素
- 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
广义表的定义：
typedef struct GNode *GList;
struct GNode{
int Tag;//标志域，0表示节点是单元素，1表示节点是广义表
union{//字表的指针域与单元素数据域Data复用，即共享存储空间
ElementType Data;
GList SubList;
}URrgion;
GList Next;//指向后继节点
};多重链表
多重链表：链表中的节点可能同时隶属多个链
- 多重链表中的节点的指针域会有多个，如上述所说包含NEXT和SubList 两个指针域
- 但包含两个指针域的链表不一定是多重链表，比如双向链表就不是多重链表
多重链表应用
十字链表存储稀疏矩阵（4行5列7项的稀疏矩阵）
结点的结构：
堆栈
堆栈：具有一定操作约束的线性表
- 只在一端插入，删除
后入先出是其最大的特点
### 栈的顺序存储实现
栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成
入栈
void Push （Stack PtrS, ElementType item) { if (PtrS->Top == MaxSize-1){ print("堆栈满"); return; }else { PtrS->Data[++(PtrS->Top)] = item;//item赋值给Top上面的那个位置 return; } }出栈
ElementTpe Pop(Stack PtrS) { if (Ptrs->Top == -1){ print("堆栈空"); return ERROR; }else return (PtrS->Data[(PtrS->Top)--]);//既能将Top传出去，还能实现Top减一 }
栈的链式存储实现
栈的链式存储结构实际上是一个单链表，叫做链栈。插入和删除操作只能在栈顶操作。所以Top只能指向链头，指向链尾的时候你删了以后你找不到前一个结点了，你就没办法给Top赋值了。
- 判断堆栈为空：
S->Next == NULL
S是指针，指向堆栈的头结点 ，头结点是 不存储数据的，头结点所指向的下一个结点才存储元素。
所以你要注意一点，堆栈上面的用数组实现，top所指的是有元素的;而链表实现的top指的是空的，是没有元素的。入栈
void Push (ElementType item, Stack S) { struct SNode *TmpCell; TmpCell=(struct SNode*)malloc(sizeof(struct SNode)); TmpCell->Element = item; TmpCell->Next = S->Next; S->Next = TmpCell; }出栈
ElementType Pop(Stack S) { struct SNode *FirstCell; ElementType TopElem; if(IsEmpty(s)){ printf("堆栈空"); return NULL; }else{ FirstCell = S->Next; S->Next = FirstCell->Next; TopElem = FirstCell->Element; free(FirstCell); return TopElem; } }
堆栈应用：后缀表达式求值
中缀表达式变为后缀表达式的流程：
从头到尾读取中缀表达式的每个对象，对不同对象按照不同情况处理。
- 运算数：直接输出；
- 左括号：压入堆栈；
- 有括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
运算符：
- 若遇到优先级大于栈顶运算符时，把它压栈；
- 若遇到优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符遇到大于栈顶运算符优先级或者左括号为止，然后将该运算符压栈；
- 若各对象处理完毕，则把堆栈中存留的运算符一并输出。
队列
队列：具有一定操作约束的线性表。
- 先进先出是其最大的特点
队列的顺序存储实现
队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
队列结构：
#define Maxsize
struct QNode{
ELementType Data[MaxSize];
int rear;
int front;
};- front 和 rear等于负1的时候队列为空
- front实际上指向的是头元素的前一个位置，而rear指向的是尾元素
循环队列：就好比把数组首尾相连一样：
- 此时front = rear就代表了队列空
- 为了防止无法区别队列空和队列满所以我们可以：1. 使用额外标记，标记目前使用几个位置。2. 仅使用n-1个数组空间。
- rear+1 = front代表 队列满
入队列：（这里采用仅使用n-1个位置的方法）
void AssQ(Queue PtrQ,ElementType item) { if((PtrQ->rear+1)%MaxSize == PtrQ->front){ print("队列满"); return; } PtrQ->rear = (PtrQ->rear+1)%MaxSize; PtrQ->Data[PtrQ->rear] = item; }出队列：
ElementType DeleteQ(Queue PtrQ) { if(PtrQ->front == PtrQ->rear){ print("队列空"); return ERROR; }else{ PtrQ->front = (PtrQ->front+1)%MaxSize; return PtrQ->Data[PtrQ->front]; } }
队列的链式存储实现
队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行。
front作删除操作，rear做插入操作。所以链表头做front。链表尾做rear。
- front=NULL 队列空
队列结构：
struct Node{
ElementType Data;
struct Node *Next;
};
struct QNode{
struct Node *rear;//指向队尾
struct Node *front;//指向队头
};
出队：
ElementType DeleteQ(Queue PtrQ) { struct Node *FrontCell; ElementType FrontElem; if(PtrQ->front == NULL){ printf("队列空"); return ERROr; } FrontCell = PtrQ->front; if(PtrQ->front == PtrQ->rear)//若队列元素只有一个元素 PtrQ->front = PtrQ->rear = NULL;//删除队列后置空 else PtrQ->front = PtrQ->front->Next; FrontElem = FrontCell->Data; free(FrontCell);//释放被删除的空间 return FrontElem; }
