一、线性表（详细版+习题）

1.线性表的定义

具有一对一的特征。

线性表，全名线性存储结构。

标准定义：由n(n>=0)个数据元素（结点）组成的有限序列。（所有的结点具有相同的数据类型）

2.线性表的基本特点

（1）具有相同的数据类型

（2）元素下标表示该元素在线性表中的位置，但是这个位置仅表示元素的先后关系，并不表示元素之间的大小关系。

（3）a1是线性表的首元素，an是线性表的尾元素，n表示的是元素的个数。

（4）除a1以外，每个元素都有前驱；除an以外，每个元素都有后继，a1.a2,a3,a4，.....，ai-1均是a1的前驱，ai-1是a1的直接前驱ai+1,.ai+2,ai+3,ai+4，......，an均是ai的后继，ai+1是ai的直接后继。

3.线性表的顺序存储

1. 定义

   把线性表中的元素按照先后顺序存储到连续的空间中就是线性表的顺序结构

   a1	a2	a3	a4	a5	a6

   具有相同的数据元素类型，且每个元素占用的内存空间大小是相同的，

   在C语言中，采用数组来表示线性表的顺序结构。

   数组	a1	a2	a3	a4	a5
   下标	0	1	2	3	4

   经典定义方式
   #define MAX_SIZE 100   //数组最大长度
   typedef int ElemType;  //数据类型的别名
   typedef struct sqlist{  //定义线性表结构体
       Elemtype data[MAX_SIZE];//线性表存储元素的数组
       int length; //记录线性表的长度
   }SqList;  //线性表的名称
   //通常情况下length的长度是小于数组的最大长度（即顺序表中元素的个数小于数组的最大长度）
   

2. 顺序表的随机存取(按位置查找)

顺序结构在内存中占有连续的地址空间，顺序表具有随机访问的能力。

数组	1	10	30	4	15	26	27
下标	0	1	2	3	4	5	6
元素大小	4B	4B	4B	4B	4B	4B	4B

数据元素1和数据元素1的地址相差4B。假如给定的数据元素1在内存中的地址是100，则数据元素10的地址就是104（100+14），数据元素30的地址是108（100+24。
推广：
假设线性表在内存中存储时，每个元素占用L个存储空间，则相邻两个元素在内存中存储地址相差L，如果知道第一个元素的内存地址，顺序表中的任意元素地址公式如下：
LOC（ai）=LOC(a1)+（i-1）L

3.顺序表的初始化

SqList* L->data=(ElementType*)malloc(sizeof(ElementType)*MAX_SIZE)
 //分配一个空的数组空间

4.顺序表的查找

int FindBuValue(SqList *L,int e){
	int i;
	for(i = 0;i < L->length;i++){
        if(L->data[i]==e)
            return i+1;
    }
    return -1;
}

5.顺序表的插入

• 将线性表L中的第i个至第n个结点后移一个位置。

• 将结点e插入到结点ai+1之后。

• 线性表长度加1

  
  bool ListInsert(SqList* L,int i, int e){
      if(i < 1 || i > L->length +1)
          return false;
      if（L->length > MAX_SIZE）
          return false;
      for(int j = L->length;j >= i;j--){
          L->data[j] = L->data[j-1];
      }
      L->data[i-1] = e;
      L->lenght++;
      return true;
  }
  

6.顺序表的删除

(1)按元素删除

• 将线性表L中的第i+1个至第n个结点依次向前移动一个位置。

• 线性表长度减1.

  
  bool ListDelete(SqList* L,int i, int e){
    if(L->length == 0 )
        return false;
     if(i < 1 || i > L->length)
         return false;
      e = L->data[i-1];
   	for(int j = i; j < L->length;j++){
  		L->data[j-1] = L->data[j];
      }
      L->length--;
      return true;
  
  

  (2)查找定位删除操作。

  在线性表L=（a1，....，ai-1，ai，ai+1.....，an）中删除值为x的第一个结点，实现步骤如下:

• 在线性表L中查找值为x的第一个数据元素。

• 将从找到的位置至最后一个结点依次向前移动一个位置。

• 线性表长度减1。

  
  bool Locate_Delete_SqList(SqList* L,int x){
      //删除线性表L中值为x的第一个结点
      int i=0,k;
      while(i < L->length){
          if(L->data[i] != x)//查找值为x的结点
              i++;
          else{
              for(k = i+1;k < L->length;k++){
                  L->data[k-1] = L->data[k];
              }
              L->length--;
              break;
          }
      }
      if(i >= L->length){
          printf("要删除的数据元素不存在！\n");
          return false;
      }
      return true;
  }
  

总结：

顺序表具有空间连续、预先分配、查找容易[O(1)，随机查找]、增删难[O(n)，需要移动元素]等特点。

1. 编写算法将两个非递减的有序顺序表A和B合并成一个新的非递减有序顺序表C。已知顺序表A和B的元素个数分别为m和n，其中顺序表采用动态分配空间，定义如下。

Typedef struct{
    Elemtype * elem; //存储空间基地址
    int length;//当前长度
    int listsize;//当前分配的存储容量
}SqList;

解析：
	算法思想：要合并两个有序的顺序表A和B，那么需要开辟一个新的数组空间C，当A和B都未到末尾时，逐个比较A和B的元素，将较小的元素放到C中，若元素相等，只保留一个。当A或B时，将未结束的表的元素逐个放到C中。
	将两个非递减有序顺序表A和B合并成一个新的非递减有序的顺序表C，可以用3个数组分别指向A、B、C 3个数组。数组A、B、C的合并过程及元素的变化如图所示。首先数组A的第0个元素与数组B的第0个元素相比较，发现1 < 4，将1加入顺序表C，i++，k++，插入元素2、3也是如此；当i=3时，数组A的元素5与数组B的元素4作比较，发现5>4，于是将4加入顺序表C，j++,k++;如此比较下去，直到将A表中的元素全部插入到C表中，此时，B表还没有元素没有插入，则直接将B表剩余的元素插入到C表中。

代码实现如下

void Combination(SqList &L1,SqList &L2,SqList &L3){
    int i=0,j=0,k=0;
    while((i!=L1->length)&&(j!=L2->length)){
        if(L1->data[i] > L2->data[i]){//L1中的元素大，合并L2中的元素到L3中
            L3->data[k++] = L2->data[j++];
        }
        else if(L1->data[i] == 2->data[j]{
            // 元素相等，只保留一个，合并到L3中
            L3->data[k++] = L2->data[j++];
            i++;
        }
        else{ //L2中元素大，合并L1中的元素到L3中
            L3->data[k++] = L1->data[i++];
        }
        L3->length++;
    }
    while(i<L1->length){ // L2结束，合并L1中的元素到L3中
        L3->data[k++] = L1->data[i++];
        L3->length++;
    }
     while(j<L2->length){ // L1结束，合并L2中的元素到L3中
         L3->data[k++] = L2->data[j++];
         L3->length++;
     }
}

2.实现顺序表的就地逆序

int ListOppose(SqList &L){
    int i;
    ElemType x;
    //只需要遍历原表的一半就可以实现数据元素位置的交换
    for(i=0;i < L->length/2;i++){
        x = L->data[i];
        L->data[i] = L->data[L->length-i-1]; // 数据元素交换 ——>逆置
        L->data[L->length-i-1] = x;
    }
    return 1;
}

3.设计一算法将正数与负数分开，且负数在正数的前面。

// 左右指针法
int ReArrange(SqList &a,int n){
	int low = 0,high = n-1;
    int t = a[low];// 枢轴元素，只是暂存，不作为比较对象
    while(low < high){
        while(low < high && a[high] >= 0)//寻找小于0的元素
            high--;
        a[low] = a[high]
        while(low < high && a[low] <= 0)//寻找小于0的元素
            low++;
        a[high] = a[low];
    }
    a[low] = t;// 将枢轴元素放到最终位置 
}

4.线性表的链式存储

1.单链表的定义

单链表的结构

data	next

data:数据域，用来存储数据信息

next:指针域，用来存储直接后继的地址信息。

#define ElemType int
typedef struct LNode{
    Elemtype data;   //存放元素值
    struct LNode *next;// 指向后继结点
}LNode,*Linklist;// 单链表结点类型

	单链表要有个头（起始位置），一般把第一个结点称为第一数据结点，为了操作方便，会在单链表的第一个数据结点前附加一个结点，这个结点称为头结点，它不存储信息或者只存储单链表的长度，头结点的指针域存储的是指向第一个数据结点的指针。
	头指针指向头结点，头结点的指针域指向第一个数据结点。

3.单链表的操作

// 结点的创建代码如下
LNode *p; // 函数malloc分配了一个类型为LNode的结点变量的空间 
p = (LNode*)malloc(sizeof(LNode));
p->data = 20;
p->next = NULL;

p = q->next // 赋值为直接后继结点
p = p->next// 指针向后移动

在指针p后面插入指针q。

1. 找前驱
2. 防断链

//1.
q-next = p->next;
//2.
p-next = q;

删除指针p的直接后继。

1. 找前驱
2. 找断链

q = p-next;
p->next = q->next;
free(q);

4.单链表的头结点

第一个结点：

1. 有

   head-next = node
   

2. 无

   head = node;
   

5.单链表的创建

1. 头插法创建单链表。

Linkklist Creat_list(Linklist head){
    head = (Linklist)malloc(sizeof(LNode));//为指针开辟内存空间
    LNode* node = NULL;// 定义工作指针
    int count = 0;//创建结点的个数
    head->next = =NULL;
    node = head-next;// 将最后一个结点的指针域永远保持为NULL
    scanf("%d",&count);
    for(int i = 0;i < count;i++){
        node = (LNode*)malloc(sizeof(LNode));// 为新节点开辟内存空间
        node->data = i;//为新节点的数据域
        node->next = head-next;// 将头指针所指向的下一个节点的地址，赋新的创建接点的next
        head->next = node;//将新创建的结点的地址赋值给头指针的下一个结点 
    }
    return head;
}

元素的先后顺序与结点的先后顺序是相反的

头插法逆序

2.尾插法建立单链表

Linklist Creat_list(Linklist head){
    head = (Linklist)malloc(sizeof(LNode));
    Linklist node = NULL;
    Linklist end = NULL;
    head->next= NULL;
    end = head;//为创建其余结点之前，只有一个头结点
    int count = 0;
    scanf("%d",&count);
    for(int i = 0;i < count;i++){
        node = (LNode*)malloc(sizeof(LNode));
        node->data = i;//新结点的数据域赋值
        end->next = node;//新结点赋给end的下一个
        end = node;//新结点成为新的尾结点
    }
    end->next = NULL;
    return head;
}

把新来的结点依次插到单链表的末尾。

总结：头逆尾顺

6.单链表的查找

1. 按序号查找：取单链表中的第i个元素。

bool GetElem_L(LinkList &L,int i,ElemType &e){
    // L为带头结点的单链表的头指针
    //当第i个元素存在时，其赋值给e并返回true;否则，返回false
    LNode *p;	//p为工作指针
    p = L->next;
    int j = 1;
    //找位置
    while(p &&j < i){  // (p!=null)==(p)
        p = p->next;
        ++j;	//j++也可以
    }
    //
    if(!p || j>i)
        return false;
    e = p->data;
    return true;
}

2.按值查找

LNode *Locate_Node(LNode *L,int key){
    //在以L为头结点的单链表中查找值为key的第一个结点
    LNode *p = L->next;
    while(p != NULL && p->data != key){
        p = p->next;
    }
    if(p->data == key){
        return p;
	}
    else{
        printf("所要查找的结点不存在!!\n");
        return NULL;
    }
}

7.单链表插入元素

插入的两件事：

1. 找前驱
2. 防断链

bool ListInsert_L(LinkList &L,ElemType e){
    //在带头结点的单链线性表L中第i个位置之前插入元素
    LNode *p = L;//头结点
    int j = 0;
    while(p && j < i-1){//寻找第i-1个结点的位置的过程
        p = p->next;
        ++j;
    }	//寻找第i-1个结点
    if(!p || j > i-1)
        return false;
    //执行插入操作
    //创建
    LNode *s;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    //插入
    s->next = p->next;
    p->next = s;
    return true;
}

8.单链表删除元素

1. 按序号删除：删除单链表中的第i个结点。

• 找前驱
• 防断链

bool ListDelete_L(LinkList &L,int i,ElemType &e){
    //在带头结点的单链表L中，删除第i个元素，并由e返回其值
    LNode *p;//工作指针，p->next即为被删除的元素
    LNode *q;//被删除的元素
    p = L;
    int j = 0;
    while(p->next && j < i-1){//寻找第i个结点，并令p指向其前驱
        p = p->next;
     ++j;
    }
    if(!(p-next) || j > i-1)
        return false;//删除位置不合理
    q = p->next;
    p->next = q->next;//删除并释放结点
    e = q->data;
    free(q);
    return true;
}

2.按值删除。删除单链表中值为key的第一个结点。

//算法描述
bool Delete_LinkList(LNode *L,int key){
    //删除以L为头结点的单链表值为key的第一个结点
    LNode *p = L, *q = L->next;
    while(q != NULL && q->data != key){
        p = q;
        q = q->next;
    }
    if(q->data == key){
        p->next = q->next;
        free(q);
    }else{
        printf("NULL\n");
    }
}
//删除所有值为key的结点
    while(q != NULL){
        if(q->data != key){
             p = q;
        	 q = q->next；
        }else{
            p->next = q->next;
            free(q);
            p->next = q;
        }
    }
//去重，将单链表中值相同的元素均去掉 

9.访问所有元素

从头到尾依次遍历，输出各个元素的值

void printL(LinkList L){
	LNode *p;
    p = L->next;
    while(p !=NULL){
        printf("%d",p->data);
        p = p->next;
    }
}

1. O(n),基于线性查找的技术：顺序操作。
2. 基于工作指针的操作：要指向单链表中的每个元素且确保工作指针不为零。
3. 工作指针的初始化略微不同。

练习题：

1.给定键值按升序排列的带头结点的单链表La和Lb，将其合并成升序排列的单链表，并返回新链表的表头指针。要求利用原表的结点数据空间

LNode *Merge_LinkList(LNode *La,LNode* Lb){
	//合并以La、Lb为头结点的两个有序单链表
    LNode *Lc,*pa,*pb,*pc,*ptr;
    Lc = La;
    pc = La;
    pa = La->next;
    pb = Lb->next;
    while(pa != NULL && pb != NULL){
        if(pa->data < pb->data){
            pc-next = pa;
            pc = pa;
            pa = pa->next;
        }
        //将pa所指向的结点合并，pa指向下一个结点
        else if(pa->data > pb->data){
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        //将pb所指的结点合并，pb指向下一个结点
        else if(pa->data == pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            ptr = pb;
            pb = pb->next;
            free(ptr);
        }
        //将pa所指的结点合并，pb所指结点删除
    }
    if(pa != NULL){
        pc->next = pa;
    }
    else{
        pc->next = pb;//将剩余的结点链接上
    }
    free(Lb);
    return Lc;
}


/*
思路：
1、让其中一个表与另一个表里面的元素挨个比较。
问题：
	(1)、未充分利用已知条件；两个表均未被充分利用
	(2)、回溯，时间复杂度（O（n*n））
2、变化法：让两个表连接在一起，整体排序（时间复杂度（O（n*log2n））
3、双指针不回溯
升序：尾插法（谁小谁后移，谁小谁尾插）
降序：头插法（谁小谁后移，谁小谁头插）
头逆尾顺
 时间复杂度为O(m+n)。
*/

2.删除单链表中所有值重复的结点，使得所有结点的值都不相同。

/*
解析：
基本思想：
从单链表的第一个结点开始，对每个结点进行检查，检查链表中该结点的所有后继结点，只要有结点的值和该结点的值相同，就删除；然后检查下一个结点，知道所有的结点都检查过
*/
void Delete_Node_value(LNode *L){
    //删除以L为头结点的单链表中所有值相同的结点
	LNode *p = L->next,*q,*ptr;
    while(p != NULL){//检查链表中所有结点
        q = p;
        ptr = p->next;
        //检查结点p的所有后继结点ptr
        //删除值为key(p->data)的所有结点
        while(ptr != NULL){
            if(ptr->data == p->data){
                q->next = ptr->next;
                free(ptr);
                ptr = q->next
            }
            else{
                q = ptr;
                ptr = ptr->next;
            }
            p = p->next;
        }
    }
}

3.试写出逆转线性单链表的算法，单链表结点的类型定义如下。

就地逆序：头逆尾顺

解析：基本思想：要实现链表的就地逆序，可以采用头插法借助原有节点的存储空间采用头插法建立新的单链表。

Typedef struct node{
    elemtype data;//数据域
    struct node *next;//指针域
}LNode,*Linklist;

LNode *revert_list(LNode *head){
    if(NULL == head->next){
        return head;
    }
    LNode *p = head->next;
    head->next = NULL;
    LNode *tmp = NULL;
    while(p){
        tmp = p->next;
        p->next = head->next;
        head->next = p;
        p = tmp;
    }
    return head;
}

4.已知线性表中的元素以值递增有序的方式排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删除的结点空间。（注意：mink和maxk是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同。）

/*
解析：
从表头开始，从前往后遍历链表，每走过一个结点，看看这个结点的值是否位于mink和maxk之间，如果在此区间就删除该结点。注意，在删除时，一定要保证不能断链，其方式是用一个指针保存被删除的结点的直接前驱。
*/
bool DeleteMiddleElem(LinkList &L,int mink,int maxk){
    //删除单链表中大于mink和maxk之前的数据元素
    LinkList p,q,prev = NULL;
    if(mink > maxk){
        return ERROR;//mink、maxk大小不合法
    }
    p = L;
    prev = p;//prev指向头结点
    p = p->next;//为了保证prev是指向p的直接前驱结点
    //只需要遍历从头结点到data域为maxk结点的数据元素
    while(p && p->data < maxk){
        if(p->data < mink){
            prev = p;//prev指向第1个data域大于等于mink的结点
            p = p->next;
        }
        else{//data域大于mink
            prev->next = p->next;//prev指向p的直接后继结点。
            q = p;
            p = p->next;
            free(p);//释放内存空间
        }
    }
    return true;
}

5.一直带头结点的单链表有data和next两个域，设计一个算法，将该链表中的重复元素的结点删除。例如将（7,10,10,21,30,42,42,42,51,70）变为（7,10,21,30,42,51,70）

6.已知非空线性链表由list提出，链结点的构造为（data，next）。请写出一算法，将链表中的数据域值最小的那个结点移到链表的最前面。要求不额外申请新的链接点。

void minMoveFirset(LinkedList head){
    LinkedList min;//最小结点
    LinkedList premin;//最小结点的前驱结点
    LinkedList pre;//前驱结点
    LinkedList cur;//当前结点
    if(NULL == head){//空链表直接返回
        return;
    }
    pre = head;
    cur = head->next;
    premin = pre;
    min = cur;
    while(cur){
        if(min->data > cur->data){
            premin = pre;
            min = cur;
        }
        pre = cur;//记录前驱结点
        cur = cur->next;//当前结点后移
    }
    //头插
    premin->next = min->next;
    min->next = head->next;
    head->next = min;
}

4.设有一个带头结点的单链表 hc,其结点值序列为(a,b,a,be,…,a,b)(n>1,且 a,b成对出现),设计一个算法 void decompose(LinkedList ha,LinkedList hb,LinkedList he),将 he 拆分成两个带头结点的单链表 ha 和 hb,其中 ha 的结点值序列为(a, ,a,…,a),hb的结点值序列为(b,b-,…,b),要求ha利用原hc的头结点,算法的空间复杂度为O(1)。

void decompose(LinkedList ha,LinkedList hb,Linklist hc){
    hb = (LinkedList)malloc(sizeof(LNode));
    ha = (LinkedList)malloc(sizeof(LNode));
    LinkedList p,q,tail;
    p = ha->next;
    q = hb;
    tail = hc;
    int j = 1;
    while(p){
        if(j % 2 != 0){
            q->next = p;
            q = q->next;
        }else{
            tail->next = p;
            tail = tail->next;
        }
        j++;
        p = p->next;
    }
}

8.给定两个单链表（假设两个链表均不含有环）的头指针分别为head1和head2，请设计一个算法发判断这两个单链表是否相交，如果相交就返回第一个交点，要求算法的时间复杂度为O（length1+length2），其中lenght1和length2分别为两个单链表的长度。

LinkList SearchFirst(LinkList L1,LinkList L2){
    //获取两个链表的长度
    int len1 = getLength(L1);
    int len2 = getLength(L2);
    //用于指向较长和较短链表的第一个结点
    LinkList longlist,shortlist;
    if(len1 > len2){
        longlist = L1->next;
        shortlist = L2->next;
        int dist = len1 - len2;
    }else{
        longlist = L2->next;
        shortlist = L1->next;
        int dist = len2 - len1;
    }

    while(dist--){
        longlist = longlist->next;
    }
    while(longlist != NULL){
        if(longlist == shortlist){
            return longlist;
        }else{
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }
    //没有公共结点
    return NULL;
 }

二、栈

1.栈的基本概念

1.栈的定义和术语

先进后出，后进先出

栈顶：

栈底：

栈顶元素：

给定n个元素，出栈顺序满足卡特兰数，计算公式为：

2.栈的顺序结构

栈是操作受限的线性表，采用顺序结构存储的栈称为顺序栈，用一维数组来存储。

1. 动态顺序栈

   采用动态一维数组来存储的栈称为动态顺序栈。所谓动态，是指栈的大小可以根据需要来增加空间。

   （用bottom表示栈底指针，栈底是固定不变的；用top（称为栈顶指针）指示当前栈顶位置，栈顶随着进栈和退栈操作而变化）

   动态顺序栈类型定义：

   #define STACK 100 //栈初始数组大小
   #define STACKINCREMENT 10//存储空间分配增量
   typedef int ElemType;
   typedeg struct sqstack{
       ElemType *bottom;//栈不存在时，值为NULL
       ElemType *top;//栈顶指针
       int stacksize;//当前已分配空间，以元素为单位
   }sqstack,*SqStack;
   

   2.静态顺序栈

3.栈的链式结构

4.栈的应用